機械学習を含むタスクは線形ではないかもしれないが、よく知られたいくつかのステップがある：
- 問題定義.
- データの準備.
- 基礎となるモデルを学習する.機械学習とデータ収集.
- 定量的・定性的評価により基礎となるモデルを改善する。
- モデルを発表する。
新しい問題と折り合いをつけるための良い方法の1つは、問題の特定と定義を最善の方法で行い、データから意味のある情報を取得するモデルを学ぶ作業を行うことである。 パターン認識および機械学習における問題はさまざまなタイプがありますが、大きく 3 つのカテゴリに分類できます。
- Supervised Learning:
システムには、「教師」によって与えられた例の入力とその望ましい出力が示され、入力と出力を対応付ける一般規則を学ぶことが目標です。 3585> - 強化学習：
システムは動的な環境と相互作用し、特定の目標（たとえば、車両の運転や対戦相手とのゲーム）を実行しなければならない。
教師付き学習と教師なし学習の間に、教師が不完全な学習信号（目標出力の一部（多くの場合）が欠落している学習セット）を与える半教師付き学習があります。 このブログでは、教師なし学習とデータ クラスタリングに焦点を当てます。
教師なし学習
パターン認識問題の中には、学習データが、対応する目標値を持たない入力ベクトル x の集合で構成されるものがあります。 このような教師なし学習問題での目標は、クラスタリングと呼ばれるデータ内の類似例のグループを発見することであったり、密度推定と呼ばれるデータが空間内でどのように分布しているかを決定することであったりする。 1385>
教師なし学習の問題点：
- 教師なし学習は教師あり学習と比較して難しい…
- 回答ラベルが利用できないので結果が有意義であるかどうかはどうすればわかるのか？
- 専門家に結果を見てもらう（外部評価）
- クラスタリングの目的関数を定義する（内部評価）
なぜこれらの問題にもかかわらず教師なし学習が必要なのか？
- 大きなデータセットを注釈することは非常に高価なので、少数の例だけ手動でラベル付けすることができます。 例 音声認識
- データがいくつのクラスに分かれているのか分からない場合がある。 例 データマイニング
- クラスタリングを使って、分類器を設計する前にデータの構造を把握したい場合がある。
教師なし学習はさらに2つのカテゴリに分類できる。 これは、サンプルデータが、固定されたパラメータのセットに基づく確率分布に従う母集団から来ることを仮定している。 理論的には、正規分布の系列では、すべてのメンバーが同じ形状を持ち、平均と標準偏差でパラメータ化されています。 つまり、平均と標準偏差がわかっていて、その分布が正規分布であれば、将来の観測の確率がわかるということである。 パラメトリック教師なし学習では、ガウス混合モデルを構築し、期待値最大化アルゴリズムを用いて、当該サンプルのクラスを予測する。 3585>
教師なし学習の非パラメータ化バージョンでは、データがクラスタにグループ化され、各クラスタはデータのカテゴリとクラスについて何かを語っている（と期待）。 この方法は、サンプルサイズが小さいデータをモデル化し、分析するために一般的に使用されます。 パラメトリックモデルとは異なり、ノンパラメトリックモデルはモデラーが母集団の分布について仮定する必要がないため、分布のない方法と呼ばれることもある。
クラスタリングとは？
クラスタリングは教師なし学習問題の中で最も重要だと考えられる。 クラスタリングの緩やかな定義は、「オブジェクトを、何らかの方法で類似したメンバーを持つグループに組織化するプロセス」であろう。 したがって、クラスタは、それらの間で「類似」しており、他のクラスタに属するオブジェクトに対して「非類似」であるオブジェクトのコレクションです。
Distance-based clustering.
点のセットが与えられ、点間の距離の概念があると、
- 内部（クラスタ内）距離が小さくなるように、点をある数のクラスタにグループ化することです。3585>
クラスタリングの目標
クラスタリングの目標は、ラベル付けされていないデータのセットで内部のグループ化を決定することです。 しかし、何が良いクラスタリングを構成するのかをどのように決定するのだろうか。 クラスタリングの最終的な目的から独立した絶対的な「最良の」基準は存在しないことが示される。 したがって、クラスタリングの結果がニーズに合うように、この基準を提供するのはユーザーです。
上の画像で、どのように最高のクラスタリング ソリューションがわかるでしょうか。
特定のクラスタリング ソリューションを見つけるために、クラスタの類似性測定を定義する必要があります。
近接測定
クラスタリングのために、2 つのデータ ポイントの近接測定を定義する必要があります。 ここでの近接とは、サンプルが互いに関してどれだけ似ているか/似ていないかを意味します。
- 類似度尺度 S(xi,xk): xi,xk が似ていれば大きい
- 非類似度（または距離）尺度 D(xi,xk): xi,xk が似ていなければ大きい。 xi,xkが似ていれば小さい
使用できる類似性尺度は様々である。
- Vectors: コサイン距離
- セット。 Jaccard Distance
- Points: Euclidean Distance
q=2
「良い」近接指標は非常にアプリケーション依存です。 クラスタは、その問題にとって「自然な」変換の下で不変であるべきです。 また、クラスタリング中に、複数の分布から描かれたデータを正規化することはお勧めしません。
クラスタリングアルゴリズム
クラスタリングアルゴリズムは以下に分類することができる。
- 排他的クラスタリング
- 重複クラスタリング
- 階層的クラスタリング
- 確率的クラスタリング
最初のケースでは、あるデータ点が特定のクラスターに属していれば、他のクラスターに含まれないように、データが排他的にグループ化されている。 1385>
逆に、2番目のタイプ、重複クラスタリングは、ファジーセットを使用してデータを分類し、各ポイントがメンバーシップの異なる2以上のクラスタに属せることができるようにするもの。 この場合、データは適切なメンバーシップ値に関連付けられる。
階層的クラスタリングアルゴリズムは、2つの最も近いクラスタ間の結合に基づくものである。 開始条件は、すべてのデータ点をクラスタとして設定することで実現される。 1385>
最後に、最後の種類のクラスタリングは、完全に確率的なアプローチを使用します。
このブログでは、最もよく使用される 4 つのクラスタリング アルゴリズムについて説明します。
- K-means
- Fuzzy K-means
- Hierarchical clustering
- Mixture of Gaussians
これらのアルゴリズムはそれぞれ上記の種類のクラスタリングのいずれかに属します。 K-meansは排他的クラスタリングアルゴリズム、Fuzzy K-meansは重複クラスタリングアルゴリズム、Hierarchical clusteringは明白であり、最後にMixture of Gaussiansは確率的クラスタリングアルゴリズムである。 1385>
K-Means Clustering
K-means はよく知られているクラスタリング問題を解決する最も単純な教師なし学習アルゴリズムの1つである。 この方法は、与えられたデータセットを先験的に決められたクラスタ数（kクラスタとする）により分類する単純で簡単な方法である。 主なアイデアは、各クラスタに1つずつ、k個の中心を定義することである。 これらの中心は、位置が異なると結果が異なるため、スマートな方法で配置する必要があります。 そのため、できるだけ互いに離れた場所に配置することが望ましい。 次のステップは、与えられたデータセットに属する各点を取り、それを最も近いセントロイドに関連付けることである。 保留点がない場合、最初のステップは完了し、早期のグループ化が行われる。 この時点で、前のステップで得られたクラスタの重心として、k個の新しいセントロイドを再計算する必要がある。 これらのk個の新しいセントロイドが得られたら，同じデータセット点と最も近い新しいセントロイドの間で新しい結合が行われなければならない． ループが生成された。 このループの結果として、我々は、k個のセントロイドが、これ以上の変化がなくなるまで、その位置をステップバイステップで変化させていることに気づくかもしれない。 言い換えれば、セントロイドはそれ以上移動しない。
最後に、このアルゴリズムは目的関数、この場合は二乗誤差関数を最小化することを目的としている。 目的関数
ここで
はデータ点xiとクラスタ中心cj間の選択距離指標である。 は、n 個のデータ点のそれぞれのクラスタ中心からの距離を示す指標である。
アルゴリズムは以下のステップで構成される：
- X＝{x1,x2,x3,……xn}をデータ点のセット、V＝{v1,v2,……vc}をセンターのセットとする。
- ランダムに ‘c’ クラスタセンターを選択する。
- 各データ点とクラスタセンター間の距離を計算する。
- クラスタ中心からの距離がすべてのクラスタ中心の中で最小であるクラスタ中心にデータ点を割り当てる。
ここで、「ci」はiクラスタのデータ点の数である。
- 各データ点と新しく得られたクラスタ中心との距離を再計算する。
- データ点が再割り当てされなかった場合は停止し、それ以外はステップ3）から繰り返す。
この手順は必ず終了することが証明されているが、k平均アルゴリズムは必ずしも最適な構成を見つけるとは限らず、大目的関数最小値に相当するものである。 また、このアルゴリズムは、最初に無作為に選択されたクラスタ中心に対して著しく敏感である。 1385>
K-means は、多くの問題領域に適応されている単純なアルゴリズムである。 これから見るように、ファジー特徴ベクトルを扱うための拡張の良い候補である。
k-means 手順は、クラスタ中心への2乗距離の和を最小化するよう n サンプルを k クラスタに分割する貪欲アルゴリズムとして見なすことができる。
- 平均を初期化する方法が指定されていない。 3585>
- miに最も近いサンプルの集合が空で、miが更新されないということが起こり得ます。 これは実装時に処理する必要がある問題だが、一般に無視される。
- 結果はkの値に依存し、最適な「k」を記述する方法はない。
この最後の問題は特に厄介で、クラスタがいくつ存在するか知る方法がないことが多いからである。 上に示した例では、同じアルゴリズムを同じデータに適用すると、次のような3-meansクラスタリングが生成されます。 これは 2-meansクラスタリングより良いか悪いか。
残念ながら、任意のデータセットに対する最適クラスタ数を求める一般理論解は存在しない。 簡単なアプローチは、異なるkクラスで複数の実行結果を比較し、与えられた基準に従って最適なものを選択することであるが、kを大きくすると定義により誤差関数値が小さくなるが、オーバーフィッティングのリスクも高くなるので注意が必要である。
Fuzzy K-Means Clustering
ファジークラスタリングでは、従来のk平均のように完全にひとつのクラスタだけに属するのではなく、それぞれの点は各クラスタに属している確率がある。 ファジィk-meansは特に、距離を確率に置き換えることによって、点が中心の間にあったり、そうでなければ曖昧であったりする問題に対処しようとするもので、もちろん、距離の逆数に対する確率を持つなど、距離の何らかの関数を持つことができる。 ファジーk-meansはこれらの確率に基づき重み付けされたセントロイドを用いる。 初期化、反復、終了のプロセスはk-meansで用いられたものと同じである。 得られたクラスタは、ラベルのハードな割り当てではなく、確率的な分布として分析するのが最適である。 使用される確率関数が、データ点がセントロイドに最も近い場合に単純に1、そうでない場合に0である場合、k-meansはファジーk-meansの特殊なケースであることを理解すべきである。
ファジーk-meansアルゴリズムは以下の通りである：
- クラスタの固定数Kと仮定する。
- 初期設定。 クラスタに関連するk-means μkをランダムに初期化し、各データ点Xiが与えられたクラスタKのメンバーである確率、
P（PointXiHasLabelK|Xi,K）を計算する。 - イテレーションを行う。 すべてのデータ点Xiのメンバー確率を与えて、重み付きセントロイドとしてクラスタのセントロイドを再計算する :
- Termination: 収束するまで、またはユーザーが指定した反復回数に達するまで反復する (反復はいくつかの局所的な最大値または最小値でトラップされる場合があります)
理解を深めるために、この単純な一次元の例について考えてみましょう。 あるデータセットが与えられたとき、それを軸上に分布するように表現するとする。 下図はこれを表しています。
図を見て、2つのデータ集中の近傍にある二つのクラスタを確認できるかも知れません。 それらを’A’と’B’を使って参照することにする。 このチュートリアルで示した最初のアプローチ – k-meansアルゴリズム- では、各データ点を特定のセントロイドに関連付けました。したがって、このメンバーシップ関数は次のようになります：
代わりにファジー k-means 法では、同じ与えられたデータ点が明確に定義されたクラスタにのみ属さない、中間に置かれることが可能です。
上の図では、赤い印で示したデータポイントはAクラスタよりもBクラスに属していることが分かる。 1385>
Hierarchical Clustering Algorithms
クラスタ化されるN個のアイテムセット、およびN*N個の距離（または類似度）行列がある場合、階層的クラスタリングの基本プロセスは次のようになります：
- N 個のアイテムがあれば、それぞれ1個だけを含むN個のクラスタを持っているので、それぞれのアイテムをクラスターに割り当てることから開始します。
- クラスタ間の距離（類似度）を、それらが含むアイテム間の距離（類似度）と同じにする。
- クラスタの最も近い（最も似ている）ペアを見つけ、それらを単一のクラスタにマージし、これでクラスタは1つになる。
- 新しいクラスタと古いクラスタのそれぞれの間の距離（類似度）を計算する。
- すべてのアイテムをサイズNの単一のクラスにクラスタ化するまで2、3手順を繰り返し。
クラスタリング問題を扱う別の方法としてモデルベースのアプローチ、つまりクラスタに特定のモデルを使用してデータとモデル間の適合性を最適化しようとするものがある。
実際には、各クラスタはガウスのようなパラメトリック分布によって数学的に表すことができます。 したがって、データセット全体はこれらの分布の混合物によってモデル化される。
高い尤度を持つ混合モデルは、以下の特徴を持つ傾向がある：
- 成分分布が高い「ピーク」を持つ（1つのクラスタ内のデータが密である）；
- 混合モデルがデータをよく「カバー」する（データ内の支配的パターンが成分分布によって捕捉される）。
Main advantages of model-based clustering:
- well-studied statistical inference techniques available;
- flexibility in choosing the component distribution;
- obtain a density estimation for each cluster;
- a soft” classification is available.The model-based clustering is major advantages of model-based clustering: Multimedia in industry:
[2][3][4]。
Mixture of Gaussians
この種のクラスタリング手法で最も広く使われているのは、ガウスの混合分布の学習に基づいている：
混合モデルはk成分分布の混合で、集合的には混合分布f（x）とするものである。
αkはf（x）を構成するk番目の成分の寄与を表しています。 実際には、パラメトリック分布（ガウシアンなど）は、その挙動を理解するために多くの研究がなされているため、よく使われます。 1385>
EMアルゴリズム
期待値最大化では、データが複数の多変量正規分布から構成されていると仮定する（これは非常に強い仮定であり、特にクラスタ数を固定した場合、非常に強い仮定であることに注意！）。 言い換えれば、EM は、モデル内の変数の一部が観測されない場合 (すなわち、潜在変数がある場合)、尤度関数を最大化するためのアルゴリズムです。 さて、微分をとってゼロにすることでこれを最大化しようとすると、多くの場合、一階条件が解をもたないことに気づきます。 モデル・パラメータを解くためには、観測されないデータの分布を知る必要がありますが、観測されないデータの分布はモデル・パラメータの関数なのです。
期待値最大化アルゴリズム
- Start with guess for values of the model parameters
- E-step。 欠損値を持つ各データポイントについて、モデルパラメータの現在の推測と観測されたデータを与えて、欠損データの分布を解くためにモデル方程式を使用します（期待値ではなく、各欠損値の分布について解いていることに注意してください）。 各欠損値の分布がわかったので、未観測変数に関する尤度関数の期待値を計算することができます。 モデル・パラメータの推測が正しければ、この期待尤度は観測されたデータの実際の尤度となり、パラメータが正しくなければ、単なる下界となります。 3585>
- M-ステップ：観測されない変数がない期待尤度関数ができたので、完全に観測された場合と同様に関数を最大化し、モデルパラメータの新しい推定値を得る。
- 収束するまで繰り返す。 その中でも、
- 多数の次元と多数のデータ項目を扱うことは、時間の複雑さのために問題となり得る。
- 方法の有効性は、「距離」の定義に依存する（距離ベースのクラスタリングの場合）。 明白な距離尺度が存在しない場合、それを「定義」しなければならないが、特に多次元空間では必ずしも容易ではない。
- クラスタリング アルゴリズムの結果 (多くの場合、それ自体が任意である) は、さまざまな方法で解釈することが可能である。
Possible Applications
クラスタリング アルゴリズムは多くの分野で応用できる。たとえば、
- Marketing: 顧客の特性や過去の購買記録を含む顧客データの大規模データベースから、類似した行動をとる顧客のグループを見つけ出す。 3585>
- 地震研究：観測された地震の震源地をクラスタリングして危険地帯を特定する；
- World Wide Web：文書分類；Weblogデータをクラスタリングして類似のアクセスパターンのグループを発見する；
- 自動車保険：平均請求額の高い自動車保険契約者群を特定する。