不定核大間隔聚類算法*

李　森，薛　暉+1.東南大學計算機科學與工程學院，南京2111892.東南大學計算機網絡和信息集成教育部重點實驗室，南京211189

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

Received 2015-05,Accepted 2015-07.

CNKI網絡優先出版：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.東南大學計算機科學與工程學院，南京211189
2.東南大學計算機網絡和信息集成教育部重點實驗室，南京211189

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

Received 2015-05,Accepted 2015-07.

CNKI網絡優先出版：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

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

關鍵詞：大間隔聚類；不定核；半無限規劃

1　引言

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

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

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

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

本文組織結構如下：第2章簡單回顧MMC模型；第3章在MMC模型的基礎上提出IKMMC模型，并給出該模型的具體優化算法；第4章在不同數據集上驗證IKMMC算法的有效性，給出與簡單譜變換不定核MMC以及基于高斯核的k-means算法的對比實驗；最后對相關工作進行總結。

2　大間隔聚類

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

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

由于式（1）是關于標記y的整數規劃，其相對于二次規劃效率較低，故對式（1）進行變換[25]：

聚類后樣本的標記通過yi＝sign(wT?(xi)＋b)得到，由此可將整數規劃轉化為二次規劃求解。

3　不定核大間隔聚類算法

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

3.1模型構建

根據Mercer定理，當核矩陣K半正定時，樣本點與其在Hilbert空間中的映射點存在如下映射：

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

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

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

3.2優化求解

IKMMC算法采取迭代優化方法：首先隨機給樣本賦初始標記，然后優化式（3），將第t步的輸出標記作為第t＋1步的輸入標記，并將每步迭代時樣本預測的錯誤率（與輸入標記相比）作為迭代終止條件。由此，不定核聚類問題轉變為不定核分類問題的迭代過程。下式為第t＋1步的目標函數：

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

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

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

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

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

S(α，λ，γ，K?)≤S(α?，λ?，γ?，K?)≤S(α?，λ?，γ?，K)因為S(α，λ，γ，K)是關于K的凸函數，所以有：

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

Fig.2 Flow chart of SIP圖2　SIP優化流程圖

SIP優化過程對應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)可以改寫為如下形式：

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

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

算法1 IKMMC算法

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

輸出：w，b，K

3.3算法分析

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

命題2設(d?，α?，λ?，γ?)為式（6）的最優解，K?為式（6）取最優解時的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)單調遞增，g(i)單調遞減。

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

對式（10）兩邊關于α、λ、γ取極大值，因為式（6）的最優解是一個鞍點，所以有下式成立：

即g(i)≥d?成立。

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

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

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

4　實驗與分析

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

表1給出了實驗中使用的數據集。其中，Ionosphere、Image、Diabetis、Wdbc均是來自UCI[27]的兩類數據集。DNA數據集是一個生物數據集[28]，包含3類樣本，實驗選擇其中樣本數目相當的兩類數據。

Table 1 Data characteristics of benchmark datasets表1　數據集數據特征

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

實驗中以聚類錯誤率和Rand Index（RI）作為評價聚類算法性能的準則。

錯誤率的計算方式如下：

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

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

RI計算方式如下：

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

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

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

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

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

5　結束語

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

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

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

致謝向對本文工作給予支持和建議的老師們表示感謝。

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—），男，東南大學計算機科學與工程學院碩士研究生，主要研究領域為機器學習，模式識別等。

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年于南京航空航天大學計算機應用專業獲得博士學位，現為東南大學計算機科學與工程學院副教授、碩士生導師，CCF會員，主要研究領域為機器學習，模式識別等。

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.

文獻標志碼：A

中圖分類號：TP391.4

doi:10.3778/j.issn.1673-9418.1505052