[發明專利]基于動態聚類趨勢分析的增量聚類數據挖掘方法

在審

• 申請號: 201910445205.3
• 申請日: 2019-05-27
• 公開（公告）號: CN110263814A
• 公開（公告）日: 2019-09-20
• 發明（設計）人: 樊仲欣
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 劉傳玉

1.一種基于動態聚類趨勢分析的增量聚類數據挖掘方法，其特征在于，包含以下步驟：

令現有頂點數據集合x_q＝{x_q1,x_q2,…x_qm}為第q個頂點的數據，1≤q≤n，n為頂點數量，id_q為第q個頂點的唯一標識，頂點id_q即第q個頂點；頂點唯一標識集合ID＝{id₁,id₂,...,id_n}；現有頂點數據集合的最小距離連通圖為MDG[ID,E]，其中，E為最臨近邊矩陣、其內n-1行分別是n-1條連接頂點的邊，且該n-1條邊為所述n個頂點按照最臨近距離相互連接而成；E中的任意一條邊e_qp＝[id_q,id_p,d_qp]，其中d_qp為頂點id_q和頂點id_p之間的歐氏距離，1≤p≤n；令棧T為空，則對于數據為x_new＝{x_new1,x_new2,…x_newm}的新增頂點id_new：

步驟1)，建立新增頂點后頂點數據集合的最小距離連通圖；

步驟1.1)，計算頂點x_new和X中各個頂點的歐氏距離，生成歐氏距離集合D＝{d_new1,d_new2,…d_newq,…,d_newn}，其中，d_newq為頂點x_new和頂點x_q之間的歐氏距離；

步驟1.2)，篩選出D中第一個出現的最小距離d_newi，生成邊e_newi＝[id_new,id_i,d_newi]，并將邊e_newi其加入至最臨近邊矩陣E中；

步驟1.3)，將棧T置為空，將邊e_newi壓入棧T中，設置檢索排除頂點唯一標識集合EXI＝{id_new}；

步驟1.4)，設置邊集合KN和JN為空，將棧T的棧頂數據彈出、即將棧T的棧頂數據取出后從棧中刪除，令棧T的彈出數據為邊e_jk＝[id_j,id_k,d_jk]，首先使得EXI＝EXI∪{id_k}；然后在最臨近邊矩陣E中檢索出所有包含頂點id_k的邊，如果該邊的另一頂點的唯一標識不在集合EXI中，則將該邊存入集合KN中；

步驟1.5)，如果集合KN不為空，將剛出棧的邊e_jk壓入棧T；然后調整集合KN中第一條邊的前兩列數據順序，使得其第1列數據為id_k、第2列數據為該邊另一頂點的唯一標識后，將該邊壓入棧T中；

遍歷棧T，獲取棧T中各條邊的第3列即其兩個頂點間的歐氏距離中第一個最大值d_bc的所在邊e_bc＝[id_b,id_c,d_bc]；如果d_bc大于新增頂點id_new和頂點id_c之間的歐式距離d_newc，d_newc∈D，則從最臨近邊矩陣E中刪除邊e_bc，并在最臨近邊矩陣E中新增邊e_newc＝[id_new,id_c,d_newc]，然后將棧T和集合EXI設置為空，并將邊e_newc壓入棧T中、設置EXI＝{id_new}；

步驟1.6)，如果集合KN為空且棧T也為空，此時彈出的邊e_jk＝[id_j,id_k,d_jk]即為邊e_newi，在最臨近邊矩陣E中檢索出所有包含頂點id_j的邊，如果該邊的另一頂點的唯一標識不在集合EXI中，則將該邊存入集合JN中；如果JN不為空，調整集合JN中第一條邊的前兩列數據順序，使得其第1列數據為id_j、第2列數據為該邊另一頂點的唯一標識后，將該邊壓入棧T中；

遍歷棧T，獲取棧T中各條邊的第3列即其兩個頂點間的歐氏距離中第一個最大值d_bc的所在邊e_bc＝[id_b,id_c,d_bc]；如果d_bc大于新增頂點id_new和頂點id_c之間的歐式距離d_newc，d_newc∈D，則從最臨近邊矩陣E中刪除邊e_bc，并在最臨近邊矩陣E中新增邊e_newc＝[id_new,id_c,d_newc]，然后將棧T和集合EXI設置為空，并將邊e_newc壓入棧T中、設置EXI＝{id_new}；

步驟1.7)，遍歷最臨近邊矩陣E，獲得其第3列的最大值d_max；篩選出歐氏距離集合D中所有小于d_max的歐式距離，將其對應的頂點唯一標識的集合記為集合ID2，

步驟1.8)，重復步驟1.4)至步驟1.7)，直到EXI＝ID∪{id_new}或者

步驟1.9)，將{x_new1,x_new2,…x_newm,id_new}加入到X中，更新頂點數據集合X；將id_new加入到ID中，更新完成最小距離連通圖MDG[ID,E]；

步驟2)，計算聚類趨勢指數MDGCTI；

步驟2.1)，計算最臨近邊矩陣E中除第一行外每一行第三列和上一行第三列的差值，取其中的最大值dd_max在E中對應行第三列的值和對應行下一行第三列的值計算平均值，得到均值ddm_max，ddm_max即為肘閾值；

步驟2.2)，用最臨近邊矩陣E第三列D_E中小于ddm_max的值建立歐式距離集合D_ic,用最臨近邊矩陣E第三列D_E中大于ddm_max的值建立歐式距離集合D_oc；

步驟2.3)，計算出歐式距離集合D_ic、D_oc中元素的個數num_ic、num_oc；

步驟2.3.1)，如果num_ic＝num_oc＝0，MDGCTI＝-1；

步驟2.3.2)，如果num_ic或num_oc不等于0；

步驟2.3.2.1)，計算出歐式距離集合D_ic、D_oc的均值mean_ic、mean_oc；

步驟2.3.2.2)，計算出歐式距離集合D_ic、D_E的變異系數cv_ic、cv_E，如果mean_ic＝0，則cv_ic＝0；

步驟2.3.2.3)，根據以下公式計算聚類趨勢指數MDGCTI：

式中，