張?zhí)煊?，諶志群，黃孝喜, 王榮波

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

基于改進(jìn)CFSFDP算法的電信投訴文本聚類方法

張?zhí)煊?，諶志群，黃孝喜, 王榮波

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

為了提高電信服務(wù)質(zhì)量，增強(qiáng)企業(yè)競爭力，對電信投訴文本進(jìn)行聚類，方便電信運(yùn)營商分析投訴原因，文中提出了基于改進(jìn)CFSFDP算法對電信投訴文本進(jìn)行聚類的方法。通過差分進(jìn)化算法尋找CFSFDP算法中最優(yōu)密度閾值和距離閾值，降低密度及距離閾值的隨機(jī)性選取對聚類準(zhǔn)確率造成的影響。該算法使用Gaussian Kernel計(jì)算數(shù)據(jù)點(diǎn)密度，降低參數(shù)對密度計(jì)算的影響。在電信投訴文本數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果顯示，改進(jìn)CFSFDP算法聚類結(jié)果達(dá)到了與K-Means算法、CFSFDP算法、Agglomerative Clustering算法更好或者相當(dāng)?shù)男Ч?，證明了算法的有效性。

CFSFDP算法；文本聚類；電信投訴；密度；距離；差分進(jìn)化

AbstractTo improve the accuracy of the service quality, and enhance enterprise competitiveness,clustering of telecom complaints text is helpful for telecom operators to analyze the reasons of complaints, This paper proposed a clustering method for telecom complaints text based on the improved CFSFDP algorithm. To reduce the effects on the method by random select of optimal density and distance threshold for CFSFDP, the method searches density threshold and distance threshold using differential evolution algorithm. The algorithm calculates the density of data points using the Gaussian Kernel, to reduce the effects of parameters on density calculation. Experiments on datasets of telecom complaints text show that clustering result of improved CFSFDP algorithm is better than k-means algorithm,CFSFDP algorithm and agglomerative clustering, the algorithm is effective.

KeywordsCFSFDP algorithm;text clustering; telecom complaints; density; distance; differential evolution

在電信運(yùn)營商同質(zhì)化的業(yè)務(wù)和服務(wù)下，客戶對服務(wù)質(zhì)量有更高的要求。客戶投訴是客戶對電信業(yè)服務(wù)不認(rèn)可而提出的疑義。它不僅數(shù)量龐大，而且種類繁多。采用文本聚類[1]技術(shù)，深入分析客戶投訴內(nèi)容，及時(shí)發(fā)現(xiàn)客戶投訴熱點(diǎn)，對電信運(yùn)營商提高服務(wù)質(zhì)量具有重要意義。

目前，通用的聚類算法主要有基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法以及基于模型的方法[2-3]。而對文本數(shù)據(jù)集進(jìn)行聚類的常用方法有基于劃分的聚類方法和基于層次的聚類方法。但是在數(shù)據(jù)集形狀較復(fù)雜的情況下，傳統(tǒng)聚類算法的準(zhǔn)確率一般較低。CFSFDP(Clustering by Fast Search and Find of Density Peaks)是一種新的密度聚類算法[4]，該算法具有能有效處理復(fù)雜形狀數(shù)據(jù)集、算法效率高、不需要指定類別個(gè)數(shù)等優(yōu)點(diǎn)。通過分析現(xiàn)有文本聚類算法的局限性，本文提出一種改進(jìn)的CFSFDP電信投訴文本聚類方法。

1 CFSFDP算法

1.1 CFSFDP算法原理

CFSFDP作為一種基于密度的聚類方法，算法的大致步驟是：尋找數(shù)據(jù)集的聚類中心，對剩余數(shù)據(jù)點(diǎn)歸屬完成聚類。聚類中心通常具有以下特點(diǎn)：密度較周圍數(shù)據(jù)點(diǎn)的密度大；與其他密度更大的數(shù)據(jù)點(diǎn)之間的“距離”相對更大。

1.2 局部密度與距離

(1)

距離是指數(shù)據(jù)點(diǎn)i與密度較它高的最近點(diǎn)的距離。定義為

(2)

通過計(jì)算密度及距離得到密度大且與其它更高密度點(diǎn)距離大的點(diǎn)作為聚類中心。計(jì)算剩余數(shù)據(jù)點(diǎn)到各個(gè)聚類中心的距離，將數(shù)據(jù)點(diǎn)歸屬到距離其最近的聚類中心，完成聚類。

2 差分進(jìn)化算法

差分進(jìn)化算法[5-7]是一種基于變異、交叉、選擇的全局優(yōu)化算法。該算法通過模擬生物進(jìn)化的過程，在反復(fù)迭代的基礎(chǔ)上淘汰了不適應(yīng)環(huán)境的個(gè)體，而保存了適應(yīng)環(huán)境的個(gè)體。算法的基本思想：首先從隨機(jī)產(chǎn)生的初始群體中隨機(jī)選取兩個(gè)個(gè)體，對選取的兩個(gè)個(gè)體作差運(yùn)算生成一個(gè)差向量。然后對差向量進(jìn)行加權(quán)操作，將得到的加權(quán)結(jié)果與第3個(gè)個(gè)體按照一定的規(guī)則進(jìn)行求和產(chǎn)生一個(gè)變異個(gè)體，此過程即為變異操作。將變異操作中得到的變異個(gè)體與某個(gè)預(yù)先決定的目標(biāo)個(gè)體進(jìn)行參數(shù)混合生成一個(gè)試驗(yàn)個(gè)體，此過程即為交叉操作。比較試驗(yàn)個(gè)體與目標(biāo)個(gè)體的適應(yīng)度值。若目標(biāo)個(gè)體其適應(yīng)度值優(yōu)于試驗(yàn)個(gè)體的適應(yīng)度值，則保存目標(biāo)個(gè)體；否則，保留試驗(yàn)個(gè)體。此過程即為選擇操作。通過差分進(jìn)化算法對多個(gè)個(gè)體進(jìn)行操作，使個(gè)體在每次迭代過程中朝最優(yōu)目標(biāo)進(jìn)化，從而得到最優(yōu)解。

3 CFSFDP聚類方法

在對電信投訴文本聚類時(shí)，將N條投訴文本劃分成k類，其目的是使各個(gè)類中投訴文本內(nèi)容的相似度較高而類間投訴文本內(nèi)容的相似度較低。

3.1 算法流程圖

算法流程圖如圖1所示。關(guān)鍵步驟包括：文本預(yù)處理，數(shù)據(jù)點(diǎn)密度及距離的計(jì)算，尋找最優(yōu)參數(shù)組，數(shù)據(jù)點(diǎn)歸屬完成聚類。

圖1 算法流程圖

3.2 算法步驟

步驟1所需數(shù)據(jù)準(zhǔn)備以及初始化參數(shù)。設(shè)原始投訴文本集為X；已知?jiǎng)澐謹(jǐn)?shù)據(jù)集為P；最大進(jìn)化代數(shù)為g；種群數(shù)量為m；縮放系數(shù)為F；交叉概率為CR；

步驟2文本預(yù)處理。對電信投訴文本進(jìn)行特征詞提取并構(gòu)建領(lǐng)域詞庫。使用Pythonjieba分詞程序?qū)﹄娦磐对V文本進(jìn)行分詞，并通過與構(gòu)建的詞庫對照，提取特征詞。計(jì)算特征詞的權(quán)重tfidf(d,t)；

步驟3計(jì)算密度及距離。將步驟2中得到的每個(gè)向量作為一個(gè)數(shù)據(jù)點(diǎn)，對數(shù)據(jù)點(diǎn)計(jì)算各自的密度以及比當(dāng)前數(shù)據(jù)密度大的所有數(shù)據(jù)點(diǎn)中的最小距離；

步驟4尋找最優(yōu)參數(shù)組。通過差分進(jìn)化算法初始化參數(shù)群體。初始化群體時(shí)首先對密度及距離參數(shù)給定閾值范圍，然后隨機(jī)產(chǎn)生k組閾值范圍內(nèi)的參數(shù)并進(jìn)行實(shí)數(shù)編碼，將其作為初始種群；利用生成的閾值參數(shù)選擇聚類中心；對數(shù)據(jù)點(diǎn)歸屬完成聚類，并通過適應(yīng)度函數(shù)計(jì)算出參數(shù)個(gè)體的適應(yīng)度值；判斷算法是否達(dá)到最大進(jìn)化代數(shù)或適應(yīng)度值是否達(dá)到最小值，滿足上述條件之一，輸出相應(yīng)的參數(shù)組，此閾值參數(shù)組為最優(yōu)參數(shù)組；否則重復(fù)該步驟直到滿足算法終止條件；

步驟5完成聚類。對步驟4得到的參數(shù)組選擇聚類中心，通過數(shù)據(jù)點(diǎn)歸屬完成聚類。

3.3 適應(yīng)度函數(shù)

差分進(jìn)化算法需要定義一個(gè)適應(yīng)度函數(shù)來反應(yīng)聚類結(jié)果的好壞。本文采用Rand系數(shù)的倒數(shù)作為適應(yīng)度函數(shù)。適應(yīng)度函數(shù)f(x)計(jì)算方式如下[8]

(3)

設(shè)經(jīng)算法產(chǎn)生的聚類結(jié)果為：C={C1,C2,…,Ck2}，設(shè)此聚類集為A；已知聚類為P={P1,P2,…Pk1}，設(shè)此聚類集為B。適應(yīng)度函數(shù)中有變量SS，SD，DS，DD，其計(jì)算方式分別如下

當(dāng)某兩個(gè)數(shù)據(jù)點(diǎn)滿足在A中屬于同一類且在B中也屬于同一類時(shí)，有u1(pi,pj)=1，否則u1(pi,pj)=0；當(dāng)某兩個(gè)數(shù)據(jù)點(diǎn)滿足在A中屬于同一類但在B中不屬于同一類時(shí)，有u2(pi,pj)=1，否則u2(pi,pj)=0；當(dāng)某兩個(gè)數(shù)據(jù)點(diǎn)滿足在A中不屬于同一類但在B中屬于同一類時(shí)，有u3(pi,pj)=1，否則u3(pi,pj)=0；當(dāng)某兩個(gè)數(shù)據(jù)點(diǎn)滿足在A中不屬于同一類且在B中也不屬于同一類時(shí)，有u4(pi,pj)=1，否則u4(pi,pj)=0；

3.4GaussianKernel密度計(jì)算

由于CutoffKernel計(jì)算密度的方式過高地依賴于數(shù)據(jù)集的特征，其密度值會(huì)因統(tǒng)計(jì)錯(cuò)誤而受到影響[4]。本文采用GaussianKernel[4]來計(jì)算局部密度，計(jì)算公式如下

(4)

此外，本文采用向量空間模型[9]對文本進(jìn)行向量化表示，使用tfidf[10]計(jì)算特征詞權(quán)重。文本相似度計(jì)算[11]通過歐式距離實(shí)現(xiàn)。

4 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文所提算法的可行性和有效性，提取部分電信用戶投訴文本，應(yīng)用本文所提算法進(jìn)行聚類。此外，對基本的CFSFDP[4]算法，K-Means[12]算法以及AgglomerativeClustering[13]算法在相同數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)并對比。所有實(shí)驗(yàn)都在i5處理器，8GB內(nèi)存，Windows7操作系統(tǒng)上進(jìn)行，使用Python實(shí)現(xiàn)具體算法。

實(shí)驗(yàn)中從電信投訴文本中抽取了5 000條由電信運(yùn)營商提供的用戶投訴記錄。抽取的投訴文本類別與數(shù)目分別如下：寬帶類1 599條，固定電話類277條，itv類241條，流量類375條，套餐類741條，短信類181條，賠退類471條，費(fèi)用類857條，其它類258條。其中，其它類表示投訴文本數(shù)量比較少但是存在的類別。

4.1 評價(jià)指標(biāo)

本文通過引入聚類精度(Accuracy，AC)、純度(Rrecision，PR)、召回率(Recall，RE)和F值(F1)[14-15]4個(gè)評價(jià)指標(biāo)來評價(jià)聚類算法的性能。設(shè)P={P1,P2,…,Pk1}為數(shù)據(jù)集X的人工聚類，C={C1,C2,…,Ck2}為聚類算法對數(shù)據(jù)集X的聚類結(jié)果，nij=|Ci∩Pj|為Ci和Pj的共同部分的基數(shù)，bi是Ci中的對象個(gè)數(shù)，dj是Pj中的對象個(gè)數(shù)。則上述4個(gè)評價(jià)指標(biāo)公式如下

(5)

(6)

(7)

(8)

4.2 實(shí)驗(yàn)結(jié)果分析

分別用本文算法、基本的CFSFDP算法、K-Means算法、AgglomerativeClustering算法對抽取的5 000條記錄進(jìn)行聚類。對K-Means算法、AgglomerativeClustering算法給定具體類別數(shù)目9。設(shè)置差分進(jìn)化算法種群數(shù)量為20，縮放因子為0.5，交叉概率為0.9。

通過表1的實(shí)驗(yàn)結(jié)果可以看出，本文算法在電信投訴文本中的聚類結(jié)果相比其他3種聚類算法都有所提高。由于電信投訴文本較復(fù)雜、存在噪聲點(diǎn)等特點(diǎn)，使得基本的CFSFDP算法在確定聚類中心時(shí)，會(huì)出現(xiàn)錯(cuò)選、漏選、多選聚類中心的情況，因此導(dǎo)致CFSFDP算法的聚類效果不佳。K-Means算法隨機(jī)選取初始中心點(diǎn)的策略導(dǎo)致其聚類準(zhǔn)確率下降。另外，K-Means對噪聲點(diǎn)敏感的特點(diǎn)進(jìn)一步影響了K-Means聚類的準(zhǔn)確率。AgglomerativeClustering算法在聚類過程中由于存在不能更正錯(cuò)誤的缺陷，在復(fù)雜的數(shù)據(jù)集中會(huì)導(dǎo)致聚類效果的降低。此外，該算法的時(shí)間復(fù)雜度過高，不適用于大型數(shù)據(jù)集。本文提出的改進(jìn)后算法針對傳統(tǒng)的CFSFDP算法的缺陷，作了相應(yīng)的改進(jìn)。通過實(shí)驗(yàn)對比，證明了改進(jìn)后算法的有效性。

表1 4種算法的AC、PR、RE、F1值比較

5 結(jié)束語

本文針對CFSFDP算法過于依賴密度與距離值而導(dǎo)致聚類效果不佳的問題，對CFSFDP算法進(jìn)行改進(jìn)。通過引入差分進(jìn)化算法尋找最優(yōu)密度、距離值，降低CFSFDP算法對閾值參數(shù)的依賴性，提高了算法準(zhǔn)確率。作者用GaussianKernel公式代替CutoffKernel公式來計(jì)算數(shù)據(jù)點(diǎn)密度，在一定程度上降低了截?cái)嗑嚯x對數(shù)據(jù)點(diǎn)密度計(jì)算的影響。實(shí)驗(yàn)結(jié)果表明，在投訴文本聚類中本文提出的改進(jìn)CFSFDP算法比常見的文本聚類算法有著更好或者相當(dāng)?shù)男Ч?。本文研究對電信投訴文本的智能分析與挖掘提供了新方法，對電信運(yùn)營商把握客戶投訴熱點(diǎn)，提升客戶滿意度具有重要的實(shí)踐價(jià)值。

[1]VermaVK,RanjanM,MishraP.Textminingandinformationprofessionals:Role,issuesandchallenges[C].Noida:InternationalSymposiumonEmergingTrendsandTechnologiesinLibrariesandInformationServices,IEEE, 2015.

[2]SunJG,LiuJ,ZhaoLY.Clusteringalgorithmsresearch[J].JournalofSoftware,2008,19(19)：48-61.

[3] 王虹,孫紅.基于混合聚類算法的客戶細(xì)分策略研究[J].電子科技,2016,29(1):29-32.

[4]RodriguezA,LaioA.Machinelearning.Clusteringbyfastsearchandfindofdensitypeaks[J].Science, 2014, 344(6191):1492-1496.

[5]KarwaS,ChatterjeeN.Discretedifferentialevolutionfortextsummarization[C].Bhubaneswar:InternationalConferenceonInformationTechnology,IEEE,2014.

[6] 劉亞丹,古發(fā)輝.差分進(jìn)化算法研究進(jìn)展[J].科技廣場,2013(3):20-23.

[7]LiGY,LiuMG.Thesummaryofdifferentialevolutionalgorithmanditsimprovements[C].Chengdu:InternationalConferenceonAdvancedComputerTheory&Engineering,IEEE, 2010.

[8]HalkidiM,BatistakisY,VazirgiannisM.Onclusteringvalidationtechniques[J].JournalofIntelligentInformationSystems, 2015,17(2-3):107-145.

[9]SaltonG,WongA,YangCS.Avectorspacemodelforautomaticindexing[M].NewYork:MorganKaufmannPublishersInc.,1997.

[10]CaoNieqing,CaoJingjing,LuHaili,etal.SentimentclassificationusingTF-1DFfeaturesandextendedspaceforestensemble[C].Guangzhou:InternationalConferenceonMachineLearningandCybernetics,IEEE,2015.

[11] 譚靜.基于向量空間模型的文本相似度算法研究[D].成都:西南石油大學(xué),2015.

[12] 吳夙慧,成穎,鄭彥寧,等.K-means算法研究綜述[J].現(xiàn)代圖書情報(bào)技術(shù),2011(5):28-35.

[13] 段明秀.層次聚類算法的研究及應(yīng)用[D].長沙:中南大學(xué),2009.

[14]LiangJ,BaiL,DangC,etal.TheMeans-typealgorithmsversusimbalanceddatadistributions[J].IEEETransactionsonFuzzySystems, 2012,20(4):728-745.

[15] 張鳴.符號數(shù)據(jù)聚類評價(jià)指標(biāo)研究[D].太原:山西大學(xué),2013.

Clustering Method for Telecom Complaints Text Based on Improved CFSFDP Algorithm

ZHANG Tianyu, CHEN Zhiqun, HUANG Xiaoxi, WANG Rongbo

(School of Computer Science, Hangzhou Dianzi University, Hangzhou 310018,China)

TP391

A

1007-7820(2017)10-093-04

2016- 12- 06

國家自然科學(xué)基金青年基金(61202281)；杭州電子科技大學(xué)“管理科學(xué)與工程”省高校人文社科重點(diǎn)研究基金(ZD04-201402)

張?zhí)煊?1992-),男,碩士研究生。研究方向：中文信息處理。諶志群(1973-),男,副教授。研究方向：中文信息處理。黃孝喜(1979-)，男，博士，副教授。研究方向：語言認(rèn)知計(jì)算。王榮波(1978-),男,博士,副教授。研究方向：自然語言處理。

10.16180/j.cnki.issn1007-7820.2017.10.025