基于Spark的K-means安全區間更新優化算法

李玉波，楊余旺，唐 浩，陳光煒

(1.南京理工大學 計算機科學與工程學院，江蘇 南京 210094；2.普渡大學，印第安納州 西拉法葉 47906)

基于Spark的K-means安全區間更新優化算法

李玉波1，楊余旺1，唐 浩1，陳光煒2

(1.南京理工大學 計算機科學與工程學院，江蘇 南京 210094；2.普渡大學，印第安納州 西拉法葉 47906)

每次K-means算法更新聚類中心后，會對數據集中所有的點迭代計算它們與最新聚類中心的距離，進而獲取點的最新聚類。這種全局迭代計算的特征導致傳統K-means算法時間效率低。隨著數據集增大，算法的時間效率和聚類性能下降過快，因此傳統的K-means算法不適合大數據環境下的聚類使用。針對大數據場景下的時間效率和性能優化問題，提出了一種基于Spark的K-means安全區間更新優化算法。在每次更新聚類中心后，該算法更新安全區間標簽，根據標簽是否大于0每次判斷落在該區間內的全部數據的簇別，避免計算所有點與中心的距離，減少因全局迭代造成的時間和計算資源開銷。算法基于Spark機器MLlib組件的點向量模型優化了模型性能。通過衡量平均誤差準則和算法時間兩個指標，進行了優化K-means與傳統K-means聚類的性能對比實驗。結果表明，所提出的優化算法在上述兩個指標上均優于傳統的K-means聚類算法，適用于大數據環境下的數據聚類場景。

K-means；安全區間；Spark；大數據；時間效率

0 引 言

聚類分析是數據挖掘領域中的重要分析，廣泛應用于網絡入侵檢測、醫學圖像處理、文本檢索、生物信息學等領域[1]。K-means算法是針對具有連續特征屬性的數值型數據進行聚類劃分，因為其較好的伸縮性和簡單的實現方式而被廣泛采用[2]。傳統K-means聚類算法通過不斷迭代與重新計算聚類中心直至收斂進行聚類，具有兩個明顯的制約因素。由于初始聚類中心的隨機性，當算法在完備數據空間進行不完全搜索時，使得局部極值點成為了目標函數的最大值，無法得到全局最優解[3-4]。因此，傳統的K-means算法對初始聚類中心敏感，且每次迭代需要進行全局元素的遍歷。當陷入局部最優解時會造成算法收斂時間過長、計算量增大的問題。隨著數據量的增加，在大數據環境下，傳統聚類算法的收斂時間過長，計算量增加明顯，造成算法時間復雜度較高，執行時間變長，性能下降明顯。

為解決大數據條件下的算法執行時間過長問題，海沫等[5]在并行計算基礎上提出將數據集分散到不同計算引擎的分布式聚類方案，其基本思想是：先在各子節點進行局部聚類，然后主節點對各子節點的局部聚類結果進行全局聚類，進而得到全局聚類模型，最后主節點將全局聚類模型返回各子節點，各子節點根據該模型進行聚類更新。各子節點傳遞給主節點的僅是該節點數據集的部分代表點，存在忽略關鍵點的可能。會造成分布式聚類算法的聚類準確性低于集中式聚類算法。要提高聚類結果準確性，必須為主節點傳遞更多數據。導致增加站點間的通信量造成節點計算量傾斜。因此，分布式聚類算法同樣面臨平衡聚類準確性和時間復雜度的問題。

為解決K-means并行計算中數據偏移的問題，趙衛中等[6]提出使用Hadoop平臺的并行計算引擎進行處理，將聚類中心每次存入HDFS中作為全局變量。雖然能緩解局部極值問題，但是增加了大量的磁盤IO操作，造成算法時間效率過低[7-8]。

為此，提出了一種基于Spark的K-means安全區間更新優化算法。將數據集的點映射到安全區間，每次聚類中心更新后，避免全局迭代計算所有點與聚類中心的距離。僅通過判斷安全區間標簽來確定該區間內所有點的簇別，減少了因進行數據集全局迭代計算產生的時間耗費和性能開銷。算法利用Spark棧MLlib組件的點向量計算模型，優化大數據環境下向量點距離的并行計算模型和過程，進一步優化算法執行時間，減小平均誤差，以提高聚類精度。

1 K-means安全區間更新優化算法

傳統的K-means算法更新聚類中心后，需要迭代計算數據集內所有的點與k個聚類中心之間的距離，并判斷距離點最近的聚類中心，重新劃分點到新簇。這種全局迭代方法由于計算量較大，時間復雜度增長明顯，大數據環境下聚類性能下降很快[2,9]。

K-means的安全區間更新優化算法將點按照其跳轉到其他簇的最近距離，將數據集的點劃分為k個安全區間。每次聚類中心更新后，通過更新安全區間標簽，確定該區間內所有點是否需要變更簇別。標簽小于等于0的安全區間中點被檢出并重新映射對應的安全區間，直到所有點均落在標簽為正數的安全區間，即獲得點對應的簇別。

1.1 安全距離算法

基于Spark的K-means安全區間更新優化算法核心是將數據集中的點按照安全距離映射到各自距離標簽范圍內的安全區間。其中，安全距離是指聚類中心更新后，數據集中的某點仍然能夠保持在原聚類簇中的最小偏差值，即從原簇跳轉到距離該點最近的另一個簇需要變更的最小距離。安全區間是指能夠容納這些安全距離的連續區間，其標簽為區間的終點值。

如圖1所示，以3-簇為例，該數據集的聚類中心分別為C0,C1,C2，且P是原屬于C0簇的某點，P到各聚類中心的距離分別記為dPC0，dPC1，dPC2。點P要從原C0簇跳轉到C1或C2，至少移動的距離為：

Δp=min(dPC1-dPC0,dPC2-dPC0)

(1)

其中，Δp為點P留在C0簇的安全距離。即，當聚類中心移動Δf后，只要偏移后仍滿足Δp-Δf>0，則點P簇別不會發生變化。同理，將數據集中所有滿足該關系的點映射到一個安全距離區間，標記為Δp。當經過K-means算法迭代，聚類中心發生變更后，只需檢驗對應的安全區間標簽是否滿足Δp-Δf>0，可按組將安全區間內的點是否發生簇別變更全部檢出。

圖1 安全距離示意圖

(2)

(3)

聯立式(2)和式(3)：

(4)

要使安全區間標簽更新后區間內的點仍留在原簇，區間內點的安全距離要滿足式(4)。

1.2 安全區間更新優化算法

按數據集中點的安全距離可以將所有的點映射到不同的安全區間。K-means更新聚類中心后，用新聚類中心相對原聚類中心的最大偏移量更新安全區間的標簽，以實現同時對整個區間內的所有點簇別的更新，減少迭代后的距離計算次數。算法流程如下：

算法1：K-means安全區間更新優化算法。

(1)定義一個常量WIDTH作為區間長度。

(2)定義一系列區間Ii=[i*WIDTH,(i+1)*WIDTH]，并將它們的標簽記為i*WIDTH。其中i為連續的正整數。

(3)選擇k個聚類中心。

(4)對于數據集中的每個點，計算安全跳轉距離Δp=min(dPCl-dPCs)。其中，Cs為距離該點最近的中心，Cl為其他的簇中心，s=1,2,…,K且s≠l。

按i*WIDTH<Δp<(i+1)*WIDTH將所有的點映射到步驟(2)中的區間i*WIDTH中。

(6)使用聚類中心移動的距離D更新區間Ii的標簽。對所有的區間標簽減去2*D，即將區間內的值向邊界靠近2*D距離。

(7)檢出那些區間標簽小于或等于0的點，并返回步驟(4)，直到所有的點都被檢出。

與傳統聚類算法不同的是，優化算法將所有的點按安全距離映射到安全區間，每次更新聚類中心后，只更新對應的區間標簽即可檢出區間全部點的簇別，減少了簇內點距離計算和比較造成的時間開銷，提高了算法的時間效率。

設數據集含x個點，更新聚類中心的次數為n，將所有點聚為k簇，則傳統K-means聚類方法的時間復雜度為O(x*n*k)[10-11]，安全區間更新優化K-means算法的時間復雜度為O(x/k*n)。相比傳統K-means聚類算法，大數據集下，傳統K-means的時間復雜度過高。優化算法在大數據量下，時間復雜度相對減少k2倍。

2 Spark的向量并行計算模型

基于Spark的K-means安全區間更新優化算法旨在優化大數據環境下的算法時間復雜度。傳統K-means算法在每次迭代獲取聚類中心后，需要全局迭代計算和比較數據集內的所有點與聚類中心的距離，以獲取所有點的最新簇別。當數據集擴充到大數據環境下時，按照時間復雜度O(x*n*k)計算，其時間開銷過高。尤其是大數據環境下容易陷入局部極值，此時，算法時間成倍增加，性能下降很快。

在改進K-means算法數據點簇別計算方式的基礎上，基于Spark MLlib解決大數據量的并行迭代計算能力，提高數據點距離模型計算效率。在使用安全區間更新優化K-means聚類算法同時，通過Spark框架的并行計算能力和MLlib模塊對向量集計算的優化機制，提高大數據集的K-means聚類計算效率。

2.1 Spark并行計算框架

Spark是一種融合了批處理、流處理、迭代式計算等獨立分布式系統功能的并行計算框架。數據輸入輸出使用RDD(彈性分布式數據集，Resilient Distributed Datasets)抽象出橫跨多個物理節點的數據集合，方便了并行的數據處理過程，改善了大數據環境下的并行計算效率[12-13]。Spark框架并行模型如圖2所示。

圖2 Spark框架并行模型

利用Spark框架在大數據分布式內存計算的優勢，在Spark框架下實現優化的K-means算法，充分提高安全區間更新優化K-means算法在大數據下的并行執行效率。如圖2所示，大數據集被存入分布式文件系統HDFS后，抽象成RDD數據模型，并分配到A/C中的多個物理節點，由多個計算引擎并行執行map和flatmap計算[14-15]，并將一輪聚類結果輸入到不同RDD，并利用寬依賴進行RDD的轉換。假設物理節點數為t，則該優化算法在Spark框架下的時間復雜度至少降低到O(x/k*n/t)。

同時，RDD模型在內存中轉換，減少了磁盤IO的時間耗費。Spark MLlib模塊優化了點到向量的計算模型，大量縮減了Spark上K-means安全區間更新優化算法的執行時間。

2.2 Spark MLlib點向量模型

使用Spark MLlib組件對K-means聚類算法進行了優化。在訓練模型與預測模型兩部分中，利用分布式MLlib向量均值計算，快速獲取簇的聚類中心，避免陷入局部極值點，并使用內置誤差平方和計算獲取算法性能指標等。

使用Spark MLlib對K-means算法的優化基于向量數據模型(Vector)實現。向量和矩陣運算使用Breeze庫的Vector/Matrix類型實現。計算中，Spark將分布式存放在不同節點上的聚類數據文件抽象成RDD模型，使用MLlib模塊按行讀取記錄，將所有元素從文本數據轉換為浮點數并map操作后形成新的RDD模型。RDD中每行記錄作為數據點(a1,a2,…,an)被抽象為n維稠密向量模型。數據集中的點被抽象成空間向量進行聚類計算。由于Spark的并行計算特征，向量計算在Spark框架下存在更多的優勢。

2.3 基于Spark的K-means安全區間更新優化算法

基于Spark的K-means安全區間更新優化算法，其并行化實現主要由Driver類、Mapper類、Combiner類以及Reducer類組成。算法流程如圖3所示。

圖3 基于Spark的K-means安全區間更新優化算法并行實現流程

Driver類初始化安全區間更新優化算法，通過setMapper(),setCombiner()和setReducer()驅動Mapper類、Combiner類和Reducer類，在相應類中實現map,combine和reducebykey操作函數對數據集進行處理。Spark MLlib通過textFile()將數據集作為一個RDD加載到Spark中，并用addFile函數拷貝共享數據到集群中的每個節點。Mapper類實現數據集的map過程，構建全局變量聚類中心點鏈表centerList，將數據集進行分類。通過map函數逐行掃描計算數據集中的數據對象RDD，將數據對象映射到對應的安全區間，最終輸出鍵值對。其中key為數據對象，value為在該聚類中心所在聚類中的安全區間。迭代計算中間數據使用cache()函數轉化為RDD。算法map過程偽代碼如算法2所示。

算法2：基于Spark的K-means安全區間更新優化算法的并行map算法。

輸入：

輸出：

構建全局變量centerList，計算出初始centerList載入待處理數據集

for(Vectorscluster:centerList){

val distance=cluster.getV2().dist(value)

If(distance

min=distance;nearest_cluster=cluster. map(parseVector(_)).cache()

}}

key_new=nearest

clustercontext.write(key_new,value)

end

Combiner類實現RDD中間數據集的combine過程，數據集經過map過程后會生成大量RDD中間數據集，Spark平臺為了不使網絡通信成為瓶頸，會調用Combiner類在本地(同一節點)對屬于同一key的value值求平均，精簡得到局部結果后，再將數據傳給主節點進行處理，減少通信量。Reducer類實現計算節點局部結果reduce的過程，匯總合并來自計算節點的combine過程局部結果，并用collect()函數將結果RDD以數組的形式返回生成全局結果。其中每個計算節點中combine的數據點數量不一，使用計數器對數據點進行統計，得出一個權值，在reduce計算時使用權值和局部結果計算得出全局結果。

K-means安全區間更新優化算法并行的reduce過程偽代碼如算法3所示。

算法3：并行化的K-means安全區間更新優化算法的reduce算法。

輸入：

輸出：

初始化一個kmeans_Vector類型的average來存儲新的中心點

for(kmeans_Vector v:value){

計算value均值，存在temp_average內}

將temp_average賦值給value_new

if(安全區間標簽不小于0)

context.write(center,value_ new)

end

基于Spark MLlib組件的Vector向量模型和基礎聚類功能，將要進行K-means安全區間更新優化聚類的大數據集加載到RDD，在多個物理工作節點上進行算法的并行計算，進一步提高算法的數據處理時間，適應于大數據下的使用場景。

3 實驗與分析

實驗使用數據來源于田間環境監測數據。環境傳感器部署到江蘇省農業科學院信息技術研究所的實驗基地，采集觀測點的光照，空氣溫濕度和土壤溫濕度數據。數據以“編號|光照量|空氣溫度|空氣濕度|土壤溫度|土壤濕度|結束位”的形式實時上傳到大數據中心，最終存入大數據倉庫Hive進行分析處理。通過Spark框架將數據文件進行RDD抽象，加載為浮點數并規格化，基于MLlib模塊的向量模型，把數據記錄映射為空間點向量并進行聚類，分析誤差等。實驗把環境數據記錄分為3類氣象特征，并觀測對應特征下的作物生長情況，以指導作物科學種植。

3.1 數據規格化

算法測試數據來源于環境傳感器，每條環境數據記錄被作為一個點向量，光照和溫濕度被作為點向量的屬性。使用誤差評價函數作為算法性能指標。由于光照量、溫濕度等指標的單位和數值相差較大，模型計算結果容易受到離群值和較大方差的特征影響。因此，在訓練聚類模型之前，需要對特征屬性進行歸一化和標準化。通過對不同屬性歸一化，將數據保持在[0,1]之間進行精度控制，簡化模型計算。

設某屬性規格化之前為ai，規格化時考慮所有記錄中該屬性值的數值區間長度，并按式(5)對該屬性進行規格化。

(5)

實驗數據中共有5個環境屬性值指標。其中，光照數值范圍為0～10 000 Lux，空氣和土壤溫度數值范圍為0℃～90 ℃，而空氣和土壤濕度數值范圍均為0%～100%。由于一條記錄中存在5個不同屬性數值范圍和計算單位，在進行聚類時，數值范圍較大的光照量會產生較大方差影響模型訓練。將所有記錄屬性進行規格化處理，提高模型訓練的準確性，避免離群值和較大方差屬性的影響。

圖4是原始環境記錄和規格化后的對應結果。

圖4 原始環境記錄和規格化后的對應結果

3.2 效率評估分析

將圖4規格化后的數據作為向量輸入到基于Spark的K-means安全區間更新優化算法，進行聚類效果檢測。使用平均誤差準則函數和聚類完成的時間耗費作為聚類效果的評估依據。其中，平均誤差準則是指每次選好中心點后進行的偏移量，數值大小與聚類效果成反比[16]，計算公式為：

(6)

其中，xi表示數據集中某點；ck表示該點所屬類別的中心點。

這種計算點與聚類中心方差和的評估方法稱為WCSS(Within_Cluster Sum of Squares)。

3.2.1 測試環境

使用Intel i7處理器，8 GB內存作為物理機，使用VMWare作為虛擬機搭建Spark集群，集群的操作系統使用Linux開源版本的CentOS。Spark框架使用Spark-1.4.0-Hadoop-2.6.0。Spark的數據源來自Hadoop的分布式文件系統模塊HDFS進行文件存儲。

Spark框架從集群角色上，將虛擬機分為負責作業調度的Nimbus和負責任務執行的Workers，分別使用一個VMWare虛擬機實現。算法數據計算基于Spark MLlib的SparkContext，創建分布式的RDD數據集，將HDFS上的傳感器數據文件通過textFile()函數加載到內存中，跨越多個物理節點進行聚類運算。

3.2.2 算法實現

基于Spark的K-means安全區間更新優化算法將規格化后的環境數據記錄抽象為包含光照、溫濕度等屬性的空間點向量，輸入MLlib進行向量運算。算法使用Spark的MLlib模塊作為向量運算的模型基礎，通過并行計算向量屬性，可以快速獲取多個簇中集群的中心，避免了單機操作中串行的點計算過程。此外，MLlib提供了快速計算平均誤差準則WCSS的API，優化了向量計算的底層數據模型，相比單機下使用Java等模型或普通浮點數模型計算效率更高。將環境數據無監督地聚為3簇，以用于歸納不同氣象特征的數據，研究對應的作物生長狀態。

3.2.3 結果分析

從直觀的聚類結果圖可以發現，原始環境數據的簇別被設置為0。改進K-means算法和傳統K-means算法相比，聚類準確性方面，主要在于將傳統K-means算法簇0的記錄表現為簇1和簇2。偏差記錄數量較少，絕大部分數據記錄線重合，表明改進K-means算法對聚類準確性影響較小。

如表1和表2所示，基于Spark的K-means安全區間更新優化算法在平均誤差準則上，隨著聚類記錄數快速增加，其變化較小。表明優化K-means算法在聚類效果上與傳統K-means算法有相似的準確性。

表1 傳統K-means和優化K-means下的算法時間性能

如表1和表2所示，在記錄數為425，850和1 700條時，優化算法時間耗費分別占傳統K-means的26.6%，15.6%和10%。因此，提出的基于Spark的K-means安全區間更新優化算法與傳統K-means算法相比，在聚類準確性和聚類效果上，具有基本相似的聚類效果。在時間耗費上，具有明顯的時間優勢，且隨著數據量增大，時間優勢更加明顯。

表2 傳統K-means和優化K-means下的聚類性能對比

4 結束語

為了解決大數據環境下K-means時間復雜度過大的問題，提出了基于Spark的K-means安全區間更新優化算法。與傳統K-means算法相比，該算法避免了全局迭代計算點與聚類中心的距離，而將所有的點映射到安全區間，每次更新聚類中心后只需更新安全區間的標簽即可更新區間內所有點的簇別，提高了聚類時全局的距離迭代計算效率，減少了時間復雜度。利用Spark的MLlib組件的向量并行計算模型，對大數據集進行RDD分布式數據處理，加快了算法對數據的處理時間。調用MLlib的WCSS函數和向量簇中心API，快速實現簇內計算。實驗結果表明，隨著傳感器數據量的快速增加，優化算法保證了聚類準確性并具有明顯的時間優勢。

[1] 吳夙慧,成 穎,鄭彥寧,等.K-means算法研究綜述[J].現代圖書情報技術,2011(5):28-35.

[2] 李 梓,于海濤,賈美娟.基于改進模擬退火的優化K-means算法[J].計算機工程與應用,2012,48(24):77-80.

[3] 袁 方,周志勇,宋 鑫.初始聚類中心優化的k-means算法[J].計算機工程,2007,33(3):65-66.

[4] 謝娟英,王艷娥.最小方差優化初始聚類中心的K-means算法[J].計算機工程,2014,40(8):205-211.

[5] 海 沫,張書云,馬燕林.分布式環境中聚類問題算法研究綜述[J].計算機應用研究,2013,30(9):2561-2564.

[6] 趙衛中,馬慧芳,傅燕翔,等.基于云計算平臺Hadoop的并行k-means聚類算法設計研究[J].計算機科學,2011,38(10):166-168.

[7] 徐新瑞,孟彩霞,周 雯,等.一種基于Spark時效化協同過濾推薦算法[J].計算機技術與發展,2015,25(6):48-55.

[8] 虞倩倩,戴月明,李晶晶.基于MapReduce的ACO-K-means并行聚類算法[J].計算機工程與應用,2013,49(16):117-120.

[9] Poteras C M,Mihaescu M C,Mocanu M.An optimized version of the K-Means clustering algorithm[C]//Computer science and information systems.[s.l.]:IEEE,2014:695-699.

[10] Brusco M J,Cradit J D.A variable-selection heuristic for k-means clustering[J].Psychometrika,2001,66(2):249-270.

[11] 張雪鳳,張桂珍,劉 鵬.基于聚類準則函數的改進K-means算法[J].計算機工程與應用,2011,47(11):123-127.

[12] 陳僑安,李 峰,曹 越,等.基于運行數據分析的Spark任務參數優化[J].計算機工程與科學,2016,38(1):11-19.

[13] 梁 彥.基于分布式平臺Spark和YARN的數據挖掘算法的并行化研究[D].廣州:中山大學,2014.

[14] 吳哲夫,張 彤,肖 鷹.基于Spark平臺的K-means聚類算法改進及并行化實現[J].互聯網天地,2016(1):44-50.

[15] Gopalani S,Arora R.Comparing apache spark and map reduce with performance analysis using k-means[J].International Journal of Computer Applications,2015,113(1):8-11.

[16] 韓凌波,王 強,蔣正鋒,等.一種改進的k-means初始聚類中心選取算法[J].計算機工程與應用,2010,46(17):150-152.

Optimization ofK-means Updating Security Interval Based on Spark

LI Yu-bo1，YANG Yu-wang1，TANG Hao1，CHEN Guang-wei2

(1.School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China；2.Purdue University,West Lafayette 47906,USA)

At each time when theK-means algorithm updates the cluster center,it needs to calculate iteratively the distance between all the points in the dataset with the latest clustering center to get the latest clustering of each point.This feature of global iterative computation leads to low efficiency of traditionalK-means algorithm.As the data set increases,its time efficiency and clustering performance decrease too fast,so that the traditionalK-means algorithm is not suitable for clustering in big data.Therefore,a newK-means secure interval updating algorithm based on Spark is proposed for time efficiency and performance optimization in big data.After updated the cluster center every time,it updates security interval label.According to whether the label is greater than 0 instead of calculation of the distance between all the points and the new center and cluster identification of all the data in the interval every time,which reduces the overhead of time and computation.The performance of the algorithm model based on the point vector model of Spark MLlib component has been optimized.It is made a comparison with the traditionalK-means algorithm on average error criterion and operation time.The experimental results show that it is superior to the traditionalK-means clustering algorithm in the above two indexes and is suitable for data clustering scenario in big data.

K-means;security interval;Spark;big data;time efficiency

2016-09-29

2016-12-29 網絡出版時間：2017-07-05

江蘇省農業科技自主創新資金項目(CX(16)1006)

李玉波(1991-)，男，碩士研究生，研究方向為大數據應用；楊余旺，博士，教授，博士生導師，研究方向為網絡編碼、大數據應用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1652.072.html

TP301

A

1673-629X(2017)08-0001-06

10.3969/j.issn.1673-629X.2017.08.001