k-means聚类算法原理及其实现

k-means(k-均值)算法是一种基于距离的聚类算法,它用质心(Centroid)到属于该质心的点距离这个度量来实现聚类,通常可以用于N维空间中对象。下面,我们以二维空间为例,概要地总结一下k-means聚类算法的一些要点: 除了随机选择的初始质心,后续迭代质心是根据给定的待聚类的集合S中点计算均值得到的,所以质心一般不是S中的点,但是标识的是一簇点的中心。 基本k-means算法,开始需要随机选择指定的k个质心,因为初始k个质心是随机选择的,所以每次执行k-means聚类的结果可能都不相同。如果初始随机选择的质心位置不好,可能造成k-means聚类的结果非常不理想。 计算质心:假设k-means聚类过程中,得到某一个簇的集合Ci={p(x1,y1), p(x2,y2), …,p(xn,yn)},则簇Ci的质心,质心x坐标为(x1+x2+ …+xn)/n,质心y坐标为(y1+y2+ …+yn)/n。 k-means算法的终止条件:质心在每一轮迭代中会发生变化,然后需要重新将非质心点指派给最近的质心而形

DBSCAN聚类算法原理及其实现

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)聚类算法,它是一种基于高密度连通区域的、基于密度的聚类算法,能够将具有足够高密度的区域划分为簇,并在具有噪声的数据中发现任意形状的簇。我们总结一下DBSCAN聚类算法原理的基本要点: DBSCAN算法需要选择一种距离度量,对于待聚类的数据集中,任意两个点之间的距离,反映了点之间的密度,说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难,所以对于二维空间中的点,可以使用欧几里德距离来进行度量。 DBSCAN算法需要用户输入2个参数:一个参数是半径(Eps),表示以给定点P为中心的圆形邻域的范围;另一个参数是以点P为中心的邻域内最少点的数量(MinPts)。如果满足:以点P为中心、半径为Eps的邻域内的点的个数不少于MinPts,则称点P为核心点。 DBSCAN聚类使用到一个k-距离的概念,k-距离是指:给定数据集P={p(i); i=0,1,…n},对于任意点P(i

聚类算法:K-means

K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大。该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标。 对于聚类问题,我们事先并不知道给定的一个训练数据集到底具有哪些类别(即没有指定类标签),而是根据需要设置指定个数类标签的数量(但不知道具体的类标签是什么),然后通过K-means算法将具有相同特征,或者基于一定规则认为某一些对象相似,与其它一些组明显的不同的数据聚集到一起,自然形成分组。之后,我们可以根据每一组的数据的特点,给定一个合适的类标签(当然,可能给出类标签对实际应用没有实际意义,例如可能我们就想看一下聚类得到的各个数据集的相似性)。 首先说明一个概念:质心(Centroid)。质心可以认为就是一个样本点,或者可以认为是数据集中的一个数据点P,它是具有相似性的一组数据的中心,即该组中每个数据点到P的距离都比到其