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

2dmin

聚类就是将数据对象分组成多个类或者簇，划分的原则是在同一个粗中的对象之间具有较高的相似度，而不同簇中的对象差别较大。属于一种无指导的学习方法。 好的聚类算法应该满足以下几个方面：（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都很大的时候。