放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

4.4 k-means 算法

目录

前面的三种基于链接的算法都是“合并”,k-means算法是一种“分割”算法,据说是实际应用最广泛的聚类算法。

4.4.1 初识k-means算法

主程序:

package com.hankcs;

import iweb2.ch4.clustering.partitional.KMeansAlgorithm;
import iweb2.ch4.data.SFData;
import iweb2.ch4.data.SFDataset;
import iweb2.ch4.model.DataPoint;

public class ch4_3_Partitional
{
    public static void main(String[] args) throws Exception
    {
        SFDataset ds = SFData.createDataset();

        DataPoint[] dps = ds.getData();

        KMeansAlgorithm kMeans = new KMeansAlgorithm(8, dps);

        kMeans.cluster();

        kMeans.print();
    }
}

输出:

From file: C:/iWeb2/data/ch04/clusteringSF.dat
Using attribute names: [Age, IncomeRange, Education, Skills, Social, isPaid]
Loaded 20 data points.
Clusters:
{Charlie,
Carl,
Bill}
{Aurora,
Alexandra}
{Catherine,
Bob}
{Elena,
Eric,
Frank,
Dmitry,
Constantine}
{John}
{Athena,
Babis,
Albert}
{Lukas}
{Jack,
Maria,
George}

k-means的k指的是将所有元素分割为k个聚类,算法思想的核心是根据所有元素的“重心”展开的。

4.4.2 k-means的内部原理

k-means中的means指的是重心的意思,该算法首先随机挑选k个点作为初始的重心:

    /**
     * 随机建立重心点集
     * @param k
     * @param data
     * @return
     */
    public static DataPoint[] pickInitialCentroids(int k, DataPoint[] data)
    {

        Random randGen = new Random();
        DataPoint[] centroids = new DataPoint[k];

        // Calculate random mean values for each cluster based on the data
        /**
         * TODO: 4.2 -- Selecting the means for seeding
         *
         * In large datasets, the selection of the initial centroids can be
         * important from a computational (time) complexity perspective.
         *
         * In general, how can we improve the seeding of the initial mean values?
         * For example, consider the following heuristic:
         *
         *   1. pick randomly one node
         *   2. calculate the distance between that node and O (10*k) other nodes
         *   3. sort the list of nodes according to their distance from the first node
         *   4. pick every 10th node in the sequence
         *   5. calculate the mean distance between each one of these nodes and the original node
         *
         * This algorithmic choice is as ad hoc as they come, however, it does have
         * some key principles embedded in it? What are these principles?
         * How can you generalize this algorithm?
         *
         * Discuss advantages/disadvantages of the initial seeding with your friends.
         *
         */
        Set<Integer> previouslyUsedIds = new HashSet<Integer>();
        for (int i = 0; i < k; i++)
        {
            // pick point index that we haven't used yet
            // 选出还未用到的点集
            int centroidId;
            do
            {
                centroidId = randGen.nextInt(data.length);
            }
            while (previouslyUsedIds.add(centroidId) == false);

            // Create DataPoint that will represent the cluster's centroid.
            String label = "Mean-" + i + "(" + data[centroidId].getLabel() + ")";
            double[] values = data[centroidId].getNumericAttrValues();
            String[] attrNames = data[centroidId].getAttributeNames();
            centroids[i] = new DataPoint(label,
                                         Attributes.createAttributes(attrNames, values));
        }

        return centroids;
    }

然后开始对所有点找出离它最近的重心:

    /**
     * This method calculates the closest centroid for a given data point
     * 这个方法计算离给定数据点最近的重心
     *
     * @param centroids
     * @param x         is the <CODE>DataPoint</CODE> for which we seek the closest centroid
     * @return the index (from the centroids array) of the closest centroid
     * 重心在centroids中的下标
     */
    private int findClosestCentroid(DataPoint[] centroids, DataPoint x)
    {
        double minDistance = Double.POSITIVE_INFINITY;
        int closestCentroid = -1;
        for (int i = 0, n = centroids.length; i < n; i++)
        {
            double d = distance(centroids[i], x);
            // if the d == minDistance then keep current selection
            if (d < minDistance)
            {
                minDistance = d;
                closestCentroid = i;
            }

        }
        return closestCentroid;
    }

然后将该点加入该重心所属的聚类,这会导致重心发生改变,于是重新计算重心,然后重复上一步,直到重心不再发生改变(当没有点可供加入的时候重心自然就不会变化了)。

public void cluster()
    {

        boolean centroidsChanged = true;

        while (centroidsChanged == true)
        {
            // Create a set points for each cluster
            // 创建每个聚类的数据点集合
            List<Set<DataPoint>> clusters = new ArrayList<Set<DataPoint>>(k);
            for (int i = 0; i < k; i++)
            {
                clusters.add(new HashSet<DataPoint>());
            }

            // Assign points to each set based on minimum distance from the centroids
            // 根据到重心的最短距离为每个聚类分配数据点
            for (DataPoint p : allDataPoints)
            {
                int i = findClosestCentroid(allCentroids, p);
                clusters.get(i).add(p);
            }

            for (int i = 0; i < k; i++)
            {
                // 创建聚类
                allClusters[i] = new Cluster(clusters.get(i));
            }

            // Calculate new cluster centroids, and
            // check if any of the centroids has changed
            centroidsChanged = false;
            for (int i = 0; i < allClusters.length; i++)
            {
                if (clusters.get(i).size() > 0)
                {
                    double[] newCentroidValues = findCentroid(allClusters[i]);
                    double[] oldCentroidValues = allCentroids[i].getNumericAttrValues();
                    if (!Arrays.equals(oldCentroidValues, newCentroidValues))
                    {
                        allCentroids[i] = new DataPoint(allCentroids[i].getLabel(), newCentroidValues);
                        centroidsChanged = true;
                    }
                }
                else
                {
                    // keep mean unchanged if cluster has no elements.
                }
            }
        }
    }

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » 4.4 k-means 算法

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机