Taka-Coma's Blog

http://taka-coma.pro/

論文採択:隠れ条件を使ったデータ結合 @HMData_IEEE Big Data 2017

概要

  • 別個に管理されたデータは一貫性が常に保たれているとは限らない
  • 一貫性の保たれていないデータ同士の結合では不要な結果を産むことがある
  • 後処理として分析などを行う際にデータの不整合が起き悩まされることになる
  • この問題に対して,ユーザにある程度の正しい結合結果を提示してもらう
  • 正しい結果から隠れた結合条件(隠れ条件)を見つけ出し,全体の結合を正しく行う
  • 隠れ条件を見つける際の計算量をヒューリスティクスで削減
  • 実験で実データに対する有用性とヒューリスティクスの有効性を確認

内容

  • 入力:リレーション R, S と結合条件 J
  • 状況:RとSをJで結合しても期待される結果 U* を得られない
  • 仮定:RとSのレコード間には順序に基づく関連性が存在する
  • イデア:ユーザに期待される結果の一部 U^ を作成してもらい,そこからRとSのどの属性(組)間に順序に基づく関連性が存在するかを発見する.
  • 問題:属性の順序付きの組合せは O(NR!*NS!)の計算量になる.(NR, NSはそれぞれRとSの属性数)
  • 解決のアイデア:属性列の prefix による順序付けが決定的になった場合,それよりも属性を後ろに付け足しても順序は変わらない
  • 解決策:ボトムアップ方式で属性の順序つき組合せを幅優先探索し,決定的な順序付けが見つかり次第探索を打ち切る

実験

実データ(藤沢市のゴミ収集データ)を用いた手法の有用性実験

  • 藤沢市のゴミ収集データに対して本手法を適用し,結合処理の後処理に足しする人手作業がどれだけ削減できるかを確認
  • 人手作業:人が確認しなければならないレコード数(要は結合結果のレコード数)
  • 77%の削減に成功.これは,常に77%になることは保証できないが,大幅な削減が期待できる結果である.

人工データを用いた手法の有効性実験

  • 人工的に作ったデータで枝刈りがうまくできているか検証
  • 結果:効果てきめん

成果

  1. Takahiro Komamizu, Toshiyuki Amagasa, Hiroyuki Kitagawa, "Implicit Order Join: Joining Log Data with Property Data by Discovering Implicit Order-oriented Keys with Human Assistance", in Proc. The First IEEE Workshop on Human-Machine Collaboration in BigData (HMData2017) co-located with IEEE Big Data 2017 , pp. ,Boston, USA, December 11-14, 2017 (to appear)