1 實戰操作了解聚類

    2.了解相似性概念

    3 使用mahout運行一個簡單的聚類實例

    4.用于聚類的各種不同的距離測算方法

      作為人類，我們傾向于與志同道合的人合作—“鳥的羽毛聚集在一起。我們能夠發現重復的模式通過聯系在我們的記憶中的我們看到的、聽到的、問道的、嘗到的東 西。 例如，相比較鹽 ，糖能夠是我們更多地想起蜜。所以我們把糖和蜜的味道結合起來叫他們甜蜜。甚至我們不知道甜蜜的味道，但是知道他跟世界上所有的含糖的東西是相似的，是同 一類的。我們還知道它與鹽是不同類的東西。無意中，我們不同的味道使用了聚類。把糖和鹽做了聚類，每個組有數百個項目。

        在自然界中，我們觀察不同類型的群體。認為猿與猴是同一種靈長類動物。所有的猴子 都有一些性狀如短高度，長尾巴，和一個扁平的鼻子。相反，猿類有較大的尺寸，長長的手臂，和更大的頭。猿看起來不同于猴子，但都喜歡香焦。所以我們可以認 為猿和猴子作為兩個不同的組，或作為一個單一的愛香蕉的靈長類動物群。我們考慮一個集群完全取決于我們選擇的項目之間的相似性測量的特點（在這種情況下， 靈長類動物）。

    在這一章中，從mahout學習的聚類的例子中，我們將會知道聚類是什么，如何有數據概念聯系起來。讓我們從基礎開始吧！

7.1 聚類的基礎

     聚類的過程是怎么樣的呢?假如你可以去有成千上萬的書籍的圖書館。在圖書館內 ，圖書是雜亂無章的。要找到想讀的書必須橫掃所有的書籍，一本一本的才能特定的書。這不僅是繁瑣和緩慢，而且非常枯燥。

     按照標題的字母順序排序會對讀者通過標題尋找有很大的幫助，如果大多數人只是簡單地瀏覽一下，只是找一個大概的主題的書籍呢？這樣通過按照書籍的主題進 行分類要比按照標題的字母順序更有用。但是如何進行分組呢？剛剛接手這份工作，你也不會知道所有的書籍是什么的？是沖浪的、浪漫的，或你沒有遇到過的課 題。

     通過按主題把書籍分類，你不得不把所有書放在同一線上，一本一本的開始閱讀。當你遇到一本書的內容是類似以前的一本書，你就返回去把它們放在在一起。當你完成，你從數千上萬的書中獲取到你要的主題的一堆書。

    干得好！這是你的第一個聚類的經驗。如果一百個主題組太多了，你就得從頭開始和重復剛才的過程獲得書堆，直到你的主題，從另一個堆是完全不同的。

    聚類是所有關于組織項目從一個給定集合成一組類似的項目。在某些方面，這些集群可以被認為是作為項目相似集，但是與其他集群項目不同的。

     聚類集合包含三項

● 算法 ———–這是用來組書籍的方法

           ●相似性和差異性的概念——-一個在前面討論的，依賴于這本書是否屬于已經存在的堆，還是應         該另組新一堆的判斷。     

            ●終止條件———圖書館的例子中，當達到這些書不能堆積起來了，或這些堆已經相當不同的，這就是終止

          在這個簡單的例子中，圈出來的顯然是基于距離三個集群，代表了聚類的結果。圓是一個在聚類方面是一個很好的方法。由于群組通過中心點和半徑來定義的，圓的中心被叫為群重心，或者群平均（平均值），群重心的坐標是類簇中的所有點的x,y軸的平均值

           項目的相似性測量

                                        圖7.1x-y平面圖的點，圓圈代表了聚類，在平面團中的點歸類了單個邏輯群組，聚類算法有益于識別群組

        在本章中，我們將聚類可視化為一個幾何問題。聚類的核心是使用幾何的技術表達不同距離的測算。我們找到一些重要的距離測算法和聚類關系。平面聚類點與文本聚類之間的具體相似性就可以抽象出來。

          在后面的章節中，我們探討了廣泛用于聚類的方法數據，以及mahout 中使用

方法。圖書館的例子是將書分堆直到達到一定閾值的一種策 略。在這個例子中形成的簇的數目取決于數據；基于許多書和臨界值，你可能發現了100后者20，甚至是1個類簇。一個更好的策略是建立目標簇，而不是一個 臨界值，然后找到最好的群組與約束。接下來我們將詳細的介紹目標簇和不同的變量

7.2項目的相似性測量

       聚類的重要問題是找到一方法，通過任何兩個數中的一個數來量化相似性。注意一下我們整片文章中使用的專業術語 ：項目和點，這兩個是聚類數據的單位。

      在X-Y平面的例子，相似性的度量（相似性度量）的分為兩個點之間的歐幾里德距離。圖書館的例子沒有這種清晰的數學手段，而不是完全依賴的智慧館員之間的相似度來判斷書。這工作不在我們的案例，因為我們需要一個度量，可在計算機上實現.

         一個可能的度量是基于兩本書的標題共同含有的詞的數量。基于哈利·波特：哲學家的石頭和哈利·波特這兩本書：阿茲卡班的囚徒中常見的三個詞：哈利、波特、the。即時魔戒也：兩塔是類似于哈利·波特系列，這一措施相似不會捕獲這一切。你需要改變的相似性度量來對書籍本身的內容帳戶。你可以將單詞計數。

         只可惜，說的容易做起來難。這些書不僅有幾百個網頁的文本，而且英語的特點也使的分類方法更加困難。在英語文本中有一些很頻繁的次例如 a,an ,the 等等，它總是經常發生但又不能說明這是這兩本書的相似點。

         為了對抗這種影響，你可以在計算中使用的加權值，并且使用低權重表示這些詞來減少對相似度值的影響。在出現很多次的詞使用低權重值，出現少的用高權重。你可以衡量一個特定的書經常出現的，比如那些強烈建議內容的書籍–類似于魔術類的哈利波特。

       你給書中的每一個單詞一個權重，就能算出這本中的相似性–就是所有詞的詞頻乘以每一個詞的權重的和。如果這兩本書的長度相同，那么這個就是一個比較適當的方法。

   如果一本書有300頁，另一本有1000頁呢？當然書頁大的書的詞也多。

聚類算法

9.1 K-means聚類

K-means需要用戶設定一個聚類個數（k）作為輸入數據，有時k值可能非常大（10,000），這是Mahout閃光的（shines）地方，它確保聚類的可測量性。

為了用k-means達到高質量的聚類，需要估計一個k值。估計k值一種近似的方法是根據你需要的聚類個數。比如100萬篇文章，如果平均500篇 分為一類，k值可以取2000（1000000/500）。這種估計聚類個數非常模糊，但k-means算法就是生成這種近似的聚類。

9.1.1 All you need to know about k-means

下面看一下k-means算法的細節，K-means算法是硬聚類算法，是典型的局域原型的目標函數聚類方法的代表，它是數據點到原型的某種距離作 為優化的目標函數，利用函數求極值的方法得到迭代運算的調整規則。算法采用誤差平方和準則函數作為聚類準則函數。K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。該算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。k個初始類聚類中心點的選取對聚類結果具有較大的。

算法步驟：

（1）隨機選取任意k個對象作為初始聚類中心，初始代表一個簇；

（2）計算點到質心的距離，并把它歸到最近的質心的類；

（3）重新計算已經得到的各個類的質心；

（4）迭代2~3步直至新的質心與原質心相等或小于指定閾值，算法結束。

這種兩步算法是最大期望算法（EM）的典型例子，

第一步是計算期望（E），利用對隱藏變量的現有估計值，計算其最大似然估計值；

第二步是最大化（M），最大化在 E 步上求得的最大似然值來計算參數的值。

M 步上找到的參數估計值被用于下一個 E 步計算中，這個過程不斷交替進行。

9.1.2 Running k-means clustering

K-mean聚類用到KMeansClusterer或KMeansDriver類，前一個是在內存（in-memory）里對節點聚類，后者采用 MapReduce任務執行。這兩種方法都可以就像一個普通的Java程序運行,并且可以從硬盤讀取和寫入數據。它們也可以在hadoop上執行聚類，通 過分布式文件系統讀寫數據。

下面舉例,使用一個隨機點生成器函數來創建一些點。這些點生成矢量格式的點作為一個正態分布圍繞著一個中心。使用Mahout的in-memory K-means 聚類方法對這些點聚類。

創建節點：generateSamples方法，取（1,1）為中心點，標準差為2,400個圍繞著（1,1）的隨機點，近似于正態分布。另外又取了2個數據集，中心分別為（1,0）和（0,2），標準差分別為0.5和0.1。

KMeansClusterer.clusterPoints()方法用到一下參數：

• List<Vector>作為輸入；
• 距離算法DistanceMeasure采用EuclideanDistanceMeasure；
• 聚類的閾值Threshold為0.01；
• 聚類的個數為3；
• 聚類的中心點采用RandomPointsUtil，隨機選取的節點。

Mahout-example里的DisplayKMeans類可以直觀的看到該算法在二維平面的結果，9.2節將介紹運行一個Java Swing application的DisplayKMeans。

如果數據量很大時，應采取MapReduce運行方式，將聚類算法運行在多個機器上，每個mapper得到一個子集的點，每個子集運行一個mapper。這些mapper任務計算出最近的集群作為輸入流。

K-means聚類的MapReduce Job

采用KMeansDriver類的run()方法，需要輸入的參數有：

• Hadoop的配置conf；
• 輸入Vectors的路徑，SequenceFile格式；
• 初始化聚類中心的路徑，SequenceFile格式；
• 輸出結果的路徑，SequenceFile格式；
• 求相似距離時采用的方法，這里采用EuclideanDistanceMeasure；
• 收斂的閾值，沒有超過該閾值的點可移動時，停止迭代；
• 最大迭代次數，這是硬性限制，到達該最大迭代次數時，聚類停止；
• true-迭代結束后聚類；
• true-串行執行該算法，false-并行執行該算法；

public static void run(Configuration conf,Path input,Path clustersIn,Path output,
DistanceMeasure measure,
double convergenceDelta,
int maxIterations,
boolean runClustering,
boolean runSequential)

采用SparseVectorsFromSequenceFile工具，將sequenceFile轉換成Vector，因為K-means算法需要用戶初始化k個質心。