摘要：信息技術(shù)的發(fā)展催生了海量數(shù)據(jù)。聚類有助于發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在聯(lián)系,從中挖掘有價(jià)值的信息。在對數(shù)據(jù)進(jìn)行分析時(shí),容易獲得一些關(guān)于數(shù)據(jù)的背景知識(shí),使用這些有限的先驗(yàn)信息指導(dǎo)聚類,可以顯著改善聚類的結(jié)果?；陔[馬爾可夫隨機(jī)場(Hidden Markov Random Fields,HMRF)的半監(jiān)督聚類使用成對約束作為監(jiān)督信息,雖然在很多應(yīng)用場景中有較好的聚類效果,但是其時(shí)間和空間復(fù)雜度很高,無法滿足大規(guī)模數(shù)據(jù)處理的需要。針對該問題,文中首先分析了HMRF半監(jiān)督聚類與核k-means的數(shù)學(xué)聯(lián)系,使用矩陣的跡將兩者的目標(biāo)函數(shù)統(tǒng)一起來;然后,為了降低HMRF半監(jiān)督聚類的復(fù)雜度,提出HMRF半監(jiān)督近似核k-means算法(HMRF semi-supervised Approximate Kernel K-Means,HMRF-AKKM),通過采樣構(gòu)造近似核矩陣,使用近似核k-means優(yōu)化聚類的目標(biāo)函數(shù);最后,在基準(zhǔn)數(shù)據(jù)集上將HMRF-AKKM算法與相關(guān)的聚類算法進(jìn)行對比,分析不同算法在實(shí)驗(yàn)中的聚類表現(xiàn)。實(shí)驗(yàn)結(jié)果表明,在相同的聚類任務(wù)上,HMRF-AKKM算法與原始的HMRF半監(jiān)督聚類具有類似的聚類質(zhì)量,但是HMRF-AKKM算法的聚類時(shí)間更短,說明HMRF-AKKM算法繼承了HMRF半監(jiān)督聚類與近似核k-means的優(yōu)點(diǎn)。該算法一方面可以充分利用成對約束信息改善聚類質(zhì)量,另一方面通過采樣和矩陣近似提高了聚類效率,而且聚類質(zhì)量和聚類效率可以通過調(diào)節(jié)采樣比例和成對約束數(shù)量來平衡。因此,所提出的HMRF-AKKM算法具有良好的可擴(kuò)展性,適合處理大規(guī)模非線性數(shù)據(jù)的聚類問題。