基于CURE聚類算法的科技情報異常數(shù)據(jù)檢測

柳兆峰，楊 奇，霍永華，謝志敏

(1.中國人民解放軍31001部隊，北京 100094； 2.中國電子科技集團公司第五十四研究所,河北 石家莊050081； 3.中國人民解放軍海洋環(huán)境專項辦公室，北京 100181)

0 引言

情報是指按照用戶需求，針對特定情景實現(xiàn)特殊作用和價值的信息數(shù)據(jù)和知識。情報分析亦稱信息分析或情報研究，是根據(jù)社會用戶的特定需求，將分布分散、雜亂的海量信息采用科學(xué)的研究方法和技術(shù)手段進(jìn)行收集、整理，生成有價值的情報數(shù)據(jù)，為不同層次的用戶提供科學(xué)決策服務(wù)。我國提供了良好的情報分析研究工作環(huán)境，形成了以高校和圖書館為主導(dǎo)，以科技情報為核心的應(yīng)用領(lǐng)域和以政府與企業(yè)為主導(dǎo)，以路線規(guī)劃、前景預(yù)測、綜合決策為目標(biāo)的應(yīng)用領(lǐng)域[1-3]。

情報數(shù)據(jù)質(zhì)量是進(jìn)行情報分析并以此做出有效決策的重要基礎(chǔ)。互聯(lián)網(wǎng)和大數(shù)據(jù)背景下，科技情報研究的數(shù)據(jù)來源被大大拓寬，因此不可避免地出現(xiàn)數(shù)據(jù)分類錯誤、重復(fù)、缺失、格式不一致等現(xiàn)象，這些異常數(shù)據(jù)對于情報分析是無用的，甚至?xí)Ψ治鼋Y(jié)果和效率產(chǎn)生很大的負(fù)面影響，所以需要對其進(jìn)行檢測和處理，以提高數(shù)據(jù)的質(zhì)量[4]。本文重點解決科技情報中數(shù)據(jù)分類錯誤問題。

異常檢測作為數(shù)據(jù)挖掘領(lǐng)域的一個重要研究方向，主要用來檢測數(shù)據(jù)集中偏離正常分布模式的異常數(shù)據(jù)。異常檢測技術(shù)能夠從大量、模糊的復(fù)雜數(shù)據(jù)中檢測出異常信息，在大數(shù)據(jù)處理中得到廣泛應(yīng)用?，F(xiàn)有的異常檢測技術(shù)主要包含基于監(jiān)督的和基于無監(jiān)督的2種方法?；诒O(jiān)督的異常檢測方法主要包括概率統(tǒng)計、模式預(yù)測、神經(jīng)網(wǎng)絡(luò)、增量式SVM異常檢測等方法；基于無監(jiān)督的異常檢測方法主要包括K-means聚類、基于核自適應(yīng)的AP聚類異常檢測、引入約束條件的密度聚類異常檢測等方法[5-8]。

但是這些檢測方法僅針對數(shù)值型的數(shù)據(jù)，并不完全適用于情報分析領(lǐng)域。與數(shù)值型數(shù)據(jù)為主要研究對象的大數(shù)據(jù)分析不同，科技情報分析大多以文本文獻(xiàn)作為數(shù)據(jù)的對象和基礎(chǔ)，包括論文、專利、科技報告及網(wǎng)頁文本等。目前情報領(lǐng)域的異常檢測方法研究成果較少，鑒于此，本文基于無監(jiān)督CURE聚類算法，提出了一種針對科技情報數(shù)據(jù)的異常檢測方法。

1 科技情報異常數(shù)據(jù)檢測模型

科技情報異常監(jiān)測過程模型如圖1所示，主要分為3個階段：信息采集與預(yù)處理階段、文本處理階段以及聚類分析階段。

圖1 科技情報異常數(shù)據(jù)檢測模型

1.1 數(shù)據(jù)采集與存儲階段

與傳統(tǒng)情報存儲和傳輸方式不同，互聯(lián)網(wǎng)背景下，各類結(jié)構(gòu)不一的情報流轉(zhuǎn)在網(wǎng)頁、博客、論壇以及社交媒體等網(wǎng)絡(luò)媒介中，依靠人工很難高效地獲取這些情報數(shù)據(jù)，必須依靠技術(shù)手段批量獲取。

本階段主要根據(jù)情報分析需求，利用主題網(wǎng)絡(luò)爬蟲技術(shù)有選擇地自動訪問互聯(lián)網(wǎng)上的網(wǎng)頁與相關(guān)的鏈接，獲取所需要的科技情報。為了極大地減少冗余信息，可以通過網(wǎng)頁排重技術(shù)去除冗余網(wǎng)頁，同時利用網(wǎng)絡(luò)去噪技術(shù)剔除Web頁面中如導(dǎo)航條、廣告信息、版權(quán)信息以及調(diào)查問卷等與主題不相關(guān)的內(nèi)容，最后將爬取到的原始情報信息以統(tǒng)一的格式存儲在文本緩存區(qū)中，實現(xiàn)從非結(jié)構(gòu)化至結(jié)構(gòu)化數(shù)據(jù)的轉(zhuǎn)換存儲。

1.2 文本處理階段

從互聯(lián)網(wǎng)或者數(shù)據(jù)庫獲得情報信息大多是以文本形式存儲，為了實現(xiàn)基于CURE的異常檢測和為后續(xù)的情報分析提供方便，需要對文本數(shù)據(jù)進(jìn)行一系列文本處理，最終以多個特征值表示的形式存儲在數(shù)據(jù)庫中。這一過程一般包括以下4個步驟：

① 中文分詞

中文分詞(Chinese Word Segmentation)技術(shù)是將連續(xù)的字序列按一定的規(guī)范重新組合成詞序列的過程。目前流行的中文分詞算法主要是基于字符串匹配、統(tǒng)計方法和理解分析3種方式，依靠這幾類算法，國內(nèi)外出現(xiàn)了許多成熟的開源分詞軟件。如中國科學(xué)院計算技術(shù)研究所開發(fā)了NLPIR軟件，清華大學(xué)自然語言處理與社會人文計算實驗室開發(fā)了THU-LAC軟件，還有python中常用的結(jié)巴(jieba)分詞。本文選擇THU-LAC軟件作為原始情報文本的分詞工具。

② 去停用詞

情報文本中含有大量的例如“了、呢、的”一類的對情報分析工作沒有實際意義的詞語，這些詞稱為停用詞，為了降低詞典和文本特征向量空間，減少計算量，提升異常檢測效率，要在原始的情報文本中剔除掉停用詞。

③ 關(guān)鍵詞提取

關(guān)鍵詞是指反映一段情報文本核心內(nèi)容的詞語。關(guān)鍵詞提取是利用降維的方法對情報文本進(jìn)行特征選擇和提取，并對特征項的重要程度用權(quán)重加以區(qū)分，從而提高后續(xù)對信息進(jìn)行分類、聚類、主題分析等操作的結(jié)果精度。因此關(guān)鍵詞提取是異常檢測的重要前提和基礎(chǔ)。

通過爬蟲等技術(shù)手段采集的情報數(shù)據(jù)并不會像專業(yè)期刊論文一樣列出關(guān)鍵詞，在海量數(shù)據(jù)的背景下依靠人工進(jìn)行關(guān)鍵詞提取顯然是不可取的。因此，通過技術(shù)手段自動提取關(guān)鍵詞就成為情報分析研究的重點。目前文本提取關(guān)鍵詞算法主要有基于統(tǒng)計、基于詞語網(wǎng)絡(luò)、基于詞語共現(xiàn)圖3種。常見的有基于布爾權(quán)重、詞頻[8]、TFIDF值[9]等方法。本文采用TFIDF值對特征值進(jìn)行選取和加權(quán)。計算方法如下：

(1)

式中，xi為關(guān)鍵詞，N為文檔總數(shù)，n為該關(guān)鍵詞出現(xiàn)的文檔數(shù)。TFik(xi)表示關(guān)鍵詞出現(xiàn)在文檔集的頻數(shù)，分母為歸一化因子。

通過預(yù)先設(shè)定一個閾值，當(dāng)wik(xi) 低于這一閾值時，可認(rèn)為該關(guān)鍵詞幾乎沒有處理價值，可以直接將其忽略。剩余關(guān)鍵詞保留，權(quán)重為wik(xi)。

④ 文本特征表示

特征表示是指用一組特征項來表示文本信息。特征表示模型有布爾模型、向量空間模型及概率模型等。本文利用向量空間模型(Vector Space Model，VSM)對文本進(jìn)行向量化。VSM的思想是用一組特征項及其特征項對應(yīng)的權(quán)重來表示一個文本信息，將文本簡化為特征空間中的一個點。即對于一個含有n個特征值的文本D，可以表示為：

D={(t1,w2),(t2,w2),...,(tn,wn)}，

(2)

式中，ti表示第i個特征詞，wi為第i個特征詞的權(quán)重。將分詞、提取關(guān)鍵詞和特征向量之后的文本信息標(biāo)記，存入數(shù)據(jù)庫中。

1.3 聚類分析階段

聚類分析階段是本文異常數(shù)據(jù)檢測的關(guān)鍵步驟，通過聚類分析的方法對離群數(shù)據(jù)(即不良數(shù)據(jù))進(jìn)行識別和定位。下一節(jié)給出了基于CURE聚類算法的異常數(shù)據(jù)檢測方法的具體步驟。

2 基于CURE聚類算法的異常數(shù)據(jù)檢測

CURE聚類算法是一種自底向上的層次聚類算法，利用該算法對向量化后的情報文本集(即具有n維特征屬性的點集)進(jìn)行聚類，可以對異常數(shù)據(jù)進(jìn)行識別和定位。檢測出來的異常數(shù)據(jù)主要來自兩方面：一個是在首次聚類時增長較為緩慢的簇；另一類是聚類后期包含對象明顯偏少的簇。涉及到的定義如下。

定義 1：初始聚類劃分的數(shù)據(jù)分區(qū)可以用若干個分散的代表點來表示。即數(shù)據(jù)簇s表示為s.mPi(s.mean,s.n)，其中Pi為該簇的代表點，m為代表點的個數(shù)，s.mean為該簇的中心點，s.n代表簇的容量即數(shù)據(jù)對象的個數(shù)。

代表點的選擇方法如下：

① 首先確定代表點的數(shù)目m和收縮因子α；

② 選取初始m個代表點。第一個代表點是距離該簇中心點最遠(yuǎn)的點，其后的代表點是選取距離前一個選出的代表點最遠(yuǎn)的數(shù)據(jù)點；

③ 用收縮因子α收縮代表點，調(diào)節(jié)類的形狀，排除孤立點的影響。收縮公式為：

(3)

定義 2：離散度。用歐氏距離表示樣本中一個對象點距離代表點的離散程度，離散度越大說明距離該代表點越遠(yuǎn)。設(shè)代表點的集合為P，任一樣本數(shù)據(jù)點xi對于集合P中代表點Pi的離散度如下:

(4)

式中，xij為樣本點xi的第j特征值，Pij為代表點Pi的第j特征值，n為VSM模型的維度，該式代表了2個文檔之間的距離。

定義 3：設(shè)每一個樣本點的離散度集為D，取離散度的平均值為該樣本數(shù)據(jù)的離散判定值A(chǔ)D：

(5)

定義 4：設(shè)異常判定界限參數(shù)為δ：

(6)

式中，min(di)為離散度最小值。

定義 5：對于離散度集D中任意di∈D，若di>δ×AD，則di對應(yīng)的代表點Pi為離散點，其所在的簇中的樣本點即為孤立異常數(shù)據(jù)。

基于CURE聚類算法的異常數(shù)據(jù)檢測方法的基本思想是：首先確定情報分析的主題類別，通過信息采集和預(yù)處理階段得到原始的樣本集，然后經(jīng)過文本處理階段獲得文本向量化后的樣本集。之后，對樣本集進(jìn)行聚類。首次聚類先將樣本劃分為n個規(guī)模相同的數(shù)據(jù)分區(qū)(或簇)，每個簇的數(shù)據(jù)容量為m/n。然后計算簇中每個點的離散判定值(AD)及離群參數(shù)(δ)；對滿足di>δ×AD的異常點進(jìn)行標(biāo)注，并從樣本中刪除；之后對距離最近的簇進(jìn)行合并，然后對「n/q?個簇進(jìn)行二次聚類，同時對包含對象數(shù)目明顯偏少的簇進(jìn)行標(biāo)注和刪除，剩余的數(shù)據(jù)點就是正常數(shù)據(jù)。最后將標(biāo)注的異常數(shù)據(jù)作為異常檢測的結(jié)果輸出。

3 實驗結(jié)果分析

專利情報分析是科技情報研究的熱點課題，本文以專利情報為實例說明情報異常數(shù)據(jù)檢測過程。以國家專利網(wǎng)站專利信息作為研究對象，利用網(wǎng)絡(luò)爬蟲技術(shù)爬取了國家專利網(wǎng)站計算機類專利和醫(yī)療類專利各200條，原始文檔包括專利類別(計算機類/醫(yī)療類)、專利名稱、專利號及摘要等基本信息，部分原始數(shù)據(jù)如圖2所示。

圖2 原始專利數(shù)據(jù)

受爬蟲程序和網(wǎng)頁解析等方面的影響，爬取到的專利信息可能存在數(shù)據(jù)格式混亂、專利內(nèi)容與主題類別不符和數(shù)據(jù)重復(fù)等問題，這類數(shù)據(jù)稱為異常數(shù)這據(jù)。圖2中編號為5的樣本是在醫(yī)學(xué)類主題下爬取的，但是由其專利名稱和文摘內(nèi)容可以推斷出，它應(yīng)屬于計算機類，所以該樣本屬于異常點，其中“類別”一項的描述錯誤。同理編號205的樣本也屬于異常點。對上述樣本的專利名稱和摘要進(jìn)行分詞、去停用詞、關(guān)鍵詞提取和特征向量化，得到數(shù)據(jù)向量表示的樣本集。然后使用第2節(jié)中的基于CURE聚類算法的異常檢測方法對樣本集進(jìn)行聚類，最終得到2個點簇(標(biāo)號為1和2)和1個異常點集合(標(biāo)號為3)，如表1所示。

表1 異常檢測結(jié)果

編號樣本類別檢測結(jié)果111211311411513(異常集)………20523(異常集)………40022

其中一個簇代表醫(yī)學(xué)類專利，另一個代表計算機類專利。結(jié)果顯示，異常點集合包括編號5和編號205，這說明本文算法能夠準(zhǔn)確識別異常點。

為了進(jìn)一步說明本文異常檢測方法的有效性，避免上述實驗結(jié)果的偶然性，在原始各200條樣本的基礎(chǔ)上，繼續(xù)爬取國家專利網(wǎng)站上計算機類專利和醫(yī)療類專利，將每類專利測試樣本集的容量擴大至500條、1 000條、1 500條和2 000條。分別進(jìn)行異常檢測實驗，測試結(jié)果見表2和表3。下面以每類專利樣本容量2 000條(即總樣本容量為4 000條)為例，給出具體實驗步驟：

① 確定專利分析的主題類別為“計算機”和“醫(yī)療”，通過信息采集和預(yù)處理階段得到原始的樣本集各2 000條。

② 首先用人工標(biāo)記方法找出其中的實際異常數(shù)據(jù)，作為測試結(jié)果的評判標(biāo)準(zhǔn)。其中計算機類實際異常數(shù)據(jù)共117條，醫(yī)療類實際異常數(shù)據(jù)共121條。

③ 對原始樣本進(jìn)行文本處理，經(jīng)過中文分詞、去停用詞、關(guān)鍵詞提取和文本特征表示4個步驟獲得文本向量化后的樣本集。經(jīng)反復(fù)測試，關(guān)鍵詞數(shù)目為1 600時就能達(dá)到較好的測試精度和效率，部分關(guān)鍵詞及其權(quán)重如圖3所示。所以文本向量空間為1 600維，每條情報樣本由1 600個特征詞權(quán)重表示。

圖3 部分關(guān)鍵詞及其權(quán)重

④ 對向量化后的樣本集進(jìn)行CURE聚類，過程如圖4所示。首次聚類先將樣本劃分為10個規(guī)模相同的數(shù)據(jù)分區(qū)(或簇)，每個簇的包含400條文本向量化后的測試樣本，每條樣本記為簇中的一個點。設(shè)本次實驗的收縮因子α=0.5，代表點個數(shù)m=4，按照第2節(jié)中介紹的方法，得到最能代表以上10個簇形狀的代表點集合。然后計算簇中每個點的離散判定值A(chǔ)D值及離群參數(shù)δ；對滿足di>δ×AD的異常點進(jìn)行標(biāo)注，并從樣本中刪除。

⑤ 之后對距離最近的簇進(jìn)行合并，并對包含樣本數(shù)目明顯偏少的簇進(jìn)行標(biāo)注并刪除，然后對合并后的簇進(jìn)行再次聚類，即重新選取代表點和識別異常點，重復(fù)上述過程直到簇的數(shù)目減少至預(yù)先設(shè)定的目標(biāo)類個數(shù)2。最終經(jīng)過4次合并得到2個正常簇和1個標(biāo)注的異常點集合(下面簡稱為異常簇)，合并過程如圖4所示。2個正常簇分別代表計算機類和醫(yī)療類，異常簇里的數(shù)據(jù)作為異常檢測的結(jié)果輸出(其中包含表1所述樣本5和樣本205)。

圖4 聚類過程

本文定義了2個指標(biāo)—準(zhǔn)確率α和誤檢率β來衡量異常檢測結(jié)果的有效性，如式(7)和式(8)所示：

(7)

(8)

式中，N為實際異常數(shù)據(jù)的個數(shù)，n1為檢測異常數(shù)據(jù)中正確識別的異常個數(shù)，n2為檢測異常數(shù)據(jù)中錯誤識別的異常個數(shù)與未檢測出的實際異常個數(shù)之和。測試結(jié)果如表2和表3所示 。

表2 計算機類專利信息異常識別率

樣本數(shù)目實際異常數(shù)據(jù)數(shù)目檢測異常數(shù)據(jù)數(shù)目正確檢測數(shù)目錯誤識別數(shù)目未檢測的異常數(shù)目準(zhǔn)確率/%誤檢率/%5001918180194.745.261 0005856560296.553.451 5008485832198.813.572 0001171181135496.587.69

表3 醫(yī)療類專利信息異常識別率

樣本數(shù)目實際異常數(shù)據(jù)數(shù)目檢測異常數(shù)據(jù)數(shù)目正確檢測數(shù)目錯誤識別數(shù)目未檢測出異常數(shù)目準(zhǔn)確率/%誤檢率/%5001515141193.3313.331 0004947470295.924.081 5009087870396.673.332 0001211231185397.526.61

實驗結(jié)果表明，針對不同容量的樣本，本文提出的異常檢測方法均保持較高的檢測準(zhǔn)確率和較低的誤檢率，為后續(xù)的異常數(shù)據(jù)處理打下了基礎(chǔ)，同時對于情報數(shù)據(jù)分析提供了重要的參考價值。

4 結(jié)束語

將機器學(xué)習(xí)應(yīng)用到情報領(lǐng)域，有助于解決多源異構(gòu)的海量情報數(shù)據(jù)所導(dǎo)致的分析時效性低和準(zhǔn)確性差等問題。情報數(shù)據(jù)集的質(zhì)量是進(jìn)行情報分析和知識發(fā)現(xiàn)的基礎(chǔ)。本文提出了一種針對情報分析的異常檢測方法,分為信息采集與預(yù)處理階段、文本處理階段、CURE聚類分析階段3個部分。通過專利情報實例驗證了所提異常檢測方法的有效性和可行性，對于企業(yè)競爭、圖書館情報學(xué)等眾多互聯(lián)網(wǎng)情報研究領(lǐng)域有著一定的借鑒意義。