基于K-medoids聚類算法的多源信息數據集成算法

祝 鵬,郭艷光

(內蒙古農業大學 計算機技術與信息管理系,內蒙古 包頭 014109)

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

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

針對上述問題,本文基于K-medoids聚類算法對多源信息數據集成方法進行改進.在進行數據集成前,先采用K-medoids聚類算法分析多源信息遷移學習特點,對數據樣本的源域和目標域進行判定,得出變化規律和樣本的初始權重值,解決了因關聯不足而導致的集成效果較差問題,然后建立一個共識函數,得到兩個數據之間的交互信息,對交互信息量較高的數據進行集成,以保證集成的準確性.實驗結果驗證了本文算法整體過程運算簡單,邏輯表達清晰,解決了傳統方法中存在的問題.

1 基于K-medoids聚類算法的多源信息遷移學習

本文集成算法采用K-medoids聚類[3]的學習框架,放寬了學習過程中易受測試與訓練數據的約束限制[4].通過遷移學習分析數據源域與目標域之間的關聯關系,根據關聯程度[5],對存在數據的單域或雙域進行劃分,從而降低因判定失誤導致的集成失敗現象.

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

(1)

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

(2)

通過式(2)判斷可知,數據源判定算法在一定程度上進行了知識遷移,且對目標域和源域的判定結果較準確,能有效分辨二者之間存在的差異,對二者域之間的解釋能力較強,可有效解決因關聯不足而導致的負遷移[13]現象.

2 集成算法實現

(3)

交互信息平均值計算公式為

(4)

其中:φNMI表示交互信息的標準值;P表示交互信息數量;φm表示交互信息的覆蓋值,φm值越大,表示包含在第m個聚類器中的信息含量越大.

根據該特點,通過權值因子集成兩個覆蓋值較高的數據,可保證集成的準確性[17],計算公式為

(5)

得到用于標準化Z值的權值因子為

(6)

(7)

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

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

3 仿真實驗

3.1 實驗設置

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

表1 不同數據集的信息

3.2 基于NMI的集成結果判定

以標準互聯網歸一化互信息NMI作為判定集成效果的評估準則,該指標是將信息進行量化度量的結果,也可理解為目標信息出現的概率,計算公式為

(8)

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

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

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

由圖4可見,當集成數量不斷增加時,本文算法曲線趨于前平后降的小幅度變化趨勢; 而另外兩種算法則存在不穩定的下降趨勢.表明在種類較繁雜且不穩定的數據集上,本文算法最具優勢,在只選擇少數且高質量的數據比對時,3種算法差距不明顯,但選擇數量多且難度較大的數據對比時,本文算法的集成質量較高.這是因為本文算法在對特定的子集時,采用了特征查找法,通過預先標記的特征標簽進行系統搜索,在最短的時間內聚類所有信息,具有靈活性和較強的適應能力.

3.3 二次集成次數對比分析

由于信息的種類較多樣化,存在的干擾因素過多,因此算法能否在最少的集成次數下達到既定標準,也是驗證集成能力的重要指標.3種算法二次集成次數對比曲線如圖5所示.由圖5可見,本文算法所需的次數曲線最低,所需次數均在可承受范圍內,而另外兩種算法的二次集成次數過多,說明算法的適應能力較差,收斂速度較低,不能很好地消化過多的數據信息.這是因為針對非穩定數據集,一般存在無偏差和有限偏差兩種概念,兩種對比算法在進行集成時忽略了外界因素導致的有限偏差,只考慮了信息自身可能產生的影響,導致限制較大,集成效果較差.

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

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

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