用壓縮篩選樹演算法處理成本導向多標籤分類問題

Abstract

近年來許多真實世界的應用需要好的多標籤分類演 算法,而不同的應用往往需要考慮不同的衡量標準。為 此,我們針對此需求提出更一般性的架構─成本導向多 標籤分類問題 (Cost-Sensitive Multi-Label Classification), 希望藉由在學習的過程中考慮成本資訊,來一般化這個 需求。然而,大部分現存的演算法只能專注在最佳化部 分特定的衡量標準,無法有系統的處理各種不同的標準。 在此論文中,我們提出了壓縮篩選樹演算法 (Condensed Filter Tree) 來最佳化任何不同的標準。壓縮篩選樹演算法 係由在成本導向多重分類問題 (Cost-Sensitive Multi-Class Classification) 裡著名的篩選樹演算法,藉由標籤冪集 (Label Powerset) 的轉化推導而來。我們透過特殊的樹狀 結構設計與專注在關鍵的樹節點,成功的解決指數多的 轉換類別在表現 (Representatino)、學習 (Training) 與預測 (Prediction) 中的困難。最後,在真實世界的資料上的實 驗結果顯示,比起其他已提出專注於特定衡量標準的演 算法,此論文中所提出的壓縮篩選樹在不同的衡量標準 下皆有較好的表現。

Many real-world applications call for better multi-label classification algorithms in recent years and different applications often need considering different evaluation criteria. We formalize this need with a general setup, cost-sensitive multi-label classification (CSMLC), which takes the evaluation criteria into account during the learning process. Nevertheless, most existed algorithms can only focus on optimizing a few specific evaluation criteria, and cannot systematically deal with different criteria. In this paper, we propose a novel algorithm, called condensed filter tree (CFT), for optimizing any criteria in CSMLC. CFT is derived from reducing CSMLC to the famous filter tree algorithm for cost-sensitive multi- class classification via the simple label powerset approach. We successfully cope with the difficulty of having exponentially many extend-classes within the powerset for representation, training and prediction by carefully designing the tree structure and focusing on the key nodes. Experimental results across many real-world datasets validate that the pro- posed CFT algorithm results in the better performance for many general evaluation criteria when compared with existing special- purpose algorithms.