[發(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
• 代理人: 董紅曼

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

2.如權(quán)利要求1所述基于信息增益計算的海量數(shù)據(jù)異常偵測方法，其特征在于，所述離線處理階段包括如下步驟：

步驟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)出到磁盤，再清空哈希表；否則，當(dāng)插入操作全部結(jié)束后退出。

3.如權(quán)利要求1所述基于信息增益計算的海量數(shù)據(jù)異常偵測方法，其特征在于，所述在線處理階段包括如下步驟：

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

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

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

4.如權(quán)利要求3所述基于信息增益計算的海量數(shù)據(jù)異常偵測方法，其特征在于，所述步驟B2中哈希表的彈性變更策略包括如下步驟：

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

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

5.如權(quán)利要求3所述基于信息增益計算的海量數(shù)據(jù)異常偵測方法，其特征在于，所述步驟B3中各屬性的信息增益通過以下公式計算得到：

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