速度精度比較
速度（と一部アルゴリズムの精度）を比較します。Scikit-learnの対応するアルゴリズムを比較対象とします。
注意点
FortLearnerは
- 自分がコードとしてどう動くか確認したい（大雑把にせつめいできるようになりたい）
- いろんなアルゴリズムを学んでみたい（なるべく多くのことなるアルゴリズムの実装がしたい）
- 自分がどれくらい速くできるかやってみたい。とりあえず速ければいい（Sklearnをベンチマーク的にあつかう）
という考えのもとに作成しています。したがって、
- アルゴリズムの理論的な理解
- 保守性、拡張性、可読性
- もっと低レイヤーまで意識した高速化
などは基本的に抜け落ちています。
データセットについて
sklearn.dataset.make_regression と sklearn.dataset.make_regression で、行数と列数を変更しながら作成したものを用います。
UCIからFortLearnerが適用できるデータセットをダウンロードしてくるスクリプトを書いているので、今後どこかで試したいと思います。
測定単位
時間はすべて秒です。
メトリックはいろいろです。
DecisionTreeRegressor
回帰問題のみを比較しています。ソート関数を置き換えたため高速化されています。非常に重かったので、ほかの計測では実施している条件は計測していません
DecisionTreeRegressor(max_leaf_node=100)
| Data: shape(#Row, #Col) | sklearn | FortLearner |
|---|---|---|
| sklearn.datasets.make_regression: (100, 10) | 0.0018 | 0.0001 |
| sklearn.datasets.make_regression: (100, 50) | 0.0030 | 0.0005 |
| sklearn.datasets.make_regression: (100, 100) | 0.0049 | 0.0010 |
| sklearn.datasets.make_regression: (100, 200) | 0.0018 | 0.0020 |
| sklearn.datasets.make_regression: (100, 400) | 0.0083 | 0.0038 |
| sklearn.datasets.make_regression: (1000, 10) | 0.0146 | 0.0032 |
| sklearn.datasets.make_regression: (1000, 50) | 0.0064 | 0.0150 |
| sklearn.datasets.make_regression: (1000, 100) | 0.0485 | 0.0321 |
| sklearn.datasets.make_regression: (1000, 200) | 0.0897 | 0.0597 |
| sklearn.datasets.make_regression: (1000, 400) | 0.1980 | 0.1306 |
| sklearn.datasets.make_regression: (10000, 10) | 0.0602 | 0.0496 |
| sklearn.datasets.make_regression: (10000, 50) | 0.2840 | 0.2430 |
| sklearn.datasets.make_regression: (10000, 100) | 0.5910 | 0.4792 |
| sklearn.datasets.make_regression: (10000, 200) | 1.2000 | 0.9520 |
| sklearn.datasets.make_regression: (10000, 400) | 2.6800 | 1.9672 |
| sklearn.datasets.make_regression: (100000, 10) | 0.7800 | 0.5880 |
| sklearn.datasets.make_regression: (100000, 50) | 4.2300 | 2.9030 |
| sklearn.datasets.make_regression: (100000, 100) | 8.5200 | 5.5040 |
| sklearn.datasets.make_regression: (100000, 200) | 17.4000 | 11.1570 |
| sklearn.datasets.make_regression: (100000, 400) | 32.5000 | 22.0870 |
| sklearn.datasets.make_regression: (1000000, 10) | 11.1000 | 6.2800 |
| sklearn.datasets.make_regression: (1000000, 50) | 54.8000 | 29.9560 |
| sklearn.datasets.make_regression: (1000000, 100) | 115.0000 | 59.5610 |
ExtraTreeRegressor
回帰問題のみを比較しています。右端の列は速い23日目で紹介したget_minmax_matrixとget_matrix_count_and_sum_upを利用した実装です。列数が大きいほうがメモリ連続アクセスができる範囲が長いため、より効果的になっています。
ExtraTreeRegressor(max_leaf_node=100)
| Data: shape(#Row, #Col) | Sklearn | FortLearner | FortLearner_faster |
|---|---|---|---|
| sklearn.datasets.make_regression: (100, 10) | 0.00179 | 0.0036 | 0.00075 |
| sklearn.datasets.make_regression: (100, 50) | 0.00271 | 0.01733 | 0.00094 |
| sklearn.datasets.make_regression: (100, 100) | 0.00359 | 0.03132 | 0.0009 |
| sklearn.datasets.make_regression: (100, 200) | 0.00545 | 0.05712 | 0.00127 |
| sklearn.datasets.make_regression: (100, 400) | 0.00921 | 0.11181 | 0.00206 |
| sklearn.datasets.make_regression: (1000, 10) | 0.00269 | 0.00909 | 0.00189 |
| sklearn.datasets.make_regression: (1000, 50) | 0.0063 | 0.04195 | 0.00208 |
| sklearn.datasets.make_regression: (1000, 100) | 0.0108 | 0.08839 | 0.00283 |
| sklearn.datasets.make_regression: (1000, 200) | 0.0196 | 0.16653 | 0.0042 |
| sklearn.datasets.make_regression: (1000, 400) | 0.0396 | 0.33765 | 0.00667 |
| sklearn.datasets.make_regression: (10000, 10) | 0.0084 | 0.0148 | 0.0043 |
| sklearn.datasets.make_regression: (10000, 50) | 0.0408 | 0.0763 | 0.0078 |
| sklearn.datasets.make_regression: (10000, 100) | 0.0813 | 0.1446 | 0.0142 |
| sklearn.datasets.make_regression: (10000, 200) | 0.188 | 0.3053 | 0.0291 |
| sklearn.datasets.make_regression: (10000, 400) | 0.403 | 0.6191 | 0.0498 |
| sklearn.datasets.make_regression: (100000, 10) | 0.0942 | 0.0784 | 0.0456 |
| sklearn.datasets.make_regression: (100000, 50) | 0.502 | 0.3368 | 0.1312 |
| sklearn.datasets.make_regression: (100000, 100) | 1.08 | 0.7288 | 0.2162 |
| sklearn.datasets.make_regression: (100000, 200) | 2.05 | 1.304 | 0.3646 |
| sklearn.datasets.make_regression: (100000, 400) | 3.72 | 2.6974 | 0.559 |
| sklearn.datasets.make_regression: (1000000, 10) | 1.36 | 0.862 | 0.658 |
| sklearn.datasets.make_regression: (1000000, 50) | 5.91 | 3.1822 | 1.38 |
| sklearn.datasets.make_regression: (1000000, 100) | 11.6 | 5.9278 | 2.204 |
| sklearn.datasets.make_regression: (1000000, 200) | 28 | 17.0186 | 4.44 |
| sklearn.datasets.make_regression: (1000000, 400) | 55.4 | 26.56 | 6.163 |
CLOUDS: Histogram-Based Algorithm
ヒストグラムベースアルゴリズムの比較です。CLOUDSとLawuはFortLearnerの実装の時間です。Lawuはこちらの13ページを参考にして実装したものです。ビニングの時間を入れると遅くなってしまいます。ただ、SklearnのHistGradientBoostingRegressorもビニングの時間が入っているはずなのですが、そこまで遅くありません。もしかしたらビニングをソート関数を適用してからやっていることでFortLearner実装は遅くなっているかも可能性があります。クイックセレクトを使うべきだとおもうので、差し替えたいと思います。
| Data: shape(#Row, #Col) | HistGradientBoostingRegressor | CLOUDS w/ bining | CLOUDS w/o bining | Lawu w/o bining |
|---|---|---|---|---|
| sklearn.datasets.make_regression: (100, 10) | 0.00338 | 0.001392 | 0.000872 | 0.000634 |
| sklearn.datasets.make_regression: (100, 50) | 0.00725 | 0.004112 | 0.003157 | 0.002543 |
| sklearn.datasets.make_regression: (100, 100) | 0.0148 | 0.011865 | 0.009278 | 0.006655 |
| sklearn.datasets.make_regression: (100, 200) | 0.0269 | 0.027636 | 0.021656 | 0.0171 |
| sklearn.datasets.make_regression: (100, 400) | 0.0416 | 0.051128 | 0.040552 | 0.035 |
| sklearn.datasets.make_regression: (1000, 10) | 0.0229 | 0.00712 | 0.00586 | 0.00341 |
| sklearn.datasets.make_regression: (1000, 50) | 0.0708 | 0.06052 | 0.02927 | 0.041 |
| sklearn.datasets.make_regression: (1000, 100) | 0.135 | 0.1435 | 0.11259 | 0.1016 |
| sklearn.datasets.make_regression: (1000, 200) | 0.231 | 0.30134 | 0.25577 | 0.238 |
| sklearn.datasets.make_regression: (1000, 400) | 0.374 | 0.37187 | 0.26937 | 0.18178 |
| sklearn.datasets.make_regression: (10000, 10) | 0.069 | 0.0181 | 0.0123 | 0.0162 |
| sklearn.datasets.make_regression: (10000, 50) | 0.21 | 0.0805 | 0.0582 | 0.06 |
| sklearn.datasets.make_regression: (10000, 100) | 0.37 | 0.1808 | 0.116 | 0.1084 |
| sklearn.datasets.make_regression: (10000, 200) | 0.786 | 0.4272 | 0.2427 | 0.2259 |
| sklearn.datasets.make_regression: (10000, 400) | 1.3 | 0.8592 | 0.56 | 0.5131 |
| sklearn.datasets.make_regression: (100000, 10) | 0.299 | 0.298 | 0.095 | 0.18 |
| sklearn.datasets.make_regression: (100000, 50) | 1.2 | 1.17 | 0.203 | 0.357 |
| sklearn.datasets.make_regression: (100000, 100) | 2.44 | 2.189 | 0.365 | 0.461 |
| sklearn.datasets.make_regression: (100000, 200) | 5.11 | 4.572 | 0.58 | 0.931 |
| sklearn.datasets.make_regression: (100000, 400) | 11.4 | 9.312 | 1.332 | 1.911 |
| sklearn.datasets.make_regression: (1000000, 10) | 1.43 | 3.929 | 0.938 | 1.704 |
| sklearn.datasets.make_regression: (1000000, 50) | 4.96 | 12.517 | 1.772 | 3.148 |
| sklearn.datasets.make_regression: (1000000, 100) | 9.91 | 24.866 | 2.399 | 7.036 |
| sklearn.datasets.make_regression: (1000000, 200) | 26.6 | 50.76 | 5.852 | 8.149 |
| sklearn.datasets.make_regression: (1000000, 400) | 47.8 | 139.545 | 14.76 | 21.268 |
Kmeans
Kmeansは同じ異なるデータセットで測定しています。こちらは全く高速化ができていません。ElkanやHarmelyを適用した場合（Sklearnもですが）も確認してみたいと思います。
| Data: shape(#Row, #Col) | #Cluster | SK: KM | FL: KM_naive | FL: KM_fast |
|---|---|---|---|---|
| YearPredictionMSD: (412206, 90) | 2 | 0.757(±0.0128) | 1.202(±0.247) | 0.628(±0.105) |
| YearPredictionMSD: (412206, 90) | 3 | 1.47(±0.0180) | 3.260(±1.865) | 1.880(±0.61) |
| YearPredictionMSD: (412206, 90) | 4 | 2.56(±0.128) | 2.867(±0.599) | 1.725(±0.649) |
| YearPredictionMSD: (412206, 90) | 5 | 3.54(±0.0335) | 6.573(±3.428) | 3.08(±1.523) |
| YearPredictionMSD: (412206, 90) | 10 | 7.4(±0.0106) | 20.986(±7.226) | 11.457(±3.693) |
| YearPredictionMSD: (412206, 90) | 15 | 13.3(±1.29) | 38.954(±10.945) | 21.025(±7.5) |
| YearPredictionMSD: (412206, 90) | 20 | 22.5(±1.91) | 55.788(±19.302) | 34.358(±12.222) |
| YearPredictionMSD: (412206, 90) | 25 | 24.1(±3.1) | 98.84(±34.977) | 55.001(±23.099) |
| YearPredictionMSD: (412206, 90) | 30 | 29.1(±1.42) | 157.163(±52.773) | 82.906(±25.715) |
| YearPredictionMSD: (412206, 90) | 35 | 34.0(±0.646) | 184.827(±58.211) | 99.948(±31.88) |
IsolationForest
異常検知は精度検証が難しいですが、ラベル付きデータセットから作成されたものを流用しています。いくつか見つけた方法でさくせいしたのですが、どのような基準で作成されたかは理解できていません。AUCで評価しています。異常なサンプルにはラベル1、通常サンプルには０が割り振られていますが、モデルが出力した異常スコアで降順ソートした際にスコアが高いほうにラベル１が多いほどAUCは1に近くなります。ランダムでは0.5をとります。精度が高くなっている部分があるのはランダム性のためにそうなっていることもあるかなというところですが、速度が異常に高速（100倍～500倍）になっている点が非常に気になっている点です。精度が同程度なので、致命的な間違いはないと思うのですが。
IsolationForest(n_estimators=1000, max_samples=256)
http://odds.cs.stonybrook.edu/forestcovercovertype-dataset/
| dataset | Train/Test | #Samples | #Columns | FortLearner_train[sec] | Sklearn_train[sec] | FortLearner_predict[sec] | Sklearn_predict[sec] | FortLearner_AUC | Sklearn_AUC |
|---|---|---|---|---|---|---|---|---|---|
| kdd | Train | 240000 | 40 | 0.06 | 32.6 | 2.5 | 64 | 0.884 | 0.793 |
| kdd | Test | 28517 | 40 | - | - | 0.55 | 17 | 0.885 | 0.790 |
| forest_cover | Train | 120000 | 10 | 0.2 | 22.5 | 15 | 94 | 0.894 | 0.887 |
| forest_cover | Test | 46048 | 10 | - | - | 2.7 | 17 | 0.890 | 0.881 |
一部のアルゴリズムのみですが、処理時間の計測結果を記載しました。上記の計測結果は前のPCで計測したものですし、精度も併せて記載したかったのですが、全部やると多分数日かかりそうなので、今回はここまでとしたいと思います。
異常