IEEE ICDMDMC2007 その2
Machine Learning初心者によるまったりゆるゆるDMC,二回目.とりあえず前回学習一切無しで76.8%の正答率というベンチマークが出たので,これを超えたい.
k-means
普通のk-meansでは初期ラベルをランダムに割り当てるのだが,半教師あり学習なのでちょっと手順を修正する.もっといいやり方があるかもしれない.
1.ラベルありデータを使って各ラベルの重心を求める.
2.ラベルなしデータとの距離を計算し,最も近いラベルをに割り当てる.
3.新しい割り当てに基づいて各ラベルの重心を再計算する.
4.2.でラベルを割り当てたデータについて再度との距離を計算し,最も近いラベルを割り当て直す.
5.ラベルが変化しなければ終了.変化した場合は3.に戻る.
結果
ノルムを数通りに振って,一番良いケースで1183/2137(55.3%).
重心計算時に小手先の修正(スレッショルド以下の軸を切り捨てるなど)を加えても改善しなかった.
なんでこんなに悪いのか
重心からの距離を評価に用いるので,各ラベル付きデータが超平面上で球形ではない場合k-meansがあまり有効ではなくなる.データが超平面上で球形ということは「各アクセスポイントからの信号に同程度のバラツキが乗っている」ということなので,この仮定が今回のケースではあまり正しく無いかもしれない.
もうちょっと別の方法
- ラベルなしの訓練データについて尤度関数を以下に定義し,最尤のものをラベルとする.wはp-ノルム.
ただし,ラベルありデータに対して
- j番目のテストデータにはとなる訓練データiを探し,ラベルを付与
という方法を採ってみる.学習無しの際に用いてk-meansより良くクラスタリングできた,「もっとも近いデータからラベルを貰う」という発想を拡張している.分母がなぜかになっているのは,本当はにしたかったけど計算時間がかかり過ぎたので妥協したというだけ.
結果
1626/2137(76.1%).良くならない…
なんで
信号強度のノルムは雑音が強すぎる?
時系列を評価に組み込む
「テストデータの全部と訓練データの一部は,時系列順に並んでいる」という情報も使えるので,こちらを使わない手は無い.
前後数ステップでの推定値と同じラベルに対して定数倍の重みをつけてやる.
結果
重みのパラメータを幾らか振り,一番良いケースで1724/2137(80.67%).だいぶ改善された.
Graph basedな何かを追加
今回の問題では,「クライアントがグリッド上をどう移動するか」を推定する.グリッドが具体的にどういう並びなのかは与えられていないが,あるグリッドにいるクライアントが次の時間にどこにいそうなのかは,訓練データからある程度絞り込めそうではある.
学習の際にあるスレッショルドkを設定し,i番目とi+1番目のデータについて,
が成立したとき,ラベルとは隣接している可能性が高い.そこで,学習中にこのようなケースに遭遇したとき,
1.の間に重み付きのbranchを追加する
2.既にbranchが形成されていた場合は重みを増やす
という操作を行う.そして,推定のフェーズではこの重みをに対して付与してやればよい.