`
fufeng
  • 浏览: 75679 次
社区版块
存档分类
最新评论

聚类分析(三) K中心点算法(k-mediods)

阅读更多

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 中心点算法中,每次迭代后的质点都是从聚类的样本点中选取,而选取的标准就是当该样本点成为新的质点后能提高类簇的聚类质量,使得类簇更紧凑。该算法使用绝对误差标准来定义一个类簇的紧凑程度。

聚类分析(三) <wbr>K中心点算法(k-mediods)   (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.kmedoids;
import java.util.ArrayList;
public class Cluster {
    private String clusterName; // 类簇名
    private Medoid medoid; // 类簇的质点
    private ArrayList<DataPoint> dataPoints; // 类簇中各样本点

    public Cluster(String clusterName) {
        this.clusterName = clusterName;
        this.medoid = null; // will be set by calling setCentroid()
        dataPoints = new ArrayList<DataPoint>();
    }

    public void setMedoid(Medoid c) {
        medoid = c;
    }

    public Medoid getMedoid() {
        return medoid;
    }

   
    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.clusterName;
    }

    public ArrayList<DataPoint> getDataPoints() {
        return this.dataPoints;
    }
}

------------------------------------

package com.kmedoids;
import java.util.ArrayList;

public class DataPoint {
    private double dimension[]; //样本点的维度
    private String pointName; //样本点名字
    private Cluster cluster; //类簇
    private double euDt;//样本点到质点的距离

    public DataPoint(double dimension[], String pointName) {
        this.dimension = dimension;
        this.pointName = pointName;
        this.cluster = null;
    }

    public void setCluster(Cluster cluster) {
        this.cluster = 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.length;j++){
                 double temp=Math.pow((dims[j]-this.dimension[j]),2);
                 sum=sum+temp;
            }
        }

        return Math.sqrt(sum);
    }

   
    public double testEuclideanDistance(Medoid c) {
        double sum=0.0;
        double[] cDim=c.getDimensioin();

        for(int i=0;i<dimension.length;i++){
           double temp=Math.pow((dimension[i]-cDim[i]),2);
           sum=sum+temp;
        }

        return Math.sqrt(sum);
    }

    public double[] getDimensioin() {
        return this.dimension;
    }

    public Cluster getCluster() {
        return this.cluster;
    }

    public double getCurrentEuDt() {
        return this.euDt;
    }

    public String getPointName() {
        return this.pointName;
    }
}
-------------------------------

package com.kmedoids;
import java.util.ArrayList;

public class Medoid{

    private double dimension[]; // 质点的维度
    private Cluster cluster; //所属类簇
    private double etdDisSum;//Medoid到本类簇中所有的欧式距离之和


    public Medoid(double dimension[]) {
        this.dimension = dimension;
    }

    public void setCluster(Cluster c) {
        this.cluster = c;
    }

    public double[] getDimensioin() {
        return this.dimension;
    }

    public Cluster getCluster() {
        return this.cluster;
    }

    public void calcMedoid() {// 取代价最小的点
        calcEtdDisSum();
        double minEucDisSum = this.etdDisSum;
        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=tempeucDisSum;
            }
        }
    }

    // 计算该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.length;j++){
                 double temp=Math.abs(dims[j]-this.dimension[j]);
                 sum=sum+temp;
            }
        }
        etdDisSum= sum;
    }
}

--------------------------

package com.kmedoids;

import java.util.ArrayList;

public class ClusterAnalysis {

    private Cluster[] clusters;// 所有类簇
    private int miter;// 迭代次数
    private ArrayList<DataPoint> dataPoints = new ArrayList<DataPoint>();// 所有样本点
    private int dimNum;//维度

    public ClusterAnalysis(int k, int iter, ArrayList<DataPoint> dataPoints,int dimNum) {
        clusters = new Cluster[k];// 类簇种类数
        for (int i = 0; i < k; i++) {
            clusters[i] = new Cluster("Cluster:" + i);
        }
        this.miter = iter;
        this.dataPoints = dataPoints;
        this.dimNum=dimNum;
    }

    public int getIterations() {
        return miter;
    }

    public ArrayList<DataPoint>[] getClusterOutput() {
        ArrayList<DataPoint> v[] = new ArrayList[clusters.length];
        for (int i = 0; i < clusters.length; i++) {
            v[i] = clusters[i].getDataPoints();
        }
        return v;
    }

   
    public void startAnalysis(double[][] medoids) {

        setInitialMedoids(medoids);

        double[][] newMedoids=medoids;
        double[][] oldMedoids=new double[medoids.length][this.dimNum];

        while(!isEqual(oldMedoids,newMedoids)){
            for(int m = 0; m < clusters.length; 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.length; k++) {//判断样本点属于哪个类簇
                    double eucDistance=dataPoints.get(j).testEuclideanDistance(clusters[k].getMedoid());
                    if(eucDistance<minDistance){
                        minDistance=eucDistance;
                        clusterIndex=k;
                    }
                }

               //将该样本点添加到该类簇
                clusters[clusterIndex].addDataPoint(dataPoints.get(j));

            }

            for(int m = 0; m < clusters.length; m++){
                clusters[m].getMedoid().calcMedoid();//重新计算各类簇的质点
            }

            for(int i=0;i<medoids.length;i++){
                for(int j=0;j<this.dimNum;j++){
                    oldMedoids[i][j]=newMedoids[i][j];
                }
            }


            for(int n=0;n<clusters.length;n++){
                newMedoids[n]=clusters[n].getMedoid().getDimensioin();
            }

            this.miter++;
        }


    }

    private void setInitialMedoids(double[][] medoids) {
        for (int n = 0; n < clusters.length; n++) {
            Medoid medoid = new Medoid(medoids[n]);
            clusters[n].setMedoid(medoid);
            medoid.setCluster(clusters[n]);
        }
    }

   
    private boolean isEqual(double[][] oldMedoids,double[][] newMedoids){
        boolean flag=false;
        for(int i=0;i<oldMedoids.length;i++){
            for(int j=0;j<oldMedoids[i].length;j++){
                if(oldMedoids[i][j]!=newMedoids[i][j]){
                    return flag;
                }
            }
        }
        flag=true;
        return flag;
    }
}
--------------------------------------------

package com.kmedoids;

import java.util.ArrayList;
import java.util.Iterator;

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.length; 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());
            }
        }
    }

}

分享到:
评论

相关推荐

    k-mediods.rar_K mediods_K-中心点_K-中心点聚类_k-mediods聚类_k中心点

    K-中心点聚类(K-Medoids)是一种在数据挖掘和机器学习领域广泛应用的无监督学习方法,它属于划分式聚类算法的一种。与K均值算法相似,K-Medoids的目标也是将数据集分割成K个互不重叠的簇,但K-Mediods更侧重于选择...

    聚类--K-mediods1

    聚类--K-mediods1 K-medoids 算法是解决 k-means 算法中的“噪声”敏感问题的有效方法。K-means 算法会受到“噪声”点的影响,从而导致类簇质点的偏移,影响聚类结果的准确性。K-medoids 算法则通过选择合适的质点...

    k-means聚类算法k-means聚类算法k-means聚类算法k-means聚类算法.txt

    k-means聚类算法k-means聚类算法k-means聚类算法k-means聚类算法

    k - means聚类分析算法

    k-均值(k-Means)聚类分析算法是一种广泛应用的数据挖掘技术,主要用于无监督学习中的分类。它通过迭代过程将数据集中的样本点自动分配到预先设定的k个类别中,使得同一类内的样本点间差异最小,而不同类别间的样本...

    聚类算法概述, K-Means 聚类算法详解.docx

    聚类算法概述, K-Means 聚类算法详解.docx 聚类算法概述, K-Means 聚类算法详解.docx 聚类算法概述, K-Means 聚类算法详解.docx 聚类算法概述, K-Means 聚类算法详解.docx 聚类算法概述, K-Means 聚类算法详解....

    Cluster.zip_K cluster_K-mediods_mediods _聚类k_聚类算法

    K-means算法是基于中心的聚类方法,其基本思想是通过迭代找到K个簇,每个簇由距离中心最近的数据点组成。这里的中心,即为均值(mean),是簇内所有数据点的平均值。K-means算法的主要步骤如下: 1. 初始化:选择K...

    kmeans聚类算法和k-medoids聚类算法 matlab代码.rar

    K-means是最为广泛使用的聚类算法之一,其目标是将数据集分割成K个不同的簇,每个簇内的数据点彼此相近,而不同簇间的数据点相距较远。这里的“近”通常是指欧氏距离。 **工作流程:** 1. 初始化:随机选择K个数据...

    K均值聚类(K-Means聚类)-聚类算法-聚类可视化-MATLAB代码

    ‌k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法‌,其目的是将数据集划分为K个簇,每个簇通过其质心(cluster center)来表示。算法首先随机选择K个对象作为初始聚类中心,然后计算...

    k-中心点算法Matlab代码实现

    k-中心点算法(k-Medoids)是一种聚类算法,与k-均值算法相似,但使用实际数据点作为聚类中心,而非均值。它寻找的是在每个聚类中最具代表性的对象,即“medoid”,这些medoids是集群内的实际成员,而不是计算出的...

    K中心点聚类算法

    最传统的K中心点聚类算法,具有易陷入局部最优和随机选取质心的缺点

    基于python聚类算法的实现-包含:最大最小距离算法、近邻聚类算法、层次聚类算法、K-均值聚类算法、ISODATA聚类算法

    基于python聚类算法的实现--包含:最大最小距离算法、近邻聚类算法、层次聚类算法、K-均值聚类算法、ISODATA聚类算法

    初始聚类中心优化的k-means算法.pdf

    通过引入密度的概念和选择相互距离最远的高密度点作为初始中心,这种方法有效地解决了k-means算法对初始聚类中心敏感的问题。实验结果证明了该方法的有效性,对于数据挖掘领域的研究者和实践者来说具有重要的参考...

    数据挖掘聚类算法--k均值算法

    K均值算法的基本思想是通过迭代过程将数据点分配到最近的聚类中心,然后更新聚类中心为该类别所有数据点的平均值。这个过程不断重复,直到满足停止条件,如聚类中心不再变化或达到预设的最大迭代次数。 1. **算法...

    Python从零实现 K-mean 和K-中心点聚类算法的样本数据

    K-中心点算法与K-Means类似,但其质心更新规则略有不同。在K-中心点中,新的质心不是簇内所有点的均值,而是选择簇内最远的数据点作为新的质心,这一策略有时能产生更稳定的聚类结果。 Python中实现这两种算法,...

    基于聚类分析的K-means算法研究及应用.pdf

    **K-means算法**是一种迭代优化的聚类算法,其基本思想是通过迭代过程不断调整聚类中心的位置,使得每个聚类内的数据点尽可能接近其所属聚类的中心。K-means算法主要包括以下步骤: 1. **初始化**:选择K个对象作为...

    聚类分析中K-means算法综述.doc

    聚类分析中K-means算法综述

    经典聚类算法——K-Means算法实现(C#,适用于初学者)

    K-Means算法是一种广泛应用的无监督学习方法,主要用于数据的分类或聚类。它将数据集中的样本点分配到预先设定的K个类别中,使得每个样本点都尽可能接近其所在类别的中心,同时也使得类与类之间的差异最大化。在C#中...

    经典聚类的算法 聚类 k-menas

    #### 三、高效K-Means聚类算法 论文《An Efficient K-Means Clustering Algorithm》提出了一种改进的K-Means算法,该算法通过构建k-d树来提高聚类效率。 **1. k-d树简介** - **定义**: k-d树是一种多维空间的数据...

Global site tag (gtag.js) - Google Analytics