趙明明 張桂蕓 潘冬寧 王蕊

摘 要：隨著如今數(shù)據(jù)量的爆發(fā)式增長(zhǎng)，傳統(tǒng)的數(shù)據(jù)挖掘方法已經(jīng)遠(yuǎn)遠(yuǎn)不能滿足人們需求，K-means聚類作為一種經(jīng)典的聚類算法，其應(yīng)用領(lǐng)域很廣。但是K-means算法在隨機(jī)選取初始聚類K個(gè)中心時(shí)，容易使聚類結(jié)果不穩(wěn)定，因此提出基于核函數(shù)的K-means聚類算法。與此同時(shí)，結(jié)合MapReduce分布式框架對(duì)改進(jìn)后的K-means聚類算法作分布式計(jì)算。研究結(jié)果表明，基于高斯核函數(shù)的K-means聚類在分布式下的計(jì)算能夠加速K-means聚類過(guò)程，且結(jié)果優(yōu)于單獨(dú)基于核密度估計(jì)的K-means算法。

關(guān)鍵詞：高斯核函數(shù)；K-means聚類；核密度；分布式

DOI：10.11907/rjdk.172480

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）004-0064-03

Abstract：With the explosive increase of data， the traditional data mining has been far from being enough to meeting the needs of people. K-means clustering is a classical clustering algorithm， and its application field is very extensive. However， when the K-means algorithm randomly selects the initial clustering K centers， it is easy to make the clustering results unstable. Therefore， this paper proposes a K-means clustering algorithm based on kernel function. In this paper， the MapReduce distributed framework is used to do the distributed calculation of the improved K-means clustering algorithm. The results show that K-means clustering based on Gaussian kernel function can accelerate the process of K-means clustering in distributed calculation， and the result is better than K-means algorithm solely based on kernel density estimation.

Key Words：Gaussian kernel function； K-means clustering； distributed

0 引言

隨著科技的迅速發(fā)展，在工業(yè)、商業(yè)、醫(yī)療、工程、航天等各個(gè)領(lǐng)域產(chǎn)生了大量數(shù)據(jù)，數(shù)據(jù)規(guī)模已經(jīng)從先前的GB上升到TB、PB乃至EB和ZB。據(jù)統(tǒng)計(jì)，在2020年全世界的數(shù)據(jù)規(guī)模將達(dá)到40ZB，相當(dāng)于平均每人擁有5 247G的數(shù)據(jù)。因此，如何處理和管理如此龐大的數(shù)據(jù)是一項(xiàng)相當(dāng)艱巨的任務(wù)，在數(shù)據(jù)量日益暴漲的場(chǎng)景下對(duì)客戶的精準(zhǔn)推薦服務(wù)也面臨著嚴(yán)峻考驗(yàn)。為了能夠從數(shù)據(jù)中獲取有價(jià)值的信息，各公司開(kāi)始對(duì)龐大的數(shù)據(jù)進(jìn)行挖掘與分析。

K-means聚類算法是數(shù)據(jù)挖掘領(lǐng)域最重要的經(jīng)典算法之一，與其它數(shù)據(jù)挖掘方法相比，聚類不需要先驗(yàn)知識(shí)即可完成數(shù)據(jù)的分類。聚類算法可以分為基于劃分、密度、模型等多種類型[1]。然而在面對(duì)大規(guī)模數(shù)據(jù)時(shí)，K-means算法表現(xiàn)不夠理想，并且在初選K值時(shí)非常困難。針對(duì)K-means的聚類數(shù)目K值難以確定和高維大數(shù)據(jù)集上的運(yùn)算效率問(wèn)題，本文設(shè)計(jì)了一種新型聚類算法，并且提出一種基于高斯核函數(shù)的K-means聚類在分布式下的優(yōu)化算法。核函數(shù)估計(jì)又稱為核密度估計(jì)（Kernel Density Estimate，KDE），是一種非參數(shù)估計(jì)方法，不需要預(yù)知數(shù)據(jù)集分布，是一種在未知數(shù)據(jù)集分布情況下進(jìn)行聚類的有效方法。因此，可以采用核函數(shù)估計(jì)的方法處理高維度數(shù)據(jù)。另外Hadoop上的MapReduce框架能夠快速、準(zhǔn)確、高效地處理大量數(shù)據(jù)，所以采用MapReduce框架又可以解決在單機(jī)上運(yùn)行效率低的問(wèn)題。本文提出將建立好的模型運(yùn)用在MapReduce分布式框架下運(yùn)行。實(shí)驗(yàn)結(jié)果表明，該方法在不影響聚類結(jié)果的情況下，有效縮短了聚類過(guò)程所需的時(shí)間。

1 核函數(shù)估計(jì)

在給定樣本集合求解隨機(jī)變量的分布密度函數(shù)時(shí)會(huì)經(jīng)常用到兩種估計(jì)，分別是參數(shù)估計(jì)和非參數(shù)估計(jì)。由于參數(shù)模型的缺陷，Rosenblatt和Parzen提出了非參數(shù)估計(jì)方法，即核密度估計(jì)方法。由于核密度估計(jì)方法不利用有關(guān)數(shù)據(jù)分布的先驗(yàn)知識(shí)，對(duì)數(shù)據(jù)分布不附加任何假定，是一種從數(shù)據(jù)樣本本身出發(fā)研究數(shù)據(jù)分布特征的方法，因而在統(tǒng)計(jì)學(xué)理論和應(yīng)用領(lǐng)域均受到高度重視[2]。

總體而言，核函數(shù)就是將輸入空間映射到高維的特征空間，然后再在高維的數(shù)據(jù)空間進(jìn)行數(shù)據(jù)處理。這種映射是非線性變換的，才能將輸入空間映射出不同特征的高維空間。

其中，fh（x）稱為密度函數(shù)f（x）的核密度估計(jì)；K（·）稱為核函數(shù)；h通常稱為窗寬或光滑參數(shù)，是一個(gè)預(yù)先給定的正數(shù)。

通過(guò)以上定義可以得出，分布密度函數(shù)的核密度估計(jì)f不僅與給定的數(shù)據(jù)樣本集有關(guān)，還與核函數(shù)的選擇與窗寬參數(shù)h的選擇有關(guān)[3]。理論上而言，窗寬h隨著n的增大而減小，即當(dāng)n趨近于∞時(shí)，h趨近于0。如果h取值較大，然后x經(jīng)過(guò)壓縮變換xi-xh后，突出了平均化，密度細(xì)節(jié)則會(huì)被淹沒(méi)，使估計(jì)出來(lái)的密度曲線過(guò)于平穩(wěn)，導(dǎo)致結(jié)果分辨率過(guò)低；如果窗寬h值太小，隨機(jī)性的影響則會(huì)變大，從而形成一種非常不規(guī)則的曲線，導(dǎo)致密度的重要特性不會(huì)凸顯出來(lái)，最終造成密度估計(jì)波動(dòng)性大，穩(wěn)定性不好。所以要選擇一個(gè)合適的窗寬h值[4]。

如圖1所示，采用不同的窗寬h值進(jìn)行核密度估計(jì)，h=2時(shí)曲線較為光滑，h=0.05時(shí)，對(duì)應(yīng)的核密度估計(jì)曲線上下波動(dòng)較為頻繁，并且這兩條曲線與真實(shí)曲線相差甚遠(yuǎn)。圖中的虛線是實(shí)際概率密度曲線。在h=2與h=0.05之間取h=0.337，對(duì)應(yīng)的KDE密度曲線更接近于實(shí)際概率密度函數(shù)曲線。

為了解決窗寬h的選取問(wèn)題，需要引入積分均方誤差的概念。積分均方誤差可以判斷估計(jì)所得的概率密度函數(shù)（x）和真實(shí)概率密度函數(shù)f（x）存在的差異，其表達(dá)式為：

2 MapReduce

由于 Hadoop 沒(méi)有針對(duì)迭代計(jì)算作特殊優(yōu)化，因此利用 Hadoop 的核心算法 MapReduce 進(jìn)行K-means迭代設(shè)計(jì)[5]，將原有串行算法中每一次迭代計(jì)算過(guò)程對(duì)應(yīng)一次MapReduce計(jì)算過(guò)程，以此完成數(shù)據(jù)點(diǎn)到鄰近簇中心的距離，然后把每一次迭代過(guò)程封裝成一個(gè)MapReduce作業(yè)K-meansJob。為了得到更優(yōu)的聚類效果，需要?jiǎng)?chuàng)建多個(gè)K-meansJob。

圖2描述了基于高斯核函數(shù)估計(jì)的K-means聚類并行化計(jì)算流程：從HDFS上讀取數(shù)據(jù)集后進(jìn)行高斯核密度估計(jì)，獲取數(shù)據(jù)集密度分布；然后由密度分布設(shè)定密度閾值和半徑閾值，由這兩個(gè)閾值獲取K值和初始聚類中心；把K值作為初始值輸入，然后啟動(dòng)K-meansJob，每一次聚類都包括Map和Reduce兩部分，每個(gè)Reduce匯總一個(gè)簇的數(shù)據(jù)點(diǎn)集，然后計(jì)算更新該簇的中心點(diǎn)；每一次聚類結(jié)束后，都根據(jù)當(dāng)前結(jié)果判斷是否收斂；如果聚類結(jié)果沒(méi)有滿足收斂條件，則Hadoop會(huì)再次創(chuàng)建K-meansJob，把上一次的輸出結(jié)果作為本次輸入；重復(fù)執(zhí)行聚類任務(wù)，直到聚類結(jié)果滿足最大迭代次數(shù)或收斂條件為止。

3 實(shí)驗(yàn)結(jié)果分析

本次實(shí)驗(yàn)在經(jīng)典K-means算法和本文算法上各實(shí)驗(yàn)50次，每10次為一組求平均值，得出5組平均值。在經(jīng)典K-means中對(duì)初始值非常敏感，并且迭代次數(shù)較多。然而本文算法先進(jìn)行高斯核密度估計(jì)，然后再進(jìn)行K-means聚類，這樣不用賦初始K值，并且移植到MapReduce分布式框架下的運(yùn)行效率也大大提高。通過(guò)表1可以看出，本文算法相比于經(jīng)典K-means算法，迭代次數(shù)少，誤差率低，運(yùn)行結(jié)果的正確率也更高。

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)K-means聚類算法的初始K值選取困難，且對(duì)于高維大數(shù)據(jù)的聚類效果不太明顯，以及在傳統(tǒng)K-means有時(shí)會(huì)形成局部最優(yōu)，而非全局最優(yōu)的缺點(diǎn)，本文采用基于高斯核函數(shù)密度估計(jì)的方法在Hadoop平臺(tái)下進(jìn)行K-means聚類。實(shí)驗(yàn)結(jié)果顯示，本文算法明顯優(yōu)于傳統(tǒng)的K-means聚類算法，并且運(yùn)算效率也優(yōu)于單機(jī)下運(yùn)行高斯核密度估計(jì)的K-means聚類。

參考文獻(xiàn)：

[1] 翟東海，魚(yú)江，高飛，等.最大距離法選取初始聚類中心的K-means文本聚類算法的研究[J].計(jì)算機(jī)應(yīng)用研究，2014，31（3）：713-715，719.

[2] ROSENBLATT M. Remarks on some nonparametric estimates of a density function [J]. The Annals of Mathematical Statistics，1956，27（3）：832-837.

[3] JONES M C， MARRON J S， SHEATHER S J. A brief survey of bandwidth selection for density estimation [J]. Journal of the American Statistical Association，1996，3（433）：401-407.

[4] 楊茹.核函數(shù)的密度估計(jì)算法[D].哈爾濱：哈爾濱理工大學(xué)，2016.

[5] 江小平，李成華，向文，等.K-means 聚類算法的MapReduce并行化實(shí)現(xiàn)[J].華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2011， 39（1）：120-124.

[6] 熊開(kāi)玲，彭俊杰，楊曉飛，等.基于核密度估計(jì)的K-means聚類優(yōu)化[J].計(jì)算機(jī)技術(shù)與發(fā)展，2017，27（2）：1-5.

[7] 雷小鋒，謝昆青，林帆，等.一種基于K-means局部最優(yōu)性的高效聚類算法[J].軟件學(xué)報(bào)，2008，19（7）：1683-1692.

[8] 謝娟英，高紅超.基于統(tǒng)計(jì)相關(guān)性與K-means的區(qū)分基因子集選擇算法[J].軟件學(xué)報(bào)，2014，25（9）：2050-2075.

[9] MACQUEEN J B. Some methods for classification and analysis of multivariate observation [C].Proceedings of 5th Berkeley symposium on mathematical statistics and probability. California： University of California Press，1967：281-297.

[10] DUDOIT S，F(xiàn)RIDLY J.A prediction-based resampling method for estimating the number of clusters in a dataset [J]. Genome Biology，2002，3（7）：1-21.

[11] BUCH-LARSEN T， NIELSEN J P， GUILLEN M. Kernel density estimation for heavy-tailed distributions using the champernowne transformation[J]. Statistics，2005，39（6）：503-518.

[12] RASHMI C. Analysis of different approaches of parallel block processing for K-Means clustering algorithm[J]. Computer Science，2017.

[13] NIU B， DUAN Q， LIU J， et al. A population-based clustering technique using particle swarm optimization and k-means[J]. Natural Computing，2017，16：45-59.

（責(zé)任編輯：黃 健）