DEIM Forum 2017 G3-2

モバイルセンサデータベースにおける階層的クラスタリングを用いた Top-k 検索結果の多様化について
横山 正浩†隆浩†

原† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{yokoyama.masahiro,hara}@ist.osaka-u.ac.jp
あらまし

近年のセンサ技術の発展に伴い，モバイルセンサ端末が普及しており，これらの端末から収集されたモバ

イルセンサデータを活用する研究に注目が集まっている．例えば，周辺の環境属性値に比べて極端な値を持つデータを取得することで，ホットスポットの地理的分布に関する知識が得られる．このような応用に対して，地理空間上のTop-k 検索結果の多様化が有効である．筆者らはこれまでに，環境情報の空間的自己相関に基いたデータのクラスタ
リングを利用した，効率的な Top-k 検索結果の多様化手法を提案した．しかし，センシングする環境属性の数が増えると，データ間の類似度の低下に起因してクラスタの数が大幅に増加し，従来手法では計算時間が大きくなってしまう．そこで本稿では，階層的クラスタリングによって環境属性の増加にともなうクラスタ数の増加の影響を軽減可能
な，従来手法より効率的な拡張手法を提案する．
キーワード モバイルセンサデータ，ホットスポット検出，参加型センシング

1. は じ め に
近年，スマートフォンを始めとして，様々なセンサデバイス

.  : 検索範囲
: モバイルセンサデータ
. : 検索結果に含まれるデータを搭載したモバイル端末が広く普及している．このようなモバ
イル端末によって，端末保持者付近の物理現象や環境の変化を観測しデータ収集を行う手法は，参加型センシング [8] と呼ばれ，現在注目が集まっている．収集されるデータは，騒音や大気汚染指数といった，観測した現象に関する環境属性値を持った位置情報付きデータである．これらのデータはモバイルセン

図 1 ホットスポットと Top-k 検索結果の多様化

サデータと呼ばれ，多くの研究者によってモバイルセンサデー
タを利活用する研究が行われている．
現在，位置情報付きデータに対する検索について，検索範囲を指定し範囲内のデータを取得する，時空間範囲検索が主流である．また，ユーザは多くの場合，町中において高い気温や大気汚染指数を示すデータといった，極端なデータに興味があると考えられる．例えば，図 1 における各円形領域は，周辺の領域に比べてなんらかの環境属性値が大きいデータが分布する
ホットスポットであるとする．このとき，各ホットスポットで生成されたモバイルセンサデータを取得することで，検索範囲内のホットスポット検出が可能となる．このためには，分析の目的に応じたユーザの注目する環境属性の値に基いてデータにスコアを割り当て，スコアの高いデータを優先的に選択する必要がある．加えて，データ間の空間距離を考慮することで，検索結果が特定の空間位置に集中することなく，検索範囲内で分散した高スコアのデータを取得できる．
このようなデータ検索は，Top-k 検索結果の多様化 [2] によって実現できる．モバイルセンサデータベースにおける Top-k 検
索結果の多様化では，データのスコアとデータ間の空間距離によって，データの評価値が定義される．最終的な検索結果は，検索範囲内のすべてのデータの評価値を計算し，評価値が最大のデータを選択するという動作を，k 回繰り返すことで算出される．筆者らの研究グループではこれまでの研究において，モ
バイルセンサデータベースにおける効率的な Top-k 検索結果の多様化手法を提案した [9]．提案手法では，あらかじめ空間位置が近く，かつ環境属性値が似ているデータ同士をクラスタリン
グしておく．オンラインクエリ処理時にこれらのクラスタ情報を利用し，最適なデータを含まないクラスタを走査対象から除外することで，評価値が最大のデータを短時間で取得できる．
しかし，従来手法では，モバイルセンサデータの環境情報の数が増えると，計算時間が増大する問題があった．これは，環境属性値ベクトルが高次元になるほどデータ間の非類似度が大きくなるため，球形クラスタの半径が大きく，かつクラスタの数も大幅に増加することで，走査するデータの数が多くなってしまうためである．近年，様々な環境情報が参加型センシング
によって観測，収集されているため，環境属性値ベクトルの次元が大きい場合でも検索結果を短時間で取得できることが望ましい．
そこで本稿では，階層的クラスタリングを行うことで，環境属性値ベクトルの次元数の増加にともなう計算効率低下の影響を軽減可能な拡張手法を提案する．拡張手法の階層的クラスタ
リングでは，空間的に近接するすべてのデータは 1 つの上位ク

3. Top-k 検索結果の多様化

ラスタのメンバとし，上位クラスタの中でメンバデータの環境

3. 1 想定環境と問題定義

属性値の類似度に基いてさらに下位クラスタに分割する．拡張

モバイルセンサ端末は，周期的に付近の大気汚染指数，気温，手法のオンラインクエリ処理では，階層クラスタ構造を利用し，湿度などの物理現象についてセンシングするものとする．ユー

上位クラスタ内のデータが取りうる評価値の上界を推定するこザの検索クエリを q ，検索範囲を q.R としたとき，検索範囲内とで，下位クラスタをまとめて走査対象から除外できる．空間に分布するデータ集合を O で表す．q.R は Top-k 検索結果の多的に近接するデータからなる上位クラスタの数は，環境属性数

様化処理を行う時空間範囲であり，図 1 における矩形領域が該の増加に非依存であり，従来手法におけるクラスタの数よりも当する．以降では，q.R の範囲外に存在するデータは無視し，少なくなる．そのため拡張手法では従来手法と比べて，走査すデータ集合 O のみを検索対象とする．

べきデータを短時間で絞り込める．

各データのスコアは，クエリ q に基づいて決定される．ユー

以下では，2 章で関連研究について述べ，3 章で想定環境を紹

ザはクエリ q に対して，各環境属性に対する興味の度合いを示介し本稿の問題を定義する．4 章で従来手法を紹介し，5 章です重み付け係数 q.w を付与する．クエリ q における，データ o

拡張手法について説明する．最後に，6 章で本稿をまとめる．

のスコア p(q, o) は，以下の式に従って計算される．

2. 関 連 研 究p(q, o) =n∑q.wi · o.atti

(1)

i=1

Top-k クエリ処理は，全体のデータセットの中からスコアの最も高い（低い）k 個のデータを取得する検索であり，様々な

式 (1) 中の wi は i 番目の環境属性に対する重みを示す．以降

研究分野において重要な役割を担っている．固定センサネット

では文脈上明らかな場合は，p(q, o) を p(o) のように略記する．

ワークにおける Top-k 検索 [5] は，最も高い（低い）環境属性

2 つのデータ間の多様性は，空間距離 d で表される．d(u, v) は値を観測した k 個のノードを検索結果として返す．一般的に，

データ u，v の位置情報から算出される u，v 間のユークリッド

固定センサネットワークでは，設置されているセンサはセンシ

距離であり，以下の式に従って計算される．

ング間隔が同期して動作しており，設置位置も観測範囲内で分散している．一方，モバイルセンサネットワークでは，モバイ

d(u, v) =√(u.locx − v.locx )2 + (u.locy − v.locy )2 .

(2)

ルセンサは非同期かつ時空間上の任意の位置でデータを生成す

上述した環境属性値から算出されるデータのスコア，およびる．このような環境では，従来の Top-k 検索を用いた場合，多データ間の位置情報から算出される空間距離に基づいて，モバ

くの冗長なモバイルセンサデータが検索結果に含まれてしまう．

イルセンサデータベースにおける Top-k 検索結果の多様化を以よって，検索範囲内に存在するホットスポットにおいて生成さ下のように定義する．

れたモバイルセンサデータを取得するためには，別の手法が要求される．

定義. クエリ q = {R, k, λ, w} が与えられたとき，データ集合

従来の Top-k 検索では，検索結果はデータの関連度にのみ基O を検索範囲内で観測されたデータ集合 O = {oi | oi ∈ q.R}

いて定まるが，ユーザの検索要求をより満たせるように，検索とする．このとき，以下の式で与えられる最適化問題を解くこ

結果の多様性を考慮した研究が盛んに行われている [1], [2]．研
究対象は，文書に対するキーワード検索，EC サイトにおける商品推薦など多岐に渡る．モバイルセンサデータベースにおいては，データのクエリに対する関連度を環境属性値から算出されるスコア，多様性をデータ間の空間距離とすることで，ホットスポット検出に応用できる．
近年，各国で様々な参加型センシングのプロジェクトが進められており，大気汚染指数，騒音指数，夜間の光量といった，多様な環境情報が収集されている [4], [7], [8]．また，文献 [6] では，センサデータの複数の環境属性値から重回帰分析を用いて，別の環境属性値を推定する手法が提案されている．このような背景から，今後ますます多くの環境情報が，モバイルセンサとによって，最適な検索結果 Sk∗ が得られる．

Sk∗ =arg max f (Sk , q, p(·), d(·, ·)).

Sk ⊂O,|Sk |=k(3)=

ここで，f (Sk , q, p(·), d(·, ·)) は目的関数である．以降では文脈上明らかな場合は，f (Sk , q, p(·), d(·, ·)) を f (Sk ) のように略記する．本研究では，高いスコアを取るデータを優先しながらも空間的に偏りの小さい結果が得られる，文献 [3] におけるMaxmin 問題を対象とする．この場合，目的関数は以下の式で与えられる．

f (S) = min p(u) + λ min d(u, v)
u∈S

u,v∈S

(4)

データベースにおいて包括的に扱われることが予想される．一式 (4) から，正解集合 S 内のデータのスコアが大きいほど目

般的にデータが高次元になると，検索アルゴリズムが非効率的的関数の値は大きくなり，また，正解集合 S 内の任意のデータとなるため，適応的な手法が求められる．

間の距離が大きいほど目的関数の値は大きくなる．目的関数中の λ は，ユーザの検索における地理的多様性についての重要性を表しており，λ が大きいほど地理的多様性を重視してデータを要求し，地理的により分散した結果が得られる．

Algorithm 1 Algorithm for the Optimization Problems
Input: Data set O, k, λ, w

Algorithm 2 Algorithm for Clustering
Input: Data set O, r1 , r2

Output: Set S(|S| = k) that maximizes f (S)Output: Set of clusters C = C1 , C2 , ..., Cl

1: Initialize the set S = ∅1: clusterLabel = 1

2: Find x∗∗

2: for i = 1 to |O| do= arg max p(x) and set S = {x }x∈O

3: while |S| < k do
4:

∗

3:
∗

′

Find y ∈ O\S such that y = arg max d (y, S)

4:

y∈O\S

5:

if oi is not in any clusters thenMark oi as the center and initial representative of the current cluster

Set S = S ∪ {y ∗ }6: end while5:

X = retrieveNeighbors(oi , r1 , r2 , O)6:

for all o ∈ X do
if o is not in any clusters then7:

上記の組合せ最適化問題を解くことは，NP 困難であることが8:

示されており，検索範囲内のデータセットサイズ N が大きいと

9:

end if

10:

end for11:

clusterLabel++

きに全ての部分集合候補について総当りで探索するのは，計算時間の観点から現実的ではない．様々なヒューリスティックな手法の中でも，グリーディアルゴリズムは得られる正解集合の質および計算時間の観点から効果的であることが知られており，

12:Mark o with current clusterLabelend if

13: end for

様々な目的関数に応じた手法が提案されている．そこで，本研究においてもグリーディアルゴリズムをベースラインとする．

3. 2 ベースライン手法
ベースラインとなる単純なグリーディアルゴリズムを，Algo-rithm 1 に示す．1，2 行目の初期化処理では，データセット内で最大のスコアをとるデータを正解集合に追加する．3 行目から

6 行目の反復により，正解集合の大きさが k となるまで，繰り返しデータを正解集合に追加する．4 行目の d′ (·, S) は，デー
タのスコアとデータ間の空間距離から算出される評価値であり，次の式で定義される．

3，4 行目で，いずれのクラスタにも属していないデータを見つけた場合，そのデータを新たなクラスタの中心データかつ代表
データとする．ここで，5 行目の retrieveNeighbors(oi , r1 , r2 , O)
は，データ集合 O から，データ oi に空間位置が互いに近く，かつ環境属性値が互いに似ているデータを返す操作である．具
体的には，データ oi の空間位置ベクトル oi .loc を中心とした
半径 r1 の円内に存在し，かつ，データ oi の環境属性値ベクト
ル oi .att を中心とした半径 r2 の超球内に存在するデータを返す操作である．n 次元の環境属性値について，半径 r2 の超球内

1d (y, S) = min{ (p(y) + p(u)) + λd(y, u)}
u∈S 2
′

(5)

に存在するデータ集合 Oi は，ユークリッド距離を用いた以下の式で表される．

以下の式に示すように，4 行目で追加されるデータ y ∗ は，評価
値 d′ (·, S) を最大化すると同時に，目的関数 f (S ∪ y) を最大化
する．

v
u∑
u n
Oi = {o | t (oi .attj − o.attj )2 <= r2 }.

(7)j=1

y ∗ = arg max d′ (y, S) = arg max f (S ∪ y).
y∈O\S

(6)

y∈O\S

retrieveNeighbors(oi , r1 , r2 , O) で取得したデータのうち，いずれのクラスタにも属していないデータに対し，現在作成中のク

このアルゴリズムの計算量は，データセットサイズ N に依

ラスタのラベルを付与する．クラスタ間でのデータの共有はな存する．初期化処理は，データのスコアが最大のデータを探索いものとし，全てのデータがいずれかのクラスタに割り当てらするため，単純にデータセット全体の走査が必要となり，計算れるまでクラスタを生成する．

量は O(N ) である．また，3 行目から 6 行目の反復については，

4. 2 クラスタを利用したオンラインクエリ処理

反復回数が k ，各反復につき最大 k(N − k) 回の評価値の計算

4. 2. 1 アルゴリズムが必要となるため，全体の計算量は O(k 2 N ) となる．そのた

具体的なアルゴリズムを Algorithm 3 に示す．ここでは特に，め，データセットサイズが大きくなると計算時間が長くなって走査データ数削減の要点である，Algorithm 3 の反復部分（3〜しまう．

16 行目）について説明する．まず，全クラスタの代表データを

4. 従 来 手 法

走査し，評価値の最大値をとる代表データ o∗rep を探索する（4行目）．このデータの評価値が，各クラスタ内のデータを走査

従来手法は，オフライン事前クラスタリング処理とオンライ

すべきかどうかを判断する基準値となるため，以降はこのデー

ンクエリ処理からなる．本章では，それぞれについて詳しく説

タを基準データと呼ぶ．またこのときに，中心データの評価値

明する．

も計算し，記憶しておく．これは，本節の後半で説明するよう

4. 1 オフライン事前クラスタリング処理に，クラスタ内データが取りうる評価値の上界を推定する際に具体的なクラスタリングアルゴリズムを，Algorithm 2 に示す．

必要となるためである．次に，全クラスタについて，各クラス

Algorithm 3 Algorithm for Optimization Problems Leveraging
Clusters
Input: C, k, λ, w, r1 , r2

1.0

∗


 

. 



0.5

1: Initialize the set S = ∅

∈

1.0

Output: Set S(|S| = k) that maximizes f (S)2: Find x. ଶ

0.5= arg max p(x) and set S = {x∗ },. 



௜



,

௜,

, , 

x∈O



3: while |S| < k do

0

4:

Find o∗rep such that o∗rep = arg max d′ (oi,rep , S)oi,rep ∈Ci

5:

for all i = 1 to |C| do

7:

9:

end if

10:

end for

11:
12:

14:
15:

max {p(vi )}vi ∈Ci=Find y ∗ ∈ C ′ \S such that y ∗ = arg max d′ (y, S)′
y∈C \S
if y ∗ is representative data of Ci then

max

|ϵ|<
=r2 ,0<=θ<=2π= (p(oi,cen ) +{q.w · (oi,cen .att + ϵ)}
max

|ϵ|<
=r2 ,0<=θ<=2π(|q.w||ϵ|cosθ))= p(oi,cen ) + |q.w|r2 .

Select new representative data for Ci

13:


0.5
(b) 第2項の上界推定1.0

えられる（図 2(a)）．

C ′ = C ′ ∪ {Ci }8:0

図 2 クラスタの上界の推定

Estimate upper bound of each cluster d′ (Ci , S)′
if d′ (o∗rep , S) <= d (Ci , S) then6:. ଵ
1.0
0.5(a) 第1項の上界推定(9)次に，正解集合内のデータに依存する項（第 2 項）が取りうる

end if∗Set S = S ∪ {y }最大値を計算する．クラスタの中心データと正解集合内のデー
タとの，各データのスコアを加味した距離を計算し，その時の16: end while

距離が最小となる正解集合内のデータを uN N ∈ S とする．中タ内のデータの評価値が取りうる値の上界 d′ (Ci , S) を推定する（6 行目）．各クラスタの上界の推定値と，最初に計算した基準データの評価値 d′ (o∗rep , S) を比較し，推定値のほうが大きい場合，走査対象クラスタ集合 C ′ に追加する．一方，推定値のほうが小さい場合，少なくともこのクラスタ内のデータよりも，基準データ o∗rep のほうが正解集合に追加するデータとし心データとデータ uN N を直線で結んだ時，2 つの交点が存在する（図 2(b)）．ここで，データ uN N から最も離れる位置は，

2 つの交点の内，データ uN N から遠い方の点である．仮想デー
タ vi がこの点に位置するとき，正解集合 S からの距離も最大化される．そのため，第 2 項が取りうる最大値は，以下の式で与えられる．

1max {min( p(u) + λd(vi , u))}2
1
= p(uN N ) + λ{d(oi,cen , uN N ) + r1 }2て適しているため，以降の走査から除外する．

vi ∈Ci u∈S

最後に，走査対象クラスタ集合 C ′ に含まれるすべてのデー
タを走査し，最大の評価値をとるデータを，正解集合 S に追加する．追加されたデータがいずれかのクラスタの代表データ
であった場合，クラスタ内のデータからランダムに新たな代表
データを選択する（12〜14 行目）．

(10)

これらの式から，クラスタの上界を計算でき，以下の式で示される．

1{p(oi,cen ) + |q.w|r2 }21+ p(uN N ) + λ{d(oi,cen , uN N ) + r1 }2
1
= { (p(oi,cen ) + p(uN N )) + λd(oi,cen , uN N )}2
1
+ |q.w|r2 + λr1
21′= d (oi,cen , S) + |q.w|r2 + λr1(11)2

d′ (Ci , S) =4. 2. 2 クラスタの上界の推定
ここで，Algorithm 3 の 6 行目における，各クラスタ内デー
タが取りうる評価値の上界の推定方法について説明する．クラスタが含むデータの分布の詳細は不明なため，クラスタ内に存在しうる仮想的なデータ vi を考え，データ vi が取りうる最大の評価値を，可能な限り正確に計算する．評価値は，データ間の空間距離と，環境属性値に基づくスコアの 2 つの指標から算出される．ここで，評価値を正解集合内のデータに非依存の項と依存する項に分解する．

ここで，式 (11) の中心データの評価値 d′ (oi,cen , S) は，アルゴ
リズムの上界推定の前に計算し記憶されている．

1
1d (vi , S) = p(vi ) + min{ p(u) + λd(vi , u)}
u∈S 2
2
′

(8)

まず，正解集合内のデータに非依存の項（第 1 項）が取りうる最大値を計算する．クラスタ内に存在しうる仮想デー
タ vi のスコアは，重みベクトル q.w と環境属性値ベクトル

vi .att = oi,cen .att + ϵ の内積であり，最大値は以下の式で与4. 3 問 題 点
従来手法では，クラスタの上界が基準データの評価値未満であれば，そのクラスタ内のデータは走査する必要がなく，短時間で検索結果が得られる．できるだけ多くのクラスタを走査対象から除外するために，基準データの評価値はできるだけ大きい方が望ましく，従来手法では，全てのクラスタの代表データ

Algorithm 4 Algorithm for Hierarchical Clustering
Input: Data set O, r1 , r2合を取得し，これらをすべて上位クラスタのメンバとする．次に，上位クラスタ中のあるメンバに着目したとき，環境属性値

Output: Set of upper clusters U C = U C1 , U C2 , ..., U Clが類似しているメンバを下位クラスタのメンバとする．上位ク

1: upperClusterLabel = 1

ラスタのメンバがすべて，いずれかの下位クラスタに割り当て

2: for i = 1 to |O| do

られるまで上述した処理を繰り返すことで，階層クラスタが構

3:

if oi is not in any clusters then

築される．
具体的な階層的クラスリングアルゴリズムを，Algorithm 4 に

4:Mark oi as the center of the current upper cluster

5:

X = retrieveNeighbors(oi , r1 , ∞, O)示す．3，4 行目で，いずれのクラスタにも属していないデータ

for j = 1 to |X| dooi を見つけた場合，oi の空間位置ベクトルを中心とした上位ク

6:
7:
8:

lowerClusterLabel = 1

ラスタを生成する．5 行目で，全データ集合 O から，上位クラif oij is not in any clusters thenスタの中心データ oi の空間位置ベクトルを中心とした半径 r19:Mark oij as the center and initial representative of theの円内に存在するデータを取得する．取得したデータのうち，current lower-level cluster

ラベルが付与されていないデータは全てこの上位クラスタのメ′

X = retrieveNeighbors(oij , ∞, r2 , X)

10:′

for all o ∈ X do

11:

if o is not in any clusters then

12:
13:

ンバであり，これらのデータをさらに環境属性値に基づきクラスタリングする．8，9 行目で，上位クラスタのメンバのうち，いずれのクラスタにも属していないデータ oij を見つけた場合，Mark o with current lowerClusterLabel and up-

そのデータを新たな下位クラスタの中心データかつ代表データ

perClusterLabelとする．10 行目で，上位クラスタのメンバから，データ oij の14:

end if

環境属性値ベクトルを中心とした半径 r2 の超球内に存在する

15:

end for

データを取得する．取得したデータのうち，ラベルが付与され

16:

end ifていないデータに対し，現在作成中の上位クラスタおよび下位

17:

lowerClusterLabel++

クラスタのラベルを付与する．ここで，上位クラスタ U Ci が18:

end form 個の下位クラスタを含むとき，上位クラスタおよび下位クラ

19:

upperClusterLabel++

スタの関係を以下のように表現する．

20:

end if

21: end for

U Ci = {LCi1 , LCi2 , ..., LCim }(12)

従来手法と同様，クラスタ間でのデータの共有はないものとし，の内，評価値が最大のものを探索する．また，基準データを探索した後，全てのクラスタの上界を計算し基準データの評価値と比較する．このため，走査するためのデータ数を削減する
コストは，クラスタの数に依存する．しかし，モバイルセンサ
データの環境属性の数が増えるほど，データ間の類似度が小さくなるため，クラスタの数は増加する．クラスタ半径 r2 を大きくすればクラスタの増加は抑制できるが，基準データの評価
値よりも大きくクラスタの上界を推定してしまう可能性が高く，効果的ではない．

全てのデータがいずれかのクラスタに割り当てられるまでクラスタを生成する．

5. 2 階層クラスタを利用したオンラインクエリ処理
5. 2. 1 アルゴリズム
従来手法では，すべてのクラスタを探索し基準データを選択していたが，拡張手法では上位クラスタのみを探索し，上位クラスタの代表データの中から基準データを選択する．また，上位クラスタの評価値の上界を計算することで，走査対象データの絞り込みを上位クラスタ単位で行う．上位クラスタの上界が基準データの評価値を上回る場合は，下位クラスタの上界を計

5. 拡 張 手 法
本章では，クラスタ増加の影響を軽減する，階層的クラスタ
リングを利用した拡張手法について説明する．拡張手法では，空間的に近接するデータを上位クラスタとしてまとめるため，
上位クラスタの数は従来手法のクラスタの数と比べて小さくなる．よって，従来手法におけるクラスタ単位の走査対象データの絞り込みや基準データの選択を上位クラスタ単位で行うこと
で，環境属性値ベクトルが高次元である場合でも，効率的に評
価値最大のデータを取得できる．

5. 1 オフライン事前階層的クラスタリング処理
階層クラスタを構築するために，まず最初にいずれのクラス
タにも属していないデータについて空間的に近接するデータ集

算し基準データの評価値と比較することで，より細かい粒度で走査対象データの絞り込みを行う．
具体的なアルゴリズムを Algorithm 5 に示し，反復部分（3〜25 行目）について説明する．まず，全上位クラスタを走査し，基準データを選択する（5 行目）．基準データの評価値は高いほど望ましいため，上位クラスタ内の下位クラスタの代表デー
タをすべて走査し，スコアが最大のものを選択する．各上位クラスタごとに，スコアが最大の下位クラスタの代表データを記憶しておき，以降の反復ではこれら |U C| 個のデータの中から
基準データを選択する．次に，全上位クラスタについて，各上位クラスタ内のデータの評価値が取りうる値の上界 d′ (U Ci , S)を推定する（7 行目）．各上位クラスタの上界の推定値と，基準データの評価値 d′ (o∗rep , S) を比較し，推定値のほうが大きいAlgorithm 5 Algorithm for Optimization Problems Leveraging Hi-

内のデータは，環境属性値の類似度を考慮してさらに下位クラ

erarchical Clusters
Input: U C, k, λ, w, r1 , r2スタに分割される．そのため，上位クラスタの上界は，下位クラスタの上界のうち最大のものとして，以下の式で与えられる．

Output: Set S(|S| = k) that maximizes f (S)1: Initialize the set S = ∅2: Find x∗= arg max p(x) and set S = {x∗ }x∈O

3: while |S| < k dod′ (U Ci , S) =max

LCij ∈U Ci ,1<=j<=m{d′ (LCij , S)}(13)

次 に ，下 位 ク ラ ス タ 内 デ ー タ が 取 り う る 評 価 値 の 上 界

d′ (LCij , S) の推定方法について説明する．従来手法のクラ4:

Initialize the sets U C ′ = LC ′ = ∅スタの上界と同様，評価値を正解集合内のデータに非依存の項

5:

Find o∗rep such that o∗rep = arg max d′ (oi,rep , S)と依存する項に分解し，別々に上界を計算することで求める．

for all i = 1 to |U C| do

正解集合内のデータに非依存の項（第 1 項）の上界は，下位ク

oi,rep ∈U Ci

6:

Estimate upper bound of each upper cluster d′ (U Ci , S)′
if d′ (o∗rep , S) <= d (U Ci , S) then

7:
8:

U C ′ = U C ′ ∪ {U Ci }9:10:

end if

11:

end for

12:(14)

次に，正解集合内のデータに依存する項（第 2 項）の上界を計算する．下位クラスタ内データが取りうる空間位置は，上位ク

for all j = 1 to |U Ci | do

ラスタの中心データ oi,cen の空間位置ベクトルを中心とした半Estimate upper bound of each lower-level cluster

径 r1 の円内に限られる．よって，上位クラスタの中心データ

d′ (LCij , S)と正解集合内のデータとの，各データのスコアを加味した距離′′
if d (o∗rep , S) <= d (LCij , S) then

15:

′

′

LC = LC ∪ {LCij }

16:
17:

end if18:

end for21:

max {p(vij )} = p(oij,cen ) + |q.w|r2

for all i = 1 to |U C | do

14:

20:

（図 3(a)）．
vij ∈LCij

′

13:

19:

ラスタの中心データ oij,cen を用いて，以下の式で計算できる

Find y ∗ ∈ LC ′ \S such that y ∗ = arg max d′ (y, S)′
y∈LC \S∗if y is representative data of LCij thenSelect new representative data for LCij23:

end if

24:

Set S = S ∪ {y ∗ }uN N ∈ S とすると，以下の式で計算できる（図 3(b)）．
1max {min( p(u) + λd(vij , u))}2
1
= p(uN N ) + λ{d(oi,cen , uN N ) + r1 }2

vij ∈LCij u∈Send for

22:を計算し，その時の距離が最小となる正解集合内のデータを(15)

これらの式から，下位クラスタの上界を計算でき，以下の式で示される．

1{p(oij,cen ) + |q.w|r2 }21+ p(uN N ) + λ{d(oi,cen , uN N ) + r1 }2
1
= { (p(oij,cen ) + p(uN N )) + λd(oi,cen , uN N )}2
1
+ |q.w|r2 + λr1
21′= d (oij,axis , S) + |q.w|r2 + λr1(16)2d′ (LCij , S) =25: end while

場合，走査対象上位クラスタ集合 U C ′ に追加する．一方，推定値のほうが小さい場合，少なくともこの上位クラスタ内のすべてのデータよりも，基準データ o∗rep のほうが正解集合に追加するデータとして適しているため，以降の走査からは除外す

ここで oij,axis は，上位クラスタ U Ci の中心データ oi,cen の空る．全上位クラスタをチェックした後，走査対象上位クラスタ

間位置ベクトルと，下位クラスタ LCij の中心データ oij,cen の集合 U C ′ に含まれる下位クラスタについて，走査対象をさら

環境属性値ベクトルからなり，以下の式で与えられる．

に絞り込む（12〜19 行目）．ここでは，上位クラスタの絞り込
みと同様，各下位クラスタの上界の推定値と基準データの評価値を比較し，走査対象下位クラスタ集合 LC ′ に該当する下位′クラスタを追加する．最後に，LC 内のすべてのデータの評

oij,axis = (oi,cen .locx , oi,cen .locy , oij,cen .att1 , ..., oij,cen .attn )(17)
このデータの評価値 d′ (oij,axis , S) は，Algorithm 5 の 5 行目の価値を計算し，最大の評価値を取るデータを正解集合 S に追加

基準データを探索する際に計算でき，値を下位クラスタごとにする．

記憶しておくことで，以降の反復で継続して用いることができ

5. 2. 2 上位クラスタおよび下位クラスタの上界の推定る．また，式 (16) から下位クラスタの上界は，下位クラスタ内

ここで，Algorithm 5 の 7 行目における，上位クラスタ内デーのデータが取りうるスコア（第 1 項）の上界にのみ依存する．

タが取りうる評価値の上界 d′ (U Ci , S) の推定方法について説明

よって，上位クラスタの上界は，スコアの上界が最大の下位クする．上位クラスタ内に存在しうる仮想的なデータ vi を考え，ラスタの上界となる（図 3(a)）．スコアの上界は，正解集合内

データ vi が取りうる最大の評価値を計算する．上位クラスタのデータに非依存であるため一度だけ計算されればよく，以降は上位クラスタごとに記憶した値を用いる．

. 
1.0

章で説明した従来手法を用いた．

∈

max 

೔ ∈೔

実験においては，オンラインクエリ処理でセンサデータおよ1.0

びクラスタデータを RAM に読み込んだ時点から，検索結果を


. 
0.5

 

,

取得するまでの計算時間を測定した．実験で用いたクエリは，
0.5





 ,

,
0

q.w と q.λ がそれぞれ表 1 に示す一定範囲内でランダムに設定

,

, , . 

0

1.0
0.5(a) 第1項の上界推定0.5(b) 第2項の上界推定されたものである．作成されたランダムな 100 個のクエリを処理した際の，計算時間の平均値を調べた．

1.0

図 3 階層クラスタの上界の推定

6. 1 空間半径 r1 および環境属性値半径 r2 の影響
クラスタの空間半径 r1 を変化させた場合の計算時間を，環境
属性が 4，10，20 次元の場合について，それぞれ図 5(a)，(b)，表 1 パラメタの値

パラメタ(c) に示す．また，クラスタの環境属性値半径 r2 を変化させた値

場合の計算時間についても，同様に図 5(d)，(e)，(f) に示す．そ

データセットサイズ N

1M

要求データ数 k

5 - 50 (15)w の各要素0.0∼1.0λ

0.0∼5.0

環境属性の次元数 n4, 10, 20

れぞれの図から，クラスタ半径が大きい場合，従来手法・拡張手法ともに計算時間が長くなっていることがわかる．これは，クラスタ内データの評価値の上界を過大に推定しており，走査対象から除外できたクラスタ数が少ないためである．一方，クラスタ半径が小さい場合も，従来・拡張手法ともに計算時間が

. 

. 

長くなっていることがわかる．これは，クラスタ半径が小さくなると，生成されるクラスタ数が増加することによる．走査対象クラスタ数を削減できても，クラスタの上界を計算するため

にすべてのクラスタの中心データを走査しなければならず，結果として全体の計算時間は長くなってしまう場合がある．ここで，拡張手法における最短の計算時間が，ベースライン手法，
(a) 第1属性値

(b) 第2属性値

. 

. 

従来手法に比べて短くなっていることがわかる．
次節で述べる実験では，従来・拡張手法それぞれで，計算時間を最短にした r1 および r2 を用いている．

6. 2 要求データ数 k の影響
ユーザごとに，要求データ数は異なる．そこで，要求データ


数 k を変化させた場合の計算時間を図 6 に示す．従来・拡張手

法の効果は，検索範囲内に存在するホットスポットの数に依存する．すなわち，各ホットスポットにおけるデータが全て探索
(c) 第3属性値

(d) 第4属性値

図 4 環境属性値分布されるまで，走査データ数削減の効果は大きく働く．ここでも，拡張手法における最短の計算時間が，ベースライン手法，従来手法に比べて短くなっていることを確認した．

7. お わ り に
6. 評 価 実 験

本稿では，高次元な環境情報を扱うモバイルセンサデータ

Top-k 検索結果の多様化処理における，拡張手法の性能を評

ベースにおいて，効率的な Top-k 検索結果の多様化手法を提案

価する．表 1 は各パラメタの値を示し，太字はデフォルト値とした．拡張手法では，事前にモバイルセンサデータに対し階層する．

的クラスタリングを行う．オンラインクエリ処理では，上位ク

データの位置情報を，各次元の値が区間 [0, 1] 上の一様分布

ラスタおよび下位クラスタの上界を推定し，それぞれのクラスに従う，2 次元ベクトルで与えた．また，データの環境属性値

タ単位で走査対象データの絞り込みを行う．また，基準データ

は，図 4 に示すような空間的自己相関の特徴を有する分布に従の候補を上位クラスタごとに記憶することで，短時間で評価値う値とし，1 次元から 4 次元まで設定した．環境属性数が 10 まの高い基準データを取得できる．

たは 20 の場合は，これらのパターンを繰り返し第 5 属性以降

クラスタ半径，要求データ数 k を変化させたシミュレーショ

に割り当てた．具体的な環境属性値は，データの位置情報から

ン実験から，拡張手法は従来手法に比べ計算時間を削減できる決定される．また，センシング時の誤差を考慮して，位置情報

ことを確認した．

から決定される環境属性値に対し，N (0, 0.3) の正規分布に従う正規乱数を加算した．
比較手法は，3. 2 節で説明したベースライン手法，および 4.

近年，検索結果の多様化問題を継続的に行う研究が盛んに取り組まれている．今後の課題の一つとして，モバイルセンサ
データベースにおける，効率的かつ高精度な多様化結果のモニ

1000

100

10
ベースライン

従来手法

10000

計算時間[msec]

1000

計算時間[msec]

10000

計算時間[msec]

10000

100

10

拡張手法

ベースライン1
0.1

10
ベースライン

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

0.1(a)   4(b)   10(c)   20

10
従来手法

10000

計算時間[msec]

計算時間[msec]

100

1000

100

10
ベースライン

拡張手法

1

従来手法

1000

100

10

拡張手法

1
0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5

0.1

‫ݎ‬ଵ

10000

1000

拡張手法

0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

‫ݎ‬ଵ

10000

従来手法

1

‫ݎ‬ଵ

ベースライン

100

拡張手法

1
0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09

計算時間[msec]

従来手法

1000

ベースライン

従来手法

比較手法1

1
1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 2.3 2.4 2.5

1.5 1.6 1.7 1.8 1.9 2 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3

‫ݎ‬ଶ

‫ݎ‬ଶ

‫ݎ‬ଶ

(d)   4(e)   10(f)   20

図 5 空間半径 r1 および環境属性値半径 r2 の影響

100000

計算時間[msec]

10000
1000
100
10
ベースライン

従来手法

拡張手法

1
5

10

15

20

25

30

35

40

45

50

݇
図 6 要求データ数 k の影響

タリングの検討が挙げられる．
謝

辞

本研究の一部は，文部科学省科学研究費補助金・基盤研究(A)(26240013) および JST 国際科学技術共同研究推進事業（戦略的国際共同研究プログラム）の研究助成によるものである．
ここに記して謝意を表す．

文

献[1] Drosou, M. and Pitoura, E.: Disc diversity: result diversification
based on dissimilarity and coverage, VLDB, Vol. 6, No. 1, pp. 13–
24 (2012).
[2] Fraternali, P., Martinenghi, D. and Tagliasacchi, M.: Top-k Bounded
Diversification, ACM SIGMOD, pp. 421–432 (2012).
[3] Gollapudi, S. and Sharma, A.: An Axiomatic Approach for Result
Diversification, World Wide Web, pp. 381–390 (2009).
[4] Hasenfratz, D., Saukh, O., Walser, C., Hueglin, C., Fierz, M., Arn, T.,
Beutel, J. and Thiele, L.: Deriving high-resolution urban air pollution
maps using mobile sensor nodes, Pervasive and Mobile Computing,Vol. 16, Part B, pp. 268 – 285 (2015).
[5] Jiang, H., Cheng, J., Wang, D., Wang, C. and Tan, G.: A General
Framework for Efficient Continuous Multidimensional Top-k Query
Processing in Sensor Networks, Parallel and Distributed Systems,
IEEE Transactions on, Vol. 23, No. 9, pp. 1668–1680 (2012).
[6] Kurasawa, H., Sato, H., Yamamoto, A., Kawasaki, H., Nakamura,M., Fujii, Y. and Matsumura, H.: Missing sensor value estimation method for participatory sensing environment, 2014 IEEE International Conference on Pervasive Computing and Communications(PerCom), pp. 103–111 (2014).
[7] Ma, Q., He, C., Wu, J., Liu, Z., Zhang, Q. and Sun, Z.: Quantifying spatiotemporal patterns of urban impervious surfaces in China:
An improved assessment using nighttime light data, Landscape and
Urban Planning, Vol. 130, pp. 36 – 49 (2014).
[8] Rana, R. K., Chou, C. T., Kanhere, S. S., Bulusu, N. and Hu, W.:
Ear-phone: An End-to-end Participatory Urban Noise Mapping System, Proceedings of the 9th ACM/IEEE International Conference on
Information Processing in Sensor Networks, IPSN ’10, pp. 105–116(2010).
[9] Yokoyama, M. and Hara, T.: Efficient Top-k Result Diversification
for Mobile Sensor Data, 2016 IEEE 36th International Conference
on Distributed Computing Systems (ICDCS), pp. 477–486 (2016).