兩種聚類算法在網站用戶細分中的比較

肖亞鐵 柳亞飛 李魯群 李哲敏

摘要：

給出了K-means算法和層次聚類算法在具體網站用戶細分中準確率的比較，在細分網站用戶這一類問題中，K-means算法在聚類準確率和處理速度上具有較大的優勢，能夠滿足網站用戶細分準確率的基本要求，其聚類準確率達到95%左右，且K-means算法處理速度比較快;層次聚類算法的處理速度較K-means算法慢，且其聚類準確率在處理大量用戶數據時低于92%，這對于處理網站用戶數據這類信息并不具備優勢.

關鍵詞：

聚類算法; 層次; 用戶細分; 準確率

中圖分類號： TP 391.4文獻標志碼： A文章編號： 1000-5137（2018）01-0049-04

Comparison of two clustering algorithms in website user segmentation

Xiao Yatie1， Liu Yafei1， Li Luqun1*， Li Zhemin2

（1.The College of Information and Mechanical Engineering，Shanghai Normal University，Shanghai 200234，China;

2.Music College，Shanghai Normal University，Shanghai 200234，China）

Abstract：

In this paper，we compare the accuracy of K-means algorithm and Hierarchical clustering algorithm in specific website user segmentation.Among the problems of subdividing website users，K-means algorithm has the advantage of accuracy and processing speed The advantages of this algorithm are that it can meet the basic requirements of website user segmentation accuracy，the clustering accuracy is about 95%，and K-means algorithm is faster;Hierarchical clustering algorithm is slower than K-means algorithm，And its clustering accuracy is less than 92% when processing a large amount of user data，which is not advantageous for processing information such as website user data.

Key words：

clustering algorithm; hierarchy; user segmentation; accuracy

收稿日期： 2016-06-21

作者簡介： 肖亞鐵（1989-），男，碩士研究生，主要從事計算機網絡以及大數據方面的研究.E-mail：gayani@163.com

導師簡介： 李魯群（1967-），男，教授，主要從事計算機網絡以及應用技術方面的研究.E-mail：luqunli@gmail.com

*通信作者

引用格式： 肖亞鐵，柳亞飛，李魯群，等.兩種聚類算法在網站用戶細分中的比較 [J].上海師范大學學報（自然科學版），2018，47（1）：49-52.

Citation format： Xiao Y T，Liu Y F，Li L Q，et al.Comparison of two clustering algorithms in website user segmentation [J].Journal of Shanghai Normal University（Natural Sciences），2018，47（1）：49-52.

對網站用戶細分的方法中[1-3]，聚類方式[4-8]在細分方向上的效果比較好.一般而言，聚類分析方法是將數據或者數據集的特征相關性利用某種分析算法及其組合規則進行分組[8-9]，聚類方式的目的是將數據集中的不同類別對象盡可能地區別開來，使同一類別中的對象盡可能相似.聚類分析是一種無監督自學習方法，可以智能地進行數據集的分析、劃分，因此它在模式識別、特征提取、圖像分割和數據挖掘等領域應用廣泛.目前層次聚類算法[10-13]以及K-means算法[14-15]是細分領域常用的聚類算法，在此基礎上衍生出來的算法同樣應用廣泛.MacQueen在1967年提出的K-means算法[2，4-5，14-15]是進行客戶細分問題的一種經典算法，該算法簡單且分類速度較快.層次聚類方法對給定的數據對象集合進行層次的分解，按照層次聚類的形成方式，層次方法可以分為凝聚和分裂方法.整個聚類過程不管是利用K-means方式還是層次聚類方式，聚類過程均會按照之前設定的規則終結.

本文作者利用兩類聚類算法對某網站用戶類型進行細分，對已有的1 000個用戶數據進行聚類.利用K-means聚類算法和層次（凝聚）聚類算法得到的實驗數據和已有的數據進行比較，從準確率和趨勢評判出更適宜處理這一類數據量大，要求細分精確的數據集的方法，從而給網站的運營提供更加準確的導向.

1基于K-Means算法的用戶細分算法

1.1K-means 算法聚類過程

首先從n個數據對象集任意選擇設置k個對象作為初始聚類中心，將剩余對象分配給與其最相似的聚類，然后再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值），不斷重復這一過程直到標準測度函數開始收斂為止，一般都采用均方差作為標準測度函數.

1.2聚類仿真

圖1用戶數據圖

仿真平臺為Matlab2010，硬件設備：CPU：Intel（R） Core（TM） i5-430 @2.27 GHz;硬盤：希捷 Momentus 500 GB.對某網站的1 000個用戶的發帖量和在線時長兩個指標數據進行提取，將用戶類型定義為：一般用戶、中級用戶和高級用戶，如圖1所示.

圖2K-means算法準確率曲線圖

根據K-means算法，K定為3，測試用的數據量分別為3、13、21、30、45、69、81、90、120、159、200、300、400、500、600、700、800、900、1 000等，在圖1中所表示的為相應的發帖量（橫坐標）和在線時長（h）.經過K-means算法聚類后，得到的數據與原數據進行比較，可以得到準確率與數據量的曲線如圖2所示.

由圖2可知，當用戶量少于100時，準確率在91%～100%之間波動，并且波動幅度較大;當用戶量大于100時，準確率在94%～96%之間波動，波動范圍小，且有平穩趨勢.可以預測，利用該聚類算法區分析大量網站用戶相關數據時，K-means算法有較好的分析效果[6]，準確率基本維持在94%～96%之間，可以滿足網站對于其用戶類型分析的要求.

2基于層次聚類的用戶細分算法

2.1層次聚類（凝聚）過程

假定有N個對象要被聚類[8-10]，其N×N維距離矩陣D=[d（i，j）]，i，j=0，1，2，3…n-1，d（i，j）為對象i與對象j之間的距離，設L（m）為第m次聚類的層次[10-11]，d[（i），（j）]為相似度.最小距離方法基本過程如下：

（1） 將每個對象歸為一類，共得到N類，每類僅包含一個對象.類與類之間的距d（i，j），L（0）=0，m=0;

（2） 找到d[（r），（s）]=min d（i，j），將對象r，s合并成一類，總的類數減少一個，刪除r與s的行列;

（3） 重新計算新的類與所有舊類之間的d（i，j），選擇距離最小的值作為兩個簇之間的相似度;

（4） 重復第2步和第3步，直到最后合并成一個類為止或者達到某個終止條件[11-12].

2.2聚類仿真

圖3用戶數據圖

仿真環境與K-means算法實驗相同，對網站用戶的發帖量和在線時長兩個指標數據進行提取，并將網站用戶類型定義為：一般用戶、中級用戶和高級用戶，如圖3所示.

圖4層次聚類算法準確率曲線圖

測試用的數據量分別為3、13、21、30、45、69、81、90、120、159、200、300、400、500、600、700、800、900、1 000.經過層次聚類后，得到的數據與原數據進行比較，可以得到準確率與數據量的曲線圖如圖4所示.

從圖4可以看出，當輸入的數據量小于100時，層次聚類算法準確率在86%～100%之間波動，波動范圍很大;當輸入的數據量大于100時，準確率在90%～92%之間波動，波動幅度小，且趨于平穩.可以預測，該層次分類算法對于處理大量關于網站用戶相關數據時，其數據分析的準確率基本在90%～92%之間波動，較K-means算法的準確率低[5，7].

3結論

本文作者給出了K-means算法和層次聚類算法在具體網站用戶細分中準確率的比較.從兩種聚類效果來看，初次選擇輸入數據的順序和數量會影響到聚類的準確率，但當輸入大量數據進行聚類時，數據本身的輸入順序對準確率的影響不是很明顯，可以看出在細分網站用戶這一類問題中，K-means算法在聚類準確率和處理速度上具有較大的優勢，能夠滿足網站用戶細分準確率的基本要求，其聚類準確率能夠達到95%左右，且K-means算法處理速度比較快;層次凝聚聚類算法的處理速度較K-means算法處理速度慢，且其聚類準確率在處理大量用戶數據時低于92%，這對于處理網站用戶數據信息這類數據大的信息時并不具備優勢.因此利用合理的聚類算法，能準確地分析和劃分出網站用戶的類型，從而可以給某類用戶群體推送相應的知識信息，擴大相應的影響，繼而為網站的總體運營提供較好的指向.

參考文獻：

[1]吳斌，鄭毅，傅偉鵬，等.一種基于群體智能的客戶行為分析算法 [J].計算機學報，2003，26（8）：913-918.

Wu B，Zhen Y，Fu W P，et al.A customer behavior analysis algorithm based on swarm intelligence [J].Chinese Journal of Computer，2003，26（8）：913-918.

[2]詹海亮，薛惠鋒，蘇錦旗.基于人工免疫系統的克隆-K均值算法 [J].計算機仿真，2008，25（11）：191-194.

Zhan H L，Xie H F，Su J Q.A cloning-K-means algorithm based on artificial immune system [J].Computer Simulation，2008，25（11）：191-194.

[3]王濤，卿鵬，魏迪，等.基于聚類分析的進程拓撲映射優化 [J].計算機學報，2014，38（5）：1044-1055.

Wang T，Qing P，Wei D，et al.Optimization of process-to-core mapping based on clustering analysis [J].Chinese Journal of Computer，2014，38（5）：1044-1055.

[4]Kuo R J，Ho L M，Hu C M.Cluster analysis in industrial market segmentation through artificial neural network [J].Computers and Industrial Engineering，2002，42（2）：391-399.

[5]張光建，黃賢英.基于最小聚類單元的聚類算法研究及其在CRM 中的應用 [J].計算機科學，2006，33（7）：188-190.

Zhang G J，Huang X Y.Study on a New clustering algorithm based on minimum clustering cell and its application in CRM [J].Computer Science，2006，33（7）：188-190.

[6]Sambasivam S.Advanced data clustering methods of mining Web documents [J].Issues in Informing Science and Information Technology，2006，8（3）：563-579.

[7]Carpenter G A，Grossberg S.ART2：stable self-organization of pattern recognition codes for analog input patterns [C].Proceedings of the 1st International Conference on Neural Networks，New York：IEEE，1987.

[8]王博，彭玉濤，羅超.基于模糊聚類廣義回歸神經網絡的網絡入侵研究 [J].江西師范大學學報（自然科學版），2012，36（3）：288-291.

Wang B，Peng Y T，Luo Chao.The clusting research for net attack based on fuzzy clustering and GRNN [J].Journal of Jiangxi Normal University （Natural Science），2012，36（3）：288-291.

[9]陳克寒，韓盼盼，吳健. 基于用戶聚類的異構社交網絡推薦算法 [J].計算機學報，2013，36（2）：349-359.

Chen K H，Han P P，Wu J.User clustering based social network recommendation [J].Chinese Journal of Computer，2013，36（2）：349-359.

[10]栗曉聰，滕少華.頻繁項集挖掘的Apriori改進算法研究 [J].江西師范大學學報（自然科學版），2011，35（5）：498-502.

Li X C，Teng S H.The Research on improvement of Apriori algorithm based on mining frequent itemsets [J].Journal of Jiangxi Normal University （Natural Science），2011，35（5）：498-502.

[11]段明秀.層次聚類算法的研究及應用 [D].長沙：中南大學，2009.

[12]Zhang N，Tian Y Y，Patel J M.Discovery driven graph summarization [C].Proceedings of the Data Engineering，Long Beach：IEEE，2010.

[13]高靈渲，張巍，霍穎翔，等.改進的聚類模式過濾推薦算法 [J].江西師范大學學報（自然科學版），2012，36（1）：106-110.

Gao L X，Zhang W，Huo Y X，et al.Improved clustering filtering recommendation algorithm [J].Journal of Jiangxi Normal University （Natural Science），2012，36（1）：106-110.

[14]樊寧.K均值聚類算法在銀行客戶細分中的研究 [J].計算機仿真，2011，28（3）：369-372.

Fan N.Simulation study on commercial bank customer segmentation on K-means clustering algorithm [J].Computer Simulation，2011，28（3）：369-372.

[15]袁方，周志勇，宋鑫.初始聚類中心優化的K-均值算法 [J].計算機工程，2007，33（3）：65-66.

Yuan F，Zhou Z Y，Song X.K-means clustering algorithm with meliorated initial center [J].Computer Engineering，2007，33（3）：65-66.