基于K-medoids聚類算法的多源信息數(shù)據(jù)集成算法

祝 鵬,郭艷光

(內(nèi)蒙古農(nóng)業(yè)大學(xué) 計(jì)算機(jī)技術(shù)與信息管理系,內(nèi)蒙古 包頭 014109)

隨著信息和電子網(wǎng)絡(luò)社會(huì)的不斷發(fā)展,人們生活和生產(chǎn)等各領(lǐng)域都存在各種信息,多數(shù)信息都依靠網(wǎng)絡(luò)作為獲取和分享載體,其擁有海量的信息資源,為滿足用戶的需求,根據(jù)信息的類型和功能分為不同的信息平臺(tái).但隨著日益上升的數(shù)據(jù)量以及時(shí)刻都在更新變化的信息需求,各統(tǒng)計(jì)類、計(jì)算類、儲(chǔ)存類等平臺(tái)均受到一定程度的制約.而信息數(shù)據(jù)集成算法能高效解決上述問題,可將具有多元、異構(gòu)的數(shù)據(jù)進(jìn)行統(tǒng)一化集成管理,從而高效、快速地獲取用戶所需的信息.

文獻(xiàn)[1]提出了一種基于適應(yīng)高維海量數(shù)據(jù)的并行聚類集成算法,在數(shù)據(jù)采樣階段計(jì)算每個(gè)少數(shù)類樣本的近鄰值,再生成與該值相關(guān)的多個(gè)平衡數(shù)據(jù)集,將數(shù)據(jù)經(jīng)過訓(xùn)練用于分類器上,分類后將平衡數(shù)據(jù)完成集成,該算法只對(duì)數(shù)量較少且較穩(wěn)定的數(shù)據(jù)集有用,而在數(shù)量多且難度較大的數(shù)據(jù)上進(jìn)行對(duì)比時(shí),集成效果較差,實(shí)用性不強(qiáng); 文獻(xiàn)[2]采用一種基于迭代模糊聚類算法的集成模糊分類器,該分類器在第0階段輸出被擴(kuò)充到原始空間的數(shù)據(jù),以并行方式計(jì)算存在所有空間特征的數(shù)據(jù),根據(jù)泛化原理將同特征數(shù)據(jù)集成到特定空間內(nèi),但該算法的適應(yīng)能力較差,收斂速度較低,不能很好地消化過多的數(shù)據(jù)信息,導(dǎo)致集成次數(shù)相對(duì)較高.

針對(duì)上述問題,本文基于K-medoids聚類算法對(duì)多源信息數(shù)據(jù)集成方法進(jìn)行改進(jìn).在進(jìn)行數(shù)據(jù)集成前,先采用K-medoids聚類算法分析多源信息遷移學(xué)習(xí)特點(diǎn),對(duì)數(shù)據(jù)樣本的源域和目標(biāo)域進(jìn)行判定,得出變化規(guī)律和樣本的初始權(quán)重值,解決了因關(guān)聯(lián)不足而導(dǎo)致的集成效果較差問題,然后建立一個(gè)共識(shí)函數(shù),得到兩個(gè)數(shù)據(jù)之間的交互信息,對(duì)交互信息量較高的數(shù)據(jù)進(jìn)行集成,以保證集成的準(zhǔn)確性.實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法整體過程運(yùn)算簡單,邏輯表達(dá)清晰,解決了傳統(tǒng)方法中存在的問題.

1 基于K-medoids聚類算法的多源信息遷移學(xué)習(xí)

本文集成算法采用K-medoids聚類[3]的學(xué)習(xí)框架,放寬了學(xué)習(xí)過程中易受測試與訓(xùn)練數(shù)據(jù)的約束限制[4].通過遷移學(xué)習(xí)分析數(shù)據(jù)源域與目標(biāo)域之間的關(guān)聯(lián)關(guān)系,根據(jù)關(guān)聯(lián)程度[5],對(duì)存在數(shù)據(jù)的單域或雙域進(jìn)行劃分,從而降低因判定失誤導(dǎo)致的集成失敗現(xiàn)象.

在遷移學(xué)習(xí)任務(wù)中,假設(shè)初始樣本[6]的數(shù)據(jù)空間為G2,標(biāo)記為X2∈{-1,+1}; 定義域[7]為T,該定義域T中包含少量帶有原始特征標(biāo)記的訓(xùn)練樣本集合DT及不存在原始特征標(biāo)記的樣本集合DTEOT,所有數(shù)據(jù)均遵循PT概率進(jìn)行分布.初始定義空間中存在Kn個(gè)源域SKn,各源域S1,S2,…,SKn中包含帶有原始特征標(biāo)記的數(shù)據(jù)為D1,D2,…,DKn,均遵循PD分布概率.將多源域[8]的數(shù)據(jù)通過合理利用,獲取在目標(biāo)域上的初始聚類模型為fS/D:G2→D,通過學(xué)習(xí)經(jīng)驗(yàn)逐漸聚類并降低誤差.

(1)

其中p(g,d)表示樣本分布,Ω[·]表示在數(shù)據(jù)空間Ω中每次遷移產(chǎn)生的損失期望表示經(jīng)過訓(xùn)練得到的第t次遷移學(xué)習(xí)中數(shù)據(jù)的源域SKn.采用損失估計(jì)[11]變換算法,計(jì)算該次迭代可能產(chǎn)生的經(jīng)驗(yàn)誤差,表達(dá)式為

(2)

通過式(2)判斷可知,數(shù)據(jù)源判定算法在一定程度上進(jìn)行了知識(shí)遷移,且對(duì)目標(biāo)域和源域的判定結(jié)果較準(zhǔn)確,能有效分辨二者之間存在的差異,對(duì)二者域之間的解釋能力較強(qiáng),可有效解決因關(guān)聯(lián)不足而導(dǎo)致的負(fù)遷移[13]現(xiàn)象.

2 集成算法實(shí)現(xiàn)

(3)

交互信息平均值計(jì)算公式為

(4)

其中:φNMI表示交互信息的標(biāo)準(zhǔn)值;P表示交互信息數(shù)量;φm表示交互信息的覆蓋值,φm值越大,表示包含在第m個(gè)聚類器中的信息含量越大.

根據(jù)該特點(diǎn),通過權(quán)值因子集成兩個(gè)覆蓋值較高的數(shù)據(jù),可保證集成的準(zhǔn)確性[17],計(jì)算公式為

(5)

得到用于標(biāo)準(zhǔn)化Z值的權(quán)值因子為

(6)

(7)

上述公式表明,通過聚類器得到集成結(jié)果的準(zhǔn)確率高于不使用聚類器得到的集成結(jié)果,交互信息的權(quán)值是決定集成效果的重要因素,利用該方法完成的集成效果具有一定的精準(zhǔn)性,整體流程如圖1所示.

圖1 多源數(shù)據(jù)信息集成方法流程框架Fig.1 Process framework of multi-source data information integration method

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)所需的所有訓(xùn)練數(shù)據(jù)均來自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫.在數(shù)據(jù)庫中挑選1 000個(gè)不同種類的數(shù)據(jù)樣本,采用ECE(electrical and computer engineering)軟件對(duì)所有數(shù)據(jù)樣本進(jìn)行統(tǒng)一集成.選擇文獻(xiàn)[1]提出的適應(yīng)高維海量數(shù)據(jù)的并行聚類集成算法和文獻(xiàn)[2]提出的基于迭代模糊聚類算法與本文算法進(jìn)行對(duì)比分析,驗(yàn)證本文算法的有效性.3種集成算法存在的共同點(diǎn): 所生成的聚類器數(shù)量都在1～2內(nèi),表明迭代步數(shù)的最大值為400,當(dāng)數(shù)據(jù)量不斷上升超出既定值時(shí),不會(huì)出現(xiàn)迭代停止的現(xiàn)象,在規(guī)定的迭代次數(shù)內(nèi)對(duì)比3種算法可集成的數(shù)據(jù)量.為提高實(shí)驗(yàn)結(jié)果的準(zhǔn)確性,分別在3個(gè)不同的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),對(duì)比集成效果.3個(gè)數(shù)據(jù)集的信息列于表1.

表1 不同數(shù)據(jù)集的信息

3.2 基于NMI的集成結(jié)果判定

以標(biāo)準(zhǔn)互聯(lián)網(wǎng)歸一化互信息NMI作為判定集成效果的評(píng)估準(zhǔn)則,該指標(biāo)是將信息進(jìn)行量化度量的結(jié)果,也可理解為目標(biāo)信息出現(xiàn)的概率,計(jì)算公式為

(8)

其中I(x,y)表示全部集成數(shù)據(jù),φ表示度量系數(shù).NMI值越大表示集成效果越好,NMI值越小表示集成效果越差.在3個(gè)數(shù)據(jù)集上不同算法的NMI值變化曲線分別如圖2～圖4所示.由圖2～圖4可見: 數(shù)據(jù)集Leukaemia和數(shù)據(jù)集Vehicle的NMI值變化曲線較相似,3種算法的曲線走勢均呈下降趨勢,但較緩慢,存在緩沖位置; 而數(shù)據(jù)集Ecoli則存在相反變化,3種算法曲線均存在急劇下降趨勢.這是因?yàn)閿?shù)據(jù)集Ecoli中的信息種類較繁雜,同一類別的信息不處于同一標(biāo)簽內(nèi),涉及面廣、覆蓋率大,集成的難度較高,所以該數(shù)據(jù)集(圖4)的集成結(jié)果更具代表性,更能體現(xiàn)算法的優(yōu)異程度.

圖2 在數(shù)據(jù)集Leukaemia上的NMI值變化曲線Fig.2 Change curves of NMI values on Leukaemia dataset

圖3 在數(shù)據(jù)集Vehicle上的NMI值變化曲線Fig.3 Change curves of NMI values on Vehicle dataset

由圖4可見,當(dāng)集成數(shù)量不斷增加時(shí),本文算法曲線趨于前平后降的小幅度變化趨勢; 而另外兩種算法則存在不穩(wěn)定的下降趨勢.表明在種類較繁雜且不穩(wěn)定的數(shù)據(jù)集上,本文算法最具優(yōu)勢,在只選擇少數(shù)且高質(zhì)量的數(shù)據(jù)比對(duì)時(shí),3種算法差距不明顯,但選擇數(shù)量多且難度較大的數(shù)據(jù)對(duì)比時(shí),本文算法的集成質(zhì)量較高.這是因?yàn)楸疚乃惴ㄔ趯?duì)特定的子集時(shí),采用了特征查找法,通過預(yù)先標(biāo)記的特征標(biāo)簽進(jìn)行系統(tǒng)搜索,在最短的時(shí)間內(nèi)聚類所有信息,具有靈活性和較強(qiáng)的適應(yīng)能力.

3.3 二次集成次數(shù)對(duì)比分析

由于信息的種類較多樣化,存在的干擾因素過多,因此算法能否在最少的集成次數(shù)下達(dá)到既定標(biāo)準(zhǔn),也是驗(yàn)證集成能力的重要指標(biāo).3種算法二次集成次數(shù)對(duì)比曲線如圖5所示.由圖5可見,本文算法所需的次數(shù)曲線最低,所需次數(shù)均在可承受范圍內(nèi),而另外兩種算法的二次集成次數(shù)過多,說明算法的適應(yīng)能力較差,收斂速度較低,不能很好地消化過多的數(shù)據(jù)信息.這是因?yàn)獒槍?duì)非穩(wěn)定數(shù)據(jù)集,一般存在無偏差和有限偏差兩種概念,兩種對(duì)比算法在進(jìn)行集成時(shí)忽略了外界因素導(dǎo)致的有限偏差,只考慮了信息自身可能產(chǎn)生的影響,導(dǎo)致限制較大,集成效果較差.

圖4 在數(shù)據(jù)集Ecoli上的NMI值變化曲線Fig.4 Change curves of NMI values on Ecoli dataset

圖5 3種算法二次集成次數(shù)對(duì)比曲線Fig.5 Comparison curves of secondary integration times of three algorithms

綜上所述,為實(shí)現(xiàn)多源信息數(shù)據(jù)在信息種類繁雜且數(shù)據(jù)較多的環(huán)境下高效集成,本文提出了一種基于K-medoids聚類算法的多源信息數(shù)據(jù)集成方法.先通過分析計(jì)算不同種類數(shù)據(jù)的遷移學(xué)習(xí)率幫助后續(xù)的聚類集成,能更快、更精準(zhǔn)地查找到目標(biāo)區(qū)域,并實(shí)現(xiàn)劃分; 然后對(duì)源點(diǎn)較多、較雜的數(shù)據(jù),利用K-medoids聚類算法從數(shù)據(jù)的特征域和數(shù)據(jù)的源域兩方面解決源域問題,分析二者之間的差異性,通過損失函數(shù)不斷迭代修正偏差量,直至查找到準(zhǔn)確源,實(shí)現(xiàn)高質(zhì)量集成.仿真實(shí)驗(yàn)結(jié)果表明,本文算法無論在何種環(huán)境下都能保證集成效果,適應(yīng)能力較強(qiáng)且收斂速度快,二次集成概率小,性能優(yōu)異.