聚类是一种无监督学习。簇内的对象越相似,聚类的效果越好。

基于划分的聚类

K-means算法

算法步骤
1.随机选择K个中心点。
2.把每个数据点分配到离它最近的中心点。
3.重新计算每类中的点到该类中心点距离的平均值,求出新的中心点。
4.分配每个数据到它最近的中心点。
5.重复步骤3和4,直到所有的观测值不再被分配或是达到最大的迭代次数。

K-means算法

K-medoids算法

算法步骤
1.随机选择K个中心点。
2.把每个数据点分配到离它最近的中心点。
3.任意选择一个非中心对象点计算其与中心对象交换的总代价。
4.如果总代价为负值,则交换非中心点成为新的中心点。
5.循环2-4直到不再变化

具体过程

总结:适合球状分布数据,K-means容易被离群点影响,K-medoids弥补了这个缺点,但是复杂度高。

基于层次的聚类

数据集

AGNES算法

算法步骤
1.每一个对象作为初始簇。
2.找到距离最近的两个簇,进行合并,生成新的簇集合。
3.重复步骤2。

步骤图

DIANA算法

算法步骤
1.所有对象作为一个簇的集合。
2.置空两个空的集合A、B。
3.找出簇中与其它对象平均相异度最大的对象,放入集合A,其它的放入集合B。
4.计算每个对象到集合A中的对象的距离和该对象到B集合其它对象的距离,如果到A的最近距离小于到B中对象的最小距离,则将该对象放入集合A。
5.重复4直到不再变化。

步骤图

总结:可扩展性都不好,复杂度高,步骤不可撤销。

基于密度的算法

DBSCAN算法

算法步骤
1.给数据集中的所有对象标记为"unvisited"。
2.随机选择一个未访问的对象标记为"visited",检查它的邻域是否包含MinPts个对象,如果不是则标记为噪声点。否则为它创建一个新簇C,并把所有邻域中的对象加入簇N。
3.迭代的把N中不属于其它簇的对象加入C,邻域中包含大于MinPts的点都加入N,该点加入C。直到N为空。
4.重复2-3,直到所有对象都被访问。

基于网格的算法

SING算法

CLIQUE算法

Last modification:April 13, 2020
如果觉得我的文章对你有用,请随意赞赏