(57)【要約】【課題】関連技術の関数従属性を用いたデータクレンジングでは、修正コストが最小となる修正を選択する。この場合、修正コストが同一となる修正タプル候補が複数あるとき、その中で最も確からしいものを選ぶことができない。【解決手段】本発明のデータクレンジングシステムは、データ・ルール集合記憶部１００と、例外発生原因条件特定部１１０と、タプル修正部１２０と、修正済データ出力部１３０とを備えている。複数の例外に共通する原因条件を推定し、推定された原因条件によって最も確からしい修正タプル候補を決定するよう動作することにより、修正コストのみでは決定不可能な状況でも、確からしい修正タプル候補を選出することを可能にする。【選択図】図１
2013105440.tif 000002
【特許請求の範囲】
【請求項１】
複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶部と、
前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定部と、
推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正部と、
を備えたことを特徴とするデータクレンジングシステム。
【請求項２】
請求項１記載のデータクレンジングシステムであって、
前記例外発生原因条件推定部は、
前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与する例外疑いラベル付与部と、
前記属性の中から前記原因条件の候補を生成する原因条件候補生成部と、
前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出する例外発生原因スコア算出部と、
前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出する例外発生原因条件選出部とを有し、
前記タプル修正部は、
前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出する例外確率算出部と、
算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行するタプル修正実行部とを有する、
ことを特徴とするデータクレンジングシステム。
【請求項３】
請求項２記載のデータクレンジングシステムであって、
前記修正処理は、修正の対象となる前記タプル及びその修正の根拠をユーザに提示すること、及び、修正の対象となる前記タプルを前記ルールに従って自動的に修正すること、の少なくとも一方である、
ことを特徴とするデータクレンジングシステム。
【請求項４】
請求項２又は３記載のデータクレンジングシステムであって、
前記タプル修正実行部によって修正されたデータを出力する修正済データ出力部を、
更に備えたことを特徴とするデータクレンジングシステム。
【請求項５】
請求項２乃至４のいずれか一つに記載のデータクレンジングシステムであって、
前記例外疑いラベル付与部は、前記ルール集合中のルールに違反する前記タプルに対して前記例外疑いラベルである第一のラベルを付与し、それ以外の前記タプルに対して第二のラベルを付与し、
前記例外発生原因スコア算出部は、前記原因条件の候補について、
その取りうる値パタンの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第一のラベルを持つ確率Ｐ１と、
その取りうる値パタンの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第二のラベルを持つ確率Ｐ２と、
から前記情報量スコアを算出する、
ことを特徴とするデータクレンジングシステム。
【請求項６】
請求項５記載のデータクレンジングシステムであって、
前記原因条件候補生成部は、前記データ中に表れる大きさsの属性集合Ｘを全通り列挙することにより、前記原因条件の候補Ｘ１，Ｘ２，…，ＸＬを生成し、
前記例外発生原因スコア算出部は、前記原因条件の候補について、
その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第一のラベルを持つ確率Ｐ１と、Ｌｏｇ（Ｐ１）とを乗じた値をｉ＝１，…，Ｍについて合計した値と、
その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第二のラベルを持つ確率Ｐ２と、Ｌｏｇ（Ｐ２）とを乗じた値をｉ＝１，…，Ｍについて合計した値と、
を算出する、
ことを特徴とするデータクレンジングシステム。
【請求項７】
コンピュータが備えるデータ・ルール集合記憶部が、複数のタプルからなるデータ及びルール集合を記憶し、
前記コンピュータが備える例外発生原因条件推定部が、前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定し、
前記コンピュータが備えるタプル修正部が、推定された前記原因条件によって修正の対象となる前記タプルを決定する、
ことを特徴とするデータクレンジング方法。
【請求項８】
請求項７記載のデータクレンジング方法であって、
前記例外発生原因条件推定部が、
前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与し、
前記属性の中から前記原因条件の候補を生成し、
前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出し、
前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出し、
前記タプル修正部が、
前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出し、
算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行する、
ことを特徴とするデータクレンジング方法。
【請求項９】
複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶手段、
前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定手段、及び、
推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正手段、
としてコンピュータを機能させるためのデータクレンジングプログラム。
【請求項１０】
請求項９記載のデータクレンジングプログラムであって、
前記例外発生原因条件推定手段は、
前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与する例外疑いラベル付与手段と、
前記属性の中から前記原因条件の候補を生成する原因条件候補生成手段と、
前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出する例外発生原因スコア算出手段と、
前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出する例外発生原因条件選出手段とを含み、
前記タプル修正手段は、
前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出する例外確率算出手段と、
算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行するタプル修正実行手段とを含む、
ことを特徴とするデータクレンジングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、関数従属性への違反を修正することのできるデータクレンジング（Data Cleansing）システム、データクレンジング方法及びデータクレンジング用プログラムに関する。また、本発明は、データ修正補助システム、データ修正補助方法及びデータ修正補助用プログラムと呼ぶこともできる。
【背景技術】
【０００２】
関連技術のデータクレンジングシステムの一例が、非特許文献１に記載されている。このデータクレンジングシステムは、データ・ルール集合記憶手段と、修正コスト算出手段と、タプル修正手段と、修正済データ出力手段とから構成されている。このような構成を有するデータクレンジングシステムは、次のように動作する。【０００３】
すなわち、
データ中のタプルを指定された順番に並び替える（省略可）。
データ中の各タプルについて、以下の処理を行う。
タプル中のｋ個の値を他の値に変更することで得た全ての修正タプル候補のうち、ルール集合Σ中の全てのルールに合致しているものの中から、元のタプルからの修正コストが最小のものを選ぶ。
この修正が予め定められた閾値を下回る場合には、この修正をbestFixとし、修正を採用する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Gao Cong, Wenfei Fan, Floris Geerts, Xibei Jia, Shuai Ma, Improving Data Quality: Consistency and Accuracy, the 33rd International Conference on Very Large Data Bases (VLDB), 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、関連技術では、前述の動作によりデータ修正を行う場合、修正コストが同一となる修正候補が複数ある際、より確からしいものを選ぶことができない、という問題があった。【０００６】
例えば、関数従属性ルールにより「東京都」と「東京」という異なる値が同一の値に統一されるべきということが分かっても、「東京都」を「東京」に統一するという修正を選ぶべきか、「東京」を「東京都」に統一するという修正を選ぶべきか、を決定することができなかった。【０００７】
既存の手法では、修正コストが同一である複数の修正タプル候補から１つの修正を選ぶ場合、リストの先頭にあるものを選択する方法や、ランダムに選択するなどの方法が採られてきた。【０００８】
すなわち、関連技術の問題点は次のとおりである。
第１の問題点は、修正コストが同一となる修正タプル候補が複数あるとき、その中で最も確からしいものを選ぶことができないということである。
第２の問題点は、そのような場合にリストの先頭やランダムといった選択方法を採ったとき、修正タプル選出の充分な理由が無いということである。【０００９】
そこで、本発明の目的は、修正コストが同一となった場合でも、確からしい修正タプル候補を選出できる、データクレンジングシステム等を提供することにある。
本発明の他の目的は、選出された修正タプル候補について、選出の根拠をユーザに提示できる、データクレンジングシステム等を提供することにある。
【課題を解決するための手段】
【００１０】
本発明のデータクレンジングシステムは、
複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶部と、
前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定部と、
推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正部と、
を備えたことを特徴とする。【００１１】
本発明のデータクレンジング方法は、
コンピュータが備えるデータ・ルール集合記憶部が、複数のタプルからなるデータ及びルール集合を記憶し、
前記コンピュータが備える例外発生原因条件推定部が、前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定し、
前記コンピュータが備えるタプル修正部が、推定された前記原因条件によって修正の対象となる前記タプルを決定する、
ことを特徴とする。【００１２】
本発明に係るデータクレンジングプログラムは、
複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶手段、
前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定手段、及び、
推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正手段、
としてコンピュータを機能させるためのものである。
【発明の効果】
【００１３】
本発明によれば、修正コストが同一となった場合でも、確からしい修正タプル候補を選出できる、
【図面の簡単な説明】
【００１４】
【図１】本発明に係るデータクレンジングシステムの一実施形態の構成を示すブロック図である。
【図２】本発明に係るデータクレンジングシステムの一実施形態の動作を示すフローチャートである。
【図３】実施形態の具体例における、入力データ及びルール集合を示す図表である。
【図４】実施形態の具体例における、入力データに対して特徴抽出を行った結果を示す図表である。
【図５】実施形態の具体例における、入力データに対してラベル追加を行った結果を示す図表である。
【図６】実施形態の具体例における、例外発生原因条件の候補を示す図表である。
【図７】実施形態の具体例における、例外発生原因条件の候補に対して情報量スコアを付与した結果を示す図表である。
【図８】実施形態の具体例における、入力データに対して例外確率を付与した結果を示す図表である。
【図９】実施形態の具体例における、入力データに対して自動実行が行われた結果を示す図表である。
【図１０】実施形態の具体例における、ユーザに対してデータ修正提案を行う画面を示す図表である。
【発明を実施するための形態】
【００１５】
以下、添付図面を参照しながら、本発明を実施するための形態（以下「実施形態」という。）について説明する。
【００１６】
図１は、本発明に係るデータクレンジングシステムの一実施形態の構成を示すブロック図である。図２は、本発明に係るデータクレンジングシステムの一実施形態の動作を示すフローチャートである。以下、これらの図面に基づき、本実施形態の概要を説明する。
【００１７】
本実施形態のデータクレンジングシステムは、複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶部１００と、前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定部１１０と、推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正部１２０とを備えたことを特徴とする。
【００１８】
例外発生原因条件推定部１１０は、前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与する例外疑いラベル付与部１１１と、前記属性の中から前記原因条件の候補を生成する原因条件候補生成部１１２と、前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出する例外発生原因スコア算出部１１３と、前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出する例外発生原因条件選出部１１４とを有してもよい。
【００１９】
タプル修正部１２０は、前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出する例外確率算出部１２１と、算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行するタプル修正実行部１２２とを有してもよい。
【００２０】
前記修正処理は、修正の対象となる前記タプル及びその修正の根拠をユーザに提示すること、及び、修正の対象となる前記タプルを前記ルールに従って自動的に修正すること、の少なくとも一方である、としてもよい。
【００２１】
本実施形態のデータクレンジングシステムは、タプル修正実行部１２２によって修正されたデータを出力する修正済データ出力部１３０を、更に備えてもよい。
【００２２】
例えば、例外疑いラベル付与部１１１は、前記ルール集合中のルールに違反する前記タプルに対して前記例外疑いラベルである第一のラベルを付与し、それ以外の前記タプルに対して第二のラベルを付与する。
【００２３】
例えば、例外発生原因スコア算出部１１３は、前記原因条件の候補について、
その取りうる値パタンの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第一のラベルを持つ確率Ｐ１と、
その取りうる値パタンの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第二のラベルを持つ確率Ｐ２と、
から前記情報量スコアを算出する。
【００２４】
例えば、原因条件候補生成部１１２は、前記データ中に表れる大きさｓの属性集合Ｘを全通り列挙することにより、前記原因条件の候補Ｘ１，Ｘ２，…，ＸＬを生成する。
【００２５】
例えば、例外発生原因スコア算出部１１３は、前記原因条件の候補について、
その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第一のラベルを持つ確率Ｐ１と、Ｌｏｇ（Ｐ１）とを乗じた値をｉ＝１，…，Ｍについて合計した値と、
その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第二のラベルを持つ確率Ｐ２と、Ｌｏｇ（Ｐ２）とを乗じた値をｉ＝１，…，Ｍについて合計した値と、
を算出する。
【００２６】
以上のように、本実施形態のデータクレンジングシステムは、データ・ルール集合記憶部１００と、例外発生原因条件推定部１１０と、タプル修正部１２０と、修正済データ出力部１３０とを備え、複数の例外に共通する原因条件を推定し、推定された原因条件によって最も確からしい修正タプル候補を決定するよう動作する。本実施形態のデータクレンジングシステムによれば、このような構成を採用することにより、修正コストのみでは決定不可能な状況でも、確からしい修正タプル候補を選出できるので、本発明の目的を達成できる。
【００２７】
本実施形態のデータクレンジングシステムの効果は、次のとおりである。第１の効果は、同数の修正値候補がある場合など、修正コストのみでは決定不可能な状況でも、確からしい修正タプル候補を選出できることである。その理由は、複数の例外に共通する原因条件を推定し、この条件を用いて、確からしい修正タプル候補選出に関連する情報を提供するためである。第２の効果は、選出された修正タプル候補について、選出の根拠をユーザに提示できることである。その理由は、複数の例外に共通する原因条件を推定し、この原因条件に基づいて修正タプル候補を選出するためである。
【００２８】
本実施形態のデータクレンジング方法は、本実施形態のデータクレンジングシステムの動作を方法の発明として捉えたものであり、次の工程を含む。コンピュータが備えるデータ・ルール集合記憶部１００が、複数のタプルからなるデータ、及び、ルール集合を記憶する工程（ステップ１）。前記コンピュータが備える例外発生原因条件推定部１１０が、前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する工程（ステップ２〜５）。前記コンピュータが備えるタプル修正部１２０が、推定された前記原因条件によって修正の対象となる前記タプルを決定する工程（ステップ６、７）。
【００２９】
本実施形態のデータクレンジング方法において、上記各工程は更に次の工程を含んでもよい。例外発生原因条件推定部１１０は、次の工程を実行する。前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与する工程（ステップ２）。前記属性の中から前記原因条件の候補を生成する工程（ステップ３）。前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出する工程（ステップ４）。前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出する工程（ステップ５）。前記タプル修正部は、次の工程を実行する。前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出する工程（ステップ６）。算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行する工程（ステップ７）。
【００３０】
本実施形態のデータクレンジングプログラム（以下「本プログラム」と略称する。）は、本実施形態のデータクレンジングシステムの各部（以下の各手段に相当する。）を、コンピュータに機能させるためのものである。すなわち、本プログラムは、複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶手段（１００）、前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定手段（１１０）、及び、推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正手段（１２０）、としてコンピュータを機能させるためのものである。
【００３１】
ここで、例外発生原因条件推定手段（１１０）は、前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与する例外疑いラベル付与手段（１１１）と、前記属性の中から前記原因条件の候補を生成する原因条件候補生成手段（１１２）と、前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出する例外発生原因スコア算出手段（１１３）と、前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出する例外発生原因条件選出手段（１１４）とを含んでもよい。タプル修正手段（１２０）は、前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出する例外確率算出手段（１２１）と、算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行するタプル修正実行手段（１２２）とを含んでもよい。
【００３２】
このコンピュータは、ＣＰＵ、メモリ、入出力インタフェースなどを有する一般的なものでよい。このとき、本プログラムはメモリに記憶され、ＣＰＵが本プログラムをメモリから読み出し、解釈し、実行する。また、本プログラムは、非一時的な記録媒体（non-transitory storage medium）、例えば光ディスク、半導体メモリなどに記録されてもよい。その場合、本プログラムは、記録媒体からコンピュータによって読み出され、実行される。
【００３３】
本実施形態のデータクレンジング方法及びデータクレンジングプログラムのこれ以外の構成は、本実施形態のデータクレンジングシステムの構成と同様である。本実施形態のデータクレンジング方法及びデータクレンジングプログラムによれば、本実施形態のデータクレンジングシステムと同様の作用及び効果を奏する。
【００３４】
次に、本実施形態について更に詳しく説明する。
【００３５】
図１を参照すると、本発明の一実施形態は、データ・ルール集合記憶部１００と、例外発生原因条件推定部１１０と、タプル修正部１２０と、修正済データ出力部１３０とを備えている。データ・ルール集合記憶部１００は、データテーブルＤと、ルール集合Σとの、入力を受け付ける。
【００３６】
例外発生原因条件推定部１１０は、例外疑いラベル付与部１１１と、原因条件候補生成部１１２と、例外発生原因スコア算出部１１３、例外発生原因条件選出部１１４とを含む。これらの部は、それぞれ概略つぎのように動作する。
【００３７】
例外疑いラベル付与部１１１は、ルール集合Σ中のルールに違反するタプルに対して「Ｔ」のラベル付与を行い、それ以外のタプルに対して「Ｆ」のラベル付与を行う。原因条件候補生成部１１２は、例外発生原因条件の候補を複数生成する。例外発生原因スコア算出部１１３は、各原因条件候補について、それらが例外疑いラベルの値に関して持つ情報量スコアを算出する。例外発生原因条件選出部１１４は、全原因条件候補の中から、例外発生原因スコアの最も高い原因条件候補を選出する。
【００３８】
タプル修正部１２０は、例外確率算出部１２１と、タプル修正実行部１２２とを含む。これらの部は、それぞれ概略次のように動作する。
【００３９】
例外確率算出部１２１は、例外発生原因条件の属性値を与えられた際に、条件付確率ｐ（タプルｔの例外確率｜例外発生原因属性）を算出する。タプル修正実行部１２２は、算出された例外確率が予め指定された閾値を上回っている場合に、ユーザに修正推薦タプルと根拠とを提示する、又は、ルールに従った修正を自動で行う。
【００４０】
修正済データ出力部１３０は、修正済データＤrepairを出力する。
【００４１】
次に、図１及び図２を参照して本実施形態の全体の動作について詳細に説明する。
【００４２】
まず、データ・ルール集合記憶部１００が、データテーブルＤとルール集合Σを記憶する（ステップ１）。
【００４３】
続いて、例外疑いラベル付与部１１１により、クレンジング対象テーブルに新たなカラム「例外疑い」を挿入し、ルール集合Σ中のルールに違反するタプルに対して「Ｔ」のラベルを付与し、それ以外のタプルに対して「Ｆ」のラベルを付与する（ステップ２）。そして、原因条件候補生成部１１２により、例外発生原因条件の候補を生成する（ステップ３）。そして、例外発生原因スコア算出部１１３により、各例外発生原因条件候補について、それらが例外疑いラベルの値に関して持つ情報量スコアを算出する（ステップ４）。そして、例外発生原因条件選出部１１４により、全原因条件候補の中から、例外発生原因スコアの最も高い原因条件候補を選出する（ステップ５）。
【００４４】
続いて、例外確率算出部１２１により、例外発生原因条件の属性値を与えられた際に、タプルｔが例外である条件付確率ｐ（タプルｔの例外確率｜例外発生原因属性）を算出する（ステップ６）。そして、タプル修正実行部１２２により、算出された例外確率が予め指定された閾値を上回っている場合に、ユーザに修正推薦タプルと根拠とを提示する、又は、ルールに従った修正を自動で行う（ステップ７）。
【００４５】
最後に、修正済データ出力部１３０により、修正済データＤrepairを出力する。
【００４６】
次に、図３乃至図１０の具体例を用いて、本実施形態の動作を説明する。
【００４７】
図３に示すように、入力データＤとルール集合Σとがあるとする（図２ステップ１）。例として挙げる入力データは、表記ゆれを含む名簿であり、５人の人物に関するデータが重複・表記ゆれを含んで１０行のデータを構成している。ルール集合は、φ１：社員ＩＤ→氏名、部署、勤務地、電話番号、φ２：部署→勤務地とする。
【００４８】
前処理として、複数テーブルの結合（join）や、特徴抽出を行うと、より効果的に原因条件推定を行うことができる。
【００４９】
複数テーブルの結合とは、外部キーなどによって参照された２つのテーブルがあった際に、テーブルの結合（join）を行うことによって、１つのテーブルとして扱うことができるようにする処理である。
【００５０】
特徴抽出とは、データをプログラムが扱いやすいように変換を加えておくことである。例えば、数値データを閾値分割してまとめあげておくこと（下記第一例）や、複合的な記号データを分割すること（下記第二例）や、他の特徴抽出関数を作成しておくこと（下記第三例）などの特徴抽出を行う。第一例は、年齢［３５，２７，５８，２８，４７］⇒［２０−３０代，２０−３０代，４０−５０代，２０−３０代，４０−５０代］とするものである。第二例は、製品番号＝“Ｎ−１２３−４５６”⇒製品番号１＝“Ｎ”，製品番号２＝“１２３”，製品番号＝“４５６”とするものである。第三例は、県［東京都，トウキョウ，とうきょう，カナガワ］⇒［漢字，カタカナ，ひらがな，カタカナ］とするものである。
【００５１】
特に、エラーの原因に関係すると考えられる特徴を抽出しておくとよい。抽出した特徴は、新たな属性として、分析対象のテーブルに加えておく。図４に、特徴抽出を行った結果の具体例を示す。
【００５２】
続いて、図２ステップ２に従って、ラベル付与を行う。ある関数従属性ルールφ：Ｘ→Ａに関して、対象データＤ中に属性集合Ｘにおいては同一の値パタンを持つが、属性Ａにおいては異なる値を持つようなタプル組ｔ１，ｔ２が存在するとき、それらのタプルはルールφに違反する。ルール集合Σ中のいずれかのルールに違反をしているタプルには「Ｔ」、いずれのルールにも違反していないタプルには「Ｆ」、というラベルを付与する。ラベルは、他の属性と同様に、ＶＩＯなどの属性名でテーブルに追加してもよいし、他の方法で記録しておいてもよい。図５に、ラベル追加を行った結果の具体例を示す。なお、「違反」は「矛盾」と呼んでもよい。
【００５３】
続いて、図２ステップ３に従って、例外発生原因条件の候補を生成する（図６）。単純な方法としては、全ての属性を候補とすることである。例えば、入力データＤの属性集合が社員番号、氏名、部署、郵便番号であったとき、それらの社員番号、氏名、部署、郵便番号が、例外発生原因条件の候補となる。また、［Ｒ］ｋ（データＤの全属性Ｒから任意のｋ個の属性を選択して得た属性集合とその値パタンの集合）を用いて、｛社員番号、氏名｝や、｛部署、郵便番号｝など、複数条件の組み合わせを利用することも考えられる。テーブル結合や特徴抽出を行った場合、それらによって新たに加わった属性からも例外発生原因条件の候補を生成するとよい。
【００５４】
続いて、図２ステップ４に従って、各原因条件候補について、それらが例外疑いラベルの値に関して持つ情報量スコアを算出する。例外疑いラベルの値に関して持つ情報量スコアとしては、Precision, Recall, 両者の調和平均であるF-measureなどを用いてもよいが、ここでは一例として情報利得スコアを用いる。
【００５５】
ある原因条件候補κ：Ｘ＝ｖ（ｖは値パタン［ｘ１，ｘ２，…，ｘｎ］）の情報利得スコアＩＧの計算方法は、以下の通りである。
ＩＧ（κ）＝Ｈ（ＶＩＯ）−Ｈ（ＶＩＯ｜κ）
ここで、Ｈ（ＶＩＯ）＝−Ｐ（ＶＩＯ＝“Ｔ”）×ＬｏｇＰ（ＶＩＯ＝“Ｔ”）−Ｐ（ＶＩＯ＝“Ｆ”）×ＬｏｇＰ（ＶＩＯ＝“Ｆ”）であるが、データ全体に渡って不変であるので無視してよい。
Ｈ（ＶＩＯ｜Ｘ）＝−Σｖ∈π（Ｘ）Ｐ（Ｘ＝ｖ）×｛Ｐ（ＶＩＯ＝“Ｔ”｜Ｘ＝ｖ）×ＬｏｇＰ（ＶＩＯ＝“Ｔ”｜Ｘ＝ｖ）＋Ｐ（ＶＩＯ＝“Ｆ”｜Ｘ＝ｖ）×ＬｏｇＰ（ＶＩＯ＝“Ｆ”｜Ｘ＝ｖ）｝である。
ただし、π（Ｘ）は属性集合Ｘに関して、データＤ中に出現する全ての値パタンの集合である。
【００５６】
続いて、図２ステップ５に従って、例外発生原因スコアの最も高い原因条件の属性Ｘ＾を選出する。図７の例では、Ｘ＾＝「扱いオペレータ」が選出される。
【００５７】
続いて、図２ステップ６に従って、例外発生原因条件の属性値を与えられた際に、タプルｔが例外である条件付確率ｐ（タプルｔの例外確率｜例外発生原因属性）を算出する。
【００５８】
この確率の算出方法は、例えば以下のように行う。
Ｐ（ＶＩＯ＝“Ｔ”｜Ｘ＝ｔ［Ｘ］）
ただし、ｔ［Ｘ］はタプルｔの属性集合Ｘに対する値パタンである。この値は、上記説明の情報利得スコアを用いる場合には、図２ステップ４において既に算出されているものであるので、計算結果をハードディスク等に記録しておいて利用すればよい。
【００５９】
最後に、図２ステップ７に従って、算出された例外確率が予め指定された閾値を上回っている場合に、ルールに従った修正を行う。ここで、図８のタプルｔ３の情報利得スコアは閾値０．２を上回るので、ルールに従うように修正を行う。
【００６０】
修正の例としては、左辺の値をタプルｔ２と異なる値にするか、右辺の値をタプルｔ３と同じ値にするか、という２つの選択肢がある。ここでは、図１０のように、タプルｔ３を修正対象タプルとして推薦し、その根拠として条件κをユーザに提示する。右辺の値を既存の値に直すという修正に関する制約がある場合は、右辺の値をタプルｔ３と同じ値にするという修正を自動で実行してもよい。図２ステップ７は、例外タプルがある限り、繰り返す。
【００６１】
全ての例外タプルに関して修正が終わった後、修正済データＤrepairを出力する。
【００６２】
次に、本実施形態の効果について説明する。
【００６３】
本実施形態では、複数の例外に共通する原因条件を推定し、この条件を用いて、確からしい修正タプル候補選出に関連する情報を提供できるように構成されているため、同数の修正値候補がある場合など、修正コストのみでは決定不可能な状況でも、確からしい修正タプル候補を選出できる。
【００６４】
また、本実施形態では、更に、複数の例外に共通する原因条件を推定し、この原因条件に基づいて修正タプル候補を選出するというように構成されているため、選出された修正タプル候補について、選出の根拠をユーザに提示できる。
【００６５】
以上、上記実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細については、当業者が理解し得るさまざまな変更を加えることができる。また、本発明には、上記実施形態の構成の一部を相互に適宜組み合わせたものも含まれる。
【００６６】
上記の実施形態の一部又は全部は以下の付記のようにも記載され得るが、本発明は以下の構成に限定されるものではない。
【００６７】
［付記１］複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶部と、
前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定部と、
推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正部と、
を備えたことを特徴とするデータクレンジングシステム。
【００６８】
［付記２］付記１記載のデータクレンジングシステムであって、
前記例外発生原因条件推定部は、
前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与する例外疑いラベル付与部と、
前記属性の中から前記原因条件の候補を生成する原因条件候補生成部と、
前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出する例外発生原因スコア算出部と、
前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出する例外発生原因条件選出部とを有し、
前記タプル修正部は、
前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出する例外確率算出部と、
算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行するタプル修正実行部とを有する、
ことを特徴とするデータクレンジングシステム。
【００６９】
［付記３］付記２記載のデータクレンジングシステムであって、
前記修正処理は、修正の対象となる前記タプル及びその修正の根拠をユーザに提示すること、及び、修正の対象となる前記タプルを前記ルールに従って自動的に修正すること、の少なくとも一方である、
ことを特徴とするデータクレンジングシステム。
【００７０】
［付記４］付記２又は３記載のデータクレンジングシステムであって、
前記タプル修正実行部によって修正されたデータを出力する修正済データ出力部を、
更に備えたことを特徴とするデータクレンジングシステム。
【００７１】
［付記５］付記２乃至４のいずれか一つに記載のデータクレンジングシステムであって、
前記例外疑いラベル付与部は、前記ルール集合中のルールに違反する前記タプルに対して前記例外疑いラベルである第一のラベルを付与し、それ以外の前記タプルに対して第二のラベルを付与し、
前記例外発生原因スコア算出部は、前記原因条件の候補について、
その取りうる値パタンの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第一のラベルを持つ確率Ｐ１と、
その取りうる値パタンの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第二のラベルを持つ確率Ｐ２と、
から前記情報量スコアを算出する、
ことを特徴とするデータクレンジングシステム。
【００７２】
［付記６］付記５記載のデータクレンジングシステムであって、
前記原因条件候補生成部は、前記データ中に表れる大きさｓの属性集合Ｘを全通り列挙することにより、前記原因条件の候補Ｘ１，Ｘ２，…，ＸＬを生成し、
前記例外発生原因スコア算出部は、前記原因条件の候補について、
その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第一のラベルを持つ確率Ｐ１と、Ｌｏｇ（Ｐ１）とを乗じた値をｉ＝１，…，Ｍについて合計した値と、
その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉの前記データ中での出現確率と、値パタンｖｉを持つ前記タプルが前記第二のラベルを持つ確率Ｐ２と、Ｌｏｇ（Ｐ２）とを乗じた値をｉ＝１，…，Ｍについて合計した値と、
を算出する、
ことを特徴とするデータクレンジングシステム。
【００７３】
［付記７］コンピュータが備えるデータ・ルール集合記憶部が、複数のタプルからなるデータ及びルール集合を記憶し、
前記コンピュータが備える例外発生原因条件推定部が、前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定し、
前記コンピュータが備えるタプル修正部が、推定された前記原因条件によって修正の対象となる前記タプルを決定する、
ことを特徴とするデータクレンジング方法。
【００７４】
［付記８］付記７記載のデータクレンジング方法であって、
前記例外発生原因条件推定部が、
前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与し、
前記属性の中から前記原因条件の候補を生成し、
前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出し、
前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出し、
前記タプル修正部が、
前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出し、
算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行する、
ことを特徴とするデータクレンジング方法。
【００７５】
［付記９］複数のタプルからなるデータ及びルール集合を記憶するデータ・ルール集合記憶手段、
前記タプルに含まれる複数の属性の中から、複数の例外に共通する原因条件を推定する例外発生原因条件推定手段、及び、
推定された前記原因条件によって修正の対象となる前記タプルを決定するタプル修正手段、
としてコンピュータを機能させるためのデータクレンジングプログラム。
【００７６】
［付記１０］付記９記載のデータクレンジングプログラムであって、
前記例外発生原因条件推定手段は、
前記複数のタプルのうち、前記ルール集合中のルールに違反するタプルに対して例外疑いラベルを付与する例外疑いラベル付与手段と、
前記属性の中から前記原因条件の候補を生成する原因条件候補生成手段と、
前記原因条件の候補について前記例外疑いラベルの値に関して持つ情報量スコアを算出する例外発生原因スコア算出手段と、
前記原因条件の候補の中から前記情報量スコアの最も高い原因条件を選出する例外発生原因条件選出手段とを含み、
前記タプル修正手段は、
前記情報量スコアの最も高い原因条件に対応する属性を前記複数のタプルに対して与えた際に、当該タプルが例外である条件付確率を算出する例外確率算出手段と、
算出された前記条件付確率が予め指定された閾値を上回っている前記タプルに対して、修正処理を実行するタプル修正実行手段とを含む、
ことを特徴とするデータクレンジングプログラム。
【００７７】
［付記１１］データ・ルール集合記憶手段と、例外発生原因条件特定手段と、タプル修正手段とを備え、
複数の例外に共通する原因条件を推定し、推定された原因条件によって最も確からしい修正タプル候補を決定する、
ことを特徴とするデータクレンジングシステム。
【００７８】
［付記１２］付記１１記載のデータクレンジングシステムであって、
前記データ・ルール集合記憶手段は、データテーブルＤとルール集合Σを記憶し、
前記例外発生原因条件特定手段は、
ルール集合Σ中のルールに違反するタプルに対して第一のラベルを付与し、それ以外のタプルに対して第二のラベルを付与する例外疑いラベル付与手段と、
データＤ中の属性集合Ｘから例外発生原因条件の候補を生成する原因条件候補生成手段と、
各例外発生原因条件の候補について、その取りうる値パタンのＤ中での出現確率と、値パタンｖｉを持つタプルが第一のラベルを持つ確率Ｐ１と、その取りうる値パタンのＤ中での出現確率と、値パタンｖｉを持つタプルが第二のラベルを持つ確率Ｐ２と、から例外発生原因スコアを算出する例外発生原因スコア算出手段と、
を含み、
前記タプル修正手段は、
例外発生原因スコアから、あるタプルｔについて、例外発生原因属性に対する値を与えられた際に、例外発生原因属性が与えられた時のタプルｔの例外確率を条件付確率として算出し、あるタプルｔと条件付確率ｐを対にして記憶装置へ書き込む例外確率算出手段を含む、
ことを特徴とするデータクレンジングシステム。
【００７９】
［付記１３］（例外確率を算出するところまで）
付記１２記載のデータクレンジングシステムであって、
前記原因条件候補生成手段は、データＤ中に表れる大きさsの属性集合Ｘを全通り列挙することで、例外発生原因条件の候補Ｘ１，Ｘ２，… ，ＸＬを生成し、
前記例外発生原因スコア算出手段は、
各例外発生原因条件の候補について、その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉのＤ中での出現確率と、値パタンｖｉを持つタプルが第一のラベルを持つ確率Ｐ１と、Ｌｏｇ（Ｐ１）とを乗じた値をｉ＝１…Ｍについて合計した値と、
その取りうる値パタンｖ１，ｖ２，…，ｖＭが与えられた時、値パタンｖｉのＤ中での出現確率と、値パタンｖｉを持つタプルが第二のラベルを持つ確率Ｐ２と、Ｌｏｇ（Ｐ２）とを乗じた値をｉ＝１…Ｍについて合計した値を算出する、
ことを特徴とするデータクレンジングシステム。
【００８０】
［付記１４］（例外確率を算出する＋提示and/or修正）
付記１２記載のデータクレンジングシステムであって、
前記タプル修正手段は、算出された例外確率が予め指定された閾値を上回っている場合に、ユーザに修正推薦タプルと根拠を提示する、又は、ルールに従った修正を自動で行う、又は提示と修正の双方を行うタプル修正実行手段を更に含む、
ことを特徴とするデータクレンジングシステム。
【００８１】
［付記１５］付記１１乃至１４のいずれか一つに記載のデータクレンジングシステムであって、
修正済データＤrepairを出力する修正済データ出力手段を、
更に備えたことを特徴とするデータクレンジングシステム。
【００８２】
この出願は２０１２年１月１０日に出願された日本出願特願２０１２−００１８５９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００８３】
本発明によれば、関数従属性を用いたデータクレンジング（表記ゆれ統一や、名寄せも含む。）といった用途に適用できる。
【符号の説明】
【００８４】
１００  データ・ルール集合記憶部
１１０  例外発生原因条件推定部
１１１  例外疑いラベル付与部
１１２  原因条件候補生成部
１１３  例外発生原因スコア算出部
１１４  例外発生原因条件選出部
１２０  タプル修正部
１２１  例外確率算出部
１２２  タプル修正実行部
１３０  修正済データ出力部
【図１】
2013105440.tif 000003
【図２】
2013105440.tif 000004
【図３】
2013105440.tif 000005
【図４】
2013105440.tif 000006
【図５】
2013105440.tif 000007
【図６】
2013105440.tif 000008
【図７】
2013105440.tif 000009
【図８】
2013105440.tif 000010
【図９】
2013105440.tif 000011
【図１０】
2013105440.tif 000012
【国際調査報告】
2013105440.tif 000013
2013105440.tif 000014
2013105440.tif 000015
2013105440.tif 000016