頻出長大パターン抽出に基づく類似楽曲検索に関する一考察

頻出長大パターン抽出に基づく類似楽曲検索に関する一考察

Finding Similar Melodies Based on Colossal Pattern Mining

大久保 好章

∗

原口 誠

Yoshiaki OKUBO

Makoto HARAGUCHI

北海道大学大学院情報科学研究科

Graduate School of Information Science and Technology, Hokkaido University

Abstract: In this paper, we are concerned with a method for retrieving objects which are similar to a given query object. Particularly, we formalize this task as a problem of finding a frequent pattern with the maximum length. The problem can be solved efficiently with an algorithm for extracting top-N colossal frequent patterns already proposed by the authors. We also discuss how to apply the proposed method to a problem of extracting similar melodies for a given query music.

1

はじめに

本稿では，検索質問として与えられたオブジェクト に対し，それと類似したオブジェクト群を出力する検 索問題について考察し，その楽曲類似検索への応用を 試みる． 近年，ビッグデータ (Big Data) への大きな期待や 関心が寄せられている通り，我々を取り巻くデータは 膨大，かつ，多種多様なものとなっている．情報検索 (Information Retrieval) は，それらデータを有効に活 用するための最も基本的な行為と考えられる．情報通 信技術の急速な発展・普及に伴い，古くは文書データ が主であった情報検索の対象は，現在では画像・音声・ 映像にまで広がっている． 音楽データを検索対象とする音楽情報検索 (MIR:

Music Information Retrieval) の分野でも，検索技術

に関する様々な試みがなされている．しかし，そこで は信号レベルの楽曲データを扱う研究が主流であり，楽 譜情報に代表される記号レベルのデータに関する考察は 極めて少ない．一方，楽曲分類 (Music Classification) においては，近年，記号レベルのデータを積極的に利 用した研究が見られ，それによる分類性能改善への期 待が高まっている (例えば文献 [7])． こうした期待を背景に，本稿では，記号レベルの楽曲 データを対象とする類似検索問題を見据え，離散的に表 現されたオブジェクトを対象とする類似検索問題を長 大頻出パターンマイニング (Colossal Frequent Pattern

Mining) [4] の枠組みで定式化し，著者等がこれまで に提案したアルゴリズム [10] を基礎に，検索結果を高 ∗_{連絡先：大久保 好章}   〒 060-0814  札幌市北区北 14 条西 9 丁目   北海道大学大学院情報科学研究科    E-mail: [email protected] 速に出力する手法を与える．楽曲類似検索における記 号レベルデータの有効性を確認することで，従来研究 のさらなる展開への足掛かりとしたい．

2

準備

アイテム (item) の集合をI とし，I の部分集合をア イテム集合 (itemset)，または，パターン (pattern) と 呼ぶ．パターン X が k のアイテムから成る時，その長 さ (length) は k であるとし，X を k-パターンと呼ぶ． 識別子 id とパターン T ⊆ I の組 (id, T ) をトランザ クション (transaction) とし，それらの集合をトランザ クションデータベース (transaction database) と呼ぶ． D をトランザクションデータベース，X をパター ンとする．X を含む D 中のトランザクションの集合 を，X の支持集合 (support set) と呼び，D(X) で表 す．すなわち，_{D(X) = {(id, T ) ∈ D | X ⊆ T } であ} る．_{D(X) 中のトランザクション総数 |D(X)| を D に} おける X の頻度 (frequency) と呼び，f req_D(X) で参 照する． 自然数 σ に対して，f req_D(X)≥ σ が成り立つ時， X は (D において)σ-頻出であると言う．σ-頻出なパ ターンの族を _Fσ(D) とし，特にその中で，集合の包 含関係のもとで極大なものを極大 σ-頻出パターンと 呼び，それらの族を _Mσ(D) で参照する．すなわち， Mσ(D) = {X ∈ Fσ(D) | ∄ Y ∈ Fσ(D) s.t. X ⊂ Y} である．極大頻出パターンマイニング (Maximal Frequent Pattern Mining) [1] とは，所与の最小頻度閾

値 σ に対してMσ(D) を同定する問題である．

人工知能学会研究会資料 SIG-FPAI-B401-11

3

長大頻出パターンマイニング

極大頻出パターンは，バイオ情報学 (Bioinformatics) をはじめとする実応用領域において有用な情報を与え るものであることが報告されている (例えば [6])．頻度 が比較的高い極大パターンは，MAFIA [2] や LCM [3] に 代表されるシステムで高速に抽出可能であるが，頻度 はさほど高くないが無視できそうにない所謂レアな極 大パターンを見つける場合は，最小頻度閾値を十分下 げる必要があり，その結果，抽出されるパターン数が 膨大になることから，既存の枠組みでは現実的な抽出 処理が極めて困難となる． こうした問題意識のもと，著者等はこれまで，極大頻 出パターンの中で特に長さが上位 N である長大なもの を抽出ターゲットとする，Top-N 長大頻出パターンマ イニング (Top-N Colossal Frequent Pattern Mining) について考察し，そのための高速アルゴリズムを設計 した [10, 11]．

定義 1 Top-N 長大頻出パターンマイニング (Top-N Colossal Frequent Pattern Mining)

D をトランザクションデータベース，σ を最小頻度閾

値，N を自然数とする．Top-N 長大頻出パターンマイ ニングとは，長さ上位 N の極大 σ-頻出パタン族

MN

σ = {X | X ∈ Mσ(D),

X has Top-N length inMσ(D) } を同定する問題である．

4

パターンマイニングに基づくオブ

ジェクトの類似検索

各トランザクション (id, T ) をひとつのオブジェクト (object or individual) と考え，単に id で参照し，T は このオブジェクトが有する属性 (特徴) 集合であると考 える． トランザクションデータベース_{D におけるパターン} X の支持集合D(X) は，X を共有するオブジェクト の集まりにほかならない．すなわち，パターン X を有 するという意味で，_{D(X) 中のオブジェクトは互いに} 類似していると解釈できる．よって，あるオブジェク トと類似するオブジェクト群を見つける処理は，その オブジェクトが有する属性のみから成るパターン P の 支持集合_{D(P ) を抽出することで実現できる．このこ} とから，本稿では，所与のオブジェクトと類似したオ ブジェクト群を同定する手法をパターンマイニングの 枠組みで定式化することで，オブジェクトの類似検索 を実現する． 所与のオブジェクト (q, Fq) について，P ⊆ Fq なる パターン P は一般に多数存在する．特に，ここでのパ ターン P は q との類似性を考える際の根拠となるも のであるから，何らかの基準でそれらを評価する必要 がある． 最も素朴には，共有属性が多いほどそれらの類似度 は高いと考えるのが自然であろう．つまり，集合の包 含関係のもとで，できるだけ大きなパターンを重視す ることで，q との類似度が高いオブジェクト群を抽出 する．ここで，パターンとその支持集合の間には次の 性質が観察される． 観察 1 任意のパターン X と Y について， X ⊆ Y ⇒ D(X) ⊇ D(Y ). パターンが大きくなるにつれ，その支持集合は小さ くなることから，類似検索により抽出したいオブジェ クト数の下限制約のもとで，できるだけ大きなパター ンを抽出するアプローチが妥当であろう．よって，検 索質問として与えられるオブジェクト q と類似するオ ブジェクトを少なくとも σ 抽出 (検索) する類似検索問 題を次の通り定義する． 定義 2 オブジェクトの類似検索問題 D をトランザクションデータベース，(q, Fq) を検索質 問として与えられるオブジェクト，σ を検索結果のオ ブジェクト数下限値とする．q に関する類似検索とは， 次の条件を満たすパターン P の支持集合D(P ) を求め る問題である． 1. P ⊆ Fq, 2. P ∈ Mσ(D), 3. ̸ ∃X ∈ Mσ(D) such that |P | < |X|. 定義中，1 は 抽出されるオブジェクト群と q との類 似性を保証するための条件，また，2 と 3 は，q と最も 類似したオブジェクト群を抽出するための条件である． これら条件を満たすパターンは一般には複数存在す る．その場合は，それらの中から任意に一つを出力す るものとする．一方，σ の値によっては，条件を満た すパターンが存在しない場合もあることに注意する． 次節では，こうした類似検索結果を高速に同定する アルゴリズムについて議論する．

5

最長頻出パターン抽出に基づく類

似検索結果の同定

D をトランザクションデータベース，(q, Fq) を検索 質問，σ を検索結果のオブジェクト数下限値とする．q

に関する類似検索結果は，素朴には，_{D を Fq} につい て射影した_D[Fq] = {(id, T ∩ Fq) | (id, T ) ∈ D} に おける最長の極大頻出パターン P により与えられる． よって，MAFIA [2] や LCM [3] に代表される高速な極大 頻出パターン抽出システムにより得られる極大パター ン族から，最長のものを後処理で抽出すれば十分であ る．しかし，これらシステムは σ が比較的大きな場合 は極めて高速に動作するが，σ が小さくなるにつれて 計算時間が急激に増大する．ここでの σ は検索結果の オブジェクト数下限値であるから，然程大きくならな いことは経験的にも明らかであり，既存システムによ り高速に検索結果を得ることは困難であることが予想 される． そこで，本稿では文献 [10, 11] で設計された，Top-N 長大頻出パターン抽出アルゴリズムを基礎に，類似検 索の実現を試みる．

5.1

Top-N 長大頻出パターン抽出アルゴリ

ズム概略

Top-N 長大頻出パターン抽出アルゴリズムは，アイ テム集合の拡張処理を基本動作とする深さ優先分枝限 定戦略を採用しており，小さな σ に対しても高速に動 作することが実験的に示されている [10, 11]．特にそこ では，パターングラフ (pattern graph) [5] が重要な役割 を担う．パターングラフは，各アイテムを頂点とする 辺重み付きの無向グラフであり，特定の長さの頻出パ ターンの情報を近似的，かつ，簡潔に表現したもので ある．(任意の長さの) 頻出パターンは，パターングラ フにおけるクリーク (clique) を形成することから，極 大頻出パターンの抽出処理が，クリーク探索の拡張と して実現される．特に，抽出ターゲットが長さ上位 N であることを利用すると，探索処理の過程で，パター ングラフをより疎なものへと動的に更新することが可 能となり，結果として，探索処理の進行に伴いより強 力な分枝限定効果が得られる． なお，詳細については文献 [10, 11] を参照されたい．

5.2

Top-N 長大頻出パターン抽出に基づく

類似検索結果の同定

本稿での類似検索結果は，最長の極大頻出パターン により与えられることから，上記の Top-N 長大頻出 パターン抽出アルゴリズムを N = 1 として実行すれば 十分である．N が小さいほど，より強力な探索の分枝 限定効果が得られることから，小さな σ においても高 速な動作が十分期待できる． またここでは，パターン抽出において考慮すべきア イテムの集合を，検索質問 (q, Fq) が有する属性集合 Fq に限定することができる．探索の基本動作はアイテ ム集合の拡張処理であるから，考慮すべきアイテム数 が少ないほど探索ノードの分枝数が少なくなり，探索 処理には極めて好都合となる． 以上をまとめると，検索質問 (q, Fq) に関する類似検 索結果を得る手順は次の通りとなる． 1. D, σ および N = 1 を入力パラメータとして Top-N 長大頻出パターン抽出アルゴリズムを実 行．ただし，探索中に考慮すべきアイテムを Fq 中のそれに限定． 2. 1 で得られた (最長) 極大頻出パターン族から，パ ターン P を任意に選択． 3. 検索結果としてD(P ) を出力．

6

楽曲の類似検索

本節では，提案手法による所与の楽曲の類似検索に ついて考察する． 提案した枠組みで類似検索を行なうには，楽曲デー タをトランザクション形式で表現する必要がある．楽 曲データは通常，音響信号情報 (WAVE 形式等)，ある いは，演奏 (楽譜) 情報 (MIDI 形式) として記録されて いるが，ここでは扱いが比較的容易な後者の MIDI 形 式を想定する．

6.1

標準 MIDI ファイルからのメロディー

抽出

MIDI 形式の楽曲データを扱う際のファイル形式は， 標準 MIDI ファイル (SMF : Standard MIDI File) と して標準化されている．本稿においてもこうした SM F を扱うものとする． SM F には，各チャンネル (楽器に対応) 毎に，その 演奏情報がデルタタイムとイベントの組の時系列とし て記述される．各組は『いつ (when)，何 (what) をす るか』を正確に定めたものであり，これら命令に従っ て対応する楽器が制御される． イベントには，MIDI イベント・SysEx イベント・メ タイベントの 3 種類が定められており，曲のメロディー に関する情報は，MIDI イベントに記述されている． 具体的にメロディーを抽出する際には，MIDI イベン トの 発音メッセージ (ノートオン) および消音メッセー ジ (ノートオフ) に注目する．前者は鍵盤を押す操作， 後者は鍵盤を離す操作に対応し，これら情報から『ど の音がどれくらいの長さ鳴っているか』がわかる．す なわち，MIDI イベントの時系列から楽譜に記載され た音符列に相当する情報が抽出できる．

形式的に述べると，各 SM F から，音名 pi とその 持続時間 ℓi の組 (pi, ℓi) の時系列をメロディーとして 抽出する．ここで，(pi, ℓi) を音符と呼ぶ．本稿では， SM F として与えられた各楽曲を，そのメロディーか ら抽出される属性の集合として扱う． なお，SM F の詳細については，文献 [8] 等を参考に されたい．

6.2

メロディーを構成する属性集合の抽出

SM F として与えられた楽曲から抽出されるメロデ ィー (音符列) を < (p1, ℓ1), . . . , (pM, ℓM) > とする．ここではメロディーを (何らかの) 属性集合と して扱うが，各音符を一つの属性と考えると音楽的な 意味が失われる．すなわち，音符の時系列性を考慮す ることが不可欠である．よって，メロディーから抽出 可能な長さ k の音符列をひとつの属性と考えることに する．具体的には，長さ M の音符列で構成されるメ ロディーの先頭から幅 k の窓を順次後方へずらすこと で，M− k + 1 の属性 f1 = < (p1, ℓ1), . . . , (pk, ℓk) > f2 = < (p2, ℓ2), . . . , (pk+1, ℓk+1) > .. . fM−k+1 = < (pM−k+1, ℓM−k+1), . . . , (pM, ℓM) > を抽出する． 提案手法では，属性集合の共有を根拠として類似楽 曲を同定するが，上記に従って抽出した属性群に対し て，異なる楽曲において複数の属性が共有されること はあまり期待できそうにない．そこで，ここでは次の 点について属性を抽象化することで，楽曲間の類似性 判断基準を緩和する1_． 持続時間の捨象： 各音符 (pi, ℓi) から，持続時間 ℓi を捨象し，音名 pi のみを考慮する． 音名の捨象： 属性 < pi1, . . . , pik> における音名 pij を捨象し，隣接する音間の音程 (interval) のみを 考慮することで，調の違いを吸収する． これにより，長さ k の音符列であった元の属性 f =< (p1, ℓ1), . . . , (pk, ℓk) > は，長さ k− 1 の音程列 ˜f =< I1, . . . , Ik₋₁> に抽象化される． 1_{文献 [9] でも議論されている通り，他にも様々な抽象化が考え} られる．例えば，隣接する音間の上下変動のみを考慮することもで きる．

6.3

楽曲類似検索

所与の楽曲の類似検索を行なうにあたり，前処理と して，SM F の集合として与えられる楽曲データベー ス中の各楽曲を，上記抽象化後の属性集合として表現 し，これを_{D とする．} 検索楽曲として与えられる SM F q から対応する (抽 象化後の) 属性集合 Fq を抽出した後，(q, Fq)，D およ び検索楽曲数下限値 σ を提案アルゴリズムに入力する ことで，楽曲 q に関する類似検索が実現される．

7

おわりに

本稿では，トランザクション形式で表現されたオブ ジェクトを対象とした類似検索問題を，長大頻出パター ンマイニングの枠組みで定式化し，その高速な計算手 法について考察した．基礎となる Top-N 長大頻出パ ターン抽出アルゴリズムを，ここでの類似検索問題に 特化した入力パラメータのもとで実行することで，極 めて高速な類似検索結果が得られることが期待できる． 提案手法による所与の楽曲の類似検索実験を現在遂行 中であり，その結果については稿を改めて報告したい． 一般には複数存在する最長頻出パターンの選択，あ るいは，類似性の根拠となるパターンの選択について は，アイテム重みを考慮するなど，さらなる考察が必 要である．楽曲類似検索においては，各楽曲に付随す るアーティスト名・ジャンル・発表年と言ったメタ情 報の利用も考察に値する． 提案手法は特定の応用分野に限定されない一般的な 枠組みであり，文書の類似検索はもちろんのこと，画 像の類似検索への応用なども興味深い．

参考文献

[1] J. Han, H. Cheng, D. Xin and X. Yan: Frequent Pattern Mining - Current Status and Future Di-rections, Data Mining and Knowledge Discovery, 15(1), pp. 55 – 86, 2007.

[2] D. Burdick, M. Calimlim, J. Flannick, J. Gehrke and T. Yiu: MAFIA: A Maximal Frequent Item-set Algorithm, IEEE Transactions on Knowledge and Data Engineering, 17(11), pp. 1490 – 1504, 2005.

[3] T. Uno, M. Kiyomi and H. Arimura: LCM ver. 2: Efficient Mining Algorithm for Frequent/Closed/Maximal Itemsets, Proc. of IEEE ICDM’04 Workshop - FIMI’04,

http://sunsite.informatik.rwth-aachen.de/ Publications/CEUR-WS//Vol-126/, 2004. [4] F. Zhu, X. Yan, J. Han, P. S. Yu and H. Cheng: Mining Colossal Frequent Patterns by Core Pat-tern Fusion, Proc. of The 23rd IEEE Int’l Conf. on Data Engineering - ICDE’07, pp. 706 – 715, 2007.

[5] Y. Xie and P. S. Yu: Max-Clique: A Top-Down Graph-Based Approach to Frequent Pat-tern Mining, Proc. of the 2010 IEEE Int’l Conf. on Data Mining - ICDM’10, pp. 1139 – 1144, 2010.

[6] R. Alves, D. S. Rodriguez-Baena and J. S. Aguilar-Ruiz: Gene Association Analysis: A Sur-vey of Frequent Pattern Mining from Gene Ex-pression Data, Briefings in Bioinformatics, 11(2), pp. 210 – 224, 2010.

[7] C. McKay and I. Fujinaga: Improving Automatic Music Classification Performance by Extracting Features from Different Types of Data, Proc. of The 11th ACM Int’l Conf. on Multimedia Infor-mation Retrieval - MIR’10, pp. 257 – 266, 2010.

[8] (社) 音楽電子事業協会 (AMEI)：MIDI 1.0 規格書 (日本語版 98.1)，リットーミュージック，1998．

[9] Y. C. Lap and B. Kao: A Study on Musical Fea-tures for Melody Databases, HKU CSIS Techni-cal Report, TR-99-05, 1999.

[10] Y. Okubo and M. Haraguchi: Finding Top-N Colossal Patterns Based on Clique Search with Dynamic Update of Graph, Proc. of The 10th Int’l Conf. on Formal Concept Analysis -ICFCA’12, LNAI-7278, pp. 244 – 259, 2012.

[11] 大久保 好章・原口 誠：動的パターングラフを用 いた Top-N 長大パターン抽出，人工知能学会研 究会資料，SIG-FPAI-B202, pp. 55 – 60, 2012.