理学系研究科 情報科学専攻
データベース特論 II
１０：１５－１２：１５
新領域創成科学研究科 複雑理工学専攻
複雑計算論
１０：１５－１１：５５
オリエンテーション
森下 真一
データマイニング
• 理論
• アルゴリズム
• 実装
• 応用
市場のニーズ
大規模生データの存在
数ギガ～テラの生データ
•ＰＯＳデータ
•顧客データ
•受注データ 等
検索可能状態
（大福帳システム
Data Warehouse）
•検索･集計･チャート化
•経験的ルールの検証
ルールの収集･発見
技術的シーズ
データ読取装置の普及
•バーコード
•クレジットカード
•ＯＣＲ
記憶装置の低価格化
プロセッサーの高速化
並列計算機の商用化
関係ＤＢの普及
多次元的問合せ OLAP
知識発見技術の高速化
（データマイニング）
•商品間関連 •ゲノム情報
•危険度分析 •検索エンジン
•顧客分類
•発見科学
• データベース問合せ最適化
• 組合せ論的アルゴリズム
• 並列処理
Association Rules
当座取引有無
結合ルール
定期口座有無
血液型
職業コード
カードローン延滞有無
Ｘ⇒Ｙ
定期口座有無＝Ｎｏ ⇒ カードローン延滞有無＝Ｙｅｓ
サポート
Ｐｒ(XかつY)
例 ５％
確信度
Ｐｒ(Y|X)
例 ３２％
閾値を設け、上回るルールを “interesting” と考える
Interesting Rules を枚挙したい
観察
B ⇒ C が interesting
Ｐｒ(BC) は閾値以上
Ｐｒ(B) と Ｐｒ(C) も閾値以上
成功例
• オーストラリア健康保険委員会
年間 数千万ドルの節約に成功
• 開業医が不必要な処方箋を出す
ケースを見つけ出す規則の発見
HIC Provides A Healthier Future With IBM
IBM data warehousing and data mining technologies are
enabling the Health Insurance Commission (HIC) to save
the Australian healthcare systems tens of millions of
dollars a year.
The HIC is a Federal Government agency which processes
claims for Medicare, Medibank Private and the
Pharmaceutical Benefits and Child Care Programs. Every
year, it deals with 300 million transactions and pays out
eight billion dollars worth of funds.
Healthcare systems around the world are attempting to
find ways to reduce the millions of taxpayers' dollars which
are wasted by fraud and the inappropriate use of medical
tests and services.
The HIC, together with IBM has implemented a worldleading data mining solution, which analyzes data and
detects unnecessary prescriptions or referrals by medical
practitioners then intervene to reduce the incidence.
http://www.software.ibm.com/data/intelli-mine/applbrief.html
ABCD
ABC
AB
ABD
ACD
まずサポートが閾値以上の条件集合
（大きい条件集合）を枚挙
BCD
AC
BC
AD
BD
A
B
C
D
CD
φ
条件集合｛A,B,C｝ を ＡＢＣ と簡略に記述
条件数が少ない集合から徐々に
サポートを計算
ABCD
ABC
AB
ABD
まずサポートが閾値以上の条件集合
（大きい条件集合）を枚挙
ACD
BCD
AC
BC
AD
BD
A
B
C
D
CD
条件数が少ない集合から徐々に
サポートを計算
枝狩り：
Ｐｒ(AB) < 閾値 ⇒ Ｐｒ(ABC) < 閾値
ルール B ⇒ C は確信度
Ｐｒ（Ｃ|Ｂ）＝Ｐｒ(BC)／ Ｐｒ(B)
A
ＡＢ
φ
Ｐｒ（Ａ）≧閾値
Ｐｒ（ＡＢ）＜閾値
が閾値以上のとき生成
サポート計算の効率化
大きい条件集合の候補を枚挙
ABC
ABD
AB
ABE
AC
AD
ACD
AE
ACE
BC
ADE
BD
BCD
BE
CD
BCE
BDE
CE
各レコードが満たす条件集合を見つけ、サポートを増加
ACDE
DE
CDE
サポート計算の効率化
大きい条件集合の候補を枚挙
ABC
ABD
AB
ABE
AC
ACD
AD
ACE
AE
ADE
BC
BD
BCD
BE
BCE
CD
BDE
CE
各レコードが満たす条件集合を見つけ、サポートを増加
ACDE
A
Hash table
B
D
ABD
B
E
D
C
ADE
ABE
BCE
D
BDE
DE
CDE
サポート計算の効率化
大きい条件集合の候補を枚挙
ABC
ABD
AB
ABE
AC
ACD
AD
ACE
AE
ADE
BC
BD
BCD
BE
BCE
CD
BDE
CE
各レコードが満たす条件集合を見つけ、サポートを増加
ACDE
A
Hash table
B
D
ABD
B
E
D
C
ADE
ABE
BCE
D
BDE
DE
CDE
サポート計算の効率化
大きい条件集合の候補を枚挙
ABC
ABD
AB
ABE
AC
ACD
AD
ACE
AE
ADE
BC
BD
BCD
BE
BCE
CD
BDE
CE
各レコードが満たす条件集合を見つけ、サポートを増加
ABDE
A
Hash table
B
D
ABD
B
E
D
C
ADE
ABE
BCE
D
BDE
DE
CDE
条件集合の枝狩りの効率化
データベースの走査回数を
減らせないか？
ABCD
ABC
AB
ABD
ACD
BCD
AC
BC
AD
BD
A
B
C
D
φ
CD
例 サポートの
閾値が５％のとき
条件集合の枝狩りの効率化
ABCD
ABC
AB
ABD
ACD
BCD
AC
BC
AD
BD
A
B
C
D
CD
φ
A
A
A
A
落選
出馬
当確
当選
サイズ１の
条件集合の
計算を開始
ABCD
ABC
AB
ABD
ACD
BCD
AC
BC
AD
BD
A
B
C
D
CD
サイズ２
を開始
読込済
φ
A
A
A
A
落選
出馬
当確
当選
サイズ１の
条件集合の
計算を開始
ABCD
ABC
AB
AC
ABD
BC
ACD
AD
BCD
BD
サイズ３
を開始
CD
読込済
A
B
C
サイズ２
を開始
D
φ
A
A
A
A
落選
出馬
当確
当選
ABCD
ABC
AB
ABD
サイズ１の
サポート計算
終了
ACD
BCD
AC
BC
AD
BD
A
B
C
D
CD
サイズ３
を開始
読込済
サイズ２
を開始
φ
A
A
A
A
落選
出馬
当確
当選
サイズ１の
サポート計算
終了
ABCD
ABC
AB
ABD
ACD
BCD
AC
BC
AD
BD
A
B
C
D
CD
第
１
回
読
込
済
サイズ３
も開始
読
込
済
φ
A
A
A
A
落選
出馬
当確
当選
サイズ２の
計算終了
サイズ１の
条件集合の
サポート計算
を開始
A priori に比べ ２０％から４倍の性能向上との報告されている
ABCD
ABC
AB
AC
A
ABD
BC
サイズ１の
サポート計算
終了
ACD
AD
B
C
BCD
BD
CD
D
φ
A
A
A
A
落選
出馬
当確
当選
第
１
回
読
込
済
サイズ３の
計算終了
読
込
済
サイズ２の
計算終了
サイズ１の
条件集合の
サポート計算
を開始
預金残高∈Ｒ ⇒ クレジットカード＝Yes
預金残高
Ｐｒ（預金残高∈Ｒ ）≧１０％で
確信度最大
少しでも精度を上げたい
預金残高∈Ｒ ⇒ クレジットカード＝Yes
預金残高
Ｐｒ（預金残高∈Ｒ ）≧１０％で
確信度最大
確信度８０％以上で
Ｐｒ（預金残高∈Ｒ ）最大
少しでも精度を上げたい
預金残高∈Ｒ ⇒ クレジットカード＝Yes
入力： Ｐｒ(預金残高∈Ｒ) の閾値
出力： 確信度を最大化する区間 Ｒ
預金残高 X → （ Ｐｒ(預金残高≦Ｘ) ，
Ｐｒ(｛預金残高≦Ｘ，クレジットカード＝Yes｝)
確信度
閾値
預金残高∈Ｒ ⇒ クレジットカード＝Yes
入力： Ｐｒ(預金残高∈Ｒ) の閾値
出力： 確信度を最大化する区間 Ｒ
預金残高 X → （ Ｐｒ(預金残高≦Ｘ) ，
Ｐｒ(｛預金残高≦Ｘ，クレジットカード＝Yes｝)
O(M log M)
M: number of records
確信度
Ｒ の候補
Clockwise Search
Counter Clockwise Search
Clockwise, Counter Clockwise
はともに、点を高々１回だけ走査
する
（年齢,預金残高）∈Ｓ ⇒ カードローン延滞＝Yes
預金残高
年齢
（年齢,預金残高）∈Ｓ ⇒ カードローン延滞＝Yes
預金残高
年齢
（年齢,預金残高）∈Ｓ ⇒ カードローン延滞＝Yes
預金残高
年齢
（年齢,預金残高）∈Ｓ ⇒ カードローン延滞＝Yes
預金残高
年齢
領域族
矩形領域
Ｘ単調領域
直交凸領域
p( (年齢,預金残高)∈Ｓ ) を「領域Ｓのサポート」
最大確信度領域 閾値以上のサポートをもち、確信度を最大にする領域Ｓ
最大サポート領域 閾値以上の確信度を導き、サポートを最大にする領域Ｓ
（年齢,預金残高）∈ Ｓ
⇒ カードローン延滞＝Yes
領域族：矩形領域
最大サポート・最大確信度領域を O(n1.5)
で計算可能
預
金
残
高
年齢
グリッド領域へ
データ数 M, ピクセル数 n
領域族：X単調領域または直交凸領域
最大サポート・最大確信度領域を
X単調はO(n M)、直交凸はO(n 1.5 M) で
計算可能。
n と log M の多項式時間で計算すること
は P = NP でない限り不可能。
近似アルゴリズム
（年齢,預金残高）∈ Ｓ
Ｓ
⇒ カードローン延滞＝Yes
p( {年齢,預金残高）∈Ｓ,
カードローン延滞＝Yes} )
確信度
p(（年齢,預金残高）∈Ｓ)
（年齢,預金残高）∈ Ｓ
Ｓ
⇒ カードローン延滞＝Yes
p( {年齢,預金残高）∈Ｓ,
カードローン延滞＝Yes} )
近似解
確信度
サポート値の閾値
p(（年齢,預金残高）∈Ｓ)
Hand Probing による解の探索
１
凸閉包上の探索
３
２
確信度
サポート値の閾値
１回の hand probing のコスト
Ｘ単調領域
Ｏ(ｎ)
直交凸領域
Ｏ(ｎ1.5)
hand probing の回数はＯ(log Ｍ)
ｙ =θｘ ＋ a
切片 ａ の最大化
• 各ピクセルに実数で表現される濃度
• 濃度の和を最大化する領域を計算
ルールの評価 － 領域族別、メッシュ粒度別
矩形領域
#(pixels)
Training
Test
Test – Tra.
8×8
47.77%
46.92%
-0.85%
16×16
48.22%
47.66%
-0.56%
32×32
48.30%
47.52%
-0.78%
64×64
48.42%
47.03%
-1.39%
Ｘ単調領域
#(pixels)
Training
Test
Test – Tra.
8×8
52.70%
51.38%
-1.31%
16×16
53.72%
51.76%
-1.95%
32×32
55.24%
51.69%
-3.55%
64×64
57.47%
51.00%
-6.46%
直交凸領域
データを平面中に一様に生成
ガードローン延滞となる確率を
対角線からの距離に関して一様分布
#(pixels)
Training
Test
Test – Tra.
8×8
52.70%
51.56%
-1.14%
16×16
53.49%
52.24%
-1.25%
32×32
53.96%
51.79%
-2.17%
64×64
54.43%
51.75%
-2.67%
10-fold Cross Validation
Classification
入力データ例
血圧
心拍数
決定木
健康な人と心臓疾患の患者のデータ
中性脂肪
肥満度
ＧＰＴ
ＧＯＴ
心臓疾患
入力データ例
決定木
健康な人と心臓疾患の患者のデータ
血圧 ＜ 125
Yes
Yes
No
No
領域分割
ＧＰＴ
Yes
訓練データで木を生成
評価基準： 未知データでの予測精度
動機： 領域分割は予測精度向上に効くか？
No
血圧
決定木 データ分割の評価方法
正のデータ
負のデータ
決定木 データ分割の評価方法
Ｑｕｉｎｌａｎのエントロピー
最小化
正のデータ
負のデータ
n
Ent1=
- (p log p + q log q)
Ent2
n1
n2
ｐ ｑ
n1
n2
Ent1 +
Ent2
n
n
Ｓ
エントロピー関数は凸関数
エントロピー最小の領域は
凸包の境界上に存在
Ｓ中の正の
データ数
Hand Probing で探索
単純な二分探索は困難
（凸包上の全ての点の
エントロピーが一致する例）
Ｓ中のデータ数
Ｅｎｔ（三角形ＸＹＺ内の任意の点）
≧ ｍｉｎ（Ｅｎｔ（Ｘ），Ｅｎｔ（Ｙ），ＥＮＴ（Ｚ））
Ｚ
Y
X
もし Ｅｎｔ（Ｚ）≧ 現時点の最小エントロピー ならば枝狩り
Ｂｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ Ｓｅａｒｃｈ
実用上はほぼ、Ｏ（ｌｏｇＭ）のＨａｎｄ Ｐｒｏｂｉｎｇ
決定木性能評価
ＵＣ Irvine, Ｒｅｐｏｓｉｔｏｒｙ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ ｄａｔａｂａｓｅｓ
http://www.ics.uci.edu/~mlearn/MLRepository.html
10-fold Cross Validation
データベース
balance scale
breast-cancer-wisc
german credit
liver disorder
pima diabetes
segmentation
vehicle
waveform
waveform+noise
ﾚｺｰﾄﾞ数
625
699
1000
345
768
2310
846
5000
5000
属性数
4
9
24
6
8
19
18
20
40
ｸﾗｽ数
3
2
2
2
2
7
4
3
3
Ｘ単調
15.52
5.01
27.30
34.81
24.47
4.81
30.02
21.74
22.54
エラー率
直交凸
15.52
4.15
23.80
33.36
25.12
4.37
28.47
20.98
21.32
矩形
19.34
4.58
26.90
31.08
23.69
4.89
27.65
22.36
22.94
二分割
20.95
5.72
25.60
34.87
26.82
4.50
26.23
22.74
24.36
回帰木 (Regression Tree)
ＢＰＳ
ＧＤＭ
ＹＥＮ
1.443530 0.407460 0.004980
1.446120 0.408050 0.004950
:
:
:
ＴＢ３Ｍ
ＴＢ３０Ｙ
SP500
GOLD
7.02
7.04
:
9.31
9.28
:
210.88
205.96
:
326.00
339.45
:
Ｙｅｓ
Ｎｏ
Ｎｏ
Ｙｅｓ
Ｄ１
領域中
外
μ１
Ｄ２
μ２
誤差二乗平均を最小化する領域
Ａ
μ
Ｄ１
外
領域中
Ｄ２
μ１
誤差二乗平均の
最小化
クラス間分散の
最大化
μ２
Σ ｔ∈Ｄ （ｔ[Ａ]－μ
１
２ ＋
）
１
Σ ｔ∈Ｄ （ｔ[Ａ]－μ
２
２
）
２
| Ｄ１∪Ｄ２ |
| Ｄ１ |（ μ －μ１ ）２ ＋｜Ｄ２ |（ μ －μ２ ）２
| Ｄ１∪Ｄ２ |
Ｓ
クラス間分散関数は凸関数
クラス間分散最大の領域は
凸包の境界上に存在
Ｓ中データ
の目標属性
の値の和
Hand Probing で探索
単純な二分探索は困難
Ｂｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ Ｓｅａｒｃｈ
で実用上はＯ（ｌｏｇ Ｍ）
Ｓ中のデータ数
回帰木性能評価
http://www.cs.utoronto.ca/~delve/data/datasets.html
10-fold Cross Validation
データベース
add10
abalone
kin-8fh
kin-8fm
kin-8nh
kin-8nm
pumadyn-kin-8fh
pumadyn-kin-8fh
pumadyn-kin-8fh
pumadyn-kin-8fh
ﾚｺｰﾄﾞ数
9792
4177
8192
8192
8192
8192
8192
8192
8192
8192
属性数
10
8
8
8
8
8
8
8
8
8
誤差二乗平均（予測前と後の比）
Ｘ単調
直交凸
矩形
二分割
0.141
0.123
0.156
0.185
0.521
0.515
0.534
0.539
0.447
0.433
0.459
0.479
0.225
0.197
0.257
0.249
0.649
0.618
0.619
0.655
0.494
0.449
0.478
0.541
0.412
0.402
0.409
0.410
0.0604
0.0595
0.0653
0.0632
0.347
0.337
0.353
0.355
0.0530
0.0496
0.0550
0.0535
OLETF
インシュリン非依存型糖
尿病モデルラット
F344
正常のモデルラット
何世代か
交配後のラット
Intercross
Marker(1) = OLETF ホモ接合
Marker(2) = F344 ホモ接合
Marker(3) = OLETF / F344 ヘテロ接合
遺伝子型 (3×102列)
マーカー接合状態
個体
102
｜
103
個
表現型
血糖値, 疾患,
遺伝子型 (102～107列)
遺伝子発現量, SNP, ...
個体
102
｜
104
個
表現型
血糖値, 疾患,
遺伝子発現量,
薬の効果,
副作用, ...
Clustering
Expression Patterns of Genes in Various Tissues
tissues in organs
Identifier
MB00001
MB00002
MB00004
MB00005
MB00006
MB00007
MB00009
MB00010
brain heart lung kidney testis
17.3 32.8 5.0 22.7 22.2
46.5 15.2 5.0 19.0 14.3
11.5 55.2 4.5 26.5 2.3
15.1 36.0 17.8 22.9 8.2
61.9 21.6 7.9 4.6 4.0
27.0 27.3 15.3 14.8 15.6
0.0 0.0 100.0 0.0 0.0
82.9 17.1 0.0 0.0 0.0
Brain in embryo
chronological expression patterns in all tisuues in brain
tissues in brain
embryo
post-natal
10.5d. 13.5d. 17.5d. 1 d. 5 d. 7 d. 14 d. 21 d. 91 d. olfact hippo cortex corpus cereb.
5.6 8.9 11.2 9.5 12.7 12.3 8.4 12.0 6.7 38.5 33.2 9.4 5.7 13.2
5.4 7.2 7.0 10.7 12.5 10.3 10.0 15.4 8.9 42.5 20.2 11.5 4.7 21.1
5.9 8.8 8.5 10.3 10.9 9.1 8.1 15.0 12.6 58.5 14.8 9.6 4.8 12.3
9.7 11.5 7.3 12.4 13.0 10.9 6.7 10.5 5.0 32.3 18.3 5.6 16.1 27.6
2.9 13.4 10.3 11.7 10.1 13.1 10.3 10.0 8.4 45.9 29.1 4.3 9.4 11.3
4.9 7.7 3.0 10.6 13.6 10.8 13.7 12.9 9.4 20.7 19.0 15.0 27.9 17.3
0.0 4.8 7.4 7.5 7.3 17.4 10.1 24.1 14.2 0.0 100.0 0.0 0.0 0.0
0.0 5.1 8.2 16.5 18.8 16.8 5.1 6.8 3.9 41.4 15.5 15.2 0.0 27.9
Five brain tissues of adult mouse
Clustering genes via expression patterns is promising.
• A set of genes are expected to share common roles
in cellular processes.
• Genes in the same group would be observed
in the same tissue at the same time.
• Their expression patterns would be similar.
• Clustering genes by expression patterns would provide
substantial insight on real groups of genes.
Graphical Representation of Expression Patterns
Before
Clustering
After
Clustering
Cluster of genes coding
ribosomal proteins
Clusters of genes coding
myelin
Tightness of a cluster C of points
diameter
max{ || x – y || | x and y are points in C }
intra-class variance (1 / |C| ) S x in C || x – c(C) ||2
|C|
number of points in C
c(C) centroid (mean) of C, S x in C x
k-clustering of a set S of points
a partition of S into k disjoint nonempty subsets
(clusters) C1, …, Ck
Optimization criteria
Minimizing the maximum value of diameters or
intra-class variances of all clusters
Diameter Problem
• NP-hard if k is treated as a variable
• Approximation within a factor a of the optimal diameter
is NP-hard for a < 2.
• Approximation factor of 2 is achieved by
furthest point heuristic in O(n k)-time.
(n = number of points)
• O(n log k)-time version
Diameter1
Intra-class variance1
=
>>
Diameter2
Intra-class variance2
Intra-class Variance Problem
• O(n (d+2)k+1 )-time algorithm (d = number of dimensions)
• O(n(1/e)d )-time e-approximate 2-clustering algorithm
Problems of k-clustering
• It is hard to guess an appropriate value for k, beforehand.
• It is not easy to avoid generating a false-positive cluster of large
intra-class variance that may contain genes of different functions.
Our Approach
• Perform hierarchical clustering by e-approximate 2-clustering.
• Stop dividing a cluster if its intra-class variance is
no more than a given threshold.
Cluster of genes coding
ribosomal proteins
Clusters of genes coding
myelin
intra-class variance =209
intra-class variance = 128
講義の予定
結合ルールマイニング
• Apriori
• Dynamic Itemset Counting
• 最適区間
• 最適領域
• Correlation
情報科学的手法
２次記憶管理
主記憶管理 ハッシング
最悪計算量
NP完全 NP困難
動的計画法
凸包探索
分類問題 / 決定木 / 回帰木
• C4.5
• CART
• 最適部分集合
• NP-hardness / Parallel Search
• Optimized Ranges / Regions
• Boosting / Bagging / Weighted Majority
情報科学的方法
NP困難
分岐限定法
並列化
検索エンジン
• キーワード検索
• リンク情報の利用 Google / Clever
• 検索エンジンの動向
Clustering / Nearest Neighborhood
• k-means / k-clustering
情報科学的手法
近似アルゴリズム
グラフアルゴリズム
© Copyright 2024 ExpyDoc
