データマイニングにおける10の古典的なアルゴリズムの予備的調査

以下は、選考に参加した 18 個の候補アルゴリズムから選ばれた上位 10 個の古典的なアルゴリズムです。

1. C4.5

C4.5は機械学習アルゴリズムにおける分類決定木アルゴリズムです。決定木（決定木における決定ノードの構成は木のようになっていますが、実際は逆木です）コアアルゴリズムID3を改良したアルゴリズムなので、基本的に決定木の構築方法を半分理解していれば構築できます。決定木の構築方法は、実際には、現在のノードの分類条件として、毎回適切な特徴と分割ポイントを選択します。

ID3 と比較して、C4.5 には次の改善点があります。

1. 情報ゲイン率を使用して属性を選択します。

ID3 は、サブツリーの情報ゲインを使用して属性を選択します。ここで情報を定義する方法は多数あります。ID3 はエントロピー (エントロピーは不純度の尺度) を使用します。これはエントロピーの変化です。 C4.5 は情報ゲイン率を使用します。はい、違いは、一方が情報ゲインであり、もう一方が情報ゲイン率であるということです。一般的に、速度はバランスをとるために使用され、これは分散の役割に似ています。たとえば、2 人の人が走っています。1 人は 10 m/s でスタートし、10 秒後には 20 m/s になります。もう 1 人は 1 m/s でスタートし、1 秒後には 2 m/s になります。

差だけを計算すると、両者の差は大きくなります。速度増加率（加速度、1m/s^2）で測ると、2人の加速度は同じになります。そのため、C4.5 は情報ゲインを使用して属性を選択する際に値の多い属性を選択しがちであるという ID3 の欠点を克服しています。

2. ツリー構築中に剪定します。決定木を構築するときは、複数の要素がぶら下がっているノードを考慮しないのが最善です。そうしないと、簡単に過剰適合につながります。

3. 非離散データも処理できます。

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

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

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

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

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

アプリオリアルゴリズム

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 つ目は、検証データを使用して剪定するという考え方です。わかりました。そのうちの 1 つまたは 2 つを選んで、今後詳しく研究し、説明します。以上です。

18 個の候補アルゴリズムについては、こちらを参照してください: http://www.cs.uvm.edu/~icdm/algorithms/CandidateList.shtml

【編集者のおすすめ】