[發明專利]一種增量式密度峰搜索聚類方法

在審

• 申請號: 201710183749.8
• 申請日: 2017-03-24
• 公開（公告）號: CN107895165A
• 公開（公告）日: 2018-04-10
• 發明（設計）人: 洪德華;許小東
• 申請（專利權）人: 中國科學技術大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 安徽省合肥新安專利代理有限責任公司34101
• 代理人: 汪祥虬

1.一種增量式密度峰搜索聚類方法，設數據集已存放數據總數為N的歷史數據對象，每一數據對象含有特征維度為M的實數據，令數據對象的密度表為鄰居關系表為鄰居距離表為鄰居半徑為r，新增數據對象為其特征在于具體操作步驟為：

第一步：根據歐式距離測算關系式d_n＝||x-x_n||，符號||·||代表向量范數運算，依次測算新增數據對象x與數據集X中的歷史數據對象之間的歐式距離，其中令數據編號為n的第n個歷史數據對象x_n∈X與新增數據對象x之間的歐式距離為d_n，且數據編號n從1依次遞增至數據總數N；

第二步：從數據集X中構造新增數據對象x的鄰居集Q，其中鄰居集中任一數據對象與新增數據對象x之間的歐式距離d_n均應滿足鄰居集選擇條件式d_n≤r；如果鄰居集Q為空集，則跳轉至第六步；如果鄰居集Q非空，則將密度表P中數據編號對應于鄰居集Q中所有數據對象的密度值增1；

第三步：從鄰居集Q中取出一個鄰居關系尚未更新的數據對象作為當前數據對象，然后從數據集X中構造關于該數據對象的鄰居關聯集其中假設鄰居關聯集U中任一數據對象的密度為p，令鄰居集Q中當前數據對象的密度為q，其未更新之前的歷史密度為q-1，則鄰居關聯集U中任一數據對象與鄰居集Q中當前數據對象之間應滿足鄰居關聯集選擇條件式q-1≤p≤q；

第四步：如果鄰居關聯集U非空，則依歐式距離測算關系式依次測算鄰居關聯集U中所有數據對象至鄰居集Q中當前數據對象之間的距離；當此距離小于鄰居關聯集U中某數據對象對應的歷史鄰居距離時，則將鄰居集Q中當前數據對象設定為鄰居關聯集U中該數據對象的鄰居，同時更新與鄰居關聯集U中該數據對象對應的鄰居關系表R和鄰居距離表D的相應表項；如果鄰居關聯集U為空集，則返回第三步；

第五步：根據以最短距離高密度數據對象為鄰準則更新鄰居集Q中當前數據對象在鄰居關系表R和其對應的鄰居距離表D中的相應表項；重復第三步至第五步，直至鄰居集Q中所有數據對象依次被執行一遍；

第六步：將密度表P、鄰居關系表R和鄰居距離表D分別追加一個表項，然后將鄰居集Q中所有數據對象的數目作為新增數據對象x的密度添加進密度表P的相應表項中；如果鄰居集Q為空集，則記新增數據對象x的密度為1并添加進密度表P的相應表項中；接著根據以最短距離高密度數據對象為鄰準則將新增數據對象x的鄰居及其鄰居距離分別添加進鄰居關系表R和鄰居距離表D的相應表項；

第七步：從數據集X中構造密度低于新增數據對象密度的新增數據關聯集S；如果新增數據關聯集S非空，則依歐式距離測算關系式依次測算新增數據關聯集S中所有數據對象與新增數據對象x之間的距離；當該距離小于新增數據關聯集S中某數據對象對應的鄰居距離時，則將新增數據對象x設定為新增數據關聯集S中該數據對象的鄰居，同時更新與新增數據關聯集S中該數據對象對應的鄰居關系表R和鄰居距離表D的相應表項；如果新增數據關聯集S為空集或該步操作已全部完成，則將新增數據對象x添加進數據集X，同時輸出增量計算結果，然后返回等待下一個新增數據對象到達；

第八步：當用戶提出聚類查詢指令時，根據增量計算結果對數據集X中所有數據對象進行簇劃分，即依據簇頭度量關系式計算簇頭度量Γ并對其元素τn進行降序排列，其中符號表示矩陣哈達馬乘積；然后依據簇頭選擇條件式選擇簇頭度量Γ中分離度超過閾值σ的一組元素對應的數據對象作為簇頭；接下來給各個簇頭分配不同簇編號，并分別以各個簇頭作為根結點，通過遍歷鄰居關系表R將每一數據對象劃分入特定簇中，向用戶輸出聚類分析結果。