一类聚类算法MATLAB实现.ppt

云南民族大学数学与计算机科学院王军一类聚类算法的 MATLAB 实现 1 k means ?)2 k prototypes ?) 4 ( ) k medoids PAM ?) 5 CLARA )6 CLARANS ) 3 k modes ?)划分法算法扩展扩展离散型数据混合型数据数值型数据扩展扩展大型数据库大型数据库 3算法输入:簇的数目 k和包含 n个对象的数据库. 输出: k个簇,使平方误差准则最小. (1) 任意选择 k个对象作为初始的簇中心(2) (3) 分配到最邻近的簇. (4) / *更新簇平均值* /. (5) 计算/*计算准则函数 E * /. (6) E 不再明显地发生变化。 k means ? REPEAT 1 FOR j to n DO ?1 FOR i to k DO ?1 ii x C i x x C ??? 2 1 iki i x C E x x ? ?? ??? 4算法优缺点?主要优点:? ,简单,快速. ? ,该算法是相对可伸缩和高效率的. ? ,它的效果较好. ?主要缺点:? ,可能不适用于某些应用.? k(要生成的簇的数目)而且对初值敏感,对于?不同的初始值,可能会导致不同结果. ? ,它对于“噪声”和孤立点数据是敏感的. k means ? 5与算法? K-modes 算法: 1)K-means 算法只适用于数值型数据. 2)K-modes 算法实现了对离散型数据的快速聚类,保留了 K-means 算法的效率,同时将算法的应用范围扩大到离散型数据.? K-prototypes 算法: 1)算法可以对离散型与数值型属性两种混合的数据进行聚类,在中定义了一个对数值型与离散型属性都计算的相异性度量标准. 2) 度量具有混合属性的方法是,数值属性采用 K-means 得到 P1, 分类属性采用 K-modes, 那么 D=P1+a * P2,a 是权重,如果觉得分类属性重要则增加 a,否则减少 a,当 a=0 时即只有数值属性. k modes ? k prototypes ?6算法? K- modiods 算法?输入:簇的数目 k和包含 n个对象的数据库. ?输出: k个簇,使得所有对象与其最近中心点的相异度总和最小. ?(1)任意选择 k个对象作为初始的簇中心点; ?(2) ?(3)指派每个剩余的对象给离它最近的中心点所代表的簇; ?(4) ?(5)选择一个未被选择的中心点; ?(6) ?(7)选择一个未被选择过的非中心点对象; ?(8)计算用代替的总代价并记录在中; ?(9)所有的非中心点都被选择过; ?( 10 )所有的中心点都被选择过; ?( 11 )在中的所有非中心点代替所有中心点后的计算出的总代价有小?于0的存在, 找出中的用非中心点替代中心点后代价最小的一个,并用该非中心点替代对应的中心点,形成一个新的 k个中心点的集合;?( 12 )没有再发生簇的重新分配,即所有的都大于 0. REPEAT k medoids ? REPEAT REPEAT iO hO hO iOS UNTIL UNTIL IFS THEN S UNTIL S 7算法?算法: ?输入:簇的数目 k和包含 n(n很大)个对象的数据库. ?输出: k个簇,使得所有对象与其最近中心点的相异度总和最小. ?(1) ( 选样的次数) ?重复执行下列步骤(2) - (4) ). ?(2) 随机地从整个数据库中抽取一个(例如:(40+2k)) 个对象的样??本,调用从样本中找出样本的个最优的中心点. ?(3) 将这个中心点应用到整个数据库上,对于每一个非代表对象, 判断它与从样本中选出的哪个代表对象最近. ?(4) 计算上一步中得到的聚类的总代价. 若该值小于当前的最小值,用?该值替换当前的最小值,保留在这次选样中得到的个代表对象作?为到目前为止得到的最好的代表对象的集合. ?(5) 返回到步骤(1) , 开始下一个循环. ?(6) 算法结束后,输出最好的聚类结果. C L A R A CLARA 1 FOR i to v ? DO k medoids ? k N kk8 算法算法: ?输