日新计划第四天

聚类概述:

什么是聚类？

• 是把数据对象集合按照相似性划分成多个子集的过程。
• 每个子集是一个簇(cluster)，分类的最终效果：使得簇中的对象彼此相似，但与其他簇中的对象相异。
• 聚类是无监督学习，因为给的数据没有类标号信息。

分类和聚类的区别

分类

• 有监督学习；
• 通过带标签的样本进行学习，生成分类模型(分类器)。 聚类
• 无监督学习；
• 通过观察学习，根据样本间的相似性将数据分割成多个簇。

基本聚类方法

划分方法

划分方法：将有n个对象的数据集D划分成k个簇，并且k≤n，满足如下的要求：

• 每个簇至少包含一个对象
• 每个对象属于且仅属于一个簇 基本思想：
• 首先创建一个初始k划分( k为要构造的划分数，即簇的个数)；
• 然后不断迭代地计算各个簇的聚类中心，并依据新的聚类中心调整聚类情况，直至收敛。 目标：
• 同一个簇中的对象之间尽可能“接近”或相关；
• 不同簇中的对象之间尽可能“远离”或不同。 基于划分的方法实质上是一种启发式方法： k-均值(k-means)及其改进算法
• 每个簇用该簇中对象的均值来表示
• 基于质心的技术 k-中心点(k-medoids)算法
• 每个簇用接近簇中心的一个对象来表示
• 基于代表对象的技术 适用性方面：
• 适合中小规模数据库中的球状聚类；
• 对于大规模数据库和处理任意形状的聚类，这些算法需要进一步扩展。

K-Means算法

规定k=2,即划分为两个簇然后先随机选取两个红色的点作为聚类中心,然后通过计算其他点与中心点的距离来划分簇,当此次划分完成后通过计算均值来重新定义聚类中心,然后重复上述过程来重新划分簇.直到最后发现此次形成的簇与上一次相同，因此聚类过程到此结束。

Kmeans算法为启发式算法，遵循的寻优原则：\ 每次聚类保证局部最优，随后调整聚类，利用局部最优聚类的上限来不断逼近全局最优

K-Means算法优缺点

优点：

• 聚类时间快
• 当结果簇是密集的，而簇与簇之间区别明显时，效果较好
• 相对可扩展和有效，能对大数据集进行高效划分 缺点：
• 用户必须事先指定聚类簇的个数(即k值需指定)
• 常常终止于局部最优
• 只适用于数值属性聚类(计算均值有意义)
• 对噪声和异常数据也很敏感
• 不同的初始值，结果可能不同
• 不适合发现非凸面形状的簇 凸面形状的簇--指圆形矩形等形状,是指当选择形状内任意两点，这两点的连线上所有点，也都在形状内。

K-Means算法还有一些改进算法：

• K-Mode算法
• K-Means++算法

K-Mode算法 —— 解决数据敏感的问题

在K-Means算法中只能适用于连续的数值属性的聚类，为解决离散属性的问题，K-Mode算法对其进行了改进：

• 用众数代替均值；
• 使用新的相异性度量方法。

K-Means++算法 —— 解决初始点选择问题

K-Means算法中初始值选择的不同也会引起不同的聚类结果，因此K-Means++算法对其做了改进。

K-Means++算法基本原理：

• 从输入的数据点集合中随机选择一个点作为第一个聚类中心；
• 对于数据集中的每一个点X，计算其与聚类中心的距离D(X)；
• 选择一个D(X)最大的点作为新的聚类中心；
• 重复2和3步直到K个聚类中心被选出；
• 利用K个初始聚类中心运行K-Means算法。 *即尽可能选择距离远的点来作为初始种子节点

K-Mediods(K中心点算法)

K-Mediods算法可以解决K-Means算法对离群点敏感的问题。 K-中心点算法(解决对离群点敏感的问题)：

• 选用簇中位置最中心的实际对象即中心点作为参照点；
• 基于最小化所有对象与其参照点之间的相异度之和的原则来划分(使用绝对误差标准)

K-中心点算法的基本思想：

• 首先为每个簇随意选择一个代表对象，剩余的对象根据其与代表对象的距离分配给最近的一个簇。
• 然后迭代地用非代表对象来替代代表对象，以改进聚类的质量(找更好的代表对象)。
• 聚类结果的质量用一个代价函数来估算，该函数评估了对象与其参照对象之间的平均相异度。

PAM算法

PAM算法(Partitioning Around Medoids)是最早提出的K-中心点算法之一。\ PAM算法的基本思想：

• 随机选择 k 个对象作为初始的代表对象；
• 指派每个剩余的对象给离它最近的代表对象所代表的簇；
• 随机地选择一个非代表对象Orandom；
• 计算用Orandom代替其中的代表对象Oj的总代价S ；
• 如果S<0，则用Orandom替换Oj形成新的k个代表对象的集合.

总而言之就是一个不断更新中心点使得总距离不断减小的过程.

PAM算法的优缺点

优点

• 当存在噪音和孤立点时，PAM 比K-Means算法更健壮。 缺点
• PAM 对于较小的数据集非常有效，但不能很好地扩展到大型数据集，原因是计算复杂度较高。
• 每次中心点交换的时候，就要计算数据中每个点的代价