基于聚類分析算法的鐵路通信設(shè)備廠商信息智能分類

趙 穎，王華偉

（中國鐵道科學(xué)研究院集團(tuán)有限公司 電子計(jì)算技術(shù)研究所，北京 100081）

鐵路通信設(shè)備是鐵路運(yùn)輸生產(chǎn)的基礎(chǔ)，是鐵路實(shí)現(xiàn)集中統(tǒng)一指揮的重要保障，為實(shí)現(xiàn)對(duì)鐵路運(yùn)輸設(shè)備技術(shù)狀態(tài)的全面掌控和精益化管理，鐵路相關(guān)部門組織開展了鐵路通信大數(shù)據(jù)平臺(tái)相關(guān)技術(shù)的研究，實(shí)現(xiàn)了對(duì)通信設(shè)備的履歷化管理，以及設(shè)備全生命周期管理、故障預(yù)測(cè)、健康管理、狀態(tài)評(píng)價(jià)等應(yīng)用服務(wù)[1]。

通信設(shè)備履歷管理是通信大數(shù)據(jù)平臺(tái)的一個(gè)重要組成部分，而建立設(shè)備履歷需要一系列字典信息作為基礎(chǔ)，包括組織機(jī)構(gòu)字典、通信機(jī)房字典、產(chǎn)品生產(chǎn)廠商字典等。其中，產(chǎn)品生產(chǎn)廠商字典由各鐵路局用戶通過系統(tǒng)錄入并上報(bào)，需要對(duì)數(shù)據(jù)進(jìn)行分析歸類，再通過人工審核，最終才能形成規(guī)范的字典數(shù)據(jù)。

機(jī)器學(xué)習(xí)作為人工智能領(lǐng)域的一個(gè)重要分支，近年來在解決現(xiàn)實(shí)生活中的實(shí)際問題上發(fā)揮了顯著的作用，其中，在對(duì)無標(biāo)記樣本的分類任務(wù)中，研究最多、應(yīng)用最廣的是“聚類”[2]。因此，通過研究并選擇一種高效的聚類分析算法，實(shí)現(xiàn)對(duì)通信設(shè)備廠商信息的智能分類，是鐵路通信設(shè)備大數(shù)據(jù)平臺(tái)的一項(xiàng)重要工作。

1 聚類分析

1.1 算法介紹

在“無監(jiān)督學(xué)習(xí)”中，訓(xùn)練樣本的標(biāo)記信息是未知的，目標(biāo)是通過對(duì)無標(biāo)記訓(xùn)練樣本的學(xué)習(xí)來揭示數(shù)據(jù)的內(nèi)在性質(zhì)及規(guī)律，為進(jìn)一步的數(shù)據(jù)分析提供基礎(chǔ)。聚類分析將相似的對(duì)象歸到同一個(gè)簇中，將不相似的對(duì)象歸到不同的簇中。聚類方法幾乎可以應(yīng)用于所有對(duì)象，簇內(nèi)的對(duì)象越相似，聚類的效果越好。相似這一概念取決于所選擇的相似度計(jì)算方法，而采用哪種相似度計(jì)算方法取決于具體的應(yīng)用。

1.2 相似度計(jì)算方法

歐氏距離是一種常用的距離定義，指在m維空間中兩個(gè)點(diǎn)之間的真實(shí)距離，對(duì)多維向量A=(A1，A2,……,An)，B=(B1,B2,……,Bn)，歐氏距離的計(jì)算公式為：

余弦相似度用向量空間中兩個(gè)向量夾角的余弦值作為衡量兩個(gè)個(gè)體差異的大小。相比歐氏距離度量，余弦相似度更加注重兩個(gè)向量在方向上的差異，而非距離或長度上的差異。余弦值的計(jì)算公式為：

相對(duì)于歐氏距離，余弦相似度更適合計(jì)算文本的相似度。首先將文本轉(zhuǎn)換為權(quán)值向量，通過計(jì)算兩個(gè)向量的夾角余弦值，就可以評(píng)估他們的相似度。余弦值的范圍在[-1,1]之間，值越趨近于1，代表兩個(gè)向量方向越接近；越趨近于-1，代表他們的方向越相反。為了方便聚類分析，將余弦值做歸一化處理，將其轉(zhuǎn)換到[0,1]之間，并且值越小距離越近。

1.3 性能度量

同一個(gè)簇內(nèi)的樣本盡可能相似，不同簇的樣本盡可能不同，也就是說聚類結(jié)果的“簇內(nèi)相似度”高且“簇間相似度”低。

考慮聚類結(jié)果的簇劃分C={C1,C2,…,CK}，定義：

其中，μ代表簇C的中心點(diǎn)；avg(C)代表簇C內(nèi)樣本的平均距離；diam(C)代表簇C內(nèi)樣本間的最遠(yuǎn)距離；dmin(Ci,Cj)對(duì)應(yīng)于簇Ci和簇Cj最近樣本間的距離；dcen(Ci,Cj)對(duì)應(yīng)于簇Ci和簇Cj中心點(diǎn)間的距離。

基于以上公式可導(dǎo)出下面2個(gè)常用的聚類性能度量內(nèi)部指標(biāo)：

（1）DB 指數(shù)（DBI，Davies-Bouldin Index）

DB 指數(shù)的計(jì)算方法是任意兩個(gè)簇內(nèi)樣本的平均距離之和除以兩個(gè)簇的中心點(diǎn)距離，并取最大值，DBI 的值越小，簇內(nèi)距離越小，同時(shí)簇間的距離越大；Dumn 指數(shù)的計(jì)算方法是任意兩個(gè)簇的最近樣本間的距離除以簇內(nèi)樣本的最遠(yuǎn)距離的最大值，并取最小值，DI 的值越大，簇間距離大而簇內(nèi)距離小。因此，DBI 的值越小，同時(shí)DI 的值越大，聚類的效果越好。

2 數(shù)據(jù)預(yù)處理

2.1 分詞處理

對(duì)中文文本做聚類分析，首先要對(duì)文本做分詞處理，Python提供專門的中文切詞工具，它可以將中文長文本劃分為若干個(gè)單詞。

為了提高分類的準(zhǔn)確率，還要考慮兩個(gè)干擾因素：（1）英文字母大小寫的影響，為此我們將英文字母統(tǒng)一轉(zhuǎn)換為大寫；（2）將某些通用詞匯連同“（）”、“-”、“/”、“&”等符號(hào)作為停用詞，將其從分詞結(jié)果中去除掉，最后得到有效的詞匯組合。分詞并去除停用詞后的效果圖如圖1所示。

2.2 構(gòu)建詞袋模型

文本被切分成單詞后，需要進(jìn)一步轉(zhuǎn)換成向量。將所有文本中的所有詞匯構(gòu)建成一個(gè)詞條列表，其中，不含重復(fù)的詞條。再對(duì)每個(gè)文本，構(gòu)建一個(gè)向量，向量的維度與詞條列表的維度相同，向量的值是詞條列表中每個(gè)詞條在該文本中出現(xiàn)的次數(shù)，這種模型叫做詞袋模型[3-5]。例如，“阿爾西集團(tuán)”和“阿爾西制冷工程技術(shù)(北京)有限公司”兩個(gè)文本切詞后的結(jié)果是“阿爾西 集團(tuán)”和“阿爾西 制冷 工程技術(shù)北京”，它們構(gòu)成的詞條列表是[阿爾西, 集團(tuán), 制冷,工程技術(shù), 北京]，對(duì)應(yīng)的詞袋模型分別是[1,1,0,0,0]，[1,0,1,1,1]。

圖1 廠商名稱分詞效果圖

2.3 權(quán)值轉(zhuǎn)換

TF-IDF是一種統(tǒng)計(jì)方法，用來評(píng)估一個(gè)詞條對(duì)于一個(gè)文件集中一份文件的重要程度。TF-IDF的主要思想是：如果某個(gè)詞在一篇文章中出現(xiàn)的頻率TF高，并且在其他文件中很少出現(xiàn)，則認(rèn)為此詞條具有很好的類別區(qū)分能力，適合用來分類。

（1）詞頻（TF，term frequency）：

分子是詞條ti在文件dj中出現(xiàn)的次數(shù)，分母是文件dj中所有詞條出現(xiàn)的次數(shù)之和。

（2）逆向文件頻率（IDF，inverse document frequency）：

對(duì)數(shù)內(nèi)的分子是文件總數(shù)，分母是包含詞條ti的文件數(shù)，如果該詞不存在，就會(huì)導(dǎo)致分母為零，因此一般使用1+|{j:ti∈dj}|作為分母。

（3）TF-IDF：

將TF與IDF相乘得到TF-IDF權(quán)值。由以上定義可知，一個(gè)詞語在某一特定文件中出現(xiàn)的頻率高，在整個(gè)文件集中出現(xiàn)的頻率低，可以產(chǎn)生高權(quán)重的TF-IDF值。因此，將詞袋向量轉(zhuǎn)換為TF-IDF權(quán)值向量，更有利于判斷兩個(gè)文本的相似性。

3 廠商信息聚類分析

3.1 K-均值聚類

K-均值是將數(shù)據(jù)集劃分為k個(gè)簇的算法，簇的個(gè)數(shù)k是用戶給定的，每個(gè)簇通過其質(zhì)心（簇中所有點(diǎn)的中心）來描述。K-均值算法的工作流程是：

（1）隨機(jī)確定k個(gè)初始點(diǎn)作為質(zhì)心。

（2）將數(shù)據(jù)集中的每個(gè)點(diǎn)找到距離最近的質(zhì)心，并將其分配到該質(zhì)心對(duì)應(yīng)的簇中。

（3）將每個(gè)簇的質(zhì)心更新為該簇中所有點(diǎn)的平均值。

（4）重復(fù)第（2）、（3）步驟，直到簇的分配結(jié)果不再變化。

為了評(píng)價(jià)聚類的質(zhì)量，定義一種用于衡量聚類效果的指標(biāo)誤差平方和（SSE，Sum of Squared Error），誤差是指樣本到其質(zhì)心的距離。SSE值越小，表示數(shù)據(jù)點(diǎn)越接近質(zhì)心。

由于K-均值算法是隨機(jī)選取質(zhì)心，因此可能會(huì)收斂到局部最小值，而非全局最小值。為了克服這個(gè)問題，提出了一種二分K-均值算法。該算法的思路是將：（1）所有點(diǎn)作為一個(gè)簇；（2）將該簇一分為二；（3）選擇一個(gè)能最大程度降低SSE值的簇繼續(xù)進(jìn)行劃分，直到得到用戶指定的簇?cái)?shù)目為止[6-8]。

隨機(jī)選取539個(gè)樣本作為測(cè)試樣本，由于事先無法確定分類的個(gè)數(shù)k，通過觀察DI和DBI的變化趨勢(shì)來確定一個(gè)合適k值。為此，將k設(shè)置一個(gè)較大的值，通過運(yùn)算得到DI和DBI的變化趨勢(shì)，如圖2所示。

由圖2可知，DBI值趨于不變，DI值的變化趨勢(shì)也沒有規(guī)律。同時(shí)，分別對(duì)539個(gè)樣本劃分為200、300、420個(gè)簇，經(jīng)過人工校驗(yàn)，被成功分類的樣本分別為111個(gè)、106個(gè)、105個(gè)。因此，K-均值算法不適合對(duì)廠商名稱的分類，分析其原因，可能是由于廠商名稱所包含的詞匯量太少，而K-均值算法具有一定的隨機(jī)性，從而導(dǎo)致分類效果不理想。

圖2 k-均值聚類算法性能變化趨勢(shì)

3.2 層次聚類

層次聚類[2]試圖在不同的層次對(duì)數(shù)據(jù)集進(jìn)行劃分，可以采用“自底向上”的聚類策略，也可以采用“自頂向下”的分拆策略。一般采用“自底向上”的策略，它的思路是先將數(shù)據(jù)集中的每個(gè)樣本看作一個(gè)初始聚類簇，找出兩個(gè)聚類最近的兩個(gè)簇進(jìn)行合并，不斷重復(fù)該步驟，直到達(dá)到預(yù)設(shè)的聚類個(gè)數(shù)或某種條件。關(guān)鍵是如何計(jì)算兩個(gè)簇之間的距離，每個(gè)簇都是一個(gè)集合，因此，計(jì)算集合的某種距離即可。例如，給定簇Ci和Cj，可通過以下3種方式計(jì)算距離：

最小距離由兩個(gè)簇的最近樣本決定，最大距離由兩個(gè)簇的最遠(yuǎn)樣本決定，平均距離由兩個(gè)簇的所有樣本決定。

接下來要考慮如何確定一個(gè)合適的聚類個(gè)數(shù)或某種結(jié)束條件，具體思路是：

（1）選定一部分測(cè)試樣本，對(duì)其進(jìn)行層次聚類分析；

（2）記算性能度量指標(biāo)DBI和DI的變化趨勢(shì)，結(jié)合人工校驗(yàn)，得到一個(gè)合適的聚類個(gè)數(shù)和對(duì)應(yīng)的距離閾值；

（3）將此距離閾值作為聚類結(jié)束的條件，對(duì)所有樣本做聚類分析。

仍然選擇K-均值算法所用的539個(gè)樣本，對(duì)其進(jìn)行層次聚類，得到的性能指標(biāo)變化趨勢(shì)如圖3所示。

圖3 層次聚類算法性能變化趨勢(shì)

從圖3可以看出，DI值呈下降趨勢(shì)，DBI值呈階躍上升趨勢(shì)，根據(jù)性能度量的規(guī)則（DBI的值越小越好；DI的值越大越好），最優(yōu)值可能出現(xiàn)階躍點(diǎn)附近，即劃分為471類和445類兩個(gè)點(diǎn)，同時(shí)結(jié)合人工校驗(yàn)，可以確定445類更加合理。

將k值設(shè)置為445進(jìn)行層次聚類分析，發(fā)現(xiàn)仍有少量相似的樣本被劃分到不同的類。根據(jù)業(yè)務(wù)需求，為了減少后續(xù)的核實(shí)工作量，將相似的樣本盡可能劃分到同一類中，同時(shí)可以接受少部分不同的樣本劃分到同一類，給予k值適當(dāng)?shù)娜哂啵瑢⑵湓O(shè)置為420，再分別基于最大距離、最小距離、平均距離進(jìn)行分析，得到結(jié)果如表1所示。

表1 層次聚類分類效果對(duì)比

從以上分類結(jié)果看出，采用層次聚類算法對(duì)539個(gè)測(cè)試樣本進(jìn)行分類，效果明顯優(yōu)于K-均值聚類算法。并且，該算法可以通過學(xué)習(xí)得到距離閾值作為聚類結(jié)束的條件，從而解決了分類個(gè)數(shù)k值無法確定的問題。

為了降低個(gè)別樣本對(duì)整體結(jié)果的影響，選擇基于平均距離的距離分析算法，并將距離閾值設(shè)置為0.29，對(duì)全部4 574個(gè)樣本做聚類分析，最后得到3 128個(gè)類，部分樣本的分類結(jié)果如圖4所示。

圖4 層次聚類算法分類效果

4 結(jié)束語

本文針對(duì)鐵路通信大數(shù)據(jù)平臺(tái)中通信設(shè)備生產(chǎn)廠商信息不規(guī)范的問題，提出了基于聚類分析算法對(duì)生產(chǎn)廠商進(jìn)行分類的思路。通過分詞、構(gòu)建詞袋空間、權(quán)值轉(zhuǎn)換等一系列數(shù)據(jù)預(yù)處理方法，將文本轉(zhuǎn)換為可分類的權(quán)值向量。采用K-均值聚類、層次聚類算法分別對(duì)部分樣本進(jìn)行聚類分析，比較測(cè)試結(jié)果，選擇層次聚類算法對(duì)所有樣本進(jìn)行聚類分析，最終得到理想的分類結(jié)果，從而極大地降低了人工審核并規(guī)范信息的工作量，為形成廠商字典提供了有力的支持。隨著鐵路通信大數(shù)據(jù)平臺(tái)的推廣應(yīng)用，采集的數(shù)據(jù)量也會(huì)越來越大，海量數(shù)據(jù)規(guī)范、設(shè)備故障預(yù)測(cè)、智能狀態(tài)評(píng)價(jià)等需求將會(huì)日益突出，因此，通過人工智能的理論和技術(shù)來進(jìn)行數(shù)據(jù)挖掘，從而提供更加智能的決策支持將成為日后的工作重點(diǎn)。