面向分類型矩陣數(shù)據(jù)的無(wú)監(jiān)督孤立點(diǎn)檢測(cè)算法

吳曉林，曹付元

1)山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院, 山西太原030006；2)山西大學(xué)計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室, 山西太原 030006

數(shù)據(jù)挖掘通常分為關(guān)聯(lián)規(guī)則發(fā)現(xiàn)、類別判定、類別描述和孤立點(diǎn)檢測(cè)[1]4種類型．孤立點(diǎn)檢測(cè)作為數(shù)據(jù)挖掘的一個(gè)重要任務(wù)，被廣泛用于信用卡防欺詐、 網(wǎng)絡(luò)監(jiān)測(cè)、 電子商務(wù)、 故障檢測(cè)、 惡劣天氣預(yù)報(bào)和衛(wèi)生系統(tǒng)監(jiān)測(cè)[2]等方面．HAWKINS[3]給出了孤立點(diǎn)的本質(zhì)性定義，認(rèn)為孤立點(diǎn)是在數(shù)據(jù)集中與眾不同的對(duì)象，可能這些數(shù)據(jù)并非隨機(jī)偏差，而是由完全不同的機(jī)制產(chǎn)生的． 孤立點(diǎn)檢測(cè)可以形式化地描述為：給定一個(gè)包含n個(gè)對(duì)象的數(shù)據(jù)集和期望的孤立點(diǎn)數(shù)目p， 根據(jù)算法找到明顯不同的、異常的前p個(gè)對(duì)象，這p個(gè)對(duì)象就是所要找的孤立點(diǎn)．

現(xiàn)有的孤立點(diǎn)檢測(cè)算法主要有基于距離的方法[1, 4]、基于密度的方法[5]和基于偏離的方法[6]等．這些算法的輸入都是一個(gè)包含n個(gè)對(duì)象的數(shù)據(jù)集，且每個(gè)對(duì)象由一個(gè)矢量描述．但是，在許多實(shí)際應(yīng)用中，數(shù)據(jù)集中一個(gè)對(duì)象通常由多個(gè)矢量描述．表1列舉了某超市顧客的部分購(gòu)物信息．

表1 超市顧客的部分購(gòu)物信息Table 1 Shopping information of some supermarket users

表1由兩部分組成，顧客編號(hào)、性別和年齡是顧客的基本信息，日期、產(chǎn)品編號(hào)、產(chǎn)品名稱和價(jià)錢是顧客的購(gòu)買信息．觀察表1，發(fā)現(xiàn)其中的數(shù)據(jù)具有以下特征：

1)相關(guān)性．顧客基本信息和購(gòu)買信息兩部分?jǐn)?shù)據(jù)可能存在一定的相關(guān)性，表現(xiàn)在不同性別或年齡的顧客可能有不同的購(gòu)物偏好．例如，表1中25歲和26歲的女性顧客購(gòu)買傾向相似，她們僅購(gòu)買了食品，而32歲的男性顧客則購(gòu)買了家用電器和日用品．

2)一對(duì)多．表1中每個(gè)顧客均對(duì)應(yīng)不止1條記錄．例如，顧客19910506有5條購(gòu)買記錄，而顧客19830712有6條購(gòu)買記錄．

3)混合性．描述一個(gè)對(duì)象的屬性既有分類型又有數(shù)值型．比如產(chǎn)品編號(hào)是分類型屬性，價(jià)錢是數(shù)值型屬性．

4)演化性．某些屬性值會(huì)隨著時(shí)間的推移而改變．例如，顧客19830712在某天買了生活用品，但在另一天只買了食品，顧客購(gòu)買動(dòng)態(tài)的變化隱含了顧客行為的變化．

從表1中所列的顧客購(gòu)物日期、產(chǎn)品編號(hào)、產(chǎn)品名稱和價(jià)錢可見，每個(gè)顧客可能購(gòu)買多個(gè)商品，并且每種商品可能同時(shí)被多個(gè)用戶購(gòu)買．此外，商品也可以由一個(gè)顧客多次購(gòu)買．通過(guò)交易記錄可以找到不同顧客的購(gòu)買特征．如表1中前3名顧客都買了食品，但最后一位顧客沒(méi)有買食品，他購(gòu)買了其他顧客沒(méi)有購(gòu)買的3件商品，說(shuō)明最后一位顧客與前3位用戶的購(gòu)物傾向差異最大．因此，可認(rèn)為編號(hào)為19850216的顧客在表1中是一個(gè)孤立點(diǎn)．表1所示的數(shù)據(jù)集結(jié)構(gòu)被廣泛用于銀行、保險(xiǎn)、電信和醫(yī)療等領(lǐng)域．

若使用現(xiàn)有的孤立點(diǎn)檢測(cè)算法來(lái)處理矩陣數(shù)據(jù)，最直接的方法是壓縮和轉(zhuǎn)換數(shù)據(jù)，轉(zhuǎn)換成用一個(gè)矢量表示一個(gè)對(duì)象．對(duì)于數(shù)值型變量，通常用均值來(lái)表示，而對(duì)于分類型變量，則選擇用頻率高的屬性值來(lái)代表．但是，在數(shù)據(jù)壓縮和轉(zhuǎn)換的過(guò)程中通常會(huì)有大量信息被丟失，因此該方法不足以完全反映用戶的真實(shí)行為．為更好地找出矩陣數(shù)據(jù)中的孤立點(diǎn)，需要發(fā)展新的孤立點(diǎn)檢測(cè)算法．

孤立點(diǎn)檢測(cè)是通過(guò)一種有效的方法挖掘給定數(shù)據(jù)集中與多數(shù)對(duì)象不同的少數(shù)對(duì)象，可將其視為基于對(duì)象之間定義的不相似性(相似性)度量的問(wèn)題．在實(shí)際應(yīng)用中，矩陣數(shù)據(jù)集大部分以混合屬性來(lái)描述，對(duì)于數(shù)值型描述的矩陣數(shù)據(jù)，可通過(guò)Hausdorff距離[7]或其他衍生距離公式來(lái)度量對(duì)象之間的相似性；而分類型矩陣數(shù)據(jù)之間由于缺乏固有的幾何特性，很難定義矩陣對(duì)象之間的相似性．因此，如何對(duì)分類型矩陣數(shù)據(jù)進(jìn)行孤立點(diǎn)檢測(cè)是一個(gè)非常具有挑戰(zhàn)性的問(wèn)題．

針對(duì)分類型矩陣數(shù)據(jù)，本研究通過(guò)定義一種矩陣對(duì)象本身的內(nèi)聚度和該對(duì)象與其他矩陣對(duì)象間的耦合度，給出了矩陣對(duì)象的孤立因子計(jì)算公式，提出一種面向分類型矩陣數(shù)據(jù)的孤立點(diǎn)檢測(cè)算法，并通過(guò)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性.

1 孤立點(diǎn)檢測(cè)相關(guān)工作

20世紀(jì)60年代后期，孤立點(diǎn)檢測(cè)首次被提出，并一直受到人們的關(guān)注．?dāng)?shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的不斷發(fā)展，推動(dòng)了孤立點(diǎn)檢測(cè)的研究，且進(jìn)一步產(chǎn)生了許多新算法．根據(jù)數(shù)據(jù)標(biāo)簽的可用性，可將孤立點(diǎn)檢測(cè)方法分為監(jiān)督檢測(cè)、半監(jiān)督檢測(cè)和無(wú)監(jiān)督檢測(cè)3大類．原則上，監(jiān)督檢測(cè)和半監(jiān)督檢測(cè)都需要訓(xùn)練集，而無(wú)監(jiān)督檢測(cè)不需要任何訓(xùn)練集．監(jiān)督檢測(cè)包括正類和負(fù)類標(biāo)簽的實(shí)例，而半監(jiān)督檢測(cè)訓(xùn)練集中通常只包括正類標(biāo)簽的實(shí)例．現(xiàn)階段關(guān)于監(jiān)督的孤立點(diǎn)檢測(cè)研究相對(duì)較少，下面僅討論無(wú)監(jiān)督和半監(jiān)督檢測(cè)的相關(guān)工作．

無(wú)監(jiān)督孤立點(diǎn)檢測(cè)方法不需要任何帶標(biāo)簽的數(shù)據(jù)，且假設(shè)數(shù)據(jù)集中的大多數(shù)對(duì)象是正類．根據(jù)數(shù)據(jù)類型可分為數(shù)值型孤立點(diǎn)檢測(cè)和分類型孤立點(diǎn)檢測(cè)．針對(duì)數(shù)值型數(shù)據(jù)，BREUNIG[5]提出了一種局部異常因子(local outlier factor, LOF)算法，主要通過(guò)比較對(duì)象p與其鄰域?qū)ο蟮拿芏缺戎祦?lái)判斷該對(duì)象是否為孤立點(diǎn)，該比值越接近1，表明p與其鄰域?qū)ο竺芏仍浇咏?，p可能和鄰域同屬一簇；該比值越小，說(shuō)明p的密度大于其鄰域點(diǎn)密度越多，p為密集點(diǎn)；該比值越大，說(shuō)明p的密度小于其鄰域點(diǎn)密度越多，總之，兩者差值越大，p越可能是異常點(diǎn)．此外，LOF算法易受到計(jì)算第k個(gè)近鄰距離的影響．JIANG 等[8]基于DüNTSCH等給出的信息熵模型提出了一種無(wú)監(jiān)督孤立點(diǎn)檢測(cè)算法．在一個(gè)給定的信息系統(tǒng)中，首先計(jì)算相對(duì)基數(shù)，通過(guò)對(duì)比此基數(shù)，將所有對(duì)象分為兩類：屬于少數(shù)類的對(duì)象和屬于多數(shù)類的對(duì)象．然后，計(jì)算每個(gè)對(duì)象的相對(duì)熵，屬于少數(shù)群體且相對(duì)熵很高的對(duì)象更可能成為一個(gè)孤立點(diǎn)．針對(duì)分類型數(shù)據(jù)，WU 等[9]提出了一種基于信息理論的分類型無(wú)監(jiān)督孤立點(diǎn)檢測(cè)算法，基于熵和全相關(guān)系數(shù)提出了全熵的概念，給出了一個(gè)孤立點(diǎn)的新定義，并建立了孤立點(diǎn)檢測(cè)的優(yōu)化模型．基于該模型，定義了對(duì)象的孤立因子的函數(shù)公式，提出ITB-SS和ITB-SP兩種孤立點(diǎn)檢測(cè)方法．PANG等[10]介紹了一種新的框架SelectVC，它通過(guò)迭代學(xué)習(xí)選擇值耦合將值選擇和孤立點(diǎn)得分組合去發(fā)現(xiàn)高維分類型數(shù)據(jù)中的孤立點(diǎn)，通過(guò)實(shí)例POP(partial outlierness propagation)驗(yàn)證了SelectVC的性能．

半監(jiān)督孤立點(diǎn)檢測(cè)方法在訓(xùn)練階段不需要負(fù)類標(biāo)簽的實(shí)例，只需要在訓(xùn)練數(shù)據(jù)集中構(gòu)建正類實(shí)例的模型，將測(cè)試數(shù)據(jù)集中與正類模型不同的實(shí)例識(shí)別為孤立點(diǎn)．針對(duì)數(shù)值型數(shù)據(jù)，DANESHPAZHZHOUH等[11]提出了一種在給定少數(shù)正類實(shí)例標(biāo)簽信息情況下的半監(jiān)督孤立點(diǎn)檢測(cè)算法，該算法分為兩個(gè)階段：首先，從正類和未標(biāo)記的實(shí)例中提取一個(gè)負(fù)類候選集；然后，在候選集中采用基于信息熵的算法來(lái)檢測(cè)前N個(gè)孤立點(diǎn)．通過(guò)第1階段的計(jì)算，數(shù)據(jù)集的大小顯著減少，降低了算法的時(shí)間復(fù)雜度．TANG等[12]提出了一種基于局部核密度估計(jì)的局部孤立點(diǎn)檢測(cè)算法，通過(guò)考慮k個(gè)最近鄰、反向最近鄰和共享最近鄰來(lái)估計(jì)局部核密度，計(jì)算每個(gè)對(duì)象的相對(duì)密度來(lái)檢測(cè)孤立點(diǎn)．針對(duì)分類型數(shù)據(jù)，NOTO等[13]提出了一個(gè)處理分類型數(shù)據(jù)的半監(jiān)督孤立點(diǎn)檢測(cè)算法，利用訓(xùn)練集中的正實(shí)例構(gòu)建一組特征模型，然后將與這些模型不匹配的實(shí)例識(shí)別為孤立點(diǎn)．LENCO等[14]介紹了一種處理分類型數(shù)據(jù)的半監(jiān)督孤立點(diǎn)檢測(cè)算法，給定一組訓(xùn)練實(shí)例(都屬于正常類)，分析特征之間的關(guān)系，建立一個(gè)表示正常實(shí)例特征的模型，然后使用一組基于分類屬性距離的技術(shù)來(lái)區(qū)分正常類數(shù)據(jù)和異常類數(shù)據(jù)．綜上可知，盡管現(xiàn)階段孤立點(diǎn)檢測(cè)算法有很多，但是處理的數(shù)據(jù)集中每個(gè)對(duì)象都是由1條記錄描述，對(duì)于矩陣數(shù)據(jù)集尚無(wú)有效處理算法，為此，本研究提出一種針對(duì)分類型矩陣數(shù)據(jù)的孤立點(diǎn)檢測(cè)算法.

2 一種分類型矩陣數(shù)據(jù)無(wú)監(jiān)督孤立點(diǎn)檢測(cè)算法

通常用孤立因子定義一個(gè)對(duì)象的孤立程度. 在軟件工程中，通常以耦合度和內(nèi)聚度為標(biāo)準(zhǔn)來(lái)衡量模塊的獨(dú)立程度．耦合度是軟件系統(tǒng)結(jié)構(gòu)中模塊之間緊密程度的度量．模塊之間的連接越緊密，耦合性越強(qiáng)，模塊的獨(dú)立性越差．內(nèi)聚度是衡量模塊功能強(qiáng)弱的指標(biāo)，如果模塊中的元素緊密相關(guān)，則模塊的內(nèi)聚度就高．本研究通過(guò)矩陣對(duì)象與其他對(duì)象之間的耦合程度，以及其自身的內(nèi)聚程度來(lái)確定一個(gè)對(duì)象的孤立因子．

2.1 耦合度

定義1給定一個(gè)矩陣數(shù)據(jù)集X， 對(duì)于任意Aj∈A， IND({Aj})是由Aj確定的不可區(qū)分關(guān)系，X/IND({Aj})={B1,B2,…,Bk}記為由IND({Aj})導(dǎo)出的一個(gè)劃分． IND({Aj})在X上的信息熵定義為

(1)

(2)

其中，Xis在屬性Aj上的相對(duì)信息熵REAj(Xis)，且

(3)

對(duì)于任意Aj∈A，Xis∈X， 當(dāng)刪除By時(shí)，若信息熵大幅降低，則可認(rèn)為By中的元素在X中出現(xiàn)的頻率很低；反之，若信息熵減幅很小或增加，則認(rèn)為By中的元素在X中出現(xiàn)的頻率很高．因此，相對(duì)信息熵REAj(Xis)能夠反映Xis的孤立程度．相對(duì)信息熵REAj(Xis)越高，則Xis越孤立．

若X/IND({Aj})={By,X-By}， 則MEAj(Xis,By)=0， 相應(yīng)地， REAj(Xis)=1． 因此，對(duì)于任意的Xis∈X, 有0≤REAj(Xis)≤1．

給定一個(gè)矩陣數(shù)據(jù)集X， 為找到X中的孤立點(diǎn)，首先可根據(jù)一個(gè)給定的標(biāo)準(zhǔn)將X中的所有對(duì)象分成兩類：屬于X中的少數(shù)群體的對(duì)象和屬于X中多數(shù)群體的對(duì)象．此標(biāo)準(zhǔn)可定義為：

(4)

若RC(Xis,By)>0， 則Xis屬于多數(shù)類；反之，若RC(Xis,By)≤0， 則Xis屬于少數(shù)類．

ODAj(Xis)= REAj(Xis)×

(5)

少數(shù)類中對(duì)象與多數(shù)類中的對(duì)象相比，少數(shù)類中對(duì)象更可能為孤立點(diǎn)．如果RC(Xis,By)≤0， 則Xis屬于少數(shù)類；相應(yīng)地，相對(duì)信息熵REAj(Xis)越大，孤立度也越大，因此，Xis可能越孤立．

基于給定Xis∈X在屬性Aj上的孤立度，下面給出矩陣對(duì)象耦合度的定義．

定義5給定一個(gè)矩陣數(shù)據(jù)集X， 對(duì)于任意一個(gè)對(duì)象Xi， 耦合度定義為

Cou(Xi)=

(6)

2.2 內(nèi)聚度

考慮對(duì)象的耦合度后，可進(jìn)一步定義矩陣對(duì)象的內(nèi)聚度．

(7)

由于0≤MEAj(Xi)≤lbri， 所以歸一化為HEAj(Xi)=MEAj(Xi)/lbri．

可見，一個(gè)矩陣對(duì)象內(nèi)聚度可定義為

(8)

2.3 孤立因子

在定義了一個(gè)矩陣對(duì)象的耦合度和內(nèi)聚度的基礎(chǔ)上，該矩陣對(duì)象的孤立因子可定義為：

定義7給定一個(gè)矩陣對(duì)象Xi， 其孤立因子為

OF(Xi)= (1-Cou(Xi))×

(1+Coh(Xi))

(9)

在矩陣數(shù)據(jù)中檢測(cè)孤立點(diǎn)，既要考慮矩陣對(duì)象的耦合度，也要考慮內(nèi)聚度，但對(duì)象的耦合度占主要因素，因此，要減少內(nèi)聚度所占的權(quán)重，將內(nèi)聚度加1．矩陣對(duì)象的孤立因子越大，孤立度越大．

2.4 例子

給定一個(gè)矩陣數(shù)據(jù)集X={X1,X2,X3,X4,X5}，A={A1,A2}， 見表2．

表2 一個(gè)矩陣數(shù)據(jù)集Table 2 A matrix-object data set

矩陣對(duì)象X1的孤立因子計(jì)算過(guò)程如下：

1)根據(jù)定義2，每個(gè)屬性上的信息熵分別為

ME({A1})=1.927 5

ME({A2})=1.828 9

2)根據(jù)定義3，對(duì)象X1中，每個(gè)X1s所在的等價(jià)類刪除時(shí)的信息熵為

MEA1(X11)=1.685 5

MEA2(X11)=MEA2(X13)=1.657 7

MEA1(X12)=MEA1(X13)=1.488 5

MEA2(X12)=1.352 0

由此可得相對(duì)熵

REA1(X11)=0.125 5

REA2(X11)=REA2(X13)=0.093 6

REA1(X12)=REA1(X13)=0.227 7

REA2(X12 )=0.260 7

3)根據(jù)定義4，相對(duì)標(biāo)準(zhǔn)為

RC([X11]A1)= 5.500 0

RC([X11]A2)=RC([X13]A2)=6.750 0

RC([X12]A1)=RC([X13]A1)=1.750 0

RC([X12]A2)=1.750 0

4)根據(jù)定義5，可得

ODA1(X11)=0.043 6

ODA2(X11)=ODA2(X13)=0.029 2

ODA1(X12)=ODA1(X13 )=0.102 8

ODA2(X12 )=0.117 7

5)根據(jù)定義6，可得對(duì)象X1的耦合度為

Cou(Xi)=0.570 2

6)根據(jù)定義7，可得對(duì)象X1的內(nèi)聚度為

Coh(Xi)=0.579 2

7)根據(jù)定義8可得對(duì)象X1的孤立因子為

OF(X1 )=0.678 8

同理可得，OF(X2 )=0.820 3、OF(X3 )= 0.820 3、OF(X4 )= 0.728 1和OF(X5 )=1.265 9． 可見，X5的孤立因子最大，即孤立度最大．

3.5 算法實(shí)現(xiàn)

圖1給出了分類型矩陣數(shù)據(jù)孤立點(diǎn)檢測(cè)算法(outlier detection algorithm for matrix-object data, ODAMD)的偽代碼．

圖1 ODAMD算法偽代碼Fig.1 The pseudocode of ODAMD algorithm

3 實(shí) 驗(yàn)

為驗(yàn)證本算法的有效性，在3個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，分別是從Data website(http://www.datatang.com)下載的Market basket data； 從UCI網(wǎng)站(http://archive.ics.uci.edu/ml)下載的Microsoft web data； 從MovieLens 網(wǎng)站(http://grouplens.org/datasets/movielens/)上下載的MovieLens data．首先，對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理并給出評(píng)價(jià)指標(biāo)；然后，將提出的方法與3種孤立點(diǎn)檢測(cè)算法進(jìn)行比較．

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

在大多數(shù)情況下，真實(shí)數(shù)據(jù)集的分布是無(wú)序的．實(shí)驗(yàn)中3個(gè)真實(shí)數(shù)據(jù)集中的孤立點(diǎn)也沒(méi)有明確標(biāo)注信息．為解決此問(wèn)題，首先要對(duì)給定的數(shù)據(jù)集進(jìn)行預(yù)處理．通過(guò)可視化技術(shù)，可以刪除一些點(diǎn)，以獲得相對(duì)清晰的數(shù)據(jù)分布，也可以清楚地看到一些對(duì)象是孤立的，因此，能夠得到一個(gè)帶有標(biāo)記信息的數(shù)據(jù)集.最后，在新的數(shù)據(jù)集上運(yùn)行本算法并評(píng)估算法的性能．為獲得給定分類型數(shù)據(jù)集的分布，使用多維尺度變換(multi-dimensional scaling, MDS)技術(shù)[15]來(lái)可視化數(shù)據(jù)集，該技術(shù)的主要方法是將距離公式獲得的n階距離方陣傳遞給Matlab的mdscale函數(shù)，獲得n個(gè)點(diǎn)的坐標(biāo)，然后可視化這n點(diǎn)來(lái)反映數(shù)據(jù)的分布．以下是3個(gè)真實(shí)數(shù)據(jù)集的預(yù)處理過(guò)程．

3.1.1 Market basket data

從Data website下載的Market basket data記錄了1 001個(gè)用戶交易信息，每個(gè)用戶有4個(gè)屬性(用戶ID、時(shí)間、產(chǎn)品名稱和產(chǎn)品ID)．本研究只考慮用戶ID和產(chǎn)品ID，而不考慮時(shí)間和產(chǎn)品名稱，因?yàn)樗杏脩粼趯傩詴r(shí)間上都具有相同的值，而產(chǎn)品名稱的值與產(chǎn)品ID是一一對(duì)應(yīng)的． 此外，Market basket data的突出特點(diǎn)是每個(gè)用戶都有7條交易記錄． 因此， 每個(gè)用戶是一個(gè)典型的分類型矩陣對(duì)象．

圖2 預(yù)處理后的Market basket數(shù)據(jù)集分布Fig.2 Distribution of preprocessed Market basket data

Market basket data的預(yù)處理過(guò)程為：首先，通過(guò)MDS技術(shù)對(duì)數(shù)據(jù)集進(jìn)行可視化；然后，在坐標(biāo)系中選擇位于x<-0.2，y<0.2或x>0.5內(nèi)的對(duì)象，形成一個(gè)包含319個(gè)矩陣對(duì)象的新數(shù)據(jù)集．新數(shù)據(jù)集的分布如圖2．其中，“+”和“+×”表示新生成的數(shù)據(jù)集，“+”表示的對(duì)象可認(rèn)為孤立點(diǎn)．從圖2可見，經(jīng)過(guò)統(tǒng)計(jì)分析可得，“+”表示的對(duì)象屬性值出現(xiàn)頻率很低．

3.1.2 Microsoft web data

從UCI下載的Microsoft web data是通過(guò)對(duì)網(wǎng)站www.microsoft.com上的日志進(jìn)行采樣和處理而創(chuàng)建的．它記錄了32 711名匿名用戶在1998年2月訪問(wèn)該網(wǎng)站時(shí)的信息，每個(gè)人可多次訪問(wèn)網(wǎng)站．每個(gè)用戶都有2個(gè)屬性，包括用戶ID和統(tǒng)一資源定位符(uniform resource locator, URL)． 因此， 每個(gè)用戶都是一個(gè)分類型矩陣對(duì)象．

預(yù)處理過(guò)程為：在初始數(shù)據(jù)可視化后，選擇橫坐標(biāo)值位于x<0或x>0.68的點(diǎn)，形成589個(gè)對(duì)象的新矩陣數(shù)據(jù)集，然后可視化新矩陣數(shù)據(jù)集，結(jié)果如圖3．

圖3 預(yù)處理后的Microsoft web數(shù)據(jù)集分布Fig.3 Distribution of preprocessed Microsoft web data

從圖3可見，數(shù)據(jù)集由兩部分組成，其中由符號(hào)“+”表示的對(duì)象可被視為新數(shù)據(jù)集中的孤立點(diǎn)．

3.1.3 MovieLens data

實(shí)驗(yàn)使用了MovieLens數(shù)據(jù)集，它包含6 040個(gè)用戶對(duì)3 900部電影的1 000 209條評(píng)分，由4個(gè)屬性表示，分別為UserID(用戶編號(hào))、MovieID(電影編號(hào))、Rating(評(píng)分)和Timestamp(時(shí)間)．因?yàn)閷傩訲imestamp在每個(gè)記錄具有不同的值，因此不考慮該屬性．

預(yù)處理過(guò)程為：在初始數(shù)據(jù)集可視化后，選擇坐標(biāo)系中-0.10.6范圍內(nèi)的對(duì)象作為新的數(shù)據(jù)集．新數(shù)據(jù)的可視化結(jié)果如圖4．

圖4 預(yù)處理后的MovieLens數(shù)據(jù)集分布Fig.4 Distribution of preprocessed MovieLens data

從圖4可見，數(shù)據(jù)集是由一個(gè)大類和一些散點(diǎn)組成的，這些由符號(hào)“+”描繪的散點(diǎn)可看作是孤立點(diǎn)．

3.1.4 數(shù)據(jù)預(yù)處理結(jié)果

預(yù)處理后的數(shù)據(jù)集如表3．其中，p為孤立點(diǎn)的數(shù)目．

表3 預(yù)處理后的數(shù)據(jù)集Table 3 Preprocessed data set

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

為驗(yàn)證孤立點(diǎn)檢測(cè)算法的性能，使用精確度(Precision)、召回率(Recall)、F-度量(F-measure)[16]進(jìn)行評(píng)價(jià)．這3個(gè)評(píng)價(jià)指標(biāo)的計(jì)算公式分別為

(10)

(11)

(12)

其中，TruePositive為檢索到準(zhǔn)確的孤立點(diǎn)數(shù)目；FalsePositive為檢索到不是孤立點(diǎn)的數(shù)目；FalseNegative為未檢索到的孤立點(diǎn)數(shù)目.

精確度是檢索出的相關(guān)文檔數(shù)與檢索出的文檔總數(shù)的比率，衡量的是檢索系統(tǒng)的查準(zhǔn)率；召回率是檢索出的相關(guān)文檔數(shù)與文檔庫(kù)中所有相關(guān)文檔數(shù)的比率，衡量的是檢索系統(tǒng)的查全率；F-度量是這兩個(gè)指標(biāo)的綜合評(píng)價(jià)指標(biāo)，用來(lái)反映總體指標(biāo)．Precision和Recall的值在[0, 1]內(nèi)，且越接近1，實(shí)驗(yàn)結(jié)果越好．

3.3 實(shí)驗(yàn)結(jié)果

為驗(yàn)證本研究提出的孤立點(diǎn)檢測(cè)算法的有效性，將ODAMD算法與基于共同近鄰(common-neighbor-besed, CNB)算法[17]、LOF和基于信息熵(information entropy-beased, IE-based)算法[8]進(jìn)行比較．由于現(xiàn)階段沒(méi)有方法可以處理分類型矩陣數(shù)據(jù)集，所以先將矩陣數(shù)據(jù)集進(jìn)行了壓縮，每個(gè)矩陣對(duì)象用頻率最高的屬性值來(lái)表示，新生成的數(shù)據(jù)集中，一個(gè)對(duì)象只有一條記錄，然后在新生成的數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)．

真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果如表4至表6．從表4至表6可見，提出的孤立點(diǎn)檢測(cè)算法效率很高，但其他方法并不理想. 因?yàn)閿?shù)據(jù)集進(jìn)行壓縮時(shí)，會(huì)導(dǎo)致許多信息的丟失．

表4 不同算法在真實(shí)數(shù)據(jù)集中的精確度Table 4 Precision of different algorithms in real data sets

表5 不同算法在真實(shí)數(shù)據(jù)集中的召回率Table 5 Recall of different algorithms in real data sets

表6 不同算法在真實(shí)數(shù)據(jù)集中的F-度量Table 6 F-measure of different algorithms in real data sets

為進(jìn)一步驗(yàn)證提出的算法的擴(kuò)展性，在真實(shí)數(shù)據(jù)集上設(shè)置不同的孤立點(diǎn)數(shù)目，檢測(cè)新算法與比較算法的精確度，實(shí)驗(yàn)結(jié)果如圖5至圖7.

圖5 不同算法在Market basket數(shù)據(jù)集上不同孤立點(diǎn)數(shù)目的精確度Fig.5 (Color online) Precision of different algorithms for different number of outliers in Market basket data

圖6 不同算法在Microsoft web數(shù)據(jù)集上不同孤立點(diǎn)數(shù)目下的精確度Fig.6 (Color online) Precision of different algorithms for different number of outliers in Microsoft web

圖7 不同算法在MovieLens數(shù)據(jù)集上不同孤立點(diǎn)數(shù)目下的精確度Fig.7 (Color online) Precision of different algorithms for different number of outliers in MovieLens data

從圖5至圖7可見，隨著孤立點(diǎn)數(shù)目的增加，提出算法的準(zhǔn)確率比較高且比較穩(wěn)定，而3個(gè)比較算法精確度偏低，且不穩(wěn)定.比如CNB算法在數(shù)據(jù)集中存在4個(gè)孤立點(diǎn)時(shí)，精確度為1，但在其他孤立點(diǎn)數(shù)目的情況下，精確度比較低．

結(jié) 語(yǔ)

針對(duì)在實(shí)際應(yīng)用中廣泛存在的分類型矩陣數(shù)據(jù)，提出一種新的孤立點(diǎn)檢測(cè)算法ODAMD．首先，定義了一個(gè)矩陣對(duì)象與其他對(duì)象間的耦合度；然后，基于信息熵定義了一個(gè)矩陣對(duì)象自身的內(nèi)聚度，在此基礎(chǔ)上給出了分類型矩陣對(duì)象的孤立因子計(jì)算方法．在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果證明，本研究提出的孤立點(diǎn)檢測(cè)算法行之有效．