聚类是一种无监督的机器学习方法，它只根据每个样本的特征将给定的数据分成几组. 将数据分类成簇可以帮助识别样本之间未知的相似性或揭示数据集中的异常值. In the real world, clustering has significance across diverse fields from marketing to biology: 聚类 applications include market segmentation, social network analysis, diagnostic medical imaging.

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

When analyzing a data set, we need a way to accurately measure the performance of different clustering algorithms; we may want to contrast the solutions of two algorithms, 或者查看聚类结果与预期解决方案的接近程度. In this article, 我们将探讨一些指标，这些指标可用于比较从相同数据获得的不同聚类结果.

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

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

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

• $D$: the data set
• $A$， $B$:两个集群，它们是我们数据集的子集
• $C$: the ground truth clustering of $D$ that we will compare another cluster to
  • 聚类C K集群美元,美元$ C = {C₁,…,C_k} $
• $C’$: a second clustering of $D$
  • 聚类 $C’$ has $K’$ clusters, $C’ = {C^\prime_1, …, C^\prime_{k^\prime}}$

聚类结果不仅会根据排序特征变化，还会根据聚类的总数变化. 的 result depends on the algorithm, 它对微小扰动的敏感性, the model’s parameters, the data’s features. 使用我们之前提到的黑色和红色裤子和衬衫的数据集, there are a variety of clustering results that might be produced from different algorithms.

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

Additional clusterings might include more than four clusters based on different features, 比如一件衬衫是无袖还是有袖.

As seen in our example, a clustering method divides all the samples in a data set into non-empty disjoint subsets. 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'}|\]

We’ll break this down using our simplified black and red trousers and shirts example, 假设数据集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$. This means that the intersection of $c_2$ (shirts) and ${c^{\prime\prime}}_3$ (红衫军) is 200, which is correct since $c_2 \cap {c^{\prime\prime}}_3$ would simply be the set of 红衫军.

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

In this article, 我们只触及了许多可用指标中的几个, but our examples will serve to help define the three clustering metric groups.

Pair-counting

成对计数需要检查所有成对的样本, 然后计算聚类一致和不一致的对. 每对样本可以属于四组中的一组, where the set element counts ($N_{ij}$) are obtained from the confusion matrix:

• $S_{11}$, with $N_{11}$ elements: the pair’s elements are in the same cluster under both $C$ and $C’$
  • A pair of two 红衫军 would fall under $S_{11}$ when comparing $c$ and $c’’$
• $S_{00}$, with $N_{00}$ elements: the pair’s elements are in different clusters under both $C$ and $C’$
  • A pair of a red shirt and black trousers would fall under $S_{00}$ when comparing $c$ and $c’’$
• $S_{10}$, $N_{10}$元素:这对元素在$C$中属于同一个簇，在$C ' $中属于不同的簇
  • A pair of a red shirt and a black shirt would fall under $S_{10}$ when comparing $c$ and $c’’$
• $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之间, 在实践中，它的范围往往要窄得多. 值越高意味着聚类之间的相似性越高. (A 兰德指数 of 1 would represent a perfect match where two clusterings have identical clusters.)

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 is MI that is normalized by the geometric or arithmetic mean of the entropies of clusterings. 标准MI不受常量的约束, so normalized mutual information provides a more interpretable clustering metric.

这一类别中另一个流行的指标是 variation of information (VI)依赖于聚类的熵和MI. Let $H(C)$ be the entropy of a clustering and $I(C, C’)$ be the MI between two clusterings. 两个聚类之间的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, the F-measure is frequently used to compare a clustering to an optimal solution, 而不是比较两个聚类.

用F-measure应用聚类度量

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

F-measure Definition

让我们假设$C$是我们的基本真理，或最优解. For any $k$th cluster in $C$, where $k \in [1, K]$, we’ll calculate an individual F-measure with every cluster in clustering result $C’$. 这个单独的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}$

的n, the individual F-measure of the $k$th and $k’$th cluster can be calculated as the harmonic mean 这些集群的精确率和召回率:

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

现在，为了比较$C$和$C ' $，让我们看一下总体f指标. 首先，我们将创建一个类似于a的矩阵 contingency table 它们的f值是多少. Let’s assume that we’ve mapped $C$’s clusters as rows of a table and $C’$’s clusters as columns, 表值对应于每个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'}\]

As you can see, the overall F-measure is the weighted sum of our maximum individual F-measures for the clusters.

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).

We’ll use the sample data in the GitHub repository, which is made up of news articles. 数据的排列信息包括 类别, 标题, 日期, 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), as these clearly should not be the deciding features in clustering or classifying them.

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` requires given text categories to be in the column ‘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)

On comparing these cluster results with the optimal solution, we get a low F-measure of 0.198和0个簇与实际类组匹配, depicting that the agglomerative clusters do not align with the 标题 categories we chose. 让我们检查一下结果中的集群，看看它是什么样子的.

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

Upon examining the results, we see that this cluster contains 标题s from all the categories:

政治          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值并不意味着聚类结果是错误的, but that the clustering result didn’t match our desired method of partitioning the data.

聚类 Method 2: K-means

Let’s try another popular clustering algorithm on the same data set: k-means clustering. 我们将创建一个新的数据框架，并使用 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, 我们可以观察到，两种算法的聚类彼此之间的相似性大于它们与最优解的相似性.

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

An understanding of the available clustering comparison metrics will expand your machine learning model analysis. 我们已经看到了f度量聚类度量的作用, gave you the basics you need to apply these learnings to your next clustering result. 为了了解更多，以下是我推荐的进一步阅读内容:

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

---

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