鄭志嫻,吳為民,李慧敏
(福建船政交通職業(yè)學(xué)院 信息工程系, 福州 350007)
隨著大數(shù)據(jù)應(yīng)用逐漸被重視,在大數(shù)據(jù)的數(shù)據(jù)挖掘領(lǐng)域產(chǎn)生了眾多的數(shù)據(jù)挖掘聚類算法,其中包括有基于數(shù)據(jù)密度的聚類算法、基于層次分析的聚類算法、基于數(shù)據(jù)類型劃分的聚類算法等等,各類聚類算法都有其顯著的特征,在數(shù)據(jù)挖掘的某一領(lǐng)域內(nèi)具有較好的應(yīng)用效果.例如BRICH算法效率高,適用于凸型或球型聚類類型,對(duì)噪聲和輸入數(shù)據(jù)不敏感;DBSCAN算法效率一般[1-2],適用于任意形狀的聚類類型,對(duì)噪聲和數(shù)據(jù)輸入敏感;CURE算法效率較高,適用于任何形狀聚類類型,對(duì)噪聲和輸入數(shù)據(jù)不太敏感;CLARANS算法效率較低,適用于凸型或球型聚類類型,對(duì)噪聲不敏感對(duì)輸入數(shù)據(jù)敏感;CLIQUE算法效率低,適用于凸型或球型聚類類型,對(duì)噪聲和輸入數(shù)據(jù)不太敏感;K-Means算法效率較低,適用于凸型或球型聚類類型,對(duì)噪聲和輸入數(shù)據(jù)不太敏感等[3].本文以數(shù)據(jù)不斷增加、數(shù)據(jù)類型多樣、數(shù)據(jù)結(jié)構(gòu)復(fù)雜為研究對(duì)象,因此CURE算法具有較好的應(yīng)用效果,以此為研究對(duì)象進(jìn)行數(shù)據(jù)挖掘算法優(yōu)化具有非?,F(xiàn)實(shí)的意義.
CURE聚類算法是一種能夠?qū)?fù)雜數(shù)據(jù)、多類型數(shù)據(jù)進(jìn)行高效數(shù)據(jù)挖掘的算法之一,其在計(jì)算過程中將每一個(gè)類視為一個(gè)點(diǎn),用點(diǎn)來表示一類的數(shù)據(jù),再通過收縮因子對(duì)點(diǎn)進(jìn)行控制使其能夠越來越接近類的中心點(diǎn),因?yàn)閷?duì)數(shù)據(jù)的封裝所以會(huì)減少因噪聲帶來的聚類影響,對(duì)聚類的劃分更加清晰準(zhǔn)確.CURE聚類算法可以對(duì)任意類型的數(shù)據(jù)、任意形狀的聚類進(jìn)行計(jì)算,算法效率高,對(duì)隨時(shí)輸入數(shù)據(jù)不敏感,應(yīng)用范圍更加廣泛[4].
CURE聚類算法是一個(gè)基礎(chǔ)的聚類算法,在面對(duì)海量數(shù)據(jù)、結(jié)構(gòu)及其復(fù)雜、動(dòng)態(tài)性強(qiáng)和噪聲強(qiáng)的數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘計(jì)算時(shí)仍存在數(shù)據(jù)挖掘不準(zhǔn)確、數(shù)據(jù)挖掘效率低得問題[5].CURE算法以類點(diǎn)進(jìn)行聚類,對(duì)聚類對(duì)象具有嚴(yán)格的劃分,類和類之間的距離計(jì)算可采用歐式距離、馬氏距離和拉格朗日距離進(jìn)行計(jì)算,但是在數(shù)據(jù)以不規(guī)律形式增加和數(shù)據(jù)類型復(fù)雜多變的情況下,其不能夠很好的反映出數(shù)據(jù)的完整性[6],從原始數(shù)據(jù)集中抽取數(shù)據(jù)會(huì)到時(shí)數(shù)據(jù)量龐大計(jì)算效率低得問題并且會(huì)出現(xiàn)類間距離計(jì)算出現(xiàn)誤差的問題,由此會(huì)導(dǎo)致聚類的結(jié)果不準(zhǔn)確的現(xiàn)象.因此要使CURE算法能夠在數(shù)據(jù)挖掘中更加靈活,本文提出對(duì)CURE算法進(jìn)行優(yōu)化,使其具有更加良好的數(shù)據(jù)挖掘能力和計(jì)算效率.
針對(duì)CURE算法在面對(duì)海量數(shù)據(jù)計(jì)算優(yōu)勢(shì)減弱的問題,本文提出了引入并行化處理數(shù)據(jù)的方式,將MapReduce函數(shù)對(duì)不規(guī)律動(dòng)態(tài)增加的數(shù)據(jù)進(jìn)行并行化處理,以數(shù)據(jù)對(duì)象不確定性為研究目標(biāo)進(jìn)行兩個(gè)類之間的新距離計(jì)算方式對(duì)CURE算法進(jìn)行優(yōu)化,CURE算法優(yōu)化流程如圖1所示.
圖1 CURE算法優(yōu)化流程
對(duì)于CURE算法的優(yōu)化是將所采集到的原始數(shù)據(jù)劃分成為n個(gè)數(shù)據(jù)片,將數(shù)據(jù)片中的每一個(gè)數(shù)據(jù)作為一個(gè)類,計(jì)算類與類之間的距離,并將距離最小的兩個(gè)類合并,計(jì)算類間距離過程中引入Map函數(shù)實(shí)現(xiàn)并行化處理,基于區(qū)間數(shù)和標(biāo)準(zhǔn)差,Reduce函數(shù)更新代表點(diǎn),計(jì)算新類的中心點(diǎn)及代表點(diǎn),判斷聚類數(shù)是否滿足k=α,若滿足則輸出聚類結(jié)果,若不滿足則返回類重新進(jìn)行距離計(jì)算[7-8].
聚類過程分析
基于CURE聚類優(yōu)化引入了MapReduce函數(shù)進(jìn)行數(shù)據(jù)的并行化處理,利用Map函數(shù)將數(shù)據(jù)集劃分成為若干個(gè)片,每片的數(shù)據(jù)分配到不同節(jié)點(diǎn)上進(jìn)行執(zhí)行.再利用Reduce函數(shù)進(jìn)行分區(qū),根據(jù)中間結(jié)果的鍵值劃分成R塊,以解決CURE算法抽樣導(dǎo)致聚類結(jié)果又偏差的問題.同時(shí)對(duì)于不斷增加的數(shù)據(jù)可以在完成并行化處理后快速進(jìn)行下一時(shí)間節(jié)點(diǎn)的數(shù)據(jù)處理.此過程分為Map和Reduce兩個(gè)階段,Map階段將輸入的數(shù)據(jù)進(jìn)行初始化,使其成為一個(gè)類,總數(shù)標(biāo)記為Q,設(shè)定聚類個(gè)數(shù)為k,當(dāng)Q>k時(shí),距離最近的兩個(gè)類合并.Reduce階段根據(jù)Map函數(shù)的輸出,判斷Q是否大于k,如果大于則需要繼續(xù)聚類,如果Q=k,則終止聚類.
CURE算法類和類之間的距離計(jì)算可采用歐式距離、馬氏距離和拉格朗日距離進(jìn)行計(jì)算[9-10],其計(jì)算環(huán)境是數(shù)據(jù)量不變,準(zhǔn)確知道確定性的數(shù)據(jù),可以通過數(shù)據(jù)值或者界限進(jìn)行類邊界的距離測(cè)度度量,而面對(duì)不斷變化的數(shù)據(jù),原有計(jì)算方法會(huì)出現(xiàn)邊界模糊的問題,而導(dǎo)致數(shù)據(jù)缺失,所以本文提出獲取動(dòng)態(tài)數(shù)據(jù)標(biāo)準(zhǔn)差的方式進(jìn)行數(shù)據(jù)處理,對(duì)任意兩個(gè)動(dòng)態(tài)的數(shù)據(jù)對(duì)象Q1和Q2,其之間的變動(dòng)距離最小值表示為dmin(Q1,Q2),最大值表示為dmax(Q1,Q2).區(qū)間數(shù)的計(jì)算在給定區(qū)間數(shù)[X,Y]內(nèi)的任意距離d為:
d(X,Y)=‖X-Y‖=
(1)
其中:X區(qū)間數(shù)為X=[XL,XR],Y區(qū)間數(shù)為[YL,YR].
利用標(biāo)準(zhǔn)差表示區(qū)間,設(shè)一組數(shù)據(jù)X=(x1,x2,……,xn)標(biāo)準(zhǔn)差為:
(2)
用μ表示數(shù)據(jù)的平均值,數(shù)據(jù)區(qū)間表示為:
Xi=[xi-kσ,xi+kσ](1≤i≤n,k∈R|0≤k≤3)
(3)
用k表示收縮因子,k=1時(shí)數(shù)據(jù)分布在[xi-kσ,xi+kσ]概率為67.5%,k=2時(shí)的數(shù)據(jù)分布在[xi-kσ,xi+kσ]的概率為96.8%,k=3時(shí)數(shù)據(jù)分布在[xi-kσ,xi+kσ]的概率為99.9%,由此確定k的值,將不斷變動(dòng)的數(shù)據(jù)確定在可接受的概率范圍內(nèi).
用區(qū)間數(shù)值表示的數(shù)據(jù)之間的關(guān)系不能夠通過相間獲取之間距離的關(guān)系,所以要通過區(qū)間數(shù)值的包含、相離、相接、相交來確定位置關(guān)系,其中數(shù)據(jù)的相接關(guān)系距離值為0,用代數(shù)表示區(qū)間數(shù)值的距離最大值和最小值分別可表示為:
dmax=|xj-xi|+2kσ
(1≤i≤n,1≤j≤n,i≠j)
(4)
dmin=|xj-xi|-2kσ
(1≤i≤n,1≤j≤n,i≠j)
(5)
用區(qū)間表示數(shù)據(jù)之間的距離:
d(Xi,Xj)=[dmin,dmax]
(6)
對(duì)數(shù)據(jù)中的任意兩類數(shù)據(jù)u和v作為基于CURE聚類優(yōu)化的對(duì)象,其中u的中心點(diǎn)為u.mean,v的中心點(diǎn)為u.rep,兩個(gè)類之間的距離為dist(u,v).數(shù)據(jù)中的任意兩個(gè)數(shù)據(jù)項(xiàng)為p,q,則p和q之間的距離為dist(p,q),聚類數(shù)目為k,CURE聚類優(yōu)化后的過程表示如下:
通過Map函數(shù)對(duì)數(shù)據(jù)進(jìn)行劃分,將挖掘的數(shù)據(jù)劃分為n個(gè)數(shù)據(jù)片,實(shí)現(xiàn)由Map函數(shù)進(jìn)行計(jì)算的并行化處理;
被Map函數(shù)劃分的數(shù)據(jù)片進(jìn)行聚類,用聚類獲得的數(shù)據(jù)作為一個(gè)類,類和類之間的距離表示為d(p,q)=[dmin,dmax];
所計(jì)算的新類代表點(diǎn)表示為w.rep,用α表示收縮因子α[0.2,0.7],合并后類的個(gè)數(shù)變?yōu)閚-1;
使用Reduce函數(shù)對(duì)新的數(shù)據(jù)組進(jìn)行判斷,看是否合并后的類之間達(dá)到最優(yōu)聚類,如果聚類數(shù)目未達(dá)到預(yù)定值,重新進(jìn)行Map函數(shù)計(jì)算合并類,如果達(dá)到預(yù)定值則聚類結(jié)束;
刪除異常的數(shù)據(jù)點(diǎn),完成所有聚類.
實(shí)驗(yàn)
以某通信企業(yè)用戶數(shù)據(jù)為例,數(shù)據(jù)內(nèi)容包括用戶的基本信息,包括:性別、年齡、類型、行業(yè)、業(yè)務(wù)、付費(fèi)方式、付費(fèi)金額、月付費(fèi)次數(shù)、投訴時(shí)間、投訴內(nèi)容、用戶等級(jí)、用戶狀態(tài);消費(fèi)行為信息包括:平均通話次數(shù)、本地通話時(shí)長(zhǎng)、國(guó)內(nèi)長(zhǎng)途通話時(shí)長(zhǎng)、國(guó)際長(zhǎng)途通話時(shí)間、總長(zhǎng)途通話時(shí)長(zhǎng)、漫游通話時(shí)長(zhǎng)、短信條數(shù)、數(shù)據(jù)流量、其他費(fèi)用、本次通話時(shí)長(zhǎng)標(biāo)準(zhǔn)差、國(guó)內(nèi)長(zhǎng)途通話時(shí)長(zhǎng)標(biāo)準(zhǔn)差、國(guó)際長(zhǎng)途通話時(shí)長(zhǎng)標(biāo)準(zhǔn)差、漫游通話時(shí)長(zhǎng)標(biāo)準(zhǔn)差、數(shù)據(jù)流量標(biāo)準(zhǔn)差、短信條數(shù)標(biāo)準(zhǔn)差、其他費(fèi)用所占比重;用戶適用行為信息包括:用戶位置、用戶網(wǎng)絡(luò)瀏覽記錄、用戶購(gòu)買記錄、用戶下載記錄、用戶上傳記錄、用戶網(wǎng)絡(luò)流量(d)、用戶網(wǎng)絡(luò)變更、用戶機(jī)型、業(yè)務(wù)適用日志.
以該通信企業(yè)2017年1~5月份數(shù)據(jù)作為挖掘?qū)ο螅S機(jī)采集1 000個(gè)用戶進(jìn)行數(shù)據(jù)預(yù)處理,通過數(shù)據(jù)清洗、數(shù)據(jù)集成得到標(biāo)準(zhǔn)化數(shù)據(jù).數(shù)據(jù)采樣時(shí)間350 000 h,信息量包含用戶通話數(shù)據(jù)19 445條,短信息3 820條,交互信息284 901條.將預(yù)處理后的數(shù)據(jù)導(dǎo)入Matlab得到原始數(shù)據(jù)分布圖如圖2所示.
利用Matlab按照CURE聚類優(yōu)化后的方法進(jìn)行仿真,得到聚類結(jié)果如圖3所示.
圖2 大數(shù)據(jù)分布
圖3 聚類結(jié)果
將數(shù)據(jù)分為3類,獲得聚類中心分為為(0.562,0.632,0.305),(0.625,0.360,0.661),(0.246,0.475,0.510).
圖3中的紅色標(biāo)記為第一類數(shù)據(jù),數(shù)據(jù)具有穩(wěn)定的變化,通過對(duì)數(shù)據(jù)對(duì)應(yīng)的用戶進(jìn)行分析,通常此部分?jǐn)?shù)據(jù)用戶為通信公司的穩(wěn)定客戶,平均入網(wǎng)時(shí)間在3 a以上,年齡層在30~40歲之間,具有穩(wěn)定的收入,能夠保持月通話時(shí)間在300 min以上,長(zhǎng)途通過時(shí)間較長(zhǎng),通話時(shí)間段,投訴較少,對(duì)話費(fèi)不敏感.此類用戶是該通信公司的優(yōu)質(zhì)客戶,具有較好的忠誠(chéng)度,若非突發(fā)事件,不會(huì)對(duì)公司業(yè)務(wù)造成較大的不穩(wěn)定因素,是長(zhǎng)期穩(wěn)定維護(hù)基礎(chǔ)用戶.
圖3中的綠色標(biāo)記為第二類數(shù)據(jù),數(shù)據(jù)具有不穩(wěn)定變化特征,通過對(duì)數(shù)據(jù)對(duì)應(yīng)的用戶進(jìn)行分析,通常此部分?jǐn)?shù)據(jù)用戶為通信公司新入網(wǎng)用戶,平均入網(wǎng)時(shí)間在6個(gè)月以下,每次繳費(fèi)金額在50元以下,月通話時(shí)長(zhǎng)50 min以下,長(zhǎng)途通話較少.此類用戶對(duì)于通信公司來講屬于低價(jià)值用戶,用戶黏度較低.
圖3中的藍(lán)色記為第三類數(shù)據(jù),數(shù)據(jù)具有間歇變化特征,該部分用戶入網(wǎng)時(shí)間一年以上,每次繳費(fèi)金額在100~200之間,月通話時(shí)長(zhǎng)100~200 min.此類用戶為通信公司潛在用戶,具有較大的培養(yǎng)空間.
通信企業(yè)部分?jǐn)?shù)據(jù)聚類結(jié)果如表1所示.
表1通信企業(yè)部分?jǐn)?shù)據(jù)聚類結(jié)果
數(shù)據(jù)分類 用戶序號(hào)一類數(shù)據(jù)2、4、6、8、10、12、14、16、18、110、121、132、143、154、165、176、187、198、201、311、450、550、750、850、950、1000二類數(shù)據(jù)31、32、33、34、35、36、37、38、39、40、45、55、65、75、85、95、100、111、122、133、144、155、166、177、188、199、200、301、302、405、406、505、506、606、707、808、909三類數(shù)據(jù)1、3、5、7、9、11、13、15、17、19、41、42、43、44、46、47、47、49、50、51、52、53、54、56、57、58、59、115、116、117、211、212、214、315、316、415、416、517、519、619、717、719、818、891、914、999
通過通信企業(yè)部分?jǐn)?shù)據(jù)聚類結(jié)果可以清楚的劃分出每一位用戶所歸屬的分類,由此可對(duì)不同類型用戶進(jìn)行針對(duì)性的服務(wù)和管理.對(duì)于不同類型數(shù)據(jù)的分析可了解到通信企業(yè)用戶對(duì)公司品牌的信賴程度,若一類數(shù)據(jù)量較大則證明該企業(yè)具有穩(wěn)定的用戶資源,一類數(shù)據(jù)增長(zhǎng)則該公司的發(fā)展處于穩(wěn)定增長(zhǎng)期.若二類數(shù)據(jù)量較大,則證明該企業(yè)仍較為年輕,用戶資源穩(wěn)定性不高,二類數(shù)據(jù)增長(zhǎng)則是該公司在短期內(nèi)的營(yíng)銷手段起到了一定的效果,后續(xù)應(yīng)調(diào)整業(yè)務(wù)結(jié)構(gòu)使用戶成為企業(yè)忠實(shí)用戶.若三類數(shù)據(jù)量較大,則證明該企業(yè)已經(jīng)有了一定的客戶基礎(chǔ),需要對(duì)用戶進(jìn)行更好的維護(hù)使?jié)撛谟脩舫蔀橹覍?shí)用戶.由表1可以看出該企業(yè)目前二類和三類數(shù)據(jù)量較多,證明企業(yè)正處于高速的發(fā)展期,企業(yè)應(yīng)針對(duì)該時(shí)期制定針對(duì)性的業(yè)務(wù),使用戶成為企業(yè)忠實(shí)的用戶資源.
從通信企業(yè)用戶數(shù)據(jù)中抽取n組數(shù)據(jù),進(jìn)行CURE聚類優(yōu)化前后時(shí)間上的對(duì)比,結(jié)果如表2所示:
表2CURE聚類優(yōu)化前后時(shí)間對(duì)比結(jié)果
nCURE聚類算法CURE聚類算法優(yōu)化10000454240000857580000124110120000168140160000204172200000245211240000288249280000326281
由表2可見,CURE算法本身在不確定數(shù)據(jù)的聚類時(shí)間上不具有優(yōu)勢(shì),但是經(jīng)過優(yōu)化后本文所提出的CURE算法優(yōu)化在聚類時(shí)間上具有了明顯的優(yōu)勢(shì),這也證明了此次算法的改進(jìn)在聚類時(shí)間上具有較好的實(shí)用性.
再進(jìn)行算法準(zhǔn)確的比較如表3所示.
表3CURE聚類優(yōu)化前后準(zhǔn)群性對(duì)比結(jié)果
nCURE聚類算法CURE聚類算法優(yōu)化10000659940000759580000609212000058911600005491200000759024000078892800005688
由表3可見,隨著數(shù)據(jù)量的增加,CURE算法自身的穩(wěn)定性較差,優(yōu)化后穩(wěn)定性明顯提高,而且準(zhǔn)確率大幅度提升.
在互聯(lián)網(wǎng)數(shù)據(jù)爆發(fā)式增長(zhǎng),移動(dòng)設(shè)備產(chǎn)生數(shù)據(jù)量不斷增加,網(wǎng)絡(luò)數(shù)據(jù)復(fù)雜度不斷深化的過程中,對(duì)數(shù)據(jù)的挖掘難度日益的加大,而面對(duì)不斷增長(zhǎng)和變化的數(shù)據(jù)原有的數(shù)據(jù)挖掘算法顯然無法滿足數(shù)據(jù)復(fù)雜與多變的挖掘需求,因此本文通過比對(duì)分析后對(duì)基于CURE聚類算法進(jìn)行優(yōu)化使其在一定程度上滿足變動(dòng)數(shù)據(jù)挖掘的需求,介紹CURE聚類算法的基本原理和優(yōu)化方法,并闡述基于CURE聚類優(yōu)化算法的數(shù)據(jù)聚類過程,包括引入MapReduce函數(shù),計(jì)算不確定數(shù)據(jù)間距離,采用距離區(qū)間數(shù)的方式解決邊界模糊問題,提高變動(dòng)數(shù)據(jù)距離計(jì)算的準(zhǔn)確性,梳理基于CURE聚類優(yōu)化算法的數(shù)據(jù)聚類步驟.通過以某通信企業(yè)不斷變化的用戶數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn),該數(shù)據(jù)可劃分為三大類,一是用戶基本信息,二是用戶消費(fèi)行為,三是用戶操作行為,三種變動(dòng)類型數(shù)據(jù)通過數(shù)據(jù)預(yù)處理后倒入Matlab得到原始的數(shù)據(jù)分布圖,再通過CURE聚類優(yōu)化算法進(jìn)行聚類仿真得到仿真結(jié)果,試驗(yàn)證明了本文提出的以范圍約束計(jì)算變動(dòng)數(shù)據(jù)類,能夠較好的對(duì)數(shù)據(jù)進(jìn)行挖掘,提了高數(shù)據(jù)挖掘的準(zhǔn)確性和數(shù)據(jù)挖掘的效率.
[1] 齊興斌,趙 麗,李雪梅.基于BIRCH聚類加速的彩色圖像增強(qiáng)算法[J].計(jì)算機(jī)測(cè)量與控制,2016,24(4):137-140.
[2] 向柳明,周渭博,鐘 勇.基于高斯過程的CLIQUE改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用,2015(s2):85-87.
[3] 張曉琳,崔寧寧,楊 濤,等.一種分層自適應(yīng)快速K-means算法[J].計(jì)算機(jī)應(yīng)用研究,2016,33(2):421-423.
[4] 李 松,崔環(huán)宇,張麗平,經(jīng)海東.基于CURE聚類算法的靜態(tài)R樹構(gòu)建方法[J].計(jì)算機(jī)科學(xué),2015,42(10):193-197.
[5] 高長(zhǎng)元,王海晶,王 京.基于改進(jìn)CURE算法的不確定性移動(dòng)用戶數(shù)據(jù)聚類[J].計(jì)算機(jī)工程與科學(xué),2016,38(4):768-774.
[6] 王寅同,王建東,陳海燕,等.一種代表點(diǎn)的近似折半層次聚類算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(2):215-219.
[7] 倪志偉,荊婷婷,倪麗萍.一種近鄰傳播的層次優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2015,42(3):195-200.
[8] 王志春.初始中心點(diǎn)優(yōu)化的K-means聚類模型[J].電腦迷,2016(9):50-51.
[9] 伍育紅.聚類算法綜述[J].計(jì)算機(jī)科學(xué),2015,42(s1):491-499,524.
[10] 陳 曉,趙晶玲.大數(shù)據(jù)處理中混合型聚類算法的研究與實(shí)現(xiàn)[J].信息網(wǎng)絡(luò)安全,2015(4):45-49.