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

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

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

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

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

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

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

CFSFDP算法；文本聚類(lèi)；電信投訴；密度；距離；差分進(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)營(yíng)商同質(zhì)化的業(yè)務(wù)和服務(wù)下，客戶對(duì)服務(wù)質(zhì)量有更高的要求?？蛻敉对V是客戶對(duì)電信業(yè)服務(wù)不認(rèn)可而提出的疑義。它不僅數(shù)量龐大，而且種類(lèi)繁多。采用文本聚類(lèi)[1]技術(shù)，深入分析客戶投訴內(nèi)容，及時(shí)發(fā)現(xiàn)客戶投訴熱點(diǎn)，對(duì)電信運(yùn)營(yíng)商提高服務(wù)質(zhì)量具有重要意義。

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

1 CFSFDP算法

1.1 CFSFDP算法原理

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

1.2 局部密度與距離

(1)

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

(2)

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

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

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

3 CFSFDP聚類(lèi)方法

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

3.1 算法流程圖

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

圖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ù)處理。對(duì)電信投訴文本進(jìn)行特征詞提取并構(gòu)建領(lǐng)域詞庫(kù)。使用Pythonjieba分詞程序?qū)﹄娦磐对V文本進(jìn)行分詞，并通過(guò)與構(gòu)建的詞庫(kù)對(duì)照，提取特征詞。計(jì)算特征詞的權(quán)重tfidf(d,t)；

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

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

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

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

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

(3)

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

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

3.4GaussianKernel密度計(jì)算

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

(4)

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

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

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

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

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

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

(5)

(6)

(7)

(8)

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

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

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

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

5 結(jié)束語(yǔ)

本文針對(duì)CFSFDP算法過(guò)于依賴密度與距離值而導(dǎo)致聚類(lèi)效果不佳的問(wèn)題，對(duì)CFSFDP算法進(jìn)行改進(jìn)。通過(guò)引入差分進(jìn)化算法尋找最優(yōu)密度、距離值，降低CFSFDP算法對(duì)閾值參數(shù)的依賴性，提高了算法準(zhǔn)確率。作者用GaussianKernel公式代替CutoffKernel公式來(lái)計(jì)算數(shù)據(jù)點(diǎn)密度，在一定程度上降低了截?cái)嗑嚯x對(duì)數(shù)據(jù)點(diǎn)密度計(jì)算的影響。實(shí)驗(yàn)結(jié)果表明，在投訴文本聚類(lèi)中本文提出的改進(jìn)CFSFDP算法比常見(jiàn)的文本聚類(lèi)算法有著更好或者相當(dāng)?shù)男Ч?。本文研究?duì)電信投訴文本的智能分析與挖掘提供了新方法，對(duì)電信運(yùn)營(yíng)商把握客戶投訴熱點(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] 王虹,孫紅.基于混合聚類(lèi)算法的客戶細(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].科技廣場(chǎng),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)代圖書(shū)情報(bào)技術(shù),2011(5):28-35.

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

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

[15] 張鳴.符號(hào)數(shù)據(jù)聚類(lèi)評(píng)價(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

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

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

10.16180/j.cnki.issn1007-7820.2017.10.025