[發明專利]一種基于譜聚類的離群點檢測方法

在審

• 申請號: 202011122395.4
• 申請日: 2020-10-19
• 公開（公告）號: CN112287036A
• 公開（公告）日: 2021-01-29
• 發明（設計）人: 王曉春;李佳
• 申請（專利權）人: 西安交通大學
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06F16/2458
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 馬貴香

1.一種基于譜聚類的離群點檢測方法，其特征在于，首先選取一個含有m個離群點的疾病數據集R，計算疾病數據集R中每個點p_i的k個近鄰，將p_i和它的k個近鄰記為小數據集S，計算小數據集S中兩兩點對之間的相似度，組成相似度矩陣，根據相似度矩陣計算出拉普拉斯矩陣Lap，計算拉普拉斯矩陣Lap的特征值，記為ev_arr_i，將疾病數據集R中每個元素對應的特征值存入一個數組array中，對于array中的每一個元素，計算其信息熵或基尼指數作為離群點得分，對所有離群點得分進行排序，選出前m個離群點作為結果輸出。

2.根據權利要求1所述的一種基于譜聚類的離群點檢測方法，其特征在于，具體包括以下步驟：

1)選取一個含有m個離群點的疾病數據集R作為測試數據集，定義一個數組array，用來存放特征值；

2)對于疾病數據集R中每一個點計算k個近鄰點，組成一個k+1大小的小數據集S；

3)用高斯核函數求取小數據集S中兩兩點對之間的相似度，組成相似度矩陣simMatrix，根據simMatrix計算拉普拉斯矩陣Lap；

4)計算拉普拉斯矩陣Lap的特征值存入ev_arr_i，同時，記錄所有的特征值，存入數組array中；

5)對于數據集中每個點，重復步驟2)-步驟4)；

6)根據信息熵和基尼指數的計算公式，計算array中每一個元素的信息熵或基尼指數作為對應數據點的離群點得分；

7)對所有離群點得分按照從大到小的順序進行排序，選出前m個離群點作為結果輸出。

3.根據權利要求2所述的一種基于譜聚類的離群點檢測方法，其特征在于，步驟2)中采用coverTree數據結構計算疾病數據集R中每一個點的k個近鄰點。

4.根據權利要求2所述的一種基于譜聚類的離群點檢測方法，其特征在于，步驟3)中計算兩個點之間相似度的計算公式為：

其中，x_i，,x_j是數據集S中的任意兩點，σ_i和σ_j為參數，在本算法中，分別定義為x_i，,x_j到對應的k個近鄰的距離和的平均值，計算方法為：

其中，p表示點的序號，“|x-y|”表示兩個點x和y之間的距離，k為預定義的參數，計算拉普拉斯矩陣的方法為：

其中，I是單位矩陣，simMatrix是上一步計算的相似度矩陣，D是對角矩陣，其中的每一個元素d_i的計算方法為：

其中，n為小數據集S中的點數，w_ij為矩陣第i行，第j列的元素值。

5.根據權利要求2所述的一種基于譜聚類的離群點檢測方法，其特征在于，步驟6)中信息熵的計算公式為：

其中，S指的是當前這個點及其k個近鄰所組成的小數據集，n是該小數據集S中的元素個數；p_i指的是S的拉普拉斯矩陣的特征值中的第i個特征值出現的概率，計算方法為該特征值出現的次數除以數據集R所有的特征矩陣的特征值總數。

6.根據權利要求2所述的一種基于譜聚類的離群點檢測方法，其特征在于，步驟6)中基尼指數的計算公式為：