DEIM Forum 2016 D3-4
統計的信頼区間を用いた特徴的な部分データの効率的探索
水野 陽平
†鬼塚 真
††大阪大学情報科学研究科 〒565-0871 大阪府吹田市山田丘 1-5
E-mail: †{mizuno.yohei, onizuka}@ist.osaka-u.ac.jp
あらまし ビジネスデータの解析においては，データ全体の特徴を分析する OLAP(online analytical processing) 型の 集約・グループ化の分析処理が頻繁に用いられているが，販売データの地域性や時期性の影響を見て販売戦略を決 める場合などでは，ユーザが指定した分析クエリに対して，有用性が高い分析結果を生み出す部分データを探索す ることが重要である（これを特徴部分データ探索問題と呼ぶ）．この問題を処理するためには，総当りで部分データ を探索して分析クエリを実行して分析結果の有用性を判定する必要があるため，膨大な時間を要する．そこで本稿 では，特徴部分データ探索処理の高速化に取り組む．具体的には，統計的信頼区間を用いることで，有用性が高い 分析結果の候補になり得ない部分データの探索の足きりを行い高速化を図る．実際の販売データに対して提案技術 を適用した結果，95％の信頼水準において最大 3 倍の高速化を確認した． キーワード マイニング，可視化
1. ま え が き
こ れ ま で 企 業 が 扱 っ て き た デ ー タ 以 上 に 大 規 模 か つ 多 様 性 に 富 ん だ デ ー タ で あ る ビ ッ グ デ ー タ を 資 源 と し て 考 え ， 有 益 な 情 報 を 抽 出 す る 手 法 を 適 用 す る こ と が 重 要 な 課 題 と な っ て い る ． 特 に ， ビ ジ ネ ス デ ー タ の 解 析 に お い て は OLAP 型 の 分 析 処 理 []が 頻 繁 に 用 い ら れ て い る ． OLAP 型 の 分 析 を 用 い る こ と で ， 様 々 な 次 元 か ら デ ー タ ベ ー ス を 集 約 ・ グ ル ー プ 化 し て デ ー タ の 全 体 の 傾 向 を 把 握 し た り ， 例 外 的 な デ ー タ を 発 見 す る こ と が で き る ． 特 に ， デ ー タ 全 体 の 傾 向 と は 異 な る 傾 向 を 示 す 部 分 デ ー タ を 特 定 す る こ と で ， 特 徴 的 な 部 分 デ ー タ を 発 見 で き る 場 合 が あ る ． 例 え ば ， 販 売 デ ー タ の 地 域 性 や 時 期 性 の 影 響 を 見 て 販 売 戦 略 を 決 め た い 場 合 な ど で は ， 分 析 処 理 に 対 し て 有 用 性 が 高 い 分 析 結 果 を 生 み 出 す 部 分 デ ー タ を 探 索 す る こ と が 重 要 で あ る ． 本 稿 で は こ れ を 特 徴 部 分 デ ー タ 探 索 問 題 と 呼 ぶ ． 具 体 例 と し て ， 企 業 の 販 売 デ ー タ の 分 析 を 用 い て ， 特 徴 部 分 デ ー タ 探 索 問 題 の 重 要 性 を 説 明 す る ． 企 業 の 販 売 デ ー タ の 分 析 販 売 デ ー タ を 分 析 す る 場 合 ， 商 品 全 体 の 売 り 上 げ の 傾 向 か ら の 乖 離 が 大 き い 商 品 を 見 つ け る こ と が 重 要 で あ る ． な ぜ な ら ば ， 例 え ば 商 品 全 体 の 月 毎 の 売 上 げ 傾 向 と 異 な る 商 品 の 場 合 ， そ の 商 品 は 時 期 の 影 響 が 大 き い と 判 断 で き る た め で あ る ． こ の 判 断 に 基 づ い て ， 該 当 の 商 品 の 調 達 量 を 月 毎 に 調 整 し ， ま た 売 り 上 げ が 低 い 月 に 新 商 品 の 投 入 や PR を 行 う な ど の 販 売 方 針 を 戦 略 的 に 決 定 す る こ と が で き る ． 例 え ば ， 図1.1は 全 商 品 ， 男 性 が 購 入 し た 商 品 ， 衣 服 に 関 す る 商 品 の 月 毎 の 売 り 上 げ の 遷 移 の 可 視 化 結 果 で あ る （ 但 し ， 1 年 の 売 り 上 げ の 総 和 が 1 に な る よ う 正 規 化 し て い る ）． 男 性 が 購 入 し た 商 品 の 月 間 総 売 り 上 げ の 遷 移 は 全 商 品 の 月 間 総 売 り 上 げ の 遷 移 と 乖 離 が 小 さ い た め ， 特 徴 的 な 情 報 で 図 1.1：全 商 品 ，男 性 が 購 入 し た 商 品 ，衣 服 の 正 規 化 し た 月 毎 の 売 り 上 げ は な い が ， 衣 服 に 関 す る 商 品 の 月 間 総 売 り 上 げ の 遷 移 は 全 商 品 の 月 間 総 売 り 上 げ の 遷 移 と 乖 離 が 大 き い た め ， 全 商 品 と 比 較 し て 衣 服 の 売 り 上 げ は 販 売 時 期 の 影 響 を 大 き く 受 け て い る と 判 断 で き る ． そ の た め ， 衣 服 の 2014年 3月 の 売 上 が 高 い 要 因 を 分 析 し ，そ の 要 因 を 他 の 商 品 販 売 に 水 平 展 開 す る こ と に よ っ て ， 他 の 商 品 の 売 り 上 げ も 伸 ば す こ と が で き る 可 能 性 が あ る ． 上 記 の 分 析 を 行 う た め に は ， 任 意 の 条 件 を 満 た す 部 分 デ ー タ を 選 択 し ， 部 分 デ ー タ 毎 に 分 析 処 理 を 行 い ， 部 分 デ ー タ の 分 析 結 果 と 全 デ ー タ の 分 析 結 果 の 乖 離 が ど の 程 度 か を 判 断 す る 必 要 が あ る ． 分 析 す る 部 分 デ ー タ の 数 は ， 部 分 デ ー タ の 条 件 に 用 い る 属 性 の 取 り 得 る 値 の 件 数 と な り 膨 大 で あ る ． そ の た め ， 条 件 を 満 た す 部 分 デ ー タ を 手 動 で 総 当 り す る に は 多 く の 時 間 を 要 す る ． 本 稿 で は 上 記 の 問 題 に 対 し て ， 特 徴 的 な 部 分 デ ー タ を 自 動 で 高 速 に 探 索 す る 手 法 を 提 案 す る ． 自 動 化 す る 技 術 ： 有 用 性 が 高 い 分 析 結 果 を 生 み 出 す 部 分 デ ー タ と は ， 全 体 デ ー タ の 分 析 結 果 と の 乖 離 の 程 度 が 大 き い と 仮 定 す る ． 利 用 者 は 集 約 ・ グ ル ー プ 化 に よ る 分 析 ク エ リ を 事 前 に 与 え ， 更 に 分 析 処 理 を 全 体 デ ー 0 0.05 0.1 0.15 0.2 0.25 2014 年 1 月 2014 年 2 月 2014 年 3 月 2014 年 4 月 2014 年 5 月 2014 年 6 月 2014 年 7 月 2014 年 8 月 2014 年 9 月 2014 年 10 月 2014 年 11 月 2014 年 12 月 正規化し た売り 上げ 正規化した月毎の売り上げ 全商品 男性が購入した商品 衣服タ お よ び 部 分 デ ー タ に 実 行 し て 得 た 分 析 結 果 同 士 の 乖 離 の 程 度 を 数 値 化 す る 関 数 を 事 前 に 与 え る ． 解 く べ き 技 術 課 題 は ， 分 析 処 理 を 全 体 デ ー タ に 実 行 し て 得 た 分 析 結 果 に 対 し て ， 特 徴 的 な 部 分 デ ー タ の 上 位𝑘件 を 自 動 で 求 め る こ と で あ る ． 高 速 化 す る 技 術 ： 本 稿 で は ， 特 徴 部 分 デ ー タ 探 索 問 題 に 対 し て ，統 計 的 信 頼 区 間 推 定 の 技 術 を 用 い る こ と で ， 上 位𝑘件 の 部 分 デ ー タ の 探 索 範 囲 を 削 減 す る ア プ ロ ー チ で 高 速 化 に 取 り 組 む ． 具 体 的 に は ， 分 析 対 象 の デ ー タ の 処 理 の 途 中 に お い て ， 統 計 的 信 頼 区 間 推 定 の 技 術 を 適 用 す る こ と で 分 析 結 果 の 上 限 値 と 下 限 値 を 推 定 し ， 上 位𝑘件 の 候 補 に な り 得 な い 部 分 デ ー タ の 探 索 を 足 き り す る ． 更 に ， 足 き り の 可 能 性 を 高 め る た め ， 分 析 対 象 の 値 に 関 す る 分 布 に 基 づ い て 外 れ 値 の デ ー タ 集 合 を 特 定 し ， 外 れ 値 の デ ー タ 集 合 に 対 し て 事 前 に 部 分 デ ー タ の 乖 離 度 を 計 算 し て か ら ， 外 れ 値 以 外 の デ ー タ 集 合 を 対 象 に 統 計 的 信 頼 区 間 推 定 の 技 術 を 適 用 し て 特 徴 部 分 デ ー タ の 探 索 を 行 う ． 本 稿 で は ， 提 案 手 法 の プ ロ ト タ イ プ を 実 装 し 実 デ ー タ を 用 い た 評 価 実 験 を 行 っ た ． 評 価 実 験 に よ り ， 95％ の 信 頼 水 準 に お い て 上 位 1 件 の 特 徴 部 分 デ ー タ を 探 索 す る 場 合 ， 最 大 で 3 倍 の 高 速 化 が 可 能 で あ る こ と を 確 認 し た ． 本 稿 の 構 成 は ，以 下 の 通 り で あ る ．2章 に て 前 提 知 識 に つ い て 説 明 し ，3章 に お い て 提 案 手 法 の 詳 細 を 示 し ， 4章 に て 提 案 手 法 の 評 価 と 分 析 に つ い て 説 明 す る ． 5章 に て 関 連 研 究 に つ い て 述 べ ， 6 章 に て 本 稿 を ま と め ， 今 後 の 課 題 に つ い て 論 ず る ．
2. 事 前 知 識
本 章 で は 提 案 手 法 に 用 い た 信 頼 区 間 と 信 頼 区 間 の 推 定 に 用 い て い る 確 率 不 等 式 に つ い て 説 明 す る ．2.1節 で は Hoeffding の 確 率 不 等 式 に つ い て ，2.2節 で は Hoeffding の 確 率 不 等 式 を 用 い た 平 均 値 の 区 間 推 定 に つ い て 説 明 す る ． 2.1.Hoeffding の 確 率 不 等 式 確 率 不 等 式 は ， 母 集 団 の 確 率 変 数 に 対 し て ， 具 体 的 な 確 率 分 布 を 想 定 せ ず ， 期 待 値 や 分 散 な ど の 限 定 的 な 情 報 だ け に 基 づ い て ， そ れ ら の 確 率 変 数 の 和 あ る い は 平 均 に 関 す る 上 限 確 率 の 上 界 を 評 価 す る も の で あ る ． Hoeffding の 確 率 不 等 式 は ，確 立 変 数 の 期 待 値 や 有 限 の 定 義 域 が 判 明 し て い る と き に ， 確 率 変 数 の 上 限 確 率 の 上 界 を 与 え る 有 用 な 確 率 不 等 式 と し て 知 ら れ て い る ． 分 布 系 が 未 知 の 場 合 に ， 非 復 元 抽 出 し た 標 本 の 平 均 値 が 母 集 団 の 平 均 値 を 超 え る 確 率 は 以 下 の 式 で 表 せ る ． 𝑃𝑟(𝑡) = 𝑃𝑟[𝑥̅ − 𝜇 ≥ 𝑡] (2.1) 但 し ，𝑥̅ =1𝑛∑𝑛𝑖=1𝑥𝑖，𝜇 =𝑁1∑𝑁𝑖=1𝑋𝑖 で あ り ，n は サ ン プ リ ン グ サ イ ズ ，N は 母 集 団 の デ ー タ 数 で あ る ．こ の 確 率 𝑃𝑟(𝑡)に 対 し て ， t > 0 に お い て 以 下 の 式 で 上 界 を 与 え る こ と が で き る ． 𝑃𝑟(𝑡) ≤ 𝑒𝑥𝑝[−2𝑛𝑡2 (1 − 𝑓 𝑛)(𝑏 − 𝑎)2 ⁄ ] (2.2) 但 し ，𝑓𝑛= (𝑛 − 1) 𝑁⁄ ， 𝑎 = min1≤𝑖≤𝑁𝑋𝑖，𝑏 = max1≤𝑖≤𝑁𝑋𝑖 で あ る ． 2.1.Hoeffding の 確 率 不 等 式 を 用 い た 区 間 推 定 信 頼 区 間 は ， 母 数 が ど の よ う な 数 値 の 範 囲 に あ る か を 確 率 的 に 示 す 方 法 で あ る ． 母 数 と は ， 確 率 変 数 の 分 布 を 特 徴 付 け る 数 で あ る ．式(2.2)よ り 平 均 値 𝜇の 信 頼 区 間 の 式 を 導 出 す る ． 区 間 を 推 定 す る の で ，𝑥̅の 値 が 𝜇の 値 よ り 大 き く な る 場 合 だ け で な く ， 小 さ く な る 場 合 も 仮 定 す る 必 要 が あ り ， 考 え る 確 率 は 式(2.1)の 𝑥̅ − 𝜇に 絶 対 値 を 付 け た 以 下 の 式 に な る ． 𝑃𝑟′(𝑡) = 𝑃𝑟′[|𝑥̅ − 𝜇| ≥ 𝑡] (2.3) 式(2.3)は ， 式 (2.1)の 𝑥̅ − 𝜇に 絶 対 値 を 付 け た 式 な の で ， 確 率𝑃𝑟′(𝑡)は ，式 (2.2)の 確 率 𝑃𝑟(𝑡)の 2 倍 と な り ，t > 0 に お い て 以 下 の 式 で 上 界𝛼を 与 え る こ と が で き る ． 𝑃𝑟′(𝑡) ≤ 2 ∙ 𝑒𝑥𝑝[−2𝑛𝑡2 (1 − 𝑓 𝑛)(𝑏 − 𝑎)2 ⁄ ] = 𝛼 (2.4) 式(2.3), (2.4)よ り，母 集 団 の 平 均 値 𝜇の100 ∙ (1 − 𝛼)%信 頼 区 間（𝛼は 信 頼 区 間 の 有 意 水 準 ）の 式 (2.5)を 導 出 す る こ と が で き る ． 𝑥̅ − 𝑡 < 𝜇 < 𝑥̅ + 𝑡 (2.5) 式(2.4)を 𝑡に つ い て 整 理 す る と ， 𝑡の 値 は 以 下 の 式 で 計 算 す る こ と が で き る ． 𝑡 = √(1 − 𝑓𝑛)(𝑏 − 𝑎)2(log 2 − log 𝛼) 2𝑛⁄ (2.6) 導 出 し た 信 頼 区 間 の 式 の 適 用 例 を 示 す ． デ ー タ 数50 の 母 集 団（0 ≤ 𝑥𝑖≤ 1）か ら 非 復 元 抽 出 で 10(= 𝑛)の 標 本 を サ ン プ リ ン グ す る ．（ 標 本：{0.5, 0.3, 0.4, 0.6, 0.9, 0.5, 0.1, 0.2, 0.4, 0.4}）．標 本 平 均 は ，𝑥̅ = 0.43で あ る ．母 集 団 の 最 小 値 は ， 𝑎 = 0，最 大 値 は 𝑏 = 1と し た 場 合 ，式 (2.6)に 各 値 を 代 入 す る と ，母 集 団 の 平 均 値𝜇の 95%(𝛼 = 0.05)信 頼 区 間 は 以 下 の よ う に 計 算 で き る ． 𝑡 = √(1 −10 − 1 50 ) (1 − 0)2(log 2 − log 0.05) (2 × 10)⁄ 𝑡 = 0.041 ∴ 0.389 < 𝜇 < 0.4713. 提 案 手 法
本 章 で は 提 案 手 法 に つ い て 説 明 す る ．3.1節 で 特 徴 部 分 デ ー タ 特 定 問 題 の 概 要 ，3.2節 で 問 題 を 解 く 工 程 の 説 明 ，3.3節 で そ の 工 程 の 高 速 化 の 際 に ，部 分 デ ー タ の 足 き り に Hoeffding の 確 率 不 等 式 を 用 い た 区 間 推 定 の 技 術 を 適 用 す る 手 法 に つ い て 説 明 す る ． 3.1.問 題 定 義 利 用 者 は 集 約 ・ グ ル ー プ 化 に よ る 分 析 処 理 を 事 前 に 与 え ， 更 に 分 析 処 理 を 全 体 デ ー タ お よ び 部 分 デ ー タ に 実 行 し て 得 た 分 析 結 果 同 士 の 乖 離 度 を 数 値 化 す る 関 数を 事 前 に 与 え る ． 特 徴 部 分 デ ー タ 探 索 問 題 は ， 分 析 処 理 を 全 体 デ ー タ に 実 行 し て 得 た 分 析 結 果 に 対 し て ， 有 用 性 が 高 い 分 析 結 果 を 生 み 出 す 部 分 デ ー タ の 上 位𝑘件 を 求 め る 問 題 で あ る ．全 体 デ ー タ を𝐷，集 約・グ ル ー プ 化 処 理 を𝑉， 部 分 デ ー タ を 選 択 す る ク エ リ を 𝑆と す る ． 𝑉, 𝑆は 以 下 の 形 式 で 定 義 さ れ る ． S(𝐷, 𝑎, 𝑋) ≡ 𝜎(𝑎=𝑋)(𝐷) (3.1) V(𝐷, 𝑏, 𝑓, 𝑚) ≡ 𝑊𝑏,𝑓(𝑚)𝐷 (3.2) 但 し ，𝑎, 𝑏, 𝑚は 𝐷の 属 性 ，𝑋は 属 性 𝑎の 値 ，𝑓は 属 性 𝑚に 対 す る 集 約 関 数 で あ る ．𝜎は リ レ ー シ ョ ナ ル 代 数 に お け る 選 択 演 算 ，𝑊は 𝑏で グ ル ー プ 化 し 各 グ ル ー プ ご と に 集 約 関 数𝑓を 𝑚に 適 用 す る 処 理 で あ る ．例 え ば ，図 1.1の 衣 服 に 関 す る 商 品 の 月 毎 の 売 り 上 げ を 計 算 す る 処 理 は ， 𝑊 受 注 年 月,𝑆𝑈𝑀(販 売 金 額 ) 𝜎(カ テ ゴ リ =衣 服 )(𝐷) (3.3) と 表 現 さ れ る ． 以 後 ， 集 約 ・ グ ル ー プ 化 処 理 は 事 前 に 決 め ら れ て い る た め 引 数 を 省 略 す る ．Vが 集 約・グ ル ー プ 化 処 理 で あ る た め ，そ の 結 果 は シ ー ケ ン ス 型 で あ り ， 以 下 の 形 式 で 表 現 す る ． 𝑉(𝐷) = [(𝐵1, 𝑌1), ⋯ , (𝐵ℎ, 𝑌ℎ)] (3,4) 但 し ，{𝐵1, ⋯ , 𝐵ℎ} = 𝜋𝑚(𝐷)，𝑌𝑖(𝐷) = 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝐷))) (1 ≤ 𝑖 ≤ ℎ)で あ る ． 𝐵𝑖に 属 す る デ ー タ を ，𝑌𝑖の 入 力 で あ る 𝜋𝑚(𝜎𝑏=𝐵𝑖(𝐷))に 属 す るデ ー タ と 定 義 す る ．ま た ，𝐷 = 𝐻 ∪ 𝑇と す る と 𝑌𝑖(𝐷) = 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝐻 ∪ 𝑇)))で あ る ． σと πに 対 し て∪ は 分 配 則 が 適 用 可 能 で あ る た め ， 𝑌𝑖(𝐷) = 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝐻)) ∪ 𝜋𝑚(𝜎𝑏=𝐵𝑖(𝑇)))で あ る ． 𝑓が SUM や COUNT の 場 合 は ，+に よ っ て 𝑓を 分 解 可 能 で あ り ， 𝑌𝑖(𝐷) = 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝐻))) + 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝑇)))と な る ． 提 案 手 法 で は ，集 約 関 数 と し て SUM や COUNT を 仮 定 す る ． 次 に ， 全 体 デ ー タ と 部 分 デ ー タ に 同 じ 集 約 ・ グ ル ー プ 化 処 理 を し た 結 果 同 士 の 乖 離 度 を 数 値 化 す る 関 数 を 𝑈と し た と き に ，式 (3.5)に よ り 上 位 𝑘件 の 部 分 デ ー タ を 取 得 す る ．式(3.5)は ，乖 離 度 を 数 値 化 し た 値 の 上 位 𝑘件 を 取 得 す る 処 理 で あ る ． 𝑎𝑟𝑔top-k 𝑆 𝑈 (𝑉(𝐷), 𝑉(𝑆(𝐷, 𝑎, 𝑋))) (3.5) 但 し ，𝑎𝑟𝑔top-k 𝑆 𝑓(𝑥)は 𝑥を 変 化 さ せ た 際 に 𝑓(𝑥) が 最 大 の 値 を 返 却 す る 上 位𝑘個 の 𝑥を 返 却 す る 関 数 で あ り ， 𝑈 は2つ の シ ー ケ ン ス を 入 力 と し て ，シ ー ケ ン ス を 構 成 す る 各 要 素 の 乖 離 の 総 和 を 計 算 す る 関 数 で あ る ． 乖 離 度 を 数 値 化 す る 具 体 的 な 関 数 と し て ， ユ ー ク リ ッ ド 距 離 を 用 い る ． 3.2.問 題 を 解 く 行 程 の 概 要 特 徴 部 分 デ ー タ 探 索 問 題 を 解 く 工 程 を 具 体 例 と 図 3.1を 用 い て ， 説 明 す る ． ① 全 体 デ ー タ 集 約 ・ グ ル ー プ 化 処 理 ス テ ッ プ 全 体 デ ー タ𝐷に 対 し て 事 前 に 与 え ら れ た 集 約 ・ グ ル ー プ 化 処 理𝑉を 実 行 す る ．（ 図 3.1の 下 側 の 𝑉(𝐷)に 該 当 す る ）． 例 え ば1章 で 説 明 し た 企 業 の 販 売 デ ー タ を 分 析 す る 場 合 で は ，𝑉が 月 毎 の 売 り 上 げ を 計 算 す る 処 理 で あ る ．𝑉 は SQL 言 語 に よ り 以 下 の よ う に 記 述 で き る ． SELECT 受 注 年 月 , SUM(販 売 金 額 ) FROM テ ー ブ ル 名 GROUP BY 受 注 年 月 ② 部 分 デ ー タ 検 索 ス テ ッ プ 全 体 デ ー タ𝐷に 対 し て 部 分 デ ー タ を 検 索 す る ク エ リ 𝑆 を 実 行 す る ．（ 図3.1の 𝑆(𝐷, 𝑎1, 𝑋1), 𝑆(𝐷, 𝑎1, 𝑋2), … , 𝑆(𝐷, 𝑎𝑛, 𝑋𝑚)に 該 当 す る ）． 例 え ば 1章 で 説 明 し た 場 合 で は ，𝑆は 全 商 品 か ら 男 性 が 購 入 し た 商 品 を 選 択 す る 処 理 で あ る ． ③ 部 分 デ ー タ 集 約 ・ グ ル ー プ 化 処 理 ス テ ッ プ 様 々 な 部 分 デ ー タ𝑆(𝐷, 𝑎1, 𝑋1), 𝑆(𝐷, 𝑎1, 𝑋2), … , 𝑆(𝐷, 𝑎𝑛, 𝑋𝑚) に 対 し て ，事 前 に 与 え ら れ た 集 約・グ ル ー プ 化 処 理Vを 実 行 す る ．（ 図3.1の 𝑉(𝑆(𝐷, 𝑎1, 𝑋1)), 𝑉(𝑆(𝐷, 𝑎1, 𝑋2)) , … , 𝑉( 𝑆(𝐷, 𝑎𝑛, 𝑋𝑚))に 該 当 する ）．例え ば 1章 で 説 明 し た場 合 で は ， 男 性 が 購 入 し た 商 品 に 関 す る 月 毎 の 売 り 上 げ を 計 算 す る 例 が 挙 げ ら れ る ． ④ 乖 離 度 数 値 化 ス テ ッ プ 各 部 分 デ ー タ の 分 析 結 果𝑉(𝑆(𝐷, 𝑎1, 𝑋1)), 𝑉(𝑆(𝐷, 𝑎1, 𝑋2)), …,
図 3.1：設 定 した 問 題 を解 く 工 程
𝑉( 𝑆(𝐷, 𝑎𝑛, 𝑋𝑚))と 全 体 デ ー タ の 分 析 結 果 𝑉(𝐷)に 関 し て ， 関 数𝑈を 用 い て ，乖 離 度 を 数 値 化 す る ．例 え ば ① と ③ の 例 で 挙 げ た 全 商 品 に 関 す る 月 毎 の 売 り 上 げ と 男 性 が 購 入 し た 商 品 に 関 す る 月 毎 の 売 り 上 げ と の ユ ー ク リ ッ ド 距 離 を 計 算 す る 例 が 挙 げ ら れ る ． ⑤ 可 視 化 ス テ ッ プ 乖 離 度 数 値 化 ス テ ッ プ で 計 算 し た 数 値 が 上 位𝑘件 の 結 果 を 可 視 化 す る ．（ 図3.1で は 𝑘 = 2で あ る ）．例 え ば ユ ー ク リ ッ ド 距 離 の 値 が 大 き い 部 分 デ ー タ の 分 析 結 果 を 折 れ 線 グ ラ フ と し て 表 示 す る 例 が 挙 げ ら れ る ． 3.3.高 速 化 本 節 で は ， 特 徴 部 分 デ ー タ 探 索 問 題 に 対 し て ， 統 計 的 信 頼 区 間 推 定 の 技 術 を 用 い る こ と で ， 上 位𝑘件 の 部 分 デ ー タ の 探 索 範 囲 を 削 減 す る 手 法 に つ い て 説 明 す る ． 3.3.1.概 要 特 徴 部 分 デ ー タ 探 索 問 題 に お け る 特 徴 と し て ， 大 半 の 部 分 デ ー タ の 分 析 結 果 の 傾 向 は ， 全 体 デ ー タ の 分 析 結 果 の 傾 向 に 類 似 し て い る こ と が 挙 げ ら れ る ． こ の よ う な 全 体 デ ー タ の 分 析 結 果 か ら の 乖 離 が 小 さ い 部 分 デ ー タ は ，上 位𝑘件 の 候 補 に な り 得 な い た め ，分 析 対 象 の デ ー タ の 処 理 の 途 中 に お い て 足 き り す る こ と が 望 ま し い ．そ の た め ，統 計 的 信 頼 区 間 推 定 の 技 術 を 適 用 し て ， 上 位𝑘件 の 候 補 に な り 得 な い 部 分 デ ー タ を 早 期 に 判 断 し て ， 候 補 と な る 部 分 デ ー タ の 探 索 を 足 き り を す る こ と で 処 理 の 高 速 化 を 図 る ． 具 体 的 に は ， 分 析 対 象 の デ ー タ の 処 理 の 途 中 に お い て ， 統 計 的 信 頼 区 間 推 定 の 技 術 を 適 用 す る こ と で 分 析 結 果 の 上 限 値 と 下 限 値 を 推 定 し ， 上 位𝑘件 の 候 補 に な り 得 な い 部 分 デ ー タ の 探 索 を 足 き り す る ． 更 に ， 足 き り の 可 能 性 を 高 め る た め ， 分 析 対 象 の 値 に 関 す る 分 布 に 基 づ い て 外 れ 値 の デ ー タ 集 合 を 特 定 し ， 外 れ 値 の デ ー タ 集 合 に 対 し て 事 前 に 部 分 デ ー タ の 集 約 ・ グ ル ー プ 化 処 理 を し て か ら ， 外 れ 値 以 外 の デ ー タ 集 合 を 対 象 に 統 計 的 信 頼 区 間 推 定 の 技 術 を 適 用 し て 特 徴 部 分 デ ー タ の 探 索 を 行 う ． 提 案 手 法 の 処 理 の 流 れ は 以 下 の 通 り で あ る ． ・ 事 前 処 理 と し て ， 集 約 対 象 の デ ー タ に 関 す る 分 布 に 基 づ い て ， 分 析 対 象 で あ る 入 力 デ ー タ を 外 れ 値 の デ ー タ と 残 り の デ ー タ の 2つ に 分 割 す る ． ・ 外 れ 値 の デ ー タ に 対 し て ， 部 分 デ ー タ 毎 に 分 析 処 理 を 実 行 す る ． ・外 れ 値 以 外 の デ ー タ に 対 し て ，デ ー タ を M 個 の パ ー テ ィ シ ョ ン に 分 割 し ， パ ー テ ィ シ ョ ン 毎 に 段 階 的 に 統 計 的 信 頼 区 間 推 定 の 技 術 を 適 用 し て ， 分 析 結 果 の 上 限 値 と 下 限 値 を 更 新 し ， 上 位𝑘件 の 候 補 に な り 得 な い 部 分 デ ー タ の 探 索 を 足 き り す る ． 具 体 的 に は ， 1) 各 部 分 デ ー タ 毎 に ， 全 体 件 数 と 平 均 値 の 統 計 的 信 頼 区 間 を 推 定 し ， こ れ ら の 積 に よ っ て 外 れ 値 以 外 の 部 分 デ ー タ の 集 約 結 果 （ 総 和 ） の 統 計 的 信 頼 区 間 を 導 出 す る ． 導 出 し た 統 計 的 信 頼 区 間 の 値 に 外 れ 値 の 部 分 デ ー タ の 集 約 結 果 の 値 を 加 算 す る こ と に よ り 部 分 デ ー タ の 集 約 結 果 の 統 計 的 信 頼 区 間 を 求 め る ．2) 得 ら れ た 集 約 結 果 の 統 計 的 信 頼 区 間 を 用 い て ， 全 体 デ ー タ の 集 約 ・ グ ル ー Algorithm1: 信 頼 区 間 の 技 術 を 用 い た 部 分 デ ー タ の 足 き り 方 法 Input: 𝐴𝑙𝑙, 𝐻, 𝑇, 𝑎1, ⋯ 𝑎𝑙, 𝑏, 𝑚, 𝑓, 𝛼, 𝑘 Output: 𝑅𝑒𝑠𝑢𝑙𝑡 1 ∶ 𝑂𝑢𝑡𝑙𝑖𝑒𝑟 = 𝑃𝑟𝑒𝐺𝑟𝑜𝑢𝑝𝐵𝑦𝐴𝑔𝑔𝑟𝑒𝑔𝑎𝑡𝑒(𝐻, 𝑚, 𝑏, 𝑓) 2 ∶ 𝑇𝑀← 𝑃𝑎𝑡𝑖𝑡𝑖𝑜𝑛(𝑇) 3 ∶ 𝐟𝐨𝐫 𝐞𝐚𝐜𝐡 𝑇𝑖 ∈ 𝑇 𝐝𝐨 4 ∶ 𝐺𝑟𝑜𝑢𝑝𝐵𝑦𝐴𝑔𝑔𝑟𝑒𝑔𝑎𝑡𝑒(𝑅𝑒𝑠𝑢𝑙𝑡, 𝑇𝑖, 𝑚, 𝑏, 𝑓, ) 5 ∶ 𝐟𝐨𝐫 𝐞𝐚𝐜𝐡 𝑎𝑗 ∈ 𝑎1, ⋯ 𝑎𝑙 𝐝𝐨 6 ∶ 𝐟𝐨𝐫 𝐞𝐚𝐜𝐡 𝑋𝑜 ∈ 𝑎𝑗 𝐝𝐨 7 ∶ 𝐟𝐨𝐫 𝐞𝐚𝐜𝐡 𝐵𝑝 ∈ 𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑗= 𝑋𝑜] 𝐝𝐨 //各 部 分 デ ー タ 毎 に 件 数 と 平 均 値 の 信 頼 区 間 を 推 定 8 ∶ 𝑡𝑎𝑣𝑒← 𝐶𝑎𝑙𝑐𝑢𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝐴𝑣𝑒(𝑅𝑒𝑠𝑢𝑙𝑡, 𝛼) 9 ∶ 𝑡𝑛𝑢𝑚← 𝐶𝑎𝑙𝑐𝑢𝐼𝑛𝑡𝑒𝑟𝑣𝑎𝑙𝑁𝑢𝑚(𝑅𝑒𝑠𝑢𝑙𝑡, 𝛼) 10: 𝑈𝑛𝑢𝑚= 𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑗= 𝑋𝑜][𝐵𝑝]. 𝐶𝑜𝑢𝑛𝑡 +(𝑥̅𝑛𝑢𝑚+ 𝑡𝑛𝑢𝑚) ∗ 𝑈𝑛𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑒𝑑𝐷𝑎𝑡𝑎𝑁𝑢𝑚 11: 𝐿𝑛𝑢𝑚= 𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑗= 𝑋𝑜][𝐵𝑝]. 𝐶𝑜𝑢𝑛𝑡 +(𝑥̅𝑛𝑢𝑚− 𝑡𝑛𝑢𝑚) ∗ 𝑈𝑛𝑝𝑟𝑜𝑐𝑒𝑠𝑠𝑒𝑑𝐷𝑎𝑡𝑎𝑁𝑢𝑚 // 件 数 と 平 均 値 の 積 に よ っ て 集 約 結 果 の 信 頼 区 間 を 導 出 12: 𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑗= 𝑋𝑜][𝐵𝑝]. 𝑈𝑝𝑝𝐵𝑜𝑢𝑛𝑑 = 𝑂𝑢𝑡𝑙𝑖𝑒𝑟[𝑎𝑗= 𝑋𝑜][𝐵𝑝] + (𝑥̅𝑎𝑣𝑒+ 𝑡𝑎𝑣𝑒) ∗ 𝑈𝑛𝑢𝑚 13: 𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑖][ 𝑋𝑖][𝐵𝑝]. 𝐿𝑜𝑤𝐵𝑜𝑢𝑛𝑑 = 𝑂𝑢𝑡𝑙𝑖𝑒𝑟[𝑎𝑗= 𝑋𝑜][𝐵𝑝] + (𝑥̅𝑎𝑣𝑒− 𝑡𝑎𝑣𝑒) ∗ 𝐿𝑛𝑢𝑚 14: 𝐞𝐧𝐝 𝐟𝐨𝐫 15: 𝐟𝐨𝐫 𝐞𝐚𝐜𝐡 𝐵𝑝 ∈ 𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑗= 𝑋𝑜] 𝐝𝐨 16: 𝑦𝑚𝑎𝑥← 𝐿𝑎𝑟𝑔𝑒(𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑗= 𝑋𝑜][𝐵𝑝], 𝐴𝑙𝑙[𝐵𝑝]) 17: 𝑦𝑚𝑖𝑛← 𝑆𝑚𝑎𝑙𝑙(𝑅𝑒𝑠𝑢𝑙𝑡[𝑎𝑗= 𝑋𝑜][𝐵𝑝], 𝐴𝑙𝑙[𝐵𝑝]) //全 体 デ ー タ の 集 約 結 果 と の 乖 離 度 の 上 限 値 を 計 算 18: 𝑆𝑐𝑜𝑟𝑒[𝑎𝑗= 𝑋𝑜]. 𝐵𝑒𝑠𝑡 += 𝑈𝑡𝑖𝑙𝑖𝑡𝑦(𝐴𝑙𝑙[𝐵𝑝], 𝑦𝑚𝑎𝑥) //全 体 デ ー タ の 集 約 結 果 と の 乖 離 度 の 下 限 値 を 計 算 19: 𝑆𝑐𝑜𝑟𝑒[𝑎𝑗= 𝑋𝑜]. 𝑊𝑜𝑟𝑠𝑡 += 𝑈𝑡𝑖𝑙𝑖𝑡𝑦(𝐴𝑙𝑙[𝐵𝑝], 𝑦𝑚𝑖𝑛) 20: 𝐞𝐧𝐝 𝐟𝐨𝐫 21: 𝐞𝐧𝐝 𝐟𝐨𝐫 22: 𝐞𝐧𝐝 𝐟𝐨𝐫 // 全 部 分 デ ー タ に お い て 乖 離 度 の 下 限 値 が 上 位 か ら k 番 目 の 値 を 閾 値 と し て 設 定 23: 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 ← 𝐺𝑒𝑡𝑇𝑜𝑝𝑘(𝑆𝑐𝑜𝑟𝑒, 𝑘) 24: 𝐟𝐨𝐫 𝐞𝐚𝐜𝐡 𝑎𝑗 ∈ 𝑎1, ⋯ 𝑎𝑙 𝐝𝐨 25: 𝐟𝐨𝐫 𝐞𝐚𝐜𝐡 𝑋𝑜 ∈ 𝑎𝑗 𝐝𝐨 26: 𝐢𝐟 𝑆𝑐𝑜𝑟𝑒[𝑎𝑗= 𝑋𝑜]. 𝐵𝑒𝑠𝑡 < 𝑡ℎ𝑟𝑒𝑠ℎ𝑜𝑙𝑑 𝐭𝐡𝐞𝐧 //閾 値 を 超 え な い 部 分 デ ー タ に 関 し て 足 き り を 行 う 27: 𝑅𝑒𝑠𝑢𝑙𝑡. 𝑟𝑒𝑚𝑜𝑣𝑒( 𝑎𝑗= 𝑋𝑜) 28: 𝐞𝐧𝐝 𝐢𝐟 29: 𝐞𝐧𝐝 𝐟𝐨𝐫 30: 𝐞𝐧𝐝 𝐟𝐨𝐫 31: 𝐞𝐧𝐝 𝐟𝐨𝐫 32: 𝑟𝑒𝑡𝑢𝑟𝑛 𝑅𝑒𝑠𝑢𝑙𝑡 プ 化 結 果 か ら の 乖 離 度 の 下 限 値 （ 乖 離 が 小 さ い ） を 計 算 し ， 全 部 分 デ ー タ に お い て 上 位 か ら𝑘番 目 の 値 を 閾 値 と し て 設 定 す る ．3) 各 部 分 デ ー タ 毎 に ，全 体 デ ー タ か ら の 乖 離 度 の 上 限 値 （ 乖 離 が 大 き い ） を 計 算 し ， 閾 値 を 超 え な い 部 分 デ ー タ に 関 し て 足 き り を 行 う ． 3.3.2.適 用 方 法 信 頼 区 間 の 技 術 を 用 い た 部 分 デ ー タ の 足 き り の 適 用 方 法 を Algorithm1に 示 す ． 事 前 に 全 体 デ ー タ に 対 し て 集 約 ・ グ ル ー プ 化 処 理 を 実 行 す る （ 図 3.1の ① ：𝑉(𝐷)） と 共 に ， 分 析 対 象 で あ る 入 力 デ ー タ を 外 れ 値 の デ ー タ 𝐻と 残 り の デ ー タ 𝑇の 2つ に 分 割 す る（ 𝐷 = 𝐻 ∪ 𝑇）．集 約・ グ ル ー プ 化 処 理 の 際 ， 部 分 デ ー タ の 区 間 推 定 に 用 い る た め に ， シ ー ケ ン ス を 構 成 し て い る 各 要 素 の 最 小 値 や 集 約 し た デ ー タ 数 な ど の 統 計 情 報 を 取 得 す る ． ま た 結 果 の 正 規 化 を 行 う ．外 れ 値 の デ ー タ𝐻を 入 力 と し て ，各
部 分 デ ー タ 毎 に 集 約・グ ル ー プ 化 結 果 を 実 行 す る（ 1行 目 ，𝑉 (𝜎(𝑎=𝑋)(𝑇))）．1行 目 の 𝑂𝑢𝑡𝑙𝑖𝑒𝑟の型 は 2次 元 連 想 配 列 で あ り ，𝑎 = 𝑋と 𝐵で 特 定 さ れ る ． 途 中 で 足 き り の 判 定 を 行 う た め に 外 れ 値 以 外 の デ ー タ Tに 対 し て ， デ ー タ M個 の ブ ロ ッ ク に 分 割 す る （ 2行 目 ）． 各 ブ ロ ッ ク の 集 約・グ ル ー プ 化 処 理 が 終 了 後 に 足 き り の 判 定 を 行 う ． ま ず ， ブ ロ ッ ク𝑇1の 各 部 分 デ ー タ に 対 し て ， 集 約 ・ グ ル ー プ 化 処 理 を 実 行 す る （ 4 行 目 ， 図 3 の ③ ： 𝑉(𝑆(𝐷, 𝑎1, 𝑋1)), 𝑉(𝑆(𝐷, 𝑎1, 𝑋2)) , … , 𝑉( 𝑆(𝐷, 𝑎𝑛, 𝑋𝑚))．そ の 際 に デ ー タ 数 も 取 得 す る ．4行 目 の𝑅𝑒𝑠𝑢𝑙𝑡の 型 は 集 約 結 果 （ 総 和 ）の 信 頼 区 間 の 上 限 値（𝑈𝑝𝑝𝐵𝑜𝑢𝑛𝑑）と 集 約 結 果 の 信 頼 区 間 の 下 限 値（𝐿𝑜𝑤𝐵𝑜𝑢𝑛𝑑）の ク ラ ス の 2次 元 連 想 配 列 で あ り ，𝑎 = 𝑋と 𝐵で 特 定 さ れ る ． 部 分 デ ー タ の 集 約・グ ル ー プ 化 結 果 に 対 し て ，足 き り 判 定 を 行 う た め ， 全 体 デ ー タ と 部 分 デ ー タ の 集 約 ・ グ ル ー プ 化 結 果 の 乖 離 度𝑈 (𝑉((𝐷)), 𝑉 (𝜎(𝑎=𝑋)(𝐷))) の 信 頼 区 間 を 計 算 す る （ 15~20行 目 ）．乖 離 度𝑈 (𝑉((𝐷)), 𝑉 (𝜎(𝑎=𝑋)(𝐷)))の 信 頼 区 間 を 計 算 す る た め に ，𝑉 (𝜎(𝑎=𝑋)(𝐷))によ り 返 却 され る シ ー ケ ン ス の𝑌𝑖(𝜎(𝑎=𝑋)(𝐷)) = 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝜎(𝑎=𝑋)(𝐷)))) (1 ≤ 𝑖 ≤ ℎ)の 各 信 頼 区 間 を そ れ ぞ れ 計 算 す る （ 7~14行 目 ）．𝑌𝑖(𝜎(𝑎=𝑋)(𝐷)) = 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝜎(𝑎=𝑋)(𝐻)))) + 𝑓 (𝜋𝑚(𝜎𝑏=𝐵𝑖(𝜎(𝑎=𝑋)(𝑇))))で あ る ため ，例 外 値 の デ ー タ 𝐻 と 処 理 済 の ブ ロ ッ ク ま で の デ ー タ を 利 用 し て ， デ ー タ 全 体𝐷に 対 す る 𝑌𝑖(𝜎(𝑎=𝑋)(𝐷))の 各 信 頼 区 間 を 推 定 す る ． 尚 ，信 頼 区 間 の 計 算 は 式(2.5), (2.6)を 用 い る ．以下 の 説 明 で は ，𝑌1(𝜎(𝑎1=𝑋1)(𝑇1))を 用 いて ，𝑌1(𝜎(𝑎1=𝑋1)(𝑇))の信 頼 区 間 を 計 算 す る 場 合 と す る （ 8~11 行 目 ）． ま ず ， 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇1)))に 属 す る デ ー タ の 平 均 値 の 信 頼 区 間 を 計 算 す る た め に ， 式(2.5), (2.6)の 𝑡（ 8行目 の 𝑡𝑎𝑣𝑒） を 計 算 す る （ 8行 目 ）． 区 間 推 定 に 用 い る 母 集 団 の 最 小 値 は ， 事 前 に 取 得 し た𝜋𝑚(𝜎𝑏=𝐵1(𝐷))に 属 す る デ ー タ の 最 小 値 ，最 大 値 は𝐻と 𝑇を 分 割 し た 際 に 用 い た 閾 値 で あ る ．サ ン プ リ ン グ サ イ ズ は ，𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇1)))に 属 す る デ ー タ 数 ． 信 頼 区 間 推 定 の 母 集 団 と な る 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す るデ ー タ 数（ 式 (2.6)の𝑓𝑛= (𝑛 − 1) 𝑁⁄ の 𝑁）は ，𝜋𝑚(𝜎𝑏=𝐵1(𝐷))か ら 𝑇1の 処 理 が 終 了 時 点 で𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇1)))に 属 し て い な い デ ー タ 数 ∑ 𝜋𝑚(𝜎𝑏=𝐵𝑖(𝜎(𝑎1=𝑋1)(𝑇1)) に属す る デ ー タ 数 ) ℎ 𝑖=2 を 引 い て 見 積 も る ．次 に ，𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に属 す る デ ー タ 数 の𝐻の デ ー タ 数 に 対 す る 割 合 の 信 頼 区 間 を 計 算 す る た め に ，式(2.5), (2.6)の 𝑡（9行 目 の 𝑡𝑛𝑢𝑚）を 計 算 す る（ 9 行 目 ）．𝑇の デ ー タ の 中 で 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ の 値 は 1， 属 さ な い デ ー タ の 値 は 0と す る ． つ ま り 区 間 推 定 に 用 い る 母 集 団 の 最 小 値 は 0， 最 大 値 は 1 と な る ． サ ン プ リ ン グ サ イ ズ は𝐻1の デ ー タ 数 ， 母 集 団 の 数 は𝐻の デ ー タ 数 で あ る ．𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ 数 の 信 頼 区 間 の 上 限 値 は ， 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇1))) に 属 す る デ ー タ 数 に 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ 数 の 割 合 の 上 限 値 と 未 処 理 の デ ー タ 数 を 乗 算 し た 値 を 加 算 す る こ と で 計 算 で き る （ 10行 目 ）． 同 様 に ，𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇))) に 属 す る デ ー タ 数 の 信 頼 区 間 の 下 限 値 は ， 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇1))) に 属 す る デ ー タ 数 に 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ 数 の 割 合 の 下 限 値 と 未 処 理 の デ ー タ 数 を 乗 算 し た 値 を 加 算 す る こ と で 計 算 で き る（ 11行 ）．𝑌1(𝜎(𝑎1=𝑋1)(𝐷))の 信 頼 区 間 の 上限 値 は ， 事 前 に 計 算 し た 𝑌1(𝜎(𝑎1=𝑋1)(𝐻)) に 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ の 平 均 値 の 上 限 値 と𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ 数 の 上 限 値 を 乗 算 し た 値 を 加 算 す る こ と で 計 算 で き る （ 12行 目 ）． 同 様 に ，𝑌1(𝜎(𝑎1=𝑋1)(𝐷)) の 信 頼 区 間 の 下 限 値 は ， 𝑌1(𝜎(𝑎1=𝑋1)(𝐻))に 𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ の 平 均 値 の 下 限 値 と𝜋𝑚(𝜎𝑏=𝐵1(𝜎(𝑎1=𝑋1)(𝑇)))に 属 す る デ ー タ 数 の 下 限 値 を 乗 算 し た 値 を 加 算 す る こ と で 計 算 で き る （ 13 行 目 ） ． 同 様 に ， 𝑌2(𝜎(𝑎1=𝑋1)(𝐷)) , ⋯ , 𝑌ℎ(𝜎(𝑎1=𝑋1)(𝐷)) の 信 頼 区 間 を 計 算 し た 後 ， 乖 離 度 の 信 頼 区 間 の 上 限 値 ， 下 限 値 を 求 め る ． （ 15~20行 目 ，図3.1の ④：𝑈 (𝑉(𝐷), 𝑉(𝑆(𝐷, 𝑎1, 𝑋1)))）．ま ず ， 計 算 し た𝑌1(𝜎(𝑎1=𝑋1)(𝐷)) , ⋯ , 𝑌ℎ(𝜎(𝑎1=𝑋1)(𝐷)) の 信 頼 区 間 の 正 規 化 を 行 う ． 乖 離 度 の 上 限 値 を 計 算 す る 際 は ， 同 じ グ ル ー プ 化 属 性 の 値 に 属 す る 正 規 化 し た 𝑌1(𝐷), ⋯ , 𝑌ℎ(𝐷) と 比 較 し ， 正 規 化 し た 𝑌1(𝜎(𝑎1=𝑋1)(𝐷)) , ⋯ , 𝑌ℎ(𝜎(𝑎1=𝑋1)(𝐷)) の 信 頼 区 間 の 中 で 差 異 の 絶 対 値 が 大 き い 値 を 採 択 す る （ 16行 ） ． 正 規 化 し た𝑌1(𝐷), ⋯ , 𝑌ℎ(𝐷)と 採 択し た 値 で 乖 離 度 を 計 算 す る（ 18 行 ） ． 乖 離 度 の 下 限 値 を 計 算 す る 際 も 同 様 に 比 較 し ， 正 規 化 し た𝑌1(𝜎(𝑎1=𝑋1)(𝐷)) , ⋯ , 𝑌ℎ(𝜎(𝑎1=𝑋1)(𝐷))の 信 頼 区 間 の 中 で 差 異 の 絶 対 値 が 小 さ い 値 を 採 択 す る（ 17行 ）． 正 規 化 し た𝑌1(𝐷), ⋯ , 𝑌ℎ(𝐷)と 採 択 し た 値 で 乖 離 度 を 計 算 す る （ 19行 ） ． 最 後 に ， 足 き り の 判 定 を 行 う ． （ 23 行 ～ 30行 ）．足 き り の 判 定 を 行 う 閾 値 は𝑘番 目 に 大 き い 乖 離 度 の 信 頼 区 間 の 下 限 値 と す る ． あ る 部 分 デ ー タ の 乖 離 度 の 信 頼 区 間 の 上 限 値 が 閾 値 を 下 回 っ た 場 合 ， そ の 部 分 デ ー タ の𝑇2で の 集 約 ・ グ ル ー プ 化 処 理 と 判 定 処 理 を 打 ち 切 る ．𝑇2の デ ー タ を 処 理 し た 後 の 判 定 時 は ， 式(2.5), (2.6)の 母 集団 の デ ー タ 数 を 順 次 更 新 する ．そ れ に よ り ， 区 間 推 定 の 精 度 を 上 げ る こ と が で き ， よ り 多 く の 部 分 デ ー タ の 足 き り が 可 能 で あ る ．
4. 評 価 実 験
本 章 で は 提 案 手 法 の 高 速 化 の 効 果 を 評 価 す る ．4.1 節 で 実 験 方 法 に つ い て ， 4.2 節 で 実 験 結 果 に つ い て 説 明 す る ．4.1.実 験 方 法 提 案 手 法 の 有 効 性 を 検 証 す る た め に ， 信 頼 区 間 の 技 術 を 用 い た 部 分 デ ー タ の 足 き り を 適 用 し た 場 合 と し て い な い 場 合 に お け る 処 理 全 体 （ 図 3.1 の ① ， ② ， ③ ， ④ ） の 実 行 時 間 を 計 測 す る 実 験 を 行 っ た ． 乖 離 度 を 数 値 化 す る 関 数 と し て ユ ー ク リ ッ ド 距 離 を 用 い た ． 本 実 験 の デ ー タ セ ッ ト は 以 下 の と お り で あ る ． 販 売 デ ー タ ： 経 営 科 学 系 研 究 部 会 連 合 協 議 会 主 催 ， 平 成27年 度 デ ー タ 解 析 コ ン ペ テ ィ シ ョ ン で 提 供 さ れ た デ ー タ で あ る ． レ シ ー ト 情 報 ， レ シ ー ト 行 番 号 ， 税 込 金 額 ， 点 数 ， 店 舗 ， 日 付 情 報 ， 時 間 帯 ， 会 員 区 分 ， 性 別 区 分 な ど 商 品 の 受 注 に 関 す る 情 報 で 構 成 さ れ て い る ． レ コ ー ド 数 は 52,038,260（ 1 年 ），属 性 数 は 32 で あ る ． 本 実 験 で は ， 乖 離 度 が 大 き い 分 析 結 果 を 生 み 出 す 部 分 デ ー タ の 探 索 を す る 際 に ， 提 案 手 法 を 適 用 す る 場 合 と し な い 場 合 の 処 理 時 間 を 比 較 す る ． 実 験 で 選 択 し た 集 約 ・ グ ル ー プ 化 処 理 ， 部 分 デ ー タ の 条 件 に 用 い る 属 性 は 以 下 の と お り で あ る ． 集 約 ・ グ ル ー プ 化 処 理 ： 店 舗 毎 の 売 り 上 げ （9店 舗 ）， 店 舗 毎 の 販 売 点 数 （9店 舗 ）， 時 間 帯 毎 の 売 り 上 げ （ 19 時 間 帯 ），時 間 帯 毎 の 販 売 点 数（19時 間 帯 ）を 集 約・グ ル ー プ 化 処 理 と す る ． 集 約 属 性 が 税 込 金 額 の と き は ， 税 込 金 額 の 値 が1980よ り 大 き い 112848レ コ ー ド を 事 前 処 理 し た ．集 約 属 性 が 点 数 の と き は 点 数 の 値 が5よ り 大 き い100650レ コ ー ド を 事 前 処 理 し た ． 部 分 デ ー タ の 条 件 に 用 い る 属 性 ： 部 分 デ ー タ の 条 件 に 用 い る 属 性 は ，店 舗（9），時 間 帯（ 19），会 員 区 分（ 2）， 性 別 区 分（4），分 類 １ コ ー ド（ 8），分 類 ２ コ ー ド（ 25）， 分 類 ３ コ ー ド（164）の 7つ と す る1．分 類 １ コ ー ド ，分 類 ２ コ ー ド ， 分 類 ３ コ ー ド は 商 品 の カ テ ゴ リ 区 分 の 単 位 で あ る ． そ れ ぞ れ 分 類 １ コ ー ド は 分 類 ２ コ ー ド の ， 分 類 ２ コ ー ド は 分 類 ３ コ ー ド の 上 位 と な っ て い る ． グ ル ー プ 化 属 性 が 店 舗 の 集 約 ・ グ ル ー プ 化 処 理 で は ， 時 間 帯 ， 会 員 区 分 ， 性 別 区 分 ， 分 類 １ コ ー ド ， 分 類 ２ コ ー ド ， 分 類 ３ コ ー ド を 部 分 デ ー タ の 条 件 と し て 設 定 し た ． グ ル ー プ 化 属 性 が 時 間 帯 の 集 約 ・ グ ル ー プ 化 処 理 で は ， 店 舗 ， 会 員 区 分 ， 性 別 区 分 ， 分 類 １ コ ー ド ， 分 類 ２ コ ー ド ， 分 類 ３ コ ー ド を 部 分 デ ー タ の 条 件 と し て 設 定 し た ．
本 実 験 に は ， CPU が Intel(R) Core(TM) i7-4702MQ， ク ロ ッ ク 周 波 数 は2.20GHz，コ ア 数 は 4，メ モ リ は 16GB の PC を 使 用 し ， デ ー タ ベ ー ス 管 理 シ ス テ ム と し て SQLServer2014 を 用 い た ． 4.2.実 験 結 果 図 4.1 は 集 約・グ ル ー プ 化 処 理 が 店 舗 毎 の 売 り 上 げ ， 店 舗 毎 の 販 売 点 数 ， 時 間 帯 毎 の 売 り 上 げ ， 時 間 帯 毎 の 1括 弧 内 の 数 字 は 部 分 デ ー タ の 条 件 に 用 い る 属 性 の 具 体 的 な 値 の 件 数 で あ る ． 図 4.1：店 舗 毎 の 売 り 上 げ・販 売 点 数 ，時 間 帯 毎 の 売 り 上 げ ・ 販 売 点 数 に お け る 処 理 全 体 の 実 行 時 間 図 4.2： 店 舗 毎 の 売 り 上 げ に お け る 有 意 水 準 変 更 時 の 実 行 時 間 販 売 点 数 に お け る 乖 離 度 が 大 き い 部 分 デ ー タ 上 位 10 件 を 探 索 す る 処 理 の 実 行 時 間 で あ る ． 信 頼 区 間 の 有 意 水 準αは 0.05で あ る ． 店 舗 毎 の 売 り 上 げ で は 2.02倍 ， 店 舗 毎 の 販 売 点 数 で は2.12倍 ， 時 間 帯 毎 の 売 り 上 げ で は 1.41倍 ，時 間 帯 毎 の 販 売 点 数 で は 1.31倍 の 高 速 化 に 成 功 し て い る ． 全 て の 集 約 ・ グ ル ー プ 化 処 理 で ， 足 き り 判 定 を 行 っ た 場 合 の 上 位 10 件 の 結 果 は ， 足 き り 判 定 を 行 っ て い な い 場 合 の 上 位 10 件 の 結 果 と 同 じ で あ る ． 図 4.2 は 店 舗 毎 の 売 り 上 げ に お け る 有 意 水 準（α）変 更 時 の 乖 離 度 が 大 き い 部 分 デ ー タ 上 位 10 件 を 探 索 す る 処 理 の 実 行 時 間 で あ る ．α = 0.4の 場 合 は 2.18倍 ， α = 0.6の 場 合 は 2.22倍 の 高 速 化 に そ れ ぞ れ 成 功 し て い る ． α = 0.4の 場 合 は ， 足 き り 判 定 を 行 っ て い な い 場 合 と 上 位 10 件 の 結 果 は 変 わ ら ず ，α = 0.6の 場 合 は 上 位 10 件 中 9 件 の 結 果 が 一 致 し て い た ． 実 験 結 果 か ら ， 有 意 水 準 の 値 を 大 き く す る と よ り 高 速 化 を 期 待 で き る が ， 上 位𝑘件 に あ て は ま る 部 分 デ ー タ を 誤 っ て 足 き り す る 確 率 が 高 く な る と 予 想 さ れ る ． 図 4.3 は 店 舗 毎 の 売 り 上 げ に お け る 上 位𝑘件 変 更 時 の 乖 離 度 が 大 き い 部 分 デ ー タ を 探 索 す る 処 理 の 実 行 時 間 で あ る ． 信 頼 区 間 の 有 意 0 10 20 30 40 50 60 70 80 90 tim e(s ec ) 集約・グループ化処理 処理全体の実行時間 足きり判定あり 足きり判定なし 0 10 20 30 40 50 α = 0.05 α = 0.4 α = 0.6 tim e(s ec ) 有意水準（α） 有意水準変更時の実行時間 足きり判定あり
図 4.3： 店 舗 毎 の 売 り 上 げ に お け る 上 位 k 件 変 更 時 の 実 行 時 間 図 4.4： 店 舗 毎 の 売 り 上 げ に お け る デ ー タ サ イ ズ 変 更 時 の 実 行 時 間 水 準αは 0.05で あ る ．𝑘 = 1の 場 合 は 3.26倍 ，k = 20の 場 合 は1.56倍 ， 𝑘 = 50の 場 合 は 1.12倍 の 高 速 化 に 成 功 し て い る ． 全 て 足 き り 判 定 を 行 っ た 場 合 の 上 位𝑘件 の 結 果 は ， 足 き り 判 定 を 行 っ て い な い 場 合 の 上 位𝑘件 の 結 果 と 同 じ で あ る ．𝑘の 値 を 小 さ く す る と 部 分 デ ー タ の 足 き り の 判 定 に 用 い る 閾 値 が 大 き く な る の で ， よ り 多 く の 部 分 デ ー タ の 足 き り が 可 能 と な る ． 図 4.4 は 店 舗 毎 の 売 り 上 げ に お け る デ ー タ サ イ ズ 変 更 時 の 乖 離 度 が 大 き い 部 分 デ ー タ 上 位 10 件 を 探 索 す る 処 理 の 実 行 時 間 で あ る ．信 頼 区 間 の 有 意 水 準αは 0.05 で あ る ．レ コ ー ド 数 が4,406,363（ 1 ヶ 月 ）の 場 合 は 1.61 倍 ，レ コ ー ド 数 が26,524,815（ 6 ヶ 月 ）の 場 合 は 1.77倍 の 高 速 化 に そ れ ぞ れ 成 功 し て い る ． 全 て 足 き り 判 定 を 行 っ た 場 合 の 上 位 10 件 の 結 果 は ， 足 き り 判 定 を 行 っ て い な い 場 合 の 上 位 10 件 の 結 果 と 同 じ で あ る ． サ ン プ リ ン グ サ イ ズ が 大 き く な る と 信 頼 区 間 の 精 度 が 向 上 す る た め ， デ ー タ サ イ ズ が 大 き く な る ほ ど 高 速 化 の 効 果 が 期 待 で き る ．
5. 分 析 可 視 化 結 果
本 章 で は 提 案 手 法 に よ っ て 得 ら れ た 分 析 結 果 に つ い て 説 明 す る ． 図 5.1,5.2は 店 舗 毎 の 売 り 上 げ に お い て 全 商 品 と の 乖 離 度 が 大 き い 部 分 デ ー タ の 分 析 可 視 化 結 果 の 一 例 で あ る ． デ ー タ セ ッ ト は 2年 分 で あ る ． 右 軸 は 図 5.1：店 舗 毎 の 売 り 上 げ に お け る 全 商 品 と の 乖 離 度 が 大 き い 部 分 デ ー タ の 分 析 結 果 ① （ 性 別 区 分 ＝ 2） 図 5.2：店 舗 毎 の 売 り 上 げ に お け る 全 商 品 と の 乖 離 度 が 大 き い 部 分 デ ー タ の 分 析 結 果 ② （ 時 ＝ 22） 全 商 品 の 売 り 上 げ ， 左 軸 は 部 分 デ ー タ の 売 り 上 げ の 値 で あ る ．図 5.1の 部 分 デ ー タ は 女 性 が 購 入 し た 商 品 ，図 5.2の 部 分 デ ー タ は 22時 台 に 売 れ た 商 品 ，図 5.1,5.2な ど の 分 析 結 果 か ら 他 店 舗 と 比 べ ，D店 ，E店 ，F店 ，H店 は 以 下 の 共 通 の 特 徴 を 持 つ ． ・ 女 性 の 購 入 金 額 が 少 な い （ 他 店 舗 に 比 べ て 男 性 の 割 合 が 大 き い ） ・ 夜 遅 い 時 間 帯 の 売 り 上 げ の 割 合 が 大 き い ・ 非 会 員 の 購 入 金 額 が 多 い 共 通 の 特 徴 を も つ D店 ，E店 ，F店 ，H店 の 中 で 最 も 売 り 上 げ が 少 な い 店 舗 は D店 ，最 も 売 り 上 げ が 多 い 店 舗 は H 店 で あ る ．D店 の 売 り 上 げ 少 な い 要 因 と H店 の 売 り 上 げ が 多 い 要 因 を よ り 詳 し く 分 析 す る た め ， そ れ ぞ れ 部 分 デ ー タ の 条 件 を D店 で 売 れ た 商 品 か つ そ の 他 の 部 分 デ ー タ の 条 件 ， H店 で 売 れ た 商 品 か つ そ の 他 の 部 分 デ ー タ の 条 件 と 設 定 し ， 月 毎 の 売 り 上 げ に お い て 全 商 品 と の 乖 離 度 が 大 き い 分 析 結 果 を 探 索 し た ． そ の 分 析 可 視 化 結 果 の 一 例 が 図 5.3,5.4で あ る ．図 5.3の 部 分 デ ー タ は D店 で 売 れ た 商 品 か つ 23時 台 に 売 れ た 商 品 ， 図 5.4の 部 分 デ ー タ は H店 で 売 れ た 商 品 か つ 鮮 魚 に 関 す る 商 品 で あ る ． 図 5.3を 見 る と D店 は 夜 遅 い 時 間 帯 の 売 り 上 げ の 割 合 が 大 き い 店 舗 に も か か わ ら ず ， 2014年 11月 か ら 急 激 に 23時 台 の 売 り 上 げ が 落 ち て い る こ と が わ か る ． こ の 原 因 を 分 析 し ， 改 善 す る こ と で 似 た 特 徴 を も つ H店 の 売 り 上 げ ま で は D店 の 売 り 上 げ を 伸 ば す こ と が 期 待 で き る ． ま た ， 図 5.4を 見 る と H店 の 鮮 魚 に 関 す る 商 品 の 売 り 上 げ は 全 商 品 の 売 り 上 げ と 異 な る 遷 移 を 示 し て お り ， 微 増 な が ら 1年 目 の 売 り 上 げ と 比 較 し て 2年 目 の 売 り 上 げ が 増 加 し て い る ． こ の 傾 向 は D店 に お い て は あ ま り 見 ら れ な か っ た ．そ の た め ，D店 に お い て 鮮 魚 に 関 す る 商 品 展 開 に 力 を 入 れ る こ と で D店 の 売 り 上 げ を 伸 ば す こ と が で き る 可 能 性 が あ る ． 0 10 20 30 40 50 60 70 80 0 10 20 30 40 50 tim e(s ec ) k の値 上位k件変更時の実行時間 足きり判定あり 0 10 20 30 40 50 60 70 80 90 0 20,000 40,000 60,000 tim e(s ec ) レコード数（103） 店舗毎の売り上げの実行時間 足きり判定あり 足きり判定なし図 5.3：月 毎 の 売 り 上 げ に お け る 全 商 品 と の 乖 離 度 が 大 き い 部 分 デ ー タ の 分 析 結 果 ① （ D店 ， 時 ＝ 23） 図 5.4：月 毎 の 売 り 上 げ に お け る 全 商 品 と の 乖 離 度 が 大 き い 部 分 デ ー タ の 分 析 結 果 ② （ H店 ， 分 類 ２ 名 称 ＝ 鮮 魚 ）
6. 関 連 研 究
デ ー タ 解 析 ツ ー ル に は ，Spotfire[2]，Polaris[3]な ど が あ る ．Spotfire は ，散 布 図 を ベ ー ス と し た 可 視 化 シ ス テ ム で あ る ．Polaris は 基 本 的 な デ ー タ ベ ー ス ク エ リ と テ ー ブ ル 代 数 に よ る 可 視 化 の 仕 様 を 統 合 し た シ ス テ ム で あ る ． 両 者 と も デ ー タ セ ッ ト に 最 適 な 可 視 化 設 定 を 自 動 的 に 選 択 す る が ， 分 析 者 が 設 定 す る こ と も 可 能 で あ る ． こ れ ら の ツ ー ル は 分 析 者 が 着 目 し た い 全 て の 属 性 を 手 動 で 選 択 す る 必 要 が あ る ． 自 動 で 分 析 結 果 を 可 視 化 す る 機 能 を 持 つ デ ー タ 解 析 ツ ー ル に は ，Profiler[4]，Vizdeck[5]，SEEDB[6,7]な ど が あ る ．Profiler は デ ー タ の 異 常 を 自 動 で 検 出 し ，い く つ か の 可 視 化 結 果 を 表 示 す る ． Vizdeck は ダ ッ シ ュ ボ ー ド 上 に 2 次 元 で 表 示 し 得 る 全 て の 可 視 化 結 果 を 表 示 す る ．ま た ，SEEDB の 研 究 の 目 的 は ，OLAP 型 の 分 析 に お い て ， 分 析 者 が 試 行 錯 誤 を 通 し て 有 用 性 の 高 い 分 析 結 果 を 探 索 す る 工 程 を 自 動 化 す る こ と に あ る ． OLAP に よ る デ ー タ ブ ラ ウ ジ ン グ は 分 析 者 の デ ー タ セ ッ ト へ の 理 解 の 一 助 と な る [8,9,10]．本 論 文 の 提 案 手 法 と SEEDB の 相 違 点 は SEEDB が 事 前 に 与 え ら れ た 部 分 デ ー タ に 集 約 ・ グ ル ー プ 化 処 理 を 実 行 し た 際 に ， 有 用 性 が 高 い 分 析 結 果 を 生 み 出 す 集 約 ・ グ ル ー プ 化 処 理 を 探 索 す る の に 対 し て ， 提 案 手 法 は 事 前 に 与 え ら れ た 集 約 ・ グ ル ー プ 化 処 理 を 全 体 デ ー タ と 部 分 デ ー タ に 実 行 し た 際 に 乖 離 の 程 度 が 大 き い ま た は 小 さ い 部 分 デ ー タ を 探 索 す る こ と で あ る ． 複 数 の ソ ー ス か ら デ ー タ を 収 集 ・ 統 合 ・ 可 視 化 と い う 一 連 の 処 理 を 自 動 化 す る 技 術 と し て Google Fusion Tables[11]，DEVise[12]な ど が あ る ．Google fusion tables は ，web 上 か ら 様 々 な デ ー タ を 収 集 し ，統 合 す る こ と に よ り テ ー ブ ル を 作 成 し ，そ の 分 析 結 果 を 可 視 化 す る ．7. お わ り に
本 稿 で は ， 有 用 性 が 高 い 分 析 結 果 を 生 み 出 す 部 分 デ ー タ を 効 率 的 に 探 索 す る 手 法 を 提 案 し た ． 提 案 手 法 で は ， ま ず 問 題 設 定 を 定 義 し ， 乖 離 度 を 数 値 化 す る 関 数 と し て ユ ー ク リ ッ ド 距 離 を 用 い る こ と に よ り 解 く 行 程 を 説 明 し た ． さ ら に 統 計 的 信 頼 区 間 推 定 の 技 術 を 用 い て 部 分 デ ー タ の 足 き り を 行 い ， 探 索 範 囲 を 削 減 す る こ と で 高 速 化 を 実 現 し た ． 今 後 は 有 用 性 に 関 し て 更 な る 議 論 を 行 い ，よ り 詳 細 な 分 析 の も と 上 位 k件 の 分 析 可 視 化 結 果 を ユ ー ザ に 提 案 す る 機 能 を 実 装 す る 予 定 で あ る ．参 考 文 献
[1] R. J. Serfling et al. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, 2(1):39–48, 1974.
[2] C. Ahlberg. Spotfire: An information exploration environment. In SIGMOD Conference, pages 25–29, 1996.
[3] C. Stolte, D. Tang, and P. Hanrah an, “Polaris: a system for query, analysis, and visualizationof multidimensional databases,” Communications of the ACM - Remembering Jim Gray 51(11), 1990. [4] S. Kandel et al. Profiler: integrated statistical analysis
and visualization for data quality assessment. In AVI, pages 547–554, 2012.
[5] A. Key, B. Howe, D. Perry, and C. Aragon. Vizdeck: Self-organizing dashboards for visual analytics. In SIGMOD Conference, pages 681 –684, 2012.
[6] A. Parameswaran, N. Polyzotis, and H. Garcia -Molina. Seedb: Visualizing database queries efficiently. PVLDB, 7(4), 2013.
[7] M. Vartak, S. Madden, A. G. Parameswaran, and N. Polyzotis. SEEDB: automatically generating query visualizations. PVLDB, 7(13) , 2014.
[8] S. Sarawagi, “Explaining Differences in Multidimensional Aggregates ,” Proceedings of VLDB, 1999.
[9] S. Sarawagi, “User-adaptive exploration of multidimensional data,” Proceedings of VLDB, 2000.
[10] G. Sathe and S. Sarawagi , “Intelligent Rollups in Multidimensional OLAP Data,” Proceedings of VLDB, 2001.
[11] H. Gonzalez et al. Google fusion tabl es: web-centered data management and collaboration. In SIGMOD Conference, pages 1061 –1066, 2010.
[12] M.Livny, C. S.Jensen, K.Beyer, G.Chen, D.Donjerkovic, S.Lawande, J.Myllymaki, and K.Wenger, “Devise: integrated querying and visual exploration of largedataset s,” In SIGMOD Conference, pages 301-312, 1997.
