データの表現と操作(2)：データベース・OLAP - 法政大学

Data Mining:
Concepts and Techniques
データウエアハウスと OLAP
Jiawei Han
Department of Computer Science
University of Illinois at Urbana-Champaign
Data Mining: Concepts and Techniques
1
デタウアウスとＯＬＡＰ
データウエアハウスとＯＬＡＰ

データウエアハウスとは?

多次元データモデル

データウエアハウスの構成

データウエアハウスシステム

データウエアハウスとデータマイニング
Data Mining: Concepts and Techniques
2
デタウエアハウスとは?
データウエアハウスとは?

様々な定義, でも厳密なものはない

意思決定支援データベース



業務データベースとは別個に存在
業務デ
タベスとは別個に存在
情報処理を支援、分析に統合・履歴データを用いる機能を提供
“デタウエアウ(DW)とは意思決定支援のための目的指向,
“データウエアハウ(DW)とは,
目的指向統合さ
れた, 時間依存的な, でも変更のないデータの集合”—W. H. Inmon

データウエアハウス処理

DW の構築と利用のプロセス
Data Mining: Concepts and Techniques
3
DW — 目的指向 Subject
Subject-Oriented
Oriented

主たる目的



顧客customer, 製品product, 販売sales
意思決定のためのデータのモデル化と分析

日常業務の支援ではない

データベースシステムではトランザクション管理
目的に沿った単純で簡潔なビューを提示

意思決定支援に関係しないデータを除去
意思決定支援に関係しないデ
タを除去
Data Mining: Concepts and Techniques
4
DW －統合 Integrated


複数の異種デタソスを統合
複数の異種データソースを統合
 関係ＤＢ, テキストファイル, エクセルフファイル, オンライ
ン取引情報, ・・・
データクリーニングと統合
 矛盾除去：名前付け,
矛盾除去：名前付けデ
データ構成
タ構成, 属性値単位
属性値単位・尺度
尺度 etc.
etc


ホテル価格: 通貨, 税金, 朝食込, etc.
データを
デ
タを DW に移動するときに変換
Data Mining: Concepts and Techniques
5
DW — 時間依存 Time Variant


DW データが対象とする時間幅の大きさ

業務ＤＢ: 現在値が中心

DW: 履歴データの視点 (過去 past 5-10 年など)
DW のデータ構成

明示的・暗黙的に時間 time 要素を含む

業務データにはなくてもよい
業務デ
タにはなくてもよい
Data Mining: Concepts and Techniques
6
DW — 非更新 Nonvolatile

業務環境から変換され別媒体に記憶保存
業務環境から変換され、別媒体に記憶保存

DW データは業務データの変更の影響を受けない

ＤＢ基本機能（トランザクション処理・回復機能、同時制
御）不要

必要となる基本機能

デタ初期ロドとデータアクセス
データ初期ロード
デタアクセス
Data Mining: Concepts and Techniques
7
DW vs
vs. 分散異種 DBMS

従来の分散異種 heterogeneous DB の統合環境: 質問指向、整合性
質問指向整合性

異種データベース上で wrappers/mediators を構築

質問がでると



（１） meta-dictionary を使って当該サイトに向けた質問を変換

(2) 解を共通形式に変換
情報フィルタリング, 資源の競合が発生
DW: 更新指向, 高性能

予めデータを統合しておく
予めデ
タを統合しておく

ＤＷに格納し、質問処理・分析に直接使用
Data Mining: Concepts and Techniques
8
分散データベース
Di t ib t d Databases
Distributed
D t b



データが複数サイトに配置、各々を管理
 DBMSが独立に動作している
分散型データ独立
 利用者はデータは位置場所を知らない
 (物理
(物理・論理データ独立を拡張)
論理デタ独立を拡張)
分散型トランザクション管理、特に原子性
 利用者は複数の WRITE トランザクションを複数サ
トランザクシンを複数サ
イトに実行できる
法政大学データベース入門
分散ＤＢの研究対象



利用者はデータの配置場所を知っている
 データ独立性, 原子性などに疑問
効率よく管理する手法
広域的分散性の必要性（インターネット）
 管理者さえも配置場所を知りたくない
法政大学データベース入門
分散デタベスの種類
分散データベースの種類


同種 Homogeneous:
 どのサイトも同じ種類のDBMSが実行
異種 Heterogeneous:
 サイト毎に異なるDBMSが稼動
 (異なる関係DBMS、あるいは非関係 DBMS)
法政大学データベース入門
分散DBMS の方式

Client- Server

-

Client は質問をマスタサ
イトに送りすべての処理
イトに送り，すべての処理
はマスタサイトで行なう
Thin vs. Fat clients.
集合型の通信
- client サイドキャッシ
ュなどが問題
などが問題
協調型 (Collaborating)
Server

質問は複数のサイトで実
行
法政大学データベース入門
DW vs. 業務 DBMS

OLTP (on-line transaction processing)




従来 DBMS の主要な業務, 100MB – 1GB
日々の業務処理: 購買, 在庫管理, 金融, 製造, 給与処理, 登録業務,
会計 etc.
会計,
t
OLAP (on-line analytical processing)

DW の主要な業務,
の主要な業務 100GB – 1TB

データ分析と意思決定
特徴 (OLTP vs. OLAP):

利用者・システム: 顧客志向 vs. マーケット志向

データ内容: 現状・細部 vs. 履歴・統合概要的

DB 設計: ER + 応用依存 vs. スター型 + 目的別

ビュー: 現状・局所的 vs. 時系列的・統合概要的

利用パターン: 修正・おなじパターン vs. 読込み・複雑大規模・アドホック
Data Mining: Concepts and Techniques
13
個別ＤＷの必要性


高性能システム

DBMS— OLTPむけ: アクセス方式, 索引, 同時制御, 回復管理

Warehouse—OLAPむけ: 複雑なOLAP 質問, 多次元ビュー,統合化
個別機能・個別データ
デ




欠損値: 意思決定支援では履歴データが重要
データ統合化:
デ
タ統合化 DWでは統合化が必須(汎化aggregation,要約
DWでは統合化が必須(汎化
ti 要約
summarization), 異種データソース
デタの品質: 異なるデ
データの品質:
異なるデータがあれば通常別個のデータ表現(コード・
タがあれば通常別個のデタ表現(コド
書式)形式なので統合が必要
OLAP 分析を DBMS 上で直接行うシステムが増えている
Data Mining: Concepts and Techniques
15
デタウアウスとＯＬＡＰ
データウエアハウスとＯＬＡＰ

データウエアハウスとは?

多次元データモデル（データ記述）

データウエアハウスの構成

データウエアハウスシステム

データウエアハウスとデータマイニング
Data Mining: Concepts and Techniques
16
テーブル・スプレッドシートとキューブ
テ
ブルスプレッドシトとキュブ Cube

DW デ
データは
タは多次元デ
多次元データモデル
タモデル multidimensional data model を想定

データキューブ data cube

多次元でデタのモデル化操作可能
多次元でデータのモデル化・操作可能

次元テーブル



it
item
(it
(item_name, brand,
b d type)
t
)

time(day, week, month, quarter, year)
Fact テ
テーブル：measures
ブル：measures (dollars
(dollars_sold)
sold) , 各次元テ
各次元テーブルへのキー
ブルへのキ
Base cuboid : n-次元キューブ

0 D cuboid ：apex
0-D
apex cuboid
Data Mining: Concepts and Techniques
17
多次元デタ
多次元データ
S l データは
Sales
デタは product,
d t month,
th region
i の関数
次元: Product,
Product Location,
Location Time
階層集約パス：
I d t
Industry
R
Region
i
Y
Year
Category Country Quarter
P
Product
t

Product
City
Office
Month Week
Day
Month
Data Mining: Concepts and Techniques
18
Data Cube 例
2Qtr
Date
3Qtr
4Qtr
sum
USA
U.S.A
C
Canada
Mexico
Coun
ntry
TV
PC
VCR
sum
1Qtr
年間 sales
(TV , U.S.A.)
sum
Data Mining: Concepts and Techniques
19
用語



ファクトテーブル(Fact
フ
クトテブル(F t ttable)
bl )
次元テーブル(Dimension tables)
評価尺度(Measures)
product
prodId
name
price
sale
orderId
date
custId
prodId
storeId
qty
amt
store
storeId
city
customer
custId
name
address
dd
city
20
次元階層
sType
store
store storeId
s5
s7
s9
city
cityId
sfo
sfo
la
tId
t1
t2
t1
mgr
joe
fred
nancy
y
 スノーフレーク
 集約集合の配置
region
sType tId
t1
t2
size
small
large
city
pop
1M
5M
cityId
sfo
la
location
downtown
suburbs
regId
north
south
region regId
nam e
north cold region
south warm region
21
キュブ
キューブ
ファクトテブル
ファクトテーブル：
sale
prodId
p1
p2
p1
p2
storeId
c1
c1
c3
c2
多次元キューブ:
amt
12
11
50
8
p1
p2
c1
12
11
c2
c3
50
8
（２次元）
22
3-D
3
D キュ
キューブ
ブ
ファクトテーブル：
sale
prodId
p1
p2
p
p1
p2
p1
p1
storeId
c1
c1
c3
c2
c1
c2
date
1
1
1
1
2
2
多次元キューブ:
amt
12
11
50
8
44
4
day 2
day 1
p1
p2 c1
p1
12
p2
11
c1
44
c2
4
c2
c3
c3
50
8
（３次元）
23
概念階層: 次元 (location)
all
all
ll
Europe
region
country
city
office
Germany
Frankfurt
...
...
...
Spain
North_America
h
i
Canada
Vancouver ...
L. Chan
...
Data Mining: Concepts and Techniques
...
Mexico
Toronto
M. Wind
24
Cuboids ：Cubeに対応して
all
0-D(apex)
0
D(apex) cuboid
product
product,date
date
country
product,country
1-D cuboids
date, country
2-D cuboids
3-D(base) cuboid
product,
d t date,
d t country
t
Data Mining: Concepts and Techniques
25
Cube: Cuboid集合（束）
all
time
0-D(apex) cuboid
item
location
supplier
1-D cuboids
time,location
time,item
item,location
time,supplier
location,supplier
2-D cuboids
item,supplier
time,location,supplier
3-D cuboids
time item location
time,item,location
time,item,supplier
item,location,supplier
4-D(base) cuboid
time, item, location, supplier
Data Mining: Concepts and Techniques
26
DW の概念モデル

次元尺度
次元と尺度

Star スキーマ: fact テーブルを中心、次元テーブルが接続

Snowflake スキーマ:
スキマ: star スキーマの発展形
スキマの発展形


次元階層に沿って低次元テーブル集合に正規化 normalized

S
Snowflake
fl k 状
Fact Constellation : 複数の fact テーブルが次元テーブ
ルを共有

銀河スキーマ galaxy schema
Data Mining: Concepts and Techniques
27
Star スキ
Sta
スキーマ
time
item
time_key
day
day_of_the_week
y_ _ _
month
quarter
year
Sales
Sa
es Fact
act Table
ab e
time_key
item key
item_key
item_key
item name
item_name
brand
type
supplier
pp _type
yp
branch_key
location
branch
l ti
location_key
k
branch_key
branch_name
branch type
branch_type
units_sold
dollars_sold
avg_sales
location_key
street
city
state_or_province
country
Measures
Data Mining: Concepts and Techniques
30
Snowflake
S
o a e スキ
スキーマ
time
time_key
day
day_of_the_week
y_ _ _
month
quarter
year
it
item
Sales Fact Table
time_key
item
e _key
ey
item_key
item_name
brand
type
supplier_key
supplier
supplier_key
supplier
key
supplier_type
branch_key
location
branch
location key
location_key
branch_key
branch_name
branch type
branch_type
units_sold
d ll
dollars_sold
ld
avg_sales
M
Measures
Data Mining: Concepts and Techniques
location_key
street
city_key
city
city_key
city
state or province
state_or_province
country
31
Fact Constellation スキ
スキーマ
マ
time
time_key
day
day_of_the_week
month
quarter
year
item
Sales Fact Table
time_key
item_key
item_name
b d
brand
type
supplier_type
item_keyy
location_keyy
branch_key
branch_name
branch_type
units_sold
dollars sold
dollars_sold
avg_sales
time_key
item_key
shipper_key
from_location
branch_key
branch
Shi i Fact
Shipping
F t Table
T bl
location
to_location
location_key
street
city
province_or_state
country
dollars_cost
Measures
Data Mining: Concepts and Techniques
units_shipped
shipper
shipper_key
shipper
key
shipper_name
location_key
shipper_type 32
Cube 定義 (BNF) ： DMQL



Cube 定義 (Fact テーブル)
ブ
define cube <cube_name> [<dimension_list>]:
<
<measure_list>
li t>
次元定義 (次元テーブル)
d fi dimension
define
di
i <dimension_name>
di
i
as
(<attribute_or_subdimension_list>)
共有次元テブル
共有次元テーブル
 まず “cube 定義”
 define dimension
dimen ion <dimension_name>
<dimen ion n me> as
<dimension_name_first_time> in cube
<cube name first time>
<cube_name_first_time>
Data Mining: Concepts and Techniques
33
Star スキ
スキーマ定義：
マ定義： DMQL
define cube sales_star [time, item, branch, location]:
dollars_sold = sum(sales_in_dollars), avg_sales =
avg(sales_in_dollars), units_sold = count(*)
define dimension time as (time_key, day, day_of_week,
month,
th quarter,
t year))
define dimension item as (item_key, item_name, brand,
type supplier
type,
supplier_type)
type)
define dimension branch as (branch_key, branch_name,
branch type)
branch_type)
define dimension location as (location_key, street, city,
province or state country)
province_or_state,
Data Mining: Concepts and Techniques
34
Snowflake
S
o a e スキ
スキーマ定義：DMQL
定義
Q
define cube sales_snowflake [time, item, branch, location]:
dollars_sold = sum(sales_in_dollars), avg_sales =
avg(sales in dollars) units_sold
avg(sales_in_dollars),
units sold = count(*)
define dimension time as (time_key, day, day_of_week, month, quarter,
year)
define dimension item as (item_key, item_name, brand, type,
supplier(supplier_key, supplier_type))
define dimension branch as (branch_key, branch_name, branch_type)
define dimension location as (location_key, street, city(city_key,
province_or_state,
i
t t country))
t ))
Data Mining: Concepts and Techniques
35
Fact
act Co
Constellation
ste at o の定義
の定義：DMQL
Q
define cube sales [[time,, item,, branch,, location]:
]
dollars_sold = sum(sales_in_dollars), avg_sales =
avg(sales_in_dollars), units_sold = count(*)
define dimension time as ((time_key,
_ y, day,
y, day_of_week,
y_ _
, month,, quarter,
q
, year)
y )
define dimension item as (item_key, item_name, brand, type, supplier_type)
define dimension branch as (branch_key, branch_name, branch_type)
define dimension location as (location_key,
(location key, street, city, province
province_or_state,
or state,
country)
define cube shipping [time, item, shipper, from_location, to_location]:
dollar cost = sum(cost_in_dollars),
dollar_cost
sum(cost in dollars), unit_shipped
unit shipped = count(
count(*))
define dimension time as time in cube sales
define dimension item as item in cube sales
define dimension shipper as (shipper_key,
(shipper key shipper
shipper_name,
name location as location
in cube sales, shipper_type)
define dimension from_location as location in cube sales
define dimension to_location
to location as location in cube sales
Data Mining: Concepts and Techniques
36
３種類のData Cube尺度

分配的: min({1,2,3,4,5})
min({1 2 3 4 5}) = min(min({1,2,3}),min({4,5}))
min(min({1 2 3}) min({4 5}))



count(), sum(), min(), max()
代数的: 引数値から代数的に求める関数

各引数値は分配的関数で算出

avg() min_N(),
avg(),
min N() standard_deviation()
standard deviation()
全体的: 結果を示すのに記憶域上の制限がない関数

E g median(),
E.g.,
median() mode(),
mode() rank()
ank()
Data Mining: Concepts and Techniques
37
ＤＷと概念階層

階層記述
day < {month}
d
{
th} <
quarter;
week < year

階層設定
{1..10} < inexpensive
Data Mining: Concepts and Techniques
38
デタウアウスとＯＬＡＰ
データウエアハウスとＯＬＡＰ

データウエアハウスとは?

多次元データモデル（データ操作）

データウエアハウスの構成

データウエアハウスシステム

データウエアハウスとデータマイニング
Data Mining: Concepts and Techniques
39
Data Cubeのブラウジング



Data Mining: Concepts and Techniques
視覚化
OLAP 機能
対話操作
40
代表的な O
OLAP 操作

Roll up
p (drill-up):
(
p) データの要約


階層を上昇、つまり次元縮小
Drill down (roll down): roll-up の逆

高水準要約から低水準要約（詳細）



Slice and dice: 射影と選択
Pivot (rotate):


つまり新たな次元の導入
Cube
b の方向付け,
方向付け視覚化,
視覚化 3D を2D
を平面に分解
分解
そのほか


drill
d
ill across: １つ以上の fact
f t ttable
bl を関連付け
drill through: 最低レベルデータと関係をＳＱＬで関連付け
Data Mining: Concepts and Techniques
41
o
s)
Toronto
Vancouver
Q1
395
605
loc
on
at i
un
(co
Q2
computer
home
entertainment
es)
tr i
USA
Canada
time
me (quarters)
at i
t ie
time
(quarters)
loc
ci
n(
item (types)
2000
Q1 1000
Q2
Q3
Q4
security
computer
home
phone
entertainment
dice for
(location = “Toronto” or “Vancouver”)
and (time = “Q1” or “Q2”) and
(item = “home entertainment” or “computer”)
item (types)
roll-up
on location
(from cities
to countries)
)
ies
Chicago 440
cit
(
New York
1560
on
i
t
Toronto
a
395
loc
time (quarters)
Vancouver
slice
for time = “Q1”
Q1
605
825
14
400
Q2
Q3
Q4
computer
security
phone
home
entertainment
drill-down
on time
(from quarters
to months)
locatio
ation (cities)
item (types)
Chicago
New York
Toronto
Vancouver
605
825
14
computer
home
entertainment
400
s)
Chicago
t ie
(ci New York
n
o
Toronto
i
at
security
phone
loc Vancouver
January
item (types)
150
100
150
February
March
April
home
entertainment
605
computer
825
time (months)
item (typ
types)
pivot
July
August
October
November
December
400
security
June
September
14
phone
May
computer
New York
Chicago
Vancouver
Toronto
location (cities)
Data Mining: Concepts and Techniques
home
entertainment
security
phone
item (types)
42
集約処理（１） Aggregates
• 日ごとの売上合計を求めよ
• SQL: SELECT date, sum(amt) FROM SALE
GROUP BY date
d t
sale
prodId
p1
p2
p1
p
p2
p1
p1
storeId
c1
c1
c3
c2
c1
c2
date
1
1
1
1
2
2
amt
12
11
50
8
44
4
ans
date
1
2
sum
81
48
43
集約処理（２） Aggregates
•日と製品ごとに売上合計を求めよ
日と製品ごとに売上合計を求めよ
• SQL: SELECT date, sum(amt) FROM SALE
GROUP BY date,
d t prodId
dId
sale
prodId
p1
p2
p1
p2
p
p1
p1
storeId
c1
c1
c3
c2
c1
c2
date
1
1
1
1
2
2
amt
12
11
50
8
44
4
sale
l
prodId
dId
p1
p2
p1
1
date
d
t
1
1
2
amtt
62
19
48
rollup
drill-down
drill
down
44
集約処理（３） Aggregates




集約関数
sum, count, max, min, median, ave
“Having” 条件
次元階層の利用
 average by region (店の平均)
 maximum by month (日の合計)
45
キュブ集約
キューブ集約
day 2
day 1
p1
p2 c1
p1
12
p2
11
p1
p2
c1
1
56
11
c1
44
c2
4
c2
c3
Sumsの計算
...
c3
50
8
c2
2
4
8
rollup
d ill d
drill-down
c3
3
50
sum
c1
67
c2
12
c3
50
129
p1
p2
sum
110
19
46
キュブ操作
キューブ操作
day 2
day 1
p1
p2 c1
p1
12
p2
11
p1
p2
c1
1
56
11
c1
44
c2
4
c2
c3
...
c3
50
sale(c1,*,*)
8
c2
2
4
8
c3
3
50
sale(c2,p2,*)
sum
c1
67
c2
12
c3
50
129
p1
p2
sum
110
19
sale(*,*,*)
47
キュブの拡張
キューブの拡張
c2
4
8
c312
p1
p2
c1
*
12
p1
p2
c1*
44
c1
56
11
c267
4
c2
44
c3
4
50
11
23
8
8
50
*
62
19
81
*
day 2
day 1
p1
p2
*
c3
50
* 50
48
48
*
110
19
129
sale(*,p2,*)
48
次元階層を用いた集約
day 2
day 1
p1
p2 c1
p
p1
12
p2
11
c1
44
c2
4
c2
c3
c3
50
8
customer
t
region
country
p1
p2
region A region B
56
54
11
8
(customer c1 in Region A;
customers c2, c3 in Region B)
•SQL: SELECT prodId, regionId, sum(amt) FROM SALE, REGION
WHERE SALE.storeId
SALE.storeId=REGION.storeId
REGION.storeId
GROUP BY prodId, regionId
49
ピボット処理 Pivoting
ク
ブ
ファクトテーブル：
sale
prodId storeId
p1
c1
p2
c1
p1
c3
p2
c2
p1
1
c1
1
p1
c2
date
1
1
1
1
2
2
次元の縮小
多次元キューブ：
amt
12
11
50
8
44
4
day 2
day 1
p1
p2 c1
p1
12
p2
11
p1
p2
c1
56
11
c1
44
c2
4
c2
c3
c3
50
8
c2
4
8
c3
50
50
DICE 操作
視点の選択
SELECT Time,Channel,Product
FROM Sales
ORDERED BY Time
51
SLICE 操作
断面の選択
SELECT * FROM sales
WHERE Time=2011Jan
52
Star-Net
Star
Net Query Model
Customer Orders
Shipping
pp g Method
Customer
CONTRACTS
AIR-EXPRESS
ORDER
TRUCK
PRODUCT LINE
Time
Product
ANNUALY QTRLY
DAILY
PRODUCT ITEM PRODUCT GROUP
CITY
SALES PERSON
COUNTRY
DISTRICT
REGION
Location
DIVISION
各円を footprint
Promotion
Data Mining: Concepts and Techniques
Organization
53
デタウアウスとＯＬＡＰ
データウエアハウスとＯＬＡＰ

データウエアハウスとは?

多次元データモデル

データウエアハウスの構成

データウエアハウスシステム

データウエアハウスとデータマイニング
Data Mining: Concepts and Techniques
54
ＤＷの設計: ビジネス分析のフレームワーク

ＤＷ設計の４つのビュー
ＤＷ設計の４つのビュ

Top-down ビュー


Data source ビュー


業務システムで処理格納管理されている情報の開示
業務システムで処理・格納・管理されている情報の開示
Data warehouse ビュー


ＤＷに必要な情報の選択
fact tables
tables、次元tables
次元tables
Business query ビュー

末端利用者ビ
末端利用者ビューからのＤＷデータの見え方
からのＤＷデタの見え方
Data Mining: Concepts and Techniques
55
Data
ata Warehouse
a e ouse 設計プ
設計プロセス
セス



アプローチ：次のいずれか、あるいは組み合わせ

Top-down: 全体設計・プランから開始 (十分な議論)

Bottom-up: 経験とプロトタイプの積み重ねから開始 (急ぐ時)
ソフト工学的な観点から

Waterfall: 次に進む前に各段階の構造的・体系的分析を完成

Spiral: 機能部分の増分的な開発、短時間TAT
典型的なＤＷ設計プロセス

対象となる business
b i
process を選ぶ (orders,
( d
invoices,
i
i
など)

処理の grain (対象データの最小単位・粒度) を選ぶ

Fact テーブルレコードの dimensions を選ぶ

Fact テーブルレコードを構築するための measure を選ぶ
Data Mining: Concepts and Techniques
56
データウエアハウス:
データウエアハウス
デ
タウエアハウス: Multiタウエアハウス:
Multi-Tiered Architecture
関連デ
ータ
業務DBs
業務
Monitor
&
Integrator
eg a o
Metadata
Extract
Transform
Load
Refresh
Data
Warehouse
OLAP Server
Serve
Analysis
Query
Reports
Data mining
Data Marts
データソース
記憶域
OLAP Engine ツール群
Data Mining: Concepts and Techniques
57
Data Warehouse モデル


Enterprise warehouse 全域ウ
全域ウエアハウス
アウス
 全組織に関連する情報を収集
Data Mart デ
データマート
タマト
 企業情報のうち特定の利用者に有用なデータ集合. グルー
プの特定は通常は自明（営業情報など）


ＤＷと独立か連動するか
Virtual warehouse 仮想ウエアハウス
 業務ＤＢ上のビュー集合
 要約的な内容（要約ビュー）だけが格納される
要約
容（要約
）
格納
Data Mining: Concepts and Techniques
58
質問と分析ツル
質問と分析ツール





質問の構築
レポートライタ (比較, グラフ,…)
表計算システム
Web インターフェイス
データ発見手法
59
質問と分析ツル（拡張）
質問と分析ツール（拡張）



時間関連処理
 e.g., 時間平均
導出属性
 e.g.,
g , commission = sales * rate
テキスト（文字列）検索
 e.g.,
e g “X”
X と “Y”
Y という語を含む文書を検索
 e.g., “X”, “Y”, “Z” という語の出現頻度ごとに文書
をランクつけせよ
60
D t W
Data
Warehouse
h
開発
Multi-Tier Data
Warehouse
分散
分散Data
Marts
Data
Mart
Data
Mart
Model refinement
企業ＤＷ
Model refinement
高水準企業データモデルの定義
Data Mining: Concepts and Techniques
61
ＤＷ Back
Back-End
End ツ
ツール群
ル群





データ抽出 Data extraction
 複数の異種外部ソースから所望データを抽出
データクリーニング Data cleaning
 エラーを検出し訂正・補正
を検
補
データ変換 Data transformation
 個々のデータ形式からＤＷ形式に変換
個々のデタ形式からＤＷ形式に変換
ロード Load
 ソート,
ソト要約,
要約統合,
統合ビュー構築,
ビュ構築整合性検査,
整合性検査索引構築・分
索引構築分
割
同期 Refresh
 データソースの変更をＤＷに伝搬
Data Mining: Concepts and Techniques
62
メタデータ辞書
メタデ
タ辞書 Metadata Repository

メタデータ Meta data


構造記述情報


ＤＷデータを定義するデータ:
スキーマ, ビュー,
ビ
次元, 階層, 導出データ定義,
デ
デ
データマートの内容・位
置
業務メタデータ

データ関連(変換データの履歴と変換経路), データ状況 (active,
archived,, purged),
p g ), 監視情報 ((利用率統計,, エラー報告,, 追跡))

要約処理のためのアルゴリズム

業務環境とＤＷとの対応関係

システム効率に関する情報

ビジネスデータ

用語定義, データ所有者, 変更方針
Data Mining: Concepts and Techniques
63
デタウアウスとＯＬＡＰ
データウエアハウスとＯＬＡＰ

データウエアハウスとは?

多次元データモデル

データウエアハウスの構成

データウエアハウスシステム

データウエアハウスとデータマイニング
Data Mining: Concepts and Techniques
64
OLAP サーバの構成

Relational OLAP (ROLAP)
(
)





DBMS Back-End 環境の最適化、DB の要約・検索、関連ツール・サー
ビスを含む
スケーラビリティ
Multidimensional OLAP (MOLAP)

配列方式の多次元記憶域管理機構

高速索引機構で、あらかじめ計算した要約情報を処理
Hybrid
y
OLAP ((HOLAP)) ((Microsoft SQLServerなど)
Q
)


関係ＤＢＭＳを用いてＤＷデータを格納・管理し、 OLAP ミドルウエアが
これを利用
柔軟性, 関係ＤＢと配列方式の組み合わせ
SQL サーバ拡張 (Redbricksなど)

特殊な SQL 質問支援, star/snowflake スキーマに特化
Data Mining: Concepts and Techniques
65
Data Cube の効率よい処理
効率
処

Data cube ： cuboids の束として

最下位： base cuboid

最上位 (apex)
(
) ：１ cellll


L レベル n-次元 cube のデータ数
data cube の構築・格納


n
T   ( L i  1)
i1
すべてを格納 (full materialization), すべてを動的に計算
(no materialization), or 一部を格納(partial
materialization)
格納範囲を選択

サイズ, 共有範囲, 頻度で
Data Mining: Concepts and Techniques
66
Cube 操作

定義と操作 (DMQL)
( Q )
define cube sales[item, city, year]: sum(sales_in_dollars)
compute
p
cube sales

SQL-like 言語(cube by, Gray et al.’96)
()
SELECT item, city, year, SUM (amount)
FROM SALES

(city)
CUBE BY item,
item city,
city year
計算処理(Group-By)
(date, product, customer),
(date,product),(date, customer),
(product, customer),
(d t ) (product),
(date),
( d t) (customer)
( t
)
(city, item)
Data Mining: Concepts and Techniques
(item)
(city, year)
(year)
(item, year)
(city, item, year)
67
デタウエアハウスシステムの実現
データウエアハウスシステムの実現



監視 Integrating: ローディング、クリーニング,...
デ
グ
グ
処理 Processing
g: 質問処理,, 索引つけ,, ...
管理 Managing: メタデータ, 設計, ...
68
監視



ソース種別:
関係, デ
データファイル,
タファイル, IMS,, VSAM,, IDMS,, WWW,, news-wire,, …
差分的vs. リフレッシュ
custom er
id
53
81
111
nam e
joe
fred
sally
address
10 main
12 main
80 willow
city
sfo
sfo
la
new
69
監視手法








周期的なスナップショット
デタベ
データベーストリガ
トリガ
ログデータの伝播
データの伝播 (重複サービス)
トランザクションの伝播
ポーリング (ソースサイトへの問いかけ)
仮面の剥ぎ取り (screen
(
scraping)
i )
応用レベルでの監視
70
監視手法の問題




頻度
度
 周期的: 毎日,
, 毎週,, …
 トリガ: on “大きな変更”, 多数の変更, ...
データ変換
デ
タ変換
 統一形式に変換
 項目の追加削除変更
追加削除変 (e.g., 履歴に日付を加える)
標準化 (e.g., ODBC)
ゲートウエイ
71
デタの統合
データの統合



データクリーニング
デ
グ
データローディング
導出データ
Client
Client
Query & Analysis
Metadata
Warehouse
Integration
S
Source
Source
Source
72
デタクリニング
データクリーニング



マイグレーション (e.g., 円  ユーロ)
現実への適用:
現実
適用応用分野知識の利用
用分野知識利用 ((e.g.,
g , SSN))
統合 fusion (e.g., メールリスト, 顧客統合)
billing DB
service DB

customer1(Joe)
merged customer(Joe
merged_customer(Joe
customer2(Joe)
追跡: 規則や関連の発見(データ発見と類似)
73
デタの格納
データの格納




差分アプローチ vs.
vs リフレッシュ
Off-line vs. on-line
ローディングの頻度
 毎夜,
, 毎週、毎月,, 絶え間なく
並列/分割
74
導出デタ
導出データ


導出情報（２次情報）
 索引
 集約値
 materialized views (後述)
(
)
導出データの修正
 差分 vs.
vs リフレッシュ
75
ウエアハウス処理



管理情報とメタデータ
何を Materialize?
ROLAP サーバ vs. MOLAP サーバ
Cli t
Client
Client
Query & Analysis
Metadata
Warehouse
Integration
Source
Source
Source
76
管理



メタデータ
デ
ウエアハウス設計
ツール
Client
Client
Query & Analysis
Metadata
W h
Warehouse
Integration
Source
Source
Source
77
メタデータ
メタデ
タ Metadata

管理情報
 ソース・ツールの定義 ...
 スキーマ,次元階層, …
 データ獲得規則,
, クリーニング,, …
 リフレッシュ, 方針の遂行
 利用者プロファイル,
利用者プロファイルアクセス権,
アクセス権 ...
78
メタデタ
メタデータ


ビジネス
 用語 & 処理定義
 データ所有, 費用
操作
 データ系統
 データ状態(e.g.,
データ状態(e g active
active, archived
archived, purged)
 統計, エラーレポート, 追跡調査
79
Materialized Views

sale
l
SQL 式を用いて新たなウエアハウスデータを生成
prodId
dId
p1
p2
p1
p2
p1
p1
storeId
Id
c1
c1
c3
c2
c1
c2
joinTb
date
d
1
1
1
1
2
2
prodId
p1
p2
p1
p2
p1
p1
amt
12
11
50
8
44
4
name
bolt
nut
bolt
nut
bolt
bolt
product
price
10
5
10
5
10
10
storeId
c1
c1
c3
c2
c1
c2
date
1
1
1
1
2
2
id
p1
p2
amt
12
11
50
8
44
4
nam e price
bolt
10
nut
5
どこにもこのような
データは無い
80
何を Materialize すべきか

頻出する質問に対する結果を格納
day 2
day 1
p1
p2 c1
p1
12
p2
11
p1
p2
materialize
c1
56
11
c1
44
c2
4
c2
total sales
c3
...
c3
50
8
c2
4
8
c3
50
p1
c1
67
c2
12
c3
50
129
p1
p
p2
c1
110
19
81
Materialize のための条件




質問の種類/頻度
応答時間
記憶域のコスト
更新のコスト/頻度
/
82
ROLAP サ
サーバ
バ

sale
Relational OLAP サーバ
prodId
p1
p2
p1
date
1
1
2
sum
62
19
48
ツール
サービス機能
サ
ビス機能
ROLAP
サーバ
バ
専用索引, チューニング
非正規化されたスキーマ
非正規化されたスキ
マ
関係データベース
関係デ
タベス
システム
83
MOLAP サ
サーバ
バ
Multi-Dimensional OLAP サーバ
Sales
B
A
多次元ツール
Product

milk
soda
eggs
soap
1
サビス機能
サービス機能
多次元処
理サーバ
2 3 4
Date
関係DBMS
でも実現可能
84
Iceberg Cube

集約条件を満たすセルだけを処理したい
HAVING COUNT(*)
COUNT( ) >= minsup

背景
 通常対象となるデータセルはごく一部
 興味ある部分だけを探索対象としたい

100 次元の base cell 1 つしかないデータに対して、count >= 1 以
上の集約データはいくつあるか?
Data Mining: Concepts and Techniques
85
OLAP デ
データの索引つけ:
タの索引つけ: Bitmap Index





特定の列の索引つけ
各値にビットベクトルを対応
ベクトル長: base table のレコード数
i-th bit = “1” ⇔ i-th 行データが索引データを含む
行デタが索デタを含む
領域データが大きいと効率低下
Base table
Cust
C1
C2
C3
C4
C5
Region
Asia
Europe
Asia
America
Europe
索引(Region)
索引(Type)
Type RecID Asia Europe Am erica RecID Retail Dealer
Retail
1
1
0
1
1
0
0
Dealer 2
0
1
0
2
0
1
Dealer 3
1
0
0
3
0
1
Retail
4
0
0
1
4
1
0
0
1
0
5
0
1
Dealer 5
Data Mining: Concepts and Techniques
86
OLAP データの索引つけ: Join Index




Join index:
JI(R-id, S-id) where R (R-id, …)  S (S-id, …)
索引により、キー値とレコードid の対応つけ
関係数 JOIN 結果を JI ファイルに予め作成
関係代数
め作成
join index により次元値と fact table行を対応.
fact table: Sales on city Ｘ product
 city 上の JOIN INDEX で Sales レコード id
と対応
 多次元索引でもよい
Data Mining: Concepts and Techniques
87
OLAP 質問処理


どの操作が妥当か？

drill, roll などを SQL / OLAP 命令に変換

dice = selection + projection
OLAP 操作に必要な格納キューブが利用できるか？
項目 {brand, p
province_or_state} 上で “year
y
= 2004” を満たすものを検索

ここで格納されたcuboids が４種あり、どれを使うべきか?
1)) {year,
{y , item_name,
_
, city}
y}
2) {year, brand, country}
3) {year,
{y a , brand,
b a d, province
po
_o
or_state}
a }
4) {item_name, province_or_state} where year = 2004

索引構造を調べ、密構造・疎配列で判断
索引構造を調
、密構造疎配列で判断
Data Mining: Concepts and Techniques
88
Essbase (Hyperion)


multidimensional database platform
 analytic applications
Essbase (Extended Spread Sheet dataBASE)
 a p
product of Arbor Software
 merged with Hyperion Software in 1998
 Oracle Corporation acquired Hyperion Solutions
Corporation in 2007
"Oracle
Oracle Essbase
Essbase“ in 2009

IBM “DB2 OLAP Server” until late 2005
デタウアウスとＯＬＡＰ
データウエアハウスとＯＬＡＰ

データウエアハウスとは?

多次元データモデル

データウエアハウスの構成

データウエアハウスシステム

データウエアハウスとデータマイニング
Data Mining: Concepts and Techniques
91
Data
ata Warehouse
a e ouse 利用

ＤＷの応用分野

情報処理 nformation processing



質問、統計分析、レポ
質問
統計分析レポート作成
ト作成。統計表（クロス集計）,
統計表（クロス集計）チャ
チャート・グ
トグ
ラフ作成
分析処理 Analytical
分析処
y
p
processing
g

多次元データ分析

OLAP 処
処理,, slice-dice,, drilling,
g, pivoting
p
g
データマイニング Data mining

隠れたパターンからの知識獲得
識獲

同時関係・解析モデル構築。分類予測・クラスタリング・視覚化
Data Mining: Concepts and Techniques
92
On-Line Analytical Processing (OLAP) と
O Line
On
Li Analytical
A l ti l Mining
Mi i (OLAM)

OLAM の必要性
 ＤＷデータは高品質：統合された無矛盾なデータ
 ＤＷ環境
 ODBC, OLEDB, Web accessing, 関連サービス機能,
レポート作成機能
レポ
ト作成機能, OLAP tools
 OLAP-based データ分析
 操作：drilling,
操作：drilling dicing,
dicing pivoting,
pivoting etc.
etc
 ＤＭ機能に必要なオンラインデータ選択
Data Mining: Concepts and Techniques
93
An OLAM System Architecture
データマイニング質問
結果
利用者インター
フェイス
イ
User GUI API
OLAM
Engine
Layer4
OLAP
Engine
Layer3
OLAP/OLAM
Data Cube API
Layer2
MDDB
MDDB
Meta Data
Filtering&Integration
Database API
Filtering
Layer1
D t cleaning
Data
l i
Databases
Data
D
t
Data integration Warehouse
Data Mining: Concepts and Techniques
データ倉庫
94
要約: Data Warehouse と OLAP 技術

ＤＷの必要性

多次元モデル

Star スキーマ, snowflake スキーマ, fact constellations

data cube ：fact table + 次元/measures

OLAP 操作: drilling, rolling, slicing, dicing, pivoting

Data warehouse システムの構成

OLAP システム: ROLAP, MOLAP, HOLAP

data cubes 操作の効率化


格納(materialization) Partial vs. full vs. none

OALP dataの索引: Bitmap index, Join index

OLAP 質問処理
OLAP と OLAM (on-line
( li analytical
l ti l mining)
i i )
Data Mining: Concepts and Techniques
95
References (I)









S. Agarwal, R. Agrawal, P. M. Deshpande, A. Gupta, J. F. Naughton, R. Ramakrishnan,
and S. Sarawagi. On the computation of multidimensional aggregates. VLDB’96
D. Agrawal, A. E. Abbadi, A. Singh, and T. Yurek. Efficient view maintenance in data
warehouses. SIGMOD’97
R. Agrawal, A. Gupta, and S. Sarawagi. Modeling multidimensional databases. ICDE’97
S. Chaudhuri and U. Dayal. An overview of data warehousing and OLAP technology.
ACM SIGMOD Record, 26:65-74, 1997
E. F. Codd, S. B. Codd, and C. T. Salley. Beyond decision support. Computer World, 27,
July 1993.
J. Gray,
y, et al. Data cube: A relational aggregation
gg g
operator
p
generalizing
g
g group-by,
g p y,
cross-tab and sub-totals. Data Mining and Knowledge Discovery, 1:29-54, 1997.
A. Gupta and I. S. Mumick. Materialized Views: Techniques, Implementations, and
Applications. MIT Press, 1999.
J. Han. Towards on-line analytical mining in large databases. ACM SIGMOD Record,
27:97-107, 1998.
V. Harinarayan,
V
Harinarayan A.
A Rajaraman,
Rajaraman and J.
J D.
D Ullman.
Ullman Implementing data cubes efficiently.
efficiently
SIGMOD’96
Data Mining: Concepts and Techniques
96
References (II)









C. Imhoff, N. Galemmo, and J. G. Geiger. Mastering Data Warehouse Design: Relational
and Dimensional Techniques. John Wiley, 2003
W. H. Inmon. Building the Data Warehouse. John Wiley, 1996
R. Kimball and M. Ross. The Data Warehouse Toolkit: The Complete Guide to
Dimensional Modeling. 2ed. John Wiley, 2002
P. O'Neil and D. Quass. Improved query performance with variant indexes. SIGMOD'97
Microsoft. OLEDB for OLAP p
programmer's
g
reference version 1.0. In
http://www.microsoft.com/data/oledb/olap, 1998
A. Shoshani. OLAP and statistical databases: Similarities and differences. PODS’00.
S. Sarawagi and M.
S
M Stonebraker.
Stonebraker Efficient organization of large multidimensional arrays.
arrays
ICDE'94
OLAP council. MDAPI specification version 2.0. In
http://www olapcouncil org/research/apily htm 1998
http://www.olapcouncil.org/research/apily.htm,
E. Thomsen. OLAP Solutions: Building Multidimensional Information Systems. John Wiley,
1997

P Valduriez
P.
Valduriez. Join indices.
indices ACM Trans.
Trans Database Systems,
Systems 12:218-246,
12:218 246 1987.
1987

J. Widom. Research problems in data warehousing. CIKM’95.
Data Mining: Concepts and Techniques
97

Download Report