Modeling Human Location Data with Mixtures of Kernel Densities (KDD 2014) 読んだ

概要

Modeling Human Location Data with Mixtures of Kernel Densities(pdf)
位置情報にもとづくデータから個人レベルの粒度にもとづく密度を推定する問題を解く．
混合モデルベースのカーネル密度推定(KDE)を応用して個人レベルの情報と全体の傾向を取り扱う．

問題設定

データはユーザiに関するチェックインデータ $e_i^j = <i, x, y, t>$ の tuple 集合 $E_i = \{e_i^1, \cdots\}$ の集合．
密度を推定する問題を考える．

既存研究

混合ガウスによる推定の問題点

混合数が自明でない
データがスパース
そもそも環境的な要因と移動経路などによって密度が制限される -> ガウシアンにならない

カーネル密度推定(KDE)の問題点
次元の呪い -> 今回は d = 2 なので問題ない
予測時に全データ点を持ってないといけない -> もうメモリも高価じゃないから問題ない

提案手法

通常のKDE

$f_{KD}(e|E, h) = \frac{1}{n} \sum_{j=1}^n K_h(e, e^j)$
$K_h(e, e^j) = \frac{1}{2\pi h} \exp(-\frac{1}{2} (e-e^j) \Sigma_h^{-1} (e-e^j))$
$\Sigma_h$ は対角要素にhを持つ2x2行列．
hはバンド幅と呼ばれるパラメータ．大きくしたり小さくしたりすることによってどれぐらいの幅でカーネルを当てはめるかが決まる．

Adaptive bandwidth method

バンド幅 h を入力データの近傍 k 番目の点とのユークリッド距離として，データ点ごとに h を変える．実験では k = 5 が一番良い．

Mixture of kernel density models

個人レベルのKDE
もっと荒いKDE

の二つを混ぜる．混ぜ方は
$p_MKD(e|E)=\sum_c^C \alpha_c f_KD(e|E^c)$
という感じで推定に使うデータを変えつつそれぞれの重みを推定する． $E^1$ はそのユーザの全データ， $E^C$ はユーザに限らない全データ， $c=n$ の場合は適当に決める(C=3の場合のc=2は例えば地域を9x9の81gridsに区切ってそのユーザのデータが最も含まれるgridにする)．
学習は training data から validation data を分けてパラメータ推定に使う．