DEIM Forum 2016 D7-3

共通要素数を重視したハッシュベース集合間類似検索
板橋 大樹†

古賀久志†

Gibran FUENTES PINEDA††戸田 貴久†† 電気通信大学大学院情報システム学研究科 〒 182–8585 東京都調布市調布ケ丘 1-5-1†† Universidad Nacional Autonoma de Mexico Delegacion Coyoacan Mexico, D.F. 04510 Mexico
E-mail: †{itabashi,koga,takahisa.toda}@sd.is.uec.ac.jp, ††gibranfp@unam.mx
あらまし 集合間の類似検索をハッシュで実現する手法として Min-Hash が知られている．Min-Hash ではクエリ集合に対して Jaccard 係数が高い集合を発見できる．しかし，クエリ集合と共通要素が多い集合であっても，要素数がクエリ集合よりある程度大きい場合は，Jaccard 係数の定義から類似度が低下し発見が困難になる．そこで本研究では，共通要素が多い集合を発見するための Min-Hash の改良手法を提案する．本手法を画像データベースから発見されたオブジェクトへの自動タグ付けに適用して，その有効性を示す．
キーワード

ハッシュ，集合間類似検索，タグ付き画像
有効性を示した．

1. は じ め に

本論文の構成を以下に示す．2 章では Min-Hash を紹介し，3集合は様々な現実問題に対する対象を表現できる実用性が高章で共通要素数を重視した類似検索を定義し，問題の有用性にいデータ構造である．近年，多様な応用分野で，データを集合とついて述べる．4 章では提案手法を述べる．5 章では提案手法

して表現し，パターン分類やパターン認識を行うことが盛んにを実験により評価し，6 章でまとめを述べる．

行われており，集合間類似検索の重要性が増している．例えば，テキストをそれが含む単語集合として表現すれば，集合間類似

2. Min-Hash

検索により，与えられたテキストと内容が関連したテキストを

Min-Hash は Jaccard 係数を類似度とする集合間類似検索の発見できる．このような背景の下，集合間類似検索の高速化のための確率的なハッシュアルゴリズムである．本節では Min-

ニーズも高まっている．Min-Hash [1] はハッシュを用いて集合

Hash の概要を述べる．集合要素の種類数を D とし，要素の識間類似検索を高速に実現する手法である．ハッシュとはデータ別子の集合を P = {1, 2, 3, · · · , D} とする．Min-Hash におけ探索アルゴリズムの 1 つで，データをハッシュ値と呼ばれる整るハッシュ関数 mh を作るには，まず，ランダムに決定した P数に変換し，ハッシュ値の比較のみで高速なデータ探索を実現の要素の順番を入れ替える置換 π を用意する．そして，集合 A

する．集合間類似度はさまざまな定義があるが，Min-Hash はの要素群を π に従って入れ替え後，最初に出現する要素の識別

Jaccard 係数に基づく類似検索を対象とする．ここで 2 つの集

子を A のハッシュ値 mh(A) とする (式 (2))．

合 A と B の Jaccard 係数は式 (1) で定義される．

sim(A, B) =|A ∩ B|.
|A ∪ B|mh(A) = min(π(A))
(1)

(2)

例えば，D = 4 で，P = {1, 2, 3, 4}，π = {4, 3, 1, 2} とす

Min-Hash では，2 集合のハッシュ値が衝突する確率が Jaccard

る ．こ の 時 ，集 合 A = {1, 2, 3} を π に 従って 入 れ 替 え た

係数と等しく，クエリ集合に対して Jaccard 係数が大きな集合

π(A) = {3, 1, 2} となり，mh(A) = 3 となる．

をハッシュテーブルを使って発見できる．しかし，Min-Hash
は Jaccard 係数に基づくため，クエリ集合と共通要素が多い集合であっても，集合の要素数がクエリ集合よりもある程度大きい場合は，ハッシュ衝突確率が低下して発見できない．

Min-Hash ではハッシュ値が衝突する確率は Jaccard 係数と等しくなる (式 (3))．

P [mh(A) = mh(B)] = sim(A, B).

(3)

そこで本研究では，共通要素を多く含む集合をハッシュをMin-Hash を 用 い た 類 似 検 索 の 概 要 を 図 1 に 示 す．ま使って発見する手法の実現を目的とする．本研究ではこの目的

ず，ラ ン ダ ム に 選 択 す る π が 異 な る r 種 類 の ハッシュを Min-Hash を僅かに修正するだけで達成する．提案手法では，

関 数 mh1 , mh2 , · · · , mhr を 用 意 し ．r 個 の ハッシュ値 を

2 つの集合の要素数の違いが 共通要素数とは無関係に Jaccard

連 結 し て 出 力 す る 関 数 を g と す る ．つ ま り，g(A) =係数を低下させるという事実に着目し，要素数の多い集合を部(mh1 (A), mh2 (A), · · · , mhr (A))．このような g を l 種類用意

分集合に分割して，それぞれの部分集合をハッシュテーブルにし，g1 , g2 , · · · , gl とする．そして，l 個のハッシュテーブル

登録する. この方法により，ハッシュ値の衝突確率は要素数のT1 , T2 , ..., Tl を作成する．その後，集合データベース内のすべ違いに依存しにくくなり，その結果として，共通要素数によりての集合 Xi を l 個のハッシュテーブルに登録する．Xi はハッ強く依存するようにできる．提案手法を画像データベースからシュテーブル Tj (1 <=j<= l) 上でインデックス値が gj (Xi ) と発見された画像オブジェクトの自動タグ付けに適用して，そのなるバケツ b(gj (Xi )) に格納される．

図 1 Min-Hash による類似検索

図 2 VW の出現画像集合

クエリ集合 Q に対する類似検索は以下の手順で実行される．

3 回，窓に対応する v6 が 2 回出現している．よって，頻出する

まず，Q のハッシュ値 g1 (Q), g2 (Q), · · · , gl (Q) を計算する．そVW の集合 {v1 , v2 , v3 , v6 } を発見すれば，「家」オブジェクトがして，各ハッシュテーブル Tj のバケツ b(gj (q)) に格納されて見つかる．

いる集合群を，Q に対する類似集合の候補とする．これらの類[8] では Min-Hash を用いて頻出 VW 集合を高速発見した．

似集合候補に対してのみクエリ Q との Jaccard 係数を正確に具体的には，オブジェクトに対応する頻出 VW 集合の要素は，計算し、最終的に類似集合を決定する．

当該オブジェクトが出現する度に互いに共起することに着目しMin-Hash の拡張手法も盛んに研究されている．Chum ら [2]た．VW v に対して，v が出現する画像群を v の出現画像集合

は Min-Hash をマルチセットを取り扱えるように拡張した．[3]Sv と呼ぶ．共起性が高い VW 同士は同じ画像に出現するので，

では集合の要素順を入れ替えた後，最初と最後に出現する 2 要

出現画像集合の Jaccard 係数が高くなる．例えば，図 2 の左半

素をハッシュ値とすることでハッシュテーブル数を半分に減ら分は各 VW に対する出現画像集合である．
「家」オブジェクトのした．b-bit Minwise Hashing [4] はハッシュ値の下意 b bit だ

構成要素 v1 , v2 , v3 の出現画像集合はどれも {I1 , I2 , I3 } であり，けを使うことで空間計算量を劇的に減らす手法である．

Jaccard 係数は sim(v1 , v2 ) = sim(v2 , v3 ) = sim(v3 , v1 ) = 1 と

2. 1 応 用 例なり，高い値になる．窓に対応する v6 は I2 , I3 にしか出現しな

Min-Hash は様々な応用分野に適用されている．[2] では近似

いが，やはり v1 , v2 , v3 との共起性が高く，例えば v1 と v6 との複製画像 (near duplidate image) の検索に Min-Hash を使用しJaccard 係数は 23 = 0.67 となり，やはり大きい．そこで，出現た．また，木やグラフなど構造を持つデータを部分構造の集合

画像集合に Min-Hash を適用し，同一ハッシュバケツに入ったとして表し，類似検索を Min-Hash で高速に実現する研究も見

VW 群を取り出す．この VW 群は，互いに出現画像集合が類られる [5] [6]．Sigure Hash [7] では Min-Hash を類似数式の検似した共起する VW であるので，[8] ではこれをオブジェクトモ

索に適用した．

デルとした（注 1）．

以下では，本論文と関連の深い Gibran ら [8] による画像集合
からの自動画像オブジェクト発見手法を詳述する．この手法で3. 共通要素類似検索

は，同じオブジェクトが写った画像には同じパターンが出現す

本研究では，クエリ集合 A と要素を多く共有する集合 B をることに着目し，複数画像に頻出するパターンを意味のあるオ

発見する類似検索の実現を目的とする．端的に言うと，本研究

ブジェクトとして抽出する．N 枚の画像集合を {I1 , I2 , ..., IN }では集合間類似度がとする．

い．ここで，分母 |A| はクエリ集合のみに依存するので，結局，まず，N 枚の画像から局所特徴点を抽出する．各特徴点は多次元特徴ベクトルとして記述される．全特徴点を k-means 法|A∩B|という条件で類似検索を実現した|A|

分子 |A ∩ B| が大きな集合 B を見つければよい．本論文ではこの検索を共通要素類似検索と名付ける．

などでクラスタリングして得られる k 個のクラスタを Visual

Min-Hash が基盤とする Jaccard 係数は |A ∩ B| に比例する．

Word (以下，VW) と呼ぶ．個々の特徴点は，量子化により

しかし，|A ∩ B| が大きくても，B の要素数がクエリ集合 A のVW として表現できる．この状況で，オブジェクトは頻出す

要素数よりもある程度大きい場合は，Jaccard 係数が低下してる VW の集合を抽出することで発見できる．図 2 を例に説明

Min-Hash で B を発見するのは困難になる．例えば，B の要素
数が A の要素数の α 倍 (α > 1) である時，|A ∩ B| <= |A|, かする．図 2 の I1 , I2 , I3 は 3 枚の画像であり，v1 , v2 , · · · , v8 はVW である．すべての画像に「家」オブジェクトが出現しており，「家」オブジェクトの屋根，壁，煙突に対応する v1 , v2 , v3 が

（注 1）：実際には，この後で後処理が実行されるが説明は省略する

1
つ |A ∪ B| >= α|A| であることから，sim(A, B) <= α が確定する．このように，Min-Hash は共通要素類似検索に対して万全ではない．共通要素類似検索の応用例を以下に 2 つ述べる．
（ 1 ） テキスト検索：

1 章で述べたようにテキストの類似検索は，テキストを単語集合として表現することで集合間類似検索に帰着できる．ここでテキスト A と，一部分が酷似したテキスト B を探す類似検索を考えてみよう．このような検索は剽窃検知で必要性が高い．
この検索では，A と B の共通単語数 |A ∩ B| が大きな集合 Bを探すべきであるが，Min Hash では B の長さが A より十分長いと Jaccard 係数が低下して B を見落とすことになる．極端なケースでは，B が A を完全に内包していても，B の長さ
が A の長さの 10 倍, すなわち |B| = 10|A| であれば，Jaccard
係数は 0.1 と低い値になり，Min-Hash で B を発見できないということも起こり得る．
（ 2 ） 画像オブジェクトモデルへの自動タグ付け：

図 3 部分集合への分割

2. 1 章で紹介した Gibran らの手法では，出現画像集合が類似した VW 群を画像オブジェクトモデルとする．そして，Jaccard

最後に要素数 T 未満の部分集合が残る場合は，他の部分集合の係数を集合間類似度としている．
画像集合を定義できるので，出現画像集合が類似した VW 群

1 つとマージする．この結果，部分集合の要素数はT 未満にな⌊ ⌋|B|らない．また，部分集合の数は個になる．これらの部Tとタグ群を凝集することにより，発見された画像オブジェクト

分集合を B 1 , B 2 , . . . , B

モデルにタグ情報を使った自動アノテーションが可能になると（ 2 ） それぞれの部分集合に対して計算したハッシュ値の集考えられる．我々もこのアプローチを試みたが，Min-Hash を合を元の集合 B のハッシュ値とする．すなわち，使った場合は VW 群と同じハッシュバケツに入るタグが非常にハッシュ値

もし入力がタグ付き画像集合であれば，タグに対しても出現少なく，VW と出現画像集合が類似したタグ群を適切に発見で⌊ |B| ⌋Tとする．

mh(B 1 ), mh(B 2 ) . . . , mh(Bきなかった．この原因は，一般的に VW の出現画像集合の要素⌊ |B| ⌋
T

個の⌊ |B| ⌋
T)

数に対し，タグの出現画像集合の要素数は数倍から十数倍にもが，B のハッシュ値である．図 3 にハッシュ値の計算例を示す．

なるためである．タグはセマンティクスを表現するため，1 つ

データベースに登録する集合は要素数が 2T 以上であれば全のタグが多様な画像パターンに対応することが多く，タグの出て分割対象になる．Min-Hash と同様に，ハッシュテーブルの現画像集合は VW の出現画像集合より要素数が大きい．この

index は r 個のハッシュ値を連結したものを使用する．そして，

結果，VW とタグのペアが複数画像で共起しても，Jaccard 係

ハッシュテーブルは l 個用意する．1 個の部分集合は l 個のハッ数は低く同じハッシュ値にならず見落とされる．

シュテーブルに 1 度ずつ登録される．クエリ集合については

本研究を開始したきっかけはこの問題を解決することであり，分割を行うオプションと行わないオプションを設ける．アプリ

5 章の実験では，画像オブジェクトモデルへの自動タグ付けにケーションによっては，クエリ集合の要素数が少ないことがあ

提案手法を適用した結果を報告する．

らかじめわかっている場合があり，そのような場合は分割を実

4. 提 案 手 法

施しない．
類似検索を行う際には，クエリ集合 A を分割しない場合は，

Min-Hash では 2 集合間で要素数が大きく異なると，(共通要A のハッシュ値とデータベースに登録された集合 B の部分集合

素数によらず) ハッシュ衝突確率が低くなる．この事実を鑑み，のハッシュ値のどれかが衝突する場合，B を A の類似集合候提案手法の基本アイデアは要素数の差が生じないように要素数補とする．A を分割する場合は，A の部分集合のハッシュ値との多い集合は部分集合に分割してハッシュテーブルに登録する

B の部分集合のハッシュ値が 1 回以上衝突する場合に，B を類というものである．これはシンプルな考え方であり，Min-Hash

似集合候補とする．

を僅かに変更するだけで容易に実装できる．しかも，後述する
ように共通要素類似検索に適した強力な性質を持つ．
提案手法における集合 B のハッシュ値の計算手順は次のようになる．なお，閾値 T は提案手法のチューニングパラメータで本論文では，以降クエリ集合を分割しない場合に限定して議論する．

4. 1 理 論 解 析
共通要素数に依らず，Min-Hash では要素数が異なる集合間ある．

のハッシュ衝突確率が低下する．とくに，A と B の要素数の差（ 1 ） B の要素数が閾値 T よりも大きい場合，互いに素な要が大きくなるほどハッシュ衝突確率は減少し 0 に近づく．これ

素数 T の部分集合にランダムに分割する．ただし分割の結果，に対して，提案手法では要素数が大きい集合を部分集合へ分割

することで，A と B の要素数の差が大きくてもハッシュ衝突

実は，1−f (β) は B を β 個の部分集合に分割した時に A と Bの部分集合のどれかが Min-Hash でハッシュ値が衝突する確率確率の減少を抑えられる．このことを理論的に示す．
以下の議論では簡単のため，集合 A の要素数を T , 集合 B のである．集合 B を β 個の部分集合 B i (1 <=i<= β) に分割し, 共要素数を αT (α は 2 以上の自然数)，A と B の共通要素数を

通要素が部分集合に均等配分されると仮定すると，|B i | = αT
，
β

k(1 <
=k<
= T ) とする．つまり，B のみが提案手法で部分集合|A ∩ B i | = βk になる．この時，A と部分集合 B i のハッシュに分割される．

βk= (α+β)T
衝突確率は．P [mh(A) = mh(B i )] = T + αT
.
−k
−k

k

β

4. 1. 1 集合分割によるハッシュ衝突確率の増加

β

よって，β 個の部分集合のどれかと A のハッシュが衝突する確

まず，提案手法が要素数が大きい集合のハッシュ衝突確率を上げることを示す．以下では，提案手法でハッシュ値が衝突する確率を P [imh(A) = imh(B)] と記述する．これは A と B の部分集合のどれかが Min-Hash によりハッシュ値が衝突する確率である．
［Theorem 1］ 提案手法で A と B のハッシュ値が衝突する確率 P [imh(A) = imh(B)] は，Min-Hash でハッシュ値が衝突する確率 P [mh(A) = mh(B)] より大きい．
証明: 式 (3) より，P [mh(A) = mh(B)] は以下のように計算で
きる．

(

k
率は，1 − 1 − (α+β)T−k)β= 1 − f (β).

4. 1. 2 共通要素数，集合要素数とハッシュ衝突確率1 − f (β) は β に関して単調増加であるという事は，分割数が多いほど A と B の部分集合のどれかのハッシュ値が衝突する
確率が増加するということを意味する．ここで，提案手法は要素数が多い集合ほど多数の部分集合に分割するため，共通要素
数とは無関係に，要素数が多い集合のハッシュ値の衝突確率を上昇させる可能性が危惧される．提案手法ではそのようなことが発生しないことを以下に示す．

B と C を 2 つの集合とする．B の要素数を αT ，C の要素数k
P [mh(A) = mh(B)] = sim(A, B) =T + αT − kk=.
(α + 1)T − k

を α′ T とする (α, α′ は異なる自然数)．一般性を失わず α < α′と仮定する．

(4)［Theorem 2］ |A ∩ B| = |A ∩ C| =| 0 であれば，P [imh(A) =次に P [imh(A) = imh(B)] を考える．提案手法では，B を

α 個の部分集合 B i (1 <=i<= α) に分割する．共通要素が α 個の部分集合に均等配分されると仮定すると，B i の要素数は T ，Akとの共通要素数は αになる．この時，A と部分集合 B i のハッ

シュ値が衝突する確率は式 (5) になる．式 (5) は，α >= 2 より式 (4) より小さい．つまり，個々の部分集合 B i は元の集合 B

imh(B)] > P [imh(A) = imh(C)].
つまり，共通要素数が等しい場合には要素数が大きいほどハッシュ衝突確率が下がる．共通要素数が等しいという条件下では，

A と非共通な要素を C の方が B より多く含むのでこの性質は人間の直感にも合致する．
証明: 式 (6) が α > 1 の条件で，α に関して単調減少であるこ

2とから言える．単調減少性の証明は省略する．

よりもハッシュ衝突確率が小さくなる．

さらに Theorem 2 より次の定理も成り立つ．

P [mh(A) = mh(B i )] =kα

T + T − αk=k.
2αT − k［Theorem 3］ |A ∩ B| > |A ∩ C| であれば，P [imh(A) =(5)

imh(B)] > P [imh(A) = imh(C)].

P [imh(A) = imh(B)] は α 個の部分集合のどれかと A のらと言って，共通要素数が多く部分集合数が少ない集合 B より

ハッシュ値が衝突する確率であり，式 (6) で表される．

(

P [imh(A) = imh(B)] = 1 − 1 −k
2αT − kこの定理は，共通要素数が少ない集合 C が部分集合数が多いか)αもハッシュ衝突確率が高くならないことを保証する．

.

(6)

4. 2 共通要素類似検索への適性

Theorem 1 を示すには，式 (6) が式 (4) より大きいことを示提案手法が共通要素類似検索に適した性質を持つことを説明せばよい．これは以下の Lemma1 を用いて示せる．Lemma1

する．Theorem 2 より，P [imh(A) = imh(B)] は α に関しての証明は省略する.

単調減少であるが，α → ∞ で定数に収束する．収束値は(［Lemma 1］ 実数 β に関する関数(
f (β) =

1−k(α + β)T − klim 1 − 1 −

α→∞

)β

(

= lim 1 −α→∞P [mh(A) = mh(B)], P [imh(A) = imh(B)] は，それぞれ以下のように f を使って記述できる．

= lim 1 −α→∞

= lim 1 −P [mh(A) = mh(B)] = 1 − f (1).

(7)

P [imh(A) = imh(B)] = 1 − f (α).

(8)

α→∞

k

= 1 − e− 2T

1
α
−1
k

)α

)α

1 − 2T((はβ>= 1 の条件で，β に関して単調減少する．

k
2αT − k1
1 − 2T
α−1k) 2T α
) 2T
α−1
α−1
k
k

( ) 2T α
1
e

k

α−1

(9)

であり，α には依存せず，共通要素数 k にのみ依存する．従っLemma 1 より，f は β に関して単調減少するので，f (1) > f (α).

て，提案手法では，要素数がある程度大きい 2 つの集合 B,

2

C が A とハッシュが衝突する確率 P [imh(A) = imh(B)] とゆえに，P [mh(A) = mh(B)] < P [imh(A) = imh(B)].

P [imh(A) = imh(C)] の大小関係は共通要素数 |A ∩ B| と|A ∩ C| の大小によって決定される．Min-Hash で，式 (4) のP [mh(A) = mh(B)] が α → ∞ で k の値に依らず 0 に収束するのと比較して，提案手法は共通要素類似検索に適している．
提案手法は α に関して収束が早いことが望まれるが，そのシミュレーション実験の結果を図 4，図 5 に示す．図 4 はMin-Hash のハッシュ衝突確率 (式 (4))，図 5 は提案手法のハッシュ衝突確率 (式 (6)) をプロットしたものである．縦軸がP [mh(A) = mh(B)]，P [imh(A) = imh(B)]，横軸が α である．それぞれ共通要素数 k を変えて複数の曲線がプロットされている．
このグラフから以下のことが読み取れる．まず，Min-Hash
は α が大きくなるにつれてハッシュ衝突確率が k に依らず 0 に収束する．このことは Min-Hash では集合の要素数が多い集合
図 4 Min-Hash のハッシュ衝突確率

は共通要素数によらず発見できないことを示している．
一方，提案手法はハッシュ衝突確率が k に応じて異なる定数に収束し，k が大きいほど収束値が大きい．このことから，集合の要素数がある程度大きければ，ハッシュ衝突確率はもはや要素数の違いに依存せず，共通要素数にのみ支配されることがわかる．しかも，ハッシュ衝突確率の収束は早く，k の値によらず α = 5 程度で収束する．とくに，k = T4 より小さい場合
はハッシュ確率は α によらずほぼ水平線である．つまり，集合の要素数によらず，共通要素数 k が大きいほどハッシュ衝突確率が大きくなっており，共通要素類似検索が理想とする状態になっている．

4. 3 共通要素数の偏りの平坦化
本章で述べた理論解析は共通要素が B の部分集合に均等配分されると仮定している．現実には B はランダムに分割されるため，部分集合への共通要素の配分に偏りが生じ，理論解析

図 5 提案手法のハッシュ衝突確率からずれる可能性がある．この問題を緩和するため，提案手法
ではハッシュテーブルによって，ランダムに生成する部分集合を変更する．l 個のハッシュテーブル T1 , T2 , · · · , Tl が使用されたは 0.1 ％以下に出現する VW を削除する．
タグに関しては，データセット内の全てのタグを収集し，30るので，B の γ 種類の部分集合への分割方法を用意し，1 種類％以上，または 0.5 ％以下の全タグ付き画像に出現するタグをの分割方法を γl 個のハッシュテーブルに適用する．

削除する．さらに，2 文字未満あるいは 12 文字よりも長いタ

5. 実 験 評 価グ，日本語とアルファベット以外を含むタグを削除する．以上
により，4048 種類のタグが 394 種類に削減される．

本章では，提案手法を 2. 1 章で述べた画像オブジェクトモデ
ルの自動タグ付けに適用し，定性評価，定量評価を行う．

以上の手順を経て残った VW とタグに対して出現画像集合を作成する．VW に対する出現画像集合の平均要素数は 18 で

5. 1 実験で使用するタグ付き画像集合

あるのに対し，タグに対する出現画像集合の要素数は 200 を超画像投稿サービス Flickr から，建物の名前をクエリとしてえるものも存在する．出現画像集合の要素数が大きいタグは重画像を収集する．クエリは【Big Ben】,【Petronas Tower】,【Statue of Liberty】, 【Taj Mahal】, 【Tower Bridge】,【コ

要なタグであることが多い．

5. 2 定量評価：共通要素数とハッシュ衝突回数の相関

クーンタワー】，【金閣寺】，【五重塔】，【東京スカイツリー】，【東

本実験では，VW をクエリとし，出現画像集合が似たタグを京タワー】の 10 単語で，各単語につき 200 枚ずつ，合計 2000

検索する．Min-Hash と提案手法を用いて検索し，共通要素数枚のタグ付き画像からなるデータセットを作成した．データが多いタグを発見する能力を評価する．とくに，共通要素数がセット内の画像から MSER 特徴点 [9] を抽出し，それを SIFT

多いタグほどハッシュ衝突回数が多くなっているかを調査した．

記述子 [10] で記述して 128 次元ベクトルとする．全特徴点をク

具体的には各 VW に対して，

ラスタリングして VW を得る．得られた VW の中で極端に多•共通要素数順に並べたタグの順位リスト

く，あるいは極端に少ない画像に出現する VW は削除した．具•ハッシュ衝突回数順に並べたタグの順位リスト

体的には，データセットの全タグ付き画像中で，30 ％以上，まを生成し，それが相関を持つかを調べた．相関が高いほど，共通要素数が多いタグがハッシュ衝突する傾向があると言える．
本実験では，16384 個の VW から頻出に出現するものと稀にしか出現しないものを削除し，さらに，出現画像集合の要素数
が 10 未満の VW は削除する．これにより，VW の数は 9599
個となる．

Min-Hash のパラメータは，ハッシュテーブルの数 l は 250,
500, 1k, 2k, 4k, 40k, 200k の 7 パターン，ハッシュ関数 g を構成するハッシュ関数 mh の数 r = 3 とする．提案手法の集合
分割閾値 T は, VW に対する出現画像集合の平均要素数である

18 とした．また 4.3 章で述べたように，提案手法では共通要素の分布の偏り抑制のため，タグに対する出現画像集合を γ = 10l
通りの異なる方法で分割し，それぞれ 10個のハッシュテーブ

ルに適用する．
図 6 スピアマンの順位相関係数

VW v に対するハッシュ衝突回数順に並べたタグの順位リス
トは，全てのタグとのハッシュテーブル上での衝突回数を計測することで求める．各タグ t が l 個のハッシュバケツ b(gj (v))

けが明確になったことで，順位相関係数が上昇する．ハッシュ

(1 <
= j <
= l) に入った回数 (衝突回数) を求め，衝突回数順に

テーブル数 200k は現実的な値ではないが，確率の不安定さにソートすることでタグの順位リストを得る．

影響されずに順位相関係数を得るという目的の下では適切な値

共通要素数順に並べたタグの順位リストとハッシュ衝突回数順に並べたタグの順位リストの相関は，スピアマンの順位相である．

5. 3 定性評価：画像オブジェクトモデルへのタグ付け

関係数により評価する．スピアマンの順位相関係数とは順位

Gibran らの手法 [8] で発見された画像オブジェクトモデルにデータから求められる相関の指標である．同順位 (タイ) があ

自動タグ付けを実施し，提案手法が有効なタグを発見できるか

る順位データ X ，Y の場合，Dif を同じアイテムの X, Y でを定性的に評価する．本実験では，32768 個の VW から頻出にの順位の変位，タイの個数をそれぞれ Nx , Ny ，それらの順位

出現するものと稀にしか出現しないものを削除した 23560 個のを ti , tj (i = 1, 2, ..., Nx , j = 1, 2, ..., Ny ) としたとき，スピアマ

VW を入力とする．これらの VW に対する出現画像集合の要ンの順位相関係数 ρ は式 (10) で定義される．

素数の平均値は 11 である．

ρ =Tx + Ty − ΣDif 2√

2 Tx Ty

まず，Gibran らの手法 [8] により Min-Hash を使って出現画(10)

N − N − Σ(t3i − ti )12
N 3 − N − Σ(t3j − tj )
Ty =
12
3

Tx =

像集合が似た VW をクラスタリングし，画像オブジェクトモ
デルを得る．Min-Hash のパラメータは r =5，ハッシュテーブ
ル数 l =500 とした．ここでは通常の Min-Hash を使っており，提案手法とは無関係である．

•

画像オブジェクトモデルへの自動タグ付け

ハッシュテーブル数 l を変更した時の，全ての VW に対す

画像オブジェクトモデル O は VW の集合になっている．オるスピアマンの順位相関係数の平均値を図 6 に示す．この図よブジェクトモデル O をタグ付けするため，v ∈ O をクエリとしり，提案手法の方が Min-Hash よりも順位相関係数が高く共通て出現画像集合が似たタグを検索し，v とタグ t のハッシュ値が要素類似検索により適することが確認できた．提案手法では衝突した時，オブジェクトモデル O にタグ t を付与する．集合

ハッシュテーブルの数が増えるに連れ，順位相関係数が増加す

間類似検索の手法として，Min-Hash と提案手法を適用し，タる．特に，提案手法でハッシュテーブル数を 200k としたとき，グ付け結果を比較する．提案手法での集合分割閾値 T は，VW

一般的に強い相関が認められる 0.7 に近い値となる．このことに対する出現画像集合の要素数の平均値である 11 とした．なから，かなり高い精度で共通要素類似検索が実現できると言え

お，本実験では，4.3 章で述べたハッシュテーブルごとに部分る．一方，Min-Hash の順位相関係数はハッシュテーブル数に集合を変更することは行わず，全てのハッシュテーブルに同じ依らず 0.1 前後に止まる．

部分集合を登録する．

提案手法でハッシュテーブル数が少ない時に相関係数が低い
理由は，集合をハッシュテーブルに登録する回数が少ないため，

以下に画像オブジェクトモデルへの自動タグ付けの結果の事
例を 3 つ示す．

順位付けに十分な回数のハッシュ衝突が発生しないからである．

画像オブジェクトモデルを構成する VW とその出現画像集

つまり，ハッシュ衝突確率に関わらず，どのタグも数回程度し合の要素数を，表 1 ：【東京スカイツリー】，表 3 ：【コクーン

かハッシュ衝突しないので，同順位 (タイ) のタグが大量に存

タワー】，表 5 ：【tajmahal】に示す．

在し，順位付けが困難になってしまう．ハッシュテーブル数が

画像オブジェクトモデルに Min-Hash と提案手法を適用して増えると，ハッシュ衝突回数が増えて分解能が上がり，順位付付与されたタグと，タグの出現画像集合の要素数，画像オブジェクトを構成する全 VW とのハッシュ衝突回数の合計値，共

表 1 画像オブジェクトモデル【東京スカイツリー】

通要素数の合計値を表 2 ：【東京スカイツリー】，表 4 ：【コクー

VW Index

v2419

v7142

v13057v17781v18074ンタワー】，表 6 ：【tajmahal】に示す．

集合要素数

4

4

10

6

10

オブジェクトを代表する画像を，図 7 ：【東京スカイツリー】，
図8：【コクーンタワー】，図 9 ：【tajmahal】に示す．画像と表 2 オブジェクト【東京スカイツリー】：自動タグ付け結果
タグ

集合要素数

衝突回数

共通要素数

ソニー

16

3

11

従来手法で発見

fuji

16

3

2

(提案手法でも発見)

曇り

15

1

2

ツアイス

10

7

10

画像オブジェクトモデルが共有する VW の数を基に画像を順位付けし，その上位 3 枚の画像を画像オブジェクトに対する代
表画像とした．
オブジェクト【tajmahal】の考察を行う．Min-Hash では，

alpha

10

5

11

【life】，【love】のようにオブジェクトに関連しないタグのみが付

tokyo

488

1

19

与された．これらのタグは共通要素数はそれぞれ 4 個，2 個と多

night

202

1

11

東京スカイツリー

201

5

22

skytree

144

6

15

スカイツリー102

1

20

landmark

60

1

3

sony

58

6

12

fujifilm

58

1

3

cloud

31

3

2

Min-Hash で発見されなかったが，提案手法では発見できてい

zeiss

22

3

10

る．この事実は，提案手法が集合の要素数の差に依存せず，共

曇り

15

1

2

くない．しかし，出現画像集合の要素数が少ないため，Jaccard
係数が高くなり，ハッシュ衝突が発生した．一方，提案手法では【tajmahal】，【india】，【agra】のようにオブジェクトに関連提案手法で発見するタグが付与された．これらのタグは共通要素数が多いにも関わらず，VW の出現画像集合との要素数が大きく違うため

通要素数が多い集合を発見できたことを意味し，提案手法が共通要素類似検索を可能にしたと言える．
他の 2 つのオブジェクトの例でも同様に，提案手法はオブジェクトに深く関連するタグを適切に付与できた．この理由はやはり，タグの出現画像集合が VW に対する出現画像集合の数倍から数十倍の要素を持っていても，提案手法では VW に対する出現画像集合との共通要素数が多ければ発見できるためである．

6. ま と め
集合間の類似検索をハッシュで実現する手法として Min-Hashが知られている．Min-Hash は Jaccard 係数を集合間類似度とするため，クエリ集合と共通要素が多い集合でも，要素数がク

図 7 オブジェクト【東京スカイツリー】の代表画像

エリ集合よりある程度大きい場合には，類似度が低下してハッ表 3 画像オブジェクトモデル【コクーンタワー】

シュ衝突確率が減るため，発見が困難になる．そこで本研究はVW Indexv13233v14054v14087v19851v22163

集合の要素数に依らず，クエリ集合と共通要素が多い集合を発

集合要素数

7

4

4

6

4

見する共通要素類似検索の実現を目的とした．
提案手法では，要素数が閾値以上の集合を部分集合に分割し

表4

オブジェクト【コクーンタワー】：自動タグ付け結果
タグ

集合要素数

衝突回数

共通要素数

ビル

39

1

6

従来手法で発見

mode

16

1

1

(提案手法でも発見)

gakuen12

21

design11

1

1

くなる状況を回避するのが基本アイデアである．理論的にも

grass

10

1

1

Min-Hash と比較してハッシュ衝突確率が集合の要素数の違い

japan

491

1

12

に依存しにくく，共通要素数に強く依存することを示した．

tokyo

488

4

21

日本

331

2

2

コクーンタワー

200

5

25

て，それぞれの部分集合に Min-Hash を適用する．Min-Hashの僅かな改良で実現することができ，実装が容易であるという長所を持つ．部分集合への分割により，集合要素数の差が大き提案手法をタグ付き画像データベースから発見された画像オ
ブジェクトへの自動タグ付けに適用し，Min-Hash よりも提案
手法が良好なタグを付与できることを定性的に示した．さらに定量評価も行い，クエリ集合 A と発見された集合 B のハッシュ
衝突回数が，|A ∩ B| と強い相関を持つことも示した．今後の提案手法で発見

新宿

134

6

16

shinjuku

127

4

12

building

121

1

7

cocoontower

117

2

19

東京モード学園

71

4

14

課題としては，画像アノテーション以外の応用分野へ提案手法

新宿区

31

4

5

を適用することが挙げられる．

tky

26

4

5

shinjukuku

23

4

5

文

図 8 オブジェクト【コクーンタワー】の代表画像
表 5 画像オブジェクトモデル【tajmahal】
VW Index

v3504

v9941

v23292

集合要素数

6

7

12

表 6 オブジェクト【tajmahal】：自動タグ付け結果
タグ

集合要素数

衝突回数

共通要素数

従来手法で発見

love

17

4

4

(提案手法でも発見)

life

10

2

2

tajmahal

200

6

25

提案手法で発見

図9

謝

india

170

4

25

travel

157

1

10

agra

155

2

23

landscape

67

1

3

sky

66

2

5

taj

47

3

5

street40

1

2

tourist24

1

1

オブジェクト【tajmahal】の代表画像

辞本研究は科学研究費基盤研究 (C) 課題番号 15K00148 の支援を受けて行った．

献[1] E. Cohen, M. Datar, S. Fujiwara, A. Gionis, P. Indyk, R.
Motwani, J.D. Ullman, and C. Yang, “Finding interesting
associations without support pruning”, IEEE Transactions
on Knowledge and Data Engineering, vol.13, no.1, pp.64–
78, 2001.
[2] O. Chum, J. Philbin and A. Zisserman, “Near Duplicate Image Detection: Min-Hash and Tf-Idf Weighting”, in Proc.
of BMVC, 2008.
[3] J. Ji, J. Li, S. Yan, Q.Tian and B. Zhang, “Min-Max Hash
for Jaccard Similarity”, in Proc. IEEE ICDM 2013, pp.301–
309, 2013.
[4] P.Li and A.C. König “b-Bit minwise hashing”, in Proc.
WWW 2010, pp.671–680. 2010.
[5] C.H.C. Teixeira, A. Silva and W. Meira Jr., “Min-Hash Fingerprints for Graph Kernels: A Trade-oﬀ among Accuracy,
Eﬃciency, and Compression”, J. of Information and DataManagement 3(3): pp.227-242, 2012.
[6] S. Tatikonda and Srinivasan Parthasarathy, “Hashing treestructured data: Methods and application”, in Proc. IEEEICDE 2010, pp.429-440.
[7] 大橋 駿介, 相澤 彰子 “SIGUREHash:数式検索のための高速な
類似検索アルゴリズム”, DEIM Forum 2015.
[8] G. F. PINEDA，H. Koga and T. WATANABE，“Scalable
Object Discovery: A Hash-based Approach to Clustering
Co-occurring Visual Words”, IEICE Trans. on Informationand Systems，Vol.E94-D(10)，pp.2024–2035, 2011.
[9] J. Matas, O. Chum, M. Urban, and T. Pajdla, “Robust
wide baseline stereo from maximally stable extremal regions,” Proceedings of the British Machine Vision Conference, pp.384–393, 2002.
[10] D.G. Lowe, “Distinctive image features from scale-invariant
keypoints,” International Journal of Computer Vision,
vol.60, no.2 ,pp.91–110, 2004.