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

趙 穎，王華偉

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

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

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

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

1 聚類分析

1.1 算法介紹

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

1.2 相似度計算方法

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

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

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

1.3 性能度量

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

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

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

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

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

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

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

2.1 分詞處理

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

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

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

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

圖1 廠商名稱分詞效果圖

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

TF-IDF是一種統(tǒng)計方法，用來評估一個詞條對于一個文件集中一份文件的重要程度。TF-IDF的主要思想是：如果某個詞在一篇文章中出現(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）：

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

（3）TF-IDF：

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

3 廠商信息聚類分析

3.1 K-均值聚類

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

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

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

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

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

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

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

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

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

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

3.2 層次聚類

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

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

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

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

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

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

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

圖3 層次聚類算法性能變化趨勢

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

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

表1 層次聚類分類效果對比

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

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

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

4 結(jié)束語

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