《基於算法選擇的聚類統一框架研究》是鐘才明為項目負責人，寧波大學為依託單位的面上項目。
基本介紹
- 中文名：基於算法選擇的聚類統一框架研究
- 項目類別：面上項目
- 項目負責人：鐘才明
- 依託單位：寧波大學
項目摘要,結題摘要,
聚類分析是數據挖掘、模式識別、機器學習等研究領域對數據進行分析的重要工具之一。目前文獻中各類聚類算法層出不窮，但通常一個算法只適合處理某類（或某幾類）數據集，且用戶對擬分析的數據並不具有先驗知識，這導致實際套用中用戶難以選擇相對適合的聚類算法。研究者試圖用多目標最佳化、集成學習等方法解決之，雖然這些方法在一定程度上提高了聚類方法的普適性，但仍存在方法複雜、穩定性差等缺點。本項目擬用算法選擇的方法解決該問題。其思路為：1）構建經典聚類算法空間與典型數據集空間；2）建立數據集空間到算法空間的映射；3）定義數據集之間的相似性測度，並根據該測度將輸入數據集分類，從而完成聚類算法的自動選擇。其中最關鍵的科學問題是定義面向聚類算法的數據集之間的相似性測度。本項目的研究不僅僅為解決聚類算法的選擇問題，還可以推廣套用到分類算法的選擇，並力爭將聚類分析的框架成功套用到基因表達數據的處理。
1.項目背景 聚類分析是一個病態問題。提高算法普適性的方法有聚類集成與多目標最佳化。聚類集成的精確度依賴於初始聚類的質量，而多目標最佳化的聚類算法迄今也只有兩個目標函式的最佳化（緊湊性及連線性），且即使這兩個目標函式同時作用也不能處理所有數據集。本項目則試圖從數據集的相似性度量入手，對給定數據集自動選擇聚類算法。 2.主要研究內容 1）基於數據內在結構的數據集相似性度量 聚類算法的選擇框架包含典型數據集空間、經典聚類算法空間及數據集相似性度量準則。其中，典型數據集空間是典型聚類問題集合；經典聚類算法空間是典型聚類問題較適合的聚類算法；數據集相似性度量則是數據集的空間變換、特徵提取及相似性準則設計。 2）聚類集成關聯矩陣 數據集的相似性度量需要進行空間變換，聚類集成是一個較好的選擇。傳統的聚類集成關聯矩陣存在缺陷，本項目研究的主要研究內容之一是改進該矩陣。 3）最小生成樹快速算法 最小生成樹在一定程度上可以刻畫數據集的骨架，但其算法複雜度不適合用於大規模數據。那么，最小生成樹的快速算法是另一個研究內容。 3.重要結果 1）數據集關於聚類分析的相似性可從兩方面度量：基於離散化與歸一化的數據集變換的度量；基於K-means聚類集成的穩定性度量。 2）同一基類內，數據的同質性可不同；不同基類，數據的同質性也可不同。 3）快速近似最小生成樹算法的計算複雜度可達O(N^1.5)。 4.關鍵數據 1）當離散與歸一化後的數據集的相似性、基於K-means聚類集成穩定性的相似性權值分別為0.6與0.4時，算法推薦的精度最高（>=80%）。 2）關聯矩陣分別在數據點的層級及基類的層級進行改進，相應的聚類結果在16個測試數據上排名第一。 3）快速近似最小生成樹算法對低維數據邊的平均錯誤率為2%，權值的平均錯誤率為3.5%；對高維數據邊的平均錯誤率為18%，權值的平均錯誤率為3%。 5.科學意義 本項目的研究表明數據集從整體上具有面向聚類分析的結構特徵，這為聚類分析指明了一個有別於傳統聚類算法的研究方向，即聚類算法的自動選擇。實驗數據表明該方向是可行的，當然算法選擇的精確度還待提高，還需要挖掘數據集關於聚類相似性的更多有效特徵。
