文章目录
0. 引言1. 聚类2. 层次聚类2.1 概念2.2 例子
3. k 均值聚类3.1 概念3.2 例子
4. 参考
0. 引言
前情提要： 《NLP深入学习（一）：jieba 工具包介绍》 《NLP深入学习（二）：nltk 工具包介绍》 《NLP深入学习（三）：TF-IDF 详解以及文本分类/聚类用法》 《NLP深入学习（四）：贝叶斯算法详解及分类/拼写检查用法》 《NLP深入学习（五）：HMM 详解及字母识别/天气预测用法》 《NLP深入学习（六）：n-gram 语言模型》 《NLP深入学习（七）：词向量》 《NLP深入学习（八）：感知机学习》 《NLP深入学习（九）：KNN 算法及分类用法》 《NLP深入学习（十）：决策树（ID3、C4.5以及CART）》 《NLP深入学习（十一）：逻辑回归（logistic regression）》 《NLP深入学习（十二）：支持向量机（SVM）》 《NLP深入学习（十三）：AdaBoost 算法》
1. 聚类
聚类的目的是在没有预定义类别标签的情况下，根据数据集中的样本特征，自动将相似的数据对象划分为不同的组或簇（clusters），每个簇内的成员具有较高的相似度，而不同簇之间的成员差异较大。
聚类一般涉及到计算样本的相似度，以下是欧式距离、马氏距离和Cosine相似度的公式介绍：
欧式距离 (Euclidean Distance): 欧式距离是最直观的距离度量方式之一，在多维空间中，它衡量的是两个点之间的直线距离。对于二维空间中的两个点
P
1
(
x
1
,
y
1
)
P_1(x_1, y_1)
P1(x1,y1) 和
P
2
(
x
2
,
y
2
)
P_2(x_2, y_2)
P2(x2,y2)，欧式距离公式为：
d
E
(
P
1
,
P
2
)
=
(
x
2
−
x
1
)
2
+
(
y
2
−
y
1
)
2
d_E(P_1, P_2) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}
dE(P1,P2)=(x2−x1)2+(y2−y1)2
在 n 维空间中，对于两个向量
x
=
[
x
1
,
x
2
,
.
.
.
,
x
n
]
\mathbf{x} = [x_1, x_2, ..., x_n]
x=[x1,x2,...,xn] 和
y
=
[
y
1
,
y
2
,
.
.
.
,
y
n
]
\mathbf{y} = [y_1, y_2, ..., y_n]
y=[y1,y2,...,yn]，其计算公式扩展为：
d
E
(
x
,
y
)
=
∑
i
=
1
n
(
x
i
−
y
i
)
2
d_E(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}
dE(x,y)=i=1∑n(xi−yi)2
马氏距离 (Mahalanobis Distance): 马氏距离考虑了数据集协方差结构，用于衡量在具有特定分布特性的多维空间中两个点间的“有效”距离。对于服从同一多变量正态分布的数据点
x
\mathbf{x}
x 和
y
\mathbf{y}
y，以及协方差矩阵
Σ
\Sigma
Σ，马氏距离定义为：
D
M
(
x
,
y
)
=
(
x
−
y
)
⊤
Σ
−
1
(
x
−
y
)
D_M(\mathbf{x}, \mathbf{y}) = \sqrt{(\mathbf{x} - \mathbf{y})^\top \Sigma^{-1} (\mathbf{x} - \mathbf{y})}
DM(x,y)=(x−y)⊤Σ−1(x−y)
当协方差矩阵是对角阵或单位阵时，马氏距离简化为标准化后的欧氏距离。 余弦相似度 (Cosine Similarity): 余弦相似度并不是一种距离度量，而是一种衡量两个非零向量之间方向的相似程度的方法。它通过计算两个向量的夹角余弦值来评估它们的相似性。对于两个非零向量
x
\mathbf{x}
x 和
y
\mathbf{y}
y，它们的余弦相似度定义为两向量的点积除以各自模长的乘积：
C
o
s
S
i
m
(
x
,
y
)
=
cos
(
θ
)
=
x
⋅
y
∥
x
∥
∥
y
∥
=
∑
i
=
1
n
x
i
y
i
∑
i
=
1
n
x
i
2
∑
i
=
1
n
y
i
2
CosSim(\mathbf{x}, \mathbf{y}) = \cos(\theta) = \frac{\mathbf{x} \cdot \mathbf{y}}{\|\mathbf{x}\| \|\mathbf{y}\|} = \frac{\sum_{i=1}^{n} x_i y_i}{\sqrt{\sum_{i=1}^{n} x_i^2} \sqrt{\sum_{i=1}^{n} y_i^2}}
CosSim(x,y)=cos(θ)=∥x∥∥y∥x⋅y=∑i=1nxi2
∑i=1nyi2
∑i=1nxiyi 通常情况下，我们会直接使用上述点积与模长乘积的比值得到一个介于-1（完全相反）和1（完全相同方向）之间的相似度分数。在实际应用中，通常会忽略符号，取其绝对值作为相似度值。
2. 层次聚类
2.1 概念
层次聚类（Hierarchical Clustering）是一种通过构建一个层次结构或树状图来组织数据集的聚类方法。该方法能够发现数据点之间的层级关系，形成从单个对象开始逐渐合并或者分裂到最终形成一个单一聚类或者多个聚类的过程。以下是自下而上层次聚类的一般流程：
初始化： 将每个样本视为一个独立的簇。 计算相似度/距离矩阵： 计算所有样本对之间的相似度或距离，得到一个n×n的矩阵，其中n是样本数量。 最近邻聚类合并： 找出当前距离最近的两个簇（通常是根据它们之间最近样本对的距离决定），将这两个簇合并成一个新的簇。 更新相似度/距离矩阵： 合并后的簇与剩余未合并的簇之间的距离需要重新计算，通常采用某种链接策略如单链接（最小距离法）、全链接（最大距离法）、平均链接（UPGMA）或 Ward 方法等。 迭代过程： 重复步骤3和步骤4，直到达到预设的终止条件，比如：
所有样本被合并为一个大簇；达到了指定的簇数；连接距离超过某个阈值。 生成树状图（Dendrogram）： 记录每次合并的过程，可以绘制出一个树状图来可视化整个聚类过程和结果，它反映了不同层次上的簇间关系。
层次聚类的一个例子可以通过一个简单的二维数据集来说明，这里我们使用凝聚型（自下而上）的层次聚类方法，并假设采用平均链接（UPGMA）作为连接策略。以下是具体步骤：
2.2 例子
给一个层次聚类的例子，假设我们有一组城市的数据，包括它们的人口数量和平均年收入。我们想要通过层次聚类将这些城市进行分组。
假设我们有以下城市数据：
城市人口（百万）平均年收入（万元）城市128城市2310城市316城市4412城市5515
我们可以使用层次聚类来将这些城市进行分组。同样，我们首先计算城市之间的相似性，可以使用欧氏距离或其他相似性度量。然后，选择最相似的两个城市进行合并，形成一个新的聚类。这个过程不断重复，直到所有的城市都被合并为一个大的聚类。
初始聚类：
初始聚类：
1. 城市1
2. 城市2
3. 城市3
4. 城市4
5. 城市5
接下来，计算相似性并合并最相似的两个聚类：
合并聚类1：(城市3) 和 聚类2：(城市1)
合并后：
1. (城市1, 城市3)
2. 城市2
3. 城市4
4. 城市5
再次计算相似性并合并最相似的两个聚类：
合并聚类1：(城市1, 城市3) 和 聚类2：(城市2)
合并后：
1. (城市1, 城市3, 城市2)
2. 城市4
3. 城市5
继续这个过程，最终得到包含所有城市的单一聚类：
最终聚类：
1. (城市1, 城市3, 城市2, 城市4, 城市5)
这就是一个简单的层次聚类的例子，将城市根据其人口和平均年收入进行分组。
3. k 均值聚类
3.1 概念
k 均值聚类（K-means Clustering）是一种基于迭代优化的无监督学习方法，用于将数据集中的样本划分为预设数量（k）的簇。该算法的主要目标是找到 k 个中心点，并使每个簇内的样本与所属簇中心的距离平方和最小化。
以下是k均类聚类算法的基本步骤：
初始化：
随机选择 k 个数据点作为初始的簇中心（质心），记作
μ
1
,
μ
2
,
.
.
.
,
μ
k
\mu_1, \mu_2, ..., \mu_k
μ1,μ2,...,μk。 分配样本到簇：
对于数据集中的每一个样本
x
i
x_i
xi，计算其与各个簇中心之间的距离（通常使用欧氏距离）。将每个样本分配给与其最近的簇中心对应的簇。 更新簇中心：
计算每个簇中所有样本的均值（即新的簇中心）。更新每个簇的中心位置为该簇内所有样本坐标的平均值。 重复迭代：
重复步骤2和步骤3，直到达到某个停止条件为止，例如：簇中心不再显著变化，或者达到预设的最大迭代次数。 终止并输出结果：
当满足停止条件时，算法结束，并输出最终确定的簇划分以及每个簇的中心点。
3.2 例子
好的，下面是一个使用k均值（k-means）算法的简单例子。假设我们有一组包含二维数据点的数据集，我们想要将这些数据点分为两个簇。
假设我们有以下数据点：
数据点X坐标Y坐标数据点112数据点223数据点358数据点467数据点583数据点6102
我们希望使用k均值算法将这些数据点分为两个簇。下面是k均值算法的步骤：
初始化聚类中心： 随机选择两个数据点作为初始聚类中心。 初始聚类中心：
聚类中心1：(1, 2)聚类中心2：(8, 3) 分配数据点到最近的聚类中心： 计算每个数据点到两个聚类中心的距离，并将其分配到距离最近的聚类中心。 第一轮分配：
聚类1：数据点1, 数据点2, 数据点6聚类2：数据点3, 数据点4, 数据点5 更新聚类中心： 计算每个簇中数据点的均值，将其作为新的聚类中心。 新聚类中心：
聚类中心1：(4.33, 2.33)聚类中心2：(6.33, 6.0) 重复步骤2和步骤3： 重复以上步骤，直到聚类中心不再发生显著变化或达到预定的迭代次数。 第二轮分配：
聚类1：数据点1, 数据点2, 数据点6聚类2：数据点3, 数据点4, 数据点5 新聚类中心：
聚类中心1：(4.33, 2.33)聚类中心2：(6.33, 6.0)
在这个例子中，经过几轮迭代后，k均值算法收敛，最终的聚类结果为两个簇：
聚类1：数据点1, 数据点2, 数据点6聚类2：数据点3, 数据点4, 数据点5
4. 参考
《NLP深入学习（一）：jieba 工具包介绍》 《NLP深入学习（二）：nltk 工具包介绍》 《NLP深入学习（三）：TF-IDF 详解以及文本分类/聚类用法》 《NLP深入学习（四）：贝叶斯算法详解及分类/拼写检查用法》 《NLP深入学习（五）：HMM 详解及字母识别/天气预测用法》 《NLP深入学习（六）：n-gram 语言模型》 《NLP深入学习（七）：词向量》 《NLP深入学习（八）：感知机学习》 《NLP深入学习（九）：KNN 算法及分类用法》 《NLP深入学习（十）：决策树（ID3、C4.5以及CART）》 《NLP深入学习（十一）：逻辑回归（logistic regression）》 《NLP深入学习（十二）：支持向量机（SVM）》 《NLP深入学习（十三）：AdaBoost 算法》
好文阅读
发表评论