[發明專利]一種基于特征加權與MapReduce的離群數據挖掘方法

有效

• 申請號: 202010330588.2
• 申請日: 2020-04-24
• 公開（公告）號: CN111611293B
• 公開（公告）日: 2023-09-29
• 發明（設計）人: 朱曉軍;呂士欽;婁圣金
• 申請（專利權）人: 太原太工天宇教育科技有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F18/2321;G06F16/215
• 代理公司: 北京知匯宏圖知識產權代理事務所(特殊普通合伙) 11520
• 代理人: 劉紅杰

1.一種基于特征加權與MapReduce的離群數據挖掘方法，其特征在于：包括如下步驟，步驟一：基于特征加權子空間，在編程模型下將子空間數據分離為聚類中心，聚類簇和候選離群數據集；步驟二：針對步驟一中所述離群數據集計算全局距離，然后定義出離群數據；

步驟一中，所述特征加權子空間通過定義屬性維上的特征加權估計熵后獲取，然后在MapReduce編程模型下，采用密度峰值算法快速將子空間數據集分離；步驟二中，所述計算全局距離包括計算其全局Weight_k距離，計算Weight_k距離時還包括對Weight_k距離集合按降序排列，輸出TOP-N個數據的過程；

所述的特征加權子空間，首先是將屬性特征歸一化，把各維屬性的取值范圍放縮到的區間，然后計算各維特征加權估計熵，設定一個特征加權估計熵閾值，將小于閾值的維度刪除，僅保留大于閾值的維度，定義為特征加權子空間；所述的MapReduce編程模型，包括將密度峰值聚類算法并行化計算數據集中每個數據對象的局部密度和距離，分別以這兩個參數為橫坐標軸和縱坐標軸繪圖平面決策圖，平面圖中被認為是聚類中心，聚類簇和候選離群數據集；所述Weight_k距離為針對候選離群數據集中的每個對象，計算兩兩之間的距離，形成距離矩陣D，矩陣中第k行的和，定義為Weigth_k-距離；

所述的特征加權子空間計算方法包括如下步驟：

S1、設數據集DS＝{x₁,x₂,x_i,…,x_N}，令每個數據對象x的屬性集為S＝{v₁,v₂,v_i,…,v_M}，表示第i維征屬性均值，計算樣本特征發生概率，計算公式為：

S2、在步驟S1的基礎上，設U是討論域，V₁，V₂…，V_M是U的一個劃分，其上有概率分布則稱為信息源V的估計熵，其中對數取以2為底，而某個p_i為零時，則理解為0·log0＝0；

S3、在步驟S2的基礎上，計算H(V)并且歸一化，從而得到各個屬性特征加權估計熵w_l，歸一化計算方法為：其中，H(V_l)表示某屬性V的信息熵；w_l為特征加權估計熵；令S1＝{v₁,v₂,v_i}，S2＝{v_i+1,v_i+2,v_M}，其中，S1為所尋找出的特征加權估計熵較大的子空間，S2為特征加權估計熵較小的子空間，且S＝S1US2，根據算法規則，S2需要被刪除；

所述MapReduce編程模型分離出聚類中心，聚類簇和候選離群數據時還包括如下步驟：

S1、對于含N個樣本集合DB中的每個樣本點i,都需要計算每個樣本點i與其他樣本點j之間的歐式距離dij,并將計算結果按照升序排列,歐式距離及相關定義描述如下：其中：i＝(x_i1,x_i2,...,x_iM)和j＝(x_j1,x_j2,...,x_jM)是兩個M維數據對象，它們之間的相似度可用它們之間的距離d_ij的大小來度量；

S2、對于多有樣本點，選取一個階段距離dc,使得每個數據點的平均鄰域個數為樣本數據點總數的1％-2％；

S3、對于樣本數據點中的樣本點i，都需要計算兩個參數，局部密度ρ_i和距離σ_i，高密度最近鄰距離σ_i則定義為x_i到具有更大密度估計值的最近鄰樣本點的距離，即顯然，具有全局最大密度估計值的樣本點不存在高密度最近鄰，可簡單地令其高密度最近鄰距離等于所有樣本點間距離的最大值；計算這兩個量都取決于樣本的歐式距離d_ij，采用MapReduce編程模型的強大數據處理能力，根據算法處理邏輯，利用map-reduce編程框架，不斷的并行處理并生成鍵值對key,Value；

S4、對于樣本數據集S中的每個樣本點I,計算出樣本的(ρ_i，σ_i)之后，分別以這兩個參數為橫坐標和縱坐標繪制平面圖，并計算一個綜合變量：局部密度和距離的乘積，γ_i＝ρ_i*σ_i顯然，γ_i值越大，越是聚類中心；

S5、計算樣本數據集合S中所有樣本點的γ_i值，并進行降序排列，輸出前K個γ_i，同時，將ρ小，σ大的數據點，定義為候選離群集，集合大小記為L；

S6、對于樣本數據集DS中的被定義為候選離群的數據點,應該滿足以下條件：局部密度小于局部密度閾值，即ρ_iρ_τ而距離大于距離閾值σ_iσ_τ,計算公式為：其中，N為數據集大小；

S7、針對步驟S6中獲取的離群候選集CandidateSet中的每個數據對象，計算兩兩之間的距離d_ij，形成子空間距離矩陣D：令其中，w_k是矩陣D中第k行的和，定義為Weigth_k-距離和；

S8、對Weigth_k-距離和降序排列，輸出TOP-N個數據，定義為離群數據。