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

在審

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

本發明公開了一種基于動態聚類趨勢分析的增量聚類數據挖掘方法，首先針對動態增量數據生成最小距離連通圖，然后以最小距離連通圖為基礎，用肘閾值分割出簇間和簇內的邊，再綜合數量、均值和變異系數統計量，最后動態計算數據序列的聚類趨勢指數。本發明是一種非抽樣的適用于批量增量DBSCAN的聚類趨勢分析方法，應用于增量聚類數據挖掘系統之中，實現了非定量數據的增量聚類，進一步提高了聚類的可信度以及運行效率。

技術領域

本發明涉及信息技術領域下的數據聚類分析領域，尤其涉及一種基于動態聚類趨勢分析的增量聚類數據挖掘方法。

背景技術

目前在很多的應用領域如商務智能、圖像模式識別、WEB搜索、氣象預報、生物醫藥等都產生了海量的數據需要做數據挖掘的分析來找出其中尚未被發現的規律和現象，而聚類則是數據挖掘領域的一個重要研究領域，它通過對無類別標簽數據間的性質(如距離、密度、分布等)進行無監督學習，從而將數據劃分成多個簇，并使得簇內的數據具有高相似性，而簇間的數據則相似性低。聚類趨勢分析是聚類的前期預處理步驟，其意義在于確定數據是否具備可聚類性，及其可聚類性的強弱，以便于在此基礎上判斷是否有繼續進行聚類操作的必要性以及聚類結果的可信程度，這對于必然會得到一個聚類結果的各種聚類算法來說不僅能節省計算成本(尤其是大數據集的計算成本)，而且也可以作為聚類的一個先驗指標。

考慮到數據生成是具有動態特性的，也就是新增數據會不斷加入進數據序列，因此聚類為適應這種數據特性而出現了增量DBSACN以及更進一步的批量增量DBSCAN的算法，但是這些算法都忽視了聚類趨勢分析的重要性，所以只能實現定量數據(單個數據或固定量多個數據)的增量聚類，而導致了可能會生成無意義的聚類結果，造成聚類可信程度下降以及計算成本的浪費。因此，利用聚類趨勢分析進一步提高動態數據的增量聚類可信度以及運行效率是值得研究的一個方向。

現有的聚類趨勢分析研究主要分為三個方面：基于統計檢驗的方法，以Hopkins、Cow-Lewis、T-平方、Elberhardt統計量為主要代表；基于圖論的方法，以IC聚類趨勢指數為代表；基于可視化分析的方法，以VAT、sVAT、bigVAT、SpecVAT、cSpecVAT和GMMMVS-VAT 為代表。這些聚類趨勢分析算法存在以下兩點問題而均不適用于動態增量數據的聚類。

1、抽樣導致的聚類趨勢指標不穩定以及片面性

Hopkins統計量需要隨機均勻抽樣，因此指標穩定性差，尤其是在高維度稀疏數據集的情況下，Cow-Lewis雖然高維空間檢測有優勢，但是有時結果片面不穩定，T-平方和Elberhardt在實踐中效果相對較好，但是抽樣窗口在高維度空間中的設置難度很大，容易導致指標不穩定。

2、對增量數據序列的不適應性

抽樣技術應用于遞增數據序列需要每增加一次數據就重復進行一次抽樣，這樣無法充分利用增量數據的動態特性。圖論方法構造K部完全圖需要數據完備，因此也不適合應用在增量數據序列上。可視化分析方法早期的VAT、sVAT和bigVAT效率低耗時長且只適用于相異度矩陣是方陣的情況，近年提出的SpecVAT、cSpecVAT、GMMMVS-VAT方法雖然提高了適用范圍和準確性，但是由于使用到了譜方法(需要數據一次性到齊)并且需要確定特征向量的選取個數，因此算法復雜耗時更久，也不適用于動態遞增數據序列。

發明內容

本發明所要解決的技術問題是針對背景技術中所涉及到的缺陷，提供一種基于動態聚類趨勢分析的增量聚類數據挖掘方法。

本發明為解決上述技術問題采用以下技術方案：

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