基于相關(guān)子空間的多源離群檢測(cè)算法

馬 洋，趙旭俊

太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原030024

離群點(diǎn)檢測(cè)作為數(shù)據(jù)挖掘的研究方向之一，其目的是在海量數(shù)據(jù)中識(shí)別稀少、罕見(jiàn)的有價(jià)值的知識(shí)或?qū)ο?，已廣泛應(yīng)用在信用卡欺詐檢測(cè)、網(wǎng)絡(luò)魯棒性分析、入侵檢測(cè)、醫(yī)療及疾病預(yù)測(cè)等領(lǐng)域[1]。隨著科技及數(shù)據(jù)采集手段的高速發(fā)展，數(shù)據(jù)得到爆炸式的增長(zhǎng)，針對(duì)同一個(gè)任務(wù)，往往產(chǎn)生既有聯(lián)系又相互獨(dú)立的多個(gè)數(shù)據(jù)集。當(dāng)數(shù)據(jù)駐留在多個(gè)數(shù)據(jù)集中時(shí)，大多數(shù)現(xiàn)有算法的性能會(huì)嚴(yán)重下降，其原因是多數(shù)研究者采用數(shù)據(jù)融合的技術(shù)，將多個(gè)數(shù)據(jù)源獲取的數(shù)據(jù)合并為一個(gè)超大數(shù)據(jù)集，相關(guān)離群檢測(cè)算法運(yùn)行在合并后的單個(gè)超大數(shù)據(jù)集上。這不僅導(dǎo)致算法的檢測(cè)效率低下，而且忽略了多源數(shù)據(jù)之間的關(guān)聯(lián)知識(shí)和單數(shù)據(jù)源中的關(guān)鍵信息。

大數(shù)據(jù)的出現(xiàn)促進(jìn)數(shù)據(jù)源和數(shù)據(jù)量的快速增長(zhǎng)，數(shù)據(jù)融合是從多源數(shù)據(jù)集中進(jìn)行數(shù)據(jù)挖掘的一種主流技術(shù)。但是，數(shù)據(jù)融合在檢測(cè)多源離群點(diǎn)方面存在不足，其原因有兩個(gè)方面：首先，通過(guò)數(shù)據(jù)融合集成的數(shù)據(jù)集可能會(huì)丟失原始單個(gè)數(shù)據(jù)集的關(guān)鍵特征；其次，在現(xiàn)代分布式數(shù)據(jù)庫(kù)和存儲(chǔ)系統(tǒng)中，大多數(shù)大數(shù)據(jù)集（例如，大表）是跨多個(gè)服務(wù)器或站點(diǎn)實(shí)現(xiàn)的。利用多個(gè)大數(shù)據(jù)集的數(shù)據(jù)融合來(lái)構(gòu)建一個(gè)龐大的數(shù)據(jù)集是不現(xiàn)實(shí)的，也是不必要的。

另外，傳統(tǒng)的數(shù)據(jù)融合難以解決多源離群點(diǎn)檢測(cè)問(wèn)題。下面通過(guò)一個(gè)具體的實(shí)例進(jìn)行說(shuō)明。在此實(shí)例中，多源離群檢測(cè)將應(yīng)用于人口普查場(chǎng)景。假定R和S分別是源于A鎮(zhèn)的2010年和2015年的人口普查數(shù)據(jù)集。從2010年人口普查數(shù)據(jù)（即R）中，觀察到A鎮(zhèn)的留守兒童屬于離群群體。相反，A鎮(zhèn)的留守兒童在2015年人口普查數(shù)據(jù)集（即S）中被檢測(cè)為正常數(shù)據(jù)。這個(gè)結(jié)果表明，2010年至2015年期間，A鎮(zhèn)外出務(wù)工人員數(shù)量顯著增加，導(dǎo)致留守兒童成為A鎮(zhèn)的一個(gè)重要社會(huì)問(wèn)題。如果使用數(shù)據(jù)融合技術(shù)將2010年和2015年人口普查數(shù)據(jù)集（即R和S）合并為單個(gè)數(shù)據(jù)集，那么合并后的數(shù)據(jù)集將丟失R和S集本身的關(guān)鍵和關(guān)聯(lián)信息，這些信息對(duì)多源離群點(diǎn)檢測(cè)產(chǎn)生重大影響。因此，數(shù)據(jù)融合技術(shù)無(wú)法解決本例中的多源離群點(diǎn)檢測(cè)問(wèn)題。

另一個(gè)實(shí)例是通過(guò)澳大利亞稅務(wù)局的實(shí)際案例來(lái)分析如何利用來(lái)自不同數(shù)據(jù)源的離群檢測(cè)來(lái)獲得單個(gè)數(shù)據(jù)源無(wú)法得到的深層次信息。澳大利亞稅務(wù)局（ATO）為打擊偷稅、漏稅，檢測(cè)稅務(wù)欺詐，從多個(gè)互不相關(guān)的數(shù)據(jù)源中執(zhí)行離群數(shù)據(jù)檢測(cè)，其中數(shù)據(jù)源包括社交媒體帖子、私立學(xué)校記錄和移民數(shù)據(jù)等等。從不同的數(shù)據(jù)源檢測(cè)離群，提供了強(qiáng)大的深層次離群知識(shí)，成功協(xié)助澳大利亞稅務(wù)局在2016年破解、打擊近100億美元的欺詐行為。例如，在一個(gè)普通的澳大利亞家庭里，丈夫上報(bào)每年80 000美元的應(yīng)稅收入，他的妻子每年收入60 000美元，基于此，他們處于第二最低納稅范圍內(nèi)。但是從不同數(shù)據(jù)源收集的信息顯示，該家庭三個(gè)孩子都在私立學(xué)校，估計(jì)每年花費(fèi)75 000美元；而移民記錄和社交媒體的數(shù)據(jù)顯示，該家庭最近進(jìn)行了五次商務(wù)艙航班并在加拿大惠斯勒滑雪勝地度假，這都需要花費(fèi)大量金錢(qián)，屬于高消費(fèi)范疇。這些現(xiàn)象意味著他們上報(bào)的收入與他們的生活方式不符，完全有可能存在其他收入的情形。這促使澳大利亞稅務(wù)局對(duì)該家庭展開(kāi)深入調(diào)查，從多方面審查他們是否有未繳稅款的行為。

從上面一系列例子可以得出，設(shè)計(jì)開(kāi)發(fā)基于多數(shù)據(jù)源的離群數(shù)據(jù)檢測(cè)算法，能發(fā)現(xiàn)更深層次的信息和知識(shí)，這對(duì)正確決策至關(guān)重要。

總之，傳統(tǒng)的離群數(shù)據(jù)檢測(cè)方法無(wú)法適應(yīng)新的時(shí)代需求，迫切需要研究一種新的算子，實(shí)現(xiàn)多源數(shù)據(jù)上的離群檢測(cè)。此外，在海量的大數(shù)據(jù)中，不可避免地混雜著許多噪聲數(shù)據(jù)，這些噪聲隱匿在真正的離群數(shù)據(jù)中，雖能被離群算法所檢測(cè)，但無(wú)法將其與真實(shí)離群相分離，影響了離群數(shù)據(jù)的可理解性及應(yīng)用價(jià)值。與此同時(shí)，一些正常數(shù)據(jù)有時(shí)也被誤判為離群，出現(xiàn)在離群結(jié)果中，擴(kuò)大了離群數(shù)據(jù)的數(shù)量，也增加了領(lǐng)域?qū)＜冶嬲J(rèn)、理解真實(shí)離群的難度。為了滿足這一應(yīng)用需求，本文提出了一種新的離群點(diǎn)檢測(cè)算法RSMOD，它從多個(gè)相互依賴(lài)的數(shù)據(jù)源的聯(lián)合中發(fā)現(xiàn)離群點(diǎn)，這些數(shù)據(jù)源具有相互影響的關(guān)系。與傳統(tǒng)的離群點(diǎn)檢測(cè)算法不同，RSMOD驗(yàn)證了從一個(gè)數(shù)據(jù)集R中檢測(cè)到的離群點(diǎn)在另一個(gè)數(shù)據(jù)集S中的行為，證明了RSMOD是一種有效的檢測(cè)多源離群知識(shí)的方法，有助于將離群知識(shí)推廣到更多應(yīng)用領(lǐng)域。

1 相關(guān)工作

1.1 離群檢測(cè)

目前離群檢測(cè)技術(shù)大致可分為基于距離度量算法、基于密度度量算法、基于統(tǒng)計(jì)度量算法、基于近鄰度量和基于聚類(lèi)度量等方法[2-3]。典型研究有：楊曉玲等人[4]針對(duì)分布復(fù)雜的數(shù)據(jù)集提出基于逆向近鄰樹(shù)的異常挖掘算法，可有效檢測(cè)多類(lèi)型離群數(shù)據(jù)；任家東等人[5]將基于k近鄰離群檢測(cè)算法融合在網(wǎng)絡(luò)入侵檢測(cè)模型中，將離群檢測(cè)結(jié)果結(jié)合網(wǎng)絡(luò)流量的具體特征，刪除無(wú)效的異常行為，提高入侵檢測(cè)的性能；丁小歐等人[6]采用數(shù)據(jù)相關(guān)性分析的方法，針對(duì)時(shí)間序列數(shù)據(jù)進(jìn)行離群數(shù)據(jù)挖掘；劉芳等人[7]在經(jīng)典的LOF離群檢測(cè)算法基礎(chǔ)上，結(jié)合索引結(jié)構(gòu)和上界模型，提出了面向離群檢測(cè)的剪枝策略及相應(yīng)的離群數(shù)據(jù)挖掘算法，提高了LOF算法的效率；Radovanovi?等人[8]在k近鄰離群檢測(cè)基礎(chǔ)上，融合了反向近鄰的思想，通過(guò)檢測(cè)出現(xiàn)在近鄰集中的頻率來(lái)度量離群，但該方法只適用于無(wú)監(jiān)督的學(xué)習(xí)，不能擴(kuò)展到有監(jiān)督和半監(jiān)督的場(chǎng)景中。

1.2 多源及多視圖離群檢測(cè)

Wang等人[9]綜述了多源數(shù)據(jù)中的數(shù)據(jù)挖掘方法及應(yīng)用，主要研究包括：多源中的數(shù)據(jù)預(yù)處理[10]、多數(shù)據(jù)源的關(guān)聯(lián)規(guī)則挖掘[11]、多數(shù)據(jù)源的聚類(lèi)算法[12]和分類(lèi)算法研究[13]等相關(guān)內(nèi)容。但是，多源數(shù)據(jù)中的離群點(diǎn)檢測(cè)還處于起步階段，相關(guān)研究較少。Gao等人[14]利用多個(gè)數(shù)據(jù)源的數(shù)據(jù)樣本間水平關(guān)系的不一致性來(lái)挖掘離群點(diǎn)，其方法區(qū)別于傳統(tǒng)的數(shù)據(jù)樣本間垂直關(guān)系的劃分，本質(zhì)上依舊是單源數(shù)據(jù)，屬于多視圖角度進(jìn)行離群檢測(cè)。大多數(shù)多視圖離群檢測(cè)技術(shù)可分為兩大類(lèi)，即面向?qū)傩缘亩嘁晥D離群點(diǎn)和面向類(lèi)的多視圖離群點(diǎn)。前者是指在每個(gè)視圖中具有一致異常行為的異常值，而后者是指在不同視圖中不一致的異常值。Wang等人[15]提出了一種基于模糊聚類(lèi)的分布式多視圖異常檢測(cè)方法，該方法同時(shí)學(xué)習(xí)每個(gè)視圖的隸屬度矩陣，然后檢測(cè)各方的異常值；Li等人[16]針對(duì)多視圖數(shù)據(jù)源，利用交叉視圖低階編碼來(lái)揭示數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，并提出了一個(gè)多視圖低秩分析（MLRA）框架，用于離群數(shù)據(jù)檢測(cè)；Sheng等人[17]提出了基于最近鄰的多視圖異常檢測(cè)方法MUVAD，在MUVAD研究中，引入了一個(gè)異常度量準(zhǔn)則，以明確地估計(jì)正常實(shí)例集。

1.3 基于相關(guān)子空間的離群檢測(cè)

對(duì)于高維數(shù)據(jù)集，使用傳統(tǒng)的離群檢測(cè)方法[18-19]都會(huì)受到維度的影響，因此采用相關(guān)子空間的方法進(jìn)行離群檢測(cè)。相關(guān)子空間是針對(duì)異常數(shù)據(jù)尋找與其相關(guān)的屬性維，這些屬性維進(jìn)一步組成相關(guān)子空間，并在其基礎(chǔ)上進(jìn)行離群檢測(cè)。目前有很多尋找相關(guān)子空間的方法，例如，Kriegel等人[20]較早提出相關(guān)子空間的概念，主要采用主成分分析來(lái)檢索同離群數(shù)據(jù)密切相關(guān)的屬性。Muller等人[21]利用統(tǒng)計(jì)方法來(lái)檢驗(yàn)屬性維是否同離群數(shù)據(jù)檢測(cè)存在相關(guān)性，進(jìn)而遞歸查找非均勻分布的相關(guān)子空間，但很明顯，該方法存在時(shí)間復(fù)雜度高，可擴(kuò)展性差的問(wèn)題。Bao等人[22]提出了一種兩階段離群檢測(cè)模型。第一個(gè)階段是測(cè)量子空間中鄰居的密度，以發(fā)現(xiàn)低維離群值，第二階段評(píng)估連通子空間中鄰居的偏離度。最后對(duì)兩個(gè)階段的結(jié)果進(jìn)行統(tǒng)計(jì)分析，合并為最終離群分?jǐn)?shù)。Zhang等人[23-24]利用局部稀疏差異因子對(duì)每個(gè)維度上的稀疏因子進(jìn)行區(qū)分，為相關(guān)子空間的確定提供理論依據(jù)，同時(shí)也提高了算法效率，但當(dāng)維度的數(shù)據(jù)分布差異較大時(shí)，對(duì)于相關(guān)子空間的衡量就會(huì)出現(xiàn)誤差。

綜上所述，這些方法的一個(gè)共同特征是建立在單數(shù)據(jù)源或數(shù)據(jù)融合后的單數(shù)據(jù)源基礎(chǔ)上，無(wú)法檢測(cè)多源數(shù)據(jù)的異常知識(shí)，忽略了多源數(shù)據(jù)之間的關(guān)聯(lián)知識(shí)和單數(shù)據(jù)源中的關(guān)鍵信息。如果能從多源角度檢測(cè)離群，離群點(diǎn)可能會(huì)更準(zhǔn)確且具有更大的價(jià)值和意義。

2 多源數(shù)據(jù)中的離群度量

離群是少量的具有異常行為的數(shù)據(jù)對(duì)象，這些對(duì)象經(jīng)過(guò)某種度量與其他數(shù)據(jù)對(duì)象產(chǎn)生了明顯差異。然而，從單數(shù)據(jù)源中檢測(cè)的離群可能包含了噪聲以及被誤判的正常數(shù)據(jù)，這些在離群結(jié)果中的非離群數(shù)據(jù)，不能準(zhǔn)確反映數(shù)據(jù)對(duì)象之間的偏差特征，影響了離群的準(zhǔn)確性，甚至?xí)?dǎo)致用戶做出錯(cuò)誤的決策。如果能從多個(gè)數(shù)據(jù)源實(shí)現(xiàn)離群數(shù)據(jù)檢測(cè)，則可實(shí)現(xiàn)離群數(shù)據(jù)的交叉認(rèn)證，為用戶提供更有價(jià)值的離群結(jié)果。顯然，單源數(shù)據(jù)中的離群判別依據(jù)不能直接用于多源數(shù)據(jù)中，需對(duì)面向多源數(shù)據(jù)的離群度量重新定義。

2.1 多源數(shù)據(jù)中的對(duì)象影響空間

定義1（多源數(shù)據(jù)中的對(duì)象k最近鄰集）在d維空間上，給定兩個(gè)數(shù)據(jù)集R和S，其中r和s分別是R、S中的任一對(duì)象，即r∈R和s∈S，兩個(gè)對(duì)象r和s之間的相似性通過(guò)歐式距離d(r,s)來(lái)計(jì)算。數(shù)據(jù)集R中對(duì)象r的k最近鄰集，是從數(shù)據(jù)集S中檢索對(duì)象r的k個(gè)最近鄰居，被定義為knn(r,S)，將返回包含k個(gè)最近鄰居的集合。其形式化定義如下：

其中，Dk(r)被定義為一個(gè)距離，即對(duì)象r到它的第k個(gè)最近鄰之間的距離。

定義2（多源數(shù)據(jù)中的對(duì)象反向近鄰集）給定兩個(gè)數(shù)據(jù)集R、S和對(duì)象r，且r∈R，knn(s,R)是多源數(shù)據(jù)中對(duì)象s在R中的k最近鄰集，對(duì)象r的反向近鄰集被定義為kRnn(r,S)，是數(shù)據(jù)集S中對(duì)象的k最近鄰集中含有r的對(duì)象集合。其形式化定義如下：

定義3（多源數(shù)據(jù)中的對(duì)象影響空間）給定兩個(gè)數(shù)據(jù)集R和S，R中數(shù)據(jù)對(duì)象obj在數(shù)據(jù)集S中的影響空間為IS(obj,S)，是對(duì)象obj在S集中的k最近鄰集合和反向近鄰集的并集（見(jiàn)公式（3））。

多源數(shù)據(jù)中的對(duì)象影響空間，結(jié)合了對(duì)象在其他數(shù)據(jù)源中的k最近鄰集和反向近鄰集雙重的距離影響，更能準(zhǔn)確反映對(duì)象在其他數(shù)據(jù)源中的相似性和稠密性，消除了近鄰或反向近鄰單獨(dú)度量的局限性，有效減少誤報(bào)率。

定義4（屬性值的稀疏因子）給定兩個(gè)數(shù)據(jù)集R、S以及R中數(shù)據(jù)對(duì)象obj在數(shù)據(jù)集S中的影響空間IS(obj,S)，對(duì)象obj的屬性值稀疏因子可采用公式（4）進(jìn)行計(jì)算：

其中，p(xj,S)={ISj∪xj}，xj是對(duì)象obj的第j個(gè)屬性值，ISj表示obj影響空間中對(duì)象的第j個(gè)屬性值集合，Cj是p(xj,S)的平均值，|IS(obj,S)|是obj影響空間中對(duì)象數(shù)量。

稀疏因子是針對(duì)各對(duì)象的每個(gè)屬性進(jìn)行計(jì)算，在全部計(jì)算完后，數(shù)據(jù)集R中各對(duì)象的所有屬性對(duì)應(yīng)的全部稀疏因子可組成稀疏因子矩陣，可有效度量數(shù)據(jù)集的稀疏程度，其中采用p(λobj,j)來(lái)定義局部稀疏因子矩陣在屬性維Aj的對(duì)應(yīng)維取值集。設(shè)對(duì)象obj是數(shù)據(jù)集R中某一對(duì)象，用xj描述該對(duì)象的第j個(gè)屬性值，其對(duì)應(yīng)的稀疏差異因子用dobj,j表示，用于描述該屬性值在本屬性上的差異特性，形式化描述為公式（5）：

其中，Cλij是維取值集p(λobj,j)的平均值。

根據(jù)R集中各數(shù)據(jù)對(duì)象在S集的影響空間，并依據(jù)屬性值的稀疏因子（見(jiàn)公式（4）），生成面向數(shù)據(jù)集S的稀疏因子矩陣，從而有效地刻畫(huà)了數(shù)據(jù)對(duì)象在S中的局部稀疏程度；根據(jù)稀疏因子矩陣，計(jì)算屬性維對(duì)應(yīng)的稀疏差異因子（見(jiàn)公式（5）），并確定數(shù)據(jù)對(duì)象在S集中對(duì)應(yīng)的相關(guān)子空間定義向量，從而有效地體現(xiàn)了相關(guān)子空間的任意性。

2.2 實(shí)例分析

為了加深上節(jié)定義的理解，通過(guò)一個(gè)具體的實(shí)例進(jìn)行分析。給定兩個(gè)數(shù)據(jù)集R和S，包含3個(gè)屬性，為了簡(jiǎn)化運(yùn)算，屬性值采用整型，詳細(xì)信息見(jiàn)表1和表2。在下面的計(jì)算中，兩對(duì)象的相似性采用歐式距離來(lái)度量，最近鄰個(gè)數(shù)k被設(shè)定為2。

表1 實(shí)例數(shù)據(jù)集RTable 1 Example dataset R

表2 實(shí)例數(shù)據(jù)集STable 2 Example dataset S

步驟1多源數(shù)據(jù)中的對(duì)象k最近鄰集計(jì)算。首先，通過(guò)歐式距離公式計(jì)算R集中任一對(duì)象同S集中對(duì)象的距離，以對(duì)象r1和s1為例，計(jì)算如下：

同樣地，可以求得對(duì)象r1和S集中其他對(duì)象的距離，分別為d(r1,s2)≈8.06；d(r1,s3)≈64.31；d(r1,s4)≈25.10；d(r1,s5)≈13.42；d(r1,s6)≈14.50；d(r1,s7)≈13.42。從這些距離中，查找兩個(gè)最小的值，即6.48和8.06，其對(duì)應(yīng)的對(duì)象為s1和s2，因此，r1在S集中的k最近鄰集為knn(r1,S)={s1,s2}。

數(shù)據(jù)集R中對(duì)象r1的k最近鄰集，是從數(shù)據(jù)集S中檢索對(duì)象r1的k個(gè)最近鄰居，將返回包含k個(gè)最近鄰居的集合，其中，對(duì)象之間的相似性采用歐式距離進(jìn)行度量。

步驟2多源數(shù)據(jù)中的對(duì)象反向近鄰集計(jì)算。按照步驟1的計(jì)算過(guò)程，反過(guò)來(lái)計(jì)算S集中對(duì)象在R集中的k最近鄰集，結(jié)果為knn(s1,R)={r1,r3}；knn(s2,R)={r2,r5}；knn(s3,R)={r2,r4}；knn(s4,R)={r1,r5}；knn(s5,R)={r1,r3}；knn(s6,R)={r1,r5}；knn(s7,R)={r1,r5}。在這些集合中，包含對(duì)象r1的是knn(s1,R)；knn(s4,R)；knn(s5,R)；knn(s6,R)；knn(s7,R)。因此，r1在數(shù)據(jù)集S中的反向近鄰集為kRnn(r1,S)={s1,s4,s5,s6,s7}。

對(duì)象r1的反向近鄰集是數(shù)據(jù)集S中對(duì)象在R的k最近鄰集中含有r1的對(duì)象集合，因此，需要計(jì)算S中所有對(duì)象在R集中的k最近鄰集，并找出包含r1的所有對(duì)象。

步驟3求解多源數(shù)據(jù)中的對(duì)象影響空間。依據(jù)定義3，對(duì)象r1的影響空間為r1的k最近鄰集和反向近鄰集的并集，因此IS(r1,S)={s1,s2,s4,s5,s6,s7}。

多源數(shù)據(jù)中的對(duì)象影響空間，是在多源數(shù)據(jù)中估計(jì)目標(biāo)的鄰域密度分布時(shí)，同時(shí)考慮了目標(biāo)鄰域和反向鄰域的對(duì)稱(chēng)影響。在前面兩步的基礎(chǔ)上，找到了r1的k最近鄰集和反向近鄰集，這一步，只需完成兩個(gè)集合的并集，就可得到對(duì)象r1的影響空間。另外，近鄰組成的鄰域與反向近鄰組成的反向鄰域之間的這種對(duì)稱(chēng)關(guān)系將使多源數(shù)據(jù)的離群度量具有更強(qiáng)的魯棒性和語(yǔ)義正確性。

步驟4求解屬性值的稀疏因子，以對(duì)象r1的A1屬性為例進(jìn)行求解。根據(jù)公式（4），首先求解p(xj,S)，它是對(duì)象r1及其影響空間中所有對(duì)象第一個(gè)屬性（即A1）的值組成的集合，結(jié)合步驟3以及R和S兩個(gè)數(shù)據(jù)集，可以算出p(x1,S)={5 2,53,57,51,56,47,46}。其次，計(jì)算Cj，它是p(xj,S)的平均值，因此C1=(52+53+57+51+56+47+46)/7≈51.71。另外，|IS(obj,S)|是obj影響空間中對(duì)象數(shù)量，在本例中，其值為6。最后，根據(jù)公式（4），可求得r1的屬性A1稀疏因子為λr1,1=（（52?51.71）2+（53?51.71）2+（57?51.71）2+（51?51.71）2+（56?51.71）2+（47?51.71）2+（46?51.71）2）/7≈14.78。

稀疏因子是針對(duì)各對(duì)象的每個(gè)屬性進(jìn)行計(jì)算，表明該對(duì)象的屬性值在該屬性上的稀疏程度，利用公式（4）完成。主要包括p(xj,S)和Cj的計(jì)算，其中p(xj,S)是對(duì)象obj的第j個(gè)屬性值和對(duì)象obj影響空間中所有對(duì)象的第j個(gè)屬性值的集合；Cj是p(xj,S)的平均值。

步驟5求解稀疏差異因子dij，本例中計(jì)算對(duì)象r1的A1屬性稀疏差異因子。首先，利用步驟4的計(jì)算過(guò)程，可以得到R集中其他對(duì)象的關(guān)于屬性A1稀疏因子，分別為λr2,1=55.25；λr3,1=2.89；λr4,1=39.69；λr5,1=17.22。然后，求得這些稀疏因子的均值為25.37。根據(jù)公式（5），對(duì)象r1的A1屬性稀疏差異因子為dr1,1=

R集中各對(duì)象對(duì)應(yīng)屬性的稀疏因子全部計(jì)算完后，可求得這些稀疏因子的均值，然后利用公式（5），很容易得到對(duì)象r1的A1屬性稀疏差異因子，用于描述該屬性值在本屬性上的差異特性。其計(jì)算結(jié)果可以確定數(shù)據(jù)對(duì)象在S集中對(duì)應(yīng)的相關(guān)子空間定義向量，從而有效地體現(xiàn)了相關(guān)子空間的任意性，為下一節(jié)的多源數(shù)據(jù)中相關(guān)子空間度量提供研究基礎(chǔ)。

2.3 多源數(shù)據(jù)中相關(guān)子空間的度量

文獻(xiàn)[21]已充分論述了單數(shù)據(jù)源中的相關(guān)子空間，指出相關(guān)子空間是非均勻分布的子空間，能有效地體現(xiàn)出“離群數(shù)據(jù)”的有價(jià)值信息?，F(xiàn)結(jié)合稀疏因子矩陣，對(duì)多源相關(guān)子空間進(jìn)行度量，給定一個(gè)稀疏差異因子閾值ε，數(shù)據(jù)集R中任一對(duì)象及其對(duì)應(yīng)的稀疏差異因子dij，如果dij<ε，說(shuō)明該對(duì)象對(duì)應(yīng)的屬性值同周?chē)溆帱c(diǎn)相比具有較小的差異性，該點(diǎn)處于稠密區(qū)域，反之，如果dij≥ε，說(shuō)明該對(duì)象的屬性值同周?chē)溆帱c(diǎn)相比具有很大的差異性，該點(diǎn)處于一個(gè)稀疏區(qū)域。在本文采用Zij表示數(shù)據(jù)對(duì)象在特定屬性維上的稀疏密度值，當(dāng)Zij被設(shè)置為0，即Zij=0，表示數(shù)據(jù)對(duì)象obj在第j個(gè)屬性上位于一個(gè)稠密區(qū)域，Zij對(duì)應(yīng)的屬性所構(gòu)建的子空間是數(shù)據(jù)對(duì)象obj相對(duì)于S的不相關(guān)子空間。反之，Zij=1表明數(shù)據(jù)對(duì)象obj在第j個(gè)屬性上位于一個(gè)稀疏區(qū)域，Zij對(duì)應(yīng)的屬性所構(gòu)建的子空間是數(shù)據(jù)對(duì)象obj相對(duì)于S的相關(guān)子空間。因此，如果dij<ε，那么Zij=0；否則，如果dij≥ε，那么Zij=1。

當(dāng)數(shù)據(jù)集R中數(shù)據(jù)對(duì)象，在某個(gè)維度上存在相對(duì)于S的相關(guān)子空間，為了判斷該對(duì)象的偏離程度，本文采用高斯誤差函數(shù)計(jì)算該數(shù)據(jù)對(duì)象的概率密度差異因子，并通過(guò)公式（6）來(lái)定義對(duì)象obj的離群系數(shù)：

多源數(shù)據(jù)中的離群檢測(cè)，需計(jì)算R中所有對(duì)象相對(duì)于其他數(shù)據(jù)集的相關(guān)子空間，并計(jì)算每個(gè)對(duì)象的離群系數(shù)，從所有離群系數(shù)中選取最大的若干數(shù)據(jù)對(duì)象作為多源離群數(shù)據(jù)。

3 多源離群數(shù)據(jù)檢測(cè)算法

基于相關(guān)子空間的多源離群檢測(cè)算法基本思想如下：第一步，采用公式（1）計(jì)算多源數(shù)據(jù)中每個(gè)對(duì)象的k近鄰集，并通過(guò)公式（2）計(jì)算相應(yīng)的反向近鄰集，然后利用公式（3）求出數(shù)據(jù)集R中對(duì)象在其他數(shù)據(jù)集對(duì)應(yīng)的影響空間；第二步，采用公式（4）計(jì)算數(shù)據(jù)集R中每個(gè)對(duì)象的稀疏因子，并通過(guò)公式（5）求出其對(duì)應(yīng)的稀疏差異因子，通過(guò)與預(yù)先設(shè)定的稀疏差異閾值進(jìn)行比較獲取相應(yīng)的稀疏密度值；第三步，分析對(duì)象的稀疏密度值，如果該對(duì)象存在相關(guān)子空間，則通過(guò)公式（6）計(jì)算該對(duì)象的離群系數(shù)；第四步，循環(huán)執(zhí)行第二、第三步，直到遍歷全部的相關(guān)子空間，得到所有的離群稀疏值，從這些值中選取最大的N個(gè)，并將其對(duì)應(yīng)的對(duì)象輸出，這些對(duì)象就是得到的多源離群數(shù)據(jù)。RSMOD算法思想描述如下。

算法RSMOD

輸入：R，S，k，N，ε；//R和S為兩個(gè)數(shù)據(jù)集，k是近鄰個(gè)數(shù)，N為離群數(shù)量，ε為稀疏差異因子閾值

輸出：Moutliers；//輸出多源離群數(shù)據(jù)對(duì)象

1.for（int i=0；i<|R|；i++）do//R中每個(gè)對(duì)象循環(huán)

2.for（int j=0；j<|S|；j++）do

3.Di←distance（i，j）；//計(jì)算兩個(gè)對(duì)象的距離

4.end for

5.knn（r，S）←從Di中選出r的k個(gè)最近鄰居

6.kRnn（r，S）={s|s屬于S，r屬于knn（s，R）}；

7.IS（r，S）=knn（r，S）∪kRnn（r，S）；

8.end for

9.for（int i=0；i<|R|；i++）do

10.for（int j=0；j

11.λij←利用公式（4）計(jì)算屬性值的稀疏因子

12.dij←利用公式（5）計(jì)算稀疏差異因子

13.if（dij≥ε）then//判斷相關(guān)子空間

14.Zij=1；

15.Routliers←Factor（obj）；//利用公式（6）計(jì)算obj的離群系數(shù)，保存到集合Routliers

16.else

17.Zij=0；

18.end if

19.end for

20.end for

21.Moutliers←從Routliers中選擇N個(gè)最大值；

22.output（Moutliers）；

在算法RSMOD中，數(shù)據(jù)集R中所有對(duì)象在S集中的k近鄰與反向近鄰的計(jì)算，其復(fù)雜度為O(|R|×|S|)，|R|和|S|分別是數(shù)據(jù)集R和S中包含的對(duì)象數(shù)；計(jì)算稀疏因子和稀疏差異因子的時(shí)間復(fù)雜度為O(|R|×d)，d為數(shù)據(jù)集R包含的屬性維個(gè)數(shù)；同樣地，對(duì)象在相關(guān)子空間中的離群系數(shù)的時(shí)間復(fù)雜度也是O(|R|×d)。因此，整個(gè)算法的時(shí)間復(fù)雜度為O(|R|×(|S|+2×d))。

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)涉及的軟硬件環(huán)境配置如下：Intel?Core?i5-4570 CPU，8 GB內(nèi)存，Windows 7操作系統(tǒng)，Java作為開(kāi)發(fā)工具實(shí)現(xiàn)RSMOD算法，實(shí)驗(yàn)數(shù)據(jù)包括人工合成數(shù)據(jù)和美國(guó)人口普查數(shù)據(jù)IPUMS。在實(shí)驗(yàn)分析中，沒(méi)有和其他離群數(shù)據(jù)檢測(cè)算法的相關(guān)比較，其原因是其他算法是面向單個(gè)數(shù)據(jù)集或者是融合為單個(gè)數(shù)據(jù)集的離群檢測(cè)，其離群檢測(cè)結(jié)果和本文提出的RSMOD算法檢測(cè)結(jié)果完全不同，沒(méi)有可比性。

4.1 參數(shù)ε影響算法性能

參數(shù)ε是用戶設(shè)定的稀疏差異因子閾值，其值的大小直接影響對(duì)象所處稀疏區(qū)域的判定，同時(shí)間接地影響了該對(duì)象能否構(gòu)成相關(guān)子空間。本組實(shí)驗(yàn)從參數(shù)ε影響算法效率和準(zhǔn)確性兩個(gè)角度進(jìn)行設(shè)計(jì)和分析，所涉及的兩組數(shù)據(jù)集，采用隨機(jī)數(shù)據(jù)生成器，合成兩組服從正態(tài)分布的數(shù)據(jù)集R和S，每個(gè)數(shù)據(jù)集包含200個(gè)屬性以及50 000個(gè)數(shù)據(jù)對(duì)象，然后分別在數(shù)據(jù)集R和S中，增加200個(gè)服從0~1的均勻分布數(shù)據(jù)對(duì)象，作為離群數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 參數(shù)ε對(duì)算法RSMOD性能的影響Fig.1 Impacts of parameter ε on RSMOD performance

從圖1（a）中可以看出，隨著參數(shù)ε的逐漸增大，算法的運(yùn)行時(shí)間顯著減少，這是因?yàn)橐粋€(gè)較大的稀疏差異因子閾值，增多了稠密區(qū)域數(shù)量的同時(shí)，減少了稀疏區(qū)域的數(shù)量（如果dij<ε，該點(diǎn)處于一個(gè)稠密區(qū)域；否則，如果dij≥ε，該點(diǎn)處于一個(gè)稀疏區(qū)域），相應(yīng)地減少了相關(guān)子空間的數(shù)量。結(jié)合圖1（b）的算法準(zhǔn)確性實(shí)驗(yàn)結(jié)果，隨著參數(shù)ε的逐漸增加，算法的準(zhǔn)確性顯著下降，這是因?yàn)樗惴ǖ臏?zhǔn)確性和相關(guān)子空間的數(shù)量密切相關(guān)，一個(gè)小的ε值導(dǎo)致較多的處于稀疏區(qū)域的數(shù)據(jù)點(diǎn)被誤判在稠密區(qū)域，直接影響了算法的準(zhǔn)確性能。從圖1（a）還可看出，在相同的參數(shù)ε值條件下，不同的離群數(shù)量N所耗費(fèi)的時(shí)間差異較小，說(shuō)明離群數(shù)量N對(duì)整個(gè)算法的效率影響很小，結(jié)合圖1（b）的算法準(zhǔn)確性實(shí)驗(yàn)結(jié)果，一個(gè)大的N值能帶來(lái)較高的準(zhǔn)確性，這是因?yàn)?，在效率上N值僅用于從有序的候選離群數(shù)據(jù)中篩選更多的離群，其耗費(fèi)時(shí)間非常少；而在準(zhǔn)確性方面，大的N值會(huì)導(dǎo)致更多的離群出現(xiàn)，會(huì)提高其準(zhǔn)確性。

稀疏差異因子閾值ε的大小會(huì)影響相關(guān)子空間的數(shù)量，也會(huì)影響算法的效率和離群檢測(cè)結(jié)果的準(zhǔn)確性，因此ε的取值需同應(yīng)用場(chǎng)景的需求相結(jié)合。在準(zhǔn)確性要求較高的應(yīng)用中，ε應(yīng)設(shè)定一個(gè)較小的值（例如，ε=0.06），這樣會(huì)用較長(zhǎng)的運(yùn)行時(shí)間作為代價(jià)，換取較高的準(zhǔn)確性。相反地，在效率方面有較高的需求時(shí)，ε應(yīng)設(shè)定一個(gè)較大的值（例如，ε=0.3），通過(guò)損失其部分準(zhǔn)確性，來(lái)獲得較快的運(yùn)行時(shí)間。一般情況下，ε建議設(shè)定為0.1，可以同時(shí)兼顧算法的效率和檢測(cè)結(jié)果的準(zhǔn)確性。

4.2 參數(shù)k影響算法性能

參數(shù)k是對(duì)象的最近鄰個(gè)數(shù)，可直接影響對(duì)象k最近鄰集和反向近鄰集的計(jì)算。本組實(shí)驗(yàn)延用4.1節(jié)描述的數(shù)據(jù)集，從參數(shù)k影響算法效率和準(zhǔn)確性兩個(gè)角度進(jìn)行設(shè)計(jì)和分析，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 參數(shù)k對(duì)算法RSMOD性能的影響Fig.2 Impacts of parameter k on RSMOD performance

從圖2（a）中可以看出，隨著k值的持續(xù)增加，算法的執(zhí)行時(shí)間呈線性增長(zhǎng)趨勢(shì)，其原因是k值的大小影響了每個(gè)對(duì)象計(jì)算k最近鄰和反向近鄰的時(shí)間，同時(shí)擴(kuò)大了近鄰集和反向近鄰集的大小，間接地增加了對(duì)象影響空間的計(jì)算時(shí)間，從而導(dǎo)致整個(gè)算法的執(zhí)行時(shí)間成倍加速。結(jié)合圖2（b）的準(zhǔn)確性實(shí)驗(yàn)結(jié)果，大的k值會(huì)提高算法的準(zhǔn)確性，這是因?yàn)楫?dāng)k值增加時(shí)，相應(yīng)對(duì)象影響空間的計(jì)算更加準(zhǔn)確，導(dǎo)致離群數(shù)據(jù)檢測(cè)的準(zhǔn)確性也明顯提高。

最近鄰個(gè)數(shù)k的取值顯著影響了算法的執(zhí)行時(shí)間，其取值按照文獻(xiàn)[3]的分析，一般不超過(guò)N，即k≤N，其中N為數(shù)據(jù)集中的對(duì)象數(shù)量。

4.3 多源vs單源離群檢測(cè)結(jié)果

在本組實(shí)驗(yàn)中，采用真實(shí)數(shù)據(jù)集展示多源離群檢測(cè)結(jié)果與單源離群（即傳統(tǒng)離群檢測(cè)）檢測(cè)結(jié)果之間的差異。實(shí)驗(yàn)采用兩個(gè)IPUMS美國(guó)人口普查數(shù)據(jù)（即，ipums.la.97和ipums.la.98數(shù)據(jù)集），這兩個(gè)數(shù)據(jù)集分別包含1997年和1998年洛杉磯和長(zhǎng)灘地區(qū)的未加權(quán)IPUMS人口普查數(shù)據(jù)。數(shù)據(jù)集ipums.la.97和ipums.la.98具有相同的屬性，將其分別標(biāo)記為R和S；將ipums.la.97和ipums.la.98數(shù)據(jù)集中的對(duì)象合并生成R∪S，可將其看作數(shù)據(jù)融合后的單個(gè)數(shù)據(jù)集。

采用本文提出的RSMOD算法對(duì)ipums.la.97和ipums.la.98數(shù)據(jù)集進(jìn)行多源離群檢測(cè)，得到175個(gè)離群檢測(cè)結(jié)果，部分結(jié)果如表3所示。例如，第一個(gè)多源異常值顯示，總收入低于705美元的人與母親住在一起，1997年的這一異?，F(xiàn)象在1998年成為正常數(shù)據(jù)。實(shí)驗(yàn)結(jié)果表明，1998年705美元不足以買(mǎi)房，因此她或他必須留在母親身邊。第四個(gè)多源異常值表明，總收入為14 615美元的家庭在1997年可以擁有自己的住房，但在1998年這種現(xiàn)象很少見(jiàn)。1998年美國(guó)房?jī)r(jià)大幅飆升，證明了這一結(jié)果的合理性。更重要的是，這些多源離群點(diǎn)不能通過(guò)現(xiàn)有的數(shù)據(jù)融合技術(shù)獲得，因?yàn)殡x群點(diǎn)作為正常數(shù)據(jù)隱藏在一個(gè)合并后的數(shù)據(jù)集中（即R∪S），無(wú)法實(shí)現(xiàn)多源數(shù)據(jù)之間的關(guān)聯(lián)知識(shí)檢測(cè)。

表3 多源數(shù)據(jù)離群檢測(cè)的實(shí)例結(jié)果Table 3 Example results of multi-source outlier detection

5 結(jié)束語(yǔ)

在實(shí)際應(yīng)用中，多源數(shù)據(jù)之間的離群關(guān)聯(lián)知識(shí)變得越來(lái)越重要，本文針對(duì)多源數(shù)據(jù)，提出一種基于相關(guān)子空間的多源離群檢測(cè)算法，結(jié)合k近鄰及反向近鄰的雙向影響，重新定義了面向多源數(shù)據(jù)的對(duì)象影響空間；并在此基礎(chǔ)上，提出了適用于多源數(shù)據(jù)的稀疏因子和稀疏差異因子，為對(duì)象在多源數(shù)據(jù)中的稠密性度量提供依據(jù)；還給出了面向多源數(shù)據(jù)的相關(guān)子空間確定方法以及相應(yīng)的離群檢測(cè)算法，有效地實(shí)現(xiàn)了多源數(shù)據(jù)中的離群識(shí)別。下一步工作將考慮屬性之間的相關(guān)性和算法的并行化，以便于算法更適用于海量高維數(shù)據(jù)集。