大數(shù)據(jù)分析之聚類算法

1. 什么是聚類算法

所謂聚類，就是比如給定一些元素或者對(duì)象，分散存儲(chǔ)在數(shù)據(jù)庫中，然后根據(jù)我們感興趣的對(duì)象屬性，對(duì)其進(jìn)行聚集，同類的對(duì)象之間相似度高，不同類之間差異較大。最大特點(diǎn)就是事先不確定類別。
這其中最經(jīng)典的算法就是KMeans算法，這是最常用的聚類算法，主要思想是:在給定K值和K個(gè)初始類簇中心點(diǎn)的情況下，把每個(gè)點(diǎn)(亦即數(shù)據(jù)記錄)分到離其最近的類簇中心點(diǎn)所代表的類簇中，所有點(diǎn)分配完畢之后，根據(jù)一個(gè)類簇內(nèi)的所有點(diǎn)重新計(jì)算該類簇的中心點(diǎn)(取平均值)，然后再迭代的進(jìn)行分配點(diǎn)和更新類簇中心點(diǎn)的步驟，直至類簇中心點(diǎn)的變化很小，或者達(dá)到指定的迭代次數(shù)。
KMeans算法本身思想比較簡單，但是合理的確定K值和K個(gè)初始類簇中心點(diǎn)對(duì)于聚類效果的好壞有很大的影響。
    聚類算法實(shí)現(xiàn)
    假設(shè)對(duì)象集合為D，準(zhǔn)備劃分為k個(gè)簇。
    基本算法步驟如下：
    1、從D中隨機(jī)取k個(gè)元素，作為k個(gè)簇的各自的中心。
    2、分別計(jì)算剩下的元素到k個(gè)簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。
    3、根據(jù)聚類結(jié)果，重新計(jì)算k個(gè)簇各自的中心，計(jì)算方法是取簇中所有元素各自維度的算術(shù)平均數(shù)。
    4、將D中全部元素按照新的中心重新聚類。
    5、重復(fù)第4步，直到聚類結(jié)果不再變化。
    6、將結(jié)果輸出。

核心Java代碼如下：
/**
* 迭代計(jì)算每個(gè)點(diǎn)到各個(gè)中心點(diǎn)的距離，選擇最小距離將該點(diǎn)劃入到合適的分組聚類中，反復(fù)進(jìn)行，直到
* 分組不再變化或者各個(gè)中心點(diǎn)不再變化為止。
* @return
*/
public List[] comput() {
List[] results = new ArrayList[k];//為k個(gè)分組，分別定義一個(gè)聚簇集合，未來放入元素。

    boolean centerchange = true;//該變量存儲(chǔ)中心點(diǎn)是否發(fā)生變化
    while (centerchange) {
        iterCount++;//存儲(chǔ)迭代次數(shù)
        centerchange = false;
        for (int i = 0; i < k; i++) {
            results[i] = new ArrayList<T>();
        }
        for (int i = 0; i < players.size(); i++) {
            T p = players.get(i);
            double[] dists = new double[k];
            for (int j = 0; j < initPlayers.size(); j++) {
                T initP = initPlayers.get(j);
                /* 計(jì)算距離  這里采用的公式是兩個(gè)對(duì)象相關(guān)屬性的平方和，最后求開方*/
                double dist = distance(initP, p);
                dists[j] = dist;
            }

            int dist_index = computOrder(dists);//計(jì)算該點(diǎn)到各個(gè)質(zhì)心的距離的最小值，獲得下標(biāo)
            results[dist_index].add(p);//劃分到對(duì)應(yīng)的分組。
        }
        /*
         * 將點(diǎn)聚類之后，重新尋找每個(gè)簇的新的中心點(diǎn)，根據(jù)每個(gè)點(diǎn)的關(guān)注屬性的平均值確立新的質(zhì)心。
         */
        for (int i = 0; i < k; i++) {
            T player_new = findNewCenter(results[i]);
            System.out.println("第"+iterCount+"次迭代，中心點(diǎn)是："+player_new.toString());
            T player_old = initPlayers.get(i);
            if (!IsPlayerEqual(player_new, player_old)) {
                centerchange = true;
                initPlayers.set(i, player_new);
            }

        }

    }

    return results;
}
上面代碼是其中核心代碼，我們根據(jù)對(duì)象集合List和提前設(shè)定的k個(gè)聚集,最終完成聚類。我們測試一下，假設(shè)要測試根據(jù)NBA球員的場均得分情況，進(jìn)行得分高中低的聚集，很簡單，高得分在一組，中等一組，低得分一組。
我們定義一個(gè)Player類，里面有屬性goal，并錄入數(shù)據(jù)。并設(shè)定分組數(shù)目為k=3。
測試代碼如下:
List listPlayers = new ArrayList();
Player p1 = new Player();
p1.setName(“mrchi1”);
p1.setGoal(1);
p1.setAssists(8);
listPlayers.add(p1);

    Player p2 = new Player();
    p2.setName("mrchi2");
    p2.setGoal(2);
    listPlayers.add(p2);

    Player p3 = new Player();
    p3.setName("mrchi3");
    p3.setGoal(3);
    listPlayers.add(p3);
    //其他對(duì)象定義此處略。制造幾個(gè)球員的對(duì)象即可。
    Kmeans<Player> kmeans = new Kmeans<Player>(listPlayers, 3);
    List<Player>[] results = kmeans.comput();
    for (int i = 0; i < results.length; i++) {
        System.out.println("類別" + (i + 1) + "聚集了以下球員：");
        List<Player> list = results[i];
        for (Player p : list) {
            System.out.println(p.getName() + "--->" + p.getGoal()

        }
    }
算法運(yùn)行結(jié)果：

可以看出中心點(diǎn)經(jīng)歷了四次迭代變化，最終分類結(jié)果也確實(shí)是相近得分的分到了一組。當(dāng)然這種算法有缺點(diǎn)，首先就是初始的k個(gè)中心點(diǎn)的確定非常重要，結(jié)果也有差異?？梢赃x擇彼此距離盡可能遠(yuǎn)的K個(gè)點(diǎn)，也可以先對(duì)數(shù)據(jù)用層次聚類算法進(jìn)行聚類，得到K個(gè)簇之后，從每個(gè)類簇中選擇一個(gè)點(diǎn)，該點(diǎn)可以是該類簇的中心點(diǎn)，或者是距離類簇中心點(diǎn)最近的那個(gè)點(diǎn)。