摘要：k近鄰多標簽學習算法是多標簽學習領域經典算法之一，為處理多標簽問題提供了新思想。將PCA改進算法應用到k近鄰多標簽學習算法中，提出信息損耗率，并實現動態降維；根據PCA算法計算樣本的屬性重要度；采用屬性重要度作為權重改進距離計算方法。與已有多標簽學習算法相比，該算法各評價指標明顯優于已有算法。
關鍵詞關鍵詞：k近鄰多標簽學習算法；信息損耗率；主成分分析法；屬性重要度
中圖分類號：TP301
文獻標識碼：A文章編號文章編號：1672-7800（2016）004-0005-03
0引言
隨著大數據時代的到來，多元化、復雜性數據的產生，機器學習顯得尤為重要。多年來，單標簽理論發展逐步成熟和廣泛應用，但在現實生活中，數據樣本可能擁有多個標簽。比如：一則新聞可能會同時關于教育、科技、社會等多個標簽。多標簽學習[1]的研究主要有兩大任務：多標簽分類[2]（Multi-labelClassification，MLC）和標簽排名[3]（Labelranking，LR）。多標簽分類是通過訓練樣本訓練出分類器，輸出未知樣本對標簽集中每個集合是否相關的分類結果。標簽排名學習由訓練集得到一個分類器，輸出未知樣本對標簽集中每個標簽相關程度的排名。在某些領域，標簽分類和標簽排名同等重要。例如在新聞過濾系統中[2]，系統必須返回用戶最感興趣的新聞，同時將用戶最感興趣的新聞顯示在最上面。理想情況下，系統可以建立一個既可以排序，又對標簽進行相關判斷的方法，該任務定義為多標簽排序[4]（Multi-labelranking，MLR）。多標簽學習算法[2]主要有問題轉換法（ProblemTransformation）和算法改進（AlgorithmAdaption）兩大類。問題轉換算法主要有BR（BinaryRelevance）二元關系法、RPC（RankingbyPairwiseComparison）成對比較排序法、LP（LabelPowerset）標簽密集法等等，而算法改進包括決策樹（DecisionTree）、Boosting算法、神經網絡（NeuralNetwork）、支持向量機等等。為提高學習算法性能，在處理數據過程中往往需要對數據進行維數約簡。維數約簡算法包括特征選擇[5]和特征提取兩類，單標簽領域一些算法可以直接應用于多標簽學習，而一些算法經過改進后同樣也可以運用于多標簽學習。數據特征的選擇、維數約簡是決定數據挖掘方案的最重要部分，所以選擇適合多標簽數據集進行維數約簡的算法非常重要。
1相關工作
鄰近算法（或k近鄰）[1]（kNN，k-NearestNeighbor）分類算法是數據分類技術中最簡單的算法。張敏靈教授和周志華教授[1]成功將kNN算法運用于多標簽學習，即ML-kNN算法，成為多標簽學習算法的中的經典算法。ML-kNN算法沒有考慮屬性特征對標簽權重的影響，也未考慮標簽集對屬性特征的映射關系。有些屬性的特征值比較小，但其影響分類的決定性比較大，如果簡單采用歐式距離來計算樣本的距離就很容易增大樣本誤分類的可能性。
根據是否利用先驗知識劃分，主成分分析法屬于無監督降維學習方法。主成分分析法通過抽取樣本的主要影響因素，簡化復雜的問題。主成分分析法還被用于將高緯度數據投影到低維空間，消除數據間的冗余，提高學習算法的精度。文獻[7]通過PCA對k近鄰多標簽學習算法的改進來實現多標簽學習，提出了信息損耗率ξ和對k近鄰多標簽算法的改進。信息損耗率是衡量數據傳輸、轉換過程中的完整程度，損耗率越小證明數據信息越完整。在處理數據過程中，合理控制數據的信息損耗率非常重要。
目前，多標簽學習理論和應用都取得豐碩的成果。PCAIML-kNN算法就是在以往理論基礎上提出的。該算法主要分兩部分來改進，首先通過控制信息損耗率ξ得到樣本的動態維度，進而得到特征提取后的動態樣本；其次，樣本距離計算加入了抽取后定義權重，多標簽的評價指標優于與其它算法。該算法的主要思路是先對數據集進行維數約簡，再運用改進后的ML-kNN算法對數據集進行多標簽處理。
2PCAI算法
PCAI算法基于k近鄰多標簽算法，并將PCA算法改進后應用于多標簽學習。該改進算法的核心思想是對多標簽數據集維數約簡得到新數據，然后通過k近鄰算法、多標簽學習算法處理新數據集。與其它算法相比，該算法有效降低了多標簽數據集的維數，提高了分類精度。
2.1PCA算法
3實驗結果與分析
本實驗采用多標簽精確度（Precision）、覆蓋率（Coverage）、漢明損失（HammingLoss）、One-錯誤率（One-Error）、標簽排名（RankingLoss）等5個評價指標。5個評價指標中精確度越大越好（用“↑”表示），其余4個評價指標越小越好（用“↓”表示）。該實驗選用的算法有ML-kNN算法、PCAIML-kNN算法、FisherML-kNN算法、ReliefML-kNN算法。本實驗采用Yahoo部分數據集，選取Arts、Business、Computers、Education、Entertainment5個數據集。5個數據集評價指標如圖1～圖5所示。
從圖1可以看出，與ML-kNN方法相比，PCAML-kNN算法在分類精度上提高不大，FisherML-kNN、ReliefML-kNN算法與算法PCAML-kNN相比效果顯著。5個算法中，PCAIML-kNN算法在多標簽數據集分類精確度上明顯優于其它算法。圖2～圖5中，評價指標值越小其相應的評價指標性能越好。需注意的是，各個指標采用平均值和方差的形式，在上述4個評價指標中可以看出，上述方法在處理相同數據集時，方差差異不大，即比較穩定。從平均值來看，PCAIML-kNN與其它算法相比，在覆蓋率、漢明損失、one-錯誤率、排名損失評價指標中值最低，相比而言，算法最好。
