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

摘要：

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

關(guān)鍵詞：

聚類算法; 層次; 用戶細分; 準(zhǔn)確率

中圖分類號： TP 391.4文獻標(biāo)志碼： 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-），男，碩士研究生，主要從事計算機網(wǎng)絡(luò)以及大數(shù)據(jù)方面的研究.E-mail：gayani@163.com

導(dǎo)師簡介： 李魯群（1967-），男，教授，主要從事計算機網(wǎng)絡(luò)以及應(yīng)用技術(shù)方面的研究.E-mail：luqunli@gmail.com

*通信作者

引用格式： 肖亞鐵，柳亞飛，李魯群，等.兩種聚類算法在網(wǎng)站用戶細分中的比較 [J].上海師范大學(xué)學(xué)報（自然科學(xué)版），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.

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

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

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

1.1K-means 算法聚類過程

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

1.2聚類仿真

圖1用戶數(shù)據(jù)圖

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

圖2K-means算法準(zhǔn)確率曲線圖

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

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

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之間的距離，設(shè)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合并成一類，總的類數(shù)減少一個，刪除r與s的行列;

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

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

2.2聚類仿真

圖3用戶數(shù)據(jù)圖

仿真環(huán)境與K-means算法實驗相同，對網(wǎng)站用戶的發(fā)帖量和在線時長兩個指標(biāo)數(shù)據(jù)進行提取，并將網(wǎng)站用戶類型定義為：一般用戶、中級用戶和高級用戶，如圖3所示.

圖4層次聚類算法準(zhǔn)確率曲線圖

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

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

3結(jié)論

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

參考文獻：

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

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

[2]詹海亮，薛惠鋒，蘇錦旗.基于人工免疫系統(tǒng)的克隆-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]王濤，卿鵬，魏迪，等.基于聚類分析的進程拓撲映射優(yōu)化 [J].計算機學(xué)報，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 中的應(yīng)用 [J].計算機科學(xué)，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īng)網(wǎng)絡(luò)的網(wǎng)絡(luò)入侵研究 [J].江西師范大學(xué)學(xué)報（自然科學(xué)版），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]陳克寒，韓盼盼，吳健. 基于用戶聚類的異構(gòu)社交網(wǎng)絡(luò)推薦算法 [J].計算機學(xué)報，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].江西師范大學(xué)學(xué)報（自然科學(xué)版），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]段明秀.層次聚類算法的研究及應(yīng)用 [D].長沙：中南大學(xué)，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].江西師范大學(xué)學(xué)報（自然科學(xué)版），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]袁方，周志勇，宋鑫.初始聚類中心優(yōu)化的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.