DEIM Forum 2019 F7-4

属性改良問題に対する効率的な検索手法に関する研究
小栗 大輝†

董于洋†

陳漢雄††

古瀬一隆††

北川 博之††† 筑波大学院 システム情報工学研究科 コンピュータサイエンス専攻 〒 305–8573 茨城県つくば市天王台 1-1-1†† 筑波大学 システム情報系 〒 305–8571 茨城県つくば市天王台 1-1-1
E-mail: †s1820626@s.tsukuba.ac.jp, touuyou@gmail.com, ††{chx,furuse,kitagawa}@cs.tsukuba.ac.jp
あらまし EC サイトなどでよく見られるユーザの好みや商品の持つそれぞれの特性に対しての評価が，d 個の実数値，つまり d 次元ベクトルで表されるような場合において活用ができる情報推薦技術がこれまで活発に研究されてきた．
このような研究は，ユーザが好みそうな商品をランキング形式で効率よく求めるといった場合や商品販売者が商品を買ってくれそうなユーザを効率よく見つけるといった活用が考えられる．本研究では，このような研究の応用である
属性改良問題に着目した．属性改良問題は，商品販売者が与えたクエリに対してある条件化で改良を行う場合に，その改良を効率よく求めるといった問題である．具体的に，属性改良問題を解く際に局所最適解に陥らないようシードを生成し，それらとヒューリスティックなアルゴリズムの組み合わせを用いた手法を提案する．実験により提案手法にかかる実行時間や求められる解の比較，考察を行った．
キーワード 属性改良問題, Improvement Query, 情報検索

1 はじめにクエリによる情報検索技術の一つとして，一つのオブジェクトをクエリとして与え，対象のオブジェクト群により高く評価されるような属性の改良を提案する Improvement Query [1] に関する研究がこれまで行われてきた．このような研究は，例えば，EC サイトなどで商品販売者が EC サイト利用ユーザの好み情報をもとに商品の改良を行う場面のような，マーケティングでの活用が考えられる．属性改良問題の研究は，これまで活発に研究が行われてきたクエリによる情報検索技術である Top-k

図 1 k=3 の Top-k query の例

query [2] や Reverse Tok-k query [3] の応用である．このような情報検索技術では，それぞれのオブジェクトはベクトルの数値として表現される．そして，与えられたクエリとその他オブジェクトの内積計算などを用いてクエリの他のオブジェクトに対する評価を算出し，ランク付けを行うことで条件を満たすようなオブジェクト群の検索を行う．Top-k query は，EC サイトで例えるとユーザ視点の情報検索手法であり，クエリとして与えられたユーザに対して商品をどのように評価するかを算出し，評価の高い商品上位 k 位までのランキングを返すような手法である．また，Reverse Tok-k query は商品販売者視点の情報検索手法であり，クエリとして一つの商品を与えた時に，その商品を k 位より高く評価するユーザ全てを求めるような検索手法である．
これに対して属性改良問題は，商品販売者がユーザからの評価が低い商品に対して属性値の改良を行い，評価を上げることでユーザに届くような商品にしたいといった場面での問題となる．このような場面においては，闇雲に商品の属性値を改良するのではなく，実際には様々な制約が与えられた中で改良を行うこととなる．例えば，クエリとなる商品を 10 位以内に評価するユーザをある一定数まで増やしたいが，その中でもかかる

図 2 IQ で正しく改良の評価がなされていない例

コストは最小になるような改良を知りたい．であったり，またときにはある一定の予算が存在し，改良にかかるコストがその予算を超えない中で最大の改良効果を得られるような属性値の改良を知りたい．と言ったことが考えられる．このように，与えられた制約の中で最大の効果が得られるようなクエリ属性の改良を提案するのが，属性改良問題である．
これまで提案がされた属性改良問題の解決アルゴリズムには，その求め方の性質上実世界での利用にそぐわない部分が存在する．例えば，クエリとして与えられたオブジェクトによっては，改良を正しく評価できないような場合がある．[4]．図 2 に検索する手法である．Top-k query へのヒットとは，クエリ商品その例を示す．図 2 では商品の改良がなされているにも関わらがユーザの評価上位 k 番目以内に含まれるということを表す．

ず Top-k query のヒット数が変化しないため，改良として評価

また，Max-Hit IQ はある予算が与えられた際にその予算内でされない．

Top-k query のヒット数が最大となるような改良戦略を検索す

本研究では，属性改良問題について，改良にかかるコストがる手法である．Min-Cost IQ と Max-Hit IQ の定義を定義 3，定少ない属性から優先的に改良をしていく手法や一定間隔で予算

義 4 でそれぞれ示す．定義 3，定義 4 の関数 Hk (q) はクエリ商を分配し作成した改良戦略候補の中からより良い改良戦略を求

品 q ∈ P の Top-k query のヒット数を表す．

める手法のようなヒューリスティックな解法を用いた時に生じる問題の解決を目指す．具体的には，属性改良問題を解く際に定義 3 (Min-Cost IQ) オブジェクト改良の目標として Top-k局所最適解に陥ってしまうパターンを避けられるようランダム

query の最小ヒット数 τ ∈ I，クエリ商品 q ∈ P ，クエリ q を改なシードを生成し，それのシードに対して改良コストが少ない

良した時にかかるコストを表すコスト関数 Costq が与えられた属性から改良してくような組み合わせを用いた手法を提案し，時，Hk (q + s) >= τ かつ Costq (s) が最小となるような q に対実験により実行速度や誤差の測定を行い，考察を行った．

する改良戦略 s を求める．

1. 1 問 題 定 義

定義 4 (Max-Hit IQ) 予算 β ∈ R，クエリ商品 q ∈ P ，クエリ商品のデータ集合を P ，ユーザの好みのデータ集合を U ，各
商品 pi ∈ P が d 個の属性値を持ち，d 次元のベクトルで表され，
(1)

(2)

(d)

商品 pi の各属性値は pi = (pi , pi , . . . , pi ) とする．そして各ユーザ uj ∈ U が d 個の属性に対するユーザの好みを表す d 次
(1)

(2)

(d)

元のベクトルであり，ユーザの好みは uj = (uj , uj , . . . , uj )∑(k)として， dk=1 uj = 1 とする．本研究では，q ∈ P をクエリ商品として一つ与えた時に，条件を満たす改良戦略を効率良く検索することを目的とする．改良戦略の定義を定義 1 に示す．
定義 1 (改良戦略)

オブジェクトに対する改良戦略を s とする．

改良戦略 s は d 次元のベクトルとして s = (s1 , s2 , . . . , sd ) と表す．改良戦略 s を元のオブジェクト pi に適用した改良後オブジェクト p′i は，p′i = pi + s で与えられる．
本研究では，商品集合とユーザの好みデータ集合から商品のランク付けを行い，そのランクを使って属性改良問題を解く．
ここで，ランクとは商品ベクトルとユーザの好みデータベクト
ルの内積を評価値として計算し，その評価値が高く評価されるものから順に並べたものを指す．商品ベクトルとユーザの好みベクトルの定義は問題定義 1.1 に示す通りであり，ベクトルの属性値は計算の便宜上 0 に近づくほど評価が良いものとする．

2 関連研究本研究は候補となる改良オブジェクト集合から評価の高い改良オブジェクトを見つけるために，Reverse k-rank query [5] [6] [7]を利用する．定義 2 に Reverse k-rank query の定義を示す．

q を改良した時にかかるコストを表すコスト関数 Costq が与えられた時，Costq (s) <= β かつ Hk (q + s) が最大となるような qに対する改良戦略 s を求める．
先行研究 [1] の IQ では，これらの Top-k query のヒット数を用いた改良戦略の求め方について定義がなされた．また，改良後オブジェクトの Top-k query のヒット数を効率よく求める手法として Efficient Strategy Evaluation(ESE) という手法が提案された．

3 提案手法
本研究では，Improvement Query [1] で定義された Max-HitIQ の考え方を参考に属性改良問題を解いていく．また，Improvement Query の問題点を解決するために Top-k query のヒッ
ト数ではなく，オブジェクトの改良によるランク変化に着目し属性改良問題を解く手法である，Reverse Rank ImprovementQuery(RRIQ) [4] [8] をベースとした手法を提案する．RRIQ 問
題は NP 困難であるため ( [8] の 3.2 を参照)，ヒューリスティッ
クに属性の改良を求める手法を提案する．先行研究の問題点として，ヒューリスティックに改良戦略を求める手法を用いるため，局所的最適解に陥ってしまう場合がある．そこで，ランダムなシード生成とヒューリスティックな手法のハイブリッドな手法を用いて改良戦略を求めることで，このような問題を回避しながら属性改良問題を解くことができるような手法を目指す．

RRIQ 問題を解くため，本研究では 3 つのステップで改良戦略を求める．まず，1 つ目のステップで，ランダムな改良戦略候補を作成する．2 つ目のステップでは，これらの改良戦略候定義 2 (Reverse k-rank query) 商品のデータ集合 P ，ユーザ補に対して与えられた予算内で属性の改良を行うことを考える．の好みデータの集合 U ，正整数 k ，クエリ商品 q を与えた場

具体的には，改良にかかるコストが低い属性を繰り返し選びな合．Reverse k-rank query は次のデータ集合 S を求める．即ち，S ⊆ U, |S| = k であり，∀ ui ∈ S : ∀ uj ∈ (U − S) :Arank(ui , Q) <= Arank(uj , Q) が成り立つ．

がら一定値の属性改良を行っていく．そして，3 つ目のステッ
プでは，Reverse k-rank query を利用し，改良後オブジェクト集合からもっとも改良後のランク上昇量が大きいオブジェクトを先行研究 [1] では IQ を求める手法として Min-Cost IQ と Max-見つけ，そのオブジェクトの改良を属性改良問題の解とする．

Hit IQ の二つの方法が提案された．Min-Cost IQ は与えられた

以降，用いる記号は表 1 にまとめ，特に断りのない限り表に任意の数の Top-k query にヒットする改良戦略を最小コストで示した意味として用いることとする．

表 1 アルゴリズム 1 内で使用する記号とその意味

Algorithm 1 Create Random Improvement Query Candidates

記号

意味

Require: q, b, d, max candidates numk

逆 k ランククエリのパラメータ kEnsure: a set of candidated

商品およびユーザオブジェクトの次元数1: while candidates num == max candidates num doP

商品集合

2:

candidate ← q

U

ユーザの好みデータ集合

3:

current dimention ← 1q

クエリ商品

4:

while current dimention == d dob

改良予算 (>= 0)

5:s

改良戦略

6:

δ

属性の改良幅7:

逆 k ランククエリ関数8:

RkR

Arank クエリ商品の平均ランクを求める関数
S

改良戦略の候補の集合

3. 1 コスト関数

candidate’s d th attribute - random amount> 0 thenif candidate’s d th attribute =current dimention++;else
reset candidate’s d th attribute9:

continue;10:11:

end if12:

end while13:

if candidate’s improvement cost < b thencandidates ← candidate

本研究では，改良戦略を求める際にクエリ商品に改良戦略を14:適用した時のコストを考える．コストは先行研究と同様にクエ15:

リ検索時に利用者から与えられたコスト関数を元に計算をする．

16: end while関数としてコストをモデル化するのは一般的な考えであり [9]，17: Return candidates

本研究の実装には簡単のため，Costq (s) = s となるコスト関数を用いることとする．つまり，属性の改良した値がそのままコストになるという考え方で改良戦略を求めていく．また，本来

end ifAlgorithm 2 Candidates attribute improvement
Require: q, b, d, δ, a set of candidate
Ensure: a set of improved candidate

であれば属性ごとに違ったコスト関数となるべきであり，例え

1: for c ∈ a set of candidate do

ばクエリ商品としてパソコンを考えた時に，CPU を強化するの

2:とメモリを強化するのとでは，同じように商品が改良されたと

3:

for current dimension in range(1,d) do

しても，実際にかかるコストが大きく変わってくる．このよう4:c current dimention attribute -= δ

な属性値毎にかかるコストの差を表現するようなコスト関数に

5:if c current dimention attribute < 0 then

ついての実験は今後の課題としている．

3. 2 提案アルゴリズム
ステップ 1 となるランダムな改良戦略候補の作成アルゴリズ

while c’s improvement cost < b doc current dimention attribute ← 0

6:

end if7:

cost ← Cost(q, c)

8:
9:

end for10:

min cost attribute dimention ← cost

ムを Algorithm1 に示す．Algorithm1 では改良対象となるクエ

11:

リ，クエリ改良に使える予算，オブジェクトの次元，そして最12:

終的にいくつ改良戦略候補が必要かという数値が渡される．こ13: end for

れらを元に Algorithm1 は改良候補となるオブジェクトの集合

14: Return improved candidates

improved candidates ← c that min cost attribute improved by δend whileを返す．

Algorithm1 の処理は以下の手順にしたがって行われる．与えAlgorithm2 に示す．Algorithm2 では改良対象となるクエリ，クられた改良対象のクエリの各次元の属性に対して，ランダムにエリ改良に使える予算，オブジェクトの次元，属性の改良幅，改良を加える．この時，クエリの各属性は 0 から 1 の間に正規改良候補オブジェクトの集合を与える．これらを元に各属性に化されており，また 0 に近づくほど良いとする．各次元でランヒューリスティックな改良を加えた，改良候補オブジェクトのダムな改良を加えた際に，属性が 0 を下回っていないかチェッ集合を返す．

クし，正しく改良が行われていた場合は次の次元の属性の処理

Algorithm2 の処理は以下の手順にしたがって行われる．Al-に移る．この処理はあらかじめ設定された商品そしてユーザのgorithm1 で得られた改良候補オブジェクト集合全てに対して処好みオブジェクトの次元数に処理を行った次元数が一致するま理を行う．また，対象クエリからの改良コストが与えられた予で繰り返される．全ての次元について改良が終わった時点で，算 b を超えないように改良を行う．

改良にかかった予算が与えられた予算の上限を超えていなけれ

改良の手順は，まず一定の値の δ の幅だけ改良候補に改良をば解となる改良候補オブジェクト集合に追加する．最終的に改加えた c を作成する．この c に関して改良コストの計算を行良候補オブジェクト集合が規定の数に達した時点で処理を終了う．指定された属性の次元数にしたがって全ての属性に対してする．

実行し，元の改良候補オブジェクトの属性の中でもっとも改良

ステップ 2 となる改良戦略候補に対して与えられた予算内でにコストがかからない属性を見つける．この属性に対して改良ヒューリスティックに属性の改良を行うためのアルゴリズムをを行ったオブジェクトを作成する．この時点で改良コストが与えられた予算を超えたら終了し，超えていない場合は再度各属性に一定値の改良を行う部分まで戻り，同様に処理を行っていく．改良が終了した時点で返り値となる改良後オブジェクト集合にその改良オブジェクトを保持する．

4 実験・考察4. 1 実 験 環 境
提案手法の有用性を示すために，貪欲に改良戦略を見つけ出し適用する方法と提案手法について実験を行い，その結果を示した．実験環境を以下に示す．

•OS: macOS High Sierra 10.13.6•

CPU: 2.7 GHz Intel Core i5•

メモリ: 16 GB 1867 MHz DDR3•

開発言語: C++図 3 実行速度の測定結果

4. 2 実験データ
実験に使用するデータの値，変量を表 2 に示す．また，ユーザの好みと商品の属性値は 0 ∼ 1 に正規化を行い，0 に近づくほど良い評価とする．それに伴い，スコアの計算も内積の値がより小さい方が良い評価となり，高いランクがつくことになる．
商品集合 P とユーザの好みデータ集合 U には合成データを使

図 4 改良にかかったコストの測定結果用して実験を行った．また，P と U の合成データは一様分布で生成した．ランダムに改良戦略を生成する手法，ランダムに生成したのちにヒューリスティックな改良を加えた手法の実行速度，予算内での消費コスト，貪欲に全通りを探索する手法との精度の比較を示した．
表 2 実験データ設定一覧
データ

意味値|P |

商品数5,000

ユーザ数

1,000|U |ランダムに生成する改良の数 100–1,000rd

オブジェクトの次元

3b

予算上限

1.0k

RkR のパラメータ|U |/100

図 5 精度の測定結果

横軸にランダムな改良戦略をいくつ生成した実験かを示してい

4. 3 考察る．今回の実験では予算を 1.0 と設定しているので，これに近ければ近いほど無駄なく改良戦略を作成できていることになる．

図 3 には実行速度を測定した結果が示されている．縦軸にランダム手法では，500，900 などのランダム生成数で大きく消実行時間，横軸にランダムな改良戦略をいくつ生成した実験か費コストが下がっていることがわかる．ランダムに生成されたを示している．実行速度に関しては，貪欲手法では 2392.71 秒

ものでは，予算内での改良が正しく行われず，予算に無駄が生かかった．それと比べ，ランダム手法そしてハイブリッド手法じてしまっている．それに対しハイブリッドな手法では，全てのどちらも大幅に実行速度の減少が確認できた．また，ハイブの値で 1.0 に近い値を示しており，ヒューリスティックな属性のリッドな手法に関しては 700 個以上のシードを作成すると徐々改良により効率的に予算の分配が行えていることが確認できる．にではあるがランダムのみの手法と比べて実行時間が伸びてい図 5 には貪欲な手法で生成した改良戦略とランダム手法，ハく傾向を示すことがわかった．線形でなく緩やかに指数的に実イブリッド手法それぞれで求めた改良戦略を比較し，その誤差行速度が上昇しているので，より多くのシード値の生成に関しを測定したものである．縦軸に解となった改良戦略と貪欲な手てさらなる検証が必要である．

法で測定した改良戦略の平均二乗誤差を示し，横軸にランダム

図 4 には予算内での改良に対して，どれほどのコストがかかったかを示している．縦軸に予算に対する消費コスト (<= 1.0)，なシード生成数を示している．ここで，ランダムなシード生成数が増えると解となる改良戦略は貪欲な手法のものに近づいていくと予想したが，実験の結果としてはランダム手法もハイブリッド手法も不規則な誤差を示してしまう結果となった．また，ランダム手法とハイブリッド手法を比べると全体としてハイブリッド手法の方が誤差が小さくなっているものの，ハイブリッド手法の方が大きな誤差が生じてしまう実験結果も見られた．このような結果の原因として，シード値の取り方による精度のばらつきが考えられる．あらかじめユーザ集合の特徴から良い傾向が得られそうなシード値に限定して生成を行う，またはシード値の繰り返し生成により有望なシード値が生成されやすいような重み付けを行っていくなどと行った操作を行うことでこのような精度のばらつきを抑えられるのではないかと考える．

5 おわりに
本研究では，先行研究で提案された RRIQ をベースに，ランダム手法とヒューリスティックな手法を組み合わせた属性改良問題解決アルゴリズムを提案した．これは，先行研究の NP 困難な問題に対してヒューリスティックな手法を用いて解を求める場合に局所的最適解に陥ってしまうことがあるという特性を解決するような手法として提案した．今後の課題としては，一様分布の合成データ以外にも実データを含め様々な分布のデータに対して実験，考察を行う必要があることや，現在完全にランダムで行っているシードとなる改良戦略の生成について，ユーザの好みデータ集合の傾向や生成したシード値に関して測定を行い，より精度の上がるようなシード値の生成手法を提案することなどが考えられる．実験方法についても，現在商品数|P | = 5000，|U | = 1000 という限られた数に限定しているので，より多くの数，そして次元数のデータセットに対しても十分な実験，考察を行う必要がある．

文献[1] Yang, G., Cai, Y.: Querying Improvement Strategies. EDBT. pp.
294–305, 2017.
[2] Ilyas, I.F., Beskales, G., Soliman, M.A.: A survey of top-k query
processing techniques in relational database systems. ACM Comput.
Surv. 40(4), 11:1–58, 2008.
[3] Vlachou, A., Doulkeridis, C., Norvag, K., Kotidis, Y.: Branch-andBound Algorithm for Reverse Top-k Queries. SIGMOD 13, pp. 481–492, 2013.
[4] 小栗 大輝., 董 于洋., 陳 漢雄., 古瀬 一隆.: 改良コスト最小化の逆
情報推薦. DEIM Forum 2018 D3–5.
[5] Zhang, Z., Jin, C., Kang, Q.: Reverse k-ranks query. PVLDB 7(10),785796, 2014.
[6] Dong, Y., Chen, H., Furuse, K., Kitagawa, H.: Aggregate Reverse
Rank Queries. DEXA 2016, pp. 87–101, September 5–8, 2016.
[7] Dong, Y., Chen, H., Furuse, K., Kitagawa, H.: Grid-Index algorithmfor reverse rank queries. EDBT 2017, pp. 306–317, March 21–24,2017.
[8] 山下 雅弘., 佐野 ひかり., 陳 漢雄., 古瀬 一隆., 北川 博之.: 逆ラン
ク検索による情報改良支援. DEIM Forum 2018 D4–3.
[9] J. Viner. Cost curves and supply curves. Springer, 1932.