馬菲，朱昌杰*，鄭穎，鄧杰

(1.淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽淮北 235000;2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫 214122)

一種基于可變網(wǎng)格劃分的離群點(diǎn)檢測(cè)算法

馬菲1，朱昌杰*1，鄭穎1，鄧杰2

(1.淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽淮北 235000;2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫 214122)

LOF(Local Outlier Factor)算法是常用的離群點(diǎn)檢測(cè)算法，但是該算法在面對(duì)大規(guī)模數(shù)據(jù)集時(shí)往往需要高昂的時(shí)空開銷，基于固定網(wǎng)格的離群點(diǎn)檢測(cè)算法雖然在一定程度上可以解決該問(wèn)題，但是它的執(zhí)行效果易受到網(wǎng)格劃分粒度的影響。對(duì)此提出一種基于可變網(wǎng)格劃分的離群點(diǎn)檢測(cè)算法。該算法首先根據(jù)數(shù)據(jù)點(diǎn)在空間的實(shí)際分布情況來(lái)動(dòng)態(tài)構(gòu)建與原始數(shù)據(jù)集分布大體一致的網(wǎng)格空間，然后刪除網(wǎng)格中數(shù)據(jù)點(diǎn)數(shù)目超過(guò)設(shè)定閾值的網(wǎng)格中所有數(shù)據(jù)點(diǎn)，最后在剩余的數(shù)據(jù)點(diǎn)集上執(zhí)行LOF算法。實(shí)驗(yàn)結(jié)果顯示，相對(duì)于固定網(wǎng)格的離群點(diǎn)檢測(cè)算法，所提算法的執(zhí)行效率明顯提高并且檢測(cè)精確度亦有所提高。

局部離群因子;離群點(diǎn)檢測(cè);可變網(wǎng)格;大規(guī)模數(shù)據(jù)集

隨著越來(lái)越多的數(shù)據(jù)被收集并存儲(chǔ)到數(shù)據(jù)庫(kù)中，有效和高效地分析并挖掘包含在這些大規(guī)模數(shù)據(jù)集中的信息具有重要意義［1］。在大規(guī)模數(shù)據(jù)集包含的信息中，由于離群點(diǎn)常常包含潛在有用的信息，對(duì)其檢測(cè)越來(lái)越受到人們的重視。離群點(diǎn)一般被定義為數(shù)據(jù)集中與其他數(shù)據(jù)對(duì)象差異較大的那些數(shù)據(jù)對(duì)象。離群點(diǎn)檢測(cè)目的是發(fā)現(xiàn)數(shù)據(jù)集中的離群點(diǎn)并根據(jù)這些離群點(diǎn)推斷潛在的、有價(jià)值的知識(shí)。隨著大數(shù)據(jù)時(shí)代的到來(lái)，離群點(diǎn)檢測(cè)在實(shí)際生活中得到了廣泛的應(yīng)用，如在金融領(lǐng)域用來(lái)檢測(cè)信用卡的異常使用、在工業(yè)控制系統(tǒng)中對(duì)數(shù)據(jù)的預(yù)處理、網(wǎng)絡(luò)監(jiān)管系統(tǒng)中網(wǎng)絡(luò)異常識(shí)別、網(wǎng)絡(luò)健壯性分析、在醫(yī)療領(lǐng)域的公共健康分析、圖形圖像的處理等［2-4］。

LOF(Local Outlier Factor)算法于2000年被Breunig等［5］人提出，它是一個(gè)基于密度的算法。LOF算法通過(guò)計(jì)算數(shù)據(jù)點(diǎn)的局部離群因子來(lái)表征該數(shù)據(jù)點(diǎn)的偏離程度，使得對(duì)離群點(diǎn)的檢測(cè)不再是二元結(jié)果。LOF算法在進(jìn)行局部離群因子計(jì)算時(shí)，檢測(cè)精確度常常受到用戶給定參數(shù)的影響［6］。同時(shí)，在進(jìn)行大規(guī)模數(shù)據(jù)集中的離群點(diǎn)檢測(cè)時(shí)，該算法往往需要高昂的時(shí)空開銷。

為了解決這些問(wèn)題，薛安榮等人［7］提出一種改進(jìn)的局部離群點(diǎn)檢測(cè)算法。首先將對(duì)象屬性分為固有屬性和環(huán)境屬性，然后通過(guò)環(huán)境屬性確定鄰域?qū)ο?、固有屬性?jì)算離群因子的方法，有效地避免了參數(shù)的輸入，但是該算法對(duì)鄰域的確定仍然需要消耗大量的時(shí)間。Zhang Ke等人［8］提出一種新的計(jì)算局部離群因子算法，與LOF算法相比，該算法時(shí)間效率有所提高并且對(duì)參數(shù)的敏感度也有所降低。Rajendra Pamula等人［9］提出一種基于聚類的離群點(diǎn)檢測(cè)算法，該算法首先使用K-means方法進(jìn)行聚類，然后刪除離聚類中心較近的數(shù)據(jù)點(diǎn)，最后對(duì)剩余的數(shù)據(jù)點(diǎn)計(jì)算局部離群因子。由于該算法刪除了部分的數(shù)據(jù)點(diǎn)，算法的執(zhí)行效率相應(yīng)地得到提高，但是在聚類時(shí)使用K-means方法進(jìn)行聚類，導(dǎo)致算法對(duì)初始聚類中心較為敏感。文獻(xiàn)［10］中提出基于網(wǎng)格技術(shù)的高維大數(shù)據(jù)集離群點(diǎn)挖掘算法(Outlier Mining Algorithm based on Grid Techniques，OMAGT)，該算法將網(wǎng)格思想引入其中，把空間劃分為大小相同的網(wǎng)格單元，從而將對(duì)數(shù)據(jù)集中數(shù)據(jù)點(diǎn)處理轉(zhuǎn)化為對(duì)空間中有限網(wǎng)格單元的處理。通過(guò)這種方式能有效地提高算法的執(zhí)行效率，但是由于該算法使用的是固定網(wǎng)格劃分，所以易受網(wǎng)格劃分粒度的影響，并且它并沒(méi)有考慮數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的實(shí)際分布，這會(huì)導(dǎo)致計(jì)算結(jié)果有一定的偏差。

鑒于此，文中在LOF算法與OMAGT算法基礎(chǔ)上，提出一種基于可變網(wǎng)格劃分的離群點(diǎn)檢測(cè)算法(Outlier Detecting Algorithm based on Variab le Grid，ODAVG)。

ODAVG算法首先根據(jù)數(shù)據(jù)集在空間的實(shí)際分布情況，將每一維非等寬地劃分成數(shù)段，進(jìn)而在空間中形成大小不一的網(wǎng)格單元;然后統(tǒng)計(jì)每個(gè)網(wǎng)格單元中數(shù)據(jù)點(diǎn)的數(shù)目，刪除網(wǎng)格中數(shù)據(jù)點(diǎn)數(shù)目大于設(shè)定閾值網(wǎng)格中的所有數(shù)據(jù)點(diǎn);最后對(duì)剩余的數(shù)據(jù)點(diǎn)利用LOF算法進(jìn)行離群點(diǎn)檢測(cè)。在多個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，相對(duì)于OMAGT算法，ODAVG算法執(zhí)行效率明顯提高并且準(zhǔn)確率也有所提高。

1 LOF算法

1.1 LOF算法的基本概念

在離群點(diǎn)檢測(cè)領(lǐng)域，LOF算法常常被用來(lái)計(jì)算數(shù)據(jù)點(diǎn)的離群程度，它不再簡(jiǎn)單地判別數(shù)據(jù)點(diǎn)是不是離群點(diǎn)，而是給出數(shù)據(jù)點(diǎn)的離群程度，實(shí)際上反應(yīng)了該數(shù)據(jù)點(diǎn)是否偏離相對(duì)集中的區(qū)域。下面介紹LOF算法的一些基本概念。

定義1(對(duì)象p的k距離)

在數(shù)據(jù)集D中，對(duì)于任何一個(gè)正整數(shù)k，以k-distance(p)來(lái)表示對(duì)象p的k距離，以d(p，0)表示對(duì)象p到對(duì)象o(o∈D)的距離。滿足下面兩個(gè)條件，則k-distance(p)=d(p，o):

(1)至少有k個(gè)對(duì)象o'∈D{p}，它到p的距離d(p，o')≤d(p，o);

(2)至多有k－1個(gè)對(duì)象o'∈D{p}，它到p的距離d(p，o')＜d(p，o)。

定義2(對(duì)象p的k-distance鄰域)

已知對(duì)象p的k-distance(p)，p的k距離鄰域是指D中的對(duì)象q到p的距離不大于k-distance(p)的所有對(duì)象的集合，記為

定義3(對(duì)象p到對(duì)象o的可達(dá)距離)

設(shè)k是一個(gè)自然數(shù)，對(duì)象p到對(duì)象o的可達(dá)距離定義為

從可達(dá)距離定義可以看出，如果p遠(yuǎn)離o，則它們的可達(dá)距離等于兩者之間的實(shí)際距離;如果p‘足夠地’地接近o，則它們的可達(dá)距離等于o的k-distance(o)。

定義4(對(duì)象p的局部可達(dá)密度)

對(duì)象p的局部可達(dá)密度定義為

可以看出，p的局部可達(dá)密度是p的MinPts個(gè)最近鄰居的平均可達(dá)距離的倒數(shù)。

定義5(對(duì)象p的局部離群因子)對(duì)象p的局部離群因子定義為

已知，p的局部離群因子顯示p的離群程度。它等于p的MinPts個(gè)最近鄰居的局部可達(dá)密度的平均值與p的局部可達(dá)密度之比。根據(jù)公式可以很清楚地看到，p的局部可達(dá)密度越小且MinPts個(gè)最近鄰居的局部可達(dá)密度越大，則離群因子越大，也就是說(shuō)p越偏離MinPts個(gè)鄰居。

1.2 LOF算法的執(zhí)行步驟

輸入:數(shù)據(jù)集D，離群點(diǎn)數(shù)目n;輸出:前n個(gè)局部離群因子值較大的數(shù)據(jù)對(duì)象。1)對(duì)于數(shù)據(jù)對(duì)象p，根據(jù)公式(1)～(4)來(lái)計(jì)算該數(shù)據(jù)對(duì)象的局部離群因子;

2)循環(huán)遍歷數(shù)據(jù)集D的每一個(gè)對(duì)象，重復(fù)第一步，并將該結(jié)果依次存放到集合Col_LOF中;

3)對(duì)Col_LOF中的值用快速排序算法排序，并輸出前n個(gè)局部離群因子值較大的數(shù)據(jù)對(duì)象。

2 基于可變網(wǎng)格劃分的離群點(diǎn)檢測(cè)

2.1 固定網(wǎng)格劃分

固定網(wǎng)格劃分是基于網(wǎng)格劃分的離群點(diǎn)檢測(cè)中常用的一種方法，常與基于密度的離群點(diǎn)檢測(cè)算法結(jié)合，可以提高算法的執(zhí)行效率［11］。固定網(wǎng)格劃分，簡(jiǎn)單地說(shuō)，就是將目標(biāo)數(shù)據(jù)集每一維進(jìn)行等間距劃分，而后在空間中形成大小相同的網(wǎng)格單元。設(shè)D是一個(gè)d維的數(shù)據(jù)集，其屬性(A1，A2，…，Ad)的取值在一個(gè)封閉的區(qū)間里。令第i維的取值范圍是［li，hi］，其中i={1，2，…，d}，則

是一個(gè)d維的數(shù)據(jù)空間。取數(shù)據(jù)集的每一維，將該維等間距地劃分為k段，則d維空間被劃分為kd個(gè)網(wǎng)格。第i維的第j個(gè)區(qū)間段的長(zhǎng)度θi=(hi－li)/k，并且該區(qū)間段的取值范圍是Iij=(li+(j－1)×θi，li+j×θi)，其中j={1，2，…，k}。

2.2 一種新的可變網(wǎng)格劃分策略

固定網(wǎng)格劃分較易理解并且方便實(shí)現(xiàn)，但是如果在高維數(shù)據(jù)集中使用固定網(wǎng)格劃分的方法，隨著維度的增加，網(wǎng)格的數(shù)量以指數(shù)級(jí)在增長(zhǎng)，導(dǎo)致算法的復(fù)雜度大大增加，其可用性也因此而降低［12-13］。近年來(lái)，不少研究人員展開了關(guān)于可變網(wǎng)格劃分技術(shù)的研究，如文獻(xiàn)［14］提出的可變網(wǎng)格劃分方法，該方法首先對(duì)每一維進(jìn)行等深度地劃分，然后合并相似度較大的相鄰網(wǎng)格。文獻(xiàn)［15］進(jìn)行可變網(wǎng)格劃分時(shí)引入了屬性維半徑向量這一概念。QIAN Xuezhong等人［16］提出根據(jù)數(shù)據(jù)集的實(shí)際分布動(dòng)態(tài)構(gòu)建網(wǎng)格空間的策略等。

文中介紹一種新的可變網(wǎng)格劃分方法。對(duì)于數(shù)據(jù)集的每一維，首先對(duì)其等間距劃分;其次統(tǒng)計(jì)該維每個(gè)區(qū)間中數(shù)據(jù)點(diǎn)數(shù)目并計(jì)算相鄰區(qū)間段的相似性;最后比較相鄰區(qū)間的相似性，對(duì)于相似度較高的區(qū)間段進(jìn)行合并。在最后形成的網(wǎng)格空間中，由于每一維數(shù)據(jù)分布不盡相同，從而進(jìn)行合并的區(qū)間段也不盡相同，所以最后在數(shù)據(jù)空間中就構(gòu)成了大小不同的網(wǎng)格。

可變網(wǎng)格劃分的執(zhí)行步驟如下所述:

1)對(duì)于第i維，采用固定網(wǎng)格劃分方法對(duì)其進(jìn)行劃分。

2)統(tǒng)計(jì)該維每個(gè)區(qū)間段的數(shù)據(jù)點(diǎn)數(shù)目并計(jì)算相鄰段的相似性。由于每個(gè)區(qū)間段的長(zhǎng)度是一樣的，所以采用區(qū)間段中數(shù)據(jù)點(diǎn)的數(shù)目Countij來(lái)表示其密度，并引入?yún)?shù)來(lái)量化相鄰區(qū)間段的相似性，其計(jì)算方式如下:

3)對(duì)于第i維，依次比較相鄰段的相似性是否大于閾值T(0≤T≤1)，其中T用于表示兩個(gè)區(qū)間段的相似性。如果大于T，則記錄相應(yīng)的段，否則不做任何操作。比較結(jié)束后，對(duì)記錄的段進(jìn)行合并。在實(shí)際操作中，如果T值接近1，則表示進(jìn)行合并的段較少，最終剩余網(wǎng)格的數(shù)目較多，算法的執(zhí)行效率相對(duì)較低，但可以保證離群點(diǎn)檢測(cè)的精確度;如果T值接近0，表示進(jìn)行合并的段較多，則最終剩余的網(wǎng)格數(shù)目較少，雖然可以提高算法的執(zhí)行效率，但是會(huì)影響離群點(diǎn)檢測(cè)的精確度。

4)對(duì)每一維均執(zhí)行1)到3)。

2.3 基于可變網(wǎng)格劃分的離群點(diǎn)檢測(cè)算法

通過(guò)2.2節(jié)提出的可變網(wǎng)格劃分策略，可以對(duì)給定的數(shù)據(jù)集動(dòng)態(tài)地進(jìn)行網(wǎng)格劃分。劃分后的網(wǎng)格可以盡可能地將相似度大的數(shù)據(jù)點(diǎn)劃分到同一個(gè)網(wǎng)格，相似度小的數(shù)據(jù)點(diǎn)劃分到不同的網(wǎng)格。文中將上述網(wǎng)格劃分方法與LOF算法相結(jié)合，提出基于可變網(wǎng)格劃分的離群點(diǎn)檢測(cè)算法。在此引入密度閾值Min P，表示網(wǎng)格中數(shù)據(jù)點(diǎn)數(shù)目。當(dāng)網(wǎng)格中數(shù)據(jù)點(diǎn)數(shù)目大于Min P時(shí)，則認(rèn)為該網(wǎng)格中數(shù)據(jù)點(diǎn)是密集的，否則認(rèn)為是稀疏的。該算法的具體步驟如下:

輸入:數(shù)據(jù)集D，離群點(diǎn)數(shù)目n，密度閾值Min P;

輸出:前n個(gè)LOF值較大的數(shù)據(jù)點(diǎn)。

1)掃描數(shù)據(jù)集D，采用2.2節(jié)所述可變網(wǎng)格劃分方法對(duì)空間進(jìn)行劃分，將劃分后的網(wǎng)格總數(shù)記為|grid_counts|。

2)統(tǒng)計(jì)網(wǎng)格中數(shù)據(jù)點(diǎn)的數(shù)目Nm，m={1，2，…，|grid_counts|}，并比較Nm是否大于密度閾值M in P，如果大于，則刪除這個(gè)網(wǎng)格中的所有數(shù)據(jù)點(diǎn)，否則不做任何操作。

3)對(duì)于剩余的數(shù)據(jù)點(diǎn)執(zhí)行LOF算法，并輸出前n個(gè)LOF值較大的數(shù)據(jù)點(diǎn)。

3 實(shí)驗(yàn)與分析

為了測(cè)試ODAVG算法的有效可行性，在實(shí)驗(yàn)環(huán)境為Matlab R2014a、操作系統(tǒng)W in7(CPU 3.4 Hz，內(nèi)存:4.00 GB)的平臺(tái)上分別從網(wǎng)格劃分效果、執(zhí)行時(shí)間和檢測(cè)精確度3個(gè)方面對(duì)ODAVG算法、OMAGT算法和LOF算法進(jìn)行對(duì)比分析。

3.1 實(shí)驗(yàn)數(shù)據(jù)集信息

選擇5組數(shù)據(jù)集對(duì)提出算法的有效性進(jìn)行實(shí)驗(yàn)，其中2組人工數(shù)據(jù)集Dataset1和Dataset2，3組 UCI標(biāo)準(zhǔn)數(shù)據(jù)集Shuttle、Breast和KDD Cup。對(duì)于人工數(shù)據(jù)集，采用Matlab R2014a提供的函數(shù)mvnrnd(MU，COV，M)進(jìn)行生成，其中MU為均值，COV為均值對(duì)應(yīng)的協(xié)方差，M表示生成數(shù)據(jù)的規(guī)模。Dataset1數(shù)據(jù)集有3種類型的離群點(diǎn)，共100條。Dataset2數(shù)據(jù)集有4種類型的離群點(diǎn)，共1 000條。Shuttle數(shù)據(jù)集共有7個(gè)類簇，其中第2類、第6類和第7類相對(duì)較少，共54條數(shù)據(jù)，視此3類為離群點(diǎn)。對(duì)Breast數(shù)據(jù)集中進(jìn)行處理:把Malignant類減少到83條并視其為離群點(diǎn)。KDD Cup數(shù)據(jù)集是網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集。5組數(shù)據(jù)集的基本信息如表1所示。

表1 各個(gè)數(shù)據(jù)集的基本信息Tab.1 Basic in formation of each dataset

3.2 網(wǎng)格劃分效果對(duì)比

在進(jìn)行網(wǎng)格劃分效果對(duì)比時(shí)，采用Dataset1和Dataset2為測(cè)試集，對(duì)比OMAGT和ODAVG 2種算法進(jìn)行網(wǎng)格劃分以及刪除密集數(shù)據(jù)點(diǎn)后的效果圖并進(jìn)行分析。為了算法的客觀性，ODAVG算法進(jìn)行網(wǎng)格劃分時(shí)，每一維的初始區(qū)間段個(gè)數(shù)與OMAGT算法進(jìn)行網(wǎng)格劃分時(shí)保持一致。網(wǎng)格劃分的效果如圖1所示。

圖1 2種算法所畫網(wǎng)格效果Fig.1 Grid d ivision result using the tw o algorithm s

從圖1(a)～(d)可以看出:(1)ODAVG算法進(jìn)行網(wǎng)格劃分后的網(wǎng)格數(shù)目要明顯小于OMAGT算法進(jìn)行網(wǎng)格劃分的數(shù)目，這樣可以在后續(xù)的處理中提高算法的執(zhí)行效率;(2)ODAVG算法劃分的網(wǎng)格空間也更加合理，畫出的網(wǎng)格單元更符合數(shù)據(jù)點(diǎn)的實(shí)際分布，這是由于在進(jìn)行網(wǎng)格劃分時(shí)，對(duì)相似度較高的相鄰段執(zhí)行了合并操作。

刪除密集區(qū)域后對(duì)應(yīng)的效果如圖2(a)～(d)所示，其中圖1(a)與圖1(b)是二維數(shù)據(jù)對(duì)比結(jié)果，圖1(c)與圖1(d)是三維數(shù)據(jù)對(duì)比結(jié)果。

圖2 兩種算法刪除密集區(qū)域后Fig.2 Delete dense regions using the tw o algorithm s

當(dāng)密度閾值Min P一定時(shí)，從圖2(a)～(d)可以看出，ODAVG算法刪除密集區(qū)域后剩余的數(shù)據(jù)點(diǎn)的數(shù)目要小于OMAGT算法剩余的數(shù)據(jù)點(diǎn)數(shù)目，這樣減少了參與LOF算法的數(shù)據(jù)點(diǎn)數(shù)目，提高了ODAVG算法的執(zhí)行效率。

3.3 執(zhí)行時(shí)間對(duì)比分析

首先，以Dataset1作為測(cè)試集，從Dataset1中抽取數(shù)據(jù)量不同的數(shù)據(jù)集對(duì)ODAVG算法、OMAGT算法和LOF算法進(jìn)行執(zhí)行時(shí)間對(duì)比。為了使以上3種算法更具有客觀性，分別執(zhí)行上述3種算法5遍，選取平均執(zhí)行時(shí)間，并且在網(wǎng)格劃分時(shí)，ODAVG算法的每一維初始區(qū)間段個(gè)數(shù)與OMAGT算法進(jìn)行網(wǎng)格劃分時(shí)保持一致。表2表示的是在Min P=400的情況下，選擇不同數(shù)據(jù)量在ODAVG算法、OMAGT算法和LOF算法的運(yùn)行時(shí)間。

從表2可以看出，ODAVG算法和OMAGT算法的執(zhí)行時(shí)間明顯要低于LOF算法的執(zhí)行時(shí)間，這是因?yàn)镺DAVG算法和OMAGT算法刪除了大部分參與局部離群因子計(jì)算的數(shù)據(jù)點(diǎn)。由于ODAVG算法是根據(jù)數(shù)據(jù)集的分布將空間劃分大小不同的網(wǎng)格，它并不需要搜尋聚類區(qū)域，而OMAGT算法將空間進(jìn)行網(wǎng)格劃分后，需要搜尋聚類區(qū)域，同時(shí)與OMAGT算法相比，ODAVG算法刪除較多的數(shù)據(jù)點(diǎn)，所以O(shè)DAVG算法的執(zhí)行時(shí)間低于OMAGT算法的執(zhí)行時(shí)間。

表2 不同數(shù)據(jù)量的執(zhí)行時(shí)間Tab.2 Execution tim e of the differen t data size

其次，將Dataset2作為測(cè)試集，測(cè)試在數(shù)據(jù)量保持不變的情況下，通過(guò)改變密度閾值Min P的大小，來(lái)對(duì)比ODAVG算法、OMAGT算法和LOF算法的執(zhí)行時(shí)間，其中密度閾值的選取分別為300，500，700，900，1 100。為了執(zhí)行結(jié)果的客觀性，每個(gè)算法同樣運(yùn)行5遍，然后取平均值，并且在網(wǎng)格劃分時(shí)，ODAVG算法的每一維的初始區(qū)間段個(gè)數(shù)與OMAGT算法進(jìn)行網(wǎng)格劃分時(shí)保持一致。由于LOF算法沒(méi)有密度閾值，所以該算法選取執(zhí)行5遍的時(shí)間平均值。表3表示不同密度閾值下3種算法的執(zhí)行時(shí)間。

表3 不同密度閾值下的運(yùn)行時(shí)間Tab.3 Execution time of the different density threshold

從表3可以看出，LOF算法的執(zhí)行時(shí)間明顯高于ODAVG算法和OMAGT算法。當(dāng)選取不同的密度閾值時(shí)，ODAVG算法隨著密度閾值增加，它的執(zhí)行時(shí)間也不斷增加，這是因?yàn)楫?dāng)選取的密度閾值增大時(shí)，執(zhí)行刪除操作后剩余的數(shù)據(jù)點(diǎn)相對(duì)較多，因此執(zhí)行過(guò)程消耗的時(shí)間相對(duì)較多。隨著密度閾值的增大，雖然ODAVG算法的執(zhí)行時(shí)間也在增加，但是增加的幅度并沒(méi)有OMAGT算法增加的幅度大。

為了進(jìn)一步體現(xiàn)實(shí)驗(yàn)結(jié)果的真實(shí)可靠性，在UCI數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。表4給出3個(gè)算法在Breast、Shuttle和KDD Cup 3個(gè)數(shù)據(jù)集上的執(zhí)行時(shí)間。從表中可以看出，當(dāng)數(shù)據(jù)量較小時(shí)，所提算法在時(shí)間上的優(yōu)勢(shì)并不明顯(以Breast數(shù)據(jù)集為例)，但是當(dāng)數(shù)據(jù)量增大時(shí)，所提算法的優(yōu)勢(shì)明顯體現(xiàn)出來(lái)并且隨著數(shù)據(jù)量的增大，這種優(yōu)勢(shì)越明顯。為了保證算法執(zhí)行結(jié)果的客觀性，在實(shí)驗(yàn)過(guò)程中，對(duì)于Breast數(shù)據(jù)集，ODAVG算法和OMAGT算法的密度閾值Min P均設(shè)置為10;對(duì)于Shuttle數(shù)據(jù)集，ODAVG算法和OMAGT算法的密度閾值Min P均設(shè)置為120;對(duì)于KDD Cup數(shù)據(jù)集，ODAVG算法和OMAGT算法的密度閾值Min P均設(shè)置為200。對(duì)于區(qū)間段相似性閾值T，均設(shè)置為0.5。

表4 3種數(shù)據(jù)集的運(yùn)行時(shí)間Tab.4 Execution time of the three datasets

3.4 檢測(cè)精確度對(duì)比

為了測(cè)試ODAVG算法的精確度，分別采用Dataset2、Shuttle和Breast3個(gè)數(shù)據(jù)集作為測(cè)試數(shù)據(jù)集，對(duì)ODAVG算法、OMAGT算法和LOF算法進(jìn)行精確度測(cè)試。為了使結(jié)果較客觀，對(duì)每一個(gè)算法分別運(yùn)行5遍，然后取平均值。在網(wǎng)格劃分時(shí)，ODAVG算法的每一維初始的區(qū)間段個(gè)數(shù)與OMAGT算法保持一致。檢測(cè)的精確度采用以下公式進(jìn)行度量:

實(shí)驗(yàn)結(jié)果如表5所示。通過(guò)表4可以看出:對(duì)于離群點(diǎn)較少的Shuttle數(shù)據(jù)集和Breast數(shù)據(jù)集，LOF算法的檢測(cè)精確度要高于ODAVG算法和OMAGT算法，且ODAVG算法的檢測(cè)精確度要高于OMAGT算法。對(duì)于Dataset2，由于離群點(diǎn)較多并且以較小類簇的形式出現(xiàn)，導(dǎo)致LOF算法的精確度相對(duì)較低，但是由于ODAVG算法和OMAGT算法刪除了大部分參與LOF算法運(yùn)算的數(shù)據(jù)點(diǎn)，使得ODAVG算法和OMAGT算法的檢測(cè)精確度相對(duì)略高。在實(shí)驗(yàn)過(guò)程中，對(duì)于DataSet2數(shù)據(jù)集，ODAVG算法和OMAGT算法的密度閾值M in P均設(shè)置為300;對(duì)于Shuttle數(shù)據(jù)集，ODAVG算法和OMAGT算法的密度閾值Min P均設(shè)置為120;對(duì)于Breast數(shù)據(jù)集，ODAVG算法和OMAGT算法的密度閾值Min P均設(shè)置為10。對(duì)于區(qū)間段相似性閾值T，均設(shè)置為0.5。

表5 3種算法的精確度Tab.5 Accuracy of the three algorithm s

綜上所述，從網(wǎng)格劃分效果來(lái)看，相對(duì)于OMAGT算法，ODAVG算法可以根據(jù)數(shù)據(jù)集的實(shí)際分布以更少的網(wǎng)格數(shù)目構(gòu)建出與原始數(shù)據(jù)集分布一致的網(wǎng)格空間;從執(zhí)行時(shí)間上來(lái)看，相對(duì)于OMAGT算法和LOF算法，ODAVG算法由于使用了可變網(wǎng)格的策略來(lái)處理大規(guī)模數(shù)據(jù)集，因此它能夠獲得較該兩種算法更高的執(zhí)行效率，并且隨著數(shù)據(jù)量的增加，這種優(yōu)勢(shì)會(huì)更加明顯;從檢測(cè)精確度來(lái)看，ODAVG算法能夠保持與OMAGT算法和LOF算法較一致的精確度。因此，文中所提出的ODAVG算法能夠在保證較高檢測(cè)精確度的同時(shí)，可以獲得更高的執(zhí)行效率。

4 結(jié)語(yǔ)

離群點(diǎn)檢測(cè)是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)重要的研究方向，并且在實(shí)際生活中有著廣泛的應(yīng)用。文中提出了一種新的基于可變網(wǎng)格劃分的離群點(diǎn)檢測(cè)算法。該算法首先根據(jù)數(shù)據(jù)集的分布將空間劃分為大小不一的網(wǎng)格，然后刪除不可能成為離群點(diǎn)的數(shù)據(jù)點(diǎn)，最后對(duì)剩余的數(shù)據(jù)點(diǎn)執(zhí)行LOF算法。相對(duì)于固定網(wǎng)格劃分的離群點(diǎn)檢測(cè)算法與LOF算法，該算法可以在保證正確率同時(shí)提高執(zhí)行效率。但是，文中研究工作仍需要繼續(xù)進(jìn)行，如在高維大規(guī)模數(shù)據(jù)集的執(zhí)行效率是否可以進(jìn)一步減少等。

［1］DUAN L，XU L，GUO F，et al.A local-density based spatial clustering algorithm with noise［J］.Information Systems，2007，32 (7):978-986.

［2］YUAN Y，ZHANG Y，CAO H，et al.New local density definition based on m inimum hyper sphere for outlier mining algorithm using in industrial databases［C］//Control and Decision Conference(2014 CCDC)，The 26th Chinese.Changsha:IEEE，2014: 5182-5186.

［3］Aggarwal C C，YU PS.Outlier detection for high dimensional data［J］.ACM Sigmod Record，2001，30(2):37-46.

［4］古平，劉海波，羅志恒.一種基于多重聚類的離群點(diǎn)檢測(cè)算法［J］.計(jì)算機(jī)應(yīng)用研究，2013，30(3):751-753.

GU Ping，LIU Haibo，LUO Zhiheng.Multi-clustering based outlier detect algorithm［J］.Application Research of Computers，2013，30(3):751-753.(in Chinese)

［5］Breunig M M，Kriegel H P，Ng R T，et al.LOF:identifying density-based local outliers［J］.ACM Sigmod Record，2000，29(2): 93-104.

［6］王敬華，趙新想，張國(guó)燕，等.NLOF:一種新的基于密度的局部離群點(diǎn)檢測(cè)算法［J］.計(jì)算機(jī)科學(xué)，2013，40(8):181-185.

WANG Jinghua，ZHAO Xinxiang，ZHANG Guoyan，et al.NLOF:a new density-based local outlier detecting algorithm［J］.Computer Science，2013，40(8):181-185.(in Chinese)

［7］薛安榮，鞠時(shí)光，何偉華，等.局部離群點(diǎn)挖掘算法研究［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(8):1455-1463.

XUE Anrong，JU Shiguang，HEWeihua，et al.Study on algorithms for local outlicr detection［J］.Chinese Journal of Computer，2007，30(8):1455-1463.(in Chinese)

［8］ZHANG K，Hutter M，JIN H.A new local distance-based outlier detection approach for scattered real-world data［C］//Advances in Knowledge Discovery and Data Mining.Berlin，Heidelberg:Springer，2009:813-822.

［9］Pamula R，Deka J K，Nandi S.An outlier detection method based on clustering［C］//Emerging Applications of Information Technology(EAIT)，2011 Second International Conference on.Washington，DC:IEEE，2011:253-256.

［10］曹洪其，孫志揮.基于網(wǎng)格技術(shù)的高維大數(shù)據(jù)集離群點(diǎn)挖掘算法［J］.計(jì)算機(jī)應(yīng)用，2007，27(10):2369-2371.

CAO Hongqi，SUN Zhihui.Algorithm of outliers mining based on grid techniques in high dimension large dataset［J］.Computer Applications，2007，27(10):2369-2371.(in Chinese)

［11］張?zhí)煊?基于網(wǎng)格劃分的高維大數(shù)據(jù)集離群點(diǎn)檢測(cè)算法研究［D］.長(zhǎng)沙:中南大學(xué)，2011.

［12］Hsu CM，CHEN M S.Subspace clustering of high dimensional spatial data with noises［C］//Advances in Knowledge Discovery and Data Mining.Berlin，Heidelberg:Springer，2004:31-40.

［13］賀玲，蔡益朝，楊征.高維數(shù)據(jù)的相似性度量研究［J］.計(jì)算機(jī)科學(xué)，2010，37(5):155-156.

HE Ling，CAIYichao，YANG Zheng.Researches on similarity measurement of high dimensional data［J］.Computer Science，2010，37(5):155-156.(in Chinese)

［14］盛開元，錢雪忠，吳秦.基于可變網(wǎng)格劃分的密度偏差抽樣算法［J］.計(jì)算機(jī)應(yīng)用，2013，33(9):2419-2422.

SHENG Kaiyuan，QIAN Xuezhong，WU Qin.Density biased sampling algorithm based on variable grid division［J］.Journal of Computer Application，2013，33(9):2419-2422.(in Chinese)

［15］王敬華，金鵬.基于粗約簡(jiǎn)和網(wǎng)格的離群點(diǎn)檢測(cè)［J］.計(jì)算機(jī)工程與應(yīng)用，2015，51(3):133-137.

WANG Jinghua，JIN Peng.Outliers detecting based on rough reduction and grid［J］.Computer Engineering and App lications，2015，51(3):133-137.(in Chinese)

［16］QIAN Xuezhong，SHENG Kaiyuan，QIAN Heng，et.al.An improved density biased sampling for clustering large-scale datasets［J］.Journal of Information and Computational Science，2014，11(7):2355-2364.

(責(zé)任編輯:楊勇)

An Ou tlier Detecting A lgorithm Based on the Variable G rid Division

MA Fei1，ZHU Changjie*1，ZHENG Ying1，DENG Jie2
(1.School of Computer Science and Technology，Huaibei Normal University，Huaibei 235000，China;2.School of Internet of Things Engineering，Jiangnan University，Wuxi214122，China)

As a widely used outlier detecting algorithm，the LOF algorithm usually spendsmuch time and space on the dealing with the large-scale dataset.The outlier detecting algorithm based on the stationary grid can solve the problems to some extent，but its implementation effect can be influenced by the granularity of grid division.Aiming at the problem，this paper proposes an outlier detecting algorithm based on the variable grid division.The proposed algorithm can dynam ically construct the grid space according to the practical distribution of data points in space，then remove all of the data points in the grid when it contains the count of data pointsmore than the threshold，finally execute the LOF algorithm in the remainder data points.The experimental results show that the proposed algorithm can receive a higher efficiency and accuracy compared with the outlier detecting algorithm based on stationary grid.

local outlier factor，outlier detection，variable grid，large-scale dataset

TP 301.6

A

1671－7147(2015)06－0751－07

2015－06－21;

2015－09－24。

安徽省高校自然科學(xué)研究項(xiàng)目(KJ2014B24)。

馬菲(1989—)，女，河南商丘人，軟件工程專業(yè)碩士研究生。

*通信作者:朱昌杰(1963—)，男，安徽懷寧人，教授，碩士生導(dǎo)師。主要從事人工智能與數(shù)據(jù)挖掘等研究。Email:840486167@qq.com