統計的信頼区間を用いた特徴的な部分データの効率的探索

DEIM Forum 2016 D3-4
統計的信頼区間を用いた特徴的な部分データの効率的探索
水野 陽平†
鬼塚 真†
†大阪大学情報科学研究科 〒565-0871 大阪府吹田市山田丘 1-5
E-mail: †{mizuno.yohei, onizuka}@ist.osaka-u.ac.jp
全商品
全体の傾向を把握したり，例外的なデータを発見する
男性が購入した商品
2014年12月
2014年11月
2014年10月
2014年9月
2014年8月
元からデータベースを集約・グループ化してデータの
2014年7月
れ て い る ． OLAP 型 の 分 析 を 用 い る こ と で ， 様 々 な 次
2014年6月
解 析 に お い て は OLAP 型 の 分 析 処 理 []が 頻 繁 に 用 い ら
2014年5月
が重要な課題となっている．特に，ビジネスデータの
2014年4月
して考え，有益な情報を抽出する手法 を適用すること
2014年3月
つ多様性に富んだデータであるビッグデータを資源と
正規化した月毎の売り上げ
2014年2月
これまで企業が扱ってきたデータ以上に大規模か
0.25
0.2
0.15
0.1
0.05
0
2014年1月
1. ま え が き
正規化した売り上げ
あらまし ビジネスデータの解析においては，データ全体の特徴を分析する OLAP(online analytical processing) 型の
集約・グループ化の分析処理が頻繁に用いられているが，販売データの地域性や時期性の影響を見て販売戦略を決
める場合などでは，ユーザが指定した分析クエリに対して，有用性が高い分析結果を生み出す部分データを探索す
ることが重要である（これを特徴部分データ探索問題と呼ぶ）
．この問題を処理するためには，総当りで部分データ
を探索して分析クエリを実行して分析結果の有用性を判定する必要があるため，膨大な時間を要する．そこで本稿
では，特徴部分データ探索処理の高速化に取り組む．具体的には，統計的信頼区間を用いることで，有用性が高い
分析結果の候補になり得ない部分データの探索の足きりを行い高速化を図る．実際の販売データに対して提案技術
を適用した結果，95％の信頼水準において最大 3 倍の高速化を確認した．
キーワード マイニング，可視化
衣服
ことができる．特に，データ全体の傾向とは異なる傾
図 1.1：全 商 品 ，男 性 が 購 入 し た 商 品 ，衣 服 の 正 規 化 し
向を示す部分データを特定することで，特徴的な部分
た月毎の売り上げ
データを発見できる場合がある．例えば， 販売データ
はないが，衣服に関する商品の月間総売り上げの遷移
の地域性や時期性の影響を見て販売戦略を決めたい場
は全商品の月間総売り上げの遷移と乖離が大きいため，
合などでは，分析処理に対して有用性が高い分析結果
全商品と比較して衣服の売り上げは販売時期の影響を
を生み出す部分データを探索することが重要である．
大きく受けていると判断できる． そのため，衣服の
本稿ではこれを特徴部分データ探索問題と呼ぶ．
2014年 3月 の 売 上 が 高 い 要 因 を 分 析 し ，そ の 要 因 を 他 の
具体例として，企業の販売データの分析を用いて，
特徴部分データ探索問題の重要性を説明する．
企業の販売データの分析
商品販売に水平展開することによって，他の商品の売
り上げも伸ばすことができる可能性がある．
上記の分析を行うためには，任意の条件を満たす部
販売データを分析する場合，商品全体の売り上げの傾
分データを選択し，部分データ毎に分析処理を行い，
向からの乖離が大きい商品を見つ けることが重要であ
部分データの分析結果と全データの分析結果の乖離が
る．なぜならば，例えば商品全体の月毎の売上げ傾向
どの程度かを判断する必要がある．分析する部分デー
と異なる商品の場合，その商品は時期の影響が大きい
タの数は，部分データの条件に用いる属性の取り得る
と判断できるためである．この判断に基づいて，該当
値の件数となり膨大である．そのため，条件を満たす
の商品の調達量を月毎に調整し，また売り上げが低い
部分データを手動で総当りするには多くの 時間を要す
月 に 新 商 品 の 投 入 や PR を 行 う な ど の 販 売 方 針 を 戦 略
る．
的 に 決 定 す る こ と が で き る ． 例 え ば ， 図 1.1は 全 商 品 ，
本稿では上記の問題に対して，特徴的な部分データ
男性が購入した商品，衣服に関する商品の月毎の売り
を自動で高速に探索する手法を提案する．
上げの遷移の可視化結果である（但し， 1 年の売り上
自動化する技術：有用性が高い分析結果を生み出す部
げ の 総 和 が 1 に な る よ う 正 規 化 し て い る ）． 男 性 が 購
分データとは，全体データの分析結果との乖離の程度
入した商品の月間総売り上げの遷移は全商品の月間総
が大きいと仮定する．利用者は集約・グループ化によ
売り上げの遷移と乖離が小さいため，特徴的な情報で
る分析クエリを事前に与え，更に分析処理を全体デー
タおよび部分データに実行して得た分析結果同士の 乖
𝑃𝑟(𝑡)に 対 し て ， t > 0 に お い て 以 下 の 式 で 上 界 を 与 え
離の程度を数値化する関数を事前に与える．解くべき
ることができる．
技術課題は，分析処理を全体データに実行して得た分
析 結 果 に 対 し て ， 特 徴 的 な 部 分 デ ー タ の 上 位 𝑘件 を 自
𝑃𝑟(𝑡) ≤ 𝑒𝑥𝑝[−2𝑛𝑡 2 ⁄(1 − 𝑓𝑛 )(𝑏 − 𝑎)2 ]
但 し ， 𝑓𝑛 = (𝑛 − 1)⁄𝑁， 𝑎 = min 𝑋𝑖 ， 𝑏 = max 𝑋𝑖 で あ る ．
1≤𝑖≤𝑁
動で求めることである．
(2.2)
1≤𝑖≤𝑁
高速化する技術：本稿では，特徴部分データ探索問題
に 対 し て ，統 計 的 信 頼 区 間 推 定 の 技 術 を 用 い る こ と で ，
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)
評 価 実 験 に よ り ， 95％ の 信 頼 水 準 に お い て 上 位 1 件 の
式 (2.3), (2.4)よ り ，母 集 団 の 平 均 値 𝜇の 100 ∙ (1 − 𝛼)%信 頼
特徴部分データを探索する場合， 最大で 3 倍の高速化
区 間（ 𝛼は 信 頼 区 間 の 有 意 水 準 ）の 式 (2.5)を 導 出 す る こ
が可能であることを確認した．
とができる．
𝑥̅ − 𝑡 < 𝜇 < 𝑥̅ + 𝑡
本 稿 の 構 成 は ，以 下 の 通 り で あ る ．2章 に て 前 提 知 識
(2.5)
に つ い て 説 明 し ， 3章 に お い て 提 案 手 法 の 詳 細 を 示 し ，
式 (2.4)を 𝑡に つ い て 整 理 す る と ， 𝑡の 値 は 以 下 の 式 で 計
4章 に て 提 案 手 法 の 評 価 と 分 析 に つ い て 説 明 す る ． 5章
算することができる．
にて関連研究について述べ，6 章にて本稿をまとめ，
今後の課題について論ずる．
𝑡 = √(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,
2. 事 前 知 識
本章では提案手法に用いた信頼区間と信頼区間の
0.2, 0.4, 0.4}）．標 本 平 均 は ，𝑥̅ = 0.43で あ る ．母 集 団 の 最
推 定 に 用 い て い る 確 率 不 等 式 に つ い て 説 明 す る ．2.1節
小 値 は ， 𝑎 = 0，最 大 値 は 𝑏 = 1と し た 場 合 ，式 (2.6)に 各
で は Hoeffding の 確 率 不 等 式 に つ い て ， 2.2 節 で は
値 を 代 入 す る と ，母 集 団 の 平 均 値 𝜇の 95%(𝛼 = 0.05)信 頼
Hoeffding の 確 率 不 等 式 を 用 い た 平 均 値 の 区 間 推 定 に
区間は以下のように計算できる．
ついて説明する．
𝑡 = √(1 −
2.1.Hoeffding の 確 率 不 等 式
確率不等式は，母集団の確率変数に対して，具体的
な確率分布を想定せず，期待値や分散などの限定的な
10 − 1
) (1 − 0)2 (log 2 − log 0.05)⁄(2 × 10)
50
𝑡 = 0.041
∴ 0.389 < 𝜇 < 0.471
情報だけに基づいて，それらの確率変数の和あるいは
平均に関する上限確率の上界を評価するものである．
3. 提 案 手 法
Hoeffding の 確 率 不 等 式 は ，確 立 変 数 の 期 待 値 や 有 限
本 章 で は 提 案 手 法 に つ い て 説 明 す る ．3.1節 で 特 徴 部
の定義域が判明しているときに，確率変数の上限確率
分 デ ー タ 特 定 問 題 の 概 要 ，3.2節 で 問 題 を 解 く 工 程 の 説
の上界を与える有用な確率不等式として知られている．
明 ，3.3節 で そ の 工 程 の 高 速 化 の 際 に ，部 分 デ ー タ の 足
分布系が未知の場合に，非復元抽出した標本の平均値
き り に Hoeffding の 確 率 不 等 式 を 用 い た 区 間 推 定 の 技
が母集団の平均値を超える確率は以下の式で表せる．
術を適用する手法について説明する．
𝑃𝑟(𝑡) = 𝑃𝑟[𝑥̅ − 𝜇 ≥ 𝑡]
1
1
𝑛
𝑁
但 し ，𝑥̅ = ∑𝑛𝑖=1 𝑥𝑖 ，𝜇 =
(2.1)
∑𝑁
𝑖=1 𝑋𝑖 で あ り ，n は サ ン プ リ
ン グ サ イ ズ ，N は 母 集 団 の デ ー タ 数 で あ る ．こ の 確 率
3.1.問 題 定 義
利用者は集約・グループ化による分析処理を事前に
与え，更に分析処理を全体データおよび部分データに
実行して得た分析結果同士の乖離度を数値化する関数
図 3.1： 設 定 し た 問 題 を 解 く 工 程
を事前に与える．特徴部分データ探索 問題は，分析処
を取得する処理である．
理を全体データに実行して得た分析結果に 対して，有
𝑎𝑟𝑔 top-k 𝑈 (𝑉(𝐷), 𝑉(𝑆(𝐷, 𝑎, 𝑋)))
用 性 が 高 い 分 析 結 果 を 生 み 出 す 部 分 デ ー タ の 上 位 𝑘件
(3.5)
𝑆
を 求 め る 問 題 で あ る ．全 体 デ ー タ を 𝐷，集 約・グ ル ー プ
化 処 理 を 𝑉， 部 分 デ ー タ を 選 択 す る ク エ リ を 𝑆と す る ．
𝑉, 𝑆は 以 下 の 形 式 で 定 義 さ れ る ．
S(𝐷, 𝑎, 𝑋) ≡ 𝜎(𝑎=𝑋) (𝐷)
𝐷
V(𝐷, 𝑏, 𝑓, 𝑚) ≡ 𝑊𝑏,𝑓(𝑚)
但 し ， 𝑎𝑟𝑔 top-k 𝑓(𝑥)は 𝑥を 変 化 さ せ た 際 に 𝑓(𝑥) が 最 大
𝑆
(3.1)
(3.2)
の 値 を 返 却 す る 上 位 𝑘個 の 𝑥を 返 却 す る 関 数 で あ り ， 𝑈
但 し ，𝑎, 𝑏, 𝑚は 𝐷の 属 性 ，𝑋は 属 性 𝑎の 値 ，𝑓は 属 性 𝑚に 対
は 2つ の シ ー ケ ン ス を 入 力 と し て ，シ ー ケ ン ス を 構 成 す
す る 集 約 関 数 で あ る ． 𝜎は リ レ ー シ ョ ナ ル 代 数 に お け
る各要素の乖離の総和を計算する関数である． 乖離度
る 選 択 演 算 ，𝑊は 𝑏で グ ル ー プ 化 し 各 グ ル ー プ ご と に 集
を数値化する具体的な関数として，ユークリッド距離
約 関 数 𝑓を 𝑚に 適 用 す る 処 理 で あ る ．例 え ば ，図 1.1の 衣
を用いる．
服に関する商品の月毎の売り上げを計算する処理は，
3.2.問 題 を 解 く 行 程 の 概 要
𝑊
𝜎(カ テ ゴ リ =衣 服 ) (𝐷)
受 注 年 月 ,𝑆𝑈𝑀(販 売 金 額 )
(3.3)
特徴部分データ探索問題を解く工程を具体例と図
3.1を 用 い て ， 説 明 す る ．
と表現される．以後，集約・グループ化処理は事前に
①
決 め ら れ て い る た め 引 数 を 省 略 す る ．Vが 集 約・グ ル ー
全 体 デ ー タ 𝐷に 対 し て 事 前 に 与 え ら れ た 集 約 ・ グ ル ー
プ 化 処 理 で あ る た め ，そ の 結 果 は シ ー ケ ン ス 型 で あ り ，
プ 化 処 理 𝑉を 実 行 す る ．（ 図 3.1の 下 側 の 𝑉(𝐷)に 該 当 す
以下の形式で表現する．
る ）． 例 え ば 1章 で 説 明 し た 企 業 の 販 売 デ ー タ を 分 析 す
𝑉(𝐷) = [(𝐵1 , 𝑌1 ), ⋯ , (𝐵ℎ , 𝑌ℎ )] (3,4)
但 し ，{𝐵1 , ⋯ , 𝐵ℎ } = 𝜋𝑚 (𝐷)，𝑌𝑖 (𝐷) = 𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝐷))) (1 ≤
𝑖 ≤ ℎ)で あ る ． 𝐵𝑖 に 属 す る デ ー タ を ， 𝑌𝑖 の 入 力 で あ る
𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝐷))に 属 す る デ ー タ と 定 義 す る ．ま た ，𝐷 = 𝐻 ∪
𝑇と す る と 𝑌𝑖 (𝐷) = 𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝐻 ∪ 𝑇)))で あ る ． σと πに
対 し て ∪ は 分 配 則 が 適 用 可 能 で あ る た め ， 𝑌𝑖 (𝐷) =
𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝐻)) ∪ 𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝑇)))で あ る ． 𝑓 が SUM や
COUNT の 場 合 は ， +に よ っ て 𝑓を 分 解 可 能 で あ り ，
𝑌𝑖 (𝐷) = 𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝐻))) + 𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝑇)))と な る ． 提
全体データ集約・グループ化処理ステップ
る 場 合 で は ， 𝑉が 月 毎 の 売 り 上 げ を 計 算 す る 処 理 で あ
る ． 𝑉 は SQL 言 語 に よ り 以 下 の よ う に 記 述 で き る ．
SELECT 受 注 年 月 , SUM(販 売 金 額 )
FROM テ ー ブ ル 名
GROUP BY 受 注 年 月
②部分データ検索ステップ
全 体 デ ー タ 𝐷に 対 し て 部 分 デ ー タ を 検 索 す る ク エ リ 𝑆
を 実 行 す る ．（ 図 3.1の 𝑆(𝐷, 𝑎1 , 𝑋1 ), 𝑆(𝐷, 𝑎1 , 𝑋2 ), … ,
𝑆(𝐷, 𝑎𝑛 , 𝑋𝑚 )に 該 当 す る ）． 例 え ば 1章 で 説 明 し た 場 合 で
は ，𝑆は 全 商 品 か ら 男 性 が 購 入 し た 商 品 を 選 択 す る 処 理
である．
③部分データ集約・グループ化処理ステップ
様 々 な 部 分 デ ー タ 𝑆(𝐷, 𝑎1 , 𝑋1 ), 𝑆(𝐷, 𝑎1 , 𝑋2 ), … , 𝑆(𝐷, 𝑎𝑛 , 𝑋𝑚 )
に 対 し て ，事 前 に 与 え ら れ た 集 約・グ ル ー プ 化 処 理 Vを
案 手 法 で は ，集 約 関 数 と し て SUM や COUNT を 仮 定 す
実 行 す る ．（ 図 3.1の 𝑉(𝑆(𝐷, 𝑎1 , 𝑋1 )), 𝑉(𝑆(𝐷, 𝑎1 , 𝑋2 )) , … ,
る．
𝑉( 𝑆(𝐷, 𝑎𝑛 , 𝑋𝑚 ))に 該 当 す る ）．例 え ば 1章 で 説 明 し た 場 合
次に，全体データと部分データに同じ集約・グルー
では，男性が購入した商品に関する月毎の売り上げを
プ化処理をした結果同士の乖離度を数値化する 関数を
計算する例が挙げられる．
𝑈と し た と き に ，式 (3.5)に よ り 上 位 𝑘件 の 部 分 デ ー タ を
④乖離度数値化ステップ
取 得 す る ．式 (3.5)は ，乖 離 度 を 数 値 化 し た 値 の 上 位 𝑘件
各 部 分 デ ー タ の 分 析 結 果 𝑉(𝑆(𝐷, 𝑎1 , 𝑋1 )), 𝑉(𝑆(𝐷, 𝑎1 , 𝑋2 )), …,
𝑉( 𝑆(𝐷, 𝑎𝑛 , 𝑋𝑚 ))と 全 体 デ ー タ の 分 析 結 果 𝑉(𝐷)に 関 し て ，
関 数 𝑈を 用 い て ，乖 離 度 を 数 値 化 す る ．例 え ば ① と ③ の
例で挙げた全商品に関する月毎の売り上げと男性が購
入した商品に関する月毎の売り上 げとのユークリッド
距離を計算する例が挙げられる．
⑤可視化ステップ
乖 離 度 数 値 化 ス テ ッ プ で 計 算 し た 数 値 が 上 位 𝑘件 の 結
果を可視化する．
（ 図 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次 元 連 想
配 列 で あ り ， 𝑎 = 𝑋と 𝐵で 特 定 さ れ る ． 部 分 デ ー タ の 集
約・グ ル ー プ 化 結 果 に 対 し て ，足 き り 判 定 を 行 う た め ，
全体データと部分データの集約・グループ化結果の乖
𝜋𝑚 (𝜎𝑏=𝐵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) (𝑇)))に 属 す る デ ー タ 数 の 上 限 値
（ 15~20行 目 ）．乖 離 度 𝑈 (𝑉((𝐷)), 𝑉 (𝜎(𝑎=𝑋) (𝐷)))の 信 頼 区
を 乗 算 し た 値 を 加 算 す る こ と で 計 算 で き る （ 12行 目 ）．
同 様 に ， 𝑌1 (𝜎(𝑎1=𝑋1) (𝐷)) の 信 頼 区 間 の 下 限 値 は ，
間 を 計 算 す る た め に ，𝑉 (𝜎(𝑎=𝑋) (𝐷))に よ り 返 却 さ れ る シ
ー ケ ン ス の 𝑌𝑖 (𝜎(𝑎=𝑋) (𝐷)) = 𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝜎(𝑎=𝑋) (𝐷))))
(1 ≤ 𝑖 ≤ ℎ)の 各 信 頼 区 間 を そ れ ぞ れ 計 算 す る （ 7~14 行
目 ）． 𝑌𝑖 (𝜎(𝑎=𝑋) (𝐷)) = 𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝜎(𝑎=𝑋) (𝐻)))) +
𝑓 (𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝜎(𝑎=𝑋) (𝑇))))で あ る た め ，例 外 値 の デ ー タ 𝐻
と処理済のブロックまでのデータを利用して，データ
全 体 𝐷に 対 す る 𝑌𝑖 (𝜎(𝑎=𝑋) (𝐷))の 各 信 頼 区 間 を 推 定 す る ．
尚 ，信 頼 区 間 の 計 算 は 式 (2.5), (2.6)を 用 い る ．以 下 の 説
明 で は ，𝑌1 (𝜎(𝑎1=𝑋1) (𝑇1 ))を 用 い て ，𝑌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) (𝐷)) の 信 頼 区 間
区 間 を 計 算 す る 場 合 と す る （ 8~11 行 目 ）． ま ず ，
の正規化を行う．乖離度の上限値を計算する際は，同
じ グ ル ー プ 化 属 性 の 値 に 属 す る 正 規 化 し た
𝑌1 (𝐷), ⋯ , 𝑌ℎ (𝐷) と 比 較 し ， 正 規 化 し た
𝜋𝑚 (𝜎𝑏=𝐵1 (𝜎(𝑎1=𝑋1) (𝑇1 )))に 属 す る デ ー タ の 平 均 値 の 信 頼
𝑌1 (𝜎(𝑎1=𝑋1) (𝐷)) , ⋯ , 𝑌ℎ (𝜎(𝑎1=𝑋1) (𝐷)) の 信 頼 区 間 の 中 で 差
区 間 を 計 算 す る た め に ， 式 (2.5), (2.6)の 𝑡（ 8行 目 の 𝑡𝑎𝑣𝑒 ）
を 計 算 す る （ 8行 目 ）． 区 間 推 定 に 用 い る 母 集 団 の 最 小
値 は ， 事 前 に 取 得 し た 𝜋𝑚 (𝜎𝑏=𝐵1 (𝐷))に 属 す る デ ー タ の
異 の 絶 対 値 が 大 き い 値 を 採 択 す る （ 16行 ） ． 正 規 化 し
た 𝑌1 (𝐷), ⋯ , 𝑌ℎ (𝐷)と 採 択 し た 値 で 乖 離 度 を 計 算 す る （ 18
最 小 値 ，最 大 値 は 𝐻と 𝑇を 分 割 し た 際 に 用 い た 閾 値 で あ
る ．サ ン プ リ ン グ サ イ ズ は ，𝜋𝑚 (𝜎𝑏=𝐵1 (𝜎(𝑎1=𝑋1) (𝑇1 )))に 属
するデータ数．信頼区間推定の母集団となる
𝜋𝑚 (𝜎𝑏=𝐵1 (𝜎(𝑎1=𝑋1) (𝑇)))に 属 す る デ ー タ 数（ 式 (2.6)の 𝑓𝑛 =
(𝑛 − 1)⁄𝑁の 𝑁）は ，𝜋𝑚 (𝜎𝑏=𝐵1 (𝐷))か ら 𝑇1 の 処 理 が 終 了 時
点 で 𝜋𝑚 (𝜎𝑏=𝐵1 (𝜎(𝑎1=𝑋1) (𝑇1 ))) に 属 し て い な い デ ー タ 数
ℎ
行）．乖離度の下限値を計算する際も同様に比較し，
正 規 化 し た 𝑌1 (𝜎(𝑎1=𝑋1) (𝐷)) , ⋯ , 𝑌ℎ (𝜎(𝑎1=𝑋1) (𝐷)) の 信 頼 区
間 の 中 で 差 異 の 絶 対 値 が 小 さ い 値 を 採 択 す る（ 17行 ）．
正 規 化 し た 𝑌1 (𝐷), ⋯ , 𝑌ℎ (𝐷)と 採 択 し た 値 で 乖 離 度 を 計
算 す る （ 19行 ） ． 最 後 に ， 足 き り の 判 定 を 行 う ． （ 23
行 ～ 30行 ）．足 き り の 判 定 を 行 う 閾 値 は 𝑘番 目 に 大 き い
乖離度の信頼区間の下限値とする．ある部分データの
乖離度の信頼区間の上限値が閾値を下回った場合，そ
の 部 分 デ ー タ の 𝑇2 で の 集 約 ・ グ ル ー プ 化 処 理 と 判 定 処
∑𝑖=2 𝜋𝑚 (𝜎𝑏=𝐵𝑖 (𝜎(𝑎1=𝑋1) (𝑇1 )) に 属 す る デ ー タ 数 ) を 引 い て
理 を 打 ち 切 る ． 𝑇2 の デ ー タ を 処 理 し た 後 の 判 定 時 は ，
見 積 も る ．次 に ，𝜋𝑚 (𝜎𝑏=𝐵1 (𝜎(𝑎1=𝑋1) (𝑇)))に 属 す る デ ー タ
式 (2.5), (2.6)の 母 集 団 の デ ー タ 数 を 順 次 更 新 す る ．そ れ
により，区間推定の精度を上げることができ，より多
くの部分データの足きりが可能である．
数 の 𝐻の デ ー タ 数 に 対 す る 割 合 の 信 頼 区 間 を 計 算 す る
た め に ，式 (2.5), (2.6)の 𝑡（ 9行 目 の 𝑡𝑛𝑢𝑚 ）を 計 算 す る（ 9
行 目 ）． 𝑇の デ ー タ の 中 で 𝜋𝑚 (𝜎𝑏=𝐵1 (𝜎(𝑎1=𝑋1) (𝑇)))に 属 す
る デ ー タ の 値 は 1， 属 さ な い デ ー タ の 値 は 0と す る ． つ
ま り 区 間 推 定 に 用 い る 母 集 団 の 最 小 値 は 0， 最 大 値 は 1
と な る ． サ ン プ リ ン グ サ イ ズ は 𝐻1 の デ ー タ 数 ， 母 集 団
の 数 は 𝐻の デ ー タ 数 で あ る ．𝜋𝑚 (𝜎𝑏=𝐵1 (𝜎(𝑎1=𝑋1) (𝑇)))に 属
す る デ ー タ 数 の 信 頼 区 間 の 上 限 値 は ，
4. 評 価 実 験
本 章 で は 提 案 手 法 の 高 速 化 の 効 果 を 評 価 す る ．4.1 節
で 実 験 方 法 に つ い て ， 4.2 節 で 実 験 結 果 に つ い て 説 明
する．
4.1.実 験 方 法
処理全体の実行時間
術を用いた部分データの足きり を適用した場合として
い な い 場 合 に お け る 処 理 全 体 （ 図 3.1 の ① ， ② ， ③ ，
④）の実行時間を計測する実験を行った． 乖離度を数
値化する関数としてユークリッド距離を用いた．本実
time(sec)
提案手法の有効性を検証するために， 信頼区間の技
験のデータセットは以下のとおりである．
90
80
70
60
50
40
30
20
10
0
足きり判定あり
足きり判定なし
販売データ：経営科学系研究部会連合協議会主催，平
成 27年 度 デ ー タ 解 析 コ ン ペ テ ィ シ ョ ン で 提 供 さ れ た デ
ータである．レシート情報，レシート行番号，税込金
額，点数，店舗，日付情報，時間帯，会員区分，性別
集約・グループ化処理
区分など商品の受注に関する情報で構成されている．
レ コ ー ド 数 は 52,038,260（ 1 年 ），属 性 数 は 32 で あ る ．
図 4.1：店 舗 毎 の 売 り 上 げ・販 売 点 数 ，時 間 帯 毎 の 売 り
本実験では，乖離度が大きい分析結果を生み出す部分
上げ・販売点数における処理全体の実行時間
データの探索をする際に，提案手法を適用する場合と
有意水準変更時の実行時間
しない場合の処理時間を比較する．実験で選択した集
50
は以下のとおりである．
集 約 ・ グ ル ー プ 化 処 理 ： 店 舗 毎 の 売 り 上 げ （ 9店 舗 ），
店 舗 毎 の 販 売 点 数 （ 9店 舗 ）， 時 間 帯 毎 の 売 り 上 げ （ 19
time(sec)
約・グループ化処理，部分データの条件に用いる属性
40
30
足きり判定あり
20
時 間 帯 ），時 間 帯 毎 の 販 売 点 数（ 19時 間 帯 ）を 集 約・グ
10
ループ化処理とする．集約属性が税込金額のときは，
0
α = 0.05
税 込 金 額 の 値 が 1980よ り 大 き い 112848レ コ ー ド を 事 前
処 理 し た ．集 約 属 性 が 点 数 の と き は 点 数 の 値 が 5よ り 大
α = 0.4
α = 0.6
有意水準（α）
き い 100650レ コ ー ド を 事 前 処 理 し た ．
図 4.2： 店 舗 毎 の 売 り 上 げ に お け る 有 意 水 準 変 更 時 の
部分データの条件 に用いる 属性：部分データの条件に
実行時間
用 い る 属 性 は ，店 舗（ 9），時 間 帯（ 19），会 員 区 分（ 2），
性 別 区 分（ 4），分 類 １ コ ー ド（ 8），分 類 ２ コ ー ド（ 25），
販 売 点 数 に お け る 乖 離 度 が 大 き い 部 分 デ ー タ 上 位 10
分 類 ３ コ ー ド（ 164）の 7つ と す る 1 ．分 類 １ コ ー ド ，分
件を探索する処理の実行時間である．信頼区間の有意
類２コード，分類３コードは商品のカテゴリ 区分の単
水 準 αは 0.05で あ る ． 店 舗 毎 の 売 り 上 げ で は 2.02倍 ， 店
位である．それぞれ分類１コードは分類２コードの，
舗 毎 の 販 売 点 数 で は 2.12倍 ， 時 間 帯 毎 の 売 り 上 げ で は
分類２コードは分類３コードの上位となっている．グ
1.41倍 ，時 間 帯 毎 の 販 売 点 数 で は 1.31倍 の 高 速 化 に 成 功
ループ化属性が店舗の集約・グループ化処理では，時
している．全ての集約・グループ化処理で，足きり判
間帯，会員区分，性別区分，分類１コード，分類２コ
定 を 行 っ た 場 合 の 上 位 10 件 の 結 果 は ， 足 き り 判 定 を
ード，分類３コードを部分データの条件として設定し
行 っ て い な い 場 合 の 上 位 10 件 の 結 果 と 同 じ で あ る ．
た．グループ化属性が時間帯の集約・グループ化処理
図 4.2 は 店 舗 毎 の 売 り 上 げ に お け る 有 意 水 準（ α）変
では，店舗，会員区分，性別区分，分類１コード，分
更 時 の 乖 離 度 が 大 き い 部 分 デ ー タ 上 位 10 件 を 探 索 す
類２コード，分類３コードを部分データの条件として
る 処 理 の 実 行 時 間 で あ る ． α = 0.4の 場 合 は 2.18倍 ， α =
設定した．
0.6の 場 合 は 2.22倍 の 高 速 化 に そ れ ぞ れ 成 功 し て い る ．
本 実 験 に は ， CPU が Intel(R) Core(TM) i7-4702MQ，
α = 0.4の 場 合 は ， 足 き り 判 定 を 行 っ て い な い 場 合 と 上
ク ロ ッ ク 周 波 数 は 2.20GHz，コ ア 数 は 4，メ モ リ は 16GB
位 10 件 の 結 果 は 変 わ ら ず ， α = 0.6の 場 合 は 上 位 10 件
の PC を 使 用 し ， デ ー タ ベ ー ス 管 理 シ ス テ ム と し て
中 9 件の結果が一致していた．実験結果から，有意水
SQLServer2014 を 用 い た ．
準の値を大きくするとより高速化を期待できるが，上
位 𝑘件 に あ て は ま る 部 分 デ ー タ を 誤 っ て 足 き り す る 確
4.2.実 験 結 果
図 4.1 は 集 約・グ ル ー プ 化 処 理 が 店 舗 毎 の 売 り 上 げ ，
店舗毎の販売点数，時間帯毎の売り上げ，時間帯毎の
率 が 高 く な る と 予 想 さ れ る ． 図 4.3 は 店 舗 毎 の 売 り 上
げ に お け る 上 位 𝑘件 変 更 時 の 乖 離 度 が 大 き い 部 分 デ ー
タを探索する処理の実行時間である．信頼区間の有意
1括 弧 内 の 数 字 は 部 分 デ ー タ の 条 件 に 用 い る 属 性 の 具 体 的 な 値 の 件 数 で あ る ．
上位k件変更時の実行時間
80
time(sec)
70
60
50
40
30
足きり判定あり
20
10
0
0
10
20
k の値
30
40
50
図 4.3： 店 舗 毎 の 売 り 上 げ に お け る 上 位 k 件 変 更 時 の
図 5.1：店 舗 毎 の 売 り 上 げ に お け る 全 商 品 と の 乖 離 度 が
大 き い 部 分 デ ー タ の 分 析 結 果 ① （ 性 別 区 分 ＝ 2）
実行時間
time(sec)
店舗毎の売り上げの実行時間
90
80
70
60
50
40
30
20
10
0
足きり判定あり
足きり判定なし
0
20,000
40,000
レコード数（103）
60,000
図 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.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店 の 売 り 上 げ を
伸ばすことができる可能性がある．
した際に乖離の程度が大きいまたは小さい部分データ
を探索することである．
複数のソースからデータを収集・統合・可視化とい
う 一 連 の 処 理 を 自 動 化 す る 技 術 と し て Google Fusion
Tables[11]，DEVise[12]な ど が あ る ．Google fusion tables
は ，web 上 か ら 様 々 な デ ー タ を 収 集 し ，統 合 す る こ と
に よ り テ ー ブ ル を 作 成 し ，そ の 分 析 結 果 を 可 視 化 す る ．
図 5.3：月 毎 の 売 り 上 げ に お け る 全 商 品 と の 乖 離 度 が 大
き い 部 分 デ ー タ の 分 析 結 果 ① （ D店 ， 時 ＝ 23）
7. お わ り に
本稿では，有用性が高い分析結果を生み出す部分デ
ータを効率的に探索する手法を提案した．提案手法で
は，まず問題設定を定義し，乖離度を数値化する関数
としてユークリッド距離を用いることにより解く行程
を説明した．さらに統計的信頼区間推定の技術を用い
て部分データの足きりを行い，探索範囲を削減するこ
とで高速化を実現した．今後は有用性に関して更なる
議 論 を 行 い ，よ り 詳 細 な 分 析 の も と 上 位 k件 の 分 析 可 視
化結果をユーザに提案する機能を実装する予定である．
参
考
文
献
[1] R. J. Serfling et al. Probability inequalities for the sum
図 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 が 事 前 に 与 え ら れ た 部 分
データに集約・グループ化処理を実行した際に，有用
性が高い分析結果を生み出す集約・グループ化処理を
探索するのに対して，提案手法は事前に与えられた集
約・グループ化処理を全体データと部分データに実行
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
largedatasets,”
In
SIGMOD
Conference, pages 301-312, 1997.