基于MapReduce的聚類算法相似性度量分析研究

摘 要：相似性度量在聚類算法設計中起關鍵作用，使用合適的距離度量函數能夠反映數據對象間的相似性。本文對聚類算法中數據對象間相似性度量的特征進行了系統性歸納總結，通過MapReduce編程模型實現對各種相似性度量聚類算法的實驗比較分析，將為聚類分析研究者提供參考。

關鍵詞：聚類；相似性度量；MapReduce

中圖分類號：TP311.13；TP391.1 文獻標識碼：A 文章編號：2096-4706（2018）11-0010-03

Research on Similarity Measurement Analysis of

Clustering Algorithm Based on MapReduce

PENG Tianhao，PAN Youshun，YANG Shenglin

（Moutai Institute，Department of Brewing Engineering Automation，Renhuai 564507，China）

Abstract：The similarity measure plays a key role in clustering algorithms. Using appropriate distance measure function can reflect the similarity between data objects. This paper aims to conduct a systematic summary on data objects similarity measure in clustering algorithms. The paper will also implement comparative analysis on various similarity measure clustering algorithms by MapReduce programming model，which can provide references to researchers on clustering algorithms.

Keywords：clustering；similarity measure；MapReduce

0 引 言

聚類分析的研究已有很長歷史，是數據挖掘、模式識別等方面的重要研究內容之一，已經廣泛應用于電子商務、圖像識別、文本分類、Web搜索及生物信息等領域。聚類是一個把數據對象劃分成子集的過程[1]，是一個無監督的分類[2]，在數據對象分類分組中發揮著重要作用，分類后同一個類中的數據對象盡可能相似，不同類中數據對象盡可能相異。典型的聚類分析過程包括如下三個步驟。

第一，特征選擇和特征提取。特征選擇是指從原始數據集中，選擇質量好最有效的特征，以此作為進一步分析的數據對象。特征提取是指在特征選擇基礎上，通過對已經選擇好的特征進行某種轉換后產生的突出特征。該步驟非常重要，能夠提升聚類算法的執行效率，特別是在對復雜數據和高維數據進行聚類時更能突顯其重要性。

第二，聚類算法設計。選擇合適的聚類算法進行聚類，聚類算法要給出具體的數據對象間距離度量函數及構建相應的目標函數，根據實際應用來選擇確定距離度量函數，這 將直接影響聚類效果。

第三，聚類結果評估。因為不同的聚類算法將產生不同的聚類結果，即使是同一聚類算法，參數設置不同也會產生不同的聚類結果，因此如果要評估聚類結果，則主要通過三種方法：外部指標評估、內部指標評估、相關性指標評估。

聚類算法設計是聚類分析過程的核心步驟，使用合適的距離度量函數將反應數據對象間的相似性，相似性度量問題在聚類算法設計中起關鍵作用。本文將介紹一些常用的相似性度量方法，并從距離和相似系數兩方面對其進行論述，其中距離用來度量樣本之間的相似性，而相似系數用來度量變量之間的相似性，并通過數據測試進行對比，從而得出相關結論。

1 聚類算法中的相似性度量分析

1.1 明考斯基距離

設論域X={x1，x2，…，xn}為被分類的n個數據對象，每個數據對象又由p個指標組成，其中第i個數據對象表示為如下形式：

xi={xi1，xi2，…，xip} （i=1，2，…，n）

用d（xi，xj）來表示第i個數據對象xi與第j個數據對象xj之間的距離。明考斯基（Minkowski）距離表示如下：

1.1.1 歐氏距離

以上公式（1）中，當q=2時為歐氏距離，即：

歐式距離是一種幾何距離，反應數據對象在空間的絕對距離，可用于檢測特征空間中球形超球體結構數據對象的相似性度量分析。

1.1.2 曼哈頓距離

以上公式（1）中，當q=1時為曼哈頓距離，即：

用于檢測特征空間中菱形超立方體結構數據對象的相似性度量分析。

1.1.3 切比雪夫距離

以上公式（1）中，當q=∞為切比雪夫距離，即：

可用于檢測特征空間中矩形超立方體結構，主要表現為在多維空間中，數據對象從一個位置移動到另一個數據對象所要行走的最短距離。

從以上幾個比較典型的距離公式可知，明考斯基距離的基本思想就是利用數據對對象各個指標值之間的絕對差異進行分類，操作簡單明了，可以證明滿足距離的4條基本公理，具體如下：

（1）非負性：d（xi，xj）≥0；

（2）d（xi，xj）=0，當且僅當xi=xj；

（3）對稱性：d（xi，xj）=d（xj，xi）；

（4）三角不等式：d（xi，xj）≤d（xi，xk）+d（xk，xj）。

但是在明考斯基距離計算的過程中，將數據對象各分量的“單位”同等對待，沒有區分處理，沒有考慮各分量分布的差異性等。加權的明考斯基距離是根據每一個分量的重要性賦予一個權重，使聚類效果更好，但其沒有體現分量間的相關性。

1.2 馬氏距離

在樣本集中，樣本xi和樣本xj之間的馬氏距離定義為：

其中Σ為樣本對應的協方差矩陣，計算過程相對比較復雜：

其中：。

馬氏距離是一種有效地計算兩個位置樣本集的相似度方法，表示數據的協方差距離[3]，消除了量綱不同對對象聚類分析的影響，排除了變量之間的相關性的干擾，較好地避免發生一致性聚類問題，但是馬氏距離最大的問題就是Σ不易確定，容易導致馬氏距離效果不理想。

1.3 蘭氏距離

如果樣本數據的各指標取值均大于零，即xik≥0時，可以定義樣本xi和樣本xj之間的蘭氏距離為：

蘭氏距離對大的異常值不敏感，特別適合用高度傾斜的數據來評估距離度量，其與明考斯基距離有部分相同的特點，如奇異值影響小、沒有考慮變量間相關性等。

1.4 夾角余弦

設兩個p維向量樣本點xi和xj，xi和xj之間的相似程度可以用夾角余弦來度量，具體如下：

很明顯就可以看出夾角余弦的取值范圍是[-1，1]，可以用圖1比較直觀地說明夾角大小與夾角余弦值之間的關系，空間中A點和B點的夾角越小相應的夾角余弦值就越大，反之越小。從圖中還可以進一步比較歐氏距離與夾角余弦距離之間的區別，即歐氏距離的值是指A點和B點之間的絕對距離，其值大小與A點和B點所在空間位置坐標直接相關；而余弦距離指的是空間向量的夾角大小，體現在方向的差異上，而不是具體位置。

1.5 杰卡德系數

根據杰卡德（Jaccard）的相似度原理，文本數據對象A和B的Jaccard相似度等于其交集除以其并集，取值范圍在[0，1]之間，當數據對象A和B相同時取值為1，數據對象A和B交集為空時取值為0，Jaccard相似度值越大，樣本相似度越高，反之亦然。

1.6 相關系數

變量xi和xj的相關系數為：

其取值范圍在[-1，1]之間，絕對值越大，說明變量之間的相關度就越好。變量xi和xj的距離通過以上相似系數來定義：

1.7 高斯相似度

樣本xi和xj的高斯相似度計算公式如下：

高斯相似函數常用于譜聚類算法中，用來計算空間數據點之間的相似度，其值越小距離越大。

2 MapReduce編程模型

MapReduce是Google公司推出的能夠并發處理大規模數據的并行編程模型，在具體編程中無須考慮底層的實現細節，這在一定程度上降低了編程難度，是當前云計算平臺使用較多的并行數據處理模型。MapReduce編程模型的基本思想是，將大規模數據集分解成若干個數據塊splits，由集群中的相應節點并行執行Map計算任務，得到相應的一系列中間結果（key，value），再將這些中間結果作為Reduce的輸入，并行執行Reduce計算任務，形成最終結果，計算過程如圖2所示。

3 實驗分析

本文通過4臺普通計算機搭建的Hadoop集群系統完成實驗，其中1臺計算機作為NameNode服務節點，另外3臺作為DateNode服務節點。實驗數據來源于UCI數據集，可以通過官網直接下載。本實驗采用UCI數據庫中的Wine數據集，其數據維度較高，共由178個樣本組成，分為三類，每個樣本包含13個特征屬性。實驗使用k-means算法，距離度量方式分別以歐式距離和馬氏距離為代表，用Java編程實現。通過實驗，在本算法中Wine數據集采用馬氏距離的聚類精度明顯優于歐氏距離。具體使用什么距離度量方式需要根據實際應用來確定，如數據集的大小、數據維度的大小、數據類型等，不能簡單地定義哪一種度量方式更好。

4 結 論

當前，有關聚類分析的改進算法研究比較多，應用也比較廣泛，并取得了較好的效果。本文重點介紹了聚類算法中數據對象間的相似性度量，有距離度量和相似系數度量兩種方式，并介紹了一些常用的度量公式，從本身特點和應用等方面對其進行了簡單的比較，較全面地分析了其優點、難點及不足等，通過實驗介紹了聚類算法相似性度量的MapReduce并行化實現。本文意在為系統學習聚類分析中的相似性度量分析提供較好的參考價值。

參考文獻：

[1] JiaWeiHan，MichelineKamber，Jian Pei.范明，孟曉峰，譯.數據挖掘概念與技術 [M].北京：機械工業出版社，2012.

[2] 孫吉貴，劉杰，趙連宇.聚類算法研究 [J].軟件學報，2008（1）：48-61.

[3] 蔡靜穎.模糊聚類算法及應用 [M].北京：冶金工業出版社，2015.

[4] 何曉群.多元統計分析 [M].第4版.北京：中國人民大學出版社，2015.

[5] 邱宜寧.相似性度量對聚類性能的影響 [J].信息與電腦（理論版），2012（12）：116-119.

[6] 白雪.聚類分析中的相似性度量及其應用研究 [D].北京：北京交通大學，2012.

[7] 代明，鐘才明，龐永明，等.基于數據集屬性相似性的聚類算法推薦 [J].南京大學學報（自然科學），2016，52（5）：908-917.

[8] 李濤，汪光陽.標準相似性度量及其應用 [J].山西師范大學學報（自然科學版），2016，30（4）：29-33.

[9] 蔡靜穎，謝福鼎，張永.基于馬氏距離特征加權的模糊聚類新算法 [J].計算機工程與應用，2012，48（5）：198-200.

[10] 王麗娟，關守義，王曉龍，等.基于屬性權重的Fuzzy CMean算法 [J].計算機學報，2006（10）：1797-1803.

[11] 江小平，李成華，向文，等.k-means聚類算法的Map Reduce并行化實現 [J].華中科技大學學報（自然科學版），2011，39（S1）：120-124.

[12] 覃雄派，王會舉，杜小勇，等.大數據分析——RDBMS與MapReduce的競爭與共生 [J].軟件學報，2012，23（1）：32-45.

作者簡介：彭天昊（1982-），男，漢族，貴州桐梓人，副教授，碩士。主要研究方向：數據與知識工程；潘有順（1977-），男，漢族，江蘇淮安人，高級工程師，碩士。主要研究方向：網絡技術、物聯網；楊勝林（1985-），男，侗族，貴州石阡人，講師，碩士。主要研究方向：機械結構設計與CAE。