A k‐Nearest Neighbor Based Algorithm for Multi‐label Classification Min Ling Zhang , Zhi Min‐Ling Zhang , Zhi‐Hua Hua Zhou Intn'l Conf. on Granular Computing (GrC), 2005 2005, pp. 718‐721 (Oct.06, 2014, 加瀬担当) 718 721 (O 06 2014 加瀬担当) Abstract • マルチラベル分類 – 各データが複数ラベル所持 – 所持ラベル数不定 • ML‐kNN ML kNN (Multi‐Label k‐Nearest Neighbor) (Multi Label k Nearest Neighbor) – kNNに基づく手軽な方法 1 テストデータに近いｋ個の学習データ特定 1. テストデ タに近いｋ個の学習デ タ特定 2. そのｋ個よりラベル決定（MAP原理を用いる） • 実験結果（バイオ関連データにより） – 他方法と比べ謙遜無し Introduction • マルチラベル分類の必要性（例） ルチラベル分類の必要性（例） – テキスト分類 • 各テキストが複数トピック所持 – バイオインフォマティックス • 各たんぱく質が複数機能所持 • マルチラベル問題の定義 – 学習データが複数ラベル所持 学習デ タが複数ラ ル所持 – テストデータに複数ラベル付与 ※所持ラ ル数は不定 ※所持ラベル数は不定 Introduction • マルチラベル分類簡易方法 ベ 分類簡 方法 – 各クラスに対する２値分類問題に分解 各クラ 対する 値分類問題 分解 • ラベル間関係無考慮（単純すぎる） • 従来提案方法 – Multi‐label decision trees – Multi‐label kernel method etc. • 未解決問題 – 手軽なマルチラベル分類方法なし 2 Multi Label Learning 2. Multi‐Label Learning • マルチラベル分類は文書分類の必要性から 生まれた – 各文書が複数トピックを同時所持 関連研究 • BoosTexter [Schapire, Singer] – AdaBoostに基づく 基 く – 予測が難しいものに重み付け • ベイズ的方法[McCallum] ベイズ的方法[M C ll ] – 混合分布仮定，EM推定 • カーネル法使用方法[Elisseeff and Weston] – Ranking Lossとマージンに基づく Ranking Lossとマージンに基づく • 決定木[Clare and King] – C4.5に基づく 関連研究 • PMM1, PMM2 [Ueda and Saito] – 各語はあるカテゴリに属していると仮定 各語はあるカテ リ 属し る 仮定 • 決定木 [Comite et al.] – AdaBoostに基づき決定木学習 d に基づき決定木学習 • [Boutell et al.] – シーン分類に適用 – 各クラスに対する２値分類問題へ分解 評価基準 • 記号表記 – • ｄ次元空間の事例 – • Q種類のラベル集合 Q種類 ラ 集合 – • 学習データ集合 (Y : ラベル集合) – • マルチラベル分類器 – • 順位付け関数 （例． <l1のほうが高順位>） – • 分類器を順位付け関数で表現 （t(x)：閾値） 評価基準 • Hamming Loss（値↓；性能↑） 値 性能 Δ ： 対称差 一致しないラベル数の平均 致しないラベル数の平均 • One‐error（値↓：性能↑） 判定結果がランキング１位でなかった場合の平均回数 評価基準 • Coverage（値↓：性能↑） 値 性能 実際の所持ラベル中で 一番ランキングの低いも のの上位にいくつの持 ちうるラベルがあるかの 平均 • Ranking Loss（値↓：性能↑） Ranking Loss（値↓：性能↑） 実際の所持ラベルより 非所持ラベルのランキ ングが高いものの組み 合わせ数とその全組み 合わせ数の比の平均 評価基準 • Average Precision（値↑：性能↑） 値 性能 所持ラベル数により重み付け 所持ラベル中の上位ラベル個数 / 総ラベル中の上位ラベル個数 / 総ラベル中の上位ラベル個数 3 ML kNN 3. ML‐kNN • ： 事例xのカテゴリベクトル 事例 ゴ ベ –例 例. <1, 0, 0, 1> → １と４番目のラベル所持 , , , → 番目 ラ ル所持 • • : カテゴリベクトル要素 カテゴリベクトル要素 : ｘに性質が近いデータ集合 3 ML kNN 3. ML‐kNN • Membership counting vector – 各ラベル所持の近いデータ件数ベクトル 各ラ ル所持 近 デ タ件数 ク ル – 例.N(x)中(“政治”：２件“経済”：３件“国際”：１件) → C = <2, 3, 1> C = <2 3 1> 3 ML kNN 3. ML‐kNN • • ：テストデータtがラベルl所持 デ タ が ベ 所持 ：テストデ タtがラベルl非所持 ：テストデータtがラベルl非所持 • ：N(ｔ)中にラベルl所持データがｊ件 3 ML kNN 3. ML‐kNN • カテゴリベクトル推定 ゴ ベ 推定 ｔ近所にｌ所持データがC件の時， 近所 所持 件 時， ｔはラベルｌを所持するかしないか？ ベイズの定理より・・・ それぞれ推定 3 ML kNN 3. ML‐kNN • (1)to(3)： 計算 (2) (ｌ所持学習データ件数 /全件数) をラプラス補正 プ 補 • (4)to(14)： (4)t (14) 計算 (6)to(7) 初期化 (9) ｘiに近いデータｋ内のｌ所持件数計算 (10) 自信がｌを所持している (13) ｌを所持しある件数の近いデータがｌを所持 3 ML kNN 3. ML‐kNN • (15)to(19)：ラベル推定 (18) カテゴリベクトル (19) 確率値ベクトル 4 Experiments 4. Experiments A.Elisseeff , J.Weston(2002)使用データに基づく 使 デ タ 基づく • • • • • Yeast gene functional data 学習データ：1500 テストデータ：917 データ次元: デ タ次元: 103 103 クラス種類: 14 平均付与ラベル数: 4.2±1.6 4 Experiments 4. Experiments 変化なし 提案手法 k=7が最良 比較手法 kNNの性能はRank‐SVMに匹敵 5 Conclusion 5. Conclusion • 手軽なマルチラベル分類手法提案 軽な ベ 分類 法提案 • バイオインフォマティックスデータより実験 • 他の手法に匹敵するという結果
© Copyright 2024 ExpyDoc
