1631127
.
Nonnegative Matrix Factorization(NMF) NMF
1990 2001
Orthogonal Nonnegatively Penalized
Matrix Factorization ONP-MF ONP-MF
ONP-MF L2,1
Robust-Locally-invariant-ONP-MF
平 成
29
年 度 修 士 論 文
ロ バ ス ト 性 及 び 幾 何 的 性 質 を 考 慮 し た
直 交 制 約 付 き 非 負 値 行 列 分 解 に 関 す る 検 討
電 気 通 信 大 学 大 学 院
情 報・ネ ッ ト ワ ー ク 工 学 専 攻
電 子 情 報 学 プ ロ グ ラ ム
学 籍 番 号
: 1631127
藤 田 隼 輔
指 導 教 員
笠 井 裕 之 准 教 授
森 田 啓 義 教 授
平 成
30
年
1
月
29
日
目 次
第 1 章 序 論 5 1.1 背 景 . . . 5 1.2 目 的 . . . 5 1.3 問 題 点 . . . . 6 1.4 構 成 . . . 6 第 2 章 関 連 研 究 7 2.1 概 要 の 説 明 . . . 7 2.1.1 式 の 表 記 . . . 7 2.1.2 フ ロ ベ ニ ウ ス ノ ル ム . . . 7 2.1.3 L2,1ノ ル ム . . . 7 2.1.4 ク ラ ス タ リ ン グ の 次 元 縮 約 . . . 8 2.1.5 特 異 値 分 解 (SVD) . . . 8 2.1.6 勾 配 法 . . . . 8 2.1.7 直 線 探 索 . . . 9 2.1.8 ぺ ナ ル テ ィ 法 . . . 9 2.1.9 拡 張 ラ グ ラ ン ジ ュ 法 . . . 9 2.1.10 双 対 定 理 . . . 10 2.1.11 極 分 解 . . . 102.2 非 負 値 行 列 分 解 (Nonnegative Matrix Factorization:NMF) . . . 11
2.2.1 乗 法 的 更 新 則 . . . 11
2.2.2 ク ラ ス タ リ ン グ へ の 応 用 法 . . . 12
2.3 NMF の 拡 張 方 式 . . . 13
2.3.1 Orthogonal Nonnegative Matrix Factorization(ONMF) . . . . 15
2.3.2 Robust Nonnegative Matrix Factorization(RNMF) . . . 16
2.3.4 Orthogonal Nonnegatively Penalized
Matrix Factorization(ONP-MF) . . . 18
2.4 手 法 の 比 較 . . . 21
第 3 章 提 案 手 法 22 3.1 Robust Locally ONP-MF(Rbust-Li-ONP-MF) . . . 22
3.2 分 解 行 列 と ラ グ ラ ン ジ ュ 乗 数 の 更 新 . . . 23 3.2.1 U 更 新 . . . 23 3.2.2 V 更 新 . . . 23 3.2.3 Λ 更 新 . . . 24 第 4 章 評 価 実 験 25 4.1 対 象 デ ー タ セ ッ ト . . . 25 4.2 実 験 条 件 . . . 25 4.3 評 価 指 標 . . . 27 第 5 章 実 験 結 果 29 第 6 章 結 論 39
図 目 次
2.1 NMF ク ラ ス タ リ ン グ . . . 12 2.2 関 連 度 例 . . . 13 2.3 NMF モ デ ル と ア ル ゴ リ ズ ム の カ テ ゴ リ [1] . . . 15 5.1 精 度 評 価 図 (µ=0.01,p=5,noise=0.05) . . . 36 5.2 精 度 評 価 図 (µ=0.01,p=10,noise=0.1) . . . 36 5.3 精 度 評 価 図 (µ=0.01,p=5,noise=0.05) . . . 37 5.4 精 度 評 価 図 (µ=0.1,p=10,noise=0.05) . . . 37 5.5 精 度 評 価 図 (µ=0.1,p=20,noise=0.05) . . . 38表 目 次
2.1 主 問 題 と 双 対 問 題 . . . 10 2.2 手 法 の 比 較 . . . 21 4.1 実 験 デ ー タ セ ッ ト . . . 25 5.1 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=5，noise level=0.05) . . . 30 5.2 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=10，noise level=0.05) . . . 30 5.3 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=15，noise level=0.05) . . . 31 5.4 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=20，noise level=0.05) . . . 31 5.5 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=5，noise level=0.075) . . . 32 5.6 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=10，noise level=0.075) . . . 32 5.7 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=15，noise level=0.075) . . . 33 5.8 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=20，noise level=0.075) . . . 33 5.9 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=5，noise level=0.1) . . . 34 5.10 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=10，noise level=0.1) . . . 34 5.11 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=15，noise level=0.1) . . . 35 5.12 ク ラ ス タ リ ン グ 実 験 結 果 (p-num=20，noise level=0.1) . . . 35第
1
章 序論
1.1
背 景
情 報 化 社 会 の 現 代 ，イ ン タ ー ネ ッ ト を 利 用 し て 映 像 ，画 像 ，文 書 等 様 々 な デ ー タ や 信 号 が 取 得 さ れ る ．取 得 さ れ た 信 号 は 様 々 な 要 因 に よ り ，ノ イ ズ ，外 れ 値 ，デ ー タ 欠 損 が 発 生 す る 場 合 が あ る ．そ の よ う な 信 号 や デ ー タ を 効 率 よ く 処 理 す る た め に は ，高 い ロ バ ス ト 性 を 持 ち ，さ ら に 精 度 の 高 い ク ラ ス タ リ ン グ が 必 要 と さ れ る ．1.2
目 的
取 得 さ れ た 信 号 は ，行 列 で 表 現 す る こ と が 可 能 で あ り ，そ の 要 素 を 非 負 値 と 仮 定 し て も 多 く の 場 合 不 都 合 を 生 じ な い も の で あ る ．非 負 値 の 値 を 持 つ 行 列 を 解 析 す る 一 手 法 と し て ，非 負 値 行 列 因 子 分 解 [Nonnegative Matrix Factorization (以 後 NMF と 記 述 す る) ] が あ る [1]．こ の 手 法 は ，NMF は 1990 年 代 に 画 像 処 理 の 技 術 の 一 旦 と し て 研 究 さ れ て き た 手 法 で あ り ， 2001 年 [2] に 乗 法 的 更 新 則 に よ っ て 実 現 す る ア ル ゴ リ ズ ム が 発 表 さ れ ，現 在 も そ の 応 用 の 可 能 性 か ら 研 究 さ れ て い る 手 法 で あ る ．応 用 の 一 例 と し て ク ラ ス タ リ ン グ が あ り ，様 々 な 制 約 等 を 与 え る こ と で ，そ れ に 応 じ た 性 能 を 得 る こ と が で き る 手 法 で あ る ．ま た ，NMF の ク ラ ス タ リ ン グ は ， 次 元 縮 約 [3] を 利 用 し た も の で あ る た め ，大 規 模 な デ ー タ の 処 理 も 行 う こ と が 可 能 で あ る ．本 研 究 で は ，NMF の 性 質 を 利 用 し ，各 々 の 問 題 点 の 解 決 の た め の 関 連 手 法 の 特 徴 を 取 り 入 れ た Robust-Li-ONP-MF を 提 案 し ， そ の 特 徴 を 示 す か の 検 討 で あ る ．検 討 の 結 果 ，高 い 分 類 性 能 を 示 す こ と が で き れ ば ，ノ イ ズ や 外 れ 値 が 含 ま れ る 大 規 模 な デ ー タ や 信 号 に 関 し て も ，効 率 よ く 処 理 す る こ と が 可 能 と な る と 考 え ら れ る ．1.3
問 題 点
NMF は 直 交 制 約 を 付 加 し た Orthogonal NMF (ONMF) が あ る ．直 交 制 約 を 付 加 す る こ と で k-means と 同 等 の ク ラ ス タ リ ン グ 性 能 を 持 つ よ う に な る ．こ れ は ，非 負 値 制 約 を 満 た し な が ら 漸 近 的 に 直 交 制 約 を 満 た す よ う に 更 新 を 行 う も の で あ る ． ONMF は 非 負 値 を 満 た す 更 新 に よ っ て 局 所 解 に 収 束 す る 場 合 が あ る こ と ，収 束 値 が 初 期 値 の 影 響 を 受 け る と い う 問 題 点 が あ る ．そ れ ら を 解 決 す る 手 法 と し て ，Orthogonal Nonnegative Penalized Matrix Factorization (ONP-MF) が あ る ．ONP-MF は ONMF の 目 的 関 数 を 拡 張 ラ グ ラ ン ジ ュ 法 に よ っ て 定 義 さ れ た も の で あ り ，直 交 制 約 を 満 た し な が ら 漸 近 的 に 非 負 値 を 満 た す も の で あ る ．ま た ，初 期 値 を 乱 数 生 成 で は な く ，Singular Value Decomposition (SVD) に よ っ て 一 意 に 設 定 す る も の で あ る ． ONP-MF の 問 題 点 と し て ，ロ バ ス ト 性 が 乏 し い ，つ ま り ，ノ イ ズ や 外 れ 値 デ ー タ の 分 類 精 度 が 低 い こ と ，幾 何 学 的 な 情 報 の 欠 如 と い う 問 題 点 が あ る ．こ れ ら の 問 題 点 は ク ラ ス タ リ ン グ を す る 際 に 精 度 の 低 下 を も た ら す 原 因 と な る ． そ こ で ，以 上 に 述 べ た 問 題 解 決 の た め ，本 研 究 で は ONP-MF の 拡 張 を 行 う ．拡 張 の 内 容 と し て ，ONP-MF に ロ バ ス ト 性 を 持 た せ る こ と ，デ ー タ の 幾 何 学 的 な 構 造 を 保 存 を 行 う ．1.4
構 成
本 稿 の 構 成 を 以 下 に 示 す ． 2 章 で は ，関 連 研 究 に つ い て 紹 介 す る ．3 章 で は ，関 連 研 究 の 特 徴 を 取 り 入 れ た 提 案 手 法 に つ い て 説 明 す る ．4 章 で は ，提 案 手 法 に つ い て の 精 度 評 価 実 験 に つ い て 述 べ る ．最 後 に 5 章 で ま と め に つ い て 述 べ る ．第
2
章 関連研究
2.1
概 要 の 説 明
は じ め に 関 連 研 究 を 説 明 す る 上 で の ，表 記 や 語 句 等 に 概 要 に つ い て 述 べ る ．2.1.1
式 の 表 記
本 稿 で は ，行 列 を A の よ う に 太 字 の 大 文 字 表 記 を す る ．ま た ，ベ ク ト ル の 表 記 は a の よ う に 太 字 の 小 文 字 表 記 を す る ．!は ア ダ マ ー ル 積 ，÷ は elementwise division を 表 す ．A ≥ 0 は 行 列 が 非 負 値 で あ る こ と を 示 し て い る ．subject to は 制 約 条 件 ，A ∈ Rm×kは 行 列 A が m 行 k 列 で あ る こ と を 示 し て い る ．2.1.2
フ ロ ベ ニ ウ ス ノ ル ム
行 列 の 大 き さ を 表 す 量 の 一 つ で あ る ．A = [a1, . . . , aj, . . . , an] 場 合 ，フ ロ ベ ニ ウ ス ノ ル ム は 式 (2.1) の よ う に 定 義 さ れ る ． ∥A∥F = " # # $ n % i,j a2i,j (2.1) ま た ，フ ロ ベ ニ ウ ス ノ ル ム に は ，式 (2.2) の よ う に ，ト レ ー ス 行 列 と し て 表 現 す る こ と が で き る ． ∥A∥2 F = tr(AAT) = tr(ATA) (2.2)2.1.3
L
2,1ノ ル ム
L2,1ノ ル ム は サ ブ ベ ク ト ル ご と に L2ノ ル ム を 計 算 し ，そ の 総 和 を と っ た も の で あ る ．フ ロ ベ ニ ウ ス ノ ル ム と 違 い ，二 乗 誤 差 を 行 わ な い ノ ル ムで あ る ．式 (2.3) の よ う に 定 義 さ れ る ．NMF を こ の ノ ル ム を 用 い て 目 的 関 数 を 定 義 す る こ と で ，ロ バ ス ト 性 を 持 つ NMF が 提 案 さ れ て い る ．2.3.2 で 取 り 扱 う ． ∥A∥2.1 = n % i=1 ∥ai∥ (2.3)
2.1.4
ク ラ ス タ リ ン グ の 次 元 縮 約
ク ラ ス タ リ ン グ に は 以 下 の よ う な 課 題 が 存 在 す る ． • 高 次 元 に な る こ と で ベ ク ト ル 間 距 離 が 離 れ て い く • 本 質 的 に ク ラ ス タ リ ン グ は 距 離 の 近 い も の を ま と め る • 高 次 元 に な る ほ ど 妥 当 な 結 果 を 得 る こ と が 難 し く な る 次 元 縮 約 [3] を 用 い る こ と で 以 下 の よ う な 課 題 を 解 決 す る こ と が 可 能 で あ る ． • 対 処 法 と し て 次 元 縮 約 を 行 う • 高 次 元 の ベ ク ト ル 間 の 位 置 関 係 を で き る だ け 保 存 • よ り 低 次 元 の ベ ク ト ル に 変 換 す る 処 理2.1.5
特 異 値 分 解
(SVD)
特 異 値 分 解 [Singular Value Decomposition (SVD) ][4] は A ∈ Rm×nの 任 意 の 行 列 に 対 し て ，Rm×m，Rn×nの 直 交 行 列 と m × n の 対 角 行 列 内 積 で 表 現 さ れ る ．式 (2.4) で 表 現 さ れ る ．
A = U× S × V (2.4)
S の 非 対 角 成 分 は 0 で あ り ，対 角 成 分 は ，降 順 と な っ て い る ．
• f:目 的 関 数 ，x:初 期 解 ，次 解:ˆx，α0:初 期 の ス テ ッ プ 幅 ˆ x = ˆx− α0∇f(x) (2.5) • ス テ ッ プ 幅 は f(ˆx) < f(x) と な る よ う に 選 ぶ • xtが 1 次 の 必 要 条 件 を 満 た す ま で 繰 り 返 し 行 い 最 適 解 を 求 め る
2.1.7
直 線 探 索
直 線 探 索 [9] は ，連 続 最 適 化 問 題 に 置 い て ，目 的 関 数 を 求 め る た め の 手 法 の 一 つ で あ る ．現 在 の 近 似 解 x か ら 降 下 す る 方 向 d だ け 移 動 し た 点 x + αd が 最 小 と な る よ う な α を 求 め る 手 法 で あ る ．2.1.8
ぺ ナ ル テ ィ 法
ペ ナ ル テ ィ 法 [9] は ，制 約 条 件 を 破 っ た 時 に 目 的 関 数 値 に ペ ナ ル テ ィ を 加 え る こ と に よ っ て ，制 約 条 件 を 目 的 関 数 に 取 り 込 み ，制 約 な し 問 題 と し て 解 く 手 法 で あ る ．制 約 条 件 を 破 っ た 場 合 に は ，そ の 度 合 い に 応 じ て ペ ナ ル テ ィ を 課 す よ う な 値 を 与 え る ．2.1.9
拡 張 ラ グ ラ ン ジ ュ 法
拡 張 ラ グ ラ ン ジ ュ 法 [10] は 制 約 あ り の 最 適 化 問 題 の 局 所 最 適 解 を 数 値 的 に 求 め る 計 算 ア ル ゴ リ ズ ム の 一 つ で あ る ．ラ グ ラ ン ジ ュ 未 定 乗 数 法 と ペ ナ ル テ ィ 法 を 組 み 合 わ せ た も の で あ る ．式 (2.6) で 表 現 さ れ る ． • λ:ラ グ ラ ン ジ ュ 乗 数 • ρ:二 次 ペ ナ ル テ ィ パ ラ メ ー タ • ρ > 0 L(x, λ) = f(x) + m % j=1 λjgj(x) + ρ 2 m % j=1 {gj(x)}2 (2.6)2.1.10
双 対 定 理
定 式 化 さ れ た 線 形 計 画 問 題 に は ，表 裏 の 関 係 に あ る 線 形 計 画 問 題 が 存 在 し ，表 に 当 た る 問 題 を 主 問 題 ，裏 に あ た る 問 題 を 双 対 問 題 [9] と い う ． 主 問 題 が 最 適 解 を 持 つ 場 合 ，双 対 問 題 も 最 適 解 を 持 ち ，主 問 題 に お け る 最 小 値 (z) と 双 対 問 題 に お け る 最 大 値 (w) は 等 し く な る ．ま た ，双 対 問 題 の そ の ま た 双 対 問 題 は 主 問 題 と 等 し い と い う 性 質 を 持 つ 定 理 ． 表 2.1: 主 問 題 と 双 対 問 題 目 的 関 数 制 約 条 件 主 問 題 z = cTx を 最 小 化 Ax = b, x≥ 0 双 対 問 題 w = bTy を 最 大 化 ATy ≤ c2.1.11
極 分 解
極 分 解 [11] は 任 意 の 実 正 方 行 列 M は 直 交 行 列 U と 半 正 定 値 行 列 P に 分 解 す る 手 法 で あ る ．そ れ ぞ れ の 行 列 に つ い て 以 下 に 示 す ． M = UP (2.7) • 実 正 方 行 列 実 数 を 成 分 に と る 正 方 行 列 • 半 正 定 値 行 列 n× n の 実 対 象 行 列 M が 以 下 の 条 件 を 一 つ を 満 た す 行 列 ⅰ 全 て の n 次 元 実 ベ ク ト ル x に 対 し て 二 次 形 式 xTMx が 非 負 ⅱ M の 固 有 値 は 全 て 非 負 ⅲ あ る 実 正 方 行 列 X が 存 在 し ，M = XTX と 表 す こ と が で き る ⅳ M の 主 小 行 列 式 が 全 て 非 負2.2
非 負 値 行 列 分 解
(Nonnegative Matrix
Factor-ization:NMF)
NMF[2] は 非 負 信 号 か ら 構 成 さ れ る 入 力 行 列 X∈ Rm×nを ，ラ ン ク k の 2 つ の 非 負 の 行 列 U ∈ Rm×k, V∈ Rk×nに 分 解 す る 問 題 で あ る ．U は 辞 書 行 列 ，V は 係 数 行 列 と 呼 ば れ る ．NMF を ク ラ ス タ リ ン グ に 用 い る 場 合 は 係 数 行 列 V を 用 い て 行 う ．目 的 関 数 を 式 (2.8) に 示 す ． • X ∈ Rm×n, U∈ Rm×k, V∈ Rk×n min U∈Rm×k,V∈Rk×n ∥X − UV∥ 2 F (2.8) subject to U ≥ 0, V ≥ 0 NMF は 非 負 値 と い う 制 約 以 外 に 制 約 を 与 え た り ，緩 和 さ せ る こ と で ，そ れ に 応 じ た 能 力 を 持 た せ る こ と が で き る 手 法 で あ る [12]．1.3 で 述 べ た 問 題 解 決 の た め ，幾 ら か の 関 連 研 究 の 特 徴 に 着 目 し た 2 章 で は こ れ に つ い て 述 べ る ．2.2.1
乗 法 的 更 新 則
値 の 収 束 法 と し て ，NIPS2001 に お い て ，非 負 制 約 を 満 た し な が ら 乗 法 的 更 新 則 (Multiplicative Update) に よ り 実 現 す る ア ル ゴ リ ズ ム が Lee ら に よ り 提 案 さ れ て い る ．NMF の U 及 び V の 乗 法 的 更 新 則 を 式 (2.9) ， (2.10) に 示 す ． • X ∈ Rm×n, U∈ Rm×k, V∈ Rk×n • ÷ は elementwise division • !は ア ダ マ ー ル 積 U← U! XVUVVTT (2.9) V← V! UUTTX UV (2.10) 式 (2.9) ， (2.10) を 条 件 を 満 た す ま で 繰 り 返 し 反 復 さ せ る こ と で ，最 適 な 値 に 収 束 さ せ る ．2.2.2
ク ラ ス タ リ ン グ へ の 応 用 法
NMF は 次 元 縮 約 を 利 用 し た ク ラ ス タ リ ン グ 手 法 で あ り ，係 数 行 列 V を 用 い る [3]．辞 書 行 列 V の i 番 目 の 行 ベ ク ト ル が 元 の デ ー タ X の i 番 目 の 列 ベ ク ト ル を 縮 約 し た 結 果 と な っ て い る ．こ れ は ，縮 約 後 の 各 々 の 軸 が ク ラ ス タ と な る ト ピ ッ ク を 表 現 し て い る ．つ ま り ，辞 書 行 列 V の k 列 目 の 要 素 の 値 が ，k 番 目 の ト ピ ッ ク と の 関 連 度 の 大 き さ を 表 し て い る ．よ っ て ，i 番 目 の ト ピ ッ ク の ク ラ ス タ 番 号 は 式 (2.11) の よ う に 定 義 さ れ る [13]． こ の よ う に ，NMF は 次 元 縮 約 を 用 い た ク ラ ス タ リ ン グ で あ る た め ，大 規 模 な デ ー タ の ク ラ ス タ リ ン グ も 可 能 な 手 法 で あ る ．イ メ ー ジ を 図 2.1，2.2 に 示 す ． arg max h vih (2.11) 図 2.1: NMF ク ラ ス タ リ ン グ図 2.2: 関 連 度 例
2.3
NMF
の 拡 張 方 式
NMF は 様 々 な 応 用 研 究 が 行 わ れ て い る ．カ テ ゴ リ の 図 を 図 2.3 に 示 す ． 現 在 存 在 す る NMF は 以 下 の 4 つ の カ テ ゴ リ に 分 け る こ と が で き る [1]． • Basic NMF (BNMF) :非 負 値 制 約 の み の NMF • Constrained NMF (CNMF) :正 則 化 の た め に い く つ か の 制 約 の あ る NMF • Structured NMF (SNMF) :通 常 の 因 子 分 解 を 変 更 し た NMF • Generalized NMF (GNMF) :広 義 的 に 従 来 の デ ー タ 型 や 因 子 モ デ ル を 打 ち 破 っ て い る NMF 更 に 4 つ の カ テ ゴ リ か ら い く つ か の サ ブ ク ラ ス に も 分 類 さ れ る ． CNMF は 以 下 の 4 つ の サ ブ ク ラ ス に 分 類 さ れ る ． • Sparse NMF (SPNMF) :ス パ ー ス 制 約 を 課 し た NMF • Orthogonal NMF (ONMF) :直 交 制 約 を 課 し た NMF • Discriminant NMF (DNMF) :分 類 と 判 別 の た め の 情 報 を 含 ん だ NMF • NMF on manifold (MNMF) :局 所 的 に ト ポ ロ ジ カ ル な 特 性 を 保 っ て い る NMFSNMF は 以 下 の 3 つ の サ ブ ク ラ ス に 分 類 さ れ る ．
• Weighed NMF (WNMF) :各 成 分 の 相 対 的 重 要 度 の 違 い に よ っ て 重 み 付 け す る NMF
• Conventional NMF (CVNMF) :時 間-周 波 数 領 域 で の 因 子 分 解 を 考 慮 す る NMF
• Nonnegative Matrix Tri-Factorization (NNTF) :デ ー タ 行 列 を 3 つ に 因 子 分 解 す る NMF
GNMF は 以 下 の 4 つ の サ ブ ク ラ ス に 分 類 さ れ る ．
• Semi- NMF:特 定 の 因 子 行 列 に 制 約 を 緩 和 し た NMF
• Nonnegative Tensor Factorization (NTF) :行 列 形 式 の デ ー タ を 高 次 元 の テ ン ソ ル に 一 般 化 す る 手 法
• Nonnegative Matrix-Set Factorization (NMSF) :デ ー タ セ ッ ト を 行 列 か ら 行 列 の セ ッ ト に 拡 張 す る NMF
• NMF on manifold (KNMF) :非 線 形 モ デ ル の NMF
こ こ で 挙 げ た 手 法 の う ち ，本 稿 で 取 り 上 げ た 問 題 点 解 決 の た め ，い く つ か の 手 法 に つ い て 説 明 す る ．
図 2.3: NMF モ デ ル と ア ル ゴ リ ズ ム の カ テ ゴ リ [1]
2.3.1
Orthogonal Nonnegative Matrix Factorization(ONMF)
ONMF[14] は NMF の V に 直 行 制 約 を 付 与 し た も の で あ る ．NMF よ り 優 位 な 精 度 結 果 が 得 ら れ て い る 手 法 で あ る ．NMF と 同 様 に ，非 負 値 を 満 た し な が ら 乗 法 的 更 新 則 に よ っ て 実 現 さ れ る ．目 的 関 数 を 式 (2.12) に 示 す ． k は 近 似 さ れ る ラ ン ク で あ る ． • X ∈ Rm×n, U∈ Rm×k, V∈ Rk×n min U∈Rm×k,V∈Rk×n ∥X − UV∥ 2 F (2.12) subject to U≥ 0, V ≥ 0, VVT = I k 係 数 行 列 V に 直 交 制 約 を 与 え る こ と で ，必 然 的 に 各 列 に 一 つ だ け 非 負 値 要 素 を 有 す る ス パ ー ス な 行 列 と な る ．ス パ ー ス 性 が さ ら に 高 ま る た め ， 帰 属 度 が 集 約 し ，統 計 的 独 立 性 が 高 ま る た め ，行 列 分 解 の 一 意 性 を 向 上 さ せ る ．ま た ，副 次 的 効 果 と し て ，辞 書 行 列 U の 持 つ 特 徴 の 情 報 が 増 え る [15]．こ の よ う な 制 約 は ，辞 書 行 列 や 係 数 行 列 の 過 学 習 を 防 ぐ 役 割 も 果 た す ．制 約 を 敢 え て 両 辺 に 与 え な い こ と で ，用 途 に 応 じ た 柔 軟 な ク ラ ス タ リ ン グ が 可 能 と な る ．そ こ で ，ク ラ ス タ リ ン グ で 用 い る V に の み 制 約 を 与 え て い る ．
2.3.2
Robust Nonnegative Matrix Factorization(RNMF)
RNMF[16] は 高 次 元 か つ ノ イ ズ を 扱 う こ と が で き る NMF で あ る ．目 的 関 数 を 式 (2.13) に 示 す ．
• X ∈ Rm×n, U∈ Rm×k, V∈ Rk×n
• ∥A∥2.1 =&ni=1∥ai∥ と 定 義 さ れ る ．
min U∈Rm×k,V∈Rk×n ∥X − UV∥2,1 (2.13) subject to U ≥ 0, V ≥ 0 フ ロ ベ ニ ウ ス ノ ル ム は 二 乗 誤 差 で あ る た め に ，大 き く 定 ま っ て し ま う が ， L2,1 ノ ル ム を 用 い る こ と で ，そ の 問 題 を 解 決 す る こ と が 可 能 で あ る ． そ の た め ，NMF に 比 べ て ロ バ ス ト 性 能 を 持 つ [6]．外 れ 値 ，ノ イ ズ ，デ ー タ 欠 損 に 影 響 を 受 け て し ま う 問 題 の 解 決 を 図 る こ と が 可 能 な 手 法 で あ る ．
2.3.3
Graph Regularized NMF(GNMF)
GNMF [8] は 局 所 的 不 変 性 に 着 目 し た NMF で あ る ．い わ ば ，デ ー タ 空 間 の 幾 何 学 関 係 を 考 慮 し た NMF で あ る ．元 の 信 号 の 構 造 は 射 影 後 に も 保 存 さ れ る と い う こ と を ，隣 接 行 列 と 任 意 の 2 つ の デ ー タ 点 間 の 距 離 関 係 に よ っ て 導 出 し た 局 所 的 不 変 ペ ナ ル テ ィ 項 (Tr(VLVT)) で 実 現 し て い る [17]．目 的 関 数 を 式 (2.14) に 示 す ．W は 隣 接 行 列 ，µ は 正 則 化 パ ラ メ ー タ を 表 し て い る ．隣 接 行 列 は 元 の 特 徴 空 間 に お け る 幾 何 学 的 関 係 の 類 似 性 を グ ラ フ 表 現 し た 行 列 で あ る ． • X ∈ Rm×n, U∈ Rm×k, V∈ Rk×n • Db =&lWjl，L = Db − W，µ ≥ 0 min U∈Rm×k,V∈Rk×n ∥X − UV∥ 2 F + µTr(VLVT) (2.14) subject to U ≥ 0, V ≥ 0お 互 い に 近 い 距 離 に 位 置 す る は ず で あ る と い う こ と ，い わ ば 局 所 性 に 着 目 し て い る ．そ の た め に ，入 力 信 号 空 間 に お け る 2 つ の デ ー タ サ ン プ ル (xj, xl) の 距 離 関 係 と ，求 め る 係 数 行 列 V 内 に そ れ ぞ れ 対 応 す る 係 数 ベ ク ト ル (zj, zl) と の 関 係 に 着 目 し ，近 く に 位 置 す る デ ー タ サ ン プ ル 同 士 が ， 異 な る 係 数 ベ ク ト ル で 表 現 さ れ る こ と に 対 す る ペ ナ ル テ ィ 項 を ，NMF の 目 的 関 数 で 考 慮 し た も の で あ る ．ペ ナ ル テ ィ 項 は Tr(VLVT ) で 表 さ れ る ． ペ ナ ル テ ィ 項 に つ い て 2.3.3 に 示 す ． ペ ナ ル テ ィ 項 の 導 出 ペ ナ ル テ ィ 項 を 考 え る 際 ，信 号 の 特 徴 空 間 に お け る 幾 何 的 関 係 を 行 列 で 表 現 し た い ．そ の た め に ，元 の 特 徴 空 間 に お け る 幾 何 的 関 係 の 類 似 性 を グ ラ フ に 表 現 し た 行 列 で あ る 隣 接 行 列と デ ー タ 間 距 離 を 用 い る [18]． • 隣 接 行 列 W に つ い て 隣 接 行 列は ，元 の 特 徴 空 間 に お け る 幾 何 的 関 係 の 類 似 性 を グ ラ フ に 表 現 し た 行 列 で あ る ． Wjl= wjl = ⎧ ⎨ ⎩ exp * −∥xj − xl∥ 2σ2 + xjと xlが 隣 接 し て い る 場 合 0 otherwise (2.15) Wjlは 2 つ の デ ー タ 点 (xj,xl) 間 の デ ー タ 間 の 距 離 関 係 を 表 現 し て い る ． 各 サ ン プ ル に つ い て 最 も 類 似 し て い る K 個 に 重 み を 与 え ，他 の サ ン プ ル に は 重 み を 与 え な い ．こ れ に よ っ て 重 み 計 算 が よ り シ ン プ ル に 考 え る こ と が で き る ． • 係 数 ベ ク ト ル 間 距 離 d(·, ·) の 定 義 係 数 行 列 表 現 を V = [z1, . . . , zj, . . . , zn] と 定 義 す る ．新 し い 基 底 に よ る 2 つ の デ ー タ 点 (xj,xl) に 対 応 す る 表 現 係 数 ベ ク ト ル (zj, zl) 間 の 距 離 d(zj, zl) を 式 (2.16) に 定 義 す る ． d(zj, zl) = ∥zj− zl∥2 (2.16) • ペ ナ ル テ ィ 項 の 考 え 方 入 力 信 号 空 間 に お け る 2 つ の デ ー タ サ ン プ ル (xj, xl) が 近 い 場 合 Wjl の 値 が 増 加 す る よ う な ペ ナ ル テ ィ 項 を 考 え る ．ま た ，係 数 ベ ク ト
ル 間 距 離 が 大 き い 場 合 に お い て も d(zj, zl) が 増 加 す る よ う な ペ ナ ル テ ィ 項 を 考 え る ．Wjl及 び d(zj, zl) の 値 が 増 加 す る こ と で ，罰 則 効 果 も 増 加 す る よ う に 設 定 す る ． • 局 所 的 不 変 ペ ナ ル テ ィ 項 を 定 義 上 記 の ペ ナ ル テ ィ 項 の 考 え 方 よ り ，隣 接 行 列 W と 係 数 ベ ク ト ル 間 距 離 d(zj, zl) か ら 局 所 的 不 変 ペ ナ ル テ ィ 項 を 定 義 す る ． 1 2 N % j,l=1 ∥zj − zl∥2Wjl (2.17) • 局 所 的 不 変 ペ ナ ル テ ィ 項 の 導 出 式 (2.17) を 変 形 し ，局 所 的 不 変 ペ ナ ル テ ィ 項 を 導 出 す る ．こ こ で Db = &lWjl，L = Db − W と 定 義 1 2 N % j,l=1 ∥zj− zl∥2Wjl = 1 2 N % j,l=1 (zTjzj− 2zTjzl+ zTl zl)Wjl = 1 2 N % j,l=1 zTjzjWjl− N % j,l=1 zTjzlWjl+ 1 2 N % j,l=1 zTl zlWjl = N % j=1 zTjzjDbjj− N % j,l=1 zTjzlWjl = Tr(VDbVT)− Tr(VWVT) = Tr(VLVT) こ の ペ ナ ル テ ィ 項 は 提 案 手 法 に も 用 い ら れ て い る ．ペ ナ ル テ ィ 項 は ，ク ラ ス タ リ ン グ の 際 ，任 意 の 隣 接 距 離 N と 正 則 化 パ ラ メ ー タ p を 設 定 す る 必 要 が あ り ，そ の 最 適 値 は 実 験 測 で 得 る こ と が で き る ．本 稿 に お い て も ， 任 意 の 隣 接 距 離 N と 正 則 化 パ ラ メ ー タ p を 設 定 し た 実 験 を 行 な っ て い る ．
2.3.4
Orthogonal Nonnegatively Penalized
Matrix Factorization(ONP-MF)
最 適 化 問 題 の 局 所 最 適 解 を 数 値 的 に 求 め る ア ル ゴ リ ズ ム で あ る ．NMF 等 と は 違 い ，直 交 制 約 を 保 証 し た パ ラ メ ー タ 更 新 式 を 行 い な が ら ，直 交 制 約 の ペ ナ ル テ ィ に よ り ，漸 近 的 に 非 負 値 制 約 を 実 現 す る も の で あ る ．ま た ，ロ バ ス ト 性 も 持 つ ．初 期 値 を SVD に よ っ て 与 え て い る た め ，ラ ン ダ ム で 初 期 値 を 求 め る NMF と 比 較 し て ，初 期 値 依 存 性 を 低 下 さ せ る こ と が 可 能 で あ る ．目 的 関 数 を 式 (2.18) に 示 す ． • X ∈ Rm×n, U∈ Rm×k, V∈ Rk×n • Λ ∈ Rk×n，ρ ≥ 0(二 次 の ペ ナ ル テ ィ パ ラ メ ー タ) minU,V,Λ Lρ(U, V, Λ) where Lρ(U, V, Λ) = 1 2∥X − UV∥ 2 F +⟨Λ, −V⟩ +ρ 2∥min(V, 0)∥ 2 F subject to U ≥ 0, VVT= Ik (2.18) こ の 手 法 は 乗 法 的 更 新 則 で は な く ，勾 配 法 等 を 用 い て 収 束 を 行 う ．値 の 更 新 法 に つ い て 2.3.4 に 示 す ． 値 の 更 新 ONP-MF で は ，辞 書 行 列 U，係 数 行 列 V，及 び ラ グ ラ ン ジ ュ 乗 数 Λ を 条 件 を 満 た す ま で 反 復 す る こ と で ，値 を 収 束 さ せ る ．な お ，双 対 定 理 か ら ， 解 (U, V) は 双 対 問 題 の 解 と な る こ と に 注 意 し て 求 め る 必 要 が あ る ． • U の 更 新 V と Λ を 固 定 し ，以 下 の 非 負 値 制 約 の 付 い た 最 小 二 乗 問 題 を 解 く ． こ こ で ，X，V，given な 値 で あ る ． U ← arg min X∈Rm×n ∥X − YV∥2 F (2.19) • V の 更 新 勾 配 射 影 法 [20] を 用 い て 更 新 を 行 な っ て い る ．直 交 制 約 を 保 証 し な が ら V を 更 新 を 行 う ．入 力 V に 対 し て ，最 急 勾 配 降 下 法 及 び 直 線 探 索 [19] に よ っ て 更 新 し ，直 交 制 約 保 証 の た め ，VVT = I kと な る 空 間
へ の 射 影 を 行 い ，収 束 条 件 が 満 た さ れ る ま で 繰 り 返 し 計 算 を 行 う ． ス テ ッ プ サ イ ズ β の 導 出 に 直 線 探 索 を 用 い る ．収 束 条 件 が 満 た さ れ る ま で ， (A) ， (B) を 繰 り 返 す ． (A) 最 急 勾 配 降 下 法 及 び 直 線 探 索 ま ず V を 最 急 降 下 法 に よ っ て 導 出 す る ．そ の 際 ，ス テ ッ プ サ イ ズ を 求 め る た め に 直 線 探 索 を 用 い る ． ・ Z：最 急 降 下 法 に よ っ て V を 収 束 さ せ た 値 Z = V− β∂Lρ ∂V = V− β(UTX− UTUV + Λ + ρ max(−V, 0)) (2.20) (B) Z の VVT = Ik空 間 へ の 射 影 (A) で 求 め た Z を ，VVT = Ikを 満 た す 空 間 へ 射 影 す る ．Z に 極 分 解 [11] を 用 い る こ と で ，式 (2.21) ， (2.22) で 表 さ れ る よ う に ，正 規 直 交 基 底 を 取 り 出 す こ と で ，そ れ を 達 成 し て い る ． ・ ˆV：ZZT = I kを 満 た す V(V を 更 新 し た も の) ˆ V = arg min Y ∥Z − Y∥2 F subject to YYT = Ik (2.21) ˆ V = Z(ZTZ)−1/2 (2.22) • ラ グ ラ ン ジ ュ 乗 数 Λ の 更 新 関 数 Λ +→ maxΛ≥0Lρ(U, V, Λ) の Λ に 対 す る 勾 配 は−V で あ る こ と ，ま た ，Λ が 非 負 値 で あ る こ と に 注 意 し て ，式 (2.23) の よ う に 更 新 す る ． こ こ で ，α は ス テ ッ プ サ イ ズ で あ る ． Λ← max(0, Λ − αV) (2.23) ス テ ッ プ サ イ ズ α は ，α = α0/t (t:更 新 回 数) で 設 定 し て い る ．
2.4
手 法 の 比 較
こ れ ま で 述 べ た 手 法 の 特 徴 を 表 2.2 に 示 す ．そ れ ぞ れ の 特 徴 と し て ， 非 負 値 制 約 ，直 行 制 約 ，幾 何 的 制 約 ，L2,1 ノ ル ム が 挙 げ ら れ る ．ONMF， GNMF の 制 約 は 精 度 向 上 に 繋 が り ，RNMF と ONP-MF は ロ バ ス ト 性 能 を 持 つ た め ，そ れ ら の 制 約 を NMF に 与 え る こ と で ，ノ イ ズ デ ー タ 等 に 対 し て の ク ラ ス タ リ ン グ 精 度 が 向 上 す る の で は な い か と 考 え ら れ る ．提 案 手 法 に つ い て の 詳 細 は 3 章 で 述 べ る ． 表 2.2: 手 法 の 比 較方 式
非 負 値 制 約
直 交 制 約
幾 何 的 制 約
L2,1
ノ ル ム 初 期 値
NMF
Direct (MU)
random
ONMF
Direct (MU)
!
random
RNMF
Direct (MU)
!
random
GNMF
Direct (MU)
!
random
ONP-MF
Lagrangian
Direct
SVD
提 案 手 法
Lagrangian
Direct
!
!
SVD
(Projection)
• Direct: 直 接 的 (強 制 的) に 制 御
• MU: Multiplicative Update (乗 法 的 更 新 則) • Projection: 射 影 手 法 に よ る 実 現
第
3
章 提案手法
本 研 究 は ，1 章 で 述 べ た NMF の 問 題 各 々 に 関 し て ，そ の 解 決 手 法 の 一 例 が ，2 章 で 述 べ た 関 連 研 究 で あ る ．で は ，そ れ ら の 問 題 を 総 じ て 解 決 す る た め に は ，そ の 特 徴 を NMF に 取 り 入 れ ，組 み 合 わ せ る こ と で 改 善 で き な い か と 考 え た ．そ こ で ，実 際 に 取 り 入 れ ，組 み 合 わ せ た NMF は ，ノ イ ズ デ ー タ に 対 し て ク ラ ス タ リ ン グ を 行 な っ た 際 ，従 来 の ロ バ ス ト 性 を 持 つ 手 法 よ り 質 が 改 善 さ れ て い る か と い う 検 討 を 行 っ た も の で あ る ．3.1
Robust Locally ONP-MF(Rbust-Li-ONP-MF)
目 的 関 数 を 式 (3.1) に 示 す ． • X ∈ Rm×n, U∈ Rm×k, V∈ Rk×n • Λ ∈ Rk×n，ρ ≥ 0(二 次 の ペ ナ ル テ ィ パ ラ メ ー タ) • Di,i = ∥x 1 i−Uvi∥ • X = [x1, . . . , xi, . . . , xn], V = [v1, . . . , vi, . . . , vn] と 定 義 す る ． minU,V,Λ Lρ,µ(U, V, Λ) where Lρ,µ(U, V, Λ) = 1 2∥X − UV∥2,1+⟨Λ, −V⟩ +ρ 2∥min(V, 0)∥ 2 F + µTr(VLVT) subject to U≥ 0, VVT = Ik (3.1) U，V，Λ を 反 復 的 に 更 新 す る こ と で ，式 (3.1) が 最 小 と な る 値 を 求 め る ． 2.3.4 の 式 を 軸 に 関 連 研 究 で 述 べ た 手 法 の 特 徴 を 組 み 合 わ せ て い る ．そ の
3.2
分 解 行 列 と ラ グ ラ ン ジ ュ 乗 数 の 更 新
3.2.1
U
更 新
U は 勾 配 射 影 法 [20] に よ っ て 更 新 を 行 う ．勾 配 法 を 用 い て 値 の 収 束 を 行 う ． 1. A は 最 急 降 下 法 で 求 め る ．ス テ ッ プ サ イ ズ γ は 直 線 探 索 [19] に よ っ て 求 め る ． A = U− γ∂Lρ,µ ∂U = U− γ(UVDVT− XDVT) (3.2) 2. A を A ≥ 0 を 満 た す 空 間 へ 射 影 す る ． ˆ Ui,j = , Ai,j (Ai,j > 0) 0 (Ai,j ≤ 0)3.2.2
V
更 新
2.3.4 と 同 様 に ，勾 配 射 影 法 [20] に よ っ て 更 新 を 行 う ．入 力 V を ，最 急 降 下 法 に よ り 更 新 し ，直 交 制 約 保 証 の た め の VVT = I kと な る 空 間 へ の 射 影 を 行 い ，収 束 条 件 が 満 た さ れ る ま で 繰 り 返 し 計 算 を 行 う ．ス テ ッ プ サ イ ズ β は 直 線 探 索 [19] に よ っ て 求 め る ． 1. 最 急 降 下 法 を 用 い て 最 適 値 Z を 求 め る ． Z = V− β∂Lρ ∂V= V− β(UTUVD− UTXD + Λ + ρ max(−V, 0))
(3.4) 2. Z を VVT = Ik空 間 へ の 射 影 (Z，given， ˆV は 極 分 解 に よ り 導 出) す る ． ˆ V = arg min Y ∥Z − Y∥ 2 F subject to YYT = Ik (3.5) 入 力 信 号 Z の 正 規 直 交 基 底 を 取 り 出 す 極 分 解 [11] に よ り 解 ˆV を 計 算 す る ． ˆ V = Z(ZTZ)−1/2 (3.6)
3.2.3
Λ
更 新
ラ グ ラ ン ジ ュ 関 数 Λ も 勾 配 法 を 用 い て 求 め る ．2.3.4 と 同 様 に ，関 数 Λ+→ maxΛ≥0Lρ(U, V, Λ) に 対 す る 勾 配 は−V で あ る こ と ，非 負 値 で あ る こ と に 注 意 し て ，以 下 の 式 で 更 新 す る ．ス テ ッ プ サ イ ズ α は ，α = α0/t で 設 定 す る ．t は 更 新 回 数 で あ る ． Λ← max(0, Λ − αV) (3.7)第
4
章 評価実験
1.3 で 問 題 解 決 の た め ，関 連 研 究 で 述 べ た 手 法 の 特 徴 を 取 り 入 れ た 提 案 法 を 考 え た ．従 来 の も の と 比 較 し て ，ロ バ ス ト 性 及 び ク ラ ス タ リ ン グ 精 度 が 向 上 す る も の に な る と 考 え ら れ る ．そ こ で ，ノ イ ズ を 混 入 し た デ ー タ に 対 し て の ク ラ ス タ リ ン グ を 行 い ，従 来 手 法 と の 比 較 実 験 を 行 な っ た ． そ の 際 以 下 の 2 つ の 実 験 を 行 っ た. • ノ イ ズ 密 度 の 変 化 ノ イ ズ の 密 度 が 変 化 し た 際 の 性 能 へ の 影 響 の 確 認 の た め • 正 則 化 パ ラ メ ー タ µ や 隣 接 距 離 p の 値 の 変 化 正 則 化 パ ラ メ ー タ µ や 隣 接 距 離 p の 性 能 へ 与 え る 影 響 確 認 の た め4.1
対 象 デ ー タ セ ッ ト
対 象 デ ー タ セ ッ ト は 表 4.1 の も の を 用 い た ． 表 4.1: 実 験 デ ー タ セ ッ トdataset type Instances(size) Features(dimentionality) Number of clusses
COIL20 Image 1440 1024 20 • COIL20:20 種 類 の 物 体 を 5 度 ず つ 角 度 を 変 え て 撮 影 し た 画 像 デ ー タ セ ッ ト
4.2
実 験 条 件
本 稿 の 提 案 手 法 は ，2.3.3 と 同 様 に ，正 則 化 パ ラ メ ー タ µ 及 び 隣 接 距 離 p の 値 に よ っ て 精 度 が 変 化 す る ．そ の た め ，値 を 変 え る こ と に よ っ て ，ど の よ う に ク ラ ス タ リ ン グ 精 度 が 変 化 す る の に 着 目 し た 実 験 を 行 な っ た ．ロ バ ス ト 性 を 確 認 及 び ノ イ ズ の ク ラ ス タ リ ン グ 精 度 へ の 影 響 の 確 認 の た め ，ノ イ ズ デ ー タ を 使 用 し た ．本 実 験 で 行 な っ た も の は 以 下 の 3 つ の 実 験 で あ る ． 1 正 則 化 パ ラ メ ー タ を 変 え た 時 の ク ラ ス タ リ ン グ 精 度 パ ラ メ ー タ は {0.01，0.1，1} の 5 つ を 設 定 し た ． 2 隣 接 距 離 の 値 を 変 化 さ せ た 時 の ク ラ ス タ リ ン グ 精 度 パ ラ メ ー タ は {5，10，15，20} の 4 つ を 設 定 し た ． 3 ノ イ ズ の 精 度 へ の 影 響{0.05, 0.075, 0.1} の レ ベ ル の ノ イ ズ デ ー タ を 使 用 し て 実 験 を 行 な っ た ． 比 較 手 法 を 以 下 に 示 す ． • k-means[7] • NMF 2.2 参 照 • GNMF 2.3.3 参 照 • RNMF 2.3.2 参 照 • ONP-MF 2.3.4 参 照 実 験 の そ の 他 条 件 を 以 下 に 示 す ． • iteration number:1000 • 提 案 手 法 及 び 比 較 手 法 各 々 5 回 試 行 • 4.3 で 説 明 す る 評 価 指 標 の 5 回 平 均 及 び そ の 標 準 偏 差 を 結 果 と し て い る • 初 期 値 は 全 て 同 様 の 値 で ，SVD の 左 特 異 値 と 右 特 異 値 を 設 定 し て い る [21] • α =1.01，ρ=0.01 と 設 定
4.3
評 価 指 標
結 果 の 評 価 に は ，purity，Accuracy，NMI を 指 標 と し て 用 い た ．こ れ ら の 値 は 大 き な 値 で あ る 程 良 い ク ラ ス タ リ ン グ 結 果 で あ る こ と を 示 す 指 標 で あ る ． purity (純 度) [22] は 式 (4.1) で 定 義 さ れ る 指 標 で あ る ．こ の 指 標 は ，正 解 ク ラ ス タ の デ ー タ を 含 む 割 合 を 示 す も の で あ る ． • N:デ ー タ 数 ，K:生 成 ク ラ ス タ 数 • xi,j:生 成 ク ラ ス タ の i 番 目 に 置 い て ，j 番 目 の 正 し い ク ラ ス タ に 属 す る デ ー タ 数 purity = 1 N K % i=1 max j (xi,j) (4.1) Accuracy[23] (正 確 性) は 式 (4.2) で 定 義 さ れ る 指 標 で あ る ．こ の 指 標 は ク ラ ス タ の 正 確 性 を 示 す も の で あ る ． • ri:ク ラ ス タ ラ ベ ル ，di:正 解 ラ ベ ル ，N:デ ー タ 数 • δ(x, y):if x = y を 示 す 関 数 ，map(ri):そ れ ぞ れ の 正 解 ラ ベ ル と ク ラ ス タ ラ ベ ル を 対 応 さ せ る 関 数 Accuracy = max i=1 % N δ(map(ri), di) N (4.2) N M I (正 規 化 相 互 情 報 量) [24] は 式 (4.3) で 定 義 さ れ る 指 標 で あ る ． こ の 指 標 は ク ラ ス タ の 類 似 性 を 示 す も の で あ る ． • K:生 成 ク ラ ス タ 集 合 ，T :正 解 ク ラ ス タ の 集 合 • MI:相 互 情 報 量 ，H:エ ン ト ロ ピ ー N M I = M I(K, T ) max(H(K), H(T )) (4.3) H(K)，H(T ) は 式 (4.4) で 表 記 さ れ る ． • N:全 デ ー タ 数 • P (Ki) = |KNi|，|Ki|:生 成 さ れ た ク ラ ス タ Kiに 含 ま れ る デ ー タ 数H(K) =− k % i P (Ki) log P (Ki) i∈ {1, 2, ..., k} ま た ，MI(K, T ) は 式 (4.4) で 定 義 さ れ る ． M I(K, T ) = H(T ) + H(K)− H(K, T ) (4.4)
第
5
章 実験結果
精 度 評 価 結 果 を 表 5.1 か ら 表 5.12 に 示 す. ま た ，パ ラ メ ー タ の 組 み 合 わ せ の 違 う 精 度 評 価 図 を 図 5.1 か ら 図 5.5 に 示 す ．表 中 の 値 は 評 価 値 の 5 回 平 均 の 値 を ， ± は 標 準 偏 差 を 示 す. 表 は µ は 正 則 化 パ ラ メ ー タ を ，p は 隣 接 距 離 を 示 す ．ま た ，正 則 化 パ ラ メ ー タ µ や 隣 接 距 離 p の 値 が 影 響 の 無 い k-means，NMF，RNMF，ONP-MF は 各 々 の 値 が 変 化 し て も ，評 価 値 等 に 影 響 は 及 ぼ さ な い 手 法 で あ る. ま た ，最 も 高 い 精 度 を 示 し た 結 果 を 太 字 ，時 点 で 高 い 精 度 を 示 し た 結 果 に 下 線 で 表 す ． 精 度 の み 着 目 す る と ，正 則 化 パ ラ メ ー タ 等 に よ っ て 最 高 精 度 を 示 す 組 み 合 わ せ は 違 う が ，表 5.1 か ら 表 5.12 ど れ も 従 来 手 法 よ り 高 い 精 度 を 示 す 結 果 と な っ た ．こ れ は ，ロ バ ス ト 性 と 幾 何 的 な 情 報 量 を 取 り 入 れ た こ と に よ る 精 度 の 向 上 で あ る と 考 え ら れ る ． ま た ，表 5.7 と 表 5.11 に 着 目 す る と ，ノ イ ズ の 密 度 が 増 し て い る に も 関 わ ら ず ，精 度 が 増 し て い る こ と が 確 認 で き る ．こ れ は ，デ ー タ に よ っ て ， 最 適 な 正 則 化 パ ラ メ ー タ と 隣 接 距 離 の 組 み 合 わ せ に よ る こ と が 原 因 と 考 え ら れ る ．つ ま り ，幾 何 的 な 構 造 の 情 報 に よ っ て 精 度 が 向 上 し て い る こ と が 確 認 で き る ． よ っ て ，ロ バ ス ト 性 及 び 幾 何 的 な 構 造 の 情 報 の 付 与 に よ っ て ONP-MF の 問 題 を 低 減 し ，精 度 の 向 上 に つ な げ る こ と が で き た 結 果 と な っ た ．表 5.1: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=5，noise level=0.05)
method µ-num purity Accuracy NMI
k-means − 52.6 47.8 52.6 NMF − 54.7±0.9 51.0±1.2 59.7±0.6 Robust NMF − 17.8±0.3 17.3±0.2 17.4±0.1 0.01 12.9±0.08 11.9±0.1 9.5±0.1 GNMF 0.1 11.0±0.3 9.7±0.3 6.7±0.4 1 11.1±0.2 10.3±0.2 8.4±0.1 ONP-MF − 71.5±1.1 68.5±1.0 78.5±1.1 0.01 69.6±1.6 68.0±1.6 77.5±0.6 Robust-Li-ONP 0.1 72.7±0.9 70.7±1.6 78.4±0.8 1 72.9±1.0 71.1±1.9 78.8±0.5 表 5.2: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=10，noise level=0.05)
method µ-num purity Accuracy NMI
k-means − 52.6 47.8 52.6 NMF − 54.7±0.9 51.0±1.2 59.7±0.6 Robust NMF − 17.8±0.3 17.3±0.2 17.4±0.1 0.01 15.4±0.7 13.8±0.7 13.8±0.9 GNMF 0.1 13.5±0.08 12.6±0.1 11.5±0.05 1 12.0±0.03 11.2±0.03 7.9±0.06 ONP-MF − 0.72±0.1 0.69±0.09 0.79±0.01 0.01 0.71±0.1 0.68±0.1 0.78±0.07 Robust-Li-ONP 0.1 0.72±0.2 0.71 ±0.3 0.79±0.1
表 5.3: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=15，noise level=0.05)
method µ-num purity Accuracy NMI
k-means − 52.6 47.8 52.6 NMF − 54.7±0.9 51.0±1.2 59.7±0.6 Robust NMF − 17.8±0.3 17.3±0.2 17.4±0.1 0.01 12.3±0.3 11.7±0.5 9.4±0.2 GNMF 0.1 9.2±0.1 8.3±0.1 5.2±0.1 1 12.9±1.1 12.5±1.1 8.6±0.9 ONP-MF − 71.5±1.1 68.5±1.0 78.5±1.1 0.01 70.7±2.2 68.3±2.6 77.4±1.5 Robust-Li-ONP 0.1 71.3±1.6 67.9±2.3 78.2±0.8 1 72.8±1.9 70.8±2.4 79.0±1.3 表 5.4: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=20，noise level=0.05)
method µ-num purity Accuracy NMI
k-means − 52.6 47.8 52.6 NMF − 54.7±0.9 51.0±1.2 59.7±0.6 Robust NMF − 17.8±0.3 17.3±0.2 17.4±0.1 0.01 8.7±0.5 8.0±0.5 4.4±0.5 GNMF 0.1 9.5±0.6 9.0±0.5 6.3±0.9 1 10.3±1.3 9.7±1.2 6.1±1.4 ONP-MF − 71.5±1.1 68.5±0.9 78.5±1.1 0.01 71.1±2.5 69.3±3.8 78.0±1.2 Robust-Li-ONP 0.1 72.4±2.1 70.3±3.1 78.4±1.0 1 70.9±1.7 69.2±1.9 78.4±0.7
表 5.5: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=5，noise level=0.075)
method µ-num purity Accuracy NMI
k-means − 51.9 49.0 51.9 NMF − 53.6±0.7 50.8±1.1 59.8±0.5 Robust NMF − 16.4±0.5 16.2±0.5 15.2±0.8 0.01 11.4±0.4 10.3±0.4 8.6±0.7 GNMF 0.1 7.7±0.5 7.1±0.5 3.7±0.7 1 10.8±0.6 9.2±0.6 7.4±0.6 ONP-MF − 70.7±1.7 68.8±2.4 77.5±1.0 0.01 69.5±1.6 68.0±2.6 77.7±0.7 Robust-Li-ONP 0.1 69.3±1.6 66.5±1.2 77.7±0.7 1 70.5±2.7 68.4±3.2 77.7±1.3 表 5.6: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=10，noise level=0.075)
method µ-num purity Accuracy NMI
k-means − 51.9 49.0 51.9 NMF − 53.6±0.7 50.8±1.1 59.8±0.5 Robust NMF − 16.4±0.5 16.2±0.5 15.2±0.8 0.01 14.6±0.2 14.1±0.2 13.8±0.2 GNMF 0.1 7.2±0.2 6.5±0.8 2.8±0.2 1 9.3±0.07 8.5±0.05 5.1±0.07 ONP-MF − 70.7±1.7 68.8±2.4 77.5±1.0 0.01 70.2±1.9 67.5±1.6 78.4±0.5 Robust-Li-ONP 0.1 70.8±1.4 69.9±2.2 78.3±0.7
表 5.7: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=15，noise level=0.075)
method µ-num purity Accuracy NMI
k-means − 51.9 49.0 51.9 NMF − 53.6±0.7 50.8±1.1 59.8±0.5 Robust NMF − 16.4±0.5 16.2±0.5 15.2±0.8 0.01 9.2±0.4 8.5±0.3 5.7±0.7 GNMF 0.1 10.8±0.4 9.9±0.4 7.1±0.5 1 9.0±0.6 8.2±0.5 4.3±0.5 ONP-MF − 70.7±1.7 68.8±2.4 77.5±1.0 0.01 71.8±1.7 69.9±1.9 78.7±0.9 Robust-Li-ONP 0.1 72.0±1.6 69.6±1.5 78.7±0.8 1 70.4±1.2 68.5±1.4 77.1±0.9 表 5.8: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=20，noise level=0.075)
method µ-num purity Accuracy NMI
k-means − 51.9 49.0 51.9 NMF − 53.6±0.7 50.8±1.1 59.8±0.5 Robust NMF − 16.4±0.5 16.2±0.5 15.2±0.8 0.01 8.9±0.04 8.4±0.07 4.8±0.09 GNMF 0.1 14.3±0.04 13.4±0.04 11.2±0.01 1 12.0±0.03 11.4±0.03 06.5±0.2 ONP-MF − 70.7±1.7 68.8±2.4 77.5±1.0 0.01 72.1±1.8 69.6±2.6 78.5±0.8 Robust-Li-ONP 0.1 70.8±2.4 68.7±2.8 78.3±1.0 1 73.0±0.4 72.1±0.6 79.5±0.3
表 5.9: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=5，noise level=0.1)
method µ-num purity Accuracy NMI
k-means − 35.8 32.9 52.7 NMF − 52.5±1.1 49.9±1.1 59.2±0.8 Robust NMF − 11.1±0.6 10.8±0.6 7.7±0.4 0.01 13.8±0.5 13.4±0.5 9.2±1.3 GNMF 0.1 10.2±1.0 9.6±0.7 7.1±1.6 1 8.4±0.9 7.8±0.8 4.7±1.2 ONP-MF − 70.2±1.9 68.3±1.9 77.7±0.8 0.01 71.9±1.9 70.0±2.6 78.4±1.3 Robust-Li-ONP 0.1 71.5±1.1 69.7±1.7 78.3±0.9 1 71.9±1.3 70.3±1.6 78.3±0.9 表 5.10: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=10，noise level=0.1)
method µ-num purity Accuracy NMI
k-means − 35.8 32.9 52.7 NMF − 52.5±1.1 49.9±1.1 59.2±0.8 Robust NMF − 11.1±0.6 10.8±0.6 7.7±0.4 0.01 9.3±0.4 7.9±0.4 5.2±0.4 GNMF 0.1 12.6±0.1 11.5±0.1 10.0±0.4 1 11.6±0.06 11.1±0.06 8.0±0.1 ONP-MF − 70.2±1.9 68.3±1.9 77.7±0.8 0.01 70.6±2.1 68.6±2.5 77.9±1.3 Robust-Li-ONP 0.1 70.8±1.4 68.4±1.1 78.0±0.8
表 5.11: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=15，noise level=0.1)
method µ-num purity Accuracy NMI
k-means − 35.8 32.9 52.7 NMF − 52.5±1.1 49.9±1.1 59.2±0.8 Robust NMF − 11.1±0.6 10.8±0.6 7.7±0.4 0.01 13.4±0.4 11.8±0.5 10.2±0.5 GNMF 0.1 10.3±0.2 9.2±0.2 6.6.±0.2 1 11.7±0.2 10.8±0.2 7.0±0.1 ONP-MF − 70.2±1.9 68.3±1.9 77.7±0.8 0.01 72.2±1.4 70.0±2.2 78.7±0.7 Robust-Li-ONP 0.1 72.6±1.8 70.4±3.3 78.7±0.7 1 70.0±2.2 68.1±2.5 77.5±0.8 表 5.12: ク ラ ス タ リ ン グ 実 験 結 果 (p-num=20，noise level=0.1)
method µ-num purity Accuracy NMI
k-means − 35.8 32.9 52.7 NMF − 52.5±1.1 49.9±1.1 59.2±0.8 Robust NMF − 11.1±0.6 10.8±0.6 7.7±0.4 0.01 13.1±0.6 12.3±0.5 14.1±0.4 GNMF 0.1 10.9±0.3 10.5±0.3 7.1±0.6 1 9.6±1.4 9.3±1.4 5.3±1.3 ONP-MF − 70.2±1.9 68.3±1.9 77.7±0.8 0.01 71.4±2.1 69.3±2.2 78.1±0.9 Robust-Li-ONP 0.1 72.7±2.0 71.5±2.3 78.9±0.9 1 72.2±2.1 70.6±3.1 78.6±1.2
Accuracy Purity NMI evaluation method 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Clustering Measure results k-means NMF L21 GNMF Proposed ONP-MF 図 5.1: 精 度 評 価 図 (µ=0.01,p=5,noise=0.05)
Accuracy Purity NMI
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Clustering Measure results k-means NMF L21 GNMF Proposed ONP-MF
Accuracy Purity NMI evaluation method 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Clustering Measure results k-means NMF L21 GNMF Proposed ONP-MF 図 5.3: 精 度 評 価 図 (µ=0.01,p=5,noise=0.05)
Accuracy Purity NMI
evaluation method 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Clustering Measure results k-means NMF L21 GNMF Proposed ONP-MF 図 5.4: 精 度 評 価 図 (µ=0.1,p=10,noise=0.05)
Accuracy Purity NMI evaluation method 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Clustering Measure results k-means NMF L21 GNMF Proposed ONP-MF 図 5.5: 精 度 評 価 図 (µ=0.1,p=20,noise=0.05)
第
6
章 結論
本 研 究 で は ，NMF を 拡 張 し た ONP-MF の 問 題 解 決 の た め ，ロ バ ス ト 性 と 幾 何 学 的 情 報 を 手 法 に 付 加 し た Robust-Li-ONP-MF の 目 的 関 数 及 び 値 の 更 新 に つ い て の 提 案 を 行 っ た ． 結 果 と し て ，多 手 法 と 比 較 し て ，僅 か だ が 高 い ロ バ ス ト 性 が 確 認 で き た ．ま た ，評 価 指 標 か ら ，幾 何 学 的 構 造 に よ る 精 度 の 向 上 が 確 認 す る こ と が で き た ． 今 後 と し て ，多 種 の デ ー タ に 関 し て も 同 様 の 実 験 を 行 い ，ど の デ ー タ に 関 し て も 同 様 の 性 能 が 得 ら れ る か の 確 認 を 行 う 必 要 が あ る ．ま た ，任 意 の パ ラ メ ー タ に 関 し て も よ り 細 か く 設 定 し ，適 切 な パ ラ メ ー タ は ど の 範 囲 に 集 約 す る か 等 の 検 討 を 行 う ．謝辞
本 研 究 を 実 施 す る に あ た っ て ，ご 指 導 を い た だ き ま し た 笠 井 裕 之 先 生 に 心 か ら 感 謝 申 し 上 げ ま す ．ま た ，ゼ ミ や 講 座 内 発 表 等 で ご 助 言 ，ご 指 導 を い た だ き ま し た ，森 田 啓 義 先 生 ，眞 田 亜 紀 子 先 生 ，応 用 ネ ッ ト ワ ー キ ン グ 講 座 の 様 々 な 面 に お き ま し て ，助 け て い た だ き ま し た 片 桐 さ ん に 心 か ら 感 謝 申 し 上 げ ま す ．そ し て ，有 意 義 な 研 究 活 動 を 行 う こ と が で き た の は 共 に 支 え 合 い ，助 け 合 う こ と が で き た 同 講 座 内 の 仲 間 が い た か ら で す ．彼 ら に も ，感 謝 の 意 を 示 し ま す ．あ り が と う ご ざ い ま し た ．References
[1] Wang Yu-Xiong and Zhang Yu-Jin. Nonnegative matrix factorization: A com-prehensive review. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 25(6), June 2013.
[2] Daniel D Lee and H. Sebastian Seung. Algorithms for non-negative matrix factorization. Advances in neural information processing systems (NIPS), pages 556–562, 2001.
[3] Zhang Zhong-Yuan. Nonnegative matrix factorization: Models, algorithms and applications. Data Mining: Foundations and Intelligent Paradigms, 24:99–134, 2012.
[4] C. Boutsidis and E. Gallopoulos. Svd based initialization: A head start for non-negative matrix factorization. Pattern Recogn., 41(4):1350–1362, April 2008.
[5] Robust Capped Norm Nonnegative Matrix Factrization, October 2015.
[6] Kong Deguang, Ding Chris, and Huang Heng. Robust nonnegative matrix factorization using l21-norm. Association for Computing Machinery(ACM), pages 673–682, 2011.
[7] Seungjin Choi. Algorithms for orthogonal nonnegative matrix factorization. In Neural Networks, 2008. IJCNN 2008. (IEEE World Congress on Computational Intelligence). IEEE, June 2008.
[8] Cai Deng, He Xiaofei, Han Jiawei, and S. Huang Thomas. Graph rearized nonnegative matrix factrization for data representationgul. IEEE TRAN-SCATIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 33(8):Nonnegative matrix factorization, graph Laplacian, manifold regulariza-tion, clustering, August August 2011.
[10] Nocedal Jorge and J. Wright Stephen. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer-Verlag New York, 2006.
[11] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, New York, NY, USA, 2nd edition, 2012.
[12] M. Chu, F. Diele, R. Plemmons, and S. Rangni. Optimality, computation, and interpretation of nonnegative matrix factorizations. JOURNAL ON MATRIX ANALYSIS, October 2004.
[13] N. Del Buono and G. Pio. Non-negative matrix tri-factorization for co-clustering: An analysis of the block matrix. nformation Sciences, 301(C):13–26, April 2015.
[14] Ding Chris, Li Tao, Peng Wei, and Park Haesun. Orthogonal nonnegative matrix tri-factorizations for clustering. In SIGKDD, pages 126–135, August 2006.
[15] 亀 岡 弘 和. 非 負 値 行 列 因 子 分 解. In the Society of Instrument and Control Engineers, volume 51, pages 835–844. コ ロ ナ 社, 9 2012.
[16] Yang Shizhun, HouChangshui Chenping, and Wu ZhangYi. Robust non-negative matrix factorization via joint sparse and graph regularization. Neural Computing and Applications, 23:541–559, August 2013.
[17] Li Yeqing, Huang Junzhou, and Liu Wei. Scale sequential spectral cluster-ing. In AAAI’16 Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1809–1815, February 2016.
[18] Mikhail Belkin and Niyogi Partha. Laplacian eigenmaps and spectral techniques for embedding and clustering. In T. G. Dietterich, S. Becker, and Z. Ghahra-mani, editors, Advances in Neural Information Processing Systems 14, pages 585–591. MIT Press, 2002.
[20] Wang Enyuan, Zhu Zhen, Chenc Wei, and Xiaod Pengcheng. Manifold nmf with l21 norm for clustering. Neurocomputing, 2017.
[21] Pompili Filippo, Gillis Nicolas, Absil P.-A, and Glineur Francois. ONP-MF: An orthogonal nonnegative matrix factrization algorithm with application to clus-tering. In Computational Intelligence and Machine Learning (ESANN 2013), April 2013.
[22] Peng Chong, Kang Zhao, Hu Yunhong, Cheng Jie, and Cheng Qiang. Ro-bust graph regularized nonnegative matrix factorization for clustering. ACM Transactions on Knowledge Discovery from Data, 11(33), April 2017.
[23] Ma Huifang, Zhao Weizhong, Tan Qing, and Shi Zhongzhi. Orthogonal non-negative matrix tri-factorization for semi-supervised document co-clustering. Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 189– 200, 2010.
[24] Cheng Hao, A.Hua Kien, and Vu Khanh. Constrained locally weighted cluster-ing. Constrained Locally Weighted Clustering, Volume 1:Pages 90–101, August 2008.
![図 2.2: 関 連 度 例 2.3 NMF の 拡 張 方 式 NMF は 様 々 な 応 用 研 究 が 行 わ れ て い る ．カ テ ゴ リ の 図 を 図 2.3 に 示 す ． 現 在 存 在 す る NMF は 以 下 の 4 つ の カ テ ゴ リ に 分 け る こ と が で き る [1] ． • Basic NMF (BNMF) : 非 負 値 制 約 の み の NMF • Constrained NMF (CNMF) : 正 則 化 の た め に い く つ か の 制 約](https://thumb-ap.123doks.com/thumbv2/123deta/7725197.1711293/15.892.232.649.146.472/連度例NMF拡張方式様々応用研究行.webp)
![図 2.3: NMF モ デ ル と ア ル ゴ リ ズ ム の カ テ ゴ リ [1]](https://thumb-ap.123doks.com/thumbv2/123deta/7725197.1711293/17.892.132.805.125.524/図23NMFモデルアルゴリズムカテゴリ.webp)
