基于高效離群數(shù)據(jù)分析方法的客戶信息及特征屬性挖掘

夏火松,魏 翔

0 引言

在Web客戶信息處理過程中，面對龐大的數(shù)據(jù)庫，人們所需的信息只是其中的小部分，而且往往是其中較為特殊的一部分信息，它們隱藏在海量數(shù)據(jù)當中。如何能夠快速而有效地找到它們并且能夠獲知其特殊的原因，就成為當務之急。目前，成熟的信息管理技術(shù)能夠為用戶提供數(shù)據(jù)獲取、存儲、管理、搜索等豐富的功能，而以分類、聚類、關(guān)聯(lián)分析為主的數(shù)據(jù)挖掘技術(shù)也不斷發(fā)展和完善，但離群數(shù)據(jù)的挖掘技術(shù)及其應用卻仍然十分有限，其原因在于現(xiàn)有的離群數(shù)據(jù)挖掘算法的效率依然不高，穩(wěn)定性也不強，其所得到的離群信息也很有限。針對客戶信息管理過程中的這些情況，本文將在傳統(tǒng)的離群數(shù)據(jù)挖掘算法的基礎(chǔ)上，以保持挖掘結(jié)果穩(wěn)定性為前提，以提高挖掘效率為目標，嘗試探索出新的途徑。為了在檢測離群數(shù)據(jù)的同時也能夠獲得其為什么離群的相關(guān)信息，本文將把特征屬性挖掘的過程融入其中。

1 理論回顧

1.1 離群數(shù)據(jù)分析方法

離群數(shù)據(jù)分析方法主要有以下幾種：一是基于統(tǒng)計的方法[1]，已知或假定給定數(shù)據(jù)集符合某種概率分布模型，然后通過對該模型進行不一致性檢驗來確定離群數(shù)據(jù)，這一檢驗過程需要知道數(shù)據(jù)的分布模型及其參數(shù)以及預期的離群數(shù)據(jù)數(shù)目；二是基于距離的方法，定義和計算數(shù)據(jù)對象與數(shù)據(jù)集中其它對象的距離并以此來查找該數(shù)據(jù)對象的鄰居數(shù)量，離群數(shù)據(jù)即為那些鄰居數(shù)量不足的數(shù)據(jù)對象，該方法不依賴于統(tǒng)計模型及檢驗；三是基于密度的方法[2～4]，從數(shù)據(jù)對象間的距離的概念出發(fā)，結(jié)合數(shù)據(jù)對象的鄰居數(shù)量或與鄰居的平均距離得到了“密度”的概念，該方法能夠檢測到一類特殊的離群數(shù)據(jù)——局部離群數(shù)據(jù)，最有代表性的算法即是Breunig等提出的LOF算法[5]；四是基于深度的方法，先把每個數(shù)據(jù)對象映射為維數(shù)據(jù)空間中的點并賦予深度值，再依據(jù)深度值按層重組數(shù)據(jù)集，然后在深度較小的層中搜索離群數(shù)據(jù)，該方法僅在維度低于4的數(shù)據(jù)集上應用效果較好，有代表性的算法是DEEPLOC算法[6]；五是基于偏離的方法[7～8]，通過對數(shù)據(jù)集的主要特征進行檢測來發(fā)現(xiàn)離群數(shù)據(jù)，目前該方法及其算法大多數(shù)還停留在理論研究上，實際應用較少。本文所做的研究是基于距離的方法展開的。

1.2 基于距離的離群挖掘方法

基于距離的離群數(shù)據(jù)挖掘方法最初是由Knorr和Ng提出的[9]，給定數(shù)據(jù)集T，如果T中存在超過p部分的數(shù)據(jù)與某一個數(shù)據(jù)對象O之間的距離大于D值，則稱數(shù)據(jù)對象O為基于距離的離群數(shù)據(jù)，記為DB(p,D)-outlier，其中p和D是參數(shù)。這一方法的提出，不僅為離群數(shù)據(jù)挖掘提供了一種新的算法，而且為研究者們打開了思路，為后續(xù)離群數(shù)據(jù)挖掘算法的提出做了鋪墊。基于距離的離群數(shù)據(jù)挖掘算法的優(yōu)點在于，能夠直觀地反映離群數(shù)據(jù)與數(shù)據(jù)集中其它數(shù)據(jù)之間的關(guān)系，且易于理解和計算，在實際應用中也收到了良好的效果。這種方法實際上已經(jīng)包含并擴展了早期的基于統(tǒng)計的算法思想，同時相對不一致性檢驗所需的計算量來看，該方法的計算量已顯著降低，故其在應用中能夠達到和超越基于統(tǒng)計的算法的效果。另外，它對數(shù)據(jù)集中數(shù)據(jù)的維數(shù)沒有限制，可以完成對高維數(shù)據(jù)的處理和挖掘工作。

但這種方法也存在很大的缺陷，需要用戶給出參數(shù)p和D的值才能進行離群數(shù)據(jù)挖掘，然而這兩個參數(shù)卻很難給的恰到好處，同時其值的微小變化都有可能對最終的結(jié)果造成較大影響，這就需要用戶憑經(jīng)驗做出判斷并對進行p和D的取值反復嘗試以求得到較好的結(jié)果。這不僅給用戶使用帶來諸多不便，而且這一不確定性嚴重影響了結(jié)果的穩(wěn)定性和算法應用的廣度和深度。此外，該方法不能有效地反映離群程度，雖然相對基于統(tǒng)計的方法計算量顯著下降但其復雜度仍然較高，為O(d?N2)，其中d為數(shù)據(jù)集中數(shù)據(jù)對象的維度，N為數(shù)據(jù)對象的數(shù)量。針對這些主要缺陷，很多學者對算法進行了不同程度的改進，如基于索引的算法[10]引進了索引的思想來改進算法，但建立索引需要一定時間；循環(huán)嵌套算法主要通過減少I/O的次數(shù)來改善算法的效率；基于單元的算法[11]通過將數(shù)據(jù)集劃分為單元，利用單元及其鄰居的性質(zhì)來發(fā)現(xiàn)異常數(shù)據(jù)，從而提高了檢測的效率。

1.3 離群特征屬性

在離群數(shù)據(jù)挖掘算法的應用過程中，用戶查找到離群數(shù)據(jù)后，自然會關(guān)心是哪些屬性導致離群數(shù)據(jù)與其它數(shù)據(jù)不同的，即它為什么離群，于是有學者提出了離群數(shù)據(jù)知識集[12]的概念。一個高維空間上的離群數(shù)據(jù)的離群特征往往在該空間的子空間上就會表現(xiàn)出來了。這就需要尋找到能夠解釋離群數(shù)據(jù)為什么離群的屬性集合。離群數(shù)據(jù)知識集就是描述離群數(shù)據(jù)離群的最小屬性集合，它通過數(shù)據(jù)的屬性來反映離群數(shù)據(jù)的異常行為特征，這些屬性能夠解釋離群數(shù)據(jù)發(fā)生異常的原因，可以對離群數(shù)據(jù)的合理性和有效性進行評價，它們就是離群特征屬性。在檢測出離群數(shù)據(jù)并發(fā)現(xiàn)其相應的離群特征屬性后，離群數(shù)據(jù)與導致其離群的屬性間的對應關(guān)系就一目了然了，用戶可以直觀地了解離群數(shù)據(jù)之所以離群的緣由。

2 離群數(shù)據(jù)及其離群屬性空間挖掘模型

2.1 模型建立

定義1包含有n個數(shù)據(jù)對象Ai(i=1,2,…,n)，且每個數(shù)據(jù)對象Ai有d維屬性aik(i=1,2,…,n;k=1,2,…,d)的數(shù)據(jù)集記為Dataset(n,d)。

定義2由d維屬性Vk(k=1,2,…,d)構(gòu)成的屬性空間為其子空間SubSpace(Dim)=∏k∈DimVk，其中Dim?{1,2,…,d}，并用|Dim|表示集合Dim所包含的元素數(shù)量，即為子空間SubSpace(Dim)的維數(shù)。

根據(jù)定義1和定義2，對數(shù)據(jù)集Dataset(n,d)中各個數(shù)據(jù)對象Ai(i=1,2,…,n)的每一維屬性分量aik(i=1,2,…,n;k=1,2,…,d)有aik∈Vk(i=1,2,…,n;k=1,2,…,d),進而Ai∈Space(d)，故數(shù)據(jù)集可以表示為Dataset(n,d)={Ai|Ai∈ Space(d),i=1,2,…,n}。

距離的定義有很多種，這里引入兩種應用最為廣泛的距離定義，歐氏距離(即歐幾里得距離)和絕對距離(即曼哈頓距離)，它們的定義如下：

定義3在多維屬性空間SubSpace(Dim)中，數(shù)據(jù)對象Ai={aik|k∈Dim}與Aj={ajk|k∈Dim}的歐氏距離和絕對距離分別為：

其中{wk}為權(quán)重系數(shù)集。

定義4在多維屬性空間SubSpace(Dim)中，某數(shù)據(jù)對象Ai與最近的m個最近鄰居Aj1,Aj2,…,Ajm之間的距離的平均值，稱為平均近鄰距離，記為dist_MND，即

這里dist.表示一種距離，即用歐氏距離或絕對距離進行計算(下文同)。

例如，一個二維空間中的六個數(shù)據(jù)對象如圖1所示，圖中用虛線標示出了數(shù)據(jù)對象A2和A6分別與各自最近的三個鄰居的連接，以及相應的平均近鄰距離的圓弧大小。很明顯，在這六個數(shù)據(jù)對象中，A6屬于離群對象，其平均近鄰距離較大，而其它非離群對象的平均近鄰距離則相對較小。為了能對其進行數(shù)值上的比較，需進一步作一些定義。

圖1

定義5在多維屬性空間SubSpace(Dim)中，記dist_Max為最大可達距離，即

定義6(離群因子)數(shù)據(jù)對象Ai的離群因子(Outlier Factor)為：

該離群因子通過計算基于已選定屬性空間的每一個數(shù)據(jù)對象的平均近鄰距離與該屬性空間中的最大可達距離的比值，來衡量各個數(shù)據(jù)對象的離群程度，既能通過數(shù)據(jù)對象與最近鄰居的距離來反映其偏離的程度，又可以通過將其與最大可達距離求比值來統(tǒng)一數(shù)量等級，以便于對數(shù)據(jù)對象在基于不同屬性空間下的離群因子進行考察和比較。為了進一步研究離群數(shù)據(jù)對象的離群原因，即其特征屬性，下面對離群屬性空間作定義。

定義7(離群屬性空間)若數(shù)據(jù)對象Ai在屬性空間SubSpace(Dim)及其任意子空間中是離群數(shù)據(jù)對象，則稱該屬性空間為Ai的離群屬性空間，則|Dim|即為該離群屬性空間的維數(shù)。

定義8(離群特征屬性)數(shù)據(jù)對象Ai的離群屬性空間中的各維屬性即構(gòu)成該數(shù)據(jù)對象的離群特征屬性的集合，記為OFA(Ai)。

由上述對圖1的分析，在這二維空間中的六個數(shù)據(jù)對象中A6是離群數(shù)據(jù)對象。若分別將它們對兩個維度Vk1和Vk2作投影，如下圖所示，圖2(a)中，A1的投影點明顯偏離其它五個數(shù)據(jù)對象的投影點，說明A2在維度Vk1為離群數(shù)據(jù)對象，即該維度為離群數(shù)據(jù)對象A2的一維離群屬性空間。圖2(b)中，此六個數(shù)據(jù)對象在維度Vk2上的投影點均沒有明顯偏離，因而該維度不屬于離群數(shù)據(jù)對象A2的離群屬性空間。因此，OFA(Ai)=Vk1，Vk1即為A2的離群特征屬性。

圖2

離群數(shù)據(jù)對象的離群特征屬性是反映其離群的主要原因，本文擬從數(shù)據(jù)對象的每一維屬性出發(fā)，設(shè)計離群數(shù)據(jù)挖掘方法，以期在挖掘離群數(shù)據(jù)的同時發(fā)現(xiàn)離群數(shù)據(jù)對象的多維離群特征屬性。

2.2 過程設(shè)計

步驟1：對數(shù)據(jù)集中所有數(shù)據(jù)對象就其在每一維屬性Vk(k=1,2,…,d)上的屬性值{aik}(i=1,2,…,n),?k=1,2,…,d，分別進行排序操作得到{as1k,as2k,…,asnk},?k=1,2,…,d，使 得 as1k＜as2k＜…＜asnk，其 中{s1,s2,…,sn}是{1,2,…,n}的一個排列，相當于是排序后的屬性值對應原始數(shù)據(jù)集中屬性值的位置指針。

步驟2：對每一維屬性Vk(k=1,2,…,d)上的所有數(shù)據(jù)對象計算dist_MND(Ai,k,m)值，?k=1,2,…,d，采用的是絕對距離進行計算。由于步驟1中已經(jīng)對屬性Vk上的屬性值進行了排序，因此該值可以通過對{as1k,as2k,…,asnk}中連續(xù)的m+1個值計算絕對距離及相應均值即可，并對首尾兩處的計算稍作調(diào)整，具體如下：

步驟3：計算各維屬性Vk(k=1,2,…,d)中的最大可達距離dist_Max(k),?k=1,2,…,d，由于步驟1中已對屬性值排序，并擬采用絕對距離進行計算，則

步驟4：計算每個數(shù)據(jù)對象Ai(i=1,2,…,n)的一維離群因子OF(Ai,k,m)，并將其就所選維度集合Dim求和值作為綜合離群因子，即

步驟5：將OF(Ai,Dim,m)值進行逆序排序，取其前p?100%項對應的Ai及其中間過程結(jié)果作為最終的離群數(shù)據(jù)挖掘結(jié)果輸出。這些輸出結(jié)果包括：綜合離群因子OF(Ai,Dim,m)，作為離群數(shù)據(jù)離群程度衡量指標，一般取前0.1%-5%作為離群數(shù)據(jù)，也可由用戶自行選擇；一維屬性離群因子OF(Ai,k,m)，作為離群特征屬性判別依據(jù)，一般以該離群數(shù)據(jù)的最大的[|Dim|?20%]+1個一維屬性離群因子所對應的屬性作為離群特征屬性。此外，將各數(shù)據(jù)對象按各一維屬性離群因子進行排序，可為進一步分析離群原因提供參考依據(jù)。

2.3 挖掘方法說明與比較分析

2.3.1 復雜度比較分析

采用上述方法進行挖掘的主要耗時部分在于步驟1，即對各個數(shù)據(jù)對象在每一維屬性維度上進行排序。目前，排序算法已經(jīng)非常成熟，我們采用的是穩(wěn)定的歸并排序[13]的方法，其時間復雜度為O(n?log2n)，空間復雜度為O(n)。因而步驟1的時間復雜度為O(d?n?log2n)，空間復雜度為O(d?n)，而步驟2、步驟3和步驟4的時間復雜度為O(n)，故該挖掘方法的時間復雜度為O(d?n?log2n)，空間復雜度為O(d?n)。這與傳統(tǒng)的離群數(shù)據(jù)分析方法的時間復雜度O(d?n2)相比，降低了一個數(shù)量等級，而空間復雜度并沒有增加。

從實際運用角度來看，首先，該方法可以大大縮減數(shù)據(jù)預處理的過程，而傳統(tǒng)方法往往要經(jīng)過大量的數(shù)據(jù)處理才能進行進一步操作。其次，該方法充分利用了排序原理，運用成熟的排序算法可以顯著調(diào)高整體的處理速度。再次，該方法將離群數(shù)據(jù)分析與其相應特征屬性挖掘過程兼并完成，而無需進行二次挖掘。這也是較為突出的一點。

3.3.2 I/O情況分析

從輸入方面看，該方法自始至終需要用戶確定的參數(shù)有三個，此三個參數(shù)非常容易確定，且可以直接應用默認值，而不會對挖掘結(jié)果造成顯著影響。這三個參數(shù)分別是m，Dim，p。其中，根據(jù)方法的內(nèi)在性質(zhì)及相關(guān)試驗表明，對較為緊密的數(shù)據(jù)集處理時m設(shè)定為1或2即可，當檢測結(jié)果不理想或數(shù)據(jù)集較為稀疏時可以設(shè)定2≤m≤5，一般不超過6。參數(shù)Dim實際上是讓用戶選定對哪幾維度進行離群數(shù)據(jù)和相應特征屬性檢測，一般選擇所有維度或根據(jù)需要選擇即可。對參數(shù)p則可有可無，因為輸出結(jié)果本身就是將數(shù)據(jù)對象按OF值的逆序排列結(jié)果，參數(shù)p則只是用來控制顯示的數(shù)量。因此，該方法對用戶設(shè)定參數(shù)的要求比較低。

從輸出方面看，該方法能夠給出傳統(tǒng)的基于距離的離群數(shù)據(jù)挖掘方法所不能給出的離群因子指標，同時還能給出其相應的離群屬性空間中的各特征屬性的離群因子，使用戶可以較清晰地了解各個數(shù)據(jù)對象的離群程度，以及它們?yōu)楹坞x群、是由于哪幾個特征屬性造成的離群，故該方法的輸出結(jié)果較為直觀、易于理解。

3.3.3 應用分析

針對Web客戶信息的數(shù)據(jù)量大、維數(shù)高的特點，我們設(shè)計的該挖掘分析方法的重點在于，能夠在保持一定的算法穩(wěn)定性的前提下提高算法的運行速度和執(zhí)行效率，省去不必要的步驟，以適應處理大量的、高維的數(shù)據(jù)的要求。同時盡可能地簡化操作，方便用戶使用。

在對特征屬性的挖掘方面，目前的研究思路主要是通過先對離群數(shù)據(jù)進行分析，再對離群對象的特征屬性進行挖掘的兩步方法，因而應用過程中需要對數(shù)據(jù)集進行反復搜索，這并不能適應處理大量的、高維的數(shù)據(jù)的要求。而本文所述方法的優(yōu)點即在于能夠?qū)㈦x群數(shù)據(jù)分析及其特征屬性挖掘作為一個整體進行處理，從而大大提高離群特征屬性的發(fā)現(xiàn)效率，避免對數(shù)據(jù)集進行大規(guī)模的重復遍歷，這是我們對離群特征屬性挖掘研究做的新的探索。

另外，若在允許等量的消耗存儲空間的條件下，將原始數(shù)據(jù)進行了轉(zhuǎn)化并存儲，這將有利于簡化對新增數(shù)據(jù)對象的分析處理工作，因而有較高的可擴展性能。

表1 離群數(shù)據(jù)及其知識集挖掘結(jié)果(m=1，Dim={G,A,…,S}，p=0.5%)

表2 離群數(shù)據(jù)及其知識集挖掘結(jié)果(m=2，Dim={G,A,…,S}，p=0.5%)

4 實驗分析

4.1 準確度比較

為了模擬Web客戶信息及其屬性值，同時反映該方法相對于傳統(tǒng)離群數(shù)據(jù)分析方法的不同特性和效果，這里使用文獻[11]中所使用的NHL數(shù)據(jù)集進行對比研究，該數(shù)據(jù)集曾多次被用于進行離群數(shù)據(jù)分析研究。該數(shù)據(jù)集為NHL(National Hockey League)在1995～1996年度職業(yè)球員的比賽統(tǒng)計信息，樣本量為991，維度為10，屬性名稱分別為Goals，Assists，Points，Plus/Minus，Penalties in Minutes，Even Strength Goals，Power Play Goals，Short-Handed Goals，Game-Winning Goals，Shots。實驗環(huán)境為Matlab7.10，設(shè)定參數(shù)為m=1，Dim為所有10個維度，p=0.5%，結(jié)果見表1。

在給出的前5個離群數(shù)據(jù)對象中，結(jié)合綜合離群因子和一維屬性離群因子可以看出，前三個數(shù)據(jù)對象是顯著離群，其離群特征屬性分別為OFA(Mario Lemieux)={PP,S H}，OFA(Jaromir Jagr)={G,GW}，OFA(Sergei Fedorov)={+-,GW}。與文獻[11]中的結(jié)果進行比較，兩者均檢測到Mario Lemieux和Jaromir Jagr兩個離群數(shù)據(jù)對象，特征屬性檢測結(jié)果也較相近，由于兩者數(shù)據(jù)源有所差異且選取的維度不同，因而對檢測結(jié)果有一定影響?？傮w來看，該方法能夠達到傳統(tǒng)方法所能獲得的準確度。

4.2 穩(wěn)定性測試

為測試檢測結(jié)果的穩(wěn)定性，調(diào)整參數(shù)m=2，結(jié)果見表2。

實驗結(jié)果表明，當參數(shù)m由1改為2時，所得到的三個顯著離群數(shù)據(jù)對象的結(jié)果不變且其離群因子值沒有發(fā)生大的變化，這說明本算法對顯著離群的數(shù)據(jù)對象的檢測效果比較穩(wěn)定。

5 結(jié)論

本文所設(shè)計的離群數(shù)據(jù)分析方法的時間復雜度為O(d?n?log2n)，空間復雜度為O(d?n)，且檢測結(jié)果比較準確、穩(wěn)定，算法效率較傳統(tǒng)方法有大幅度提高，有利于應用于對大量的、高維的Web客戶信息的處理工作。該方法能夠一次性完成對離群數(shù)據(jù)的分析和對其相應特征屬性的挖掘過程，這對離群數(shù)據(jù)的特征屬性挖掘方法是一項有益的探索。該方法對用戶的使用要求較低，參數(shù)設(shè)置簡便，且參數(shù)的小幅改變不會對檢測結(jié)果造成嚴重影響。通過離群因子OF值來表示離群程度，簡單而易于理解。另外還具有一定的可擴展性，其中間過程數(shù)據(jù)有重復利用的價值。因此，本文所設(shè)計的方法為客戶信息管理中的離群數(shù)據(jù)分析工作提供了新的思路和方法。

[1]Barnett VLT.Outliers in Statistical Data[M].New York:John Wiley&Sons,1994.

[2]Breunig MM,Kriegel HP,Ng RT,et al.OPTICS-OF:Identifying Lo?cal Outliers[C].In Proceedings of the 3rd European Conference on Principles and Practice of Knowledge Discovery in Databases,Prague,1999.

[3]熊君麗.高維空間下基于密度的離群點探測算法實現(xiàn)[J].現(xiàn)代電子技術(shù),2006,(15).

[4]崔貫勛,朱慶生.一種改進的基于密度的離群數(shù)據(jù)挖掘算法[J].計算機應用,2007,27(3).

[5]Breunig MM,Kriegel HP,Ng RT,et al.LOF:Identifying Densi?ty-Based Local Outliers[C].In Proceedings of ACM SIGMO 2000 In?ternational Conferenceon Management of Data,Dalles,TX,2000.

[6]Struyf A,Rousseeuw PJ.High-dimensional Computation of the Deep?est Location[J].Computational Statisticsand Data Analysis,2000,3.

[7]鄭建國,焦李成.偏差檢測挖掘方法研究[J].計算機工程,2001(8).

[8]黃洪宇,林甲祥.離群數(shù)據(jù)挖掘綜述[J].計算機應用研究,2006,(8).

[9]Knorr EM,NgRT.Finding Intentional Knowledge of Distance-Based Outliers[C].In Proceedings of the 25th VLDBConference,Edinburgh,Scotland,1999.

[10]Sephen DB,Mark S.Mining Distance-based Outliers in Near Linear Time with Randomization and a Simple Pruning Rule[C].In Proceed?ings of the Ninth ACM SIGKDD International Conference on Knowl?edge Discovery and Data Mining,Washington DC,USA,2003.

[11]Anguylli F,Pizzuti C.Fast Outlier Detection in High Dimensional Spaces[C].In Proceedings of the Sixth European Conference on the Principles of Data Miningand Knowledge Discovery,2002.

[12]Chen Z,Tang J,Fu AW.Modeling and Efficient Mining of Intention?al Knowledgeof Outliers[C].Hong Kong:2003.

[13]Jyrki K,Tomi P,Jukka T.Practical In-Place Mergesort[J].Nordic Journal of Computing,1996,(3).