融合螢火蟲方法的多標簽懶惰學習算法

程玉勝 錢坤 王一賓 趙大衛

摘 要：已有的多標簽懶惰學習算法（IMLLA）在利用近鄰標簽時因僅考慮了近鄰標簽相關性信息，而忽略相似度的影響，這可能會使算法的魯棒性有所降低。針對這個問題，引入螢火蟲方法，將相似度信息與標簽信息相結合，提出一種融合螢火蟲方法的多標簽懶惰學習算法（FFMLLA）。首先，利用Minkowski距離來度量樣本間相似度，從而找到近鄰點;然后，結合標簽近鄰點和螢火蟲方法對標簽計數向量進行改進;最后，使用奇異值分解（SVD）與核極限學習機（ELM）進行線性分類。該算法同時考慮了標簽信息與相似度信息從而提高了魯棒性。實驗結果表明，所提算法較其他的多標簽學習算法有一定優勢，并使用統計假設檢驗與穩定性分析進一步說明所提出算法的合理性與有效性。

關鍵詞：多標簽學習;螢火蟲方法;標簽相關性;多標簽懶惰學習算法;極限學習機

中圖分類號：TP181

文獻標志碼：A

Abstract： The existing Improved Multilabel Lazy Learning Approach （IMLLA） has the problem that the influence of similarity information is ignored with only the neighbor label correlation information considered when the neighbor labels were used， which may reduce the robustness of the approach. To solve this problem， with firefly method introduced and the combination of similarity information with label information， a Multilabel Lazy Learning Approach based on FireFly method （FFMLLA） was proposed. Firstly， Minkowski distance was used to measure the similarity between samples to find the neighbor point. Secondly， the label count vector was improved by combining the neighbor point and firefly method. Finally， Singular Value Decomposition （SVD） and kernel Extreme Learning Machine （ELM） were used to realize linear classification. The robustness of the approach was improved due to considering both label information and similarity information. The experimental results demonstrate that the proposed approach improves the classification performance to a great extent compared to other multilabel learning approaches. And the statistical hypothesis testing and stability analysis are used to further illustrate the rationality and effectiveness of the proposed approach.

英文關鍵詞Key words： multilabel learning; firefly method; label correlation; Improved Multilabel Lazy Learning Approach （IMLLA）; Extreme Learning Machine （ELM）

0 引言

多標簽學習[1]是一種應用非常廣泛的學習范式，是機器學習研究的重要熱點之一。傳統的單標簽學習，每個對象只與單個標簽相關聯;然而，真實世界中的對象往往具有多義性，比如一篇文章可能屬于軍事、體育、運動等多個主題[2]。

多標簽學習作為處理具有豐富語義真實世界對象的學習框架之一，且其研究成果已經廣泛應用到文本分類[3]、基因工程[4]、圖像識別[5-6]、Web數據挖掘[7]和視頻自動標注[8]等多個領域。對此許多學者提出了針對多標簽分類的學習算法，例如BR（Binary Relevance）算法、LP（Label Power）算法[9]等，它們通過增加分類器個數或者標簽的種類來解決多標簽問題，但在一定程度上影響了分類器效率。經典的MLKNN（MultiLabel K Nearest Neighbors）算法[10]利用最大化后驗概率（Maximum A Posteriori）來解決多標簽學習預測問題，雖提升了分類器的性能，卻增加了其計算的復雜度。

此外，現實世界中各樣本所含標簽并不相互獨立，存在相關關系，然而目前絕大多數多標簽學習算法未充分考慮其標簽相關性。因此，充分利用標簽之間的相關性信息，對構建強泛化性能的多標簽分類學習算法具有重要意義[11]。

而針對標簽間的相關性，許多學者提出了相關算法，取得了不錯的效果。例如，RankSVM（Ranking Support Vector Machine）算法[12]采用最大間隔策略以適應多標簽學習，采用類似BR策略構建SVM（Support Vector Machine）多標簽分類器，但其時間消耗較大。由于極限學習機（Extreme Learning Machine， ELM）[13]訓練速度快，MLRKELM（MultiLabel algorithm of Regression Kernel Extreme Learning Machine）算法[14]使用回歸模式的核ELM，縮短了算法的運行時間。MLASRKELM（MLRKELM with Association Rules）算法[14]在MLRKELM算法的基礎上引入了關聯規則，保留了標簽之間的信息。針對標簽之間的相關性，張敏靈[15]在MLKNN算法基礎上提出一種新型的多標簽懶惰學習算法（Improved Multilabel Lazy Learning Approach， IMLLA）。IMLLA利用近鄰的標簽信息構建一個標記計數向量來進行分類， 此算法在構建標簽計數向量時使用了近鄰標簽信息，認為近鄰的標簽具有相同的重要性。然而，近鄰與樣本間的相似度越大，此近鄰的標簽越重要， IMLLA因未考慮近鄰相似度信息所以其泛化性有所降低。

在上述研究成果上，對于樣本分布問題，本文在IMLLA的基礎上引入螢火蟲方法[16-17]。螢火蟲方法作為模仿自然界中螢火蟲發光行為而構造出的元啟發式算法，具有操作簡單、易于并行處理、魯棒性強等特點。故利用螢火蟲方法將近鄰的標簽信息與近鄰的相似度信息相融合，以提高算法的魯棒性，而提出一種融合螢火蟲方法的多標簽懶惰學習算法（Multilabel Lazy Learning Approach based on FireFly method， FFMLLA）。本文通過螢火蟲方法根據相似度來計算樣本與近鄰間的吸引度，吸引度越大則該近鄰的標簽越重要。然后將吸引度作為權重與標簽信息相結合，對IMLLA中的標簽計數向量進行重構。由于Huang等提出的極限學習機算法[13]具有訓練速度快、泛化能力強等優點，所以在使用線性分類器進行分類時，引入ELM進行權重求解。此外，還使用了奇異值分解（Singular Value Decomposition， SVD）求解權重。為了驗證本文算法的有效性，本文將FFMLLA與標準IMLLA，以及其他經典的多標簽算法在多個公開數據集上進行實驗對比。實驗結果表明，本文算法較其他對比算法具有一定優勢。

1 理論介紹

1.1 多標簽學習

多標簽學習是針對現實生活中普遍存在的多義性對象而提出的一種學習框架。在這個框架之下，樣本由多個特征和多個標簽構成，學習的目標是將未知的實例對應更多正確的標簽。在單實例多標簽學習中，假設X={x1，x2，…，xn}T∈Rn*d表示有n個樣本且每個樣本的特征數為d，Y={1，2，…，Q}表示可能的概念構成的集合。T={（x1，Y1），（x2，Y2），…，（xm，Ym）}（xi∈X，Yi∈Y）表示訓練集，多標簽學習的目標就是得到映射關系f：X→{-1，1}Q，并對標簽未知而特征已知的樣本進行標簽預測。

1.2 IMLLA

MLKNN是一種經典的多標簽分類算法，它先獲取近鄰樣本的標簽信息，再通過“最大化后驗概率”的方式推理未見實例的標簽集合， 但它未充分考察標簽之間的相關性?；诖藛栴}，張敏靈提出一種新型的多標簽懶惰學習算法IMLLA。IMLLA首先將測試樣本在訓練集中找出k個近鄰及其k個近鄰的標記信息，然后根據k個近鄰的標記信息生成各標簽計數向量，并提交給已訓練的分類器進行標簽預測。

4 結語

本文針對基于k近鄰的多標簽相關性算法未考慮樣本分布問題進行了研究，運用螢火蟲方法的思想將相似度信息與近鄰標簽信息進行融合。螢火蟲方法是源于模擬自然界螢火蟲在晚上的群聚活動的自然現象而提出的，其計算效率高、魯棒性強，能夠很好地將相似度信息與標簽信息融合。本文算法在重構標簽計數向量后分別使用了奇異值分解與核極限學習機進行權重求解，再進行線性分類。實驗結果表明了本文提出的FFMLLA算法具有不錯的效果和較好的穩定性。

雖然將相似度信息與近鄰標簽信息相結合的方法一定程度上提升了模型的分類精度，但與預期效果之間還存在一定差距，因此如何從近鄰空間提取出比相似度信息更為有效的信息來輔助分類器進行分類是今后研究的重點。

參考文獻 （References）

[1] ??? GIBAJA E， VENTURA S. A tutorial on multilabel learning[J]. ACM Computing Surveys， 2015，47（3）：1-38.

[2] ??? 何志芬， 楊明， 劉會東. 多標記分類和標記相關性的聯合學習[J]. 軟件學報， 2014， 25（9）：1967-1981. （HE Z F， YANG M， LIU H D. Joint learning of multilabel classification and label correlations[J]. Journal of Software， 2014， 25（9）：1967-1981.）

[3] ??? LIU J， CHANG W， WU Y， et al. Deep learning for extreme multilabel text classification[C]// Proceedings of the 40th International ACM SIGIR Conference on Research & Development in Information Retrieval. New York： ACM， 2017：115-124.

[4] ??? KORDMAHALLEH M M， HOMAIFAR A， DUKKA B K C. Hierarchical multilabel gene function prediction using adaptive mutation in crowding niching[C]// Proceedings of the 13th IEEE International Conference on BioInformatics and BioEngineering. Piscataway， NJ： IEEE， 2013：1-6.

[5] ??? ZHU X， LI X， ZHANG S. Blockrow sparse multiview multilabel learning for image classification[J]. IEEE Transactions on Cybernetics， 2016， 46（2）：450.

[6] ??? WANG Z， CHEN T， LI G， et al. Multilabel image recognition by recurrently discovering attentional regions[C]// Proceedings of the 2017 IEEE International Conference on Computer Vision. Washington， DC： IEEE Computer Society， 2017：464-472.

[7] ??? OZONAT K M， YOUNG D E. Towards a universal marketplace over the Web： statistical multilabel classification of service provider forms with simulated annealing[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009：1295-1304.

[8] ??? HOU S， ZHOU S， CHEN L， et al. Multilabel learning with label relevance in advertising video[J]. Neurocomputing， 2016， 171（C）：932-948.

[9] ??? BOUTELL M R， LUO J， SHEN X， et al. Learning multilabel scene classification [J]. Pattern Recognition， 2004， 37（9）：1757-1771.

[10] ?? ZHANG M， ZHOU Z. MLKNN： a lazy learning approach to multilabel learning[J]. Pattern Recognition， 2007， 40（7）：2038-2048.

[11] ?? LEE J， KIM H， KIM N R， et al. An approach for multilabel classification by directed acyclic graph with label correlation maximization[J]. Information Sciences， 2016， 351（C）：101-114.

[12] ?? ELISSEEFF A E， WESTON J. A kernel method for multilabelled classification[C]// Proceedings of the 14th International Conference on Neural Information Processing Systems： Natural and Synthetic. Cambridge， MA： MIT Press， 2002： 681-687.

[13] ?? HUANG G， ZHU Q， SIEW C K. Extreme learning machine： theory and applications[J]. Neurocomputing， 2006， 70（1/2/3）：489-501.

[14] ?? 王一賓， 程玉勝， 何月，等. 回歸核極限學習機的多標記學習算法[J]. 模式識別與人工智能， 2018， 31（5）：419-430. （WANG Y B， CHENG Y S， HE Y， et al. Multilabel learning algorithm of regression kernel extreme learning machine[J]. Pattern Recognition and Artificial Intelligence， 2018， 31（5）： 419-430.）

[15] ?? 張敏靈. 一種新型多標記懶惰學習算法[J]. 計算機研究與發展， 2012， 49（11）：2271-2282. （ZHANG M L. An improved multilabel lazy learning approach[J]. Journal of Computer Research and Development， 2012， 49（11）：2271-2282.）

[16] ?? YANG X， HE X. Firefly algorithm： recent advances and applications[J]. International Journal of Swarm Intelligence， 2013， 1（1）：36-50.

[17] ?? HIDALGOPANIAGUA A， MIDUEL A V， JOAQUIN F， et al. Solving the multiobjective path planning problem in mobile robotics with a fireflybased approach[J]. Soft Computing， 2017， 21（4）：1-16.

[18] ?? LEI Y， ZHAO D， CAI H B. Prediction of lengthofday using extreme learning machine[J]. Geodesy and Geodynamics， 2015， 6（2）：151-159.

[19] ?? WANG Z， XIN J， TIAN S， et al. Distributed and weighted extreme learning machine for imbalanced big data learning[J]. Tsinghua Science and Technology， 2017， 22（2）：160-173.

[20] ?? LUO F F， GUO W Z， YU Y L， et al. A multilabel classification algorithm based on kernel extreme learning machine[J]. Neurocomputing， 2017， 260： 313-320.

[21] ?? 楊明極， 馬池， 王婭， 等. 一種改進Kmeans 聚類的FCMM 算法[J/OL]. 計算機應用研究， 2019， 36（7）[2018-04-12]. http：//www.arocmag.com/article/02201907006.html.（YANG M J， MA C， WANG Y， et al. Algorithm named FCMM to improve Kmeans clustering algorithm[J/OL].Application Research of Computers， 2019， 36（7）[2018-04-12]. http：//www.arocmag.com/article/02201907006.html.）

[22] ?? WANG H， WANG W， ZHOU X， et al. Firefly algorithm with neighborhood attraction[J]. Information Sciences， 2017， 382/383：374-387.

[23] ?? 程美英， 倪志偉， 朱旭輝. 螢火蟲優化算法理論研究綜述[J]. 計算機科學， 2015， 42（4）：19-24.（CHENG M Y， NI Z W， ZHU X H. Overview on glowworm swarm optimization or firefly algorithm[J]. Computer Science， 2015， 42（4）：19-24.）

[24] ?? ZHANG M L， ZHOU Z H. A Review on multilabel learning algorithms[J]. IEEE Transactions on Knowledge & Data Engineering， 2014， 26（8）：1819-1837.

[25] ?? DEMSAR J. Statistical comparisons of classifiers over multiple data sets[J]. Journal of Machine Learning Research， 2006， 7（1）：1-30.

[26] ?? ZHANG M， WU L. Lift： Multilabel learning with labelspecific features[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2015， 37（1）： 107-120.

[27] ?? LIN Y， LI Y， WANG C， et al. Attribute reduction for multilabel learning with fuzzy rough set[J]. KnowledgeBased Systems， 2018，152：51-56.