| 聚类算法总结 | 您所在的位置：网站首页 › 聚类分析效果不好 › 聚类算法总结 |
聚类算法总结
|
前言
聚类算法是一种无监督的算法，由于不需要训练集，算法简单快速，引用在一些工程里比较简单突出，今天来了解一下聚类算法。 k-means算法（k均值算法）算法步骤： （1）随机选取 K 个点，作为 K 类的聚类中心，用 K i K_i Ki表示 （2）遍历所有的数据点 P j P_j Pj，通过计算距离，找到距离 P j P_j Pj 最近的聚类中心点 K i K_i Ki，此时可以说第 j 个数据属于第 i 类 （3）分别计算第 i 类的所有数据的中心点，作为该类的新的聚类中心点。 （4）重复进行（2）（3）步骤。直到每一类的聚类中心不再发生变化 从算法中我们需要确定以下几个标准： k值的确定，我们必须确定我们算法中需要分几类计算距离公式，这个公式我们可以利用欧式距离来计算，聚类中心的计算：因为要不断更新聚类中心点，需要一个更新策略来更新 优点 k-平均算法是解决聚类问题的一种经典算法，算法简单、快速。对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是 O ( n k t ) O(nkt) O(nkt)，其中n是所有对象的数目，k是簇的数目，t是迭代的次数。通常k . . . - > x n x_n xn，类似于密度传导一样，那么， x n x_n xn由 x 1 x_1 x1 密度可达。这个性质说明了由密度直达的传递性，可以推导出密度可达。如果对于 x k x_k xk，使 x i x_i xi 和 x j x_j xj都可以由 x k x_k xk密度可达，那么，就称 x x i x_i xi和 x j x_j xj 密度相连。将密度相连的点连接在一起，就形成了我们的聚类簇。 通过上述算法我们可以看到算法需要两个参数： eps值，半径值，用来做区域MinPts值，用来判断哪些点是核心点西瓜书上的算法图： [外链图片转存失败(img-XUnqJLD8-1566869759407)(https://raw.githubusercontent.com/Klauszhao/picture/master/picture/cluster/DBSCAN%E8%81%9A%E7%B1%BB%E7%AE%97%E6%B3%95.png)] 英文算法： [外链图片转存失败(img-rOHqxEAp-1566869523673)(https://raw.githubusercontent.com/Klauszhao/picture/master/picture/cluster/DBSCAN%E8%8B%B1%E6%96%87%E7%89%88.jpg)] 优点自适应的聚类，不需要提前设定K值大小，可以自适应的做聚类结果。 对噪声不敏感。这是因为该算法能够较好地判断离群点，并且即使错判离群点，对最终的聚类结果也没什么影响 能发现任意形状的簇。这是因为DBSCAN 是靠不断连接邻域呢高密度点来发现簇的，只需要定义邻域大小和密度阈值，因此可以发现不同形状，不同大小的簇 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响 缺点对两个参数的设置敏感，即圈的半径 eps 、阈值 MinPts DBSCAN 使用固定的参数识别聚类。显然，当聚类的稀疏程度不同，聚类效果也有很大不同。即数据密度不均匀时，很难使用该算法 如果数据样本集越大，收敛时间越长。此时可以使用 KD 树优化 from sklearn.datasets.samples_generator import make_circles import matplotlib.pyplot as plt import time from sklearn.cluster import KMeans from sklearn.cluster import DBSCAN X,y_true = make_circles(n_samples=1000,noise=0.15) #这是一个圆环形状的 plt.scatter(X[:,0],X[:,1],c=y_true) plt.show() #DBSCAN 算法 t0 = time.time() dbscan = DBSCAN(eps=.1,min_samples=6).fit(X) # 该算法对应的两个参数 t = time.time()-t0 plt.scatter(X[:, 0], X[:, 1], c=dbscan.labels_) plt.title('time : %f'%t) plt.show() 凝聚式层次聚类层次聚类可以分为凝聚(agglomerative)层次聚类和分裂(divsive)层次聚类。分裂层次聚类采用的就是"自顶而下"的思想，先将所有的样本都看作是同一个簇，然后通过迭代将簇划分为更小的簇，直到每个簇中只有一个样本为止。凝聚层次聚类采用的是"自底向上"的思想，先将每一个样本都看成是一个不同的簇，通过重复将最近的一对簇进行合并，直到最后所有的样本都属于同一个簇为止。 算法步骤： 我们首先将每个数据点视为一个单一的簇，即如果我们的数据集中有 X 个数据点，那么我们就有 X 个簇。然后，我们选择一个测量两个簇之间距离的距离度量标准。作为例子，我们将用 average linkage，它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。在每次迭代中，我们将两个簇合并成一个。这两个要合并的簇应具有最小的 average linkage。即根据我们选择的距离度量标准，这两个簇之间的距离最小，因此是最相似的，应该合并在一起。重复步骤 2 直到我们到达树根，即我们只有一个包含所有数据点的簇。这样我们只需要选择何时停止合并簇，即何时停止构建树，来选择最终需要多少个簇！从算法中我们可以知道，我们需要提供一下： 距离计算公式，计算两个类之间的距离在凝聚层次聚类中，判定簇间距离的两个标准方法就是单连接(single linkage)和全连接(complete linkage)。单连接，是计算每一对簇中最相似两个样本的距离，并合并距离最近的两个样本所属簇。全连接，通过比较找到分布于两个簇中最不相似的样本(距离最远)，从而来完成簇的合并。 聚类算法（一）—— k-means算法以及其改进算法 聚类算法（三）——基于密度的聚类算法（以 DBSCAN 为例） 聚类算法（二）、聚类算法的系统性比较 |
【本文地址】