クラスタリング メトリクスで未知のものを特定する

クラスタリングは、各サンプルの特徴のみに基づいて、特定のデータをグループに分割する教師なし機械学習手法です。 データをクラスターに並べ替えると、サンプル間の未知の類似点を特定したり、データ セット内の外れ値を明らかにしたりするのに役立ちます。 現実の世界では、クラスタリングは、マーケティングから生物学まで、さまざまな分野で重要です。クラスタリングのアプリケーションには、市場セグメンテーション、ソーシャル ネットワーク分析、診断用医療画像が含まれます。

このプロセスは監視されていないため、複数のクラスタリング結果がさまざまな特徴の周りに形成される可能性があります。 たとえば、赤いズボン、黒いズボン、赤いシャツ、黒いシャツのさまざまな画像で構成されるデータ セットがあるとします。 あるアルゴリズムは服の形に基づいてクラスターを見つけ、別のアルゴリズムは色に基づいてグループを作成します。

データセットを分析する場合、さまざまなクラスタリング アルゴリズムのパフォーマンスを正確に測定する方法が必要です。 2 つのアルゴリズムの解を比較したり、クラスタリングの結果が予想される解にどれだけ近いかを確認したりすることができます。 この記事では、同じデータから得られたさまざまなクラスタリング結果を比較するために使用できるいくつかのメトリックについて説明します。

クラスタリングについて: 簡単な例

さまざまなクラスタリング メトリクスの概念を説明し、生成されるクラスタの種類を調べるために使用するデータ セットの例を定義しましょう。

最初に、いくつかの一般的な表記法と用語を示します。

• $D$: データセット
• $A$、$B$: データセットのサブセットである 2 つのクラスター
• $C$: 別のクラスターと比較する $D$ のグラウンド トゥルース ク​​ラスタリング
  • クラスタリング $C$ には $K$ 個のクラスターがあり、$C = {C_1, …, C_k}$
• $C'$: $D$ の 2 番目のクラスタリング
  • クラスタリング $C'$ には $K'$ 個のクラスターがあります。$C' = {C^\prime_1, …, C^\prime_{k^\prime}}$

クラスタリングの結果は、並べ替え機能だけでなく、クラスターの総数によっても異なる場合があります。 結果は、アルゴリズム、小さな摂動に対する感度、モデルのパラメーター、およびデータの特徴によって異なります。 前述の黒と赤のズボンとシャツのデータ セットを使用すると、さまざまなアルゴリズムから生成されるさまざまなクラスタリング結果が得られます。

一般的なクラスタリング $C$ とサンプル クラスタリングを区別するために、小文字の $c$ を使用してサンプル クラスタリングを説明します。

• $c$、形状に基づくクラスタ: $c = {c_1, c_2}$、$c_1$ はズボンを表し、$c_2$ はシャツを表します
• $c'$、色に基づくクラスタ: $c' = {c'_1, c'_2}$、ここで、$c'_1$ は赤い服を表し、$c'_2$ は黒い服を表します
• $c''$、形状と色に基づくクラスター: $c'' = {{c^{\prime \prime}}_1, {c^{\prime \prime}}_2, {c^{\prime \prime}}_3、{c^{\prime \prime}}_4}$、${c^{\prime \prime}}_1$ は赤いズボン、${c^{\prime \prime}}_2 $ は黒いズボン、${c^{\prime \prime}}_3$ は赤いシャツ、${c^{\prime \prime}}_4$ は黒いシャツを表します。

追加のクラスタリングには、シャツがノースリーブか袖付きかなど、さまざまな特徴に基づいて 5 つ以上のクラスターが含まれる場合があります。

この例に見られるように、クラスタリング メソッドは、データ セット内のすべてのサンプルを空でない互いに素なサブセットに分割します。 クラスター $c$ には、ズボンのサブセットとシャツのサブセットの両方に属する画像はありません: $c_1 \cap c_2 = \emptyset$. この概念は拡張できます。 クラスターの 2 つのサブセットが同じサンプルを持つことはありません。

クラスタリング比較メトリックの概要

クラスタリングを比較するためのほとんどの基準は、ペア $C, C'$ の混同行列を使用して記述できます。 混同行列は、$kk'$ 番目の要素 ($k$ 番目の行と $k'$ 番目の列の要素) がクラスタの交点のサンプル数である $K \times K'$ 行列になります。 $C$ の C_k$ と $C'$ の $C'_{k'}$:

\[n_{kk'} = |C_k \cap C'_{k'}|\]

データ セット $D$ に 100 の赤いズボン、200 の黒いズボン、200 の赤いシャツ、300 の黒いシャツがあると仮定して、単純化した黒と赤のズボンとシャツの例を使用してこれを分解します。 $c$ と $c''$ の混同行列を調べてみましょう:

$K = 2$ かつ $K'' = 4$ なので、これは $2 \times 4$ 行列です。 $k = 2$ と $k'' = 3$ を選びましょう。 要素 $n_{kk'} = n_{23} = 200$ であることがわかります。 これは、$c_2$ (シャツ) と ${c^{\prime\prime}}_3$ (赤いシャツ) の交点が 200 であることを意味します。これは、$c_2 \cap {c^{\prime\prime} }_3$ は単に赤いシャツのセットです。

クラスタリング メトリックは、基礎となるクラスタ比較方法に基づいて、大きく 3 つのグループに分類できます。

この記事では、利用可能な多くのメトリクスの一部のみに触れますが、例は 3 つのクラスタリング メトリクス グループを定義するのに役立ちます。

ペアカウンティング

ペアカウントでは、サンプルのすべてのペアを調べてから、クラスタリングが一致するペアと一致しないペアをカウントする必要があります。 サンプルの各ペアは、4 つのセットのいずれかに属することができます。ここで、セットの要素数 ($N_{ij}$) は混同行列から取得されます。

• $S_{11}$、$N_{11}$ 要素を持つ: ペアの要素は、$C$ と $C'$ の両方の下の同じクラスターにあります
  • $c$ と $c''$ を比較すると、赤いシャツ 2 枚組は $S_{11}$ に該当します。
• $S_{00}$、$N_{00}$ 要素を持つ: ペアの要素は $C$ と $C'$ の両方の下の異なるクラスターにあります
  • $c$ と $c''$ を比較すると、赤いシャツと黒いズボンのペアは $S_{00}$ に分類されます
• $S_{10}$、$N_{10}$ 要素を持つ: ペアの要素は $C$ の同じクラスターにあり、$C'$ の異なるクラスターにあります
  • $c$ と $c''$ を比較すると、赤いシャツと黒いシャツのペアは $S_{10}$ に該当します。
• $S_{01}$、$N_{01}$ 要素を持つ: ペアの要素は $C$ の異なるクラスターにあり、$C'$ の同じクラスターにあります
  • $c$ と $c''$ を比較すると、$S_{01}$ には要素がありません ($N_{01} = 0$)

Rand インデックスは、$(N_{00} + N_{11})/(n(n-1)/2)$ として定義されます。ここで、$n$ はサンプル数を表します。 また、（同様に処理されたペアの数）/（ペアの総数）として読み取ることもできます。 理論的にはその値の範囲は 0 から 1 の間ですが、実際にはその範囲はより狭いことがよくあります。 値が高いほど、クラスタリング間の類似性が高いことを意味します。 (Rand インデックス 1 は、2 つのクラスタリングが同一のクラスターを持つ完全な一致を表します。)

ランド インデックスの 1 つの制限は、クラスターの数が要素の数に近づくために増加するときの動作です。 この場合、1 に収束するため、クラスタリングの類似性を正確に測定することが難しくなります。 この問題に対処するために、いくつかの改善または修正されたバージョンの Rand インデックスが導入されました。 バリエーションの 1 つは、調整済みランド インデックスです。 ただし、固定数のクラスターとクラスター要素を使用して、2 つのクラスター化がランダムに描画されることを前提としています。

情報理論

これらのメトリックは、情報理論の一般的な概念に基づいています。 そのうちの 2 つ、エントロピーと相互情報量 (MI) について説明します。

エントロピーは、クラスタリングに含まれる情報の量を表します。 クラスタリングに関連付けられたエントロピーが 0 の場合、ランダムに選択されたサンプルのクラスターについて不確実性はありません。これは、クラスターが 1 つしかない場合に当てはまります。

MI は、1 つのクラスタリングが他のクラスタリングについてどの程度の情報を提供するかを表します。 MI は、$C$ のサンプルのクラスターを知ることで、$C'$ のサンプルのクラスターに関する不確実性がどの程度減少するかを示すことができます。

正規化された相互情報量は、クラスタリングのエントロピーの幾何平均または算術平均によって正規化された MI です。 標準 MI は定数値に拘束されないため、正規化された相互情報は、より解釈可能なクラスタリング メトリックを提供します。

このカテゴリでよく使用されるもう 1 つのメトリックは、クラスタリングのエントロピーと MI の両方に依存する情報の変動(VI) です。 $H(C)$ をクラスタリングのエントロピー、$I(C, C')$ を 2 つのクラスタリング間の MI とする。 2 つのクラスタリング間の VI は、$VI(C,C') = H(C)+H(C')-2I(C,C')$ として定義できます。 0 の VI は、2 つのクラスタリングが完全に一致していることを表します。

オーバーラップを設定

オーバーラップ メトリックを設定するには、クラスター間の最大オーバーラップに基づいて、$C$ のクラスターと $C'$ のクラスターの最適な一致を決定する必要があります。 このカテゴリのすべてのメトリックについて、1 はクラスタリングが同一であることを意味します。

最大一致測度は、混同行列を降順でスキャンし、混同行列の最大のエントリを最初に照合します。 次に、一致したクラスターを削除し、クラスターがなくなるまでプロセスを順番に繰り返します。

F 値は、もう 1 つのオーバーラップ メトリックです。 最大一致測度とは異なり、F 測度は、2 つのクラスタリングを比較する代わりに、クラスタリングを最適解と比較するためによく使用されます。

F メジャーを使用したクラスタリング メトリクスの適用

F 値は機械学習モデルや検索エンジンなどの重要なアプリケーションでよく使用されるため、例を使用して F 値について詳しく説明します。

F値の定義

$C$ がグラウンド トゥルース (最適解) であると仮定しましょう。 $C$ の任意の $k$ 番目のクラスター ($k \in [1, K]$) について、クラスタリング結果 $C'$ のすべてのクラスターで個別の F 値を計算します。 この個々の F 値は、クラスター $C^\prime_{k'}$ がクラスター $C_k$ をどの程度うまく説明しているかを示し、これらのクラスターの精度と再現率 (2 つのモデル評価メトリック) によって決定できます。 $I_{kk'}$ を $C$ の $k$ 番目のクラスターと $C'$ の $k'$ 番目のクラスターの要素の交点として定義し、$\lvert C_k \rvert$ を数として定義します。 $k$ 番目のクラスター内の要素の数。

• 精度 $p = \frac{I_{kk'}}{\lvert C'_{k'} \rvert}$

• $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$ を思い出してください

次に、$k$ 番目と $k'$ 番目のクラスターの個々の F 値を、これらのクラスターの適合率と再現率の調和平均として計算できます。

\[F_{kk'} = \frac{2rp}{r+p} = \frac{2I_{kk'}}{|C_k|+|C'_{k'}|}\]

$C$ と $C'$ を比較するために、全体の F 値を見てみましょう。 最初に、値がクラスターの個々の F 値である分割表に似た行列を作成します。 $C$ のクラスターをテーブルの行としてマッピングし、$C'$ のクラスターを列としてマッピングし、テーブルの値が個々の F 値に対応していると仮定します。 個々の F 測定値が最大のクラスター ペアを特定し、これらのクラスターに対応する行と列を削除します。 クラスターがなくなるまでこれを繰り返します。 最後に、全体的な F 値を定義できます。

\[F(C, C') = \frac{1}{n} \sum_{i=1}^K n_imax(F(C_i, C'_j)) \forall j \in {1, K'}\ ]

ご覧のとおり、全体的な F 値は、クラスターの最大の個々の F 値の加重合計です。

データの設定と期待される結果

Jupyter ノートブックなど、機械学習に適した任意の Python ノートブックが環境として機能します。 始める前に、私の GitHub リポジトリの README、拡張されたreadme_help_example.ipynbサンプル ファイル、およびrequirements.txtファイル (必要なライブラリ) を調べてください。

ニュース記事で構成される GitHub リポジトリのサンプル データを使用します。 データは、 category 、 headline 、 date 、およびshort_descriptionを含む情報で配置されます。

pandas を使用して、データの読み取り、分析、および操作を行うことができます。 完全なデータ セットは大きいため、データを日付で並べ替え、デモ用に小さなサンプル (10,000 のニュース ヘッドライン) を選択します。

 import pandas as pd df = pd.read_json("./sample_data/example_news_data.json", lines=True) df.sort_values(by='date', inplace=True) df = df[:10000] len(df['category'].unique())

このデータ サンプルには 30 のカテゴリがあるため、実行すると、ノートブックは結果 30 を出力するはずです。 df.head(4)を実行して、データがどのように保存されているかを確認することもできます。 (このセクションに表示されている表と一致する必要があります。)

クラスタリング機能の最適化

クラスタリングを適用する前に、まずテキストを前処理して、次のようなモデルの冗長な機能を削減する必要があります。

• 統一されたケースを持つようにテキストを更新します。
• 数字または特殊文字の削除。
• レンマタイゼーションを実行します。
• ストップワードの削除。

 import re import nltk from nltk.corpus import stopwords from nltk.stem import WordNetLemmatizer wordnet_lemmatizer = WordNetLemmatizer() nltk.download('stopwords') stop_words = stopwords.words('english') nltk.download('wordnet') nltk.download('omw-1.4') def preprocess(text: str) -> str: text = text.lower() text = re.sub('[^az]',' ',text) text = re.sub('\s+', ' ', text) text = text.split(" ") words = [wordnet_lemmatizer.lemmatize(word, 'v') for word in text if word not in stop_words] return " ".join(words) df['processed_input'] = df['headline'].apply(preprocess)

結果の前処理された見出しは、 processed_inputとして表示されます。これは、再度df.head(4)を実行することで確認できます。

ここで、任意の機械学習モデルを適用できるように、各見出しを数値ベクトルとして表す必要があります。 これを実現するためのさまざまな特徴抽出手法があります。 TF-IDF (用語頻度-逆ドキュメント頻度) を使用します。 この手法は、文書内で頻繁に出現する単語 (この例ではニュースの見出し) の影響を軽減します。これは、これらがクラスタリングまたは分類の決定的な特徴であってはならないことが明らかであるためです。

 from sklearn.cluster import AgglomerativeClustering, KMeans from sklearn.feature_extraction.text import TfidfVectorizer vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.split(' ')) tfidf_mat = vectorizer.fit_transform(df['processed_input']) X = tfidf_mat.todense() X[X==0]=0.00001

次に、これらの特徴ベクトルに対して、最初のクラスタリング方法である凝集クラスタリングを試します。

クラスタリング方法 1: 凝集クラスタリング

与えられたニュース カテゴリを最適なソリューションと見なして、これらの結果を凝集クラスタリングの結果と比較してみましょう (データ セットには 30 のカテゴリがあるため、必要なクラスタ数は 30 です)。

 clusters_agg = AgglomerativeClustering(n_clusters=30).fit_predict(X) df['class_prd'] = clusters_agg.astype(int)

結果のクラスターを整数ラベルで識別します。 同じクラスターに属する見出しには、同じ整数ラベルが割り当てられます。 GitHub リポジトリのcompare_clustersモジュールのcluster_measure関数は、集計 F 値と完全に一致するクラスターの数を返すため、クラスタリングの結果がどれほど正確であったかを確認できます。

 from clustering.compare_clusters import cluster_measure # 'cluster_measure` requires given text categories to be in the column 'text_category` df['text_category'] = df['category'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.19858339749319176, 0)

これらのクラスターの結果を最適解と比較すると、0.198 という低い F 測定値と、実際のクラス グループと一致する 0 クラスターが得られます。これは、凝集クラスターが選択した見出しカテゴリと一致しないことを示しています。 結果のクラスターを調べて、それがどのように見えるかを見てみましょう。

 df[df['class_prd'] == 0]['category'].value_counts()

結果を調べると、このクラスターにはすべてのカテゴリの見出しが含まれていることがわかります。

 POLITICS 1268 ENTERTAINMENT 712 THE WORLDPOST 373 HEALTHY LIVING 272 QUEER VOICES 251 PARENTS 212 BLACK VOICES 211 ... FIFTY 24 EDUCATION 23 COLLEGE 14 ARTS 13

したがって、結果のクラスターが最適解と一致しないことを考えると、F 値が低いことは理にかなっています。 ただし、選択した特定のカテゴリ分類は、データ セットの 1 つの可能な分割のみを反映していることを思い出すことが重要です。 ここでの低い F 値は、クラスタリングの結果が間違っていることを意味するのではなく、クラスタリングの結果が目的のデータ分割方法と一致しなかったことを意味します。

クラスタリング方法 2: K-means

同じデータセットで別の一般的なクラスタリング アルゴリズムを試してみましょう: k-means クラスタリングです。 新しいデータフレームを作成し、 cluster_measure関数を再度使用します。

 kmeans = KMeans(n_clusters=30, random_state=0).fit(X) df2 = df.copy() df2['class_prd'] = kmeans.predict(X).astype(int) res_df, fmeasure_aggregate, true_matches = cluster_measure(df2) fmeasure_aggregate, len(true_matches) # Outputs: (0.18332960871141976, 0)

凝集クラスタリングの結果と同様に、k-means クラスタリングの結果は、指定されたカテゴリとは異なるクラスターを形成しています。最適解と比較すると、F 値は 0.18 です。 2 つのクラスタリング結果は類似した F 値を持っているため、それらを互いに比較すると興味深いでしょう。 クラスタリングは既に行われているので、あとは F 値を計算するだけです。 まず、両方の結果を 1 つの列にまとめますclass_gtには凝集クラスタリングの出力があり、 class_prdには k-means クラスタリングの出力があります。

 df1 = df2.copy() df1['class_gt'] = df['class_prd'] res_df, fmeasure_aggregate, true_matches = cluster_measure(df1, gt_column='class_gt') fmeasure_aggregate, len(true_matches) # Outputs: (0.4030316435020922, 0)

より高い 0.4 の F 値を使用すると、2 つのアルゴリズムのクラスタリングが、最適解よりも互いに類似していることがわかります。

強化されたクラスタリングの結果について詳しく知る

利用可能なクラスタリング比較指標を理解すると、機械学習モデルの分析が拡張されます。 F メジャー クラスタリング メトリクスの動作を確認し、これらの学習を次のクラスタリング結果に適用するために必要な基本を説明しました。 さらに詳しく知るために、さらに読むための私のトップピックを次に示します。

• クラスタリングの比較 - Dorothea Wagner と Silke Wagner による概要
• クラスタリングの比較 - Marina Meil​​a による情報ベースの距離
• Nguyen Xuan Vinh、Julien Epps、および James Bailey によるクラスタリングの比較のための情報理論的尺度: バリアント、プロパティ、正規化、およびチャンスの補正

---

Toptal Engineering ブログの詳細情報:

• Python/NetworkX を使用したグラフ データ サイエンス
• ラベル付けされていないデータを使用した半教師付き画像分類
• 機械学習への埋め込み: 複雑なデータをシンプルにする

Toptal Engineering ブログは、この記事で紹介したコード サンプルをレビューしてくれた Luis Bronchal に感謝の意を表します。