一类聚类算法的MATLAB实现.ppt

云南民族大学数学与计算机科学院,王军,一类聚类算法的MATLAB实现,划分法算法,扩展,扩展,离散型数据,混合型数据,数值型数据,扩展,扩展,大型数据库,大型数据库,3,算法,输入：簇的数目k和包含n个对象的数据库. 输出：k个簇,使平方误差准则最小. (1) 任意选择k个对象作为初始的簇中心 (2) (3) 分配到最邻近的簇. (4) /*更新簇平均值*/. (5) 计算 /*计算准则函数E */. (6) E 不再明显地发生变化。,4,算法优缺点,主要优点: i.是解决聚类问题的一种经典算法,简单,快速. ii.对处理大数据集,该算法是相对可伸缩和高效率的. iii.当结果簇是密集的,它的效果较好. 主要缺点: i.在簇的平均值被定义的情况下才能使用,可能不适用于某 些应用. ii.必须事先给出k(要生成的簇的数目)而且对初值敏感,对于 不同的初始值,可能会导致不同结果. iii.不适合于发现非凸面形状的簇或者大小差别很大的簇.而 且,它对于“噪声”和孤立点数据是敏感的.,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时 即只有数值属性.,6,算法,K-modiods算法 输入：簇的数目k和包含n个对象的数据库. 输出：k个簇，使得所有对象与其最近中心点的相异度总和最小. （1） 任意选择k个对象作为初始的簇中心点; （2） （3） 指派每个剩余的对象给离它最近的中心点所代表的簇； （4） （5） 选择一个未被选择的中心点 ; （6） （7） 选择一个未被选择过的非中心点对象 ； （8） 计算用 代替 的总代价并记录在 中; （9） 所有的非中心点都被选择过; （10） 所有的中心点都被选择过; （11） 在 中的所有非中心点代替所有中心点后的计算出的总代价有小 于0的存在， 找出 中的用非中心点替代中心点后代价最小的 一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点 的集合; （12） 没有再发生簇的重新分配，即所有的 都大于0.,7,算法,算法： 输入：簇的数目k和包含n（n很大）个对象的数据库. 输出：k个簇,使得所有对象与其最近中心点的相异度总和最小. (1) (选样的次数) 重复执行下列步骤(2)(4) ). (2) 随机地从整个数据库中抽取一个 (例如:(40+2k)个对象的样 本,调用 从样本中找出样本的 个最优的中心点. (3)将这 个中心点应用到整个数据库上,对于每一个非代表对象 , 判断它与从样本中选出的哪个代表对象最近. (4) 计算上一步中得到的聚类的总代价. 若该值小于当前的最小值,用 该值替换当前的最小值,保留在这次选样中得到的 个代表对象作 为到目前为止得到的最好的代表对象的集合. (5) 返回到步骤(1) ,开始下一个循环. (6)算法结束后,输出最好的聚类结果.,8,算法,算法： 输入：簇的数目 和包含 （ 很大）个对象的数据库. 输出： 个簇,使得所有对象与其最近中心点的相异度总和最小. （1）输入参数 和 , 表示抽样的次数, 表示一个节点可以与任意特定邻居进行比较的数目; 令 , 用来表示已经选样的次数; 为最小 代价,初始时设为大数. （2）设置当前节点 为 中的任意一个节点. （3）令 ,（ 用来表示已经与 进行比较的邻居的个数）. （4）考虑当前节点 的一个随机的邻居 ,并计算两个节点的代价差. （5）如果 的代价较低,则 ,转到步骤（3）. （6）否则,令 .如果 ,则转到步骤（4）. （7）否则 ,当 时,当前节点为本次选样最小代价节点. 如果其代价小于 , 令 为当前节点的代价, 为当前的节点. （8）令 ,如果 ,输出 , 运算中止.否则,转 到步骤（2）.,9,主成分分析基本原理与作用,1）主成分分析基本原理 主成分分析法是一种降维的统计方法,它借助于一个正交变换,将其分量相关的原随机向量转化成其分量不相关的新随机向量,这在代数上表现为将原随机向量的协方差阵变换成对角形阵,在几何上表现为将原坐标系变换成新的正交坐标系,使之指向样本点散布最开的 个正交方向,然后对多维变量系统进行降维处理,使之能以一个较高的精度转换成低维变量系统,再通过构造适当的价值函数,进一步把低维系统转化成一维系统. 2）主成分分析主要作用 i.主成分分析能降低所研究的数据空间的维数, 即用研究 维的 空间代替 维的 空间( ),而低维的空 间代替 高维的 空间所损失的信息很少.