基于Spark的K-means安全區(qū)間更新優(yōu)化算法

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

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

基于Spark的K-means安全區(qū)間更新優(yōu)化算法

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

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

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

K-means；安全區(qū)間；Spark；大數(shù)據(jù)；時間效率

0 引 言

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

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

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

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

1 K-means安全區(qū)間更新優(yōu)化算法

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

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

1.1 安全距離算法

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

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

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

(1)

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

圖1 安全距離示意圖

(2)

(3)

聯(lián)立式(2)和式(3)：

(4)

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

1.2 安全區(qū)間更新優(yōu)化算法

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

算法1：K-means安全區(qū)間更新優(yōu)化算法。

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

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

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

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

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

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

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

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

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

2 Spark的向量并行計算模型

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

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

2.1 Spark并行計算框架

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

圖2 Spark框架并行模型

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

同時，RDD模型在內(nèi)存中轉(zhuǎn)換，減少了磁盤IO的時間耗費。Spark MLlib模塊優(yōu)化了點到向量的計算模型，大量縮減了Spark上K-means安全區(qū)間更新優(yōu)化算法的執(zhí)行時間。

2.2 Spark MLlib點向量模型

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

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

2.3 基于Spark的K-means安全區(qū)間更新優(yōu)化算法

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

圖3 基于Spark的K-means安全區(qū)間更新優(yōu)化算法并行實現(xiàn)流程

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

算法2：基于Spark的K-means安全區(qū)間更新優(yōu)化算法的并行map算法。

輸入：

輸出：

構(gòu)建全局變量centerList，計算出初始centerList載入待處理數(shù)據(jù)集

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類實現(xiàn)RDD中間數(shù)據(jù)集的combine過程，數(shù)據(jù)集經(jīng)過map過程后會生成大量RDD中間數(shù)據(jù)集，Spark平臺為了不使網(wǎng)絡通信成為瓶頸，會調(diào)用Combiner類在本地(同一節(jié)點)對屬于同一key的value值求平均，精簡得到局部結(jié)果后，再將數(shù)據(jù)傳給主節(jié)點進行處理，減少通信量。Reducer類實現(xiàn)計算節(jié)點局部結(jié)果reduce的過程，匯總合并來自計算節(jié)點的combine過程局部結(jié)果，并用collect()函數(shù)將結(jié)果RDD以數(shù)組的形式返回生成全局結(jié)果。其中每個計算節(jié)點中combine的數(shù)據(jù)點數(shù)量不一，使用計數(shù)器對數(shù)據(jù)點進行統(tǒng)計，得出一個權(quán)值，在reduce計算時使用權(quán)值和局部結(jié)果計算得出全局結(jié)果。

K-means安全區(qū)間更新優(yōu)化算法并行的reduce過程偽代碼如算法3所示。

算法3：并行化的K-means安全區(qū)間更新優(yōu)化算法的reduce算法。

輸入：

輸出：

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

for(kmeans_Vector v:value){

計算value均值，存在temp_average內(nèi)}

將temp_average賦值給value_new

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

context.write(center,value_ new)

end

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

3 實驗與分析

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

3.1 數(shù)據(jù)規(guī)格化

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

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

(5)

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

圖4是原始環(huán)境記錄和規(guī)格化后的對應結(jié)果。

圖4 原始環(huán)境記錄和規(guī)格化后的對應結(jié)果

3.2 效率評估分析

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

(6)

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

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

3.2.1 測試環(huán)境

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

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

3.2.2 算法實現(xiàn)

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

3.2.3 結(jié)果分析

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

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

表1 傳統(tǒng)K-means和優(yōu)化K-means下的算法時間性能

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

表2 傳統(tǒng)K-means和優(yōu)化K-means下的聚類性能對比

4 結(jié)束語

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

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

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

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

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

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

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

[7] 徐新瑞,孟彩霞,周 雯,等.一種基于Spark時效化協(xié)同過濾推薦算法[J].計算機技術(shù)與發(fā)展,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] 張雪鳳,張桂珍,劉 鵬.基于聚類準則函數(shù)的改進K-means算法[J].計算機工程與應用,2011,47(11):123-127.

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

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

[14] 吳哲夫,張 彤,肖 鷹.基于Spark平臺的K-means聚類算法改進及并行化實現(xiàn)[J].互聯(lián)網(wǎng)天地,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 網(wǎng)絡出版時間：2017-07-05

江蘇省農(nóng)業(yè)科技自主創(chuàng)新資金項目(CX(16)1006)

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

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