DEIM Forum 2014 C7-3

一般化ピボット法の距離定義による特性評価
小林えり†

伏見卓恭††

斉藤和巳††

池田 哲夫††† 静岡県立大学経営上学部 〒 422–8526 静岡県静岡市駿河区谷田 52-1†† 静岡県立大学経営情報イノベーション研究科 〒 422–8526 静岡県静岡市駿河区谷田 52-1
E-mail: †{b10034,j11507,k-saito,t-ikeda}@u-shizuoka-ken.ac.jp
あらまし

類似検索の高速化を目的にピボット法が提案されており，従来のピボット法ではピボットを与えられたオブジェクト集合から選択していた．これに対し，ピボットをオブジェクト集合の中から選択するのではなく，オブジェクト空間から最適なピボットを構成する一般化ピボット法が提案されている．これまでの研究により一般化ピボット法はユークリッド距離定義，マンハッタン距離定義に対応可能となった．本論文ではそれぞれの距離定義による結果の違いに着目し，目的関数，計算時間，類似検索性能，可視化結果，４つの観点からそれぞれ距離定義を比較する．本
実験ではマンハッタン距離定義によるものが目的関数，類似検索性能の２観点において最も優れた結果を示し，また可視化結果ではデータ間の隠れた関係性の抽出に成功したことを確認した．
キーワード

類似検索，ピボット法，マンハッタン，ユークリッド

1. は じ め に

2. 類似検索問題

近年，Web 上には多量のデータが蓄積されており，与えられ類似検索には様々な手法が提案されているが，本稿ではクたクエリから類似したオブジェクトを検索する類似検索研究のエリから一定のレンジ内にあるオブジェクトを検出するレン重要性はますます高まっている．類似検索とは，クエリと類似ジクエリ問題を扱う．レンジクエリ問題は，オブジェクト集合したオブジェクトをデータベースなどの中から検出する問題を

X = {x1 , · · · , xN } とクエリ q とレンジ r が与えられたとき，指す．オブジェクト間の類似度は距離関数から求まり距離関数

q と xn の距離 d(xn , q) が r 以下となるようなオブジェクトは，非負性，対称性，および三角不等式の性質を満たす．デー集合を求める問題である．本稿では，レンジクエリ計算時間

タの多くは高次元で表現されるが，高次元空間に存在するオブを短縮させるためにピボット法を用いる．ピボット法は，オブジェクト間の距離を求めるのに大量の計算が必要となる．そのジェクト間の距離計算回数を削減し検索を高速化させるためため，類似検索ではこの計算量を削減し，検索を高速化させるに，一部のオブジェクトを選定してピボット集合を求める手法

ために一部のオブジェクトをピボット集合として選定して利用である．代表的な Bustos らの提案したインクリメンタル法でする方法が提案されている．

は, クエリ q に対し，ピボット集合 P による最大の距離下界効果的なピボット集合を選択する手法として Bustos らはインクリメンタル法を提案している [1]．このインクリメンタル法
では，より良いピボット集合の指標として目的関数を定義し，

値 D(q, xn ; P ) を次式で定義する．

D(q, xn ; P ) = max |d(q, pk ) − d(xn , pk )|1<=k <=K(1)

目的関数を最大化するようにピボットを逐次追加することでピここで，ピボット集合の k 番目の要素を pk ∈ P ，集合の要ボット集合を得る．その後も，データの分布を pivot の選択に素数を K = |P | とし，d(·, ·) は上述した元空間での距離関数利用する iDistance やその応用，またクラスタリングが意味をを表す．以下に，式 (1) の距離下界値を用いる理由について補なさないようなデータに対する pivot 分割の手法など多様な手足する．オブジェクト間の距離は距離公理の三角不等式により法が提案されている [2], [3], [4], [5]．ただし，これらは，与えら式 (2)，式 (3) が成立する．

れたオブジェクト集合の中から，その部分集合としてピボット群を選択する手法である．
これに対し，オブジェクト空間の任意の点をピボットとして求める一般化ピボット計算法も提案されている [6]．一般に，オd(q, xn ) > d(q, p) − d(xn , p)(2)d(q, xn ) > d(xn , p) − d(q, p)(3)

ブジェクト集合の中からピボット集合を選択する場合と比較し，さらに距離公理の対称性条件より次式が各ピボット pk で成立

オブジェクト空間の任意の点としてピボット集合を求めれば目し，クエリとピボットとの距離 d(q, p) からクエリとオブジェ的関数値の向上が自然に期待できる．これまでの研究により，クトとの距離 d(q, xn ) 下界値を算出することができる．

一般化ピボット法はユークリッド距離，マンハッタン距離の両方の距離定義に対応できるようになった [6] [7]．本論文ではユーd(q, xn ) > |d(q, p) − d(xn , p)|(4)

クリッド距離定義，マンハッタン距離定義による結果の違いに式 (4) ではピボット数 1 だが，これを K 個に拡張すれば式 (1)着目し，それぞれを評価していく．

が導ける．すなわち，最大下界値 D(q, xn ; P ) が r 以上のオブジェクト集合 L を以下で定義する．

を構築する．式 11 はピボット候補集合 Ū で得られた cn,k (Ū )L = {xn | D(q, xn ; P ) > r}(5)

明らかに，L に属すオブジェクト集合に対しては距離計算が不を用いて目的関数を最大化させるピボット集合を求めている．

cn,k (U ) はピボット集合が更新される度に変化するため，ピボット集合が更新されれば cn,k (U ) もまた更新される．反復によって求めた，目的関数値を向上させる更新ピボット集合を Û とす

要となるため，類似検索計算時間の短縮が期待できる．

ると以下の関係が成立する．

3. 一般化ピボット計算法
Bustos ら [1] は，より良いピボット集合の指標として目的関F (Ū ) = F(Ū |Ū ) <= F (Û |Ū ) <= F(Û |Û ) = F (Û )(12)

数を定義し，目的関数を最大化させるピボット集合を求める問

関数 F (Û ) は更新後のピボット集合 Û を用いて計算した係数題として定式化した．Bustos らの手法では，与えられたオブcn,k (Û ) での目的関数である．明らかに更新ピボット集合でのジェクト集合の中から目的関数を最大化するようなピボットを係数 cn,k (Û ) を用いたほうが目的関数の向上する．

逐次選択する (p ∈ X) [1]．

3. 1 ユークリッド距離定義に基づく一般化ピボット計算法
ユークリッド距離に基づくオブジェクト xn と xm の距離はN
∑ ∑

N −1

F (P ) =D(xn , xm ; P )(6)

n=1 m=n+1

これに対し，一般化ピボット計算法では，オブジェクト空間，次式で与えられることを確認する．

vuHu∑
d(xn , xm ) = t(xn,h − xm,h )2(13)h=1H

ここでは H 次元のユークリッド空間 (R ) の任意の点として，ピボット集合を構築する手法である (u ∈ RH ) [6]．すなわち，ここで，xn,h はオブジェクト xn の第 h 次元の値を表す．各ピ一般化ピボット計算法では，次式の F (U ) を最大にするピボッ

ボット uk (k = 1, · · · , K) を逐次代入法 (Succesive Substitution

ト集合を U = {u1 , · · · , uK } を求める．オブジェクト，および，Method) による更新で求めることが出来る．つまり，目的関数ピボットは，H 次元ベクトルで表す．

F (U |Ū ) を各ピボット uk で微分し，極値を求めることで目的関数値を改善するピボット集合 U を求める．

N∑ ∑N −1

F (U ) =max |d(xn , uk ) − d(xm , uk )|n=1 m=n+1(7)1<=k <=K∑ ck,n (Ū )∂F (U |Ū )=(xn − uk ) = 0∂ukd(xn , uk )
N(14)

n=1

すなわち，U = arg maxU F (U ) を求める問題として定式化さ

式 14 より，ピボット uk は以下の式で求めることが出来る．

れる．

∑N

いま，任意のオブジェクトのペア xn と xm に対し，ピボット uk で距離の下界値が最大化されるオブジェクトの番号のペûk =アからなる集合を以下で定義する．

ck,n (Ū )xn=1 d(xn ,uk ) n∑N(15)

ck,n (Ū )n=1 d(xn ,uk )各ピボットは式 15 で更新させていく．以下にユークリッド距Sk (U ) = {{n, m} | k = arg max |d(xn , uκ )−d(xm , uκ )|}(8)1<= κ<=K

さらに，オブジェクト番号 n に着目したとき，Sk (U ) において，n とペアで出現するオブジェクト番号の集合 Sk,n (U ) を次のように定義する．

(9)

このとき，|d(xn , uk ) − d(xm , uk )| の絶対値を距離の大小で外すとき，距離 d(xn , uk ) がプラス符号で現れる回数と，マイナス符合での回数を相殺した係数 cn,k (U ) は以下となる．

L2PVL2 距離計算：任意の n と k のペアに対して d(xn , uk )を式 (13) で計算する．
で計算する．

L2PVL4 ピボット更新 : 各ピボット uk (k = 1, · · · , K) を式 (15) により更新する．
(Ū ) <L2PVL5 判定 : F (ÛF)−F= ε となるか，反復数が最大反(Ū )復回数を超えれば終了，さもなければ，ステップ L2PVL4 へ戻る．

cn,k (U ) = |{m ∈ Sk,n (U ) | d(xn , uk ) > d(xm , uk )}|− |{m ∈ Sk,n (U ) | d(xn , uk ) < d(xm , uk )}|(10)ここで，ピボット候補集合を Ū (Ū = {ū1 · · · ūK }) とし，式 10を用いて計算した目的関数は以下のようになる．
K ∑N∑

L2PVL1 初期化 : ピボット集合 U をランダムに構築する．

L2PVL3 係数計算：各オブジェクトの係数 cn,k (Ū ) を式 (10)Sk,n (U ) = {m | {n, m} ∈ Sk (U )}F (U |Ū ) =離に基づく一般化ピボット法のアルゴリズムを示す．

本実験では ε = 10−8 とし，最大反復回数は 1000 とした．

3. 2 コサイン類似度を用いた L2 一般化ピボット計算法
本論文では比較対象として，オブジェクト間の距離にコサイン類似度を用いたユークリッド距離に基づく一般化ピボット法を加える．コサイン類似度を距離に用いた場合，オブジェクト

cn,k (Ū )d(xn , uk )(11)

k=1 n=1

詳しくは各距離定義ごとの手法説明にて記述するが，一般化ピボット法はアルゴリズムを反復することで最適なピボット集合

xn と xm の距離は次式で与えられることを確認する．

vuH∑uxn,h xm,hd(xn , xm ) = t1 −h=1∥xn ∥ ∥xm ∥(16)

N∑

オブジェクト間の距離をコサイン類似度としているため，関数式 11 には 12∑K+λ (1 − uTk uk ) の制約条件が付く．
k=1 k1∑
λk (1 − uTk uk )2m∑

KF̃ (U |Ū ) = F (U |Ū ) +(17)= uk,h (k=1−にて目的関数値を改善するピボット集合 U を求める．目的関数

F (U |Ū ) を各ピボット uk で微分すると以下の式となる．
∂ F̃ (U |Ū )
=−
∂uk

n=1

xn
−λk uk = 0d(xn , uk ) ∥xn ∥(18)∥∑N

ck,n (Ū ) xn∥
n=1 d(xn ,uk ) ∥xn ∥(19)n=1

ものと同様のアルゴリズムで求める．

3. 3 マンハッタン距離定義に基づく一般化ピボット計算法

cn,k (Ū )xn,h(23).

n=m+1での和については，何も加算されず 0 を意味するものとする．
式 (23) より，目的関数 F(uk,h |Ū ) は区分線形となることが分和は 0 になる．

cn,k (Ū ) = 0

次式で与えられることを確認する．

(24)

n=1

よって，uk,h < x1,h ならば，目的関数 F (uk,h |Ū ) は次式の一定値となる．

マンハッタン距離に基づくオブジェクト xn と xm の距離はd(xn , xm ) =N∑

ただし，n = 1 から m = 0 までの和や，n = N + 1 から N まN∑

目的関数の最適化は式 (19) を用いてユークリッド距離でのH∑cn,k (Ū )xn,h +ら減算される回数を引いたものであり，全オブジェクトでの総∑N
uk =cn,k (Ū ))n=m+1

かる．ここで，係数 cn,k (Ū ) は d(xn , uk ) が加算される回数かピボット uk は式 18 より以下の式で更新される．
ck,n (Ū ) xn
n=1 d(xn ,uk ) ∥xn ∥m∑N∑cn,k (Ū ) −n=1

ユークリッド距離に基づく一般化ピボット法同様，逐次代入法

N∑
ck,n (Ū )cn,k (Ū )(xn,h − uk,h )n=m+1

F (uk,h |Ū ) =N∑

cn,k (Ū )xn,h(25)n=1|xn,h − xm,h |(20)h=1

ここで，xn,h はオブジェクト xn の第 h 次元の値を表す．また，マンハッタン距離定義で最適化する目的関数の表現は，ユーク
リッド距離定義によるもの [6] と同様に式 (7) となることに注意されたい．ここで式 (11) は以下のように書き換えることが出来る．

また，xN,h < uk,h ならば，次式となる．

F (uk,h |Ū ) = −N∑cn,k (Ū )xn,h(26)n=1

したがって，目的関数 F(uk,h |Ū ) の最大値は，区分線形式の交点 {x1,h , · · · , xN,h } のどれかで与えられる．すなわち，ピボッ
ト k の第 h 座標値の更新式は以下となる．

F (U |Ū ) =KN∑∑

cn,k (Ū )d(xn , uk )ûk,h = arg

k=1 n=1=KHN∑∑∑=∑∑F(xn,h |Ū )(27)

明らかに，更新後のピボット集合を Û で表せば，F (Ū ) <= F(Û )cn,k (Ū )|xn,h − uk,h |の関係が成り立つ．一方，上述しているように，各ピボットのk=1 h=1 n=1
Kmax{xn,h | 1<=n<=N }各次元での値の取り得る値の範囲は，有限離散点に限定される．

HF(uk,h |Ū )(21)

k=1 h=1

よって，提案法は，常に有限回の反復で収束することが保証される．

すなわち, F (uk,h |Ū ) は次式で定義される．

F (uk,h |Ū ) =N∑

cn,k (Ū )|xn,h − uk,h |

(22)

n=1

式 (7) で定義した目的関数の最大化は，各 uk,h に対し，独立に式 22 を最大化できることが分かる．
以下には，式 (22) の最大化法について述べる．いま，オブジェクト番号は x1,h <= ··· <
= xN,h となるよう再設定したとする．また，便宜上，x0,h = −∞，xN +1,h = ∞ とする．このとき，m = 0, · · · , N とし，xm,h < uk,h < xm+1,h に対して，
式 (22) は次のように変形できる．

F (uk,h |Ū ) =m∑
n=1

cn,k (Ū )(uk,h − xn,h )図1

目的関数 F(uk,h )図 1 には，目的関数 F (uk,h |Ū ) のイメージを示す．すなわ
ち，縦軸には目的関数値，横軸に ukh のとりうる値を設定したグラフである．図 1 の示すように目的関数 F(uk,h ) は，各オるのは妥当ではない．そのためそれぞれの手法の理論値を分母ブジェクトの第 h 座標値において傾きを変える．この図では，に用いて，評価関数を以下のように定義した．

x7,h で目的関数 F (uk,h |Ū ) は最大化される．以下に，L1PVL法と呼び提案アルゴリズムを示す．

F (U )
G(U ) = ∑N −1 ∑N
n=1

m=n+1d(xn , xm )× 100(28)L1PVL1 初期化 : ピボット集合 U をランダムに構築する．

すなわち，一般化ピボット法による距離下限値の良さをパーセ

L1PVL2 ソート : 各次元 h ごとにオブジェクトの座標値 xn,hントで評価する．G(U ) が高いほど元空間でのデータ量を保持を昇順にソートする．

した結果であると言える．

L1PVL3 距離計算：任意の n と k のペアに対して d(xn , uk )図 2(a) に示した MNIST の結果から，L1PVL 法がどの手を式 (20) で計算する．

法よりも高い目的関数値を算出しており，最も元空間での情報

L1PVL4 係数計算：各オブジェクトの係数 cn,k (Ū ) を式 (10)を保持した結果であることがわかった．L2PVL 法と cL2PVLで計算する．

法の結果を比較してみると，ピボット構成の際，制約のかかる

L1PVL5 ピボット更新 : 任意の k と h のペアに対して uk,hcL2PVL 法よりも L2PVL 法の方が高い目的関数値を算出してを式 (27) で計算する．

いるのが確認できる．しかしながら L1PVL 法と比較するとど

L1PVL6 判定 : L2PVL 法と同様の終了条件を満たせば終了，のピボット数のときでも 10 ％以上下回る結果であった．

さもなければ，ステップ PVL3 へ戻る．

図 2(b) に示した毎日新聞の結果から，こちらも L1PVL 法

ここで，式 (27) のピボット更新により，目的関数 (11) の値をが最も高い目的関数値を算出し，L2PVL 法と cL2PVL 法の結改善させることができるとともに，ピボットの更新値は有限集果を比較しても，cL2PVL 法よりも L2PVL 法の方が高い目的合に限定される．よって，上記アルゴリズムは有限反復回数で関数値を算出しているのが確認できた．毎日新聞の結果の場合，終了することが保証される．すなわち，上記アルゴリズムの反L1PVL 法の結果が他の手法に比べて圧倒的に高い目的関数値

復で目的関数 (11) を最大化するピボット集合 U を構成できる．

を示し，ピボット数が K = 10 の場合，約 30 ％近く他の手法4. 実験による評価を上回っていることが確認できる．
両データとも cL2PVL 法はもっとも関数値の低い結果となっ4. 1 実験データたが，これは cL2PVL 法はピボットを一定の範囲内の中から構実験データとして MNIST と 毎日新聞 を用いた．目的関数，成しなければならないために，制約のない，つまりは無限空間類似検索性能，可視化結果で用いたオブジェクトはランダムにの中からピボットを構築する L1PVl 法，L2PVL 法と比較して10, 000 オブジェクト抽出したものを使用している．

低い目的関数値となってしまったのだと考えられる．

MNIST は 手 書 き 文 字 認 識 用 デ ー タ ベ ー ス の こ と で あ

4. 3 計算時間の比較

り，”0,1,2,3,4,5,6,7,8,9”の 10 のクラスにより表されている．

図 3 に，計算時間での結果を示す．横軸はオブジェクト数を

これらの 10digits の手書き文字の 1 つが，28 × 28=784 画素表し，縦軸が計算時間を秒単位で表わしている．図 2 と同様に，各画素 0〜255 の 256 階調グレースケールで表されている．に，赤線で L1PVL 法を，青線で L2PVL 法，緑線で cL2PVL

すなわち，各文字は 784 次元のベクトルで表現される．

法を表すとともに，K はピボット数を表し，今回はピボット数

毎日新聞 は日本の新聞会社のひとつであり，本実験では，が 1，10 のときの結果を評価する．

1992 年から 2002 年の国際関係の記事のみを実験対象としてい図 3(a) に示した MNIST の結果から，L2PVL 法，cL2PVLる．オブジェクトを単語頻度ベクトルとし，次元数は記事内に法，L1PVL 法の順に短い計算時間で結果を算出していること出てきたターム数，51,030 とする．例えばオブジェクト xn のが分かる．L2PVL 法はピボット数に関わらず，他の手法と比記事内に”国”という単語が 2 回出現した場合，”国”に対応するべて非常に時間がかかっているのが分かる．各手法のアルゴリ

次元 (仮に h = 1 を”国”に対応する次元とする) の要素を 2，つズム反復終了条件は，更新によって向上する目的関数値が収束

まり xn,1 = 2 とし，オブジェクトベクトル xn を決定していく．

するか，反復回数が上限 (本実験では 1000 回) を上回る，の２以下では，これらデータを用いて目的関数，計算時間，可視つである．L1PVL 法，cL2PVL 法は前者の条件で終了してい化結果，類似検索性能４つの観点からマンハッタン距離定義にるが，L2PVL 法は後者の条件で終了している．そのため他の基づく一般化ピボット法 (以下 L1PVL 法)，ユークリッド距離手法でのアルゴリズム反復回数は 50〜100 回に対し，L2PVL定義に基づく一般化ピボット法 (以下 L2PVL 法)，コサイン類法は上限の 1000 回であり，ゆえに他の手法と比べて圧倒的に似度を用いたユークリッド距離定義に基づく一般化ピボット法

時間がかかってしまったのだと考えられる．

(以下 cL2PVL 法) の 3 手法を比較する．

図 3(b) に示した毎日新聞の結果より，L2PVL 法，L1PVL

4. 2 目的関数の比較法，cL2PVL 法の順に短い計算時間で結果を算出していること

図 2 に目的関数での結果を示す．横軸はピボット数を，縦が分かる．こちらのデータセットでも L2PVL 法の結果は他の軸は目的関数値を表している．赤線で L1PVL 法を，青線で手法よりも非常に時間がかかっており，他 2 手法に対して反復

L2PVL 法，緑線で cL2PVL 法の結果を示す．ただし，一般に回数が多いことが原因であると考えられる．L1PVL 法は一概

マンハッタン距離定義による目的関数値よりユークリッド距離にどの手法よりも高速に結果を算出できる，というわけではな

定義による目的関数値の方が大きくなるため，そのまま比較すく次元数が多いデータセットの場合だと多少時間がかかってし(b) 毎日新聞(a) MNIST
図2 目的関数(b) 毎日新聞(a) MNIST
図3 計算時間(b) 毎日新聞(a) MNIST
図4

レンジクエリ(a) L1PVL 法(a) L1PVL 法(b) L2PVL 法(b) L2PVL 法(c) cL2PVL 法(c) cL2PVL 法

図 5 MNIST での可視化結果

図 6 毎日新聞での可視化結果

まうことが分かった．

とまって近傍にプロットされているのが分かり，他の手法と比4. 4 類似検索性能の比較

べてジャンルごとにまとまってプロットされた結果だと確認で

図 4 に，レンジクエリ問題における類似検索性能の観点で 3きた．また選挙など”政治”関連の記事は左下にプロットされて手法を比較した結果を示す．横軸はレンジ r を表し，縦軸におり，”テロ”や”紛争問題”は全体に広がっているのが確認できはレンジ r としたとき，式 (5) で定義した集合 L を求め，枝る．下にプロットされた記事は総単語数が多く，そのため文字刈り成功率 |L|/N を表している．すなわち，縦軸の値が高け数の多い，特集記事や論評などが多かった．逆に，結果だけをれば高いほど効果的な枝刈りが実現できることになる．これま記事とする株価変動やスポーツの記事は総単語数が少ないため

でと同様に，赤線で L1PVL 法を，青線で L2PVL 法，緑線でに上側にプロットされている．図 6(b) から L2PVL 法の結果

cL2PVL 法を表しており，K はピボット数を表し，今回はピを見てみると下側に”テロ”，”紛争問題”などが抽出され，右端ボット数が 1，10 のときの結果を評価する．には”中国”，”台湾”，”北朝鮮”の 3 か国に関する記事が抽出さ

図 2(a) に示した MNIST の結果を見てみると，K = 1 の場れた可視化結果となった．収集期間ではテロ・紛争問題や中国・合，最も目的関数値が向上した L1PVL 法はどの手法よりも高台湾・北朝鮮関連の記事が多数記述されたために，その他の記い枝刈り成功率を算出していることが分かる．K = 10 の結事間との距離が広がり，それ故にそれ以外の記事は密集した結果の場合，レンジ距離 r = 1.0 近くでは L1PVL 法はわずかに果となったと考えられる．図 6(c) から cL2PVL 法の結果を見

L2PVL 法より高い枝刈り成功率を示している．また cL2PVLてみると，上側には政治関連の記事，詳しくは”大統領”のワー法はもっとも目的関数値が小さかったため，効率的な枝刈りをドが入った記事がまとまって抽出され，右端にはロシア関連の期待できるとは言い難い結果となった．

記事が多く見られた．収集期間の時期は 1991 年にソビエト連

図 3(b) に示した毎日新聞の結果では，MNIST よりもピボッ邦が崩壊しロシア連邦が成立する，などロシア関連の記事が多ト数，レンジ距離に関わらず各手法間に明確な差が生じている．

い時期でもあったため他の記事との距離が広がり抽出されやす

ピボット数に関わらず最も高い目的関数値を算出した L1PVLかったのではないかと考えられる．

法が最もデータの散らばった結果であると定量的に評価できる．
よって，L1PVL 法は 3 手法の中で最も効果的な枝刈りを期待できる．L2PVL 法と cL2PVL 法の結果を比較してみると，よ5. 考察

本実験にて，L2PVL 法は L1PVL 法よりも圧倒的に時間がり目的関数値が向上している L2PVL 法の結果の方が効率的なかかっているのに目的関数値は L1PVL 法を大きく下回った結枝刈りが見込めることが分かった．

果となっている．図 7 はアルゴリズム反復ごとのピボット uk

4. 5 可視化による評価のノルム ∥uk ∥ を表し，図 8 はアルゴリズム反復ごとの目的関

図 5 に示した MNIST の結果については，オブジェクト数値を表している．図 7，図 8 から L2PVL 法は最適なピボッは”0,1,2,3,4,5,6,7,8,9”の 10 のクラスにより色分けされている．

トを発見出来ていないのではないかと考えられる．L1PVL 法

図 5(a) から結果を見てみると L1PVL 法がもっともデータが全は早い段階で最適ピボットに近づくことが出来たため，図 7 に体的に散らばった可視化結果であり，効果的な枝刈りが期待で

おいて L1PVL 法の ∥uk ∥ はどのピボット数でもすぐに水平なきると分かる．L1PVL 法はクラス”1”と”0”のオブジェクトがグラフとなり，反復回数も少ない量で済んでいる．L1PVL 法

他のクラスと重ならずにまとまってプロットされている．”1”はアルゴリズムから反復回数が有限であることが保証されていや”0”ほどはっきりとは分別できないが比較的同じクラス同士はるため，局所改善によって最適ピボットを求める L2PVL 法よ

散らばらずに近傍にプロットされている．図 5(b) から L2PVL1りも最適ピボットの発見が容易である．これに対し，L2PVL法の結果を見てみるとクラス”1”，”2”，”7”が他のクラスと被法は図 7 からピボットのノルム ∥uk ∥ は反復によって常に変化らずにまとまってプロットされているのが分かる．また形のし続けており，最大反復回数を迎えてもいまだピボットは更新似ている”7”，”9”，”4”や，”0”，”6”などは近傍にプロットさし続けているため，最適なピボットを見つけていないのが分かれている．図 5(c) から cL2PVL 法の結果を見てみるとクラる．つまり L2PVL 法は最適なピボットを発見出来なかったた

ス”7”，”0”が他のクラスとは被らずにまとまってプロットされめに目的関数が伸び悩んだのだと判断できる．そのため最大ているのが分かる．L2PVL 法と同様，同一クラス同士，形の反復回数を増やせば目的関数の向上が期待できるかもしれな

似ているクラス同士は比較的近傍にプロットされているのが確

いが，図 3 の示す通り計算時間が膨大な量になってしまうた

認できた．

め，実用的ではないと考えられる．図 7， 8 には載せていない

次に図 6 に示した毎日新聞の結果を評価する．オブジェク

が cL2PVL 法に関して，こちらも L2PVL 法同様，局所改善

トは記事のジャンルによって色分けされており，収集期間の時によって最適ピボット集合を求める手法であるが，こちらはピ期は北朝鮮のテポドン発射，アメリカの同時多発テロ問題，イボット構成の際，無限空間からではなく，制約された有限空間ラク戦争などの紛争問題，などといった，”北朝鮮関連”，”核の中から構成されるため，L2PVL 法よりも最適ピボット見つ問題”，”テロ・紛争問題”が多い時期であったことを考慮されけやすい環境にある．しかしながら有限空間でのピボット構成たい．図 6(a) から L1PVL 法の結果を見てみると他の手法とのために目的関数値が伸び悩むという欠点が確認された．

比べてデータが全体的に満遍なく広がった可視化結果となった．”スポーツ”，”金融”，”兵器”と”核”といったジャンルはま(b) 毎日新聞(a) MNIST
図7

反復による ∥pk ∥ の更新(b) 毎日新聞(a) MNIST
図8

反復による目的関数値の更新

6. お わ り に[2]

本論文ではマンハッタン距離定義，ユークリッド距離に基づく一般化ピボット法の結果の違いに着目し，目的関数，計算時間，類似検索性能，可視化結果，以上の４つの観点からそれぞ[3]れを比較した．マンハッタン距離定義に基づく一般化ピボット法はユークリッド距離のものよりも高い目的関数値を算出しており，効果的な枝刈りの期待できることが分かった．また，デー[4]タ間の隠れた関係性を発見することのできる可視化結果を確認でき，今回の実験ではマンハッタン距離定義に基づく手法の有[5]効性を発見することが出来た．今後は，距離定義を混合したようなデータに対応する，混合型一般化ピボット法の提案を行う．

[6]

謝辞

[7]

本研究は，科学研究費補助金基盤研究 (C)(No.23500128)の補助を受けた.
文

献[1] B. Bustos, G. Navarro, and E. Chavez.: ”Pivot Selection Techniques for Proximity Searching in Metric Spaces”,

Pattern Recognition Lettes, Vol.24, No.14, pp. 2357-2366(2003)
E. Chevez and G. Navarro, A compact space decomposition
for eﬀective metric indexing, Pattern Recognition Letters,
24(9), pp.1363-1376, 2005 (2005)
H. V. Jagadish, B. C. Ooi, K. L. Tran, C. Yu and R. Zhang,idistance: Anadaptive b+-tree based indexing method fornearest neighbor search, ACMTODS, 30(2), pp.364-397,2003 (2003)
H. Kurasawa, D. Fukagawa, A. Takasu and J. Adachi, Pivot
selection method for optimizing both pruning and balancing
in metric space indexes, Proc. DEXA, 2010 (2010)
Y. Zhuang, Y. Zhuang, Q. Li, L. Chen and Y. Yu, Indexing
high-dimensional data in dual distance spaces: a symmetrical encoding approach, Proc. EDBT, 2008 (2008)
木村 学，斉藤和巳，池田哲夫，上田修功: ”効率的な類似検索のためのピボット学習法”，情報処理学会論文誌，Vol.50, No.8，1883-1891（2009）小林 えり，伏見 卓恭，斉藤和巳，池田哲夫: ”マンハッタン距離に基づく一般化ピボット計算法”，”第 6 回 Web とデータベースに関するフォーラム（WebDB2013），Nov.2013.（2013）