【摘要】針對數(shù)據(jù)量大、含有噪聲、屬性變量較多的數(shù)據(jù)集群，提出了一種基于消除噪聲的聚類算法。該算法對數(shù)據(jù)進行分析及預(yù)處理，接著進行消除噪聲處理，之后采用改進聚類算法對數(shù)據(jù)集進行聚類分析。在實驗中，采用10 000條移動用戶的手機數(shù)據(jù)，對通常的聚類方法和消除噪聲后的改進聚類算法進行分析比較，發(fā)現(xiàn)改進后的算法效率更高、準確度也更好。根據(jù)聚類后的數(shù)據(jù)總結(jié)分析移動用戶對新業(yè)務(wù)的使用情況，將有助于指導(dǎo)業(yè)務(wù)的開展。

【關(guān)鍵詞】聚類算法消除噪聲手機用戶行為

中圖分類號：TP392文獻標識碼：A文章編號：1006-1010(2014)-07-0036-04

1 概述

根據(jù)用戶的行為數(shù)據(jù)對客戶群體進行細分，從而采取不同的營銷策略，是目前各通信運營商常用的業(yè)務(wù)推廣方式[1-2]。對行為數(shù)據(jù)篩選聚類質(zhì)量的高低，往往對細分人群特征提取起到?jīng)Q定性作用。一些常用的聚類算法，需結(jié)合通信行業(yè)服務(wù)特點，進行專門的優(yōu)化和改進，借此提高客戶識別率和命中率，從而幫助企業(yè)更好地制定相關(guān)營銷策略，差異化服務(wù)相應(yīng)客戶。

本文提出了一種消除噪聲的聚類算法來分析手機用戶的行為，該方法針對手機用戶的數(shù)據(jù)特點進行除噪再聚類，使得分析后的結(jié)果更準確，效率也更高。

2 除噪模塊的提出

由于采集到的實際數(shù)據(jù)比較零散，不適合直接進行分析[3-4]；為此，本文首先對收集到的數(shù)據(jù)進行一系列處理，合成ARFF格式的文件，然后使用K-Means算法進行數(shù)據(jù)挖掘的處理操作。

然而，在對手機用戶行為進行分析時，K-Means算法有幾個不適宜之處：

第一，K-Means算法要求先定義簇的平均值再進行使用[5-6]，而這對于有分類屬性的數(shù)據(jù)是不太適宜的。因為，如果用戶事先給出k（要生成的簇的數(shù)目），那么對于不同的初始值，就會得出不同的聚類結(jié)果，這樣就使得對初始值的選取十分敏感。

第二，K-Means算法對于凸面形狀的簇，以及屬性大小差別很大的簇識別能力有限；那么在手機用戶群體屬性差異較大時，會產(chǎn)生較大的誤差。

第三，K-Means算法對于“噪聲”和孤立點數(shù)據(jù)十分敏感，少量的該類數(shù)據(jù)會對平均值產(chǎn)生極大影響。

因此，本文加入“除噪模塊”對數(shù)據(jù)進行處理，這樣可以提高效率和準確率。

3 消除噪聲的改進聚類算法的實現(xiàn)

3.1除噪聚類算法描述

為了能快速方便地處理大量數(shù)據(jù)，又要盡量減弱數(shù)據(jù)庫中噪聲點對聚類分析帶來的不利影響，本文將兩種算法相結(jié)合，即結(jié)合處理噪聲數(shù)據(jù)源效果較好的DBSCAN算法與操作快速簡便的K-Means算法，先利用前者對數(shù)據(jù)源文件進行除噪處理，再利用后者進行聚類分析。

（1）算法1：除噪聚類算法

輸入：簇的數(shù)目k，包含n個對象的數(shù)據(jù)庫，鄰域半徑ε，最小數(shù)目MinPts；

輸出：k個簇，使平方誤差準則最小。

過程：

Step1 調(diào)用DBSCAN算法對數(shù)據(jù)中的噪聲事件進行判斷和挖掘；

Step2對Step1產(chǎn)生的噪聲進行處理；

Step3 對處理噪聲后的數(shù)據(jù)，采用K-Means進行聚類分析；

Step4 K-Means采用不同的k值得到平方誤差準則最小的分類。

（2）算法2：DBSCAN算法

Algorithm DBSCAN(D, ε, MinPts)//初始時所有對象沒有進行分類

輸入：包含n個數(shù)據(jù)對象的數(shù)據(jù)庫D，鄰域半徑ε，最小數(shù)目MinPts；

輸出：所有生成的簇，達到密度要求。

過程：

REPEAT

從數(shù)據(jù)庫中找出一個未處理過的點；

IF 抽出的事核心點

THEN 找出所有從該點密度可達的對象，形成一個簇；

ELSE 抽出的點是邊緣點（非核心對象），跳出本次循環(huán)，尋找下一點；

UNTIL 所有的點都被處理。

3.2除噪算法分析

本算法是一個嵌套算法，是兩種不同聚類算法的結(jié)合。以下對算法的性能進行分析：

（1）空間復(fù)雜度分析

假設(shè)數(shù)據(jù)集D包含n個數(shù)據(jù)對象。若沒有索引，在查詢數(shù)據(jù)集中的某個點時，都要遍歷整個數(shù)據(jù)集，因此時間復(fù)雜度是O(n2)；若使用索引，那么遍歷操作的時間復(fù)雜度可降為O(nlgn)。

解釋：

∵R*樹的高度是O(lgn)，而ε鄰域相對于整個數(shù)據(jù)空間很小，當查詢樹的有限分支時，對此“小”區(qū)域查詢的平均耗時即為O(lgn)；

又∵對于數(shù)據(jù)集中的每個點，算法至多只需執(zhí)行一次“小”區(qū)域查詢；

∴使用R*樹索引使得算法的時間復(fù)雜度降為O(lgn)。

（2）算法特點分析

①優(yōu)點：DBSCAN算法能夠把具有足夠高密度的區(qū)域劃分為簇，同時可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)滿足指定條件的聚類。

②缺點：對內(nèi)存要求高，輸入?yún)?shù)敏感，數(shù)據(jù)要求分布均勻。

3.3除噪算法改進

考慮到除噪算法有上述缺點，筆者提出改進后的除噪算法如下：

（1）使用R*樹索引。構(gòu)造R*樹，使用索引，從而將數(shù)據(jù)處理的時間復(fù)雜度降為O(nlgn)，降低該算法對內(nèi)存的要求；

（2）試探性確定合理的參數(shù)ε和MinPts。

在一般情況下，為減少運算量，可以固定ε和MinPts中任意一個參數(shù)的值[7-9]，而根據(jù)需要確定另一個參數(shù)的值。若固定MinPts值，根據(jù)較密的那些類來選取較小的ε值，那么就可以使得位于相對較稀的那些類中的對象，減少鄰域中的數(shù)據(jù)對象的數(shù)目，當該數(shù)目小于MinPts時，將這些對象定義為噪聲點，這樣就避免了分布較稀的類中的對象被分成多個性質(zhì)相似的類。反之，根據(jù)較稀的那些類的性質(zhì)確定一個較大的ε值，這樣離得近且密度大的那些類之間的差異也就會被忽略，它們即可合并為同一個類。

4 實驗和結(jié)果分析

4.1消除噪聲的改進聚類算法

在中國移動某分公司提供的數(shù)據(jù)中，共針對153個屬性進行篩選，選擇其中的30個屬性作為重點進行研究。在原始數(shù)據(jù)經(jīng)過處理后，得到本文研究所需的weka數(shù)據(jù)文件，該文件中包含了30個屬性值的10 000條記錄。

（1）消除噪聲的改進聚類算法的實現(xiàn)過程

①發(fā)現(xiàn)噪聲實例

由于在數(shù)據(jù)庫實例的采集過程中，可能會有一些數(shù)據(jù)采集誤差和數(shù)據(jù)預(yù)處理的錯誤操作，數(shù)據(jù)中存在著可以稱得上“噪聲”的實例。為了進行更準確的數(shù)據(jù)挖掘，需要先對這些噪聲進行處理，然后在消除噪聲的基礎(chǔ)上進行數(shù)據(jù)挖掘，提高數(shù)據(jù)挖掘效率。

測試條件：利用DBSCAN算法發(fā)現(xiàn)數(shù)據(jù)中潛在的噪聲實例，選取參數(shù)ε=0.8，MinPts=4。

結(jié)果分析：觀察運行結(jié)果可知，實例數(shù)目為10 000，屬性個數(shù)為30，生成2個聚類，運行時間為549.8s；同時，該算法運行結(jié)果中，被判斷為噪聲的實例數(shù)目為8。

②消除噪聲實例

對源文件中的實例進行篩選，找出運行結(jié)果為噪聲的實例并刪除，在刪除被判斷為噪聲的8個實例后，保存為文件finally.arff，即為刪除噪聲后的數(shù)據(jù)文件。該文件中含有實例9 992個，屬性數(shù)為30。

③除噪后聚類分析

針對文件finally.arff，再次利用K-Means算法進行聚類分析。

（2）兩種模塊對比

對兩種模塊分別用K-Means算法進行聚類分析，其中設(shè)置“numClusters”為6，即k=6。從兩種不同模塊的運行結(jié)果中不難看出，噪聲是影響數(shù)據(jù)挖掘質(zhì)量的一個重要因素，在消除噪聲后，迭代次數(shù)從29次減到5次，簇內(nèi)的誤差平方和也有一定程度的降低，從而驗證了消除噪聲后再進行數(shù)據(jù)挖掘的必要性，見表1：

endprint

表1噪聲消除前后K-Means算法性能參數(shù)對比表

類型 迭代次數(shù) 簇內(nèi)的誤差平方和

未消除噪聲 29 1 722.186 132 049 162 3

消除噪聲 5 1 484.293 250 367 957 9

4.2手機用戶群體行為分析

根據(jù)上述改進的聚類算法，本文對10 000份移動用戶消費數(shù)據(jù)進行分析，由4.1節(jié)的分析得知刪除噪聲后的數(shù)據(jù)文件中含有實例樣本9 992個。本文按照年齡段進行劃分，針對移動新近推出的幾類新業(yè)務(wù)進行聚類分析，得到如圖1所示的結(jié)果。

聚類依據(jù)：

◆上網(wǎng)本用戶：流量使用達到每月10M以上；

◆電子渠道用戶：訪問網(wǎng)上營業(yè)廳1次以上；

◆手機報用戶：每月定制3種以上手機報業(yè)務(wù)；

◆彩鈴用戶：自行下載3條以上彩鈴；

◆短信用戶：點對點短信每月250條以上。

由聚類結(jié)果可知，根據(jù)用戶年齡層次劃分，每類用戶間的消費狀況基本相似，因此營銷策劃首先應(yīng)根據(jù)年齡段進行規(guī)劃。圖2總結(jié)了根據(jù)圖1的聚類結(jié)果進行分析的手機用戶群體行為以及提升方案：

從上述分析可以看出，移動業(yè)務(wù)的使用帶有一定的群體行為；那么在制定和推廣業(yè)務(wù)時，運營商應(yīng)考慮到群體的特點，推出相應(yīng)的特色業(yè)務(wù)，以吸引更多的客戶。

5 總結(jié)

對于數(shù)據(jù)量大、含有噪聲、屬性變量較多數(shù)據(jù)分析的問題，往往采用數(shù)據(jù)挖掘的方法，但需要根據(jù)數(shù)據(jù)自身的特點選擇合適的方法。本文主要討論手機用戶的群體行為，根據(jù)其特點提出了去除噪聲后的聚類算法，該方法避免了一些噪聲點對整體數(shù)據(jù)分析的影響，從而能更好地指導(dǎo)對手機用戶行為的分析。

參考文獻：

[1] 唐曉蘭,劉中臨,劉嘉勇. 一種基于知識庫的行為特征檢測模型[J]. 信息安全與通信保密, 2012(2): 78-82.

[2] 孫燕花,李杰,李建. 基于CURE算法的網(wǎng)絡(luò)用戶行為分析[J]. 計算機技術(shù)與發(fā)展, 2011,21(9): 35-38.

[3] 牛紅惠,徐甜. 基于聚類粒子群算法網(wǎng)絡(luò)異常檢測模型研究[J]. 微電子學(xué)與計算機, 2012,29(3): 102-105.

[4] 許瓊來,唐守廉. 3G時代移動用戶市場細分研究[J]. 移動通信, 2008(1): 71-74.

[5] 李丹,劉雁. 從用戶消費偏好出發(fā)淺析移動增值業(yè)務(wù)營銷策略[J]. 移動通信, 2007(7): 89-92.

[6] 朱旭東,劉志鏡. 基于主題隱馬爾科夫模型的人體異常行為識別[J]. 計算機科學(xué), 2012,39(3): 251-257.

[7] 吳斌,鄭毅,傅偉鵬,等. 一種基于群體智能的客戶行為分析算法[J]. 計算機學(xué)報, 2003,26(8): 913-918.

[8] Eduardo Ares M, Parapar Javier, Barreiro Alvaro. An experimental study of constrained clustering effectiveness in presence of erroneous constraints[J]. Information Processing & Management, 2011,48(3): 537-551.

[9] Guerra L, Robles V, Bielza C. A comparison of clustering quality indices using outliers and noise[J]. Intelligent Data Analysis, 2012,16(4): 703-715.★

作者簡介

顧強：碩士畢業(yè)于南京郵電大學(xué)，現(xiàn)就職于中國移動通信集團江蘇有限公司，研究方向為數(shù)據(jù)倉庫、經(jīng)營分析、數(shù)據(jù)挖掘等。

endprint

表1噪聲消除前后K-Means算法性能參數(shù)對比表

類型 迭代次數(shù) 簇內(nèi)的誤差平方和

未消除噪聲 29 1 722.186 132 049 162 3

消除噪聲 5 1 484.293 250 367 957 9

4.2手機用戶群體行為分析

根據(jù)上述改進的聚類算法，本文對10 000份移動用戶消費數(shù)據(jù)進行分析，由4.1節(jié)的分析得知刪除噪聲后的數(shù)據(jù)文件中含有實例樣本9 992個。本文按照年齡段進行劃分，針對移動新近推出的幾類新業(yè)務(wù)進行聚類分析，得到如圖1所示的結(jié)果。

聚類依據(jù)：

◆上網(wǎng)本用戶：流量使用達到每月10M以上；

◆電子渠道用戶：訪問網(wǎng)上營業(yè)廳1次以上；

◆手機報用戶：每月定制3種以上手機報業(yè)務(wù)；

◆彩鈴用戶：自行下載3條以上彩鈴；

◆短信用戶：點對點短信每月250條以上。

由聚類結(jié)果可知，根據(jù)用戶年齡層次劃分，每類用戶間的消費狀況基本相似，因此營銷策劃首先應(yīng)根據(jù)年齡段進行規(guī)劃。圖2總結(jié)了根據(jù)圖1的聚類結(jié)果進行分析的手機用戶群體行為以及提升方案：

從上述分析可以看出，移動業(yè)務(wù)的使用帶有一定的群體行為；那么在制定和推廣業(yè)務(wù)時，運營商應(yīng)考慮到群體的特點，推出相應(yīng)的特色業(yè)務(wù)，以吸引更多的客戶。

5 總結(jié)

對于數(shù)據(jù)量大、含有噪聲、屬性變量較多數(shù)據(jù)分析的問題，往往采用數(shù)據(jù)挖掘的方法，但需要根據(jù)數(shù)據(jù)自身的特點選擇合適的方法。本文主要討論手機用戶的群體行為，根據(jù)其特點提出了去除噪聲后的聚類算法，該方法避免了一些噪聲點對整體數(shù)據(jù)分析的影響，從而能更好地指導(dǎo)對手機用戶行為的分析。

參考文獻：

[1] 唐曉蘭,劉中臨,劉嘉勇. 一種基于知識庫的行為特征檢測模型[J]. 信息安全與通信保密, 2012(2): 78-82.

[2] 孫燕花,李杰,李建. 基于CURE算法的網(wǎng)絡(luò)用戶行為分析[J]. 計算機技術(shù)與發(fā)展, 2011,21(9): 35-38.

[3] 牛紅惠,徐甜. 基于聚類粒子群算法網(wǎng)絡(luò)異常檢測模型研究[J]. 微電子學(xué)與計算機, 2012,29(3): 102-105.

[4] 許瓊來,唐守廉. 3G時代移動用戶市場細分研究[J]. 移動通信, 2008(1): 71-74.

[5] 李丹,劉雁. 從用戶消費偏好出發(fā)淺析移動增值業(yè)務(wù)營銷策略[J]. 移動通信, 2007(7): 89-92.

[6] 朱旭東,劉志鏡. 基于主題隱馬爾科夫模型的人體異常行為識別[J]. 計算機科學(xué), 2012,39(3): 251-257.

[7] 吳斌,鄭毅,傅偉鵬,等. 一種基于群體智能的客戶行為分析算法[J]. 計算機學(xué)報, 2003,26(8): 913-918.

[8] Eduardo Ares M, Parapar Javier, Barreiro Alvaro. An experimental study of constrained clustering effectiveness in presence of erroneous constraints[J]. Information Processing & Management, 2011,48(3): 537-551.

[9] Guerra L, Robles V, Bielza C. A comparison of clustering quality indices using outliers and noise[J]. Intelligent Data Analysis, 2012,16(4): 703-715.★

作者簡介

顧強：碩士畢業(yè)于南京郵電大學(xué)，現(xiàn)就職于中國移動通信集團江蘇有限公司，研究方向為數(shù)據(jù)倉庫、經(jīng)營分析、數(shù)據(jù)挖掘等。

endprint

表1噪聲消除前后K-Means算法性能參數(shù)對比表

類型 迭代次數(shù) 簇內(nèi)的誤差平方和

未消除噪聲 29 1 722.186 132 049 162 3

消除噪聲 5 1 484.293 250 367 957 9

4.2手機用戶群體行為分析

根據(jù)上述改進的聚類算法，本文對10 000份移動用戶消費數(shù)據(jù)進行分析，由4.1節(jié)的分析得知刪除噪聲后的數(shù)據(jù)文件中含有實例樣本9 992個。本文按照年齡段進行劃分，針對移動新近推出的幾類新業(yè)務(wù)進行聚類分析，得到如圖1所示的結(jié)果。

聚類依據(jù)：

◆上網(wǎng)本用戶：流量使用達到每月10M以上；

◆電子渠道用戶：訪問網(wǎng)上營業(yè)廳1次以上；

◆手機報用戶：每月定制3種以上手機報業(yè)務(wù)；

◆彩鈴用戶：自行下載3條以上彩鈴；

◆短信用戶：點對點短信每月250條以上。

由聚類結(jié)果可知，根據(jù)用戶年齡層次劃分，每類用戶間的消費狀況基本相似，因此營銷策劃首先應(yīng)根據(jù)年齡段進行規(guī)劃。圖2總結(jié)了根據(jù)圖1的聚類結(jié)果進行分析的手機用戶群體行為以及提升方案：

從上述分析可以看出，移動業(yè)務(wù)的使用帶有一定的群體行為；那么在制定和推廣業(yè)務(wù)時，運營商應(yīng)考慮到群體的特點，推出相應(yīng)的特色業(yè)務(wù)，以吸引更多的客戶。

5 總結(jié)

對于數(shù)據(jù)量大、含有噪聲、屬性變量較多數(shù)據(jù)分析的問題，往往采用數(shù)據(jù)挖掘的方法，但需要根據(jù)數(shù)據(jù)自身的特點選擇合適的方法。本文主要討論手機用戶的群體行為，根據(jù)其特點提出了去除噪聲后的聚類算法，該方法避免了一些噪聲點對整體數(shù)據(jù)分析的影響，從而能更好地指導(dǎo)對手機用戶行為的分析。

參考文獻：

[1] 唐曉蘭,劉中臨,劉嘉勇. 一種基于知識庫的行為特征檢測模型[J]. 信息安全與通信保密, 2012(2): 78-82.

[2] 孫燕花,李杰,李建. 基于CURE算法的網(wǎng)絡(luò)用戶行為分析[J]. 計算機技術(shù)與發(fā)展, 2011,21(9): 35-38.

[3] 牛紅惠,徐甜. 基于聚類粒子群算法網(wǎng)絡(luò)異常檢測模型研究[J]. 微電子學(xué)與計算機, 2012,29(3): 102-105.

[4] 許瓊來,唐守廉. 3G時代移動用戶市場細分研究[J]. 移動通信, 2008(1): 71-74.

[5] 李丹,劉雁. 從用戶消費偏好出發(fā)淺析移動增值業(yè)務(wù)營銷策略[J]. 移動通信, 2007(7): 89-92.

[6] 朱旭東,劉志鏡. 基于主題隱馬爾科夫模型的人體異常行為識別[J]. 計算機科學(xué), 2012,39(3): 251-257.

[7] 吳斌,鄭毅,傅偉鵬,等. 一種基于群體智能的客戶行為分析算法[J]. 計算機學(xué)報, 2003,26(8): 913-918.

[8] Eduardo Ares M, Parapar Javier, Barreiro Alvaro. An experimental study of constrained clustering effectiveness in presence of erroneous constraints[J]. Information Processing & Management, 2011,48(3): 537-551.

[9] Guerra L, Robles V, Bielza C. A comparison of clustering quality indices using outliers and noise[J]. Intelligent Data Analysis, 2012,16(4): 703-715.★

作者簡介

顧強：碩士畢業(yè)于南京郵電大學(xué)，現(xiàn)就職于中國移動通信集團江蘇有限公司，研究方向為數(shù)據(jù)倉庫、經(jīng)營分析、數(shù)據(jù)挖掘等。

endprint