郭燁旻

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

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

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

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

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

2 預(yù)測(cè)強(qiáng)度優(yōu)化的聚類(lèi)算法

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

具體的計(jì)算步驟為：

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

(2)以k作為當(dāng)前聚類(lèi)數(shù)，對(duì)兩個(gè)子集進(jìn)行聚類(lèi)，記錄結(jié)果；

(3)將兩個(gè)子集的聚類(lèi)結(jié)果進(jìn)行判別；

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

(5)以k為聚類(lèi)數(shù)的預(yù)測(cè)強(qiáng)度為所有正確率中的最小值。

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

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

通過(guò)預(yù)測(cè)強(qiáng)度確定聚類(lèi)數(shù)k，從而進(jìn)行聚類(lèi)的對(duì)應(yīng)算法如下：

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

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

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

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

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

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

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

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

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

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

圖2 不同類(lèi)訪客在所有欄目上的平均停留時(shí)間

3 結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

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