[發(fā)明專利]一種基于信息增益計算的海量數(shù)據(jù)異常偵測方法

有效

• 申請?zhí)枺?/td>: 201110414602.8
• 申請日: 2011-12-13
• 公開（公告）號: CN102567471A
• 公開（公告）日: 2012-07-11
• 發(fā)明（設(shè)計）人: 金澈清;張敬偉;周傲英
• 申請（專利權(quán)）人: 華東師范大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 上海麥其知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31257
• 代理人: 董紅曼

技術(shù)領(lǐng)域

本發(fā)明涉及一種僅需單次遍歷數(shù)據(jù)庫，以求解關(guān)鍵分類的方法，屬于數(shù)據(jù)挖掘和知識發(fā)現(xiàn)技術(shù)領(lǐng)域。

背景技術(shù)

數(shù)據(jù)挖掘技術(shù)從紛繁蕪雜的數(shù)據(jù)集合之中獲取有用的知識。自從上世紀90年代中期以來，數(shù)據(jù)挖掘技術(shù)在許多領(lǐng)域均得到了深度應(yīng)用，例如金融、物流、交通、科學(xué)研究等領(lǐng)域。典型的數(shù)據(jù)挖掘算法包括分類、聚類、關(guān)聯(lián)規(guī)則、回歸分析等。進入21世紀以來，在很多領(lǐng)域中待處理的數(shù)據(jù)的規(guī)模變得愈來愈龐大，往往無法直接套用傳統(tǒng)的數(shù)據(jù)挖掘算法進行解決，需要開發(fā)新算法，改進某些關(guān)鍵步驟來解決相關(guān)問題。

本發(fā)明研究一種針對海量數(shù)據(jù)的異常偵測技術(shù)，其目的是為了探尋導(dǎo)致某種異常因素發(fā)生的主要原因。當數(shù)據(jù)規(guī)模并不很大時，傳統(tǒng)的基于信息增益的決策樹分析方法較為有效；當數(shù)據(jù)規(guī)模再度擴大時，則需要修正傳統(tǒng)算法，改進若干關(guān)鍵步驟，以有效地解決這個問題。

本發(fā)明克服了現(xiàn)有技術(shù)中傳統(tǒng)算法分析海量規(guī)模數(shù)據(jù)時導(dǎo)致內(nèi)存溢出與處理時間開銷過大的缺陷，提出了一種基于信息增益計算的海量數(shù)據(jù)異常偵測方法。本發(fā)明提出了一種新方法，通過兩個不同階段，即離線階段和在線階段，來處理海量信息，針對數(shù)據(jù)規(guī)模龐大、計算機系統(tǒng)內(nèi)存相對不足等情況，解決了傳統(tǒng)算法分析海量規(guī)模數(shù)據(jù)時導(dǎo)致的內(nèi)存溢出、處理時間開銷過大等問題，從而提升分析性能。

發(fā)明內(nèi)容

本發(fā)明公開了一種基于信息增益計算的海量數(shù)據(jù)異常偵測方法，所述海量數(shù)據(jù)異常偵測方法為基于哈希表數(shù)據(jù)結(jié)構(gòu)，包括離線階段處理和在線階段處理；其中，所述離線階段處理是根據(jù)輸入的原始數(shù)據(jù)生成中間數(shù)據(jù)；所述在線階段處理是根據(jù)所述中間數(shù)據(jù)得到計算結(jié)果、且得到最終的熵值。

其中，所述離線階段處理包括如下步驟：

步驟A1：針對所述原始數(shù)據(jù)中每個原始數(shù)據(jù)項創(chuàng)建若干個中間數(shù)據(jù)項；

步驟A2：若所述中間數(shù)據(jù)項能夠在哈希表中找到對應(yīng)的碼，則將該項與哈希表中的數(shù)據(jù)項合并；否則，將所述中間數(shù)據(jù)項插入哈希表中；

步驟A3：若所述步驟A1中插入操作導(dǎo)致所述中間數(shù)據(jù)所在的哈希表溢出，則將所述哈希表中的數(shù)據(jù)導(dǎo)出到磁盤，再清空哈希表；否則，當插入操作全部結(jié)束后退出。

其中，所述在線階段處理包括如下步驟：

步驟B1：針對從數(shù)據(jù)庫中提取出來的每一項，若能夠在哈希表中找到對應(yīng)的碼，則將該項與哈希表中的現(xiàn)存項合并；否則，將新項插入到哈希表中；

步驟B2：若所述步驟B1中插入操作導(dǎo)致哈希表溢出，則利用哈希表的彈性變更策略刪除哈希表中的部分項；

步驟B3：遍歷完所有數(shù)據(jù)之后，利用哈希表計算各屬性的信息增益，并返回最佳屬性。

其中，所述哈希表的彈性變更策略包括如下步驟：

步驟C1：初始化容忍失敗的最大頻數(shù)；

步驟C2：當哈希表溢出，從哈希表中移除所有失敗頻數(shù)小于所述容忍失敗的最大頻數(shù)，并且所述容忍失敗的最大頻數(shù)遞增。

其中，所述步驟B3中各屬性的信息增益通過以下公式計算得到：

式中，I代表信息，c代表某關(guān)系中所有元組個數(shù)，表示某關(guān)系中失敗元組的個數(shù)，E(A_i)表示屬性A_i的熵，Gain(A_i)表示屬性A_i的信息增益。

本發(fā)明基于信息增益計算的海量數(shù)據(jù)異常偵測方法，采用兩個不同階段處理，即離線階段和在線階段處理。離線階段處理時，根據(jù)輸入數(shù)據(jù)生成一些中間數(shù)據(jù)，中間數(shù)據(jù)量會小于原始數(shù)據(jù)，且分離存放。在線階段處理時，根據(jù)中間數(shù)據(jù)量得到計算結(jié)果，并且得到最終的熵值。本發(fā)明能夠較好地偵測海量數(shù)據(jù)異常。

附圖說明

圖1為本發(fā)明的離線處理階段流程示意圖。

圖2為本發(fā)明的在線處理階段流程示意圖。

圖3為本實施例的離線處理階段系統(tǒng)框圖。

圖4為本實施例的在線處理階段系統(tǒng)框圖。

具體實施方式

結(jié)合以下具體實施例和附圖，對本發(fā)明作進一步的詳細說明，本發(fā)明的保護內(nèi)容不局限于以下實施例。在不背離發(fā)明構(gòu)思的精神和范圍下，本領(lǐng)域技術(shù)人員能夠想到的變化和優(yōu)點都被包括在本發(fā)明中，并且以所附的權(quán)利要求書為保護范圍。