鄭志嫻，吳為民，李慧敏

(福建船政交通職業(yè)學院 信息工程系, 福州 350007)

隨著大數(shù)據(jù)應用逐漸被重視，在大數(shù)據(jù)的數(shù)據(jù)挖掘領域產(chǎn)生了眾多的數(shù)據(jù)挖掘聚類算法，其中包括有基于數(shù)據(jù)密度的聚類算法、基于層次分析的聚類算法、基于數(shù)據(jù)類型劃分的聚類算法等等，各類聚類算法都有其顯著的特征，在數(shù)據(jù)挖掘的某一領域內(nèi)具有較好的應用效果.例如BRICH算法效率高，適用于凸型或球型聚類類型，對噪聲和輸入數(shù)據(jù)不敏感；DBSCAN算法效率一般[1-2]，適用于任意形狀的聚類類型，對噪聲和數(shù)據(jù)輸入敏感；CURE算法效率較高，適用于任何形狀聚類類型，對噪聲和輸入數(shù)據(jù)不太敏感；CLARANS算法效率較低，適用于凸型或球型聚類類型，對噪聲不敏感對輸入數(shù)據(jù)敏感；CLIQUE算法效率低，適用于凸型或球型聚類類型，對噪聲和輸入數(shù)據(jù)不太敏感；K-Means算法效率較低，適用于凸型或球型聚類類型，對噪聲和輸入數(shù)據(jù)不太敏感等[3].本文以數(shù)據(jù)不斷增加、數(shù)據(jù)類型多樣、數(shù)據(jù)結構復雜為研究對象，因此CURE算法具有較好的應用效果，以此為研究對象進行數(shù)據(jù)挖掘算法優(yōu)化具有非?，F(xiàn)實的意義.

1 CURE聚類算法介紹

CURE聚類算法是一種能夠對復雜數(shù)據(jù)、多類型數(shù)據(jù)進行高效數(shù)據(jù)挖掘的算法之一，其在計算過程中將每一個類視為一個點，用點來表示一類的數(shù)據(jù)，再通過收縮因子對點進行控制使其能夠越來越接近類的中心點，因為對數(shù)據(jù)的封裝所以會減少因噪聲帶來的聚類影響，對聚類的劃分更加清晰準確.CURE聚類算法可以對任意類型的數(shù)據(jù)、任意形狀的聚類進行計算，算法效率高，對隨時輸入數(shù)據(jù)不敏感，應用范圍更加廣泛[4].

CURE聚類算法是一個基礎的聚類算法，在面對海量數(shù)據(jù)、結構及其復雜、動態(tài)性強和噪聲強的數(shù)據(jù)進行數(shù)據(jù)挖掘計算時仍存在數(shù)據(jù)挖掘不準確、數(shù)據(jù)挖掘效率低得問題[5].CURE算法以類點進行聚類，對聚類對象具有嚴格的劃分，類和類之間的距離計算可采用歐式距離、馬氏距離和拉格朗日距離進行計算，但是在數(shù)據(jù)以不規(guī)律形式增加和數(shù)據(jù)類型復雜多變的情況下，其不能夠很好的反映出數(shù)據(jù)的完整性[6]，從原始數(shù)據(jù)集中抽取數(shù)據(jù)會到時數(shù)據(jù)量龐大計算效率低得問題并且會出現(xiàn)類間距離計算出現(xiàn)誤差的問題，由此會導致聚類的結果不準確的現(xiàn)象.因此要使CURE算法能夠在數(shù)據(jù)挖掘中更加靈活，本文提出對CURE算法進行優(yōu)化，使其具有更加良好的數(shù)據(jù)挖掘能力和計算效率.

2 CURE聚類算法優(yōu)化

針對CURE算法在面對海量數(shù)據(jù)計算優(yōu)勢減弱的問題，本文提出了引入并行化處理數(shù)據(jù)的方式，將MapReduce函數(shù)對不規(guī)律動態(tài)增加的數(shù)據(jù)進行并行化處理，以數(shù)據(jù)對象不確定性為研究目標進行兩個類之間的新距離計算方式對CURE算法進行優(yōu)化，CURE算法優(yōu)化流程如圖1所示.

圖1 CURE算法優(yōu)化流程

對于CURE算法的優(yōu)化是將所采集到的原始數(shù)據(jù)劃分成為n個數(shù)據(jù)片，將數(shù)據(jù)片中的每一個數(shù)據(jù)作為一個類，計算類與類之間的距離，并將距離最小的兩個類合并，計算類間距離過程中引入Map函數(shù)實現(xiàn)并行化處理，基于區(qū)間數(shù)和標準差，Reduce函數(shù)更新代表點，計算新類的中心點及代表點，判斷聚類數(shù)是否滿足k=α，若滿足則輸出聚類結果，若不滿足則返回類重新進行距離計算[7-8].

3 基于CURE聚類優(yōu)化算法的數(shù)據(jù)

聚類過程分析

3.1 引入MapReduce函數(shù)

基于CURE聚類優(yōu)化引入了MapReduce函數(shù)進行數(shù)據(jù)的并行化處理，利用Map函數(shù)將數(shù)據(jù)集劃分成為若干個片，每片的數(shù)據(jù)分配到不同節(jié)點上進行執(zhí)行.再利用Reduce函數(shù)進行分區(qū)，根據(jù)中間結果的鍵值劃分成R塊，以解決CURE算法抽樣導致聚類結果又偏差的問題.同時對于不斷增加的數(shù)據(jù)可以在完成并行化處理后快速進行下一時間節(jié)點的數(shù)據(jù)處理.此過程分為Map和Reduce兩個階段，Map階段將輸入的數(shù)據(jù)進行初始化，使其成為一個類，總數(shù)標記為Q，設定聚類個數(shù)為k，當Q>k時，距離最近的兩個類合并.Reduce階段根據(jù)Map函數(shù)的輸出，判斷Q是否大于k，如果大于則需要繼續(xù)聚類，如果Q=k，則終止聚類.

3.2 不確定數(shù)據(jù)類間距離計算

CURE算法類和類之間的距離計算可采用歐式距離、馬氏距離和拉格朗日距離進行計算[9-10]，其計算環(huán)境是數(shù)據(jù)量不變，準確知道確定性的數(shù)據(jù)，可以通過數(shù)據(jù)值或者界限進行類邊界的距離測度度量，而面對不斷變化的數(shù)據(jù)，原有計算方法會出現(xiàn)邊界模糊的問題，而導致數(shù)據(jù)缺失，所以本文提出獲取動態(tài)數(shù)據(jù)標準差的方式進行數(shù)據(jù)處理，對任意兩個動態(tài)的數(shù)據(jù)對象Q1和Q2，其之間的變動距離最小值表示為dmin(Q1,Q2)，最大值表示為dmax(Q1,Q2).區(qū)間數(shù)的計算在給定區(qū)間數(shù)[X,Y]內(nèi)的任意距離d為：

d(X,Y)=‖X-Y‖=

(1)

其中：X區(qū)間數(shù)為X=[XL,XR]，Y區(qū)間數(shù)為[YL,YR].

利用標準差表示區(qū)間，設一組數(shù)據(jù)X=(x1,x2,……,xn)標準差為：

(2)

用μ表示數(shù)據(jù)的平均值，數(shù)據(jù)區(qū)間表示為：

Xi=[xi-kσ,xi+kσ](1≤i≤n,k∈R|0≤k≤3)

(3)

用k表示收縮因子，k=1時數(shù)據(jù)分布在[xi-kσ,xi+kσ]概率為67.5%，k=2時的數(shù)據(jù)分布在[xi-kσ,xi+kσ]的概率為96.8%，k=3時數(shù)據(jù)分布在[xi-kσ,xi+kσ]的概率為99.9%，由此確定k的值，將不斷變動的數(shù)據(jù)確定在可接受的概率范圍內(nèi).

用區(qū)間數(shù)值表示的數(shù)據(jù)之間的關系不能夠通過相間獲取之間距離的關系，所以要通過區(qū)間數(shù)值的包含、相離、相接、相交來確定位置關系，其中數(shù)據(jù)的相接關系距離值為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)

3.3 基于CURE聚類優(yōu)化算法的數(shù)據(jù)聚類步驟

對數(shù)據(jù)中的任意兩類數(shù)據(jù)u和v作為基于CURE聚類優(yōu)化的對象，其中u的中心點為u.mean，v的中心點為u.rep，兩個類之間的距離為dist(u,v).數(shù)據(jù)中的任意兩個數(shù)據(jù)項為p，q，則p和q之間的距離為dist(p,q)，聚類數(shù)目為k，CURE聚類優(yōu)化后的過程表示如下：

通過Map函數(shù)對數(shù)據(jù)進行劃分，將挖掘的數(shù)據(jù)劃分為n個數(shù)據(jù)片，實現(xiàn)由Map函數(shù)進行計算的并行化處理；

被Map函數(shù)劃分的數(shù)據(jù)片進行聚類，用聚類獲得的數(shù)據(jù)作為一個類，類和類之間的距離表示為d(p,q)=[dmin,dmax]；

所計算的新類代表點表示為w.rep，用α表示收縮因子α[0.2,0.7]，合并后類的個數(shù)變?yōu)閚-1；

使用Reduce函數(shù)對新的數(shù)據(jù)組進行判斷，看是否合并后的類之間達到最優(yōu)聚類，如果聚類數(shù)目未達到預定值，重新進行Map函數(shù)計算合并類，如果達到預定值則聚類結束；

刪除異常的數(shù)據(jù)點，完成所有聚類.

4 基于CURE聚類優(yōu)化算法仿真

實驗

4.1 原始數(shù)據(jù)分布

以某通信企業(yè)用戶數(shù)據(jù)為例，數(shù)據(jù)內(nèi)容包括用戶的基本信息，包括：性別、年齡、類型、行業(yè)、業(yè)務、付費方式、付費金額、月付費次數(shù)、投訴時間、投訴內(nèi)容、用戶等級、用戶狀態(tài)；消費行為信息包括：平均通話次數(shù)、本地通話時長、國內(nèi)長途通話時長、國際長途通話時間、總長途通話時長、漫游通話時長、短信條數(shù)、數(shù)據(jù)流量、其他費用、本次通話時長標準差、國內(nèi)長途通話時長標準差、國際長途通話時長標準差、漫游通話時長標準差、數(shù)據(jù)流量標準差、短信條數(shù)標準差、其他費用所占比重；用戶適用行為信息包括：用戶位置、用戶網(wǎng)絡瀏覽記錄、用戶購買記錄、用戶下載記錄、用戶上傳記錄、用戶網(wǎng)絡流量(d)、用戶網(wǎng)絡變更、用戶機型、業(yè)務適用日志.

以該通信企業(yè)2017年1～5月份數(shù)據(jù)作為挖掘對象，隨機采集1 000個用戶進行數(shù)據(jù)預處理，通過數(shù)據(jù)清洗、數(shù)據(jù)集成得到標準化數(shù)據(jù).數(shù)據(jù)采樣時間350 000 h，信息量包含用戶通話數(shù)據(jù)19 445條，短信息3 820條，交互信息284 901條.將預處理后的數(shù)據(jù)導入Matlab得到原始數(shù)據(jù)分布圖如圖2所示.

4.2 數(shù)據(jù)聚類仿真

利用Matlab按照CURE聚類優(yōu)化后的方法進行仿真，得到聚類結果如圖3所示.

圖2 大數(shù)據(jù)分布

圖3 聚類結果

將數(shù)據(jù)分為3類，獲得聚類中心分為為(0.562,0.632,0.305)，(0.625,0.360,0.661)，(0.246,0.475,0.510).

圖3中的紅色標記為第一類數(shù)據(jù)，數(shù)據(jù)具有穩(wěn)定的變化，通過對數(shù)據(jù)對應的用戶進行分析，通常此部分數(shù)據(jù)用戶為通信公司的穩(wěn)定客戶，平均入網(wǎng)時間在3 a以上，年齡層在30～40歲之間，具有穩(wěn)定的收入，能夠保持月通話時間在300 min以上，長途通過時間較長，通話時間段，投訴較少，對話費不敏感.此類用戶是該通信公司的優(yōu)質客戶，具有較好的忠誠度，若非突發(fā)事件，不會對公司業(yè)務造成較大的不穩(wěn)定因素，是長期穩(wěn)定維護基礎用戶.

圖3中的綠色標記為第二類數(shù)據(jù)，數(shù)據(jù)具有不穩(wěn)定變化特征，通過對數(shù)據(jù)對應的用戶進行分析，通常此部分數(shù)據(jù)用戶為通信公司新入網(wǎng)用戶，平均入網(wǎng)時間在6個月以下，每次繳費金額在50元以下，月通話時長50 min以下，長途通話較少.此類用戶對于通信公司來講屬于低價值用戶，用戶黏度較低.

圖3中的藍色記為第三類數(shù)據(jù)，數(shù)據(jù)具有間歇變化特征，該部分用戶入網(wǎng)時間一年以上，每次繳費金額在100～200之間，月通話時長100～200 min.此類用戶為通信公司潛在用戶，具有較大的培養(yǎng)空間.

4.3 數(shù)據(jù)聚類結果分析

通信企業(yè)部分數(shù)據(jù)聚類結果如表1所示.

表1通信企業(yè)部分數(shù)據(jù)聚類結果

數(shù)據(jù)分類 用戶序號一類數(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è)部分數(shù)據(jù)聚類結果可以清楚的劃分出每一位用戶所歸屬的分類，由此可對不同類型用戶進行針對性的服務和管理.對于不同類型數(shù)據(jù)的分析可了解到通信企業(yè)用戶對公司品牌的信賴程度，若一類數(shù)據(jù)量較大則證明該企業(yè)具有穩(wěn)定的用戶資源，一類數(shù)據(jù)增長則該公司的發(fā)展處于穩(wěn)定增長期.若二類數(shù)據(jù)量較大，則證明該企業(yè)仍較為年輕，用戶資源穩(wěn)定性不高，二類數(shù)據(jù)增長則是該公司在短期內(nèi)的營銷手段起到了一定的效果，后續(xù)應調整業(yè)務結構使用戶成為企業(yè)忠實用戶.若三類數(shù)據(jù)量較大，則證明該企業(yè)已經(jīng)有了一定的客戶基礎，需要對用戶進行更好的維護使?jié)撛谟脩舫蔀橹覍嵱脩?由表1可以看出該企業(yè)目前二類和三類數(shù)據(jù)量較多，證明企業(yè)正處于高速的發(fā)展期，企業(yè)應針對該時期制定針對性的業(yè)務，使用戶成為企業(yè)忠實的用戶資源.

從通信企業(yè)用戶數(shù)據(jù)中抽取n組數(shù)據(jù)，進行CURE聚類優(yōu)化前后時間上的對比，結果如表2所示：

表2CURE聚類優(yōu)化前后時間對比結果

nCURE聚類算法CURE聚類算法優(yōu)化10000454240000857580000124110120000168140160000204172200000245211240000288249280000326281

由表2可見，CURE算法本身在不確定數(shù)據(jù)的聚類時間上不具有優(yōu)勢，但是經(jīng)過優(yōu)化后本文所提出的CURE算法優(yōu)化在聚類時間上具有了明顯的優(yōu)勢，這也證明了此次算法的改進在聚類時間上具有較好的實用性.

再進行算法準確的比較如表3所示.

表3CURE聚類優(yōu)化前后準群性對比結果

nCURE聚類算法CURE聚類算法優(yōu)化10000659940000759580000609212000058911600005491200000759024000078892800005688

由表3可見，隨著數(shù)據(jù)量的增加，CURE算法自身的穩(wěn)定性較差，優(yōu)化后穩(wěn)定性明顯提高，而且準確率大幅度提升.

5 結 語

在互聯(lián)網(wǎng)數(shù)據(jù)爆發(fā)式增長，移動設備產(chǎn)生數(shù)據(jù)量不斷增加，網(wǎng)絡數(shù)據(jù)復雜度不斷深化的過程中，對數(shù)據(jù)的挖掘難度日益的加大，而面對不斷增長和變化的數(shù)據(jù)原有的數(shù)據(jù)挖掘算法顯然無法滿足數(shù)據(jù)復雜與多變的挖掘需求，因此本文通過比對分析后對基于CURE聚類算法進行優(yōu)化使其在一定程度上滿足變動數(shù)據(jù)挖掘的需求，介紹CURE聚類算法的基本原理和優(yōu)化方法，并闡述基于CURE聚類優(yōu)化算法的數(shù)據(jù)聚類過程，包括引入MapReduce函數(shù)，計算不確定數(shù)據(jù)間距離，采用距離區(qū)間數(shù)的方式解決邊界模糊問題，提高變動數(shù)據(jù)距離計算的準確性，梳理基于CURE聚類優(yōu)化算法的數(shù)據(jù)聚類步驟.通過以某通信企業(yè)不斷變化的用戶數(shù)據(jù)進行仿真實驗，該數(shù)據(jù)可劃分為三大類，一是用戶基本信息，二是用戶消費行為，三是用戶操作行為，三種變動類型數(shù)據(jù)通過數(shù)據(jù)預處理后倒入Matlab得到原始的數(shù)據(jù)分布圖，再通過CURE聚類優(yōu)化算法進行聚類仿真得到仿真結果，試驗證明了本文提出的以范圍約束計算變動數(shù)據(jù)類，能夠較好的對數(shù)據(jù)進行挖掘，提了高數(shù)據(jù)挖掘的準確性和數(shù)據(jù)挖掘的效率.

[1] 齊興斌，趙 麗，李雪梅.基于BIRCH聚類加速的彩色圖像增強算法[J].計算機測量與控制,2016,24(4):137-140.

[2] 向柳明，周渭博，鐘 勇.基于高斯過程的CLIQUE改進算法[J].計算機應用,2015(s2):85-87.

[3] 張曉琳，崔寧寧，楊 濤，等.一種分層自適應快速K-means算法[J].計算機應用研究,2016,33(2):421-423.

[4] 李 松，崔環(huán)宇，張麗平，經(jīng)海東.基于CURE聚類算法的靜態(tài)R樹構建方法[J].計算機科學,2015,42(10):193-197.

[5] 高長元，王海晶，王 京.基于改進CURE算法的不確定性移動用戶數(shù)據(jù)聚類[J].計算機工程與科學,2016,38(4):768-774.

[6] 王寅同，王建東，陳海燕，等.一種代表點的近似折半層次聚類算法[J].小型微型計算機系統(tǒng),2015,36(2):215-219.

[7] 倪志偉，荊婷婷，倪麗萍.一種近鄰傳播的層次優(yōu)化算法[J].計算機科學,2015,42(3):195-200.

[8] 王志春.初始中心點優(yōu)化的K-means聚類模型[J].電腦迷,2016(9):50-51.

[9] 伍育紅.聚類算法綜述[J].計算機科學,2015,42(s1):491-499,524.

[10] 陳 曉，趙晶玲.大數(shù)據(jù)處理中混合型聚類算法的研究與實現(xiàn)[J].信息網(wǎng)絡安全,2015(4):45-49.