600字范文 > [Python] [机器学习] 基础聚类算法(K-means AHC DBSCAN)简介及可视化代码

[Python] [机器学习] 基础聚类算法(K-means AHC DBSCAN)简介及可视化代码

时间：2022-11-10 18:06:31

之前写的入门级介绍，有点久远有些ref找不着了

文章目录

简介目标作用类型聚类vs分类K-means[K-means] 伪代码[K-means] 过程详解[K-means] 初始点的选择[K-means] 距离的度量[K-means] 质心的选择[K-means] 参数确定[K-means] 优缺点AHC[AHC] 层次聚类类型[AHC] 伪代码[AHC] 过程详解[AHC] 邻近度度量[AHC] 优缺点DBSCAN[DBSCAN] 伪代码1[DBSCAN] 过程详解[DBSCAN] 三个点[DBSCAN] 伪代码2[DBSCAN] 参数确定[DBSCAN] 优缺点不同数据集效果对比其他知识点

简介

根据在数据中发现的描述对象及其关系的信息，将数据对象分组。对大量未知标注的数据集，按数据的内在相似性将数据集划分为多个类别，使类别内的数据相似度极大而类别间的数据相似度极小。

目标

组内的对象相互之间是相似的，不同组中的对象是不同的。

作用

易于理解

?生物学：界门纲目科属种

?信息检索：搜索引擎返回结果分类

?商业：对客户进行分类

更加实用

?降维：样本数的降维、特征数的降维

?发现最近邻：减少计算量

类型

聚类vs分类

import randomimport matplotlib.pyplot as pltimport pandas as pdfrom sklearn import datasetsfrom pandas import DataFrame# 造数据# 圈圈noisy_circles=datasets.make_circles(n_samples=1000,factor=.5,noise=.05)circle = DataFrame()circle['x1'] = noisy_circles[0][:,0]circle['x2'] = noisy_circles[0][:,1]circle['label'] = noisy_circles[1]# 堆堆def random_sample(num, mean, st):'''num：个数mean：均值st：标准差'''sample = []i = 0while i < num:sample.append(random.gauss(mean, st))i += 1return samplenum = 300sample_0 = pd.DataFrame({'x1':random_sample(num, 4, 0.5), 'x2': random_sample(num, 4, 0.5), 'y': [0 for i in range(num)]})sample_1 = pd.DataFrame({'x1':random_sample(num, 2, 0.5), 'x2': random_sample(num, 2, 0.5), 'y': [1 for i in range(num)]})sample = pd.concat([sample_0, sample_1])# 聚类vs分类plt.figure(figsize=(16,8))plt.subplot(1,2,1)plt.scatter(sample_0['x1'], sample_0['x2'], marker = 'o', c = 'k')plt.scatter(sample_1['x1'], sample_1['x2'], marker = 'o', c = 'k')plt.title('聚类（无监督）', fontsize =25)plt.subplot(1,2,2)plt.scatter(sample_0['x1'], sample_0['x2'], marker = 'o', c = 'b')plt.scatter(sample_1['x1'], sample_1['x2'], marker = 'o', c = 'r')plt.title('分类（有监督）', fontsize =25)plt.show()

K-means

[K-means] 伪代码

#####################################

选择kkk个点作为初始质心。repeat 将每个点指派到最近的质心，形成kkk个簇。重新计算每个簇的质心。until质心不发生变化。

#####################################

[K-means] 过程详解

ref: GitHub: snippet-code

# 修改data = samplerepeat = 20# ================开始================# 导入数据points = [[data.iloc[i].x1, data.iloc[i].x2] for i in range(len(data))]# 初始质心currentCenter1 = [data.x1.min() + (data.x1.max()-data.x1.min())*random.random(), data.x1.min() + (data.x2.max()-data.x2.min())*random.random()]currentCenter2 = [data.x1.min() + (data.x1.max()-data.x1.min())*random.random(), data.x1.min() + (data.x2.max()-data.x2.min())*random.random()]# 记录每次迭代后每个簇的质心的更新轨迹center1 = [currentCenter1]; center2 = [currentCenter2]# 丢点图plt.figure(figsize=(18,18))ax = plt.subplot(3,3, 1)change_ax(ax)plt.title('step 0', fontsize = 15)plt.plot([eachpoint[0] for eachpoint in points], [eachpoint[1] for eachpoint in points], '.', color='grey')plt.scatter([eachcenter[0] for eachcenter in center1], [eachcenter[1] for eachcenter in center1], marker='x', c='b', s=100)plt.scatter([eachcenter[0] for eachcenter in center2], [eachcenter[1] for eachcenter in center2], marker='x', c='g', s=100)# 两个簇group1 = []; group2 = []for runtime in range(repeat):group1 = []; group2 = []for eachpoint in points:# 计算每个点到质心的距离distance1 = pow(abs(eachpoint[0]-currentCenter1[0]),2) + pow(abs(eachpoint[1]-currentCenter1[1]),2)distance2 = pow(abs(eachpoint[0]-currentCenter2[0]),2) + pow(abs(eachpoint[1]-currentCenter2[1]),2)# 将该点指派到离它最近的质心所在的簇mindis = min(distance1,distance2)if(mindis == distance1):group1.append(eachpoint)else:group2.append(eachpoint)if runtime < 5 or runtime > (repeat - 4): # 只可视化前五次最后三次if runtime < 5:ax = plt.subplot(3,3, runtime+2)change_ax(ax)plt.title('step %d'%(runtime+1), fontsize = 15)else:ax = plt.subplot(3,3, 10-repeat+runtime)change_ax(ax)plt.title('step %d'%(runtime+1), fontsize = 15)# 打印所有的点，用颜色标识该点所属的簇plt.plot([eachpoint[0] for eachpoint in group1], [eachpoint[1] for eachpoint in group1], '.', color='lightsteelblue')#, linewidth=1)plt.plot([eachpoint[0] for eachpoint in group2], [eachpoint[1] for eachpoint in group2], '.', color='lightgreen')#, linewidth=0.3)# 画质心plt.plot([eachcenter[0] for eachcenter in center1], [eachcenter[1] for eachcenter in center1],'bx')plt.plot([eachcenter[0] for eachcenter in center1], [eachcenter[1] for eachcenter in center1], 'b--', linewidth=0.5)plt.plot([eachcenter[0] for eachcenter in center2], [eachcenter[1] for eachcenter in center2],'gx')plt.plot([eachcenter[0] for eachcenter in center2], [eachcenter[1] for eachcenter in center2], 'g--', linewidth=0.5)# 指派完所有的点后，更新每个簇的质心currentCenter1 = [sum([eachpoint[0] for eachpoint in group1])/len(group1),sum([eachpoint[1] for eachpoint in group1])/len(group1)]currentCenter2 = [sum([eachpoint[0] for eachpoint in group2])/len(group2),sum([eachpoint[1] for eachpoint in group2])/len(group2)]# 记录该次对质心的更新center1.append(currentCenter1)center2.append(currentCenter2)plt.show()

[K-means] 初始点的选择

随机选取

kmeans++kmeans++kmeans++

在选取第一个聚类中心(n=1)(n=1)(n=1)时同样通过随机的方法。

假设已经选取了nnn个初始聚类中心(0<n<k)(0<n<k)(0<n<k)，则在选取第n+1n+1n+1个聚类中心时：距离当前nnn个聚类中心越远的点会有更高的概率被选为第n+1n+1n+1个聚类中心。

结合其他算法

选用层次聚类或CanopyCanopyCanopy算法进行初始聚类，然后从kkk个类别中分别随机选取kkk个点，来作为kmeanskmeanskmeans的初始聚类中心点。

[K-means] 距离的度量

曼哈顿距离

d(x,y)=∑k=1n∣xk−yk∣d(x,y)=\sum_{k=1}^n|x_k-y_k| d(x,y)=k=1∑n∣xk−yk∣

欧几里得距离

d(x,y)=∑k=1n(xk−yk)2d(x,y)=\sum_{k=1}^n(x_k-y_k)^2 d(x,y)=k=1∑n(xk−yk)2

余弦相似度

d(x,y)=cos(x,y)=x⋅y∣∣x∣∣∣∣y∣∣d(x,y)=cos(x,y)=\frac{x\cdot y}{||x||\ ||y||} d(x,y)=cos(x,y)=∣∣x∣∣∣∣y∣∣x⋅y

其中，"⋅\cdot⋅"表示向量点积，∣∣x∣∣||x||∣∣x∣∣是向量x的长度。

BregmanBregmanBregman散度

d(x,y)=ϕ(x)−ϕ(y)−⟨∇ϕ(y),(x−y)⟩d(x,y)=\phi(x)-\phi(y)-\langle\nabla\phi(y),(x-y)\rangle d(x,y)=ϕ(x)−ϕ(y)−⟨∇ϕ(y),(x−y)⟩

其中，ϕ(⋅)\phi(\cdot)ϕ(⋅)是一个严格的凸函数，∇ϕ(y)\nabla\phi(y)∇ϕ(y)是在yyy上计算的ϕ\phiϕ的梯度，x−yx-yx−y是xxx与yyy的向量差，而⟨∇ϕ(y),(x−y)⟩\langle\nabla\phi(y),(x-y)\rangle⟨∇ϕ(y),(x−y)⟩是两者的内积。

[K-means] 质心的选择

[K-means] 参数确定

K值确定

根据实际情况确定

?设计新款时确定潜在客户（新款数已知）

肘部法则

肘部法则会把不同kkk值的成本函数值画出来。随着kkk值的增大，平均畸变程度会减小；每个类包含的样本数会减少，于是样本离其质心会更近。

但是，随着kkk值继续增大，平均畸变程度的改善效果会不断减低。k值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的kkk值就是肘部。

CostFunction：J=∑i=1k∑x∈Cid(x,ci)Cost\ \ Function：\ J=\sum_{i=1}^k\sum_{x\in C_i}d(x,c_i) CostFunction：J=i=1∑kx∈Ci∑d(x,ci)

from sklearn.cluster import KMeanscri = pd.DataFrame(columns=['k', 'j'])for i in range(1,11):km = KMeans(n_clusters=i)km.fit(sample[['x1', 'x2']])cri.loc[i] = [i, km.inertia_]plt.figure(figsize=(13,7))plt.plot(cri['k'], cri['j'])plt.title("肘部法则", fontsize = 25)plt.xlabel('k(聚类个数)', fontsize =15)plt.ylabel('损失函数', fontsize = 15)plt.show()

与层次聚类结合

首先采用层次凝聚算法决定结果粗的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。

稳定性方法、系统演化方法、Calinski−HarabaszCalinski-HarabaszCalinski−Harabasz准则法、轮廓系数法等（参考从零开始实现Kmeans聚类算法、kmeans算法原理以及实践操作(多种k值确定以及如何选取初始点方法)）

[K-means] 优缺点

优点：

算法快速、简单容易解释适用于高维

缺点：

对离群点敏感，对噪声点和孤立点很敏感需要自定义kkk不同的初始点可能得到的结果完全不同不适用于非凸的簇或大小差别很大的簇

AHC

AHCAHCAHC(凝聚层次聚类): AgglomerativeHierarchicalAlgorithmsAgglomerative Hierarchical AlgorithmsAgglomerativeHierarchicalAlgorithms

[AHC] 层次聚类类型

产生层次聚类的基本方法

凝聚的：从点作为个体簇开始，每一步合并两个最接近的簇。

分裂的：从包含所有点的某个簇开始，每一步分裂一个簇

[AHC] 伪代码

#####################################

如果需要，计算邻近度矩阵。repeat 合并最接近的两个簇。更新邻近性矩阵，以反映新的簇与原来的簇之间的邻近性。until仅剩下一个簇。

#####################################

[AHC] 过程详解

欧式距离矩阵（组平均）：

0123Step1:0123[0604104720]⟹将1和2合并为A\begin{matrix} 0&1&2&3 \end{matrix}\ \ \ \ \ \ \ \\ Step\ 1: \ \ \ \ \ \ \ \ \ \ \ \begin{matrix} 0 \\1\\2\\3 \end{matrix} \left[ \begin{matrix} 0& \\ 6&0 \\ 4&1&0 \\ 4&7&2&0 \end{matrix} \right] \ \ \ \ \ \Longrightarrow将1和2合并为A 0123Step1:0123⎣⎢⎢⎡0644017020⎦⎥⎥⎤⟹将1和2合并为A

03AStep2:03A[04054.50]⟹将0和3合并为B\begin{matrix} 0&3&A \end{matrix}\ \ \ \ \ \ \ \\ Step\ 2: \ \ \ \ \ \ \ \ \ \ \ \ \begin{matrix} 0\\3\\A \end{matrix} \left[ \begin{matrix} 0& \\ 4&0 \\ 5&4.5&0 \end{matrix} \right] \ \ \ \ \ \Longrightarrow将0和3合并为B 03AStep2:03A⎣⎡04504.50⎦⎤⟹将0和3合并为B

ABStep3:AB[04.750]⟹将A和B合并为C\begin{matrix} A&B \end{matrix}\ \ \ \ \ \ \ \ \ \\ Step\ 3: \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{matrix} A\\B \end{matrix} \left[ \begin{matrix} 0& \\ 4.75&0 \\ \end{matrix} \right] \ \ \ \ \ \Longrightarrow将A和B合并为C ABStep3:AB[04.750]⟹将A和B合并为C

num = 4dist = pd.DataFrame(squareform(sample))plt.figure(figsize=(8,5))row_clusters = linkage(sample, method='average')row_dendr = dendrogram(row_clusters,labels=list(range(num)))plt.annotate('A', (9.5,0.6), fontsize=30, color='tomato')plt.annotate('B', (30,3.6), fontsize=30, color='tomato')plt.annotate('C', (19,4.35), fontsize=30, color='tomato')plt.ylabel('距离', fontsize=20)plt.xlabel('样本', fontsize=20)plt.tight_layout()

[AHC] 邻近度度量

MIN（单链）：两个簇的两个最近的点之间的距离。MAX（全链）：两个簇的两个最远的点之间的距离。组平均：两个簇的所有点对邻近度的平均值。

4.Ward法：两个簇合并时导致的平方误差的增量。

5.质心法：两个簇质心之间的距离。

[AHC] 优缺点

优点：

不用提前确定聚类个数（想要分多少个簇都可以直接根据树结构来得到结果）

缺点：

计算量和存储量大不可撤销（簇之间不能交换对象）

DBSCAN

DBSCAN:Density−BasedSpatialClusteringofApplicationswithNoiseDBSCAN:\ Density-Based\ Spatial\ Clustering\ of\ Applications\ with\ NoiseDBSCAN:Density−BasedSpatialClusteringofApplicationswithNoise

[DBSCAN] 伪代码1

[DBSCAN] 过程详解

……

[DBSCAN] 三个点

核心点：以该点为圆心，EpsEpsEps半径内有大于等于MinPtsMinPtsMinPts个样本。

边界点：以该点为圆心，EpsEpsEps半径内仅有小于个MinPtsMinPtsMinPts样本，但在核心点的邻域中。

噪声点：以该点为圆心，EpsEpsEps半径内仅有小于个MinPtsMinPtsMinPts样本，且不在核心点的邻域中。

[DBSCAN] 伪代码2

#####################################

将所有点标记为核心点、边界点或噪声点。删除噪声点。为距离在EpsEpsEps之内的所有核心点之间赋予一条边。每组连通的核心点形成一个簇。将每个边界点指派到一个与之关联的核心点的簇中。

#####################################

[DBSCAN] 参数确定

Eps：

a. 试…

from sklearn import datasetsfrom sklearn.cluster import DBSCANdef lin_dbscan(sample, eps, minpts):'''单个DBSCAN结果画图'''dbscan = DBSCAN(eps = eps, min_samples = minpts)sample['dbscan'] = dbscan.fit_predict(sample[['x1', 'x2']])a = pd.DataFrame(sample.dbscan.value_counts())clusters = a.indextry:clusters = clusters.drop([-1])noise = sample[sample['dbscan'] == -1]ns = plt.scatter(noise['x1'], noise['x2'], marker='x')plt.legend([ns], ['噪声点'], fontsize = 13, loc='lower right')except:#print('eps=%g, MinPts=%d 没有噪声点'%(dbscan.eps, dbscan.min_samples))passfor i in clusters:temp = sample[sample['dbscan'] == i]plt.scatter(temp['x1'], temp['x2'])plt.title('Eps=%g, MinPts=%d \n 分为%d类'%(dbscan.eps, dbscan.min_samples, len(clusters)), fontsize =20)param = {1: [0.1, 10],2: [0.1, 20],3: [0.1, 30],4: [0.2, 25],5: [0.2, 32],6: [0.2, 35]}plt.figure(figsize=(16,10))plt.subplots_adjust(hspace = 0.3)for i in param.keys():plt.subplot(2,3,i)eps = param.get(i)[0]minpts = param.get(i)[1]lin_dbscan(circle, eps, minpts)

b. kkk-距离曲线

给定kkk邻域参数kkk,对于数据中的每个点，计算对应的第kkk个最近邻域距离，并将数据集所有点对应的最近邻域距离按照降序方式排序，称这幅图为排序的kkk距离图，选择该图中第一个谷值点位置对应的k距离值设定为EpsEpsEps。

import numpy as npdef cal_dist(a,b):'''计算两个变量之间的距离'''c = a-bdist = np.sqrt(np.dot(c, c.transpose()))return distdef single_sample_dist(sample, sample_no, k):'''计算单个变量的第k近邻'''k_sample = []a = np.array([sample.iloc[sample_no].x1, sample.iloc[sample_no].x2])for i in range(len(sample)):b = np.array([sample.iloc[i].x1, sample.iloc[i].x2])k_sample.append(cal_dist(a,b))k_sample.sort()if np.mod(sample_no, 100) == 0:print("第%d个变量距离计算完毕！"%(sample_no))return k_sample[k]def sample_dist(sample, k):'''计算所有变量的第k近邻'''dists = []for i in range(len(sample)):dists.append(single_sample_dist(sample, i, k))return distsdef plot_dist(sample, k):'''画出k近邻的距离图'''dists = sample_dist(sample, k)dists.sort()plt.figure(figsize=(15,8))plt.plot(dists)plt.title('%dth近邻距离图'%(k), fontsize = 25)plt.savefig('./pic/%dth近邻距离图.jpg'%(k))plt.show()return distsdists = plot_dist(circle, 10)

2.MinPts：MinPts≥dim+1

dimdimdim表示待聚类数据的维度