吳 希

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

吳 希

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

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

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

譜聚類算法概述

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

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

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

構造相似約束矩陣

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

算法1

輸入：數(shù)據(jù)x1， x2，…，xn；

輸出：相似約束矩陣A ；

1.計算每一對數(shù)據(jù)點之間的距離δij；

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

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

啟發(fā)式的約束性譜聚類一般形式

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

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

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

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

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

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

算法2

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

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

實驗分析與結論

表1　數(shù)據(jù)集描述

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

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

總結

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

圖1　數(shù)據(jù)集Iris上誤差率的比較

圖2　數(shù)據(jù)集pendigits上誤差率的比較

10.3969/j.issn.1001-8972.2015.15.023