1134人阅读
机器学习（8）
K&中心点算法（&K-medoids&）
前面介绍了&k-means&算法，并列举了该算法的缺点。而&K&中心点算法（&K-medoids&）正好能解决&k-means&算法中的&“噪声”敏感这个问题。
如何解决的呢？
首先，我们得介绍下&k-means&算法为什么会对“噪声”敏感。还记得&K-means&寻找质点的过程吗？对某类簇中所有的样本点维度求平均值，即获得该类簇质点的维度。当聚类的样本点中有“噪声”（离群点）时，在计算类簇质点的过程中会受到噪声异常维度的干扰，造成所得质点和实际质点位置偏差过大，从而使类簇发生“畸变”。
Eg:&类簇&C1&中已经包含点&A(1,1)&、&B(2,2)&、&C(1,2)&、&D(2,1)&，&假设&N(100,100)&为异常点，当它纳入类簇&C1时，计算质点&Centroid((1+2+1+2+100)/5,(1+2+2+1+100)/5)=centroid(21,21),&此时可能造成了类簇&C1&质点的偏移，在下一轮迭代重新划分样本点的时候，将大量不属于类簇&C1&的样本点纳入，因此得到不准确的聚类结果。
为了解决该问题，&K&中心点算法（&K-medoids&）提出了新的质点选取方式，而不是简单像&k-means&算法采用均值计算法。在&K&中心点算法中，每次迭代后的质点都是从聚类的样本点中选取，而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量，使得类簇更紧凑。该算法使用绝对误差标准来定义一个类簇的紧凑程度。
&&&(p&是空间中的样本点，Oj&是类簇Cj&的质点)
如果某样本点成为质点后，绝对误差能小于原质点所造成的绝对误差，那么&K&中心点算法认为该样本点是可以取代原质点的，在一次迭代重计算类簇质点的时候，我们选择绝对误差最小的那个样本点成为新的质点。
Eg&：样本点&A –&E1=10
样本点&B –&E2=11
样本点&C –&E3=12
原质点&O–&E4=13&，那我们选举&A&作为类簇的新质点。
与&K-means&算法一样，&K-medoids&也是采用欧几里得距离来衡量某个样本点到底是属于哪个类簇。终止条件是，当所有的类簇的质点都不在发生变化时，即认为聚类结束。
该算法除了改善&K-means&的“噪声”敏感以后，其他缺点和&K-means&一致，并且由于采用新的质点计算规则，也使得算法的时间复杂度上升：&O&（&k(n-k)2&）
Java实现代码如下：
package com.
import java.util.ArrayL
public class Cluster {
&&& private String clusterN // 类簇名
&&& private M // 类簇的质点
&&& private ArrayList&DataPoint& dataP // 类簇中各样本点
&&& public Cluster(String clusterName) {
&&& &&& this.clusterName = clusterN
&&& &&& this.medoid = // will be set by calling setCentroid()
&&& &&& dataPoints = new ArrayList&DataPoint&();
&&& public void setMedoid(Medoid c) {
&&& &&& medoid =
&&& public Medoid getMedoid() {
&&& public void addDataPoint(DataPoint dp) { // called from CAInstance
&&& &&& dp.setCluster(this);// 标注该类簇属于某点,计算欧式距离
&&& &&& this.dataPoints.add(dp);
&&& public void removeDataPoint(DataPoint dp) {
&&& &&& this.dataPoints.remove(dp);
&&& public int getNumDataPoints() {
&&& &&& return this.dataPoints.size();
&&& public DataPoint getDataPoint(int pos) {
&&& &&& return (DataPoint) this.dataPoints.get(pos);
&&& public String getName() {
&&& &&& return this.clusterN
&&& public ArrayList&DataPoint& getDataPoints() {
&&& &&& return this.dataP
------------------------------------
package com.
import java.util.ArrayL
public class DataPoint {
&&& private double dimension[]; //样本点的维度
&&& private String pointN //样本点名字
&&& private C //类簇
&&& private double euDt;//样本点到质点的距离
&&& public DataPoint(double dimension[], String pointName) {
&&&&&&& this.dimension =
&&&&&&& this.pointName = pointN
&&&&&&& this.cluster =
&&& public void setCluster(Cluster cluster) {
&&&&&&& this.cluster =
&&& public double calEuclideanDistanceSum() {
&&& &&& double sum=0.0;
&&& &&& Cluster cluster=this.getCluster();
&&&&&&& ArrayList&DataPoint& dataPoints=cluster.getDataPoints();
&&&&&&& for(int i=0;i&dataPoints.size();i++){
&&&&&&& &&& double[] dims=dataPoints.get(i).getDimensioin();
&&&&&&& &&& for(int j=0;j&dims.j++){
&&&&&&& &&& &&& &double temp=Math.pow((dims[j]-this.dimension[j]),2);
&&&&&&& &&& &&& &sum=sum+
&&&&&&& &&& }
&&& &&& return Math.sqrt(sum);
&&& public double testEuclideanDistance(Medoid c) {
&&& &&& double sum=0.0;
&&& &&& double[] cDim=c.getDimensioin();
&&& &&& for(int i=0;i&dimension.i++){
&&&&&&&&&& double temp=Math.pow((dimension[i]-cDim[i]),2);
&&&&&&&&&& sum=sum+
&&& &&& return Math.sqrt(sum);
&&& public double[] getDimensioin() {
&&&&&&& return this.
&&& public Cluster getCluster() {
&&&&&&& return this.
&&& public double getCurrentEuDt() {
&&&&&&& return this.euDt;
&&& public String getPointName() {
&&&&&&& return this.pointN
-------------------------------
package com.
import java.util.ArrayL
public class Medoid{
&&& private double dimension[]; // 质点的维度
&&& private C //所属类簇
&&& private double etdDisS//Medoid到本类簇中所有的欧式距离之和
&&& public Medoid(double dimension[]) {
&&& &&& this.dimension =
&&& public void setCluster(Cluster c) {
&&& &&& this.cluster =
&&& public double[] getDimensioin() {
&&& &&& return this.
&&& public Cluster getCluster() {
&&& &&& return this.
&&& public void calcMedoid() {// 取代价最小的点
&&& &&& calcEtdDisSum();
&&& &&& double minEucDisSum = this.etdDisS
&&& &&& ArrayList&DataPoint& dps = this.cluster.getDataPoints();
&&& &&& for (int i = 0; i & dps.size(); i++) {
&&& &&& &&& double tempeucDisSum = dps.get(i).calEuclideanDistanceSum();
&&& &&& &&& if (tempeucDisSum & minEucDisSum) {
&&& &&& &&& &&& dimension = dps.get(i).getDimensioin();
&&& &&& &&& &&& minEucDisSum=tempeucDisS
&&& &&& &&& }
&&& // 计算该Medoid到同类簇所有样本点的欧斯距离和
&&& private void calcEtdDisSum() {
&&& &&& double sum=0.0;
&&& &&& Cluster cluster=this.getCluster();
&&&&&&& ArrayList&DataPoint& dataPoints=cluster.getDataPoints();
&&&&&&& for(int i=0;i&dataPoints.size();i++){
&&&&&&& &&& double[] dims=dataPoints.get(i).getDimensioin();
&&&&&&& &&& for(int j=0;j&dims.j++){
&&&&&&& &&& &&& &double temp=Math.abs(dims[j]-this.dimension[j]);
&&&&&&& &&& &&& &sum=sum+
&&&&&&& &&& }
&&&&&&& etdDisSum=
--------------------------
package com.
import java.util.ArrayL
public class ClusterAnalysis {
&&& private Cluster[]// 所有类簇
&&&// 迭代次数
&&& private ArrayList&DataPoint& dataPoints = new ArrayList&DataPoint&();// 所有样本点
&&& private int dimN//维度
&&& public ClusterAnalysis(int k, int iter, ArrayList&DataPoint& dataPoints,int dimNum) {
&&& &&& clusters = new Cluster[k];// 类簇种类数
&&& &&& for (int i = 0; i & i++) {
&&& &&& &&& clusters[i] = new Cluster(&Cluster:& + i);
&&& &&& this.miter =
&&& &&& this.dataPoints = dataP
&&& &&& this.dimNum=dimN
&&& public int getIterations() {
&&& public ArrayList&DataPoint&[] getClusterOutput() {
&&& &&& ArrayList&DataPoint& v[] = new ArrayList[clusters.length];
&&& &&& for (int i = 0; i & clusters. i++) {
&&& &&& &&& v[i] = clusters[i].getDataPoints();
&&& public void startAnalysis(double[][] medoids) {
&&& &&& setInitialMedoids(medoids);
&&& &&& double[][] newMedoids=
&&& &&& double[][] oldMedoids=new double[medoids.length][this.dimNum];
&&& &&& while(!isEqual(oldMedoids,newMedoids)){
&&& &&& &&& for(int m = 0; m & clusters. m++){//每次迭代开始情况各类簇的点
&&& &&& &&& &&& clusters[m].getDataPoints().clear();
&&& &&& &&& }
&&& &&& &&& for (int j = 0; j & dataPoints.size(); j++) {
&&& &&& &&& &&& int clusterIndex=0;
&&& &&& &&& &&& double minDistance=Double.MAX_VALUE;
&&& &&& &&& &&& for (int k = 0; k & clusters. k++) {//判断样本点属于哪个类簇
&&&&&&&&&&&&&&&&&&& double eucDistance=dataPoints.get(j).testEuclideanDistance(clusters[k].getMedoid());
&&&&&&&&&&&&&&&&&&& if(eucDistance&minDistance){
&&&&&&&&&&&&&&&&&&& &&& minDistance=eucD
&&&&&&&&&&&&&&&&&&& &&& clusterIndex=k;
&&&&&&&&&&&&&&&&&&& }
&&& &&& &&& &&& }
&&&&&&&&&&&&&& //将该样本点添加到该类簇
&&& &&& &&& &&& clusters[clusterIndex].addDataPoint(dataPoints.get(j));
&&& &&& &&& }
&&& &&& &&& for(int m = 0; m & clusters. m++){
&&& &&& &&& &&& clusters[m].getMedoid().calcMedoid();//重新计算各类簇的质点
&&& &&& &&& }
&&& &&& &&& for(int i=0;i&medoids.i++){
&&& &&& &&& &&& for(int j=0;j&this.dimNj++){
&&& &&& &&& &&& &&& oldMedoids[i][j]=newMedoids[i][j];
&&& &&& &&& &&& }
&&& &&& &&& }
&&& &&& &&& for(int n=0;n&clusters.n++){
&&& &&& &&& &&& newMedoids[n]=clusters[n].getMedoid().getDimensioin();
&&& &&& &&& }
&&& &&& &&& this.miter++;
&&& private void setInitialMedoids(double[][] medoids) {
&&& &&& for (int n = 0; n & clusters. n++) {
&&& &&& &&& Medoid medoid = new Medoid(medoids[n]);
&&& &&& &&& clusters[n].setMedoid(medoid);
&&& &&& &&& medoid.setCluster(clusters[n]);
&&& private boolean isEqual(double[][] oldMedoids,double[][] newMedoids){
&&& &&& boolean flag=
&&& &&& for(int i=0;i&oldMedoids.i++){
&&& &&& &&& for(int j=0;j&oldMedoids[i].j++){
&&&&&&&&&&&&&&& if(oldMedoids[i][j]!=newMedoids[i][j]){
&&&&&&&&&&&&&&& &&&
&&&&&&&&&&&&&&& }
&&& &&& &&& }
&&& &&& flag=
--------------------------------------------
package com.
import java.util.ArrayL
import java.util.I
public class TestMain {
&&& public static void main (String args[]){
&&&&&&& ArrayList&DataPoint& dataPoints = new ArrayList&DataPoint&();
&&&&&&& double[] a={2,3};
&&&&&&& double[] b={2,4};
&&&&&&& double[] c={1,4};
&&&&&&& double[] d={1,3};
&&&&&&& double[] e={2,2};
&&&&&&& double[] f={3,2};
&&&&&&& double[] g={8,7};
&&&&&&& double[] h={8,6};
&&&&&&& double[] i={7,7};
&&&&&&& double[] j={7,6};
&&&&&&& double[] k={8,5};
&&&&&&& double[] l={100,2};//孤立点
&&&&&&& double[] m={8,20};
&&&&&&& double[] n={8,19};
&&&&&&& double[] o={7,18};
&&&&&&& double[] p={7,17};
&&&&&&& double[] q={7,20};
&&&&&&& dataPoints.add(new DataPoint(a,&a&));
&&&&&&& dataPoints.add(new DataPoint(b,&b&));
&&&&&&& dataPoints.add(new DataPoint(c,&c&));
&&&&&&& dataPoints.add(new DataPoint(d,&d&));
&&&&&&& dataPoints.add(new DataPoint(e,&e&));
&&&&&&& dataPoints.add(new DataPoint(f,&f&));
&&&&&&& dataPoints.add(new DataPoint(g,&g&));
&&&&&&& dataPoints.add(new DataPoint(h,&h&));
&&&&&&& dataPoints.add(new DataPoint(i,&i&));
&&&&&&& dataPoints.add(new DataPoint(j,&j&));
&&&&&&& dataPoints.add(new DataPoint(k,&k&));
&&&&&&& dataPoints.add(new DataPoint(l,&l&));
&&&&&&& dataPoints.add(new DataPoint(m,&m&));
&&&&&&& dataPoints.add(new DataPoint(n,&n&));
&&&&&&& dataPoints.add(new DataPoint(o,&o&));
&&&&&&& dataPoints.add(new DataPoint(p,&p&));
&&&&&&& dataPoints.add(new DataPoint(q,&q&));
&&&&&&& ClusterAnalysis ca=new ClusterAnalysis(3,0,dataPoints,2);
&&&&&& double[][] cen={{8,7},{8,6},{7,7}};
&&&&&& ca.startAnalysis(cen);
&&&&& ArrayList&DataPoint&[] v = ca.getClusterOutput();
&&&&&&& for (int ii=0; ii&v. ii++){
&&&&&&&&&&& ArrayList tempV = v[ii];
&&&&&&&&&&& System.out.println(&-----------Cluster&+ii+&---------&);
&&&&&&&&&&& Iterator iter = tempV.iterator();
&&&&&&&&&&& while(iter.hasNext()){
&&&&&&&&&&&&&&& DataPoint dpTemp = (DataPoint)iter.next();
&&&&&&&&&&&&&&& System.out.println(dpTemp.getPointName());
&&&&&&&&&&& }
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：21049次
排名：千里之外
转载：19篇
(2)(3)(5)(11)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'苹果/安卓/wp
积分 27, 距离下一级还需 18 积分
道具: 彩虹炫, 涂鸦板, 雷达卡, 热点灯, 金钱卡下一级可获得
道具: 显身卡
购买后可立即获得
权限: 隐身
道具: 金钱卡, 彩虹炫, 雷达卡, 热点灯, 涂鸦板
用spss做K均值聚类分析，如果想设定初始聚类中心，该聚类中心应该是什么格式的
载入中......
做好把数据格式给列出来
SPSS中K-Means 聚类法“读取初始聚类中心”下面有一个是“保存聚类中心”的功能框...
您先用默认中心保存一个聚类中心数据文件.然后....您就可以打开这个“保存”数据文件....也就知道数据格式了...
“CLUSTER_”多了这个东西...
bakoll 发表于
SPSS中K-Means 聚类法“读取初始聚类中心”下面有一个是“保存聚类中心”的功能框...
您先用默认中心保存一 ...没看到您说的“保存聚类中心”的功能框呀
他指的是最下方的写入最终聚类中心
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
&nbsp&nbsp|
如有投资本站或合作意向，请联系（010-）；
邮箱：service@pinggu.org
投诉或不良信息处理：（010-）
论坛法律顾问：王进律师K-中心点和K-均值聚类算法研究_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
K-中心点和K-均值聚类算法研究
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩52页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢扫二维码下载作业帮
2亿+学生的选择
下载作业帮安装包
扫二维码下载作业帮
2亿+学生的选择
关于K-Means聚类算法的,论文里都说：K-Means算法对数据输入顺序敏感.怎么理解呢?我的理解是：K-Means算法选取前K个点为中心,数据输入顺序不同,选取的K个中心点就不同,因此聚类结果不同.这个的根源还是K-Means算法对初始聚类中心的敏感性而且,我做过实验,打乱了iris中数据的顺序,得到3个不同的数据集.但是我采用相同的中心,得到的结果是一样的.大家是怎么理解：K-Means算法对数据输入顺序敏感的,
一笑泪光寒085
扫二维码下载作业帮
2亿+学生的选择
当然是敏感的,跟程序中如何处理数据有很大的关系.比如两个中心点（-1,0）（1,0）,这时读入数据（0,0）,那么程序计算与所有中心点的距离,因为距离相同,程序会给其中一个,至于给哪个,都是由程序决定,一般按数据存储的先后顺序来给.而且结果不同不能代表聚类结果差,而是说明结果的多样化,本身K的选取就是没有一个约定的方法,所以结果有差别也是理所当然的.关键是你要如何体现你的算法的优越性.就是要跟别的算法作比较,比如从算法的空间、时间复杂度,算法的运行处理速度等等因素来做比较.
为您推荐：
其他类似问题
扫描下载二维码R语言数据挖掘实践——K-中心点聚类
R语言数据挖掘实践——K-中心点聚类
K-中心点聚类与K-均值聚类类似，其主要区别在于：K-均值聚类选择簇中心表示聚类簇，而K-中心点聚类选择靠近簇中心的对象表示聚类簇。基于中心点的划分（PAM）是K-中心点聚类的景点算法。PAM算法不能有效扩展到较大规模的数据集上，而CLARA算法是对PAM算法的改进，CLARA算法先从数据集中抽取多个样本集，然后在每一个样本集上应用PAM算法，并返回最好地聚类。在处理较大的数据集时，CLARA算法的性能优于PAM算法。cluster包中的pam()函数和clara()函数分别用于在R语言中实现PAM算法和CLARA算法。对于这两个算法，用户都需要指定一个k，即聚类簇的个数。fpc包中提供了更强大的pamk()函数，该函数不要求用户输入k的值，而是调用pam()函数或clara()函数根据最优平均阴影宽度估计的聚类簇个数来划分数据。下面使用代码演示如何利用pam()函数和pamk()函数找到聚类。& library(fpc)& iris2 &-& iris2$Species &- NULL& pamk.result &- pamk(iris2)& pamk.result$nc[1] 2& table(pamk.result$pamobject$clustering, iris$Species)setosa versicolor virginica1 50 1 02 0 49 50& layout(matrix(c(1,2),1,2))& plot(pamk.result$pamobject)& layout(matrix(1))pamk()函数生成了两个簇：一个是”setosa“，另一个是”versicolor“和”virginica“的混合。在生成的图形中，左边的图像为两个簇的2维聚类图像（”clusplot“），两个簇中间的直线表示距离；右边的图像显示了这两个簇的阴影。当Si的值较小时（接近0）表明观测点位于这两个簇重叠的部分。如果观测点的Si值为负数，则说明观测点被划分到错误的簇中。上面右图中的Si均值分别0.81和0.62，所以这表明这两个簇划分结果很好。现在我们使用pam()函数，并设置k=3。& library(cluster)& pam.result &- pam(iris2,3)& table(pam.result$clustering,iris$Species)1 50 0 02 0 48 143 0 2 36& plot(pam.result)使用pam()函数生成的结果含有3个簇：第一个簇为”setosa“，该簇与其他两个簇能够很好地划分开来；第二个簇主要由”versicolor“构成，其中也包含有几个”virginica “类的实例；第三个簇主要是”virginica“类的实例，其中也包含2个”versicolor“的实例。对比上面两个聚类的结果，很难说函数pamk()和pam()哪一个能获得更好的聚类结果，结果质量的好坏依赖于目标问题以及领域知识和经验。在这里例子中，pam()函数得到的聚类结果似乎更好，这是因为它识别出3个不同的簇，分别对应于3个不同的种类。因此，使用启发方式来识别簇个数的pamk()函数并不意味着总是能得到更好地聚类结果。还需要注意的是，由于事先已经知道Species属性确实只包含了3个种类，因此在使用pam()函数时将k设置为3也具有一定的投机性。
本文仅代表作者观点，不代表百度立场。系作者授权百家号发表，未经许可不得转载。
百家号 最近更新：
简介: 热衷于搞笑短片、段子
作者最新文章}