[發明專利]一種基于子空間的離群點檢測算法

在審

• 申請號: 202010085040.6
• 申請日: 2020-02-10
• 公開（公告）號: CN111309782A
• 公開（公告）日: 2020-06-19
• 發明（設計）人: 張瑤瑤;韓博;譚薇;王丹;杜豐
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/22;G06F16/28;G06Q40/02
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 李曉曉

1.一種基于子空間的離群點檢測算法，其特征在于，包括以下步驟：

步驟一，在有標簽的數據D中隨機選擇Φ個樣本作為根節點，根據信息增益方法選擇切割子空間的屬性T；

步驟二，計算屬性T的熵；

步驟三，根據屬性的熵計算屬性T給分類C帶來的信息增益；

步驟四，通過熵的計算公式推得屬性T與類別的信息增益公式；

步驟五，計算每個屬性的信息增益值，按照信息增益值排序，篩選屬性，構成新的屬性子空間；

步驟六，新的屬性子空間中隨機選擇一個屬性p構成的超平面來切割空間，把小于p的數據放在當前節點的左孩子，把大于等于p的數據放在當前節點的右孩子；

步驟七：在孩子節點中遞歸構造新的孩子節點，直到滿足以下條件中的一個：

1)孩子節點中只有一個數據；

2)孩子節點已到達限定高度；

3)當前子樹的所有節點值的所有屬性完全一致；

停止構造，完成檢測。

2.根據權利要求1所述的一種基于子空間的離群點檢測算法，其特征在于，步驟二中，子空間屬性T的熵的計算公式如下：

其中，T為空間中某一屬性，其可能的取值有種分別為t₁,t₂…,t_n，每一種取到的概率為p(t_i)。

3.根據權利要求1所述的一種基于子空間的離群點檢測算法，其特征在于，步驟三中，信息增益的計算公式如下：

Gain(T)＝H(C)-H(C|T)

其中，C為分類類別，H(C)為類別的熵值。

4.根據權利要求3所述的一種基于子空間的離群點檢測算法，其特征在于，H(C|T)包括兩種情況，一種為屬性T出現，標記為t，另一種為屬性T不出現，標記為t'，H(C|T)的計算公式為：

H(C|T)＝p(t)H(C|t)+p(t′)H(C|t′)。