使用聚類指標識別未知數

聚類是一種無監督機器學習方法，僅根據每個樣本的特徵將給定數據分組。 將數據分類成簇有助於識別樣本之間的未知相似性或揭示數據集中的異常值。 在現實世界中，聚類在從營銷到生物學的各個領域都具有重要意義：聚類應用包括市場細分、社交網絡分析和診斷醫學成像。

因為這個過程是無監督的，所以可以圍繞不同的特徵形成多個聚類結果。 例如，假設您有一個由紅褲子、黑褲子、紅襯衫和黑襯衫的各種圖像組成的數據集。 一種算法可能會根據服裝形狀找到聚類，而另一種算法可能會根據顏色創建組。

在分析數據集時，我們需要一種方法來準確衡量不同聚類算法的性能； 我們可能想要對比兩種算法的解決方案，或者查看聚類結果與預期解決方案的接近程度。 在本文中，我們將探討一些可用於比較從相同數據中獲得的不同聚類結果的指標。

理解聚類：一個簡單的例子

讓我們定義一個示例數據集，我們將使用它來解釋各種聚類度量概念並檢查它可能產生的聚類類型。

首先，一些常見的符號和術語：

• $D$：數據集
• $A$, $B$：作為我們數據集子集的兩個集群
• $C$：$D$ 的真實聚類，我們將與另一個聚類進行比較
  • 聚類 $C$ 有 $K$ 個簇，$C = {C_1, ..., C_k}$
• $C'$：$D$ 的第二個聚類
  • 聚類 $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$代表黑色襯衫

其他聚類可能包括四個以上基於不同特徵的聚類，例如襯衫是無袖的還是有袖的。

如我們的示例所示，聚類方法將數據集中的所有樣本劃分為非空不相交的子集。 在集群 $c$ 中，沒有圖像既屬於褲子子集又屬於襯衫子集：$c_1 \cap c_2 = \emptyset$。 這個概念可以擴展； 任何集群的兩個子集都沒有相同的樣本。

聚類比較指標概述

大多數比較聚類的標準可以用$C,C'$對的混淆矩陣來描述。 混淆矩陣將是一個 $K \times K'$ 矩陣，其第 $kk'$ 個元素（第 $k$ 行和第 $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$ 只是一套紅襯衫。

基於底層的聚類比較方法，聚類指標可以大致分為三組：

在本文中，我們僅涉及許多可用指標中的幾個，但我們的示例將有助於定義三個集群指標組。

對數

對計數需要檢查所有樣本對，然後計算聚類一致和不一致的對。 每對樣本可以屬於四個集合之一，其中集合元素計數 ($N_{ij}$) 是從混淆矩陣中獲得的：

• $S_{11}$，具有 $N_{11}$ 個元素：該對的元素在 $C$ 和 $C'$ 下的同一簇中
  • 比較 $c$ 和 $c''$ 時，兩件紅襯衫會低於 $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$)

蘭德指數定義為$(N_{00} + N_{11})/(n(n-1)/2)$，其中$n$代表樣本數； 它也可以讀作（類似處理的對數）/（對數總數）。 儘管理論上它的值範圍在 0 和 1 之間，但實際上它的範圍通常要窄得多。 較高的值意味著聚類之間的相似性更高。 （蘭德指數為 1 表示兩個聚類具有相同聚類的完美匹配。）

蘭德指數的一個限制是它在聚類數量增加到接近元素數量時的行為。 在這種情況下，它向 1 收斂，這給準確測量聚類相似度帶來了挑戰。 已經引入了幾個改進或修改的蘭德指數版本來解決這個問題。 一種變化是調整後的蘭德指數； 但是，它假設兩個聚類是隨機繪製的，具有固定數量的聚類和聚類元素。

信息論

這些指標基於信息論的一般概念。 我們將討論其中兩個：熵和互信息（MI）。

熵描述了一個聚類中有多少信息。 如果與聚類相關的熵為 0，則隨機選取的樣本的聚類不存在不確定性，當只有一個聚類時這是正確的。

MI 描述了一個聚類提供了多少關於另一個聚類的信息。 MI 可以表明知道$C$ 中樣本的聚類在多大程度上降低了$C'$ 中樣本聚類的不確定性。

歸一化互信息是由聚類熵的幾何或算術平均值歸一化的 MI。 標準 MI 不受常數值的約束，因此標準化互信息提供了更易解釋的聚類度量。

此類別中的另一個流行指標是信息的變化(VI)，它取決於聚類的熵和 MI。 令 $H(C)$ 為聚類的熵，$I(C, C')$ 為兩個聚類之間的 MI。 兩個聚類之間的 VI 可以定義為 $VI(C,C') = H(C)+H(C')-2I(C,C')$。 VI 為 0 表示兩個聚類之間的完美匹配。

設置重疊

設置重疊指標涉及根據集群之間的最大重疊確定 $C$ 中的集群與 $C'$ 中的集群的最佳匹配。 對於此類別中的所有指標，1 表示聚類是相同的。

最大匹配度量以降序掃描混淆矩陣，並首先匹配混淆矩陣的最大條目。 然後它會刪除匹配的集群並按順序重複該過程，直到集群耗盡。

F-measure是另一組重疊度量。 與最大匹配測度不同，F 測度經常用於將聚類與最優解進行比較，而不是比較兩個聚類。

使用 F-measure 應用聚類指標

由於 F-measure 在機器學習模型和搜索引擎等重要應用中的常見用途，我們將通過一個示例更詳細地探討 F-measure。

F-measure 定義

讓我們假設 $C$ 是我們的基本事實或最優解決方案。 對於$C$ 中的任何第k$ 個簇，其中$k \in [1, K]$，我們將在聚類結果$C'$ 中為每個簇計算一個單獨的F-measure。 這個單獨的 F 度量表明集群 $C^\prime_{k'}$ 描述集群 $C_k$ 的程度，並且可以通過這些集群的精度和召回率（兩個模型評估指標）來確定。 讓我們將$I_{kk'}$定義為$C$的第$k$簇和$C'$的$k'$th簇中元素的交集，$\lvert C_k \rvert$作為數字$k$th 簇中的元素個數。

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

• 回想一下 $r = \frac{I_{kk'}}{\lvert C_{k} \rvert}$

然後，$k$th 和 $k'$th 集群的單個 F 度量可以計算為這些集群的準確率和召回率的調和平均值：

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

現在，為了比較 $C$ 和 $C'$，讓我們看一下整體 F-measure。 首先，我們將創建一個類似於列聯表的矩陣，其值是集群的各個 F 度量。 假設我們已將 $C$ 的集群映射為表的行，將 $C'$ 的集群映射為列，表值對應於各個 F 度量。 識別具有最大單個 F 度量的集群對，並刪除與這些集群對應的行和列。 重複此操作，直到集群耗盡。 最後，我們可以定義整體 F-measure：

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

如您所見，整體 F 度量是我們對集群的最大單個 F 度量的加權和。

數據設置和預期結果

任何適合機器學習的 Python notebook，例如 Jupyter notebook，都可以作為我們的環境使用。 在開始之前，您可能需要檢查我的 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

接下來，我們將在這些特徵向量上嘗試我們的第一個聚類方法，凝聚聚類。

聚類方法一：凝聚聚類

將給定的新聞類別視為最佳解決方案，讓我們將這些結果與凝聚聚類的結果進行比較（由於數據集中有 30 個類別，因此期望的聚類數為 30）：

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

我們將通過整數標籤識別生成的集群； 屬於同一簇的標題被分配相同的整數標籤。 來自我們 GitHub 存儲庫的compare_clusters模塊的cluster_measure函數返回聚合 F-measure 和完美匹配集群的數量，因此我們可以看到我們的聚類結果有多準確：

 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 度量是有意義的。 然而，重要的是要記住，我們選擇的給定類別分類只反映了數據集的一種可能劃分。 這裡的低 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。 由於兩個聚類結果具有相似的 F 度量，因此將它們相互比較會很有趣。 我們已經有了聚類，所以我們只需要計算 F-measure。 首先，我們將兩個結果合併到一個列中， 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)

使用更高的 F-measure 0.4，我們可以觀察到兩種算法的聚類彼此之間的相似性高於最優解。

了解有關增強聚類結果的更多信息

了解可用的聚類比較指標將擴展您的機器學習模型分析。 我們已經看到了 F-measure 聚類指標的實際應用，並為您提供了將這些知識應用到下一個聚類結果所需的基礎知識。 要了解更多信息，以下是我的首選進一步閱讀：

• 比較聚類——Dorothea Wagner 和 Silke Wagner 的概述
• 比較聚類——Marina Meil​​a 的基於信息的距離
• 聚類比較的信息論測量：變體、屬性、歸一化和機會校正Nguyen Xuan Vinh、Julien Epps 和 James Bailey

---

進一步閱讀 Toptal 工程博客：

• 使用 Python/NetworkX 進行圖形數據科學
• 使用未標記數據的半監督圖像分類
• 機器學習中的嵌入：使復雜數據變得簡單

Toptal 工程博客對 Luis Bronchal 對本文中提供的代碼示例的審閱表示感謝。