一種基于啟發式思維的約束性譜聚類算法

吳 希

一種基于啟發式思維的約束性譜聚類算法

吳 希

本文在譜聚類算法的基礎上提出了一種基于啟發式思想的相似約束矩陣的構建方法，并利用正約束和負約束，結合半監督思想，利用先驗信息引導聚類過程，同時結合優化中的KKT條件進行聚類，數據實驗證明這種方法的誤差率較低，聚類效果較好。

隨著科學技術的發展，人類每天都在主動或被動的囤積著大量的數據，這些數據一方面演繹了我們生活中的一些變化，同時，在其背后，也蘊藏了很多有用的信息，因此，對于大量甚至海量數據的處理就成為了人們所面臨的一項主要任務。數據挖掘是指從大量數據中提取內在隱含的信息和知識的過程，當然這些數據的形態并不理想，甚至是不完全的，有噪聲的，隨機的，模糊的 。

數據挖掘中包括很多方法，其中重要的手段之一是聚類分析，目前將聚類分析應用于生物信息、金融交易、醫學影像的例子比比皆是，很多傳統的聚類算法都有了相應的發展與推廣，本文中，我們基于啟發式的思維，建立一種新的構造約束矩陣的方法，并利用優化問題中的KKT條件，對正則化譜聚類算法進行改進，提出一種新的聚類算法。

譜聚類算法概述

傳統聚類方法是在數據的基礎上所提出的，容易陷入局部最優，即若數據滿足假設條件，則會有較準確的聚類結果，反之，效果則不理想。為了能在任意的樣本空間上進行聚類，并使其收斂于全局最優解，提出了譜聚類算法。譜聚類算法是基于圖論理論的基礎上提出的，算法的核心是確定圖G=（V， E）的相似矩陣，矩陣中的元素一般定義為：

其中δij是點xi和xj之間的歐氏距離，σ是一常數，習慣上定義Aii=0。

構造矩陣時，參數σ的選擇是十分重要的，不同于以往直接估計的方法，下面我們引入一個新的參數m，基于啟發式的思維，提出一種確定σ的方法。

構造相似約束矩陣

算法的構造思想是首先計算數據間的距離，然后對距離進行排序，計算相鄰兩距離之差，若最大，則參數m確定，這樣能夠保證相鄰的數據點有較大的隸屬度。算法步驟如下：

算法1

輸入：數據x1， x2，…，xn；

輸出：相似約束矩陣A ；

1.計算每一對數據點之間的距離δij；

2.將距離升序排列，計算相鄰數據點間的距離之差；

3.由max｛δ′j+1-δ′j｝確定參數m ；

啟發式的約束性譜聚類一般形式

半監督學習是近年來數據挖掘中提出的一種新的學習方法，它將數據中存在的有限的先驗信息加入到算法中，算法能借助這些信息得到更準確的結果。這里，對已知的先驗信息進行如下的限制：

定義一個限制矩陣Qn×n，Qn×n中包含已知的先驗信息：

同時定義分類指示向量f∈｛-1，+1｝n，則聚類時若體現先驗信息的價值，應滿足

事實上，為了更好的解決問題，只要限制fTQf≥α即可。

將此式引入到正則化譜聚類算法中，在優化問題的KKT條件基礎上，建立如下算法。

輸入：矩陣A 、Q 以及參數α（其中A 、Q的定義如上所示，α由用戶指定）；

算法2

輸出：向量f*（f*中的分量代表對應數據的分類結果）；

3.計算Lv=μv 的特征值和特征向量；

實驗分析與結論

表1　數據集描述

在人工數據集上，新算法的誤差率ER=0，在真實數據集上，圖1和圖2給出了本文算法與傳統KKM算法的對比。

綜合以上兩組實驗可以看到，本文算法具有良好的聚類效果。

總結

聚類算法是數據挖掘中的重要算法之一，近年來，在醫學、商業等很多方面都得到了廣泛的應用，其中譜聚類算法由于其良好的收斂性及聚類效果，使其成為了聚類算法中的使用較頻繁的一種算法。本文從啟發式思想入手，提出了一種新的構造相似約束矩陣的方法，同時結合KKT條件和半監督方法，對正則化譜聚類進行了改進，并取得了較好的實驗結果。

圖1　數據集Iris上誤差率的比較

圖2　數據集pendigits上誤差率的比較

10.3969/j.issn.1001-8972.2015.15.023