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