不定核大間隔聚類算法*

李　森，薛　暉+1.東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京2111892.東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，南京211189

* The National Natural Science Foundation of China under Grant No. 61375057 (國家自然科學(xué)基金); the Natural Science Foundation of Jiangsu Province under Grant No. BK20131298 (江蘇省自然科學(xué)基金).

Received 2015-05,Accepted 2015-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-08-11, http://www.cnki.net/kcms/detail/11.5602.TP.20150811.1521.005.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0112-10

?

不定核大間隔聚類算法*

李森1,2，薛暉1,2+
1.東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京211189
2.東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室，南京211189

* The National Natural Science Foundation of China under Grant No. 61375057 (國家自然科學(xué)基金); the Natural Science Foundation of Jiangsu Province under Grant No. BK20131298 (江蘇省自然科學(xué)基金).

Received 2015-05,Accepted 2015-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-08-11, http://www.cnki.net/kcms/detail/11.5602.TP.20150811.1521.005.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0112-10

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

Key words: maximum margin clustering; indefinite kernel; semi-infinite program

摘要：受限于傳統(tǒng)統(tǒng)計(jì)學(xué)習(xí)理論，大多數(shù)核方法都要求核矩陣半正定，但是在很多實(shí)際問題中這樣的要求常常很難滿足，由此產(chǎn)生了不定核。近年來，研究者們提出了一系列基于不定核的分類方法，取得了很好的性能，但是關(guān)于不定核聚類方法的研究相對較少，而且現(xiàn)有的核聚類算法基本上都是基于正定核而設(shè)計(jì)的，無法或者很難處理核矩陣不定的情況。針對此問題，以大間隔聚類（maximum margin clustering，MMC）模型為基礎(chǔ)，提出了一種新的不定核大間隔聚類（indefinite kernel maximum margin clustering，IKMMC）算法。IKMMC算法旨在尋求一個正定核以逼近不定核，并將度量兩者差異性的F-范數(shù)作為一個正則化項(xiàng)嵌入到MMC框架中。首先給定樣本初始標(biāo)記，然后迭代優(yōu)化目標(biāo)函數(shù)，并將每步迭代得到的樣本預(yù)測錯誤率作為迭代終止條件。在每步迭代時，IKMMC算法進(jìn)一步將目標(biāo)函數(shù)轉(zhuǎn)化為半無限規(guī)劃（semi-infinite program，SIP）形式，并動態(tài)調(diào)整約束集進(jìn)行交替優(yōu)化。實(shí)驗(yàn)驗(yàn)證了IKMMC算法的有效性。

關(guān)鍵詞：大間隔聚類；不定核；半無限規(guī)劃

1　引言

核方法是機(jī)器學(xué)習(xí)領(lǐng)域的一種重要學(xué)習(xí)方法，其通過一個非線性映射函數(shù)將數(shù)據(jù)由低維空間映射到高維空間，以解決低維空間無法解決的分類問題。受限于傳統(tǒng)的統(tǒng)計(jì)學(xué)習(xí)理論，大多數(shù)核方法要求核函數(shù)正定，并滿足Mercer條件[1]，使得在再生核Hilbert空間（reproducing kernel Hilbert space，RKHS）[2]中內(nèi)積與核函數(shù)之間一一對應(yīng)，并導(dǎo)出凸優(yōu)化問題，進(jìn)而可獲得全局最優(yōu)解。然而，當(dāng)為了提高方法性能而在正定核方法中嵌入先驗(yàn)知識時，往往會導(dǎo)致核函數(shù)不定。而且在很多現(xiàn)實(shí)問題中，使用不定核卻能獲得比正定核更好的性能。例如，在人臉識別中，Liu在核主成分分析（kernel principal component analysis，KPCA）方法中使用了不定的分?jǐn)?shù)階多項(xiàng)式核，取得了比使用正定多項(xiàng)式核KPCA更好的識別效果[3]。

近年來，研究者們提出了一系列不定核分類算法，大致可分為3類。第一類是對不定核矩陣做譜變換。其中包括將不定核矩陣負(fù)特征值置零的Clip變換方法[4]，對負(fù)特征值取反的Flip變換方法[5]以及將所有特征值與最小負(fù)特征值的絕對值之和作為新特征值的Shift變換方法[6]。第二類是直接使用不定核矩陣。例如，Lin等人對于非正定Sigmoid核支持向量機(jī)（support vector machine，SVM）的非凸對偶形式，提出了一種序列最小化方法以尋求穩(wěn)定點(diǎn)[7]。 Haasdonk對不定核SVM給出了一個幾何解釋，并將相應(yīng)的優(yōu)化問題轉(zhuǎn)化為偽歐氏空間中兩凸包之間距離最小化問題[8]。Loosli等人將SVM拓展到Krein空間并直接對不定核矩陣進(jìn)行操作，得到了比正定核更好的效果[9]。Alabdulmohsin等人將1-范式SVM拓展到不定核情況，保證了目標(biāo)函數(shù)為凸，用不定核函數(shù)得到了較高準(zhǔn)確率[10]。第三類是將不定核矩陣K0視作某個未知正定核矩陣K的加噪形式，將不定核中的優(yōu)化問題替換為核矩陣的學(xué)習(xí)問題。Luss等人最早提出了這種學(xué)習(xí)框架，他們把K和K0的F-范數(shù)嵌入目標(biāo)函數(shù)中，將不可微的目標(biāo)函數(shù)進(jìn)行二次平滑，分別采用投影梯度和中心點(diǎn)割平面方法[11]進(jìn)行求解[12]。進(jìn)一步地，Chen等人提出了用交替優(yōu)化方法得到K的算法，將目標(biāo)函數(shù)表達(dá)為一個半無限二次約束線性規(guī)劃問題，通過迭代求解可最終收斂至一個全局最優(yōu)解[13]。Chen等人視K為K0的譜修正，將K嵌入目標(biāo)函數(shù)中，并把目標(biāo)函數(shù)表達(dá)為二階錐約束線性規(guī)劃的形式求解[14]。Gu等人將KPCA刻畫為一個核變換框架，并把不定核SVM嵌入該框架中聯(lián)合求解，從而有效保持了核替代的一致性[15]。

盡管這些不定核方法效果很好，但大都用于分類，很少能解決基于不定核方法的聚類問題。大間隔聚類（maximum margin clustering，MMC）是基于核方法的經(jīng)典聚類算法之一。Xu等人最先提出將SVM的最大化分類間隔準(zhǔn)則應(yīng)用到聚類問題中，并將基于這一準(zhǔn)則的聚類算法稱為大間隔聚類[16]。同SVM引入核方法解決數(shù)據(jù)在低維空間線性不可分問題相似，MMC也引入了核方法以求得到更好的聚類效果。為了實(shí)現(xiàn)MMC，Xu等人將其表達(dá)為一個整數(shù)規(guī)劃問題，再通過放寬約束條件將其表達(dá)為一個半定規(guī)劃問題，從而可以利用優(yōu)化包進(jìn)行優(yōu)化。由于半定規(guī)劃問題的求解復(fù)雜度較高，Zhang等人提出了基于交替優(yōu)化的iterSVR算法[17]，其思想是先用簡單的聚類算法（如k-means）給定初始類別標(biāo)記，訓(xùn)練SVR （support vector regression）得到權(quán)向量，然后通過整數(shù)規(guī)劃得到新樣本標(biāo)記，再將新標(biāo)記作為輸入，如此迭代直到算法收斂。Zhao等人進(jìn)一步提出了用割平面方法和凹凸約束規(guī)劃（constrained concave-convex procedure，CCCP）[18]優(yōu)化MMC模型的算法[19]。該算法首先將約束集置空，用CCCP優(yōu)化目標(biāo)函數(shù)，然后選擇最違反約束的條件加入約束集迭代優(yōu)化，直到算法收斂。為了提高優(yōu)化效率，Wang等人又提出了cpMMC（cutting plane MMC）算法[20]，先用CCCP將原問題分解為多個子問題，再用割平面算法優(yōu)化子問題。Zhang等人提出SKMMC（sparse kernel MMC）算法[21]，將cpMMC拓展到非線性核情況?？紤]到非凸問題只有局部最優(yōu)解以及半定規(guī)劃問題的復(fù)雜性，Li等人將樣本標(biāo)記松弛為其凸包，從而將非凸的整數(shù)規(guī)劃問題松弛為凸問題并表達(dá)為凹凸規(guī)劃的形式，通過割平面方法和多核優(yōu)化方法優(yōu)化該問題[22]。Wu等人進(jìn)一步將該方法拓展到SVR模型[23]。不同于前述方法，Gopalan等人從樣本點(diǎn)和間隔的關(guān)系出發(fā)，首先通過數(shù)據(jù)點(diǎn)在多條直線上的映射結(jié)果得到樣本點(diǎn)間的相似度，然后通過NCut進(jìn)行聚類，得到了較好的結(jié)果[24]。

雖然MMC算法的聚類效果很好，但均要求核正定。當(dāng)核不定時，MMC算法無法應(yīng)用。針對以上問題，本文以MMC為基礎(chǔ)，提出了一個新的不定核大間隔聚類（indefinite kernel maximum margin clustering，IKMMC）算法，旨在尋求一個正定核以逼近不定核，并將度量兩者差異性的F-范數(shù)作為一個正則化項(xiàng)嵌入到MMC框架中，為解決不定核聚類問題提供了一種可行思路。IKMMC算法首先給定樣本初始標(biāo)記，然后迭代優(yōu)化目標(biāo)函數(shù)，并將每次迭代時樣本預(yù)測錯誤率作為迭代終止條件。優(yōu)化目標(biāo)函數(shù)時，IKMMC算法將其轉(zhuǎn)化為半無限規(guī)劃（semi-infinite program，SIP）形式，動態(tài)調(diào)整約束集進(jìn)行交替優(yōu)化。實(shí)驗(yàn)結(jié)果表明，該模型在核矩陣不定情況下能取得較好的聚類效果。

本文組織結(jié)構(gòu)如下：第2章簡單回顧MMC模型；第3章在MMC模型的基礎(chǔ)上提出IKMMC模型，并給出該模型的具體優(yōu)化算法；第4章在不同數(shù)據(jù)集上驗(yàn)證IKMMC算法的有效性，給出與簡單譜變換不定核MMC以及基于高斯核的k-means算法的對比實(shí)驗(yàn)；最后對相關(guān)工作進(jìn)行總結(jié)。

2　大間隔聚類

當(dāng)核矩陣為對稱半正定且將樣本聚成兩類時，給定樣本X＝{x1，x2，…，xn}，MMC旨在尋找一個聚類超平面，使得聚類后不同標(biāo)記的樣本到該超平面的最小距離最大化，即尋找一個最大間隔。具體地，可以通過優(yōu)化下式得到該超平面和樣本標(biāo)記：

其中，?是非線性映射函數(shù)，將數(shù)據(jù)由原始空間映射到高維空間：xi→?(xi)，進(jìn)而使樣本可以在高維空間中聚類。式（1）中，w和b唯一確定該超平面，最后一個約束條件用來控制樣本間的平衡，防止聚類后得到的間隔過大，影響聚類效果。

由于式（1）是關(guān)于標(biāo)記y的整數(shù)規(guī)劃，其相對于二次規(guī)劃效率較低，故對式（1）進(jìn)行變換[25]：

聚類后樣本的標(biāo)記通過yi＝sign(wT?(xi)＋b)得到，由此可將整數(shù)規(guī)劃轉(zhuǎn)化為二次規(guī)劃求解。

3　不定核大間隔聚類算法

雖然MMC算法具有較好的聚類性能，但是當(dāng)核矩陣不定時，無法應(yīng)用MMC算法。因此，本文以MMC模型為基礎(chǔ)，提出了一個基于不定核的大間隔聚類模型。

3.1模型構(gòu)建

根據(jù)Mercer定理，當(dāng)核矩陣K半正定時，樣本點(diǎn)與其在Hilbert空間中的映射點(diǎn)存在如下映射：

其中，λt是K的第t個特征值；vt是λt對應(yīng)的特征向量。若K不定，樣本點(diǎn)與Hilbert空間中的點(diǎn)不再一一對應(yīng)。因此，為了在不定核情況下進(jìn)行大間隔聚類，需要找到一個“最接近”原不定核的正定核。

最簡單的方法是對不定核矩陣做譜變換，但是簡單譜變換會丟失原不定核中有用的信息，進(jìn)而影響算法的性能。因此，本文采用了正定核替換策略，將不定核矩陣K0看作某個未知正定核矩陣K的加噪形式，學(xué)習(xí)K以逼近K0，進(jìn)而提出IKMMC模型：

觀察式（3）可知，與MMC模型不同的是，IKMMC模型的目標(biāo)函數(shù)同時是K的非凸函數(shù)。樣本標(biāo)記由w、b以及K0的正定核逼近K共同確定，這增加了模型優(yōu)化的難度。圖1描述了IKMMC與其他聚類算法的關(guān)系。3.2節(jié)給出了該模型的具體優(yōu)化方法。

3.2優(yōu)化求解

IKMMC算法采取迭代優(yōu)化方法：首先隨機(jī)給樣本賦初始標(biāo)記，然后優(yōu)化式（3），將第t步的輸出標(biāo)記作為第t＋1步的輸入標(biāo)記，并將每步迭代時樣本預(yù)測的錯誤率（與輸入標(biāo)記相比）作為迭代終止條件。由此，不定核聚類問題轉(zhuǎn)變?yōu)椴欢ê朔诸悊栴}的迭代過程。下式為第t＋1步的目標(biāo)函數(shù)：

顯然，式（4）相對于w、b和K均為凸函數(shù)，因此存在一個全局最優(yōu)解。對(w，b，ξ)求對偶可得：

Fig.1 Relationship between IKMMC and other clustering algorithms圖1　IKMMC與其他聚類算法的關(guān)系描述

式（4）和式（5）都是凸二次規(guī)劃問題且它們的對偶間隙為0，因此優(yōu)化式（5）得到的解就是式（4）的最優(yōu)解。令：

易知該最優(yōu)解是由S(α，λ，γ，K)張成的超面上的一個鞍點(diǎn)，該點(diǎn)對K取極小值，對α、λ、γ取極大值。

設(shè)(α?，λ?，γ?，K?)為式（5）的最優(yōu)解。對于任意滿足式（5）約束條件的α、λ、γ、K有下式成立：

S(α，λ，γ，K?)≤S(α?，λ?，γ?，K?)≤S(α?，λ?，γ?，K)因?yàn)镾(α，λ，γ，K)是關(guān)于K的凸函數(shù)，所以有：

式（7）約束集是式（6）約束集的一個子集，隨著式（7）中約束集合逐漸增加，式（7）的最優(yōu)解逐漸逼近式（6）的最優(yōu)解。通過更新約束集，優(yōu)化式（7）可以逐步逼近“最優(yōu)解”。SIP優(yōu)化過程如圖2所示。

Fig.2 Flow chart of SIP圖2　SIP優(yōu)化流程圖

SIP優(yōu)化過程對應(yīng)IKMMC算法步驟3～步驟13。求K?以更新約束集時，有如下命題成立。

命題1給定(α，λ，γ)，K?＝S(α，λ，γ，K)，則K?可以通過如下公式得到：

其中，Z(t)＝diag(，，…，)；1n×1表示n維全1列向量；X＋＝∑imax(0，λi)xi；λi和xi分別為X的第i個特征值和特征向量。

證明S(α，λ，γ，K)可以改寫為如下形式：

在當(dāng)前(α，λ，γ)上，最優(yōu)的K?是通過優(yōu)化S(α，λ，γ，K)得到的。由于(α，λ，γ，l)已知，且||K?K0＝tr((K?K0)T(K?K0))，則S(α，λ，γ，K)與下式等價(jià)：

IKMMC算法的偽代碼如下所示，算法的計(jì)算復(fù)雜度為O(n3)。

算法1 IKMMC算法

輸入：不定核矩陣K0，懲罰因子C、ρ，類平衡參數(shù)l

輸出：w，b，K

3.3算法分析

顯然，式（7）的解是式（6）的一個近似解，有如下命題成立[13]：

命題2設(shè)(d?，α?，λ?，γ?)為式（6）的最優(yōu)解，K?為式（6）取最優(yōu)解時的K。SIP在第i步時記＝S(αi?1，λi?1，γi?1，K)，f(i)＝S(αj?1，λj?1，γj?1，)，g(i)＝di＝S (α，λ，γ，Kj)，有不等式f(i)≤ d*≤g(i)成立，且f(i)單調(diào)遞增，g(i)單調(diào)遞減。

證明由于式（7）約束集是式（6）約束集的子集，故有如下關(guān)系成立：

對式（10）兩邊關(guān)于α、λ、γ取極大值，因?yàn)槭剑?）的最優(yōu)解是一個鞍點(diǎn)，所以有下式成立：

即g(i)≥d?成立。

因此第i步求得的點(diǎn)S(αi?1，λi?1，γi?1，)位于集合Ω中，從而f(i)＝S(αj?1，λj?1，γj?1，)≤d?。

根據(jù)式（7），SIP優(yōu)化過程不停止迭代時，集合K_set都會加入，每加入一個，目標(biāo)函數(shù)值減小一次，故g(i)單調(diào)遞減。進(jìn)一步根據(jù)f(i)的定義，可知f(i)單調(diào)遞增。

由命題2可知，算法1內(nèi)層迭代過程（步驟3～步驟13）中始終有f(i)≤d?≤g(i)成立，且f(i)遞增，g(i)遞減，因此f(i)和g(i)間的間隙逐步縮小，即f(i)和g(i)逐步逼近d?。當(dāng)此間隙在有限步內(nèi)迭代到小于某個預(yù)先給定的閥值時，步驟3～步驟13收斂。在外層循環(huán)，IKMMC將樣本標(biāo)記預(yù)測的錯誤率作為迭代終止條件，實(shí)驗(yàn)中算法基本在10步以內(nèi)迭代至一個穩(wěn)定點(diǎn)。

4　實(shí)驗(yàn)與分析

給定不定核K0，對其進(jìn)行特征值分解K0＝UΛUT。將Λ負(fù)特征值置零可得Λclip，Kclip＝UΛclipUT即為Clip變換后得到的半正定核，基于該核的MMC算法記作Clip_MMC。類似地，對負(fù)特征值求絕對值可得Flip_MMC，對Λ中每個特征值加上最小特征值的絕對值得到Shift_MMC。為了檢驗(yàn)IKMMC算法的聚類效果，本文將其與上述3種譜變換MMC算法以及基于高斯核的K-means算法（KKM）在基準(zhǔn)數(shù)據(jù)集上進(jìn)行了比較。

表1給出了實(shí)驗(yàn)中使用的數(shù)據(jù)集。其中，Ionosphere、Image、Diabetis、Wdbc均是來自UCI[27]的兩類數(shù)據(jù)集。DNA數(shù)據(jù)集是一個生物數(shù)據(jù)集[28]，包含3類樣本，實(shí)驗(yàn)選擇其中樣本數(shù)目相當(dāng)?shù)膬深悢?shù)據(jù)。

Table 1 Data characteristics of benchmark datasets表1　數(shù)據(jù)集數(shù)據(jù)特征

為了得到不定核矩陣，實(shí)驗(yàn)中先用高斯核生成半正定核矩陣，然后向其中加入隨機(jī)擾動r?(E＋ET)/2，其中，E是均值為0的單位協(xié)方差矩陣，r為擾動因子，r＝0.1。核函數(shù)的參數(shù)σ、懲罰因子C以及正則化因子ρ均由交叉驗(yàn)證確定。若數(shù)據(jù)集中正負(fù)樣本數(shù)目相當(dāng)，則平衡參數(shù)l取0.03n，否則取0.3n，其中n是樣本個數(shù)。

實(shí)驗(yàn)中以聚類錯誤率和Rand Index（RI）作為評價(jià)聚類算法性能的準(zhǔn)則。

錯誤率的計(jì)算方式如下：

其中，Wk為通過聚類算法得到的樣本子集；Cj為按照樣本原始標(biāo)記得到的子集。各聚類算法在不同數(shù)據(jù)集上的錯誤率如表2所示。

Table 2 Clustering errors on various datasets表2　聚類算法在不同數(shù)據(jù)集上的錯誤率

RI計(jì)算方式如下：

其中，TP表示標(biāo)記相同被聚到同一簇的樣本個數(shù)；TN表示標(biāo)記不同被聚到不同簇的樣本個數(shù)；FP表示標(biāo)記不同被聚到同一簇的樣本個數(shù)；FN表示標(biāo)記相同被聚到不同簇的樣本個數(shù)。各算法在不同數(shù)據(jù)集上的RI值如表3所示。

Table 3 Rand Indices on various datasets表3　聚類算法在不同數(shù)據(jù)集上的RI值

Fig.3 Clustering errors with various values for σ on various datasets圖3　算法在各數(shù)據(jù)集上聚類錯誤率隨σ的變化關(guān)系

由表2可見，IKMMC算法在所有數(shù)據(jù)集上的錯誤率均低于其他對比算法。特別地，在Ionosphere數(shù)據(jù)集上，IKMMC算法的錯誤率比譜變換得到的3種MMC算法和KKM算法低8%～16%。在DNA數(shù)據(jù)集上，4種不定核MMC算法與KKM相比，錯誤率低12%以上。此外，在其他3個數(shù)據(jù)集上，IKMMC比其他3種不定核MMC算法低4%左右。由表3可見，IKMMC 在RI指標(biāo)上亦優(yōu)于其他4種算法。這說明在復(fù)雜的實(shí)際問題中，使用不定核能得到比正定核更好的性能。

圖3和圖4分別給出了各算法在不同數(shù)據(jù)集上的聚類錯誤率隨主要參數(shù)σ和C的變化關(guān)系。從圖3可以看出，5種算法錯誤率隨著σ的變化，均呈現(xiàn)一定程度的震蕩。但是在Image和Diabetis數(shù)據(jù)集上，IKMMC算法的錯誤率始終低于其他算法。在其他3個數(shù)據(jù)集上，IKMMC算法均達(dá)到了最小值。由于KKM算法與參數(shù)C無關(guān)，故圖4描述了IKMMC、Clip_MMC、Flip_MMC、Shift_MMC算法與C的變化關(guān)系。由圖4可見，各算法在不同數(shù)據(jù)集上的錯誤率整體上隨C的增大而增大。其中，在Ionosphere和DNA數(shù)據(jù)集上，IKMMC的錯誤率全面低于其他3種算法。在Diabetis、Image和Wdbc數(shù)據(jù)集上，IKMMC算法錯誤率也基本小于其他3種算法，且在C的變化區(qū)域達(dá)到了最小值。因此，基于正定核替換策略的IKMMC模型比譜變換得到的MMC模型有更好的聚類效果。

5　結(jié)束語

本文以MMC模型為基礎(chǔ)，通過向其目標(biāo)函數(shù)中嵌入度量正定核與不定核差異性的F-范數(shù)，尋求正定核以逼近不定核，提出了基于不定核的大間隔聚類模型IKMMC及其聚類算法。該算法首先給定樣本一組初始標(biāo)記，然后迭代優(yōu)化IKMMC模型，并將預(yù)測錯誤率作為判斷算法迭代終止的條件。在每步迭代時，IKMMC將目標(biāo)函數(shù)轉(zhuǎn)化為半無限規(guī)劃形式，并動態(tài)調(diào)整約束集進(jìn)行交替優(yōu)化。實(shí)驗(yàn)驗(yàn)證了IKMMC算法具有較好的聚類效果。

下一步工作可以考慮將算法進(jìn)一步拓展到多類情況，也可將單不定核的IKMMC拓展到多不定核情況以提高性能。

Fig.4 Clustering errors with various values for C on various datasets圖4　算法在各數(shù)據(jù)集上聚類錯誤率隨C的變化關(guān)系

致謝向?qū)Ρ疚墓ぷ鹘o予支持和建議的老師們表示感謝。

References:

[1] Cristianini N, Shawe-Taylor J. An introduction to support vector machines and other kernel-baesd learning methods[M]. Cambridge, UK: Cambridge University Press, 2000.

[2] Sum H. Mercer theorem for RKHS on noncompact sets[J]. Journal of Complexity, 2005, 21(3): 337-349.

[3] Liu Chengjun. Gabor-based kernel PCA with fractional power polynomial models for face recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(5): 572-581.

[4] Pekalska E, Paclik P, Duin R P W. A generalized kernel approach to dissimilarity-based classification[J]. Journal of Machine Learning Research, 2002, 2: 175-211.

[5] Kondor R I, Lafferty J D. Diffusion kernels on graphs and other discrete input structures[C]//Proceedings of the 19th International Conference on Machine Learning. San Francisco, USA: Morgan Kaufmann Publishers Inc, 2002: 315-322.

[6] Roth V, Laub J, Kawanabe M, et al. Optimal cluster preserving embedding of nonmetric proximity data[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(12): 1540-1551.

[7] Lin H T. Lin C J.Astudy on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods[EB/OL]. (2003)[2015-03-30]. http://www.csie.ntu.edu.tw/～htlin/paper/ doc/tanh.pdf.

[8] Haasdonk B. Feature space interpretation of SVMs with indefinite kernels[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(4): 482-492.

[9] Loosli G, Ong C S, Canu S. SVM in Krein spaces[R/OL]. (2013)[2015-03-30]. https://hal.archives-ouvertes.fr/hal-00869658/document.

[10] Alabdulmohsin I, Gao Xin, Zhang Xiangliang. Support vector machines with indefinite kernels[C]//Proceedings of the 6th Asian Conference on Machine Learning, Vietnam, 2014: 32-47.

[11] Grotschel M, Wakabayashi Y. A cutting plane algorithm fora clustering problem[J]. Mathematical Programming, 1989, 45(1/3): 59-96.

[12] Luss R, d'Aspremont A. Support vector machine classification with indefinite kernels[C]//Advances in Neural Information Processing Systems 21: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems, Vancouver, Canada, Dec 8-11, 2008: 953-960.

[13] Chen Jianhui, Ye Jieping. Training SVM with indefinite kernels[C]//Proceedings of the 25th International Conference on Machine Learning, Helsinki, Finland, 2008. New York, USA:ACM, 2008: 136-143.

[14] Chen Yihua, Gupta M R, Recht B. Learning kernels from indefinite similarities[C]//Proceedings of the 26th Annual International Conference on Machine Learning, Montreal, Canada, 2009. New York, USA:ACM, 2009: 145-152.

[15] Gu Suicheng, Guo Yuhong. Learning SVM classifiers with indefinite kernels[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence. Menlo Park, USA: AAAI, 2012.

[16] Xu Linli, Neufeld J, Larson B, et al. Maximum margin clustering[C]//Advances in Neural Information Processing Systems 17: Proceedings of the 18th Annual Conference on Neural Information Processing Systems, Vancouver, Canada, Dec 13-18, 2004: 1537-1544.

[17] Zhang Kai, Tsang I W, Kwok J T. Maximum margin clustering made practical[J]. IEEE Transactions on Neural Networks, 2009, 20(4): 583-596.

[18] Yuille A L, Rangarajan A. The concave-convex procedure (CCCP)[J]. Neural Computation, 2003, 15(4): 915-936.

[19] Zhao Bin, Kwok J T, Zhang Changshui. Multiple kernel clustering[C]//Proceedings of the SIAM International Conference on Data Mining, Sparks, USA, Apr 30-May 2, 2009. Philadelphia, USA: SIAM, 2009: 638-649.

[20] Wang Fei, Zhao Bin, Zhang Changshui. Linear time maximum margin clustering[J]. IEEE Transactions on Neural Networks, 2010, 21(2): 319-332.

[21] Zhang Xiaolei, Wu Ji. Linearithmic time sparse and convex maximum margin clustering[J]. IEEE Transactions on Systems, Man, and Cybernetics: Part B Cybernetics, 2012, 42(6): 1669-1692.

[22] Li Yufeng, Tsang I W, Kwok J T, et al. Tighter and convex maximum margin clustering[J]. Journal of Machine Learning Research, 2009, 5: 344-351.

[23] Wu Ji, Zhang Xiaolei. Sparse kernel maximum margin clustering[J]. Neural Network World, 2011, 21(6): 551.

[24] Gopalan R, Sankaranarayanan J. Max-margin clustering: detecting margins from projections of points on lines[C]// Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, Providence, USA, Jun 20-25, 2011. Piscataway, USA: IEEE, 2011: 2769-2776.

[25] Zhao Bin, Wang Fei, Zhang Changshui. Efficient maximum margin clustering via cutting plane algorithm[C]//Proceedings of the SIAM International Conference on Data Mining, Atlanta, USA, Apr 24-26, 2008. Philadelphia, USA: SIAM, 2008: 751-762.

[26] Hettich R, Kortanek K O. Semi-infinite programming: theory, method,andapplications[J].SIAMReview,1993,35(3):380-429.

[27] Asuncion A, Newman D. UCI machine learning repository. 2007.

[28] Rakotomamonjy A, Bach F, Canu S, et al. SimpleMKL[J]. Journal of Machine Learning Research, 2008, 9: 2491-2521.

LI Sen was born in 1989. He is an M.S. candidate at School of Computer Science and Engineering, Southeast University. His research interests include machine learning and pattern recognition, etc.

李森（1989—），男，東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，模式識別等。

XUE Hui was born in 1979. She received the Ph.D. degree in computer application technology from Nanjing University of Aeronautics and Astronautics in 2008. Now she is an associate professor and M.S. supervisor at School of Computer Science and Engineering, Southeast University, and the member of CCF. Her research interests include machine learning and pattern recognition, etc.

薛暉（1979—），女，江蘇南京人，2008年于南京航空航天大學(xué)計(jì)算機(jī)應(yīng)用專業(yè)獲得博士學(xué)位，現(xiàn)為東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院副教授、碩士生導(dǎo)師，CCF會員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，模式識別等。

Indefinite Kernel Maximum Margin Clustering Algorithm*

LI Sen1,2, XUE Hui1,2+
1. School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2. Key Laboratory of Computer Network and Information Integration, Ministry of Education, Southeast University, Nanjing 211189, China
+ Corresponding author: E-mail: hxue@seu.edu.cn

LI Sen, XUE Hui. Indefinite kernel maximum margin clustering algorithm. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：112-121.

Abstract:Limited to traditional statistical learning theory, most kernel methods require the kernel matrices to be positive semi-definite. But in many practical problems, such requirement is difficult to be satisfied and thus indefinite kernels appear. Recently, researchers have proposed many methods to solve indefinite kernel classification problems and achieved much better performance. However, the research about indefinite kernel clustering is relatively scarce. Furthermore, existing clustering methods are mainly designed based on positive definite kernels which are incapable in indefinite kernel scenarios. This paper proposes a novel method termed as indefinite kernel maximum margin clustering (IKMMC) based on the state-of-the-art maximum margin clustering (MMC) model. IKMMC aims to find a proxy positive definite kernel to approximate the original indefinite one and thus embeds a new F-norm regularizer measuring the diversity of the two kernels into the MMC model. Given a set of initial labels, IKMMC uses an iterative approach to optimize the objective function and takes the error rate of prediction as the loop-termination criteria. At each iteration, IKMMC transfers the objective function into semi-infinite program (SIP) form, and dynamically adjusts constraint set for optimizing alternately.The experimental results show the superiority of IKMMC algorithm.

文獻(xiàn)標(biāo)志碼：A

中圖分類號：TP391.4

doi:10.3778/j.issn.1673-9418.1505052