多重ラベル分類を用いた意外性を有する楽曲検索・推薦手法の実験的考察

全文

(1)Vol.2017-MUS-116 No.20 2017/8/26. 情報処理学会研究報告 IPSJ SIG Technical Report. 多重ラベル分類を用いた意外性を有する楽曲検索・推薦手法の実験的考察大久保好章1. 原口誠1,a). 劉赫宇1. 概要：本報告では，著者等が現在考察を進めているラベル情報の意外性を考慮した検索・推薦手法の楽曲データへの適用を試みる．具体的には，信号ベースの特徴量空間における楽曲の近接性，および，楽曲が有するラベル情報に関する近接性を考えることで，データベース中の楽曲とクエリ楽曲間に二種類の距離を導入する．ラベルが未知のクエリに対して，後者の近接性に基づいて多重ラベル推定を行い，特徴量空間ではクエリと近く，すなわち関連性があるが，一方で，ラベルに関しては遠い楽曲をここでは『意外なもの』と定め，こうした意外性を有する楽曲を含むクラスタをユーザに提示する枠組みを考察する．. 1. はじめに. なわち，遠い (非類似な) ラベルを有するという意味での意外性を有するオブジェクトの検出を試みている．. 情報検索 [1] は，膨大なデータを有効に活用するための最. 本稿では，文献 [5] の基本アイデアを楽曲データに対し. も基本的な手段であり，今や我々の日常生活の一部となっ. て展開し，その有効性を実験的に確認することを目的とす. ている．その対象は，古くは文書 (テキスト) が主であった. る．具体的には，音響特徴量と (多重) ジャンルラベルが付. が，現在は音楽や動画を含む広範囲に及ぶ．. 与された楽曲データに対し，データベース中の楽曲に付与. 通常の情報検索では，データベース中のオブジェクトを. された多重ラベルの類似性を反映した部分空間での近接性. 特徴付ける属性空間での近接性に基づいてクエリとの関連. に基づき，クエリ楽曲のラベル推定を行い，元の特徴量空. 性を判断するが，実際にはこうした主要な属性に加え，付. 間ではクエリと近接，すなわち，関連性がある一方で，部. 加的な属性が利用できることも少なくない．例えば，音楽. 分空間では離れている，すなわち，遠いラベルを有する楽. や映画といった対象には，商用目的でのカタログ的なラベ. 曲の検出を試みる．こうした楽曲は，例えば，これまでに. ルが付与されることが多く，さらに，インターネットを介. 興味のなかったジャンルに目を向けるきっかけを与え得る. したメディア配信サービスや，それらを専門に扱う SNS. ものであり，ユーザの新たな音楽的興味を刺激するものと. の普及により，ユーザが自由に付与したタグ情報も現在で. 期待したい．. は入手可能となっている．こうしたラベル情報は，検索や. そこでは，ラベルに関する意外性 (遠さ) を測る物差しの. 推薦を行なう上で極めて有用なものであり，それら情報を. 設計が重要であるが，文献 [5] では，多重ラベルを有する対. 取り込むことで，より柔軟な検索・推薦処理の実現が期待. 象-属性データ行列から，対象のラベルを学習・推定する手. できる．. 法を与えた Sun 等のアイデア [2] を採用し，対象のラベル. こうした期待のもと，著者等はこれまで，所与のクエリ. 情報とその近接性を最もよく近似できる属性部分空間を用. に対するラベル情報の意外性を考慮した検索・推薦手法に. いている．ただし，[2] では，そうした空間を k-次元部分空. ついて考察した [5]．そこでは，データベース中のオブジェ. 間の直交基底を固有値問題を解くことで求めるが，単にク. クトに付与された多重ラベルの類似性を反映した属性部分. エリーを含めて対象がラベルに関して遠いか否かを判定で. 空間での近接性に基づいて，(ラベルが未知の) クエリのラ. きれば十分であるとの立場のもと，1-次元，すなわち，数直. ベルを暗に推定し，元の属性空間ではクエリと近接，すな. 線への射影を求めることで高負荷の固有値計算を回避して. わち，関連性がある一方で，部分空間では離れている，す. いる．特に，1-次元の場合は，グラフラプラシアンの正の最小固有値の近似解を二部グラフの交差数最小化アルゴリ. 1. a). 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University [email protected]. ⓒ 2017 Information Processing Society of Japan. ズム [3] により高速 (データサイズを n とした O(n log n)) に求めた上で判定できることがポイントとなっている．上述した二種類の距離のもと，クエリ楽曲に関するラベ. 1.

(2) Vol.2017-MUS-116 No.20 2017/8/26. 情報処理学会研究報告 IPSJ SIG Technical Report. 3. 多重ラベル分類. .3

(3) /4 &0 (2+)

(4) $-

(5) . . ' .3,. M -次元 (実) ベクトルで表現される N のデータ xi (1 ≤ i ≤ N ) から成る M × N データ行列を X = (x1 · · · xN ) とする．いま，Ls をラベルの集合とした時，各データ xi には，Ls 中のいくつかのラベル (多重ラベル) が付与されているものとし，それを L(xi ) (⊆ Ls) で参照する．. .3. ラベルが未知のデータ q ∈ RM について，X 中のデー (2+) 1 '.3. #"

(6) /4 &0 !%*

(7) 1

(8) 1. タとの類似性をもとに，q に付与されるであろう多重ラベルを推定するタスクを多重ラベル分類問題と呼ぶ．. 3.1 低次元空間への射影に基づく多重ラベル推定図 1. Sun 等は文献 [2] において，X 中の各データを頂点，各. クエリと関連性が高いが意外なラベルを有する楽曲を含むクラスタのイメージ. ラベル i ∈ Ls が付与されたデータ集合 (頂点集合) をハイ. ルの意外性を考慮した検索タスクを，特徴量空間での類似. パーエッジとするハイパーグラフ G により，データ群と. 度グラフにおけるクリーク探索問題として定式化する．よ. それら多重ラベルの関係を表現し，G のスター展開によっ. り正確には，特徴量空間でクエリと関連性のある楽曲から. て得られる二部グラフの正規化ラプラシアン L をスペク. 成る極大クリークのうち，意外な楽曲を最も多く含むもの. トル分解することで，多重ラベル間の類似性を反映した属. をここでの抽出ターゲットとし，それらを計算するための. 性部分空間を (近似的に) 同定し，そこでのデータ間の近接. 深さ優先分枝限定アルゴリズムを与える (図 1)．. 性をもとに，ラベルが未知のデータのラベル推定を行なう手法を提案した．その詳細は文献 [2] に譲るが，簡単に述. 2. 準備. べると，正規化ラプラシアン L の固有ベクトルを正の固有. 本稿では単純無向グラフ (simple undirected graph) を扱い，以降の議論ではこれを単にグラフと呼ぶ．頂点集合 V ，辺集合 E ⊆ V × V のグラフを G = (V, E) と表す．頂点 u, v ∈ V について (u, v) ∈ E である時，u と. 値が小さな方から k (< M ) 並べた N × k 行列 HM の第. ˜ i は，X 中のデータ xi の，多重ラベルの i-行ベクトル x 類似性が反映された k-次元部分空間への射影を与える *1 ．よって， T HM WTX. v は G において互いに隣接すると言う．頂点 v ∈ V につ. (1). いて，v の隣接頂点集合を NG (v) で参照する．すなわち，. なる M × k 行列 W = (w1 · · · wk ) がわかれば，ラベルが. NG (v) = {u ∈ V |(u, v) ∈ E}. 未知のデータ q ∈ RM の k-次元部分空間への射影が W T q. である．なお，議論の文脈上明らかな場合は，これを単に. N (v) と略記する．. T ˜ Ti と W T q ので与えられることから，HM の列ベクトル x. 類似性に基いて，q のラベル推定を行なうことができる．ここで，HM = (h1 · · · hk ) とすると，式 (1) は. グラフ G = (V, E) の頂点集合 X ⊆ V について，. G[X] = (X, E ∩ (X × X)) で定義されるグラフを，X. (h1 · · · hk ) (X T w1 · · · X T wk ). による G の誘導部分グラフと呼ぶ．特に，G[X] における任意の異なる頂点のペアが隣接する時，G[X] を G のク. と書けるから，こうした W は，hi X T wi の最小二乗解. リークと呼ぶ．簡単のため，クリーク G[X] を，それを誘. wi を計算することで得られる．. 導する頂点集合 X で参照する．クリーク X ⊆ V と頂点 v ∈ (V \ X) について，X ∪ {v}. データ行列 X の k-次元部分空間への射影である行列 T HM. は，正規化ラプラシアン L の固有ベクトルから得ら. がクリークである時，v を X の候補頂点と呼び，X の候. れるが，行列の固有値計算は一般に負荷が大きく，昨今の. 補頂点の集合を Cand(X) と表す．議論の対象となるグ. 大規模データを扱う際には何らかの工夫が必要となる．. ラフ G を明確にする場合は，特に CandG (X) と表記することもある．定義より，Cand(X) = v∈X N (v) であ. り，ラプラシアンの第二固有ベクトル (Fiedler ベクトル). り，特に，X ⊆ Y なるクリーク X と Y について，常に. *2. Cand(X) ⊇ Cand(Y ) となる．. は，データサイズを n として，交差数最小化問題の近似解. 互いに素な頂点集合 V0 と V1 について，E ⊆ V0 × V1 を辺集合とするグラフを二部グラフと呼び，G = (V0 , V1 , E). を O(n log n) で高速に計算可能なアルゴリズムが与えられ. と表記する．ここで，V0 と V1 をそれぞれ部集合と呼ぶ． ⓒ 2017 Information Processing Society of Japan. そこで，文献 [5] では，二部グラフの交差数最小化によ. *1 *2. の良い近似が得られることに注目した [3]．文献 [3] で. 正確には，各頂点の次数による補正操作等も必要となる．正の最小固有値に属する固有ベクトル．. 2.

(9) Vol.2017-MUS-116 No.20 2017/8/26. 情報処理学会研究報告 IPSJ SIG Technical Report. ており，これを用いることで，先の議論における k-次元部. 外性を考慮した検索・推薦を実現する．. 分空間として，k = 1，すなわち，数直線を考え，そこでの. いま，M -次元ベクトル xi ∈ RM で表現される N の楽. データ間の近接性に基づいて多重ラベル間の遠さを判定す. 曲群から成るデータベースを考え，これを M × N 行列. ることとした [5]．. X = (x1 · · · xN ) で表す．ここで，各楽曲 xi には，Ls 中のいくつかのラベル (多重ラベル) が付与されているものと. 3.2 二部グラフの交差数最小化二部グラフ G = (V0 , V1 , E) は，各部集合 Vi の頂点を，. し，それを L(xi ) (⊆ Ls) で参照する．また，クエリ楽曲を. q ∈ RM とし，特にそのラベルは未知であると仮定する．. それぞれ並行する直線 Li 上に並べ，隣接する頂点間を直線で結ぶことで図示できる．ここで，各頂点 v ∈ V0 ∪ V1. 4.1 クエリに関する意外性 [5]. に対して，対応する直線上での座標を割り当てる関数を. 文献 [5] で提案するクエリに関する意外性は，その推定. h : V0 ∪V1 → R とすると，h は G のひとつの描画 (drawing). ラベルと，データベース中の各オブジェクトに付与された. を与える．. ラベルとの遠さ (非類似性) をひとつの根拠とするもので. G のある描画 h において，辺 e ∈ E と交差する辺の総. ある．. 数を crh (e) で参照すると，描画 h における辺の交差数は ∑ cr(h) = 12 e∈E crh (e) で与えられる．G の交差数最小化. 4.1.1 ラベルの遠さ. 問題とは，h∗ = arg minh cr(h) なる描画 h∗ を求める問題. に付与された多重ラベル L(xi ) の関係を二部グラフ Glabel. である．. で表現し，その正規化ラプラシアンのスペクトル分解によ. 一方，描画関数 h により定義される G の隣接頂点間の ∑ 各直線上での座標の差分総和 Lh = (u,v)∈E |h(u) − h(v)|. り，多重ラベルの類似性が反映された最適な k-次元部分空. が最小となる頂点の並び順 (序数) を決める問題は，線形. 応する頂点を vi とする頂点集合 VX = {v1 , . . . , vN } と，ラ. 配置問題と呼ばれる．. ベル集合 Ls をそれぞれ部集合とし，辺集合 E ⊆ VX × Ls. 文献 [3] では，ラプラシアンの二次形式最小化問題として定式化される (正規化) カット最小化の意味での二部グラフの最適分割問題と線形配置問題が，ともにラプラシアン. Sun 等の手法 [2] に従うと，X 中の各楽曲 xi と，それ. 間を得ることができる．ここで，Glabel は，各楽曲 xi に対. は次の通り定義される：. E = {(vi , ℓ) | vi ∈ VX , ℓ ∈ L(xi )}.. の第二固有ベクトル (Fiedler Vector) を求めることで (近. すなわち，Glabel = (VX , Ls, E) は，各楽曲とそれに付与. 似的に) 解けること，および，交差数最小化問題の解が線. されたそれぞれのラベルを隣接関係によって表現した二部. 形配置問題のよい近似解を与えることが示された．このこ. グラフである．. とから，交差数最小化に基づく二部グラフの分割 (クラス. しかし，Glabel のラプラシアンの固有値計算はコスト. タリング) 手法が提案され，その有効性が理論的・実験的. の高い処理であることから，文献 [5] と同様に，二部グラ. に示されている [3]．文献 [5] では，そこで示された交差数最小化問題の近似. フの交差数最小化アルゴリズム [3] により，Glabel のラプ. 解を高速に求めるアルゴリズムを用いてラプラシアンの第. ラシアンの第二固有ベクトルを近似した N -次元ベクトル ˜ = (h1 , . . . , hN )T を求め，h ˜ を，多重ラベル間の類似性 h. 二固有ベクトルを近似的に求め，それをデータ行列 X の. を反映した 1-次元部分空間，すなわち，数直線 (Llabel と. 直線上 (1-次元部分空間) への射影と考えている．. する) と考える．ここで，k-次元部分空間として直線を考. 4. 意外性を有する楽曲検索・推薦のためのクラスタ抽出本節では，ラベルが未知のクエリ楽曲 q に対して，意. えることは過度な次元削減にも思えるが，ここでの目的は. q のラベルを正確に推定することではなく，あくまでも q とは遠いラベル (非類似) を有する楽曲がわかれば十分との立場である．. 外性のある楽曲を検索・推薦するタスクを，二種類の距離. より正確に述べると，Glabel の交差数最小化の結果得ら. を考慮したクラスタ抽出問題として定式化する．具体的に. れる部集合 VX 上の序数を，全単射 π : VX → {1, . . . , N } ˜ は，で表すと，h. は，データベース中の楽曲に付与された多重ラベルの類似性を反映した空間での距離と，それら楽曲が属する元の特徴量空間での距離のもとで，元の空間では q と近いという. ˜ = (π(v1 ), . . . , π(vN ))T h. 意味で関連性を有するが，q の推定ラベルとは遠いラベル. で与えられ，その各成分 π(vi ) は，行列 X 中の楽曲 xi の. を有するという意味で意外性のある楽曲を含むクラスタを. Llabel 上の座標を表す．. 抽出する．特にここでは，元の特徴量空間での楽曲間の距. ˜ T ≃ wT X なるベクトル w がわよって，式 (1) より，h. 離に基づいて類似度グラフ G を作成し，意外性のある楽曲. かれば，クエリ q の Llabel 上の座標は，wT q で与えられ ˜ ≃ X T w の最小二乗解を求めるこる．こうした w は，h. を最も多く含む G の極大クリークを列挙することで，意 ⓒ 2017 Information Processing Society of Japan. 3.

(10) Vol.2017-MUS-116 No.20 2017/8/26. 情報処理学会研究報告 IPSJ SIG Technical Report. とで同定できる．. Llabel はデータベース中の楽曲に付与された多重ラベル間の類似性を反映した数直線であるから，Llabel 上で q と. xi に対応する頂点を vi とした頂点集合 VX = {v1 , . . . , vN } について，距離 δM 以内にある楽曲間に辺を作成したものであり，形式的には次の通り定義される．. 離れて位置する楽曲は，q とは遠いラベルを有すると推測. GM = (VX , EX ),. できるだろう．ここでは，数直線 Llabel 上での楽曲間の距離に基づいて，ラベル情報の遠さを認識するものとする．具体的には，近傍パラメータ δL (> 0) を導入し，Llabel 上で δL より離れて位置する楽曲のラベルは，q のそれとは遠い (非類似である) と考える．すなわち，q と楽曲 xi について，|w q − π(vi )| > δL が成り立つ時，q と xi の T. ラベルは遠いとする．. 4.1.2 ラベルの意外性上述した通り，楽曲が有するラベルの非類似性は，数直線 Llabel 上での離れ具合により認識可能であるが，非類似. ここで. EX = {(vi , vj ) ∈ VX × VX | i ̸= j, distM (xi , xj ) ≤ δM } である．いま，q と関連する楽曲集合を {xi | distM (xi , q) ≤ δM } と定め，その対応する頂点集合を R(q) で参照する．この時，R(q) に誘導される GM の部分グラフ GM [R(q)] における極大クリークは，q と関連する楽曲から成り，かつ，それらも互いに関連し合うものとなる．. 性は必ずしも意外性を含意するものではない．クエリ q と. GM [R(q)] の極大クリークは一般に複数存在することか. の関連性が低い楽曲のラベルが，q のそれと類似しないこ. ら，こうした極大クリークを抽出対象とすることで多様. とはある意味自然であり，そこに意外性を見出すことは困. な検索結果を得ることができる．反面，特に大規模な楽曲. 難である．様々な意外性の定義が考えられるが，文献 [5]. データベースにおいては，GM [R(q)] の極大クリーク数が. では，データ行列が表現された元の空間での近接性が示唆. 膨大になることが多く，素朴な極大クリーク列挙は現実的. するオブジェクト間の関連性をもとに，関連性の高いオブ. な検索としては不十分である．より実用的な検索を実現す. ジェクト同士は多くの場合，類似するラベルを有するであ. るためには，何らかの条件を課すことで抽出すべき極大ク. ろうとの仮説のもと，クエリとの関連性が高いオブジェク. リークを絞り込む必要がある．本稿では，意外性を考慮し. トが，クエリの推定ラベルとは遠いラベルを有する時，そ. た楽曲検索・推薦を実現すべく，抽出すべき極大クリーク. れはクエリに関して意外なものであると定めた．. に対して，q に関する意外な楽曲を含むことを要請する．. 本稿でもそれに倣い，データベース X 中の楽曲が表現された元の M -次元空間において，クエリ q との関連性が. 特にここでは，意外な楽曲を最も多く含む極大クリークを列挙する問題を考えるものとする．. 高い楽曲が，q の (推定) ラベルとは遠いラベルを有する時，それは意外なものであると考え，それらを検索結果と. 定義：極大クリーク探索によるクエリに関する意外性を考. して積極的に取り込むこととする．. 慮した検索. 具体的には，元の M -次元空間における近傍パラメータ. M × N データ行列で表現される楽曲データベースを X ，. δM (> 0) を導入し，適当な距離関数 distM : RM ×RM → R. その対応する類似度グラフを GM = (VX , EX ) とする．ク. のもとで，楽曲 xi が. エリ楽曲 q ∈ RM に関する意外性を考慮した検索を，次を. 関連性制約：q と xi の関連性は高い. 満たす GM の極大クリーク C を列挙するタスクと定める．. distM (q, xi ) ≤ δM ，および，. 関連性制約：任意の vi ∈ C について，X 中の対応する. ラベルの遠さ制約：q と xi のラベルは遠い. |w q − π(vi )| > δL T. ベクトル xi は distM (q, xi ) ≤ δM を満たす．意外な楽曲数最大化：関連性制約を満たす GM の極大. を満たす時，xi はクエリ q に関して意外な楽曲であると. クリーク Q の中で，C に含まれる意外な楽曲数は最. 定める．. 大である．すなわち，こうした任意の Q について，. |C ∩ U | ≥ |Q ∩ U| である． 4.2 ラベルの意外性を考慮した極大クリーク探索による楽曲クラスタ抽出. ここで，U は q に関する意外な楽曲集合に対応する頂点集合である．. ここでは，所与のクエリに関するラベルの意外性を考慮した楽曲検索タスクを，意外性を有する楽曲を含む極大クリーク探索問題として定式化する．楽曲データベース X ∈ RM ×N とクエリ楽曲 q ∈ RM に. 4.3 意外性を有する楽曲を含む極大クリーク列挙アルゴリズム. ついて，q と関連性の高い楽曲群を同定するために，ここで. ここでは，関連性制約を満たす GM の極大クリークの. は，M -次元空間における近傍パラメータ δM (> 0) をもと. 中で，そこに含まれる意外な楽曲数が最大であるものを列. に，X の類似度グラフ GM を作成する．GM は，X の各楽曲. 挙する深さ優先分枝限定探索アルゴリズムを与える．. ⓒ 2017 Information Processing Society of Japan. 4.

(11) Vol.2017-MUS-116 No.20 2017/8/26. 情報処理学会研究報告 IPSJ SIG Technical Report. 4.3.1 極大クリーク探索の基本戦略いま，GM の頂点集合 VX = {v1 , . . . , vN } 上の全順序 ≺. 5. おわりに. を仮定し，VX の任意の部分集合の要素は，この順序に従って整列しているものとする．この時，全順序 ≺ のもとで，. VX のべき集合 2VX は，包含関係に基づいて，空集合を根とする集合列挙木で表現できる．ここで，集合 P の最終要素を tail(P ) で参照すると，親子関係にある P と P ′ において，P = P ′ \ {tail(P ′ )} が成り立つ．定義より，クリーク Q ⊆ VX の任意の部分集合はクリークであるから，根を起点として集合列挙木の各ノードを深さ優先で辿ることで，すべての極大クリークを漏れなく抽出することができる．より具体的には，クリーク P を，tail(P ) に後続する候補頂点 x ∈ Cand(P ) を用いてクリーク P ∪ {x} に拡張する処理を，∅ で初期化した頂点集合 P に対して深さ優先で繰り返せばよい．その際，. Cand(P ) = ∅ なる P が極大クリークとなる． 4.3.2 意外性を有する楽曲を含む極大クリーク探索上述した探索基本戦略に従い，ここでは，クエリとの関連性を有する楽曲から成り，かつ，意外性を有する楽曲を最も多く含む極大クリークを抽出する手続きを与える．関連性の要請から，ここでは GM の部分グラフ GM [R(q)] における極大クリーク探索を行えば十分である．抽出ターゲットである極大クリークを効率良く抽出するためには，意外な楽曲を十分な数含まない極大クリークに到達する探索ノードを，できるだけ早期に枝刈ってやればよい．いま，q に関する意外な楽曲集合に対応する頂点集合を U とすると，クリーク Q 中の意外性を有する楽曲数は |Q ∩ U| となる．ここで，Q の拡張処理は Cand(Q) 中の頂点のみが用いられることに注意すると，Q から到達可能な極大クリークが含む意外性を有する楽曲数は高々. 本稿では，意外性を考慮した検索・推薦を実現するための，形式概念探索手法を議論した．所与のクエリに対し，ラベル情報に関する意外性を有するオブジェクトを含む形式概念を抽出することで，ユーザが新たな興味を発見するきっかけを提供できるものと期待している．現在，システムの実装作業を含む計算機実験の準備を進めており，その結果については口頭発表時に報告したい．実験に用いるデータは，Million Song Datasets [6] をより有用なベンチマークデータとすべく整備した Million Song. Dataset Benchmarks [7]. 種々音響特徴量が与えられ，特にその内の約 400, 000 曲については (多重) ジャンルラベルも与えられている．実験では，これら 400, 000 曲をデータベースと考え，ジャンルが付与されていない楽曲をクエリとして検索を行なう．この場合，クエリ楽曲に対して，それと音響特徴量の点では関連 (類似) するが，遠いジャンルラベルを有するであろう意外な楽曲を含むクラスタ (群) が抽出される．なお，実験においては，前処理としてデータの次元圧縮が必要となることも考えられる．その方法や度合いは得られる検索・推薦結果を大きく左右することから，こうした影響の観察・考察を通して適切な次元圧縮の方針を得ることは重要である．参考文献 [1] [2]. |(Q ∪CandG (Q))∩ U | となる．また，Q ⊃ Q なる任意のクリーク Q′ について，(Q′ ∪ Cand(Q′ )) ⊆ (Q ∪ Cand(Q)) で [3]. なる．よって，|(Q∪Cand(Q))∩U| は，Q から到達可能な極大クリークが含む意外な楽曲数の上限を与える．これより，探索過程でそれまでに抽出された極大クリーク中の意外な楽. [4]. 曲数の最大値を max とすると，|(Q∪Cand(Q))∩U| < max なるクリーク Q からは所望の極大クリークが得られないことがわかり，以降の拡張処理を直ちに打ち切ることが可. [5]. 能となる．上記の分枝限定操作を組み込んだ探索アルゴリズムの疑. [6]. 似コードを図 2 に示す．図中，先の議論で与えた δM , δL ,. distM , w，および，π を既知のものとして用いている．なお，本疑似コードには反映されていないが，文献 [4] で議. [7]. 論された非極大なクリークに到達する不要な拡張処理の抑制機構は，ここでも有効に機能する． *3. ⓒ 2017 Information Processing Society of Japan. を考えている．そこでは，約. 1, 000, 000 曲のクロマベクトル・MFCC ベクトル等を含む. ′. あるから，|(Q′ ∪ Cand(Q′ )) ∩ U | ≤ |(Q ∪ Cand(Q)) ∩ U | と. *3. Salton, G. and McGill, M. J.: Introduction to Modern Information Retrieval, 440 pages, McGraw-Hill, 1983. Sun, L., Ji, S. and Ye, J.: Hypergraph Spectral Learning for Multi-Label Classification, Proc. of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD’08, pp. 668 – 676, 2008. Ahmad, W. and Khokhar, A.: cHawk: An Eﬃcient Biclustering Algorithm Based on Bipartite Graph Crossing Minimization, Proc. of the 2007 VLDB Workshop on Data Mining in Bioinformatics, 2007. Tomita, E., Tanaka, A. and Takahashi, H.: The WorstCase Time Complexity for Generating All Maximal Cliques and Computational Experiments, Theoretical Computer Science, 363(1), pp. 28 – 42, Elsevier, 2006. 大久保好章・原口誠・劉赫宇：意外性を持つ検索・推薦のための多重ラベル分類を用いた形式概念探索，情報処理学会研究報告，Vol. 2017-MPS-113, No. 30, 2017. Bertin-Mahieux, T, Ellis, D. P.W., Whitman, B. and Lamere, P.: The Million Song Dataset, Proceedings of The 12th International Society for Music Information Retrieval Conference - ISMIR’11, pp. 591 - 596, 2011. Schindler, A., Mayer, R. and Rauber, A.: Facilitating Comprehensive Benchmarking Experiments on the Million Song Dataset, Proceedings of The 13th International Society for Music Information Retrieval Conference - ISMIR’12, pp. 469 - 474, 2012. http://www.ifs.tuwien.ac.at/mir/msd/. 5.

(12) Vol.2017-MUS-116 No.20 2017/8/26. 情報処理学会研究報告 IPSJ SIG Technical Report. [Input] GM = (VX , EX ) : the similarity graph obtained from the data matrix X = (x1 · · · xN ) with a neighborhood parameter δM q : a query vector [Output] C : the set of maximal cliques in GM each of which consists of only relevant objects with the maximum number of unexpected ones [Global Var.] G : the subgraph of GM whose vertices correpond to objects relevant to q C : the set of target maximal cliques max : the number of unexpected objects in maximal clique previously found procedure Main(GM , q) : C←∅; R ← {vi | vi ∈ VX , distM (q, xi ) ≤ δM }; // the set of relevant objects w.r.t. q U ← {vi | vi ∈ VX , |wT q, π(vi ))| > δL } ; // the set of unexpected objects w.r.t. q max ← 0; G ← (R, EX ∩ (R × R)); // the relevant subgraph of GM Fix a total order ≺ on VX such that for any vi ∈ U and vj ∈ (VX \ U ), vi ≺ vj ; for each v ∈ U do begin MaxCliqueFind({v}, CandG ({v})); end return C ; procedure MaxCliqueFind(Q, Cand) : if Cand = ∅ then // Q is a maximal clique if |Q ∩ U | > max then C ← {Q}; else if |Q ∩ U | = max then C ← C ∪ {Q}; endif return; endif for each v ∈ Cand such that tail(Q) ≺ v do begin if |((Q ∪ {v}) ∪ CandG (Q ∪ {v})) ∩ U| < max then // branch-and-bound pruning continue; else MaxCliqueFind(Q ∪ {v}, CandG (Q ∪ {v})); endif end 図 2. ⓒ 2017 Information Processing Society of Japan. 意外性を有する楽曲を含む極大クリーク探索アルゴリズム. 6.

(13)