数据挖掘--聚类方法(1)

聚类就是将数据对象分组成多个类或者簇，划分的原则是在同一个粗中的对象之间具有较高的相似度，而不同簇中的对象差别较大。属于一种无指导的学习方法。

好的聚类算法应该满足以下几个方面：

（1） 可伸缩型：无论对小数据量还是大数据量应该都是有效的。

（2） 具有处理不同类型属性的能力。

（3） 能够发现任意形状的聚类。

（4） 输入参数对领域知识的弱依赖性

（5） 对于输入记录顺序不敏感

（6） 能够处理很多维度的数据，而不止是对3维左右的数据有效

（7） 处理噪声数据的能力

（8） 基于约束的距离：既能找到满足特定的约束，又具有良好聚类特性的数据分组

（9） 挖掘出来的信息是可理解的和可用的。

聚类分析主要在以下几个方面应用：

（1） 可以作为其他算法的预处理步骤

（2） 可以作为一个独立的工具来获得数据的分布情况

（3） 可以完成孤立点挖掘，用来预示欺诈行为的存在。

基本概念

聚类分析的输入可以用一组有序对（X,s）或(X,d)表示，这里X表示一组样本，s和d分别是度量样本间相似度或相异度(距离)的标准。聚类系统的输出是一个分区C={C1,C2,…,Ck}，其中Ci是X的子集，成为类。类的特征可以用如下几种方式表示：

2 通过类的中心或类的边界点表示一个类。

2 使用聚类树中的结点图形化地表示一个类。

2 使用样本属性的逻辑表达式表示类。

聚类分析的方法：

聚类分析有很多大量的、经典的算法，比如k-平均、k-中心点、PAM、CLARANS, BIRTH,CURE,OPTICS,DBSCAN,STING,CLIQUE,WAVECLUSTER等。

度量标准：

一个聚类分析过程的质量取决于对度量标准的选择，因此必须仔细选择度量标准。（1）距离函数

2 明可夫斯基距离：

x, y 是相应的特征，n是特征的维数。则明可夫斯基距离d(x,y)表示如下

，r=2为欧式距离。

2 二次型距离：

2 余弦距离

2 二元特征样本的距离

假定x和y分别是n维特征，xi和yi分别表示每维特征，且xi和yi的取值为二元类型数值{0，1}。则x和y的距离定义的常规方法是先求如下几个参数，然后采用SMC、Jaccard系数或Rao系数。

a是样本x和y中满足 xi=yi=1的二元类型属性的数量

b是样本x和y中满足xi=1,yi=0的二元类型属性的数量

c是样本x和y中满足xi=0,yi=1的二元类型属性的数量

d是样本x和y中满足xi=yi=0的二元类型属性的数量

则简单匹配系数（Simple Match Coefficient, SMC）的公式如下：

Jaccard系数：

Rao系数：

（2）类间距离

设有两个类Ca和Cb，分别有m和n个元素，他们的中心分别为ra和rb。设元素x属于Ca，y属于Cb，这两个元素之间的距离记为d(x,y),类间距记为D(Ca,Cb)。

2 最短距离法：类中最靠近的两个元素的距离为类间距离：

2 最长距离法：类中最远的两个元素的距离为类间距离

2 重心法：类中两个中心点间的距离为类间距离。因此就需要定义类中心，类中心的定义：

2 类平均法：两个类中任意两个元素之间的距离相加后取平均值。

2 离差平方和：用到了类直径，类直径反应了类中各元素的差异，可以定义为各元素到类中心的欧式距离之和，这样就得到了Ca,Cb,Ca+b的直径分别为ra,rb,ra+b,那么类间距为ra+b – ra - rb。

划分聚类方法层划分聚类算法的基本思想

给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇，k<=n。 这k个划分满足下列条件：

2 每个簇至少包含一个对象

2 每个对象属于且仅属于一个簇

对于给定的k，算法首先给出一个初始的划分方法，以后通过迭代来改变划分，是得每一次改进之后的划分方案都较前一次更好。所谓更好的标准时是：同一个簇中的对象越接近越好，不同簇之间的对象越远越好。目标是最小化所有对象与其参考点之间的相异度之和。这里的远近或者相异度/相似度实际上是聚类的评价函数。

评价函数：

评价函数应该考虑里两个方面：每个簇应该是紧凑的，每个簇间的距离应该尽可能地远。这就需要观察两个值：类内差异和类间差异。类内差异可以采用多种距离函数来定义，最简单的就是计算类内的每一个点到类中心的距离的平方和，一般用w(C)表示。类间差异定义为类中心之间的距离，一般用b(C)表示。

K-means算法

首先随机地选择k个对象，每个对象处划地代表了一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离，将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。准则如下：

准则函数其实就是所有对象的平法误差的总和，这个准则试图试生成的结果簇尽可能地紧凑和独立。

算法描述：

输入：簇的数目k和包含n个对象的数据库

输出：k个簇，是平方误差准则最小

（1） 任意选择k个对象作为初始的簇中心

（2） Repeat

（3） 根据簇中对象的平均值，将每个对象赋给最类似的簇

（4） 更新簇的平均值，即计算每个对象簇中对象的平均值

（5） 计算准则函数

（6） Until E不再明显地发生变化

算法性能：

优点：

（1） 简单、快速

（2） 对大数据集，是可伸缩和高效率的。

（3） 算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显的时候，效果较好。

缺点：

（1） 不适合分类属性的数据

（2） 必须给定k，对初始值k比较敏感

（3） 不适合发现非凸面形状的簇，对噪声和孤立点数据是敏感的。

改进措施：

（1）k-模算法，可以对离散属性计算

（2）不采用簇中的平均值作为参考点，而选用簇中位置最靠近中心的对象。这样可以避免孤立点的影响。

PAM算法（也称k-中心点算法）

PAM算法需用簇中位置最靠近中心的对象作为代表对象，然后反复地用非代表对象来代替代表对象，试图找出更好的中心点，在反复迭代的过程中，所有可能的“对象对”被分析，每个对中的一个对象是中心点，另一个是非代表对象。一个对象代表可以被最大平方-误差值减少的对象代替。

一个非代表对象Oh是否是当前一个代表对象Oi的一个好的替代，对于每个非中心点对象Oj，有以下四种情况需要考虑：

（1） Oj当前隶属于Oi，如果Oi被Oh替换，且Oj离另一个Om最近，i！=m，那么Oj被分配给Om，则替换代价为Cjih=d(j,m)-d(j,i)。

（2） Oj当前隶属于Oi，如果Oi被Oh替换，且Oj离Oh最近，那么Oj被分配给Oh，则替换代价为Cjih=d(j,h)-d(j,i)。

（3） Oj当前隶属于Om，m！=i，如果Oi被Oh替换，且Oj仍然离Om最近，那么Oj被分配给Om，则替换代价为Cjih=0。

（4） Oj当前隶属于Om，m！=i，如果Oi被Oh替换，且Oj离Oh最近，那么Oj被分配给Oh，则替换代价为Cjih=d(j,h)-d(j,m)。

然后计算

如果 为负，则可以替换。

算法描述：

输入：簇的数目k和包含n个对象的数据库

输出：k个簇，使得所有对象与其最近中心点的相异度总和最小

（1） 任意选择k个对象作为初始的簇中心点

（2） Repeat

（3） 指派每个剩余对象给离他最近的中心点所表示的簇

（4） Repeat

（5） 选择一个未被选择的中心点Oi

（6） Repeat

（7） 选择一个未被选择过的非中心点对象Oh

（8） 计算用Oh代替Oi的总代价并记录在S中

（9） Until 所有非中心点都被选择过

（10） Until 所有的中心点都被选择过

（11） If 在S中的所有非中心点代替所有中心点后的计算出总代价有小于0的存在，then找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合；

（12） Until 没有再发生簇的重新分配，即所有的S都大于0.

算法性能：

(1) 消除了k-平均算法对于孤立点的敏感性。

(2) K-中心点方法比k-平均算法的代价要高

(3) 必须指定k

(4) PAM对小的数据集非常有效，对大数据集效率不高。特别是n和k都很大的时候。