DEIM Forum 2013 D6-4

オブジェクト可視化と類似検索性能による頑健線形射影法の評価
小林 えり†

伏見 卓恭††

斉藤 和巳†,††

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

高次元データの次元圧縮は重要な研究課題であり，縮小写像を実現する代表的な埋め込み手法として主成分分析があげられる．しかしデータ内には外れ値が存在し，結果に影響を与え頑健性を損ねてしまう場合がある．本
論文では，代表的な既存埋め込み法と同様に元空間でのオブジェクト間の関係をできるだけ保持した縮小写像を実現し，かつ，次元圧縮の頑健性を向上させることを目的に開発した，頑健線形射影法を提案する．提案法はアイテム間の距離に絶対値を採用しており，外れ値に対して頑健性があることが期待できる．提案法をレビューサイトから収集したアイテム集合を用いて可視化結果と類似検索性能の面から定量的に評価し，主成分分析と比較して提案法により優れた次元圧縮結果が得られたことを示す．
キーワード

主成分分析，外れ値，頑健性，低次元埋め込み，高次元ベクトル，類似検索，可視化，縮小写像

Eri KOBAYASHI† , Takayasu FUSHIMI†† , Kazumi SAITO†,†† , and Tetsuo IKEDA†,††† School of Management and Information, University of Shizuoka
52-1 Yada, Suruga-ku, Shizuoka 422–8526, Japan†† Graduate School of Management and Information of Innovation, University of Shizuoka
52-1 Yada, Suruga-ku, Shizuoka 422–8526, Japan
E-mail: †{b10034,j11507,k-saito,t-ikeda}@u-shizuoka-ken.ac.jp

1. は じ め にタの散らばり具合を最大にするような射影軸を求めるために，分散共分散行列の最大固有値を求めることで計算する．しかし近年，Ｗｅｂ上には膨大な量のデータが蓄積されており，そデータ内には外れ値が存在することがあり，外れ値との距離がれらを有効活用するためには，データ間の関係や特性を把握す強く影響し，頑健な結果が得られない場合がある．そこで代表ることは一層重要になっている. 画像や音声，映像などに代表的な既存埋め込み法と同様に元空間でのオブジェクト間の関係されるマルチメディアデータの多くは高次元ベクトルで表現でをできるだけ保持した縮小写像を実現し，かつ，この外れ値にき，高次元ベクトルで定義されたオブジェクト集合を低次元ベ対して頑健性のある頑健線形射影法（以下 RLP 法）を提案す

クトルに埋め込むことはデータの隠れた構造やオブジェクト間る. RLP 法は，射影後のデータの散らばり具合として絶対値をの関係を視覚的に把握するために重要なことである [1] [2]. さら用いて計算するため，外れ値に対して頑健であることが期待でに，蓄積された膨大な量のデータから，与えられたクエリと類きる．

似するオブジェクトを検索する類似検索の研究は，非常に重要

本論文では，2 つのレビューサイトから収集したアイテム集になってきている．類似検索においては，クエリからある範囲合をオブジェクトとして用い既存手法である主成分分析と提案内のオブジェクトを検索するレンジクエリ問題があるが，高次手法である RLP 法に対して，低次元空間への射影結果に関し元空間から低次元空間への縮小写像を実現できれば，レンジ内て，可視化結果と類似検索の観点から定量的に評価する．に存在するオブジェクトをある程度枝刈りでき，レンジクエリ

本論文の構成は以下のとおりである．2 節で RLP 法につい検索の効率化が図れる [3] [4]．RLP 法ならびに PCA 法は縮小て説明し，3 節でレビューサイトのアイテムデータを用いて両写像であるため，圧縮した低次元空間でのノード間の距離は元手法を比較，評価する．4 節で本論文のまとめと今後の展望に空間 (高次元空間) での距離よりも小さくなることが言える．高

ついて述べる．

次元データの低次元空間への埋め込み法の代表例として，主成分分析（以下 PCA 法） [1] があげられる. PCA 法では，デー（ 1 ） 初期化：s = 0， ws をランダムに初期化；

2. 頑健線形射影法（ 2 ） 射影：||ws || = 1 と正規化し，x = wsT Z で元空間座

RLP 法は，PCA 法と同様に，射影後のデータの散らばり標ベクトル群 Z を ws へ射影する；具合が最大となる射影軸を求める手法である．以下の小節で，（ 3 ） ソート：射影後の値 x によりオブジェクトを降順ソーRLP 法のアイデアとアルゴリズム，その特徴について述べる．

トし，ソート後のオブジェクト順序リストを r 構築する；

2. 1 提案法のアイデア（ 4 ） 更新：射影軸を ŵs+1 =入力として元空間の座標ベクトル群 Z を用いる．(Z =更新する．

(z1 · · · zN )) 元空間の座標ベクトル群を射影軸 w に射影した値∑Nk=1T（ 5 ） 判定：目的関数値 v = ŵs+1(N − 2k + 1)zr(k) と∑N
k=1(N − 2k + 1)zr(k)を成分とする埋め込み射影値ベクトル x を出力とする．射影軸が収束すれば x = wT Z を出力し終了，さもなければ s ← s + 1w は以下の目的関数 R(w) を最大化するように求める．とし 2. へ；N∑ ∑T T
出力 : 埋め込み座標ベクトル群 X = (xT
1 , · · · xL )N −1

R(w) =|w zi − w zj |TT(1)

i=1 j=i+1

ここで，N は全オブジェクト数，||w|| = 1 である．元空間ベクトル Z を求められた w に射影し，埋め込み射影値ベクトルx = wT Z を決定する．目的関数 1 は，絶対値を用いている点
で PCA 法の 目的関数 2 よりノイズに対して頑健であると期待できる．
N∑ ∑(wT zi − wT zj)2(2)i=1 j=i+1

また，目的関数 1 は，絶対値関数を最大化する問題であるため，PCA 法の場合と異なり微分することにより最適化することができない．しかし，全オブジェクトを射影後の座標値 wT ziによって降順にソートすることで，目的関数を以下のように書き換えることができる．
N∑ ∑ゴリズムを実行することにより求めることができる．

2. 3 頑健線形射影法の特徴
RLP 法には以下の 3 点の特徴があげられる．まず始めに絶る．次に，ソートすることによりアルゴリズム全体の計算量を軽減している点である．単純に全オブジェクト間の距離（類似度）を計算するには，オブジェクト数の自乗オーダー（O(N 2 )）の時間計算量がかかる．提案アルゴリズムでは，射影後の値でオブジェクトを降順ソートし，オブジェクト数のオーダーで目的関数値を計算できるため，アルゴリズム全体の時間計算量はなっている．最後に RLP 法は，反復ごとに射影軸 w の改善が|wT zi − wT zj |数学的に保証されているため，射影軸 w について収束の保証

i=1 j=i+1= (N − 1)w zr(1) + (N − 2)w zr(2) − w zr(2) + · · ·T

PCA 法と比較して外れ値による影響が小さくなると考えられソートにかかる O(N log N ) となり，効率的なアルゴリズムにN −1

R(w) =る際には，既に求めた射影軸 w の直交補空間において，アル対値を距離として採用しているため，自乗値を距離としている

N −1

P(w) =

上述したアルゴリズムにより，射影後のバラつきが最大となるような射影軸 w を求めることができる．第 2 軸以降を求め

TT= (N − 1)wT zr(1) + (N − 3)wT zr(2) + · · ·性が期待できる．

3. 実験による評価∑N= wT

RLP 法，および，PCA 法に対して，以下で説明するレビュー(N − 2k + 1)zr(k)サイトのアイテム集合を用いて評価する．

k=1

ここで r は，射影後の値を降順ソートした順序リストであり，

3. 1 実験データ

r(k) は順位が k 番目のオブジェクトを表す．この目的関数，す本 稿 で は@cosme，ア ニ コ レ を 実 験 デ ー タ と し て 用 い た.

なわち射影軸 w との内積を最大となるのは，求める射影軸が@cosme [5] は，化粧品をアイテムとしたレビューサイトであり，(N − 2k + 1)zr(k) と同じ方向を向くときである．従って，2008 年 12 月から 2009 年 12 月にかけてクロールして取得し∑N

k=1ŵ ∝N∑

(N − 2k + 1)zr(k)たものである．48,548 アイテム，45,024 ユーザー，331,084 レ(3)k=1を得る．

ビューを有する. 本稿ではレビュー数の多い上位 1,000 アイテ
ムを評価対象とした.
アニコレ [6] は，アニメをアイテムとしたレビューサイトで2. 2 アルゴリズムあり，2012 年 8 月 8 日に取得したものである．1,790 アイテ

目的関数を最大化するには，射影後の値により降順ソートすム，13,111 ユーザー，299,887 レビューを有する.

る必要があり，また，降順ソートするには，射影軸 w を求めアイテム数を N ，ユーザ数を M とし，アイテム i へのユーる必要があるため，反復法により目的関数を最適化する．目的

ザー評点を要素とする M 次元ベクトル zi で定義し，||zi || = 1

関数 R を最大化するアルゴリズムを説明する．と正規化して入力とした．

入力 : 元空間の座標ベクトル群 Z = (z1 , · · · zN )(N は全オブジェクト数を示す): 埋め込み次元 L

3. 2 可視化結果による評価@cosme の分析結果 図 1(a) と 図 1(b) を比較してみると，@cosme ではどちらの手法でもスキンケア用品，メイクアップ

(a) PCA 法(b) RLP 法
図 1 2 次元平面布置結果（@cosme）(a) PCA 法(b) RLP 法
図 2 2 次元平面布置結果（アニコレ）

アイテムなど使用用途ごと，また同一のブランドごとにまとている 2010 年夏期アニメ以前のアニメはアニメ全話を見てかまって近傍に射影されている．このデータでは”ラッシュ”といらレビューを投稿するケースが主である．そのためレビューすうブランドのアイテムがほかのブランドとは異なるユーザー層る側も自分の印象に残っている作品や掘り出して視聴した作品に支持されており他のブランドとの距離が大きくなっている.

が主になるためアニメ作品による認知度の違いなどもあり，レそのため，自乗距離を最大化する PCA 法では”ラッシュ”とそビューするユーザが疎らになる傾向になる．一方，放映中のアの他のブランド間の距離が支配的となり他のブランド間の距離ニメに対するレビューの多くは配信ごとにレビューが更新してが縮小された結果となったと考えられる. RLP 法ではこのよういくものが多い．放映中アニメを視聴するユーザはその放映時な点に対応するため絶対値距離を採用しているため全体が万遍期の全アニメを網羅して視聴していることが多いため，ユーザなく散らばり，より解釈可能な可視結果が得られた.

はその時期の放映中アニメ全てに対してレビューを投稿していアニコレの分析結果 図 2(a) と 図 2(b) を比較してみると，る傾向が高い．そのため，放映中アニメ同士はレビューしていどちらの手法でも，子供向け映画に関するアイテム集合や原作るユーザが被るケースが多くなる．よって，放映中に初めてレに関するアイテム集合が近傍に射影されており，もとの高次元ビューを受けるアニメ作品，つまり 2110 秋期以降放映された空間での類似構造を保存した射影結果が得られた. 2111 年〜

アニメ作品同士がまとまって射影された結果になったと考えら

2012 年放映アニメが比較的まとまって射影された結果となっれる．

たが，これはレビューサイト元であるアニコレが 2010 年秋に3. 3 空間充填率創設されたためだと考えられる．サイト創設時に放映が終了し

空間充填率を以下のように定義し，2 次元可視化結果を定量

11PCA
RLP

0.9

PCA
RLP

0.9

space filling rate S(G)space filling rate S(G)

0.8
0.7
0.6
0.5

0.8

0.7

0.6

0.4
0.5
0.3
0.2
0100

200300400500600
number of meshs G

700

800

0.4
0900

100

200300

400
500
600
number of meshs G

700

800

900(b) 空間充填率（アニコレ）(a) 空間充填率（@cosme）
図 3 空間充填率結果

500400800
L = 1 PCA
L = 2 PCA
L = 3 PCA
L = 10 PCA
L = 1 RLP
L = 2 RLP
L = 3 RLP
L = 10 RLP

mean number of objects within the range Dmean number of objects within the range D

600300200

100000.02

0.04

0.06

0.08

0.1700600
500

L = 1 PCA
L = 2 PCA
L = 3 PCA
L = 10 PCA
L = 1 RLP
L = 2 RLP
L = 3 RLP
L = 10 RLP

400
300
200
100000.02

0.04

range D

0.06

0.08

range D(a) 平均近傍オブジェクト数（@cosme）(b) 平均近傍オブジェクト数（アニコレ）
図4

定量評価結果的に評価する．2 次元平面を G 個のメッシュに分割する．g 番3. 4 定量的評価法

目のメッシュにオブジェクトが含まれていれば cg = 1 とし，空低次元空間への射影結果に関して，類似検索の観点から定量的に評価する．一般に，低次元空間の方が高次元空間での距離間充填率を以下のように計算する．

1 ∑S(G) =cgG(4)g

明らかに，オブジェクトが 2 次元平面上にあまねく散らばっている方が S(G) が高くなる．
横軸がメッシュの数 G，縦軸が空間充填率 S(G) とする．

@cosme の分析結果， 図 3(a) を見ると，メッシュを増加していくと RLP 法は PCA 法に比べて常に約 20 ％ほど高い空間充填率を示し，RLP 法の方が PCA 法より射影後の散らばり具合が大きく空間充填率の高い射影が実現できている.
アニコレの分析結果， 図 3(b) を見るとメッシュを増加していくと RLP 法は PCA 法に比べて常に約 10 ％ほど高い空間充填率を示し，こちらも RLP 法の方が空間充填率の高い，よりデータの散らばった可視化結果となった．

計算よりコストが少なく済む．縮小写像により射影した低次元空間で範囲 D 内にあるオブジェクトは，高次元空間でも範囲D 内に存在する．従って，元空間（高次元空間）で範囲 D 内に存在するオブジェクトを検索するレンジクエリにおいて，低次元空間で範囲 D 内にあることは必要条件であるため，条件に満たないオブジェクトを枝刈りできれば理想的である．
オブジェクト i から範囲 D 内に存在するオブジェクトの集合を QD (i) としたとき，全オブジェクトの平均 D 近傍オブ
1
ジェクト数 Q̄D = N

∑N

i=1

|QD (i)| により評価する．RLP 法ならびに PCA 法は縮小写像であるため，元空間における範囲D 内の平均オブジェクト数より，低次元射影後における範囲 D内の平均オブジェクト数の方が多くなる．しかしながら，低次元射影後にできるだけ少ない数のオブジェクトに絞ることがで0.1

きれば，レンジクエリ検索の効率化が期待できる．

3. 5 類似検索機能による評価図 4(a) と図 4(b) に類似検索の観点から，射影後の低次元空間での平均近傍オブジェクト数による定量評価結果を示す．検索用データベース内に，既に非常に類似するオブジェクトが存在するかを確認するというタスクの観点から，0.01 から 0.1 の範囲でレンジを変化させた結果を示す．
横軸をレンジ D，縦軸を平均近傍オブジェクト数 Q̄D とする．@cosme の分析結果である図 4(a) を見ると，10 次元以上への射影では有意な差は見られないものの，低次元へ射影した空間において，PCA 法より RLP 法の方が平均近傍オブジェクト数が小さいことがわかる．L = 1，つまり 1 次元では大きな差は見られなかったが，1 < L <= 3 次元では有意な差が確認できた．すなわち，RLP 法を用いた射影による低次元での距離計算において，より少ないオブジェクト数に絞ることができ，効率的なレンジクエリ検索への貢献が期待できる．@coseme のデータには外れ値である”ラッシュ”ブランドのアイテムが存在し，ゆえに”ラッシュ”ブランドのアイテム集合と他のブランドアイテム集合間の距離が支配的となっている．そのため”ラッシュ”のアイテム集合ではない，その他のブランドアイテム集合同士が近傍に射影されたために範囲 D 内の平均オブジェクト数が大きくなってしまったと考えられる．RLP 法の場合，絶対値を距離として採用しているため，近傍に射影されていた他のブランドアイテム集合が全体に散らばり，範囲 D 内の平均オブジェクト数が減少した結果となった．PCA 法を用いて枝刈りをした場合，類似度の小さいアイテムが枝刈りされずに残ってしまう可能性があるが，RLP 法を用いて枝刈りをした場合，枝刈りされずに残っていたアイテムが散らばり，PCA 法に比べてより精密な枝刈りが期待できる．
アニコレの分析結果，図 4(b) を見ると，@cosme ほど顕著な差ではないが，RLP 法による射影空間での平均近傍オブジェクト数の方が小さいことがわかる．こちらも距離に絶対値を採用したために近傍に射影されていたアイテム同士が散らばり，範囲 D 内の平均オブジェクト数が減少したと考えられる．

4. お わ り に
本論文では，外れ値に対して頑健性を示し，元空間でのオブジェクト間の関係をできるだけ保存する埋め込み法について研究し，射影後のデータの散らばり具合が PCA 法よりも大きくなる方法を提案した. また，データによっては，外れ値の影響を受けて効果的な枝刈りが期待できない可能性があったが，提案法により，データの散らばり具合が向上したので，類似検索において非類似オブジェクトの効果的な枝刈りが期待できることを確認できた．今後は PCA 法だけでなく自己組織化写像法などといった他の既存手法との比較, 次元圧縮した際, 高次元空間でのデータ関係をどれだけ保存することが出来たか, という観点から提案法を評価していく．
謝辞

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

文

献[1] J. A. Lee, and M. Verleysen.: ”Nonlinear DimensionalityReduction (Information Science and Statistics)” SpringerVerlag, New York, (2008)[2] R. Spence, A. Press.:”Information Visualization”,
Addison-Wesley, 2001.
[3] P. Zezula, G. Amato, V. Dohnal, and M. Batko, “Similarity
Search: The Metric Space Approach (Advances in DatabaseSystems)”, Springer-Verlag, New York, 2006.
[4] B. Bustos, G. Navarro, and E. Chavez.: ”Pivot Selection Techniques for Proximity Searching in Metric Spaces”,
Proc. of Pattern Recognition Lettes, Vol.24, No.14, pp.
2357-2366, 2003.
[5] http://www.cosme.net/[6] http://www.anikore.jp/