聚类是一种无监督的机器学习方法，它只根据每个样本的特征将给定的数据分成几组. 将数据分类成簇可以帮助识别样本之间未知的相似性或揭示数据集中的异常值. 在现实世界中，聚类在从市场营销到生物学的各个领域都具有重要意义: 聚类 applications include market segmentation, social network analysis, diagnostic medical imaging.

由于该过程是无监督的，因此可以围绕不同的特征形成多个聚类结果. 例如, 假设您有一个由各种红色裤子图像组成的数据集, black trousers, 红衫军, black shirts. 一种算法可能会根据衣服的形状找到聚类, 而另一个可能会根据颜色创建组.

在分析一个数据集时，我们需要一种方法来准确地度量不同的性能 clustering algorithms; we may want to contrast the solutions of two algorithms, 或者查看聚类结果与预期解决方案的接近程度. In this article, 我们将探讨一些指标，这些指标可用于比较从相同数据获得的不同聚类结果.

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

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

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

• $D$: the data set
• $A$， $B$:两个集群，它们是我们数据集的子集
• $C$: $D$的基础真聚类，我们将与之比较另一个聚类
  • 聚类C K集群美元,美元$ C = {C₁,…,C_k} $
• $C’$: a second clustering of $D$
  • 聚类C K美元美元的美元集群,$ C ' = {C ^ \ prime_1,…,C ^ \ prime_ {K ^ \ '}} $

聚类结果不仅会根据排序特征变化，还会根据聚类的总数变化. 的 result depends on the algorithm, 它对微小扰动的敏感性, the model’s parameters, the data’s features. 使用我们之前提到的黑色和红色裤子和衬衫的数据集, 不同的算法可能产生不同的聚类结果.

为了区分一般聚类和我们的示例聚类, 我们将使用小写的$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$表示黑色t恤

基于不同的特性，额外的聚类可能包括四个以上的聚类, 比如一件衬衫是无袖还是有袖.

As seen in our example, 聚类方法将数据集中的所有样本划分为不相交的非空子集. In cluster $c$, 没有同时属于裤子子集和衬衫子集的图像:$c_1 \cap c_2 = \emptyset$. This concept can be extended; no two subsets of any cluster have the same sample.

聚类比较指标概述

大多数比较聚类的标准可以用对$C的混淆矩阵来描述, C’$. 混淆矩阵将是一个K × K矩阵，其中K × K的第K个元素(第K行和第K列的元素)是$C的$C_k$和$C的$C ' _{K '}$的$C ' $的$C ' $相交的样本数:

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

我们将使用我们简化的黑色和红色裤子和衬衫的例子来分解这个问题, 假设数据集D有100条红裤子, 200 black trousers, 200 红衫军, 300 black shirts. 让我们来看看$c$和$c " $的混淆矩阵:

由于$K = 2$和$K " = 4$，这是一个$2 \乘以4$矩阵. Let’s choose $k = 2$ and $k’’ = 3$. 我们看到元素$n_{kk '} = n_{23} = 200$. 这意味着$c_2$(衬衫)和${c^{\prime\prime}}_3$(红衬衫)的交集是200, 哪一个是正确的，因为$c_2 \cap {c^{\prime\prime}}_3$就是一组红衬衫.

基于底层聚类比较方法，聚类指标大致可分为三类:

In this article, 我们只触及了许多可用指标中的几个, 但是我们的示例将有助于定义三个集群度量组.

Pair-counting

成对计数需要检查所有成对的样本, 然后计算聚类一致和不一致的对. 每对样本可以属于四组中的一组, 其中集合元素计数($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)$, where $n$ represents the number of samples; it can also be read as (number of similarly treated pairs)/(total number of pairs). 虽然理论上它的值在0到1之间, 在实践中，它的范围往往要窄得多. 值越高意味着聚类之间的相似性越高. (Rand指数为1表示完全匹配，两个聚类具有相同的聚类.)

One limitation of the 兰德指数 is its behavior when the number of clusters increases to approach the number of elements; in this case, it converges toward 1, 在准确测量聚类相似性方面带来了挑战. 为了解决这个问题，已经引入了几个改进或修改版本的兰德指数. One variation is the adjusted 兰德指数; however, 它假设随机绘制两个具有固定数量的聚类和聚类元素的聚类.

Information 的ory

这些度量是基于信息论的一般概念. 我们将讨论其中的两个:熵和互信息(MI).

熵描述了聚类中有多少信息. 如果与聚类相关的熵为0, 这样，随机抽取的样本就没有不确定性了, 当只有一个集群时，哪一个是正确的.

MI描述了一个聚类提供了多少关于另一个聚类的信息. MI可以表明，知道$C$中的样本簇可以在多大程度上减少$C$中样本簇的不确定性.

Normalized mutual information MI是由聚类熵的几何或算术平均值归一化的吗. 标准MI不受常量的约束, 因此，规范化的互信息提供了一个更可解释的聚类度量.

这一类别中另一个流行的指标是 variation of information (VI)依赖于聚类的熵和MI. 设$H(C)$为聚类的熵，$I(C, C ')$为两个聚类之间的MI. 两个聚类之间的VI可以定义为$VI(C,C ') = H(C)+H(C ')-2I(C,C ')$. VI为0表示两个聚类之间的完美匹配.

设置重叠

集合重叠度量包括根据集群之间的最大重叠来确定$C$中的集群与$C ' $中的集群的最佳匹配. 对于这个类别中的所有指标，1表示聚类是相同的.

的 maximum matching measure 按降序扫描混淆矩阵，首先匹配混淆矩阵中最大的条目. 然后，它删除匹配的集群，并依次重复该过程，直到集群耗尽.

的 F-measure is another set overlap metric. Unlike the maximum matching measure, f度量经常用于比较聚类和最优解, 而不是比较两个聚类.

用F-measure应用聚类度量

因为f值在 machine learning models 还有一些重要的应用，比如搜索引擎, 我们将通过一个示例更详细地探讨f度量.

F-measure Definition

让我们假设$C$是我们的基本真理，或最优解. For any $k$th cluster in $C$, where $k \in [1, K]$, 我们将对聚类结果$C ' $中的每个聚类计算一个单独的f度量. 这个单独的f度量表明簇$C^\prime_{k '}$对簇$C_k$的描述有多好，可以通过 precision and recall (两个模型评价指标). 我们将$I_{kk '}$定义为$C ' '的$k$th聚类和$C ' '的$k ' $th聚类中元素的交集, $\lvert C_k \rvert$表示第k个簇中的元素个数.

• 精密$ p = \压裂{I_ {kk’}}{\ lvert C ' _ {k”}\ rvert} $

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

然后，第k$th和第k$th聚类的单个f测度可以计算为 harmonic mean 这些集群的精确率和召回率:

\ [f {kk”}= \压裂{2 rp} {r + p} = \压裂{2 i_ {kk}} {| C_k | + | C ' _ {k”}|}\]

现在，为了比较$C$和$C ' $，让我们看一下总体f指标. 首先，我们将创建一个类似于a的矩阵 contingency table 它们的f值是多少. 假设我们将$C$的集群映射为表的行，将$C$的集群映射为列, 表值对应于每个f值. 找出个体f值最大的群集对, 并删除与这些集群对应的行和列. 重复此操作，直到集群耗尽为止. 最后，我们可以定义总体f值:

\ [F (C, C ') = \压裂{1}{n} \ sum_ {i = 1} ^ K n_imax (F(为C_i C的_j)所有j的\ \ {1 K”}\]

As you can see, 总体f值是我们对集群的最大单个f值的加权和.

Data Setup and Expected Results

任何适合机器学习的Python笔记本, such as a Jupyter notebook, will work as our environment. 在我们开始之前，你可能想检查一下我的 GitHub repository’s README, extended readme_help_example.ipynb example file, 需求.文本文件。 file (the required libraries).

我们将使用GitHub存储库中的示例数据，该存储库由新闻文章组成. 数据的排列信息包括 类别, 标题, 日期, short_description:

我们可以用 熊猫 读取、分析和操作数据. 我们将按日期对数据进行排序，并选择一个小样本(10,因为完整的数据集非常大，所以我们的演示需要:

import 熊猫 as pd
Df = pd.read_json(“./sample_data/example_news_data.json", lines=True)
df.sort_values(=“日期”,原地= True)
df = df[:10000]
len(df['类别'].独特的())

在运行, 您应该看到笔记本输出结果30, 因为这个数据样本中有30个类别. You may also run df.头(4) to see how the data is stored. (它应该与本节中显示的表匹配.)

Optimizing 聚类 Features

在应用集群之前，我们应该首先 preprocess the text 减少模型的冗余特征，包括:

• 更新文本以使其具有统一的大小写.
• 删除数字或特殊字符.
• Performing lemmatization.
• Removing stop words.

进口再保险
进口nltk
从nltk.corpus import stopwords
从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:
    文本=文本.低()
    文本= re.sub('[^a-z]',' ',text)
    文本= re.sub('\s+', ' ', text)
    文本=文本.分割(" ")
    words = [wordnet_lemmatizer.如果单词不在stop_words中，则对文本中的单词进行引理化(word， 'v')    
    返回" ".加入(单词)

Df [' processsed_input '] = Df ['标题'].apply(preprocess)

得到的预处理标题如下所示 processed_input，您可以通过再次运行来观察 df.头(4):

现在, 我们需要将每个标题表示为一个数字向量，以便能够对其应用任何机器学习模型. 的re are various feature extraction techniques to achieve this; we will be using TF-IDF (词频率-逆文档频率). 这种技术减少了文档中出现频率高的单词的影响(在我们的示例中), news 标题s), 因为这些显然不应该成为聚类或分类的决定性特征.

from sklearn.群集导入agglomerativeclu群集，KMeans
from sklearn.feature_extraction.text import TfidfVectorizer

vectorizer = TfidfVectorizer(max_features=300, tokenizer=lambda x: x.分割(' '))
tfidf_mat = vectorizer.fit_transform (df [' processed_input '])
X = tfidf_mat.todense ()
X[X==0]=0.00001

下一个, 我们将尝试第一种聚类方法, agglomerative clustering, on these feature vectors.

聚类方法1:聚集聚类

考虑给定的新闻类别作为最优解, 让我们将这些结果与聚集聚类的结果进行比较(由于数据集中有30个类别，因此期望的聚类数量为30):

clusters_agg = Agglomerative聚类(n_clusters=30).fit_预测(X)
df['class_prd'] = clusters_agg.astype (int) 

We will identify the resulting clusters by integer labels; 标题s belonging to the same cluster are assigned the same integer label. 的 cluster_measure function from the compare_clusters 我们的GitHub存储库的模块返回聚合F-measure和完美匹配集群的数量，这样我们就可以看到我们的聚类结果有多准确:

from clustering.Compare_clusters import cluster_measure
# ' cluster_measure '要求给定的文本类别位于' text_类别 '列中
Df ['text_类别'] = Df ['类别']
Res_df, fmeasure_aggregate, true_matches = cluster_measure(df, gt_column= class_gt)
fmeasure_aggregate, len (true_matches)  

# Outputs: (0.19858339749319176, 0)

将这些聚类结果与最优解进行比较，我们得到一个低f值0.198和0个簇与实际类组匹配, 描述聚集的集群与我们选择的标题类别不一致. 让我们检查一下结果中的集群，看看它是什么样子的.

Df [Df ['class_prd'] == 0]['类别'].value_counts()

在检查结果时，我们看到这个聚类包含所有类别的标题:

政治          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

So, 考虑到我们的结果集群与最优解决方案不一致，我们的低f度量是有意义的. 然而, 重要的是要记住，我们选择的给定类别分类只反映了数据集的一种可能的划分. 低f值并不意味着聚类结果是错误的, 但是聚类结果与我们期望的数据划分方法不匹配.

聚类 Method 2: K-means

让我们在相同的数据集上尝试另一种流行的聚类算法:k-means聚类. 我们将创建一个新的数据框架，并使用 cluster_measure function again:

kmeans = kmeans (n_clusters=30, random_state=0).适合(X)
Df2 = df.副本()
df2['class_prd'] = kmeans.预测(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值. 首先，我们将把两个结果放到一个列中，用 class_gt 具有聚集聚类输出，并且 class_prd 具有k-means聚类输出的:

Df1 = df2.副本()
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)

With a higher F-measure of 0.4, 我们可以观察到，两种算法的聚类彼此之间的相似性大于它们与最优解的相似性.

发现更多关于增强的聚类结果

了解可用的集群比较指标将扩展您的 machine learning model analysis. 我们已经看到了f度量聚类度量的作用, 并为您提供了将这些学习应用于下一个聚类结果所需的基础知识. 为了了解更多，以下是我推荐的进一步阅读内容:

• Comparing 聚类s - An Overview by Dorothea Wagner and Silke Wagner
• 比较聚类——基于信息的距离 by Marina Meilă
• 聚类比较的信息理论测度:变量, 属性, 归一化和修正的机会 作者:Nguyen Xuan Vinh, Julien Epps, James Bailey

---

Toptal 工程博客向 Luis Bronchal 查看本文中提供的代码示例.