【K-Means聚类算法 + agglomerative层次聚类算法】机器学习公式推导计算+详细过程

- 日理万妓 2023-02-23 07:50 32阅读 0赞

**K-Means算法**

*  K-Means聚类算法是非监督学习方法。对于样本数据，按样本之间的距离大小，将样本划分为K个簇。让簇内的点之间距离尽可能的小，同时让簇之间的距离尽可能的大。
 *  簇划分为 （ C 1 , C 2 , C 3 , … , C k ） （C\_1, C\_2, C\_3, …, C\_k） （C1,C2,C3,…,Ck）

**目标函数，最小化平方误差**  
 E = ∑ i = 1 k ∑ x ∈ C i ∣ ∣ x − μ i ∣ ∣ 2 2 E = \\sum\_\{i=1\} ^ k \\sum\_\{x \\in C\_i\} ||x - \\mu\_i||^\{2\}\_2 \\quad E=i=1∑kx∈Ci∑∣∣x−μi∣∣22

(11.1)式中，$ \\mu\_i  是 簇 是簇 是簇 C\_i $的均值向量，即为质心。

μ i = 1 ∣ C i ∣ ∑ x ∈ C i x \\mu\_i = \\frac\{1\}\{|C\_i|\}\\sum\_\{x \\in C\_i\} x \\quad μi=∣Ci∣1x∈Ci∑x

**K-Means算法流程**

*  input：样本D, 簇个数k, 最大迭代次数T

D = x 1 , x 2 , x 3 , … , x n D = \{x\_1, x\_2, x\_3, …,x\_n\} D=x1,x2,x3,…,xn

*  output：簇划分

、 C = （ C 1 , C 2 , C 3 , … , C k ） C =（C\_1, C\_2, C\_3, …, C\_k） C=（C1,C2,C3,…,Ck）

1.从样本 D D D中随机选择 k k k个样本作为初始的k个质心向量： μ 1 ， μ 2 , μ 3 , … , μ k \{\\mu\_1，\\mu\_2, \\mu\_3, …, \\mu\_k\} μ1，μ2,μ3,…,μk,将每个簇初始化为 ∅ \\emptyset ∅

2.对于 t = 1 , 2 , 3 , … , T t = 1, 2, 3, …, T t=1,2,3,…,T

（1）对于 i = 1 , 2 , 3 , … , N i = 1, 2, 3, …, N i=1,2,3,…,N，计算样本 x i x\_i xi和各个执行向量 μ j , j = 1 , 2 , 3 , … , k \\mu\_j, j = 1, 2, 3, …, k μj,j=1,2,3,…,k的欧氏距离，将 x i x\_i xi划分到最近的簇中，更新 C j = C j ⋃ \{ x i \} C\_j = C\_j \\bigcup \\\{x\_i\\\} Cj=Cj⋃\{ xi\}

（2）对于 j = 1 , 2 , 3 , … , k j = 1, 2, 3, …, k j=1,2,3,…,k， C j C\_j Cj中所有的样本点重新计算新的质心

（3）如果所有的 k k k个质心向量都没有发生变化，那么跳转到步骤（3）

3.最终输出簇划分

C = （ C 1 , C 2 , C 3 , … , C k ） C =（C\_1, C\_2, C\_3, …, C\_k） C=（C1,C2,C3,…,Ck）

**评估方法-肘部法则公式**

S S E = ∑ i = 1 k ∑ x ∈ C i ∣ ∣ x − μ i ∣ ∣ 2 SSE = \\sum\_\{i=1\} ^ k \\sum\_\{x \\in C\_i\} ||x - \\mu\_i||^\{2\} \\quad SSE=i=1∑kx∈Ci∑∣∣x−μi∣∣2

上式中， C i C\_i Ci是第 i i i簇， x x x是 C i C\_i Ci中的样本点， μ i \\mu\_i μi是 C i C\_i Ci的质心，即 C i C\_i Ci所有样本的均值， S S E SSE SSE是所有样本的聚类误差。

**agglomerative算法**

*  agglomerative算法有两种实现方式：一种是“自底向上”的Hierarchical；另一种是“自顶向下”的Divisive。

\*\* Hierarchical算法 \*\*

*  Hierarchical算法：“自底向上”。首先每个样本点各自为一个类别，然后每一次迭代去距离最近的两个类别将他们合并，最后只有一个类别时，迭代结束。

\*\* 计算距离公式 \*\*

*  最小距离公式（single-linkage）：

d m i n ( C i , C j ) = m i n d i s t ( p , q ) d\_\{min\}(C\_i, C\_j) = min \\quad dist(p, q) \\quad dmin(Ci,Cj)=mindist(p,q)

*  上式中， C i , C j C\_i, C\_j Ci,Cj为聚类簇， p ∈ C i , q ∈ C j p \\in C\_i, q \\in C\_j p∈Ci,q∈Cj
 *  最大距离公式(complete-linkage)

d m a x ( C i , C j ) = m a x d i s t ( p , q ) d\_\{max\}(C\_i, C\_j) = max \\quad dist(p, q) \\quad dmax(Ci,Cj)=maxdist(p,q)

\*上式中， C i , C j C\_i, C\_j Ci,Cj为聚类簇， p ∈ C i , q ∈ C j p \\in C\_i, q \\in C\_j p∈Ci,q∈Cj

*  平均距离公式(average-linkage)

d a v g ( C i , C j ) = 1 ∣ C i ∣ ∣ C j ∣ ∑ p ∈ C i ∑ q ∈ C j d i s t ( p , q ) d\_\{avg\}(C\_i, C\_j) = \\frac\{1\}\{|C\_i||C\_j|\} \\sum\_\{p \\in C\_i\} \\sum\_\{q \\in C\_j\} dist(p, q) \\quad davg(Ci,Cj)=∣Ci∣∣Cj∣1p∈Ci∑q∈Cj∑dist(p,q)

*  上式中， C i , C j C\_i, C\_j Ci,Cj为聚类簇， p ∈ C i , q ∈ C j p \\in C\_i, q \\in C\_j p∈Ci,q∈Cj

**Hierarchical算法流程**

1.将每个样本作为一个簇。

2.计算任意两侧簇之间的距离，选取距离最近的两个簇。

3.将步骤2中的两个簇合并成一个新的簇，删除合并前的那两个簇。

4.重复步骤2、步骤3，直到所有簇仅剩一个簇，迭代结束。

> > > #### 欢迎大家交流学习，任何问题都可以留言 ####