ICDM の選択: データ マイニングの代表的なアルゴリズム トップ 10

2006 年 12 月、国際的に有名な学術組織である IEEE 国際データマイニング会議 (ICDM) は、データマイニング分野の上位 10 の古典的なアルゴリズムとして、C4.5、k-Means、SVM、Apriori、EM、PageRank、AdaBoost、kNN、Naive Bayes、CART を選択しました。

選ばれた上位 10 個のアルゴリズムだけでなく、実際に選択に参加した 18 個のアルゴリズムのいずれもが古典的なアルゴリズムと呼べるもので、データ マイニングの分野に大きな影響を与えてきました。

1. C4.5

C4.5 アルゴリズムは、機械学習アルゴリズムにおける分類決定木アルゴリズムです。その中核となるアルゴリズムは ID3 アルゴリズムです。C4.5 アルゴリズムは ID3 アルゴリズムの利点を継承し、次の点で ID3 アルゴリズムを改善しています。

1) 情報ゲイン率を使用して属性を選択すると、多くの値を持つ属性を選択する傾向がある属性を選択するために情報ゲインを使用する欠点が克服されます。

2) 樹木構築中の剪定

3) 連続属性を離散化する能力

4) 不完全なデータを処理する能力。

C4.5 アルゴリズムには、生成された分類ルールが理解しやすく、精度率が高いという利点があります。欠点は、ツリーを構築するプロセスで、データセットを複数回スキャンして順番にソートする必要があり、アルゴリズムの非効率性につながることです。

2. k平均法アルゴリズム

k-means アルゴリズムは、n 個のオブジェクトをその属性に応じて k 個のパーティションに分割するクラスタリング アルゴリズムです (k < n)。これは、データ内の自然なクラスターの中心を見つけようとする点で、正規分布の混合に対する期待最大化アルゴリズムと非常によく似ています。オブジェクト属性は空間ベクトルから得られるものと想定し、各グループ内の平均二乗誤差の合計を最小化することを目標とします。

3. サポートベクターマシン

サポートベクターマシンは、英語ではSupport Vector Machineと呼ばれ、SVマシンと略されます（論文では一般的にSVMと呼ばれます）。これは、統計的分類や回帰分析で広く使用されている教師あり学習法です。サポート ベクター マシンは、ベクトルを高次元空間にマッピングし、最大マージン超平面を確立します。データを分離する超平面の両側に 2 つの平行超平面が構築されます。分離超平面は、2 つの平行超平面間の距離を最大化します。平行な超平面間の距離またはギャップが大きいほど、分類器の全体的な誤差が小さくなると想定されます。優れたガイドとしては、CJC Burges の『パターン認識のためのサポートベクターマシンのガイド』があります。 van der Walt と Barnard は、サポート ベクター マシンと他の分類器を比較しました。

4. アプリオリアルゴリズム

Apriori アルゴリズムは、ブール関連ルールの頻繁なアイテムセットをマイニングするための最も影響力のあるアルゴリズムの 1 つです。その中核は、2 段階の周波数セットの考え方に基づいた再帰アルゴリズムです。この関連ルールは、単一次元、単一レイヤーのブール関連ルールとして分類されます。ここで、サポートが最小サポートより大きいすべてのアイテム セットは、頻繁アイテム セット、または略して頻繁セットと呼ばれます。

5. 期待最大化（EM）アルゴリズム

統計計算において、期待値最大化 (EM) アルゴリズムは、観測不可能な潜在変数に依存する確率モデル内のパラメータの最大尤度推定値を見つけるためのアルゴリズムです。最大期待値は、機械学習やコンピューター ビジョンにおけるデータ クラスタリングの分野でよく使用されます。

6. ページランク

PageRank は Google アルゴリズムの重要な部分です。 2001年9月に米国特許が付与され、特許所有者はGoogleの創設者の一人であるラリー・ペイジ氏です。したがって、PageRank のページは Web ページではなくページを指します。つまり、このランキング方法はページにちなんで名付けられています。

PageRank は、外部リンクと内部リンクの量と質に基づいて Web サイトの価値を測定します。 PageRank の背後にある概念は、ページへの各リンクはそのページに対する投票であり、リンクの数が多いほど他のサイトからの投票も増えるというものです。これは「リンク人気」と呼ばれ、自分のサイトをあなたのサイトにリンクする意思のある人の数を測る指標です。 PageRank の概念は、学術論文の引用頻度から派生したものです。つまり、論文が他の人に引用される回数が多いほど、その論文の権威性が高いと一般的に判断されます。

7. アダブースト

Adaboost は反復アルゴリズムです。その基本的な考え方は、同じトレーニング セットに対して異なる分類器 (弱い分類器) をトレーニングし、これらの弱い分類器を組み合わせて、より強力な最終分類器 (強い分類器) を形成することです。アルゴリズム自体は、データ分布を変更することによって実装されます。各トレーニング セット内の各サンプルの分類が正しいかどうか、および最後の全体的な分類の精度に基づいて、各サンプルの重みを決定します。重みが変更された新しいデータセットは、トレーニングのために下位レベルの分類器に送信され、最後に各トレーニングから取得された分類器が最終決定分類器として融合されます。

8. kNN: k近傍分類

K 近傍法 (KNN) 分類アルゴリズムは、理論的には比較的成熟した方法であり、最も単純な機械学習アルゴリズムの 1 つです。この方法の考え方は、サンプルの最も類似した k 個のサンプル (つまり、特徴空間内の最も近いサンプル) のほとんどが特定のカテゴリに属する​​場合、サンプルもこのカテゴリに属する​​というものです。

9. ナイーブベイズ

数多くの分類モデルの中で、最も広く使用されている 2 つの分類モデルは、決定木モデルと単純ベイズモデル (NBC) です。 ナイーブベイズモデルは古典的な数学理論に由来し、強固な数学的基礎を持ち、安定した分類効率を備えています。同時に、NBC モデルでは推定に必要なパラメータが少なく、欠損データの影響をあまり受けず、アルゴリズムも比較的単純です。理論的には、NBC モデルは他の分類方法と比較してエラー率が最も低くなります。 ただし、常にそうであるとは限りません。これは、NBC モデルでは属性が互いに独立していると想定しているためですが、実際のアプリケーションではこれが当てはまらないことがよくあります。これは、NBC モデルの正しい分類に一定の影響を及ぼします。属性の数が多い場合や属性間の相関が大きい場合、NBC モデルの分類効率は決定木モデルほど良くありません。属性の相関が小さい場合、NBC モデルのパフォーマンスは最高になります。

10. CART: 分類と回帰ツリー

CART、分類および回帰ツリー。 分類ツリーの背後には 2 つの重要な考え方があります。 1 つ目は、独立変数の空間を再帰的に分割するというアイデアに関するもので、2 つ目は検証データによるプルーニングに関するものです。