簡介： 智 能推薦大都基于海量數(shù)據(jù)的計(jì)算和處理，然而我們發(fā)現(xiàn)在海量數(shù)據(jù)上高效的運(yùn)行協(xié)同過濾算法以及其他推薦策略這樣高復(fù)雜的算法是有很大的挑戰(zhàn)的，在面對解決這 個(gè)問題的過程中，大家提出了很多減少計(jì)算量的方法，而聚類無疑是其中最優(yōu)的選擇之一。 聚類 (Clustering) 是一個(gè)數(shù)據(jù)挖掘的經(jīng)典問題，它的目的是將數(shù)據(jù)分為多個(gè)簇 (Cluster)，在同一個(gè)簇中的對象之間有較高的相似度，而不同簇的對象差別較大。聚類被廣泛的應(yīng)用于數(shù)據(jù)處理和統(tǒng)計(jì)分析領(lǐng)域。Apache Mahout 是 ASF(Apache Software Foundation) 的一個(gè)較新的開源項(xiàng)目，它源于 Lucene，構(gòu)建在 Hadoop 之上，關(guān)注海量數(shù)據(jù)上的機(jī)器學(xué)習(xí)經(jīng)典算法的高效實(shí)現(xiàn)。本文主要介紹如何基于 Apache Mahout 實(shí)現(xiàn)高效的聚類算法，從而實(shí)現(xiàn)更高效的數(shù)據(jù)處理和分析的應(yīng)用。

查看本系列更多內(nèi)容

聚類分析

什么是聚類分析？

聚類 (Clustering) 就是將數(shù)據(jù)對象分組成為多個(gè)類或者簇 (Cluster)，它的目標(biāo)是：在同一個(gè)簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。所以，在很多應(yīng)用中，一個(gè)簇中的數(shù)據(jù)對象可以被作 為一個(gè)整體來對待，從而減少計(jì)算量或者提高計(jì)算質(zhì)量。

其實(shí)聚類是一個(gè)人們?nèi)粘Ｉ畹某Ｒ娦袨?，即所謂“物以類聚，人以群分”，核心的思想也就是聚類。人們總是不斷地改進(jìn)下意識中的聚類模式來學(xué) 習(xí)如何區(qū)分各個(gè)事物和人。同時(shí)，聚類分析已經(jīng)廣泛的應(yīng)用在許多應(yīng)用中，包括模式識別，數(shù)據(jù)分析，圖像處理以及市場研究。通過聚類，人們能意識到密集和稀疏 的區(qū)域，發(fā)現(xiàn)全局的分布模式，以及數(shù)據(jù)屬性之間的有趣的相互關(guān)系。

聚類同時(shí)也在 Web 應(yīng)用中起到越來越重要的作用。最被廣泛使用的既是對 Web 上的文檔進(jìn)行分類，組織信息的發(fā)布，給用戶一個(gè)有效分類的內(nèi)容瀏覽系統(tǒng)（門戶網(wǎng)站），同時(shí)可以加入時(shí)間因素，進(jìn)而發(fā)現(xiàn)各個(gè)類內(nèi)容的信息發(fā)展，最近被大家關(guān) 注的主題和話題，或者分析一段時(shí)間內(nèi)人們對什么樣的內(nèi)容比較感興趣，這些有趣的應(yīng)用都得建立在聚類的基礎(chǔ)之上。作為一個(gè)數(shù)據(jù)挖掘的功能，聚類分析能作為獨(dú) 立的工具來獲得數(shù)據(jù)分布的情況，觀察每個(gè)簇的特點(diǎn)，集中對特定的某些簇做進(jìn)一步的分析，此外，聚類分析還可以作為其他算法的預(yù)處理步驟，簡化計(jì)算量，提高 分析效率，這也是我們在這里介紹聚類分析的目的。

不同的聚類問題

對于一個(gè)聚類問題，要挑選最適合最高效的算法必須對要解決的聚類問題本身進(jìn)行剖析，下面我們就從幾個(gè)側(cè)面分析一下聚類問題的需求。

聚類結(jié)果是排他的還是可重疊的

為了很好理解這個(gè)問題，我們以一個(gè)例子進(jìn)行分析，假設(shè)你的聚類問題需要得到二個(gè)簇：“喜歡詹姆斯卡梅隆電影的用戶”和“不喜歡詹姆斯卡梅隆 的用戶”，這其實(shí)是一個(gè)排他的聚類問題，對于一個(gè)用戶，他要么屬于“喜歡”的簇，要么屬于不喜歡的簇。但如果你的聚類問題是“喜歡詹姆斯卡梅隆電影的用 戶”和“喜歡里奧納多電影的用戶”，那么這個(gè)聚類問題就是一個(gè)可重疊的問題，一個(gè)用戶他可以既喜歡詹姆斯卡梅隆又喜歡里奧納多。

所以這個(gè)問題的核心是，對于一個(gè)元素，他是否可以屬于聚類結(jié)果中的多個(gè)簇中，如果是，則是一個(gè)可重疊的聚類問題，如果否，那么是一個(gè)排他的聚類問題。

基于層次還是基于劃分

其實(shí)大部分人想到的聚類問題都是“劃分”問題，就是拿到一組對象，按照一定的原則將它們分成不同的組，這是典型的劃分聚類問題。但除了基于 劃分的聚類，還有一種在日常生活中也很常見的類型，就是基于層次的聚類問題，它的聚類結(jié)果是將這些對象分等級，在頂層將對象進(jìn)行大致的分組，隨后每一組再 被進(jìn)一步的細(xì)分，也許所有路徑最終都要到達(dá)一個(gè)單獨(dú)實(shí)例，這是一種“自頂向下”的層次聚類解決方法，對應(yīng)的，也有“自底向上”的。其實(shí)可以簡單的理解， “自頂向下”就是一步步的細(xì)化分組，而“自底向上”就是一步步的歸并分組。

簇?cái)?shù)目固定的還是無限制的聚類

這個(gè)屬性很好理解，就是你的聚類問題是在執(zhí)行聚類算法前已經(jīng)確定聚類的結(jié)果應(yīng)該得到多少簇，還是根據(jù)數(shù)據(jù)本身的特征，由聚類算法選擇合適的簇的數(shù)目。

基于距離還是基于概率分布模型

在本系列的第二篇介紹協(xié)同過濾的文章中，我們已經(jīng)詳細(xì)介紹了相似性和距離的概念?；诰嚯x的聚類問題應(yīng)該很好理解，就是將距離近的相似的對象聚在一起。相比起來，基于概率分布模型的，可能不太好理解，那么下面給個(gè)簡單的例子。

一個(gè)概率分布模型可以理解是在 N 維空間的一組點(diǎn)的分布，而它們的分布往往符合一定的特征，比如組成一個(gè)特定的形狀?；诟怕史植寄Ｐ偷木垲悊栴}，就是在一組對象中，找到能符合特定分布模 型的點(diǎn)的集合，他們不一定是距離最近的或者最相似的，而是能完美的呈現(xiàn)出概率分布模型所描述的模型。

下面圖 1 給出了一個(gè)例子，對同樣一組點(diǎn)集，應(yīng)用不同的聚類策略，得到完全不同的聚類結(jié)果。左側(cè)給出的結(jié)果是基于距離的，核心的原則就是將距離近的點(diǎn)聚在一起，右側(cè) 給出的基于概率分布模型的聚類結(jié)果，這里采用的概率分布模型是一定弧度的橢圓。圖中專門標(biāo)出了兩個(gè)紅色的點(diǎn)，這兩點(diǎn)的距離很近，在基于距離的聚類中，將他 們聚在一個(gè)類中，但基于概率分布模型的聚類則將它們分在不同的類中，只是為了滿足特定的概率分布模型（當(dāng)然這里我特意舉了一個(gè)比較極端的例子）。所以我們 可以看出，在基于概率分布模型的聚類方法里，核心是模型的定義，不同的模型可能導(dǎo)致完全不同的聚類結(jié)果。

回頁首

Apache Mahout 中的聚類分析框架

Apache Mahout 是 Apache Software Foundation (ASF) 旗下的一個(gè)開源項(xiàng)目，提供一些可擴(kuò)展的機(jī)器學(xué)習(xí)領(lǐng)域經(jīng)典算法的實(shí)現(xiàn)，旨在幫助開發(fā)人員更加方便快捷地創(chuàng)建智能應(yīng)用程序，并且，在 Mahout 的最近版本中還加入了對 Apache Hadoop 的支持，使這些算法可以更高效的運(yùn)行在云計(jì)算環(huán)境中。

關(guān)于 Apache Mahout 的安裝和配置請參考《基于 Apache Mahout 構(gòu)建社會化推薦引擎》，它是筆者 09 年發(fā)表的一篇關(guān)于基于 Mahout 實(shí)現(xiàn)推薦引擎的 developerWorks 文章，其中詳細(xì)介紹了 Mahout 的安裝步驟。

Mahout 中提供了常用的多種聚類算法，涉及我們剛剛討論過的各種類型算法的具體實(shí)現(xiàn)，下面我們就進(jìn)一步深入幾個(gè)典型的聚類算法的原理，優(yōu)缺點(diǎn)和實(shí)用場景，以及如何使用 Mahout 高效的實(shí)現(xiàn)它們。

回頁首

深入聚類算法

深入介紹聚類算法之前，這里先對 Mahout 中對各種聚類問題的數(shù)據(jù)模型進(jìn)行簡要的介紹。

數(shù)據(jù)模型

Mahout 的聚類算法將對象表示成一種簡單的數(shù)據(jù)模型：向量 (Vector)。在向量數(shù)據(jù)描述的基礎(chǔ)上，我們可以輕松的計(jì)算兩個(gè)對象的相似性，關(guān)于向量和向量的相似度計(jì)算，本系列的上一篇介紹協(xié)同過濾算法的文章中 已經(jīng)進(jìn)行了詳細(xì)的介紹，請參考《“探索推薦引擎內(nèi)部的秘密”系列 - Part 2: 深入推薦引擎相關(guān)算法 -- 協(xié)同過濾》。

Mahout 中的向量 Vector 是一個(gè)每個(gè)域是浮點(diǎn)數(shù) (double) 的復(fù)合對象，最容易聯(lián)想到的實(shí)現(xiàn)就是一個(gè)浮點(diǎn)數(shù)的數(shù)組。但在具體應(yīng)用由于向量本身數(shù)據(jù)內(nèi)容的不同，比如有些向量的值很密集，每個(gè)域都有值；有些呢則是很稀 疏，可能只有少量域有值，所以 Mahout 提供了多個(gè)實(shí)現(xiàn)：

1. DenseVector，它的實(shí)現(xiàn)就是一個(gè)浮點(diǎn)數(shù)數(shù)組，對向量里所有域都進(jìn)行存儲，適合用于存儲密集向量。
2. RandomAccessSparseVector 基于浮點(diǎn)數(shù)的 HashMap 實(shí)現(xiàn)的，key 是整形 (int) 類型，value 是浮點(diǎn)數(shù) (double) 類型，它只存儲向量中不為空的值，并提供隨機(jī)訪問。
3. SequentialAccessVector 實(shí)現(xiàn)為整形 (int) 類型和浮點(diǎn)數(shù) (double) 類型的并行數(shù)組，它也只存儲向量中不為空的值，但只提供順序訪問。

用戶可以根據(jù)自己算法的需求選擇合適的向量實(shí)現(xiàn)類，如果算法需要很多隨機(jī)訪問，應(yīng)該選擇 DenseVector 或者 RandomAccessSparseVector，如果大部分都是順序訪問，SequentialAccessVector 的效果應(yīng)該更好。

介紹了向量的實(shí)現(xiàn)，下面我們看看如何將現(xiàn)有的數(shù)據(jù)建模成向量，術(shù)語就是“如何對數(shù)據(jù)進(jìn)行向量化”，以便采用 Mahout 的各種高效的聚類算法。

1. 簡單的整形或浮點(diǎn)型的數(shù)據(jù)

   這種數(shù)據(jù)最簡單，只要將不同的域存在向量中即可，比如 n 維空間的點(diǎn)，其實(shí)本身可以被描述為一個(gè)向量。

2. 枚舉類型數(shù)據(jù)

   這類數(shù)據(jù)是對物體的描述，只是取值范圍有限。舉個(gè)例子，假設(shè)你有一個(gè)蘋果信息的數(shù)據(jù)集，每個(gè)蘋果的數(shù)據(jù)包括：大小，重量，顏色等，我們以顏色為例，設(shè)蘋果 的顏色數(shù)據(jù)包括：紅色，黃色和綠色。在對數(shù)據(jù)進(jìn)行建模時(shí)，我們可以用數(shù)字來表示顏色，紅色 =1，黃色 =2，綠色 =3，那么大小直徑 8cm，重量 0.15kg，顏色是紅色的蘋果，建模的向量就是 <8, 0.15, 1>。

   下面的清單 1 給出了對以上兩種數(shù)據(jù)進(jìn)行向量化的例子。

   
   
   清單 1. 創(chuàng)建簡單的向量
   

   // 創(chuàng)建一個(gè)二維點(diǎn)集的向量組 public static final double[][] points = { { 1, 1 }, { 2, 1 }, { 1, 2 }, { 2, 2 }, { 3, 3 }, { 8, 8 }, { 9, 8 }, { 8, 9 }, { 9, 9 }, { 5, 5 }, { 5, 6 }, { 6, 6 }}; public static List<Vector> getPointVectors(double[][] raw) { List<Vector> points = new ArrayList<Vector>(); for (int i = 0; i < raw.length; i++) { double[] fr = raw[i]; // 這里選擇創(chuàng)建 RandomAccessSparseVector Vector vec = new RandomAccessSparseVector(fr.length); // 將數(shù)據(jù)存放在創(chuàng)建的 Vector 中 vec.assign(fr); points.add(vec); } return points; } // 創(chuàng)建蘋果信息數(shù)據(jù)的向量組 public static List<Vector> generateAppleData() { List<Vector> apples = new ArrayList<Vector>(); // 這里創(chuàng)建的是 NamedVector，其實(shí)就是在上面幾種 Vector 的基礎(chǔ)上， //為每個(gè) Vector 提供一個(gè)可讀的名字 NamedVector apple = new NamedVector(new DenseVector( new double[] {0.11, 510, 1}), "Small round green apple"); apples.add(apple); apple = new NamedVector(new DenseVector(new double[] {0.2, 650, 3}), "Large oval red apple"); apples.add(apple); apple = new NamedVector(new DenseVector(new double[] {0.09, 630, 1}), "Small elongated red apple"); apples.add(apple); apple = new NamedVector(new DenseVector(new double[] {0.25, 590, 3}), "Large round yellow apple"); apples.add(apple); apple = new NamedVector(new DenseVector(new double[] {0.18, 520, 2}), "Medium oval green apple"); apples.add(apple); return apples; }

   
   
3. 文本信息

   作為聚類算法的主要應(yīng)用場景 - 文本分類，對文本信息的建模也是一個(gè)常見的問題。在信息檢索研究領(lǐng)域已經(jīng)有很好的建模方式，就是信息檢索領(lǐng)域中最常用的向量空間模型 (Vector Space Model, VSM)。因?yàn)橄蛄靠臻g模型不是本文的重點(diǎn)，這里給一個(gè)簡要的介紹，有興趣的朋友可以查閱參考目錄中給出的相關(guān)文檔。

   文本的向量空間模型就是將文本信息建模為一個(gè)向量，其中每一個(gè)域是文本中出現(xiàn)的一個(gè)詞的權(quán)重。關(guān)于權(quán)重的計(jì)算則有很多中：

   • 最簡單的莫過于直接計(jì)數(shù)，就是詞在文本里出現(xiàn)的次數(shù)。這種方法簡單，但是對文本內(nèi)容描述的不夠精確。
   • 詞的頻率 (Team Frequency, TF)：就是將詞在文本中出現(xiàn)的頻率作為詞的權(quán)重。這種方法只是對于直接計(jì)數(shù)進(jìn)行了歸一化處理，目的是讓不同長度的文本模型有統(tǒng)一的取值空間，便于文本相 似度的比較，但可以看出，簡單計(jì)數(shù)和詞頻都不能解決“高頻無意義詞匯權(quán)重大的問題”，也就是說對于英文文本中，“a”，“the”這樣高頻但無實(shí)際意義的 詞匯并沒有進(jìn)行過濾，這樣的文本模型在計(jì)算文本相似度時(shí)會很不準(zhǔn)確。
   • 詞頻 - 逆向文本頻率 (Term Frequency – Inverse Document Frequency, TF-IDF)：它是對 TF 方法的一種加強(qiáng)，字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時(shí)會隨著它在所有文本中出現(xiàn)的頻率成反比下降。舉個(gè)例子，對于“高頻無意義詞 匯”，因?yàn)樗鼈兇蟛糠謺霈F(xiàn)在所有的文本中，所以它們的權(quán)重會大打折扣，這樣就使得文本模型在描述文本特征上更加精確。在信息檢索領(lǐng)域，TF-IDF 是對文本信息建模的最常用的方法。

   對于文本信息的向量化，Mahout 已經(jīng)提供了工具類，它基于 Lucene 給出了對文本信息進(jìn)行分析，然后創(chuàng)建文本向量。下面的清單 2 給出了一個(gè)例子，分析的文本數(shù)據(jù)是路透提供的新聞數(shù)據(jù)，參考資源里給出了下載地址。將數(shù)據(jù)集下載后，放在“clustering/reuters”目錄 下。

   
   
   清單 2. 創(chuàng)建文本信息的向量
   

   public static void documentVectorize(String[] args) throws Exception{ //1. 將路透的數(shù)據(jù)解壓縮 , Mahout 提供了專門的方法 DocumentClustering.extractReuters(); //2. 將數(shù)據(jù)存儲成 SequenceFile，因?yàn)檫@些工具類就是在 Hadoop 的基礎(chǔ)上做的，所以首先我們需要將數(shù)據(jù)寫 // 成 SequenceFile，以便讀取和計(jì)算 DocumentClustering.transformToSequenceFile(); //3. 將 SequenceFile 文件中的數(shù)據(jù)，基于 Lucene 的工具進(jìn)行向量化 DocumentClustering.transformToVector(); } public static void extractReuters(){ //ExtractReuters 是基于 Hadoop 的實(shí)現(xiàn)，所以需要將輸入輸出的文件目錄傳給它，這里我們可以直接把它映 // 射到我們本地的一個(gè)文件夾，解壓后的數(shù)據(jù)將寫入輸出目錄下 File inputFolder = new File("clustering/reuters"); File outputFolder = new File("clustering/reuters-extracted"); ExtractReuters extractor = new ExtractReuters(inputFolder, outputFolder); extractor.extract(); } public static void transformToSequenceFile(){ //SequenceFilesFromDirectory 實(shí)現(xiàn)將某個(gè)文件目錄下的所有文件寫入一個(gè) SequenceFiles 的功能 // 它其實(shí)本身是一個(gè)工具類，可以直接用命令行調(diào)用，這里直接調(diào)用了它的 main 方法 String[] args = {"-c", "UTF-8", "-i", "clustering/reuters-extracted/", "-o", "clustering/reuters-seqfiles"}; // 解釋一下參數(shù)的意義： // -c: 指定文件的編碼形式，這里用的是"UTF-8" // -i: 指定輸入的文件目錄，這里指到我們剛剛導(dǎo)出文件的目錄 // -o: 指定輸出的文件目錄 try { SequenceFilesFromDirectory.main(args); } catch (Exception e) { e.printStackTrace(); } } public static void transformToVector(){ //SparseVectorsFromSequenceFiles 實(shí)現(xiàn)將 SequenceFiles 中的數(shù)據(jù)進(jìn)行向量化。 // 它其實(shí)本身是一個(gè)工具類，可以直接用命令行調(diào)用，這里直接調(diào)用了它的 main 方法 String[] args = {"-i", "clustering/reuters-seqfiles/", "-o", "clustering/reuters-vectors-bigram", "-a", "org.apache.lucene.analysis.WhitespaceAnalyzer" , "-chunk", "200", "-wt", "tfidf", "-s", "5", "-md", "3", "-x", "90", "-ng", "2", "-ml", "50", "-seq"}; // 解釋一下參數(shù)的意義： // -i: 指定輸入的文件目錄，這里指到我們剛剛生成 SequenceFiles 的目錄 // -o: 指定輸出的文件目錄 // -a: 指定使用的 Analyzer，這里用的是 lucene 的空格分詞的 Analyzer // -chunk: 指定 Chunk 的大小，單位是 M。對于大的文件集合，我們不能一次 load 所有文件，所以需要 // 對數(shù)據(jù)進(jìn)行切塊 // -wt: 指定分析時(shí)采用的計(jì)算權(quán)重的模式，這里選了 tfidf // -s: 指定詞語在整個(gè)文本集合出現(xiàn)的最低頻度，低于這個(gè)頻度的詞匯將被丟掉 // -md: 指定詞語在多少不同的文本中出現(xiàn)的最低值，低于這個(gè)值的詞匯將被丟掉 // -x: 指定高頻詞匯和無意義詞匯（例如 is，a，the 等）的出現(xiàn)頻率上限，高于上限的將被丟掉 // -ng: 指定分詞后考慮詞匯的最大長度，例如 1-gram 就是，coca，cola，這是兩個(gè)詞， // 2-gram 時(shí)，coca cola 是一個(gè)詞匯，2-gram 比 1-gram 在一定情況下分析的更準(zhǔn)確。 // -ml: 指定判斷相鄰詞語是不是屬于一個(gè)詞匯的相似度閾值，當(dāng)選擇 >1-gram 時(shí)才有用，其實(shí)計(jì)算的是 // Minimum Log Likelihood Ratio 的閾值 // -seq: 指定生成的向量是 SequentialAccessSparseVectors，沒設(shè)置時(shí)默認(rèn)生成還是 // RandomAccessSparseVectors try { SparseVectorsFromSequenceFiles.main(args); } catch (Exception e) { e.printStackTrace(); } }

   
   

   
   這里補(bǔ)充一點(diǎn)，生成的向量化文件的目錄結(jié)構(gòu)是這樣的：

   
   
   圖 2 文本信息向量化
   
   
   
   • df-count 目錄：保存著文本的頻率信息
   • tf-vectors 目錄：保存著以 TF 作為權(quán)值的文本向量
   • tfidf-vectors 目錄：保存著以 TFIDF 作為權(quán)值的文本向量
   • tokenized-documents 目錄：保存著分詞過后的文本信息
   • wordcount 目錄：保存著全局的詞匯出現(xiàn)的次數(shù)
   • dictionary.file-0 目錄：保存著這些文本的詞匯表
   • frequcency-file-0 目錄 : 保存著詞匯表對應(yīng)的頻率信息。

介紹完向量化問題，下面我們深入分析各個(gè)聚類算法，首先介紹的是最經(jīng)典的 K 均值算法。

K 均值聚類算法

K 均值是典型的基于距離的排他的劃分方法：給定一個(gè) n 個(gè)對象的數(shù)據(jù)集，它可以構(gòu)建數(shù)據(jù)的 k 個(gè)劃分，每個(gè)劃分就是一個(gè)聚類，并且 k<=n，同時(shí)還需要滿足兩個(gè)要求：

• 每個(gè)組至少包含一個(gè)對象
• 每個(gè)對象必須屬于且僅屬于一個(gè)組。

K 均值的基本原理是這樣的，給定 k，即要構(gòu)建的劃分的數(shù)目，

1. 首先創(chuàng)建一個(gè)初始劃分，隨機(jī)地選擇 k 個(gè)對象，每個(gè)對象初始地代表了一個(gè)簇中心。對于其他的對象，根據(jù)其與各個(gè)簇中心的距離，將它們賦給最近的簇。
2. 然后采用一種迭代的重定位技術(shù)，嘗試通過對象在劃分間移動(dòng)來改進(jìn)劃分。所謂重定位技術(shù)，就是當(dāng)有新的對象加入簇或者已有對象離開簇的時(shí)候，重新計(jì)算簇的平均值，然后對對象進(jìn)行重新分配。這個(gè)過程不斷重復(fù)，直到?jīng)]有簇中對象的變化。

當(dāng)結(jié)果簇是密集的，而且簇和簇之間的區(qū)別比較明顯時(shí)，K 均值的效果比較好。對于處理大數(shù)據(jù)集，這個(gè)算法是相對可伸縮的和高效的，它的復(fù)雜度是 O(nkt)，n 是對象的個(gè)數(shù)，k 是簇的數(shù)目，t 是迭代的次數(shù)，通常 k<<n，且 t<<n，所以算法經(jīng)常以局部最優(yōu)結(jié)束。

K 均值的最大問題是要求用戶必須事先給出 k 的個(gè)數(shù)，k 的選擇一般都基于一些經(jīng)驗(yàn)值和多次實(shí)驗(yàn)結(jié)果，對于不同的數(shù)據(jù)集，k 的取值沒有可借鑒性。另外，K 均值對“噪音”和孤立點(diǎn)數(shù)據(jù)是敏感的，少量這類的數(shù)據(jù)就能對平均值造成極大的影響。

說了這么多理論的原理，下面我們基于 Mahout 實(shí)現(xiàn)一個(gè)簡單的 K 均值算法的例子。如前面介紹的，Mahout 提供了基本的基于內(nèi)存的實(shí)現(xiàn)和基于 Hadoop 的 Map/Reduce 的實(shí)現(xiàn)，分別是 KMeansClusterer 和 KMeansDriver，下面給出一個(gè)簡單的例子，就基于我們在清單 1 里定義的二維點(diǎn)集數(shù)據(jù)。

                              
 // 基于內(nèi)存的 K 均值聚類算法實(shí)現(xiàn)
 public static void kMeansClusterInMemoryKMeans(){ 
 // 指定需要聚類的個(gè)數(shù)，這里選擇 2 類
 int k = 2; 
 // 指定 K 均值聚類算法的最大迭代次數(shù)
 int maxIter = 3; 
 // 指定 K 均值聚類算法的最大距離閾值
 double distanceThreshold = 0.01; 
 // 聲明一個(gè)計(jì)算距離的方法，這里選擇了歐幾里德距離
 DistanceMeasure measure = new EuclideanDistanceMeasure(); 
 // 這里構(gòu)建向量集，使用的是清單 1 里的二維點(diǎn)集
 List<Vector> pointVectors = SimpleDataSet.getPointVectors(SimpleDataSet.points); 
 // 從點(diǎn)集向量中隨機(jī)的選擇 k 個(gè)作為簇的中心
 List<Vector> randomPoints = RandomSeedGenerator.chooseRandomPoints(pointVectors, k); 
 // 基于前面選中的中心構(gòu)建簇
 List<Cluster> clusters = new ArrayList<Cluster>(); 
 int clusterId = 0; 
 for(Vector v : randomPoints){ 
         clusters.add(new Cluster(v, clusterId ++, measure)); 
 } 
 // 調(diào)用 KMeansClusterer.clusterPoints 方法執(zhí)行 K 均值聚類
 List<List<Cluster>> finalClusters = KMeansClusterer.clusterPoints(pointVectors, 
 clusters, measure, maxIter, distanceThreshold); 

 // 打印最終的聚類結(jié)果
 for(Cluster cluster : finalClusters.get(finalClusters.size() -1)){ 
         System.out.println("Cluster id: " + cluster.getId() + 
" center: " + cluster.getCenter().asFormatString()); 
         System.out.println("       Points: " + cluster.getNumPoints());        
 } 
 } 
 // 基于 Hadoop 的 K 均值聚類算法實(shí)現(xiàn)
 public static void kMeansClusterUsingMapReduce () throws Exception{ 
 // 聲明一個(gè)計(jì)算距離的方法，這里選擇了歐幾里德距離
         DistanceMeasure measure = new EuclideanDistanceMeasure(); 
         // 指定輸入路徑，如前面介紹的一樣，基于 Hadoop 的實(shí)現(xiàn)就是通過指定輸入輸出的文件路徑來指定數(shù)據(jù)源的。
         Path testpoints = new Path("testpoints"); 
         Path output = new Path("output"); 
         // 清空輸入輸出路徑下的數(shù)據(jù)
 HadoopUtil.overwriteOutput(testpoints); 
         HadoopUtil.overwriteOutput(output); 
         RandomUtils.useTestSeed(); 
 // 在輸入路徑下生成點(diǎn)集，與內(nèi)存的方法不同，這里需要把所有的向量寫進(jìn)文件，下面給出具體的例子
         SimpleDataSet.writePointsToFile(testpoints); 
 // 指定需要聚類的個(gè)數(shù)，這里選擇 2 類
 int k = 2; 
 // 指定 K 均值聚類算法的最大迭代次數(shù)
 int maxIter = 3; 
         // 指定 K 均值聚類算法的最大距離閾值
 double distanceThreshold = 0.01; 
 // 隨機(jī)的選擇 k 個(gè)作為簇的中心
 Path clusters = RandomSeedGenerator.buildRandom(testpoints, 
 new Path(output, "clusters-0"), k, measure); 
 // 調(diào)用 KMeansDriver.runJob 方法執(zhí)行 K 均值聚類算法
 KMeansDriver.runJob(testpoints, clusters, output, measure, 
 distanceThreshold, maxIter, 1, true, true); 
 // 調(diào)用 ClusterDumper 的 printClusters 方法將聚類結(jié)果打印出來。
 ClusterDumper clusterDumper = new ClusterDumper(new Path(output, 
"clusters-" + maxIter -1), new Path(output, "clusteredPoints")); 
 clusterDumper.printClusters(null); 
 } 
 //SimpleDataSet 的 writePointsToFile 方法，將測試點(diǎn)集寫入文件里
 // 首先我們將測試點(diǎn)集包裝成 VectorWritable 形式，從而將它們寫入文件
 public static List<VectorWritable> getPoints(double[][] raw) { 
         List<VectorWritable> points = new ArrayList<VectorWritable>(); 
 for (int i = 0; i < raw.length; i++) { 
                 double[] fr = raw[i]; 
                 Vector vec = new RandomAccessSparseVector(fr.length); 
                 vec.assign(fr); 
 // 只是在加入點(diǎn)集前，在 RandomAccessSparseVector 外加了一層 VectorWritable 的包裝
                 points.add(new VectorWritable(vec)); 
         } 
 return points; 
 } 
 // 將 VectorWritable 的點(diǎn)集寫入文件，這里涉及一些基本的 Hadoop 編程元素，詳細(xì)的請參閱參考資源里相關(guān)的內(nèi)容
 public static void writePointsToFile(Path output) throws IOException { 
         // 調(diào)用前面的方法生成點(diǎn)集
         List<VectorWritable> pointVectors = getPoints(points); 
         // 設(shè)置 Hadoop 的基本配置
         Configuration conf = new Configuration(); 
         // 生成 Hadoop 文件系統(tǒng)對象 FileSystem 
         FileSystem fs = FileSystem.get(output.toUri(), conf); 
 // 生成一個(gè) SequenceFile.Writer，它負(fù)責(zé)將 Vector 寫入文件中
         SequenceFile.Writer writer = new SequenceFile.Writer(fs, conf, output, 
         Text.class,  VectorWritable.class); 
         // 這里將向量按照文本形式寫入文件
         try { 
 for (VectorWritable vw : pointVectors) { 
 writer.append(new Text(), vw); 
                 } 
         } finally { 
                 writer.close(); 
         }  
 } 

執(zhí)行結(jié)果
 KMeans Clustering In Memory Result 
 Cluster id: 0 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
"vector":"{"values":{"table":[0,1,0],"values":[1.8,1.8,0.0],"state":[1,1,0],
"freeEntries":1,"distinct":2,"lowWaterMark":0,"highWaterMark":1,
"minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,"lengthSquared":-1.0}"} 
       Points: 5 
 Cluster id: 1 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{"values":{"table":[0,1,0],
 "values":[7.142857142857143,7.285714285714286,0.0],"state":[1,1,0],
 "freeEntries":1,"distinct":2,"lowWaterMark":0,"highWaterMark":1,
 "minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,"lengthSquared":-1.0}"} 
       Points: 7 

 KMeans Clustering Using Map/Reduce Result 
         Weight:  Point: 
         1.0: [1.000, 1.000] 
         1.0: [2.000, 1.000] 
         1.0: [1.000, 2.000] 
         1.0: [2.000, 2.000] 
         1.0: [3.000, 3.000] 
         Weight:  Point: 
         1.0: [8.000, 8.000] 
         1.0: [9.000, 8.000] 
         1.0: [8.000, 9.000] 
         1.0: [9.000, 9.000] 
         1.0: [5.000, 5.000] 
         1.0: [5.000, 6.000] 
         1.0: [6.000, 6.000] 

介紹完 K 均值聚類算法，我們可以看出它最大的優(yōu)點(diǎn)是：原理簡單，實(shí)現(xiàn)起來也相對簡單，同時(shí)執(zhí)行效率和對于大數(shù)據(jù)量的可伸縮性還是較強(qiáng)的。然而缺點(diǎn)也是很明確的，首 先它需要用戶在執(zhí)行聚類之前就有明確的聚類個(gè)數(shù)的設(shè)置，這一點(diǎn)是用戶在處理大部分問題時(shí)都不太可能事先知道的，一般需要通過多次試驗(yàn)找出一個(gè)最優(yōu)的 K 值；其次就是，由于算法在最開始采用隨機(jī)選擇初始聚類中心的方法，所以算法對噪音和孤立點(diǎn)的容忍能力較差。所謂噪音就是待聚類對象中錯(cuò)誤的數(shù)據(jù)，而孤立點(diǎn) 是指與其他數(shù)據(jù)距離較遠(yuǎn)，相似性較低的數(shù)據(jù)。對于 K 均值算法，一旦孤立點(diǎn)和噪音在最開始被選作簇中心，對后面整個(gè)聚類過程將帶來很大的問題，那么我們有什么方法可以先快速找出應(yīng)該選擇多少個(gè)簇，同時(shí)找到簇 的中心，這樣可以大大優(yōu)化 K 均值聚類算法的效率，下面我們就介紹另一個(gè)聚類方法：Canopy 聚類算法。

Canopy 聚類算法

Canopy 聚類算法的基本原則是：首先應(yīng)用成本低的近似的距離計(jì)算方法高效的將數(shù)據(jù)分為多個(gè)組，這里稱為一個(gè) Canopy，我們姑且將它翻譯為“華蓋”，Canopy 之間可以有重疊的部分；然后采用嚴(yán)格的距離計(jì)算方式準(zhǔn)確的計(jì)算在同一 Canopy 中的點(diǎn)，將他們分配與最合適的簇中。Canopy 聚類算法經(jīng)常用于 K 均值聚類算法的預(yù)處理，用來找合適的 k 值和簇中心。

下面詳細(xì)介紹一下創(chuàng)建 Canopy 的過程：初始，假設(shè)我們有一組點(diǎn)集 S，并且預(yù)設(shè)了兩個(gè)距離閾值，T1，T2（T1>T2）；然后選擇一個(gè)點(diǎn)，計(jì)算它與 S 中其他點(diǎn)的距離（這里采用成本很低的計(jì)算方法），將距離在 T1 以內(nèi)的放入一個(gè) Canopy 中，同時(shí)從 S 中去掉那些與此點(diǎn)距離在 T2 以內(nèi)的點(diǎn)（這里是為了保證和中心距離在 T2 以內(nèi)的點(diǎn)不能再作為其他 Canopy 的中心），重復(fù)整個(gè)過程直到 S 為空為止。

對 K 均值的實(shí)現(xiàn)一樣，Mahout 也提供了兩個(gè) Canopy 聚類的實(shí)現(xiàn)，下面我們就看看具體的代碼例子。

                           
 //Canopy 聚類算法的內(nèi)存實(shí)現(xiàn)
 public static void canopyClusterInMemory () { 
         // 設(shè)置距離閾值 T1,T2 
 double T1 = 4.0; 
         double T2 = 3.0; 
 // 調(diào)用 CanopyClusterer.createCanopies 方法創(chuàng)建 Canopy，參數(shù)分別是：
         //      1. 需要聚類的點(diǎn)集
         //      2. 距離計(jì)算方法
         //      3. 距離閾值 T1 和 T2 
         List<Canopy> canopies = CanopyClusterer.createCanopies( 
 SimpleDataSet.getPointVectors(SimpleDataSet.points), 
                 new EuclideanDistanceMeasure(), T1, T2); 
         // 打印創(chuàng)建的 Canopy，因?yàn)榫垲悊栴}很簡單，所以這里沒有進(jìn)行下一步精確的聚類。
         // 有必須的時(shí)候，可以拿到 Canopy 聚類的結(jié)果作為 K 均值聚類的輸入，能更精確更高效的解決聚類問題
 for(Canopy canopy : canopies) { 
                 System.out.println("Cluster id: " + canopy.getId() + 
" center: " + canopy.getCenter().asFormatString()); 
                 System.out.println("       Points: " + canopy.getNumPoints());         
         } 
 } 

 //Canopy 聚類算法的 Hadoop 實(shí)現(xiàn)
 public static void canopyClusterUsingMapReduce() throws Exception{ 
         // 設(shè)置距離閾值 T1,T2 
 double T1 = 4.0; 
         double T2 = 3.0; 
         // 聲明距離計(jì)算的方法
         DistanceMeasure measure = new EuclideanDistanceMeasure(); 
         // 設(shè)置輸入輸出的文件路徑
         Path testpoints = new Path("testpoints"); 
         Path output = new Path("output"); 
         // 清空輸入輸出路徑下的數(shù)據(jù)
         HadoopUtil.overwriteOutput(testpoints); 
         HadoopUtil.overwriteOutput(output); 
         // 將測試點(diǎn)集寫入輸入目錄下
 SimpleDataSet.writePointsToFile(testpoints); 

 // 調(diào)用 CanopyDriver.buildClusters 的方法執(zhí)行 Canopy 聚類，參數(shù)是：
         //      1. 輸入路徑，輸出路徑
         //      2. 計(jì)算距離的方法
         //      3. 距離閾值 T1 和 T2 
         new CanopyDriver().buildClusters(testpoints, output, measure, T1, T2, true); 
         // 打印 Canopy 聚類的結(jié)果
         List<List<Cluster>> clustersM = DisplayClustering.loadClusters(output);
                 List<Cluster> clusters = clustersM.get(clustersM.size()-1); 
         if(clusters != null){ 
 for(Cluster canopy : clusters) { 
    System.out.println("Cluster id: " + canopy.getId() + 
" center: " + canopy.getCenter().asFormatString()); 
   System.out.println("       Points: " + canopy.getNumPoints());
                 } 
         } 
 } 

執(zhí)行結(jié)果
 Canopy Clustering In Memory Result 
 Cluster id: 0 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{"values":{"table":[0,1,0],"values":[1.8,1.8,0.0],
 "state":[1,1,0],"freeEntries":1,"distinct":2,"lowWaterMark":0,
 "highWaterMark":1,"minLoadFactor":0.2,"maxLoadFactor":0.5},
 "size":2,"lengthSquared":-1.0}"} 
       Points: 5 
 Cluster id: 1 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{"values":{"table":[0,1,0],"values":[7.5,7.666666666666667,0.0],
 "state":[1,1,0],"freeEntries":1,"distinct":2,"lowWaterMark":0,
 "highWaterMark":1,"minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,
 "lengthSquared":-1.0}"} 
       Points: 6 
 Cluster id: 2 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{"values":{"table":[0,1,0],"values":[5.0,5.5,0.0],
 "state":[1,1,0],"freeEntries":1,"distinct":2,"lowWaterMark":0,
 "highWaterMark":1,"minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,
 "lengthSquared":-1.0}"} 
       Points: 2 

 Canopy Clustering Using Map/Reduce Result 
 Cluster id: 0 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector", 
 "vector":"{"values":{"table":[0,1,0],"values":[1.8,1.8,0.0],
 "state":[1,1,0],"freeEntries":1,"distinct":2,"lowWaterMark":0,
 "highWaterMark":1,"minLoadFactor":0.2,"maxLoadFactor":0.5},
 "size":2,"lengthSquared":-1.0}"} 
       Points: 5 
 Cluster id: 1 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{"values":{"table":[0,1,0],"values":[7.5,7.666666666666667,0.0],
 "state":[1,1,0],"freeEntries":1,"distinct":2,"lowWaterMark":0,
 "highWaterMark":1,"minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,
 "lengthSquared":-1.0}"} 
       Points: 6 
 Cluster id: 2 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector", 
 "vector":"{"values":{"table":[0,1,0], 
 "values":[5.333333333333333,5.666666666666667,0.0],"state":[1,1,0],
 "freeEntries":1,"distinct":2,"lowWaterMark":0,"highWaterMark":1,
 "minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,"lengthSquared":-1.0}"} 
       Points: 3 

模糊 K 均值聚類算法

模糊 K 均值聚類算法是 K 均值聚類的擴(kuò)展，它的基本原理和 K 均值一樣，只是它的聚類結(jié)果允許存在對象屬于多個(gè)簇，也就是說：它屬于我們前面介紹過的可重疊聚類算法。為了深入理解模糊 K 均值和 K 均值的區(qū)別，這里我們得花些時(shí)間了解一個(gè)概念：模糊參數(shù)（Fuzziness Factor）。

與 K 均值聚類原理類似，模糊 K 均值也是在待聚類對象向量集合上循環(huán)，但是它并不是將向量分配給距離最近的簇，而是計(jì)算向量與各個(gè)簇的相關(guān)性（Association）。假設(shè)有一個(gè)向量 v，有 k 個(gè)簇，v 到 k 個(gè)簇中心的距離分別是 d₁，d₂… d_k，那么 V 到第一個(gè)簇的相關(guān)性 u₁可以通過下面的算式計(jì)算：

計(jì)算 v 到其他簇的相關(guān)性只需將 d₁替換為對應(yīng)的距離。

從上面的算式，我們看出，當(dāng) m 近似 2 時(shí)，相關(guān)性近似 1；當(dāng) m 近似 1 時(shí)，相關(guān)性近似于到該簇的距離，所以 m 的取值在（1，2）區(qū)間內(nèi)，當(dāng) m 越大，模糊程度越大，m 就是我們剛剛提到的模糊參數(shù)。

講了這么多理論的原理，下面我們看看如何使用 Mahout 實(shí)現(xiàn)模糊 K 均值聚類，同前面的方法一樣，Mahout 一樣提供了基于內(nèi)存和基于 Hadoop Map/Reduce 的兩種實(shí)現(xiàn) FuzzyKMeansClusterer 和 FuzzyMeansDriver，分別是清單 5 給出了一個(gè)例子。

                           
 public static void fuzzyKMeansClusterInMemory() { 
 // 指定聚類的個(gè)數(shù)
 int k = 2; 
 // 指定 K 均值聚類算法的最大迭代次數(shù)
 int maxIter = 3; 
 // 指定 K 均值聚類算法的最大距離閾值
 double distanceThreshold = 0.01; 
 // 指定模糊 K 均值聚類算法的模糊參數(shù)
 float fuzzificationFactor = 10; 
 // 聲明一個(gè)計(jì)算距離的方法，這里選擇了歐幾里德距離
 DistanceMeasure measure = new EuclideanDistanceMeasure(); 
 // 構(gòu)建向量集，使用的是清單 1 里的二維點(diǎn)集
         List<Vector> pointVectors = SimpleDataSet.getPointVectors(SimpleDataSet.points); 
 // 從點(diǎn)集向量中隨機(jī)的選擇 k 個(gè)作為簇的中心
         List<Vector> randomPoints = RandomSeedGenerator.chooseRandomPoints(points, k); 
         // 構(gòu)建初始簇，這里與 K 均值不同，使用了 SoftCluster，表示簇是可重疊的
         List<SoftCluster> clusters = new ArrayList<SoftCluster>(); 
         int clusterId = 0; 
         for (Vector v : randomPoints) { 
                 clusters.add(new SoftCluster(v, clusterId++, measure)); 
         } 
 // 調(diào)用 FuzzyKMeansClusterer 的 clusterPoints 方法進(jìn)行模糊 K 均值聚類
         List<List<SoftCluster>> finalClusters = 
         FuzzyKMeansClusterer.clusterPoints(points, 
 clusters, measure, distanceThreshold, maxIter, fuzzificationFactor); 
         // 打印聚類結(jié)果
         for(SoftCluster cluster : finalClusters.get(finalClusters.size() - 1)) { 
                 System.out.println("Fuzzy Cluster id: " + cluster.getId() + 
" center: " + cluster.getCenter().asFormatString()); 
         } 
 } 

 public class fuzzyKMeansClusterUsingMapReduce { 
 // 指定模糊 K 均值聚類算法的模糊參數(shù)
         float fuzzificationFactor = 2.0f; 
 // 指定需要聚類的個(gè)數(shù)，這里選擇 2 類
         int k = 2; 
 // 指定最大迭代次數(shù)
         int maxIter = 3; 
 // 指定最大距離閾值
         double distanceThreshold = 0.01; 
 // 聲明一個(gè)計(jì)算距離的方法，這里選擇了歐幾里德距離
         DistanceMeasure measure = new EuclideanDistanceMeasure(); 
 // 設(shè)置輸入輸出的文件路徑
         Path testpoints = new Path("testpoints"); 
         Path output = new Path("output"); 
 // 清空輸入輸出路徑下的數(shù)據(jù)
         HadoopUtil.overwriteOutput(testpoints); 
         HadoopUtil.overwriteOutput(output); 
 // 將測試點(diǎn)集寫入輸入目錄下
         SimpleDataSet.writePointsToFile(testpoints); 
 // 隨機(jī)的選擇 k 個(gè)作為簇的中心
         Path clusters = RandomSeedGenerator.buildRandom(testpoints, 
 new Path(output, "clusters-0"), k, measure); 
         FuzzyKMeansDriver.runJob(testpoints, clusters, output, measure, 0.5, maxIter, 1, 
 fuzzificationFactor, true, true, distanceThreshold, true); 
 // 打印模糊 K 均值聚類的結(jié)果
         ClusterDumper clusterDumper = new ClusterDumper(new Path(output, "clusters-" + 
 maxIter ),new Path(output, "clusteredPoints")); 
         clusterDumper.printClusters(null); 
 } 

執(zhí)行結(jié)果
 Fuzzy KMeans Clustering In Memory Result 
 Fuzzy Cluster id: 0 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{"values":{"table":[0,1,0],
 "values":[1.9750483367699223,1.993870669568863,0.0],"state":[1,1,0],
 "freeEntries":1,"distinct":2,"lowWaterMark":0,"highWaterMark":1,
 "minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,"lengthSquared":-1.0}"} 
 Fuzzy Cluster id: 1 
 center:{"class":"org.apache.mahout.math.RandomAccessSparseVector",
 "vector":"{"values":{"table":[0,1,0], 
 "values":[7.924827516566109,7.982356511917616,0.0],"state":[1,1,0],
 "freeEntries":1, "distinct":2,"lowWaterMark":0,"highWaterMark":1,
 "minLoadFactor":0.2,"maxLoadFactor":0.5},"size":2,"lengthSquared":-1.0}"} 

 Funzy KMeans Clustering Using Map Reduce Result 
 Weight:  Point: 
         0.9999249428064162: [8.000, 8.000] 
         0.9855340718746096: [9.000, 8.000] 
         0.9869963781734195: [8.000, 9.000] 
         0.9765978701133124: [9.000, 9.000] 
         0.6280999013864511: [5.000, 6.000] 
         0.7826097471578298: [6.000, 6.000] 
         Weight:  Point: 
         0.9672607354172386: [1.000, 1.000] 
         0.9794914088151625: [2.000, 1.000] 
         0.9803932521191389: [1.000, 2.000] 
         0.9977806183197744: [2.000, 2.000] 
         0.9793701109946826: [3.000, 3.000] 
         0.5422929338028506: [5.000, 5.000] 

狄利克雷聚類算法

前面介紹的三種聚類算法都是基于劃分的，下面我們簡要介紹一個(gè)基于概率分布模型的聚類算法，狄利克雷聚類（Dirichlet Processes Clustering）。

首先我們先簡要介紹一下基于概率分布模型的聚類算法（后面簡稱基于模型的聚類算法）的原理：首先需要定義一個(gè)分布模型，簡單的例如：圓形， 三角形等，復(fù)雜的例如正則分布，泊松分布等；然后按照模型對數(shù)據(jù)進(jìn)行分類，將不同的對象加入一個(gè)模型，模型會增長或者收縮；每一輪過后需要對模型的各個(gè)參 數(shù)進(jìn)行重新計(jì)算，同時(shí)估計(jì)對象屬于這個(gè)模型的概率。所以說，基于模型的聚類算法的核心是定義模型，對于一個(gè)聚類問題，模型定義的優(yōu)劣直接影響了聚類的結(jié) 果，下面給出一個(gè)簡單的例子，假設(shè)我們的問題是將一些二維的點(diǎn)分成三組，在圖中用不同的顏色表示，圖 A 是采用圓形模型的聚類結(jié)果，圖 B 是采用三角形模型的聚類結(jié)果?？梢钥闯?，圓形模型是一個(gè)正確的選擇，而三角形模型的結(jié)果既有遺漏又有誤判，是一個(gè)錯(cuò)誤的選擇。

Mahout 實(shí)現(xiàn)的狄利克雷聚類算法是按照如下過程工作的：首先，我們有一組待聚類的對象和一個(gè)分布模型。在 Mahout 中使用 ModelDistribution 生成各種模型。初始狀態(tài)，我們有一個(gè)空的模型，然后嘗試將對象加入模型中，然后一步一步計(jì)算各個(gè)對象屬于各個(gè)模型的概率。下面清單給出了基于內(nèi)存實(shí)現(xiàn)的狄 利克雷聚類算法。

                              
 public static void DirichletProcessesClusterInMemory() { 
 // 指定狄利克雷算法的 alpha 參數(shù)，它是一個(gè)過渡參數(shù)，使得對象分布在不同模型前后能進(jìn)行光滑的過渡
         double alphaValue = 1.0; 
 // 指定聚類模型的個(gè)數(shù)
         int numModels = 3; 
 // 指定 thin 和 burn 間隔參數(shù)，它們是用于降低聚類過程中的內(nèi)存使用量的
         int thinIntervals = 2; 
         int burnIntervals = 2; 
 // 指定最大迭代次數(shù)
         int maxIter = 3; 
         List<VectorWritable> pointVectors = 
         SimpleDataSet.getPoints(SimpleDataSet.points); 
 // 初始階段生成空分布模型，這里用的是 NormalModelDistribution 
         ModelDistribution<VectorWritable> model = 
 new NormalModelDistribution(new VectorWritable(new DenseVector(2))); 
 // 執(zhí)行聚類
         DirichletClusterer dc = new DirichletClusterer(pointVectors, model, alphaValue, 
 numModels, thinIntervals, burnIntervals); 
         List<Cluster[]> result = dc.cluster(maxIter); 
 // 打印聚類結(jié)果
         for(Cluster cluster : result.get(result.size() -1)){ 
                 System.out.println("Cluster id: " + cluster.getId() + " center: " + 
 cluster.getCenter().asFormatString()); 
                 System.out.println("       Points: " + cluster.getNumPoints());        
         } 
 } 

執(zhí)行結(jié)果
 Dirichlet Processes Clustering In Memory Result 
 Cluster id: 0 
 center:{"class":"org.apache.mahout.math.DenseVector",
 "vector":"{"values":[5.2727272727272725,5.2727272727272725],
 "size":2,"lengthSquared":-1.0}"} 
       Points: 11 
 Cluster id: 1 
 center:{"class":"org.apache.mahout.math.DenseVector",
 "vector":"{"values":[1.0,2.0],"size":2,"lengthSquared":-1.0}"} 
       Points: 1 
 Cluster id: 2 
 center:{"class":"org.apache.mahout.math.DenseVector",
 "vector":"{"values":[9.0,8.0],"size":2,"lengthSquared":-1.0}"} 
       Points: 0 

Mahout 中提供多種概率分布模型的實(shí)現(xiàn)，他們都繼承 ModelDistribution，如圖 4 所示，用戶可以根據(jù)自己的數(shù)據(jù)集的特征選擇合適的模型，詳細(xì)的介紹請參考 Mahout 的官方文檔。

Mahout 聚類算法總結(jié)

前面詳細(xì)介紹了 Mahout 提供的四種聚類算法，這里做一個(gè)簡要的總結(jié)，分析各個(gè)算法優(yōu)缺點(diǎn)，其實(shí)，除了這四種以外，Mahout 還提供了一些比較復(fù)雜的聚類算法，這里就不一一詳細(xì)介紹了，詳細(xì)信息請參考 Mahout Wiki 上給出的聚類算法詳細(xì)介紹。

回頁首

總結(jié)

聚類算法被廣泛的運(yùn)用于信息智能處理系統(tǒng)。本文首先簡述了聚類概念與聚類算法思想，使得讀者整體上了解聚類這一重要的技術(shù)。然后從實(shí)際構(gòu)建 應(yīng)用的角度出發(fā)，深入的介紹了開源軟件 Apache Mahout 中關(guān)于聚類的實(shí)現(xiàn)框架，包括了其中的數(shù)學(xué)模型，各種聚類算法以及在不同基礎(chǔ)架構(gòu)上的實(shí)現(xiàn)。通過代碼示例，讀者可以知道針對他的特定的數(shù)據(jù)問題，怎么樣向量 化數(shù)據(jù)，怎么樣選擇各種不同的聚類算法。

本系列的下一篇將繼續(xù)深入了解推薦引擎的相關(guān)算法 -- 分類。與聚類一樣，分類也是一個(gè)數(shù)據(jù)挖掘的經(jīng)典問題，主要用于提取描述重要數(shù)據(jù)類的模型，隨后我們可以根據(jù)這個(gè)模型進(jìn)行預(yù)測，推薦就是一種預(yù)測的行為。同 時(shí)聚類和分類往往也是相輔相成的，他們都為在海量數(shù)據(jù)上進(jìn)行高效的推薦提供輔助。所以本系列的下一篇文章將詳細(xì)介紹各類分類算法，它們的原理，優(yōu)缺點(diǎn)和實(shí) 用場景，并給出基于 Apache Mahout 的分類算法的高效實(shí)現(xiàn)。

最后，感謝大家對本系列的關(guān)注和支持。

參考資料

學(xué)習(xí)

• 聚類分析：Wikipedia 上關(guān)于聚類分析的介紹
  
  
• 數(shù)據(jù)挖掘：概念與技術(shù)（韓家偉）：關(guān)于數(shù)據(jù)挖掘的經(jīng)典著作，詳細(xì)介紹了數(shù)據(jù)挖掘領(lǐng)域的各種問題和應(yīng)用，其中對聚類分析的經(jīng)典算法也有詳盡的講解。
  
  
• 數(shù)據(jù)挖掘：實(shí)用機(jī)器學(xué)習(xí)技術(shù)：同樣是數(shù)據(jù)挖掘的經(jīng)典著作，對領(lǐng)域內(nèi)的算法，算法的發(fā)展進(jìn)行了詳細(xì)的介紹。
  
  
• “Apache Mahout簡介” （Grant Ingersoll，developerWorks，2009 年 10 月）：Mahout 的創(chuàng)始者 Grant Ingersoll 介紹了機(jī)器學(xué)習(xí)的基本概念，并演示了如何使用 Mahout 來實(shí)現(xiàn)文檔集群、提出建議和組織內(nèi)容。
  
  
• Apache Mahout：Apache Mahout 項(xiàng)目的主頁，搜索關(guān)于 Mahout 的所有內(nèi)容。
  
  
• Apache Mahout算法總結(jié)：Apache Mahout 的 Wiki 上關(guān)于實(shí)現(xiàn)算法的詳細(xì)介紹。
  
  
• Mahout In Action：Sean Owen 詳細(xì)介紹了 Mahout 項(xiàng)目，其中有很大篇幅介紹了 Mahout 提供的聚類算法，并給出一些簡單的例子。
  
  
• TF-IDF：Wikipedia 上關(guān)于 TF-IDF 的詳細(xì)介紹，包括它的計(jì)算方法，優(yōu)缺點(diǎn)，應(yīng)用場景等。
  
  
• 路透數(shù)據(jù)集：路透提供了大量的新聞數(shù)據(jù)集，可以作為聚類分析的數(shù)據(jù)源，本文中對文本聚類分析的部分采用了路透“Reuters-21578”數(shù)據(jù)集
  
  
• Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching，發(fā)表于 2000 的 Canopy 算法的論文。
  
  
• 狄利克雷分布：Wikipedia 上關(guān)于狄利克雷分布的介紹，它是本文介紹的狄利克雷聚類算法的基礎(chǔ)
  
  
• 基于Apache Mahout構(gòu)建社會化推薦引擎：筆者 09 年發(fā)布的一篇關(guān)于基于 Mahout 實(shí)現(xiàn)推薦引擎的 developerWorks 文章，其中詳細(xì)介紹了 Mahout 的安裝步驟，并給出一個(gè)簡單的電影推薦引擎的例子。
  
  
• 機(jī)器學(xué)習(xí)：機(jī)器學(xué)習(xí)的 Wikipedia 頁面，可幫助您了解關(guān)于機(jī)器學(xué)習(xí)的更多信息。
  
  
• developerWorks Java技術(shù)專區(qū)：數(shù)百篇關(guān)于 Java 編程各個(gè)方面的文章。
  
  
  
• developerWorks Web development 專區(qū)：通過專門關(guān)于 Web 技術(shù)的文章和教程，擴(kuò)展您在網(wǎng)站開發(fā)方面的技能。
  
  
• developerWorks Ajax 資源中心：這是有關(guān) Ajax 編程模型信息的一站式中心，包括很多文檔、教程、論壇、blog、wiki 和新聞。任何 Ajax 的新信息都能在這里找到。
  
  
• developerWorks Web 2.0 資源中心，這是有關(guān) Web 2.0 相關(guān)信息的一站式中心，包括大量 Web 2.0 技術(shù)文章、教程、下載和相關(guān)技術(shù)資源。您還可以通過 Web 2.0 新手入門 欄目，迅速了解 Web 2.0 的相關(guān)概念。
  
  
• 查看 HTML5 專題，了解更多和 HTML5 相關(guān)的知識和動(dòng)向。