Subscribed unsubscribe Subscribe Subscribe

IEEE ICDMDMC2007

うちの学科の講義としては異色の課題.IEEE ICDMのData Mining Contestを解いてみて,Machine Learningの凄い人達が出した成果に「後だしジャンケン」で勝てるか?というもの.

問題設定

詳細はこちら.ICDM DMC 07
内容はWifi信号強度を用いた位置推定.無線環境下にいるクライアントに対して,100個のアクセスポイントからの信号受信強度が与えられており,その値をもとに位置ID[1..247]を推定せよという問題.宇宙工学の世界でも惑星探査機からの受信電波を使って探査機の軌道を推定するなんてことをやってたりしますので,割と馴染み易い問題だといえるかも.
訓練データはこんな感じ.左から時刻,位置,アクセスポイントID:強度.位置が与えられていないものは‐1が代入されている.

Trace_1 
118629xxx44.984	-1	61:-92	67:-85	71:-60	73:-87	75:-74	76:-91	77:-94	79:-91	
118629xxx45.484	-1	61:-92	67:-85	71:-60	73:-87	75:-74	76:-91	77:-94	79:-91	
118629xxx51.984	-1	61:-92	67:-83	71:-65	73:-82	75:-61	76:-87	77:-93	79:-91	80:-89	
118629xxx52.484	-1	61:-92	67:-83	71:-65	73:-82	75:-61	76:-87	77:-93	79:-91	80:-89	
118629xxx52.984	-1	61:-92	67:-81	71:-68	73:-83	75:-70	76:-87	77:-93	79:-88	80:-93	81:-89	
118629xxx53.484	-1	61:-92	67:-81	71:-68	73:-83	75:-70	76:-87	77:-93	79:-88	80:-93	81:-89	
118629xxx58.984	-1	61:-82	67:-79	71:-70	73:-79	75:-60	76:-90	77:-88	79:-89	80:-91	
118629xxx61.984	-1	61:-82	67:-80	71:-66	73:-82	75:-74	76:-83	77:-88	79:-93	80:-91	
118629xxx63.484	163	61:-82	67:-79	71:-76	73:-82	75:-66	76:-93	79:-88	80:-84	81:-94	
118629xxx64.484	-1	67:-79	71:-76	73:-82	75:-66	76:-93	79:-88	80:-84	81:-94	

テストデータも同じような形式.クライアントの移動が時系列に沿って記録されているので,そちらの情報も推定に使うことができる.

Trace_1 
118629xxx85.984	71:-92	78:-75	86:-86	87:-87	90:-89	96:-77	99:-88	100:-85
118629xxx86.484	71:-92	78:-76	86:-84	87:-87	90:-86	96:-80	99:-88	100:-86
118629xxx87.484	71:-92	78:-76	86:-84	87:-87	90:-86	96:-80	99:-88	100:-86
118629xxx88.484	78:-65	86:-89	87:-86	90:-86	96:-76	99:-89	100:-86
118629xxx88.984	78:-65	86:-89	87:-86	90:-86	96:-76	99:-89	100:-86
118629xxx92.484	71:-87	78:-73	86:-91	87:-92	88:-94	90:-82	96:-79	99:-94	100:-83
118629xxx92.984	71:-87	78:-73	86:-91	87:-92	88:-94	90:-82	96:-79	99:-94	100:-83
118629xxx93.484	71:-87	78:-73	86:-91	87:-92	88:-94	90:-82	96:-79	99:-94	100:-83
118629xxx94.984	71:-87	78:-73	86:-88	88:-94	96:-79	99:-90	100:-83
118629xxx95.484	71:-87	78:-73	86:-88	88:-94	96:-79	99:-90	100:-83

全3196の訓練データのうち,位置ラベル付きは787個.1つの位置IDに対してラベル付きの訓練データが平均3.18個,少ない所では1個しか無い.また,Wifi信号は環境の影響を受けやすく,かなりノイジーであると主催者側が言っている.何らかの半教師あり学習でデータの分離境界をうまく決めたいところだけど,ノイズの素性に対して相性が悪いと逆効果にもなりそう.

まずは学習無しで

とりあえず

  • ラベル付きの訓練データのみ使用
  • 信号強度のみを推定に使用

とする.んで,推定基準は

  • 全訓練データとのp-ノルムを取り,それが最小となる相手のラベルを貰う

とする.信号強度の形が一番似ているものが持っているラベルが最も正解らしいというシンプルな推定.パラメータは何ノルムを使うかという点しか無い.

結果

1/4-ノルム 1339/2137個正解(62.6%)
1/3-ノルム 1642/2137個正解(76.8%) 
1/2-ノルム 1618/2137個正解(75.7%)
1-ノルム 1518/2137個正解(71.0%)
2-ノルム 1432/2137個正解(67.0%)
1/3ノルム〜1/2ノルム辺りにピークが来るのはデータの特性がそういうもんだということか.p<1ということは,信号強度自体の大小よりもどのアクセスポイントから信号を受けているかという情報に対してピーキー.とりあえずこの値をベンチマークとして,学習させた場合と比較してみたい.今日はここまで.