聚类算法的初步了解

聚类算法主要是用在聚类分析中的算法,而聚类分析(群集分析)是对于统计数据分析的一门技术把相似的对象通过静态分类的方法分成不同的组别或者更多的子集,这样让在同一个子集中的成员对象都有相似的一些属性,常见的包括在坐标系中更加短的空间距离等。

移动对象常访问位置点的挖掘(聚类算法):

  • 基于划分的算法的输入是包含n个对象的数据库和簇的数目 k;输出是 k 个簇,使平方误差准则最小。优点:简单,易于理解和实现;时间复杂度低。缺点:K-means 要手工输入类数目,对初始值的设置很敏感;对噪声和离群值非常敏感;只用于 numerical 类型数据,不适用于 categorical 类型数据;不能解决非凸 (non-convex) 数据;主要发现圆形或者球形簇,不能识别非球形的簇。
  • 基于密度的算法的输入是包含n个对象的数据库,输出是多个簇。优点:与 K-means 方法相比,DBSCAN 不需要事先知道要形成的簇类的数量;与 K-means 方法相比,DBSCAN 可以发现任意形状的簇类;同时,DBSCAN 能够识别出噪声点;DBSCAN 对于数据库中样本的顺序不敏感。缺点:DBSCAN 不能很好反映高尺寸数据;DBSCAN 不能很好反映数据集变化的密度;对于高维数据,点之间极为稀疏,密度很难定义。
  • 基于层次的算法的输入是包含 n 个对象的数据库,输出是一类簇。优点:距离和规则的相似度容易定义,限制少;不需要预先制定聚类数;可以发现类的层次关系;可以聚类成其它形状。缺点:计算复杂度太高;奇异值也能产生很大影响;算法很可能聚类成链状。
  • 基于网络的算法的输入是高维的输入向量,输出是聚类网络。优点:可以实现从输入空间(n 维)到输出平面(2 维)的降维映射。缺点:时间复杂度高,处理时间较长。

K-means 是划分方法中较经典的聚类算法之一。由于该算法的效率高,所以在对大规模数据进行聚类时被广泛应用。目前,许多算法均围绕着该算法进行扩展和改进。
K-means 算法以 k 为参数,把 n 个对象分成 k 个簇,使簇内具有较高的相似度,而簇间的相似度较低。K-means 算法的处理过程如下:首先,随机地选择 k 个对象,每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象,根据其与各簇中心的距离,将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数收敛。

0%