FAHES: A Robust Disguised Missing Values Detector

FAHES: A Robust Disguised Missing Values Detector(KDD2018 Research Track Papers)を読んでまとめました。
解釈間違い等ある時がありますので、その場合指摘いただけると助かります。

背景と概要

背景

実データにおいて、データはきれいな状態である訳ではなく、そのデータを基にした誤った意思決定が行われる場合がある。
そして欠損値は一般的なものであると同時にデータ分析において深刻な影響を与える事がある。
また元は欠損値だったものを人為的に埋められたデータも存在している。 (本内容では、missing valueを欠損値の表現で統一します)
一般的に、欠損値には2種類存在する。
- explicitly missing values(明示的欠損値):NULL等
- implicitly missing values(別名disguised missing values (DMVs)、暗示性欠損値):電話番号を11111111で埋めている等
explicitly missing valuesの検出は容易だが、DMVsはそうはいかない。

概要

本論文では、DMVsを検出するロバストなシステムとしてFAHESが提案されている。
DMVsとその検出方法は以下で構成される
- 検出可能なoutlier
  - カテゴリ変数に対するsyntactic outlier detection
  - 連続変数に対するdensity-based outlier detection
- 検出可能なinlier
  - 以下の問題とする
  - missing-completely-at-random(MCAR)
  - missing-at-random(MAR)
FAHESは上記のアンサンブル手法となる。

DMVs

DMVsのタイプ分け

検出可能なDMVsが以下の5タイプに分けられている

変数定義の範囲外(e.g.正の値しかとらない変数に負の値が入っている等)
外れ値(e.g.年齢の変数に1000が入っている)
同じ数字が連続しているか、キーボードの隣り合った文字が入力されている(e.g.電話番号で55555555が入っている)
データタイプが合っていない(e.g.数値変数に文字が入っている)
データの範囲でランダムな値が入っている

f:id:yhiss:20200118145429p:plain — DMVsのサンプル

DMVs検出問題の定式化

作りたいのは以下の式で定義される $T' = [t'_{ij}$ ]

FAHES Architecture

FAHESのアーキテクチャは以下の要素で構成されている。

Statistical Profiler
Detection Engine
Aggregation

f:id:yhiss:20200118185235p:plain — アーキテクチャ概要

Statistical Profiler

以下のような統計量を取得する。

テーブル毎の統計量(e.g. #-records,#-attributes)
カラム毎の統計量(e.g. #-empty (null) cells, #-numerical entries, #-strings, #-distinct values)

Detection Engine

DMVsのタイプに応じた下記の異なるモジュールを含んでいる。

outlier
- syntactic outlier detector
  - 以下を含む
  - syntactic pattern discovery
  - repeated patterns discovery
  - numerical outlier detector
inlier
- RandomDMVD
- 以下を含む
- missing-completely-at-random (MCAR) model
- missing-at-random (MAR) model

f:id:yhiss:20200118185316p:plain — DMVの例(a,b:outlier、c,d:inlier)

Aggregation

同じDMVが異なるモジュールにおいて検出されることがあるため、重複を加味して返す

DMV Ensembles

検出精度の向上のため、外れ値検出のアンサンブル手法を参考にした、各々の検出モジュールのアンサンブルを行っている。
DMV detectionおよび外れ値検出は、双方共に教師なし問題となる。
各々のモジュールからは0~1のスコアが算出される。アンサンブル手法詳細は以下文献を参照している。
[C. C. Aggarwal. Outlier ensembles: Position paper. SIGKDD Explor. Newsl., 14, 2013.]

DMVs検出モジュール

モジュールの中身はざっくりまとめていきます。
Syntactic Pattern(SynPat) Discovery

構文の構成要素を下の表のように定義

f:id:yhiss:20200119171629p:plain 上記より、電話番号は d¹⁰ 、ZIPコードが d⁵ - d⁴ と表される。
更に下記のルールを用いる事でパターンを減らしている。

f:id:yhiss:20200119173756p:plain その結果下図のようなパターンが検出される。

f:id:yhiss:20200119174014p:plain — パターン例

f:id:yhiss:20200119174103p:plain — Syntactic Pattern Discoveryのアルゴリズム

Repeated Pattern Identification

連続したパターンの検出は、スコアリング関数rep(S)を定義して、以下の様に行われる。

Numerical Outlier Detector

アルゴリズムは以下で表される。

RandomDMVD

RandomDMVDではMCARモデルおよびMARモデルを用いている。
下記の論文をコンセプトとしてモデルが構築されている。
- [M. Hua and J. Pei. Cleaning disguised missing values: A heuristic approach. In KDD’07, 2007.]
- [M. Hua and J. Pei. DiMaC: A disguised missing data cleaning tool. In KDD’08, 2008.]
詳細な中身は今回割愛します(参考論文含めて別の機会にまとめたい)

まとめ

データにおける欠損値を以下の2つで定義している。
- explicitly missing values(明示的欠損値)
- implicitly missing values(別名disguised missing values (DMVs)、暗示性欠損値)
検出可能なDMVsとして5タイプで定義
アーキテクチャは以下の要素で構成されている。
- Statistical Profiler
- Detection Engine
- Aggregation
Detection Engineでは以下のモジュールで構成される。
- outlier
  - syntactic outlier detector
    - syntactic pattern discovery
    - repeated patterns discovery
    - numerical outlier detector
- inlier
  - RandomDMVD
  - missing-completely-at-random (MCAR) model
  - missing-at-random (MAR) model

参考文献