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

云南民族大学数学与计算机科学院
王军
一类聚类算法的MATLAB实现
1
划分法算法
扩展
扩展
离散型数据
混合型数据
数值型数据
扩展
扩展
大型数据库
大型数据库
2
3
算法
输入:簇的数目k和包含n个对象的数据库.
输出:k个簇,使平方误差准则最小.
(1) 任意选择k个对象作为初始的簇中心
(2)
(3) 分配到最邻近的簇.
(4)

/*更新簇平均值*/.
(5) 计算/*计算准则函数E */.
(6) E 不再明显地发生变化。
4
算法优缺点
主要优点:
,简单,快速.
,该算法是相对可伸缩和高效率的.
,它的效果较好.
主要缺点:
,可能不适用于某
些应用.
(要生成的簇的数目)而且对初值敏感,对于
不同的初始值,可能会导致不同结果.

且,它对于“噪声”和孤立点数据是敏感的.
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)主成分分析基本原理
主成分分析法是一种降维的统计方法,它借助于一个正交变换,将其分量相关的原随机向量转化成其分量不相关的新随机向量,这在代数上表现为将原随机向量的协方差阵变换成对角形阵,在几何上表现为将原坐标系变换成新的正交坐标系,使之指向样本点散布最开的个正交方向,然后对多维变量