郭燁旻

(吉林工程技術(shù)師范學院信息工程學院，吉林長春 130052)

大數(shù)據(jù)聚類算法的應(yīng)用主要集中在圖形處理、模式匹配、市場分析等領(lǐng)域。大數(shù)據(jù)的聚類分析研究存在著各種困難，而這些困難是由大數(shù)據(jù)本身的特點所決定的。進入大數(shù)據(jù)時代后需要處理的數(shù)據(jù)量規(guī)模劇增，使用串行方式進行數(shù)據(jù)分析的傳統(tǒng)聚類方法已經(jīng)難以適應(yīng)當前云計算網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)處理需求，本研究采用并行的方式，以預(yù)測強度為切入點對大數(shù)據(jù)聚類算法進行研究和優(yōu)化。

對某一指定的數(shù)據(jù)集以其一項或幾項屬性為出發(fā)點，對其進行分類的這一過程被稱為聚類，而在聚類的過程中并不需要對數(shù)據(jù)集的全部屬性進行充分的了解。一般將所分的多個類別中的每一個稱為一個蔟(Cluster)，以數(shù)據(jù)在一項或幾項特定屬性上的相似度，作為不同蔟之間的劃分標準。所以，在聚類的過程中并不需要預(yù)先設(shè)置分類標準，而是以數(shù)據(jù)本身的特定屬性為依據(jù)，自動進行分類。

1 數(shù)據(jù)分析系統(tǒng)

當前大數(shù)據(jù)分析處理系統(tǒng)主要有兩大方向：以Hadoop為代表的批處理系統(tǒng)；為特定應(yīng)用所開發(fā)的流處理(Stream Processing)系統(tǒng)。其主要區(qū)別在于批處理系統(tǒng)需要儲存后再處理，而流處理系統(tǒng)則是直接處理。單一的數(shù)據(jù)分析處理系統(tǒng)對當前云計算網(wǎng)絡(luò)環(huán)境下數(shù)據(jù)量劇增的情況難以適應(yīng)，應(yīng)用體系結(jié)構(gòu)與底層設(shè)計語言混合以及大數(shù)據(jù)處理高層計算模式混合的混合式數(shù)據(jù)分析系統(tǒng)更加適應(yīng)當前的應(yīng)用需要。

2 預(yù)測強度優(yōu)化的聚類算法

預(yù)期中要將數(shù)據(jù)集劃分為蔟的數(shù)量是聚類過程中的重要參數(shù)，本研究在計算聚類數(shù)時使用Tibshirani在2001年提出的基于預(yù)測強度的方法。

具體的計算步驟為：

(1)將當前數(shù)據(jù)集以隨機劃分的方式分為測試集A和測試集B；

(2)以k作為當前聚類數(shù)，對兩個子集進行聚類，記錄結(jié)果；

(3)將兩個子集的聚類結(jié)果進行判別；

(4)統(tǒng)計集合A所有蔟中的樣本在集合B中的分類誤差，計算分配的正確率；

(5)以k為聚類數(shù)的預(yù)測強度為所有正確率中的最小值。

在預(yù)測強度定義中，C(A,k)表示將集合A聚為k類，Akj表示集合B聚成的第j類，nkj代表Akj中的元素數(shù)量，D[C(A,k),B]ii′為聚類結(jié)果判別矩陣中i行i′列的元素值。由此可見，預(yù)測強度值pk(s)∈[0,1]，受聚類數(shù)影響。預(yù)測強度值越大，說明當前聚類算法能夠?qū)⑿聰?shù)據(jù)元素劃分到正確的蔟的預(yù)測能力越強。

預(yù)測集合和測試集合對數(shù)據(jù)的隨機劃分，會導致預(yù)測強度受到偶然因素干擾比較嚴重。本文提出將數(shù)據(jù)先行劃分成多個隨機類，分別作為測試集計算預(yù)測強度，取多個預(yù)測強度的平均值作為當前聚類數(shù)下的最終預(yù)測強度，從而減小偶然因素對預(yù)測強度的干擾，起到優(yōu)化算法的作用。

通過預(yù)測強度確定聚類數(shù)k，從而進行聚類的對應(yīng)算法如下：

輸入：數(shù)據(jù)集D={d1,d2,…,di,…,dn}，當前最佳聚類數(shù)k

(1)從D集合中選取k個屬于D的數(shù)據(jù)點d1′,…,dk′作為聚類后的蔟的質(zhì)心；

(5)循環(huán)運行步驟(2)和步驟(3)，直到(4)的值不再變化，顯而易見，準則函數(shù)值是在不斷縮小的。

其中，Nj應(yīng)為距數(shù)據(jù)di最近的質(zhì)心dj′所在的蔟，sign(Nj=j)表示當Nj=j時其值為1，其他所有情況其值為0。

輸出：質(zhì)心d1′,…,dk′所在的蔟N1,…,Nk

取某直播平臺訪客在不同欄目上停留時間的數(shù)據(jù)，輸入三個欄目的數(shù)據(jù)，以主播數(shù)量3作為變量數(shù)進行分析。選用BIC準則建立模型，生成變量數(shù)與聚類數(shù)之間的函數(shù)曲線，對比優(yōu)化后的基于預(yù)測強度的變量數(shù)與聚類數(shù)關(guān)系函數(shù)曲線如圖1所示。

圖1 優(yōu)化后算法與已有算法對比圖

在相同變量數(shù)的條件下，BIC準則本身對聚類數(shù)的確定沒有影響，從使用BIC準則的圖1中可看出，當聚類數(shù)超過4之后圖像趨于平穩(wěn)，受偶然因素干擾程度較小，聚類數(shù)應(yīng)為超過4的值，但無法完全確定具體取值。而使用優(yōu)化后的算法可得到聚類數(shù)為4時預(yù)測強度有最大值，能夠較為準確地確定聚類數(shù)。

按照測試強度確定聚類數(shù)為4，聚類分析后的曲線如圖2所示。

通過對圖2的分析可以明顯看出，具有第一類屬性的訪客對大部分欄目都有較大的興趣，他們所具有的屬性與平臺的欄目設(shè)置方向一致性較大，對該屬性用戶的服務(wù)可以做適當?shù)膬A斜。而第四類用戶明顯對平臺當前的內(nèi)容興趣欠缺，在沒有開設(shè)新欄目之前可以對具有第四類屬性的用戶適當忽略。

圖2 不同類訪客在所有欄目上的平均停留時間

3 結(jié)語

通過以上測試可以看到優(yōu)化后的聚類算法在實際應(yīng)用中的作用。以傳統(tǒng)聚類算法為基礎(chǔ)，對確定具體聚類數(shù)量的方法進行適當?shù)膬?yōu)化，可以有效地減少偶然因素對聚類結(jié)果的干擾，使用該算法在進行大量數(shù)據(jù)聚類分析時能夠有效地減少時間復雜度以及經(jīng)濟支出，具有一定的應(yīng)用價值。

[參考文獻]

[1]李國杰,程學旗.大數(shù)據(jù)研究:未來科技及經(jīng)濟社會發(fā)展的重大戰(zhàn)略領(lǐng)域——大數(shù)據(jù)的研究現(xiàn)狀與科學思考[J].網(wǎng)絡(luò)新媒體技術(shù),2012(6):647-657.

[2]黃宜華.深入理解大數(shù)據(jù):大數(shù)據(jù)處理與編程實踐[M].北京:機械工業(yè)出版社,2014.

[3]楊彥侃.并行的聚類算法研究[D].包頭:內(nèi)蒙古科技大學,2010.

[4]R Tibshirani,G Walther.Cluster Validation by Predication Strength[J].Journal of Computational & Graphical Statistics,2005(3):511-528.