资源描述
云南民族大学数学与计算机科学院,王军,一类聚类算法的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.主成分分析能降低所研究的数据空间的维数,即用研究维的空间代替维的空间(),而低维的空间代替高维的空间所损失的信息很少.ii.有时可通过因子负荷的结论,弄清变量间的某些关系.iii.多维数据的一种图形表示方法.,10,基于划分聚类算法模块化流程图,11,模块化的MATLAB实现,12,THANKYOUFORATTENTION!,
展开阅读全文