使用聚类指标识别未知数

聚类是一种无监督机器学习方法，仅根据每个样本的特征将给定数据分组。 将数据分类成簇有助于识别样本之间的未知相似性或揭示数据集中的异常值。 在现实世界中，聚类在从营销到生物学的各个领域都具有重要意义：聚类应用包括市场细分、社交网络分析和诊断医学成像。

因为这个过程是无监督的，所以可以围绕不同的特征形成多个聚类结果。 例如，假设您有一个由红裤子、黑裤子、红衬衫和黑衬衫的各种图像组成的数据集。 一种算法可能会根据服装形状找到聚类，而另一种算法可能会根据颜色创建组。

在分析数据集时，我们需要一种方法来准确衡量不同聚类算法的性能； 我们可能想要对比两种算法的解决方案，或者查看聚类结果与预期解决方案的接近程度。 在本文中，我们将探讨一些可用于比较从相同数据中获得的不同聚类结果的指标。

理解聚类：一个简单的例子

让我们定义一个示例数据集，我们将使用它来解释各种聚类度量概念并检查它可能产生的聚类类型。

首先，一些常见的符号和术语：

• $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 对本文中提供的代码示例的审阅表示感谢。