GridSearchCV 和时间复杂度

数据挖掘 网格搜索 时间复杂度
2022-03-04 12:18:06

因此,我正在学习并尝试实现 GridSearch。我对我写的以下代码有疑问:

from sklearn.metrics import make_scorer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV

dtc = DecisionTreeClassifier(random_state = 42, max_features = "auto", class_weight = "balanced")
clf = AdaBoostClassifier(base_estimator= dtc, random_state= 42)

parameters = {'base_estimator__criterion': ['gini', 'entropy'],
      'base_estimator__splitter': ['best', 'random'],
      'base_estimator__max_depth': list(range(1,4)),
      'base_estimator__min_samples_leaf': list(range(1,4)),
      'n_estimators': list(range(50, 500, 50)),
      'learning_rate': list(range(0.5, 10)),
      }

scorer = make_scorer(fbeta_score, beta=0.5)

grid_obj = GridSearchCV(clf, parameters, scoring=scorer, n_jobs= -1)

grid_fit = grid_obj.fit(X_train, y_train)

best_clf = grid_fit.best_estimator_

predictions = (clf.fit(X_train, y_train)).predict(X_test)
best_predictions = best_clf.predict(X_test)

因此,我正在学习并尝试实现 GridSearch。我对我写的以下代码有疑问:

from sklearn.metrics import make_scorer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV

dtc = DecisionTreeClassifier(random_state = 42, max_features = "auto", class_weight = "balanced")
clf = AdaBoostClassifier(base_estimator= dtc, random_state= 42)

parameters = {'base_estimator__criterion': ['gini', 'entropy'],
          'base_estimator__splitter': ['best', 'random'],
          'base_estimator__max_depth': list(range(1,4)),
          'base_estimator__min_samples_leaf': list(range(1,4)),
          'n_estimators': list(range(50, 500, 50)),
          'learning_rate': list(range(0.5, 10)),
          }

scorer = make_scorer(fbeta_score, beta=0.5)

grid_obj = GridSearchCV(clf, parameters, scoring=scorer, n_jobs= -1)

grid_fit = grid_obj.fit(X_train, y_train)

best_clf = grid_fit.best_estimator_

predictions = (clf.fit(X_train, y_train)).predict(X_test)
best_predictions = best_clf.predict(X_test)

这是矫枉过正吗?我的意思是,我有一台不错的 PC,或者至少我认为它还不错,但是这段代码运行了 5 个多小时,而且......它没有!我不得不停止它并为 GridSearch 编写一个参数更少的更简单的版本,以便它运行并提供一些结果。更简单的版本如下:

parameters = {'base_estimator__splitter': ['best'],
      'base_estimator__max_depth': [2, 3, 5],
      'n_estimators': [100, 250, 500],
      'learning_rate': [1.0, 1.5, 2.0],
      }

花了20分钟。

我对 GridSearch 了解不多,我认为代码一切都很好,我的意思是它没有错误,所以它没有提供任何结果,因为它没有结束运行......关于时间有什么好的参考吗运行网格搜索的复杂性,特别是在运行 AdaBoost 的参数时?我对此没有直觉,并且在 3 或 4 小时后,我不确定问题是否是我的 PC 不够强大,或者代码将永远运行,因为我确实写错了东西或其他任何东西。但是自从我改变了,一切都很好,所以问题一定是时间。有人告诉我运行 RandomizedSearch,直到昨天我才听说过。它可以是一个解决方案。但这总是 GridSearch 的问题吗?是否有任何代码可以帮助我告诉我算法搜索了多少参数或类似的东西?因为看着屏幕和时钟并意识到已经过去了 5 个小时,我不知道它会运行多长时间,或者即使它有一天会完成......

1个回答

没有困难的时间复杂度问题,您只需要了解做什么GridSearchCV,它就会澄清一切。其实很简单:

sklearn 文档说它GridSearchCV执行“对估计器的指定参数值的详尽搜索”。穷举搜索意味着算法简单地迭代搜索空间中的所有可能性搜索空间由参数值的所有组合组成,即:

  • base_estimator__criterion: 2,
  • base_estimator__splitter: 2,
  • base_estimator__max_depth: 3,
  • base_estimator__min_samples_leaf: 3,
  • n_estimators: 9,
  • learning_rate: 我不知道,因为range(0.5, 10)给出了一个错误,比如说 5。

现在这给了我们个参数组合。默认情况下使用 5-fold CV,因此该函数将训练模型并评估它次。当然,所花费的时间取决于数据的大小和复杂性,但即使单个训练/测试过程只需要 10 秒,仍然大约需要 81000 秒 = 1350 百万 = 22.5 小时。223395=1620GridSearchCV16205=8100

相比之下,您的第二组参数仅包含组合。由于需要 20 分钟,我们可以估计单个组合(完整的 CV)需要 0.7 百万次运行。这意味着在上述第一种情况下,整个过程(大约)需要 mn = 20 小时。333=271620.7=1200

通常的解决方案是:

  • 减少组合的数量,就像你在第二种情况下所做的那样
  • 将过程与n_jobs参数并行化,这将大致将时间除以当然,它仅在您有多个内核并且您不打算在此期间使用它们时才有效;)n