新普金娱乐第十一章 K-Means(K均值)算法模型实现(下)机器上十非常算法的K-Means

KMeans的应用

聚类是数码挖掘领域被最主要之技术有,用于发现数中未知之归类。聚类分析已经来矣老大丰富的研究历史,其重大都越来越受人们的一定。聚类算法是机械上、数据挖掘与模式识别等研究方向的要研究内容有,在甄别数据对象的内在关联方面,具有极其重要的意向。聚类主要运用叫模式识别中之语音识别、字符识别等,机器上着之聚类算法应用被图像分割,图像处理着,主要用来数据压缩、信息搜索。聚类的任何一个要使用是数量挖掘、时空数据库应用、序列以及特别数据解析等。此外,聚类还运用被统计是,同时,在生物学、地质学、地理学与市场营销、银行客户等划分等方面为保有重大之意。

  K-means算法是最好经典的依据划分的聚类方法,是十万分经典数据挖掘算法有。K-means算法的中坚考虑是:以空间中k个点为核心进行聚类,对极度接近她们的目标分类。通过迭代底办法,逐次更新各聚类中心的价值,直至获得最好好之聚类结果。

优点

1.算法便捷、简单;
2.当聚类是密集的,且看似以及类似中区别明显时,效果比较好。
3.对天意据集有较高之效率又是可伸缩性的;
4.日子复杂度近于线性,而且称挖掘大规模数据集。
K-Means聚类算法的时日复杂度是O(nkt)
,其中n代表数据汇总对象的数目,t代表着算法迭代的次数,k代表着簇的数码。

新普金娱乐 1

缺点

1.以 K-means 算法中 K 是先行给定的,这个 K
值的选定是颇难以估计的。有的算法是经过类似的电动合并和分裂,得到比较合理的门类数目
K,例如 ISODATA 算法。

2.每当 K-means
算法中,首先需要基于初步聚类中心来确定一个方始分,然后针对起来分进行优化。这个起聚类中心的精选针对性聚类结果有较充分的熏陶,一旦初始值选择的糟糕,可能无法获得管用之聚类结果,这吗变为
K-means算法的一个首要问题。对于拖欠问题之缓解,许多算法采用遗传算法,例如文献
中使用遗传算法(GA)进行初始化,以中间聚类准则作为评价指标。

3.于 K-means
算法框架可以看到,该算法需要不停地拓展样本分类调整,不断地计算调整后底初的聚类中心,因此当数据量非常非常时,算法的日开是深充分的。所以需要针对算法的辰复杂度进行辨析、改进,提高算法应用范围。

kmeans.jpg

运案例

k-means算法一个诙谐的用示范:中国男足近几年到底在亚洲处在几淌水平?

  今年中国男足可算是杯具到家了,几乎到了过街老鼠人人喊打的地步。对于目前中国男足在亚洲的地位,各方也是各执一词,有人说中国男足亚洲二流,有人说三流,还有人说根本不入流,更有人说其实不比日韩差多少,是亚洲一流。既然争论不能解决问题,我们就让数据告诉我们结果吧。

  下图是我采集的亚洲15只球队在2005年-2010年间大型杯赛的战绩(由于澳大利亚是后来加入亚足联的,所以这里没有收录)。

新普金娱乐 2

里头包个别赖世界杯和同一赖亚洲杯。我提前对数据做了如下预处理:对于世界杯,进入决赛圈则获该最后排名,没有进去决赛圈的,打入预选赛十胜赛赋予40,预选赛小组不出线的给50。对于亚洲海,前四叫做取得该行,八大赋予5,十六大赋予9,预选赛没起的施17。这样做是以使所有数据化标量,便于后续聚类。

  下面先对数据进行[0,1]规格化,下面是规格化后的数据:

新普金娱乐 3

  接着用k-means算法进行聚类。设k=3,即将这15支球队分成三个集团。

  现抽取日本、巴林和泰国的值作为三个簇的种子,即初始化三个簇的中心为A:{0.3, 0, 0.19},B:{0.7, 0.76, 0.5}和C:{1, 1, 0.5}。下面,计算所有球队分别对三个中心点的相异度,这里以欧氏距离度量。下面是我用程序求取的结果:

新普金娱乐 4

自完成右依次表示各开球队到手上中心点的欧氏距离,将诸开球队分至近来底簇,可针对各个开发球队举行如下聚类:

  中国C,日本A,韩国A,伊朗A,沙特A,伊拉克C,卡塔尔C,阿联酋C,乌兹别克斯坦B,泰国C,越南C,阿曼C,巴林B,朝鲜B,印尼C。

  第一次聚类结果:

  A:日本,韩国,伊朗,沙特;

  B:乌兹别克斯坦,巴林,朝鲜;

  C:中国,伊拉克,卡塔尔,阿联酋,泰国,越南,阿曼,印尼。

  下面根据第一次聚类结果,调整各个簇的中心点。

  A簇的新中心点为:{(0.3+0+0.24+0.3)/4=0.21, (0+0.15+0.76+0.76)/4=0.4175, (0.19+0.13+0.25+0.06)/4=0.1575} = {0.21, 0.4175, 0.1575}

  用同样的方法计算得到B和C簇的新中心点分别为{0.7, 0.7333, 0.4167},{1, 0.94, 0.40625}。

  用调整后的中心点再次进行聚类,得到:

新普金娱乐 5

其次不良迭代后底结果也:

  中国C,日本A,韩国A,伊朗A,沙特A,伊拉克C,卡塔尔C,阿联酋C,乌兹别克斯坦B,泰国C,越南C,阿曼C,巴林B,朝鲜B,印尼C。

  结果无变化,说明结果已收敛,于是给出最终聚类结果:

  亚洲一流:日本,韩国,伊朗,沙特

  亚洲二流:乌兹别克斯坦,巴林,朝鲜

  亚洲三流:中国,伊拉克,卡塔尔,阿联酋,泰国,越南,阿曼,印尼

  看来数据告诉我们,说国足近几年处在亚洲三流水平真的是没有冤枉他们,至少从国际杯赛战绩是这样的。

  其实上面的分析数据不仅告诉了我们聚类信息,还提供了一些其它有趣的信息,例如从中可以定量分析出各个球队之间的差距,例如,在亚洲一流队伍中,日本与沙特水平最接近,而伊朗则相距他们较远,这也和近几年伊朗没落的实际相符。另外,乌兹别克斯坦和巴林虽然没有打进近两届世界杯,不过凭借预算赛和亚洲杯上的出色表现占据B组一席之地,而朝鲜由于打入了2010世界杯决赛圈而有幸进入B组,可是同样奇迹般夺得2007年亚洲杯的伊拉克却被分在三流,看来亚洲杯冠军的分量还不如打进世界杯决赛圈重啊。其它有趣的信息,有兴趣的朋友可以进一步挖掘。

点的使用案例获得自参考文献3,资料有点遥远,只供就学算法运用。Kmeans算法目前尽管形容这么多,之后有利用及新的好的精益求精要么想法会继续补的。

  k-means 算法接受参数 k ;然后以预输入的n个数据对象划分为
k独聚类以便使所获取的聚类满足:同一聚类中的靶子相似度较高;而不同聚类中之目标相似度较小。聚类相似度是使每聚类中目标的均值所得到一个“中心目标”(引力中心)来进行测算的。
  假设要把样本集分为c个项目,算法描述如下:

参考文献

1、《机器上实战》(书)
2、《k-means聚类算法的钻》(硕士论文)
3、算法杂货铺——KMeans均值聚类(博客)
4、 K均值聚类(kmeans)算法和下(博客)
5、其他各种网站(略)

(1)适当选择c个类似的启中心;
(2)在第k涂鸦迭代中,对轻易一个样本,求其交c个主导的离开,将欠样本归到去太短的主导所于的好像;
(3)利用均值等措施创新该类的骨干值;
(4)对于具有的c个聚类中心,如果应用(2)(3)的迭代法更新后,值保持不移,则迭代结束,否则继续迭代。

  该算法的绝酷优势在简洁与高速。算法的关键在于初始中心的抉择和距离公式(即相似性度量方式:可以是欧式距离,可以是余弦相似度等,可参照https://www.jianshu.com/p/a0dfcdf07f18)。
k-Means的简短实现如下:

import java.util.LinkedList;
import java.util.List;

/**
 * K-Means Clustering:
 * step: 1. random choose k samples as center of each Clustering.
 * step: 2. calculate distances of samples to each center, 
 *          and cluster them into coresponding centers.
 * step: 3.recalculate all centers by obtaining the centroid of each cluster.
 *          if all centers never change or several times have been iterated, 
 *          stop the iteration and return results. Else continue step 2.
 *          
 * @author QuanMaster 2018年1月24日 下午8:29:08
 *
 */
public class Algorithm_kMeans { 
    //最大迭代次数。
    public static final int MAX_ITER_TIMES = 10;

    public Clusters kMeans(int k, List<DataNode> samples){
        Clusters clusters = null;
        if(samples.size() < k){
            System.out.println("lack of samples!");
            return clusters;
        }

        double[][] centers = new double[k][];
        //初始化k个聚类的中心
        for(int i = 0; i < k; i++){
            centers[i] = samples.get(i).getFeatures();
        }

        for(int i = 0; i < MAX_ITER_TIMES; i++){
            clusters = clusterWithCenters(centers, samples);
            System.out.println("\n\nAfter " + (i+1) +"-th iterator:");
            System.out.println(clusters);
            if(!updateCenters(centers, clusters)) break;
        }
        return clusters;
    }

    /**
     * cluster according to current centers.
     * 
     * @param centers
     * @param samples
     * @return
     */
    private Clusters clusterWithCenters(double[][] centers, List<DataNode> samples){
        Clusters cluster = new Clusters(centers.length);
        samples.forEach(s->{
            double[] features = s.getFeatures();
            double min = Double.MAX_VALUE;
            int index = 0;
            for(int i =0; i < centers.length; i++ ){
                index = min > MLUtils.euclideanDistance(centers[i], features) ? i : index;
            }
            cluster.insertDataNodeIntoCluster(index, s);
        });
        return cluster;
    }

    /**
     * update centers during each iterator.
     * 
     * @param centers
     * @param clusters
     * @return
     */
    private boolean updateCenters(double[][] centers, Clusters clusters){
        boolean updated = false;
        for(int i = 0; i < centers.length; i++){
            if(!MLUtils.isSameArray(centers[i],reObtainCentroidForCluster(clusters.clusters[i])))
                updated = true;
        }
        return updated;
    }


    /**
     * 计算每个簇上的样本的平均值作为当前簇的几何中心。
     * @param cluster
     * @return
     */
    private double[] reObtainCentroidForCluster(List<DataNode> cluster){
        int dimension = cluster.get(0).getFeatures().length;
        int clusterSize = cluster.size();

        double[] newCentroid = new double[dimension];
        cluster.forEach(node->{
            double[] features = node.getFeatures();
            for(int i=0; i < dimension; i++){
                newCentroid[i] += features[i];
            }
        });

        for(int i=0; i < dimension; i++){
            newCentroid[i] /= clusterSize;
        }
        return newCentroid;
    }


    /**
     * Object defined for Clustring results.
     * @author zhaoshiquan 2018年1月24日 下午8:03:48
     *
     */
    class Clusters{
        private int k = 1;
        private List<DataNode>[] clusters;

        Clusters(int k){
            this.k = k;
            this.clusters = new LinkedList[k];
        }

        public int getK() {
            return k;
        }

        public void setK(int k) {
            this.k = k;
        }

        public List<DataNode>[] getClusters() {
            return clusters;
        }

        public void setClusters(List<DataNode>[] clusters) {
            this.clusters = clusters;
        }

        @Override
        public String toString() {
            return "Clusters [k=" + k + ", clusters=" + clusters + "]";
        }

        public void insertDataNodeIntoCluster(int k, DataNode node){
            this.clusters[k].add(node);
        }

    }
}

算法优点

K-Means聚类算法的助益主要集中在:

1.算法飞速、简单;
2.对准命运据集有较高的效率又是可伸缩性的;
3.工夫复杂度近于线性,而且适合挖掘大规模数据集。K-Means聚类算法的工夫复杂度是O(nkt)
,其中n代表数据集中对象的数,t代表着算法迭代的次数,k代表着簇的数额。[1]

算法缺点

k-means 算法缺点
  ① 在 K-means 算法中 K 是先行给定的,这个 K
值的选定是甚难以估计的。很多时光,事先并不知道给定的数据集应该分为小只类别才最适合。这为是
K-means
算法的一个不足。有的算法是由此类似的全自动合并和分裂,得到比较合理的类数目
K,例如 ISODATA 算法。关于 K-means 算法中聚类数目K
值的确定于文献中,是依据方差分析理论,应用混合
F统计量来规定最佳分类数,并使用了模糊划分熵来证实最佳分类数的没错。在文献中,使用了一样种组成全协方差矩阵的
RPCL
算法,并逐渐删除那些只含少量训多少的接近。而文献中采取的凡相同种叫做次胜者受罚的竞争上规则,来自动决定类的合适数目。它的思辨是:对每个输入而言,不仅竞争获胜单元的权值被修正为适应输入值,而且本着不良高单元采用惩罚的法门而之远离输入值。
  ② 在 K-means
算法中,首先用依据初步聚类中心来规定一个起分,然后对始发分进行优化。这个开聚类中心的选料针对性聚类结果来于充分的震慑,一旦初始值选择的坏,可能无法赢得有效的聚类结果,这为变为
K-means算法的一个生死攸关问题。对于该问题的解决,许多算法采用遗传算法(GA),例如文献
中使遗传算法(GA)进行初始化,以中聚类准则作为评指标。
  ③ 从 K-means
算法框架可以看到,该算法需要不停地拓展样本分类调整,不断地计算调整后的初的聚类中心,因此当数据量非常非常时,算法的光阴开是格外特别之。所以待针对算法的年华复杂度进行分析、改进,提高算法应用范围。在文献中自该算法的日复杂度进行分析考虑,通过自然之相似性准则来去丢聚类中心的侯选集。而当文献中,使用的
K-means
算法是指向样本数量进行聚类,无论是初始点的选还是平涂鸦迭代完成时对数码的调整,都是起在自由选的范本数量的基本功之上,这样可增强算法的消解速度。

参考:https://baike.baidu.com/item/K-means/4934806

相关文章