理学系研究科　情報科学専攻 データベース特論 II １０：１５－１２：１５ 新領域創成科学研究科　複雑理工学専攻 複雑計算論 １０：１５－１１：５５ オリエンテーション 森下　真一

データマイニング 　理論 　アルゴリズム 　実装 　応用

市場のニーズ 技術的シーズ 大規模生データの存在 データ読取装置の普及 記憶装置の低価格化 検索可能状態 プロセッサーの高速化 数ギガ～テラの生データ ＰＯＳデータ 顧客データ 受注データ　等 データ読取装置の普及 バーコード クレジットカード ＯＣＲ 記憶装置の低価格化 検索可能状態 　（大福帳システム　 　　Data Warehouse） プロセッサーの高速化 並列計算機の商用化 関係ＤＢの普及 多次元的問合せ OLAP 検索･集計･チャート化 経験的ルールの検証 ルールの収集･発見 （データマイニング） 知識発見技術の高速化 データベース問合せ最適化 組合せ論的アルゴリズム 並列処理 商品間関連　 危険度分析 顧客分類 ゲノム情報　 検索エンジン 発見科学

Association Rules

定期口座有無＝Ｎｏ ⇒ カードローン延滞有無＝Ｙｅｓ サポート Ｐｒ(XかつY) 例 ５％ 確信度 Ｐｒ(Y|X) 例 ３２％ 当座取引有無 定期口座有無 血液型 職業コード カードローン延滞有無 結合ルール Ｘ ⇒ Ｙ 定期口座有無＝Ｎｏ ⇒ カードローン延滞有無＝Ｙｅｓ サポート Ｐｒ(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 world-leading 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 HIC Provides A Healthier Future With IBM オーストラリア健康保険委員会 年間 数千万ドルの節約に成功 開業医が不必要な処方箋を出す ケースを見つけ出す規則の発見

φ A B C D AB AC BC AD BD CD ABC ABD ACD BCD ABCD まずサポートが閾値以上の条件集合 （大きい条件集合）を枚挙 条件数が少ない集合から徐々に サポートを計算 条件集合｛A,B,C｝ を ＡＢＣ と簡略に記述

Ｐｒ（Ｃ|Ｂ）＝Ｐｒ(BC)／ Ｐｒ(B) ABCD まずサポートが閾値以上の条件集合 （大きい条件集合）を枚挙 条件数が少ない集合から徐々に サポートを計算 枝狩り： Ｐｒ(AB) < 閾値 ⇒ Ｐｒ(ABC) < 閾値 ルール B ⇒ C は確信度 Ｐｒ（Ｃ|Ｂ）＝Ｐｒ(BC)／ Ｐｒ(B) が閾値以上のとき生成 ABC ABD ACD BCD AB AC BC AD BD CD A B C D φ A Ｐｒ（Ａ）≧閾値 ＡＢ Ｐｒ（ＡＢ）＜閾値

ACDE サポート計算の効率化 各レコードが満たす条件集合を見つけ、サポートを増加 大きい条件集合の候補を枚挙 AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 各レコードが満たす条件集合を見つけ、サポートを増加 ACDE

ACDE サポート計算の効率化 各レコードが満たす条件集合を見つけ、サポートを増加 大きい条件集合の候補を枚挙 AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 各レコードが満たす条件集合を見つけ、サポートを増加 ACDE A B B D C D D E ABD ABE ADE BCE BDE Hash table

ACDE サポート計算の効率化 各レコードが満たす条件集合を見つけ、サポートを増加 大きい条件集合の候補を枚挙 AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 各レコードが満たす条件集合を見つけ、サポートを増加 ACDE A B B D C D D E ABD ABE ADE BCE BDE Hash table

ABDE サポート計算の効率化 各レコードが満たす条件集合を見つけ、サポートを増加 大きい条件集合の候補を枚挙 AB AC AD AE BC BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE 各レコードが満たす条件集合を見つけ、サポートを増加 ABDE A B B D C D D E ABD ABE ADE BCE BDE Hash table

条件集合の枝狩りの効率化 データベースの走査回数を 減らせないか？ φ A B C D AB AC BC AD BD CD ABC ABD ACD BCD ABCD 例 サポートの 閾値が５％のとき

条件集合の枝狩りの効率化 ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D φ A 当確 当選 サイズ１の 条件集合の 計算を開始 A 当確 当選 落選 出馬

ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D φ A 当確 当選 落選 出馬 サイズ２ を開始 A B C D 読込済 φ サイズ１の 条件集合の 計算を開始 A 当確 当選 落選 出馬

ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D φ A 当確 当選 落選 出馬 サイズ３ 読込済 サイズ３ を開始 AB AC BC AD BD CD サイズ２ を開始 A B C D φ A 当確 当選 落選 出馬

ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D φ A 当確 当選 落選 出馬 サイズ１の サポート計算 終了 読込済 ABC ABD ACD BCD サイズ３ を開始 AB AC BC AD BD CD サイズ２ を開始 A B C D φ A 当確 当選 落選 出馬

ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D φ A 当確 当選 落選 出馬 サイズ１の サポート計算 終了 ABCD 第 １ 回 読 込 済 ABC ABD ACD BCD サイズ３ も開始 AB AC BC AD BD CD サイズ２の 計算終了 A B C D 読 込 済 φ サイズ１の 条件集合の サポート計算 を開始 A 当確 当選 落選 出馬

A priori に比べ ２０％から４倍の性能向上との報告されている ABCD サイズ１の サポート計算 終了 第 １ 回 読 込 済 ABC ABD ACD BCD 読 込 済 サイズ３の 計算終了 AB AC BC AD BD CD サイズ２の 計算終了 A B C D φ サイズ１の 条件集合の サポート計算 を開始 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 データ数 M, ピクセル数 n 領域族：矩形領域 最大サポート・最大確信度領域を O(n1.5) で計算可能 預金残高 領域族：X単調領域または直交凸領域 最大サポート・最大確信度領域を X単調はO(n M)、直交凸はO(n 1.5 M) で計算可能。 n と log M の多項式時間で計算することは P = NP でない限り不可能。 年齢 グリッド領域へ 近似アルゴリズム

Ｓ （年齢,預金残高）∈ Ｓ ⇒ カードローン延滞＝Yes p( {年齢,預金残高）∈Ｓ, カードローン延滞＝Yes} ) 確信度 p( {年齢,預金残高）∈Ｓ, カードローン延滞＝Yes} ) p(（年齢,預金残高）∈Ｓ)

近似解 Ｓ （年齢,預金残高）∈ Ｓ ⇒ カードローン延滞＝Yes p( {年齢,預金残高）∈Ｓ, カードローン延滞＝Yes} ) 確信度 サポート値の閾値 近似解 p( {年齢,預金残高）∈Ｓ, カードローン延滞＝Yes} ) p(（年齢,預金残高）∈Ｓ)

hand probing の回数はＯ(log Ｍ) サポート値の閾値 確信度 １ ２ ３ 凸閉包上の探索 １回の hand probing のコスト Ｘ単調領域 Ｏ(ｎ) 直交凸領域 Ｏ(ｎ1.5) hand probing の回数はＯ(log Ｍ)

ｙ =θｘ ＋ a 切片 ａ の最大化 各ピクセルに実数で表現される濃度 濃度の和を最大化する領域を計算

ルールの評価 － 領域族別、メッシュ粒度別 データを平面中に一様に生成 ガードローン延滞となる確率を 対角線からの距離に関して一様分布 10-fold Cross Validation

Classification

決定木 入力データ例 健康な人と心臓疾患の患者のデータ 血圧 心拍数 中性脂肪 肥満度 ＧＰＴ ＧＯＴ 心臓疾患

入力データ例 健康な人と心臓疾患の患者のデータ 決定木 入力データ例 健康な人と心臓疾患の患者のデータ 血圧 ＜ 125 Yes No Yes No 領域分割 血圧 ＧＰＴ Yes 訓練データで木を生成 評価基準： 未知データでの予測精度 動機： 領域分割は予測精度向上に効くか？ No

決定木 データ分割の評価方法 正のデータ 負のデータ

決定木 データ分割の評価方法 Ｑｕｉｎｌａｎのエントロピー 最小化 n Ent1= - (p log p + q log q) Ent2 決定木 データ分割の評価方法 Ｑｕｉｎｌａｎのエントロピー 最小化 正のデータ 負のデータ n Ent1= - (p log p + q log q) Ent2 n1 n2 ｐ ｑ n n1 Ent1 n n2 Ent2 +

Ｓ Ｓ中の正の データ数 Ｓ中のデータ数 エントロピー関数は凸関数 エントロピー最小の領域は 凸包の境界上に存在 Hand Probing で探索 単純な二分探索は困難 （凸包上の全ての点の エントロピーが一致する例） Ｓ中の正の データ数 Ｓ中のデータ数

≧ ｍｉｎ（Ｅｎｔ（Ｘ），Ｅｎｔ（Ｙ），ＥＮＴ（Ｚ）） Ｅｎｔ（三角形ＸＹＺ内の任意の点） ≧ ｍｉｎ（Ｅｎｔ（Ｘ），Ｅｎｔ（Ｙ），ＥＮＴ（Ｚ）） X Y Ｚ もし Ｅｎｔ（Ｚ）≧ 現時点の最小エントロピー ならば枝狩り Ｂｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ Ｓｅａｒｃｈ 実用上はほぼ、Ｏ（ｌｏｇＭ）のＨａｎｄ Ｐｒｏｂｉｎｇ

決定木性能評価 ＵＣ Irvine, Ｒｅｐｏｓｉｔｏｒｙ ｏｆ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ ｄａｔａｂａｓｅｓ http://www.ics.uci.edu/~mlearn/MLRepository.html 10-fold Cross Validation エラー率 データベース ﾚｺｰﾄﾞ数 属性数 ｸﾗｽ数 Ｘ単調 直交凸 矩形 二分割 balance scale 625 4 3 15.52 15.52 19.34 20.95 breast-cancer-wisc 699 9 2 5.01 4.15 4.58 5.72 german credit 1000 24 2 27.30 23.80 26.90 25.60 liver disorder 345 6 2 34.81 33.36 31.08 34.87 pima diabetes 768 8 2 24.47 25.12 23.69 26.82 segmentation 2310 19 7 4.81 4.37 4.89 4.50 vehicle 846 18 4 30.02 28.47 27.65 26.23 waveform 5000 20 3 21.74 20.98 22.36 22.74 waveform+noise 5000 40 3 22.54 21.32 22.94 24.36

回帰木 (Regression Tree) ＢＰＳ ＧＤＭ ＹＥＮ ＴＢ３Ｍ ＴＢ３０Ｙ SP500 GOLD 1.443530 0.407460 0.004980 7.02 9.31 210.88 326.00 1.446120 0.408050 0.004950 7.04 9.28 205.96 339.45 : : : : : : :

Ｙｅｓ Ｎｏ Ｎｏ Ｙｅｓ

外 Ｄ１ Ｄ２ 領域中 μ１ μ２ 誤差二乗平均を最小化する領域

Σ Σ Ａ μ 外 Ｄ１ Ｄ２ 領域中 μ１ μ２ （ｔ[Ａ]－μ１ ）２ （ｔ[Ａ]－μ２ ）２ 誤差二乗平均の 最小化 ＋ ｔ∈Ｄ１ Σ （ｔ[Ａ]－μ２ ）２ ｔ∈Ｄ２ 誤差二乗平均の 最小化 ＋ | Ｄ１∪Ｄ２ | | Ｄ１ |（ μ －μ１ ）２ ＋｜Ｄ２ |（ μ －μ２ ）２ クラス間分散の 最大化 | Ｄ１∪Ｄ２ |

Ｓ Ｓ中データ の目標属性 の値の和 Ｓ中のデータ数 クラス間分散関数は凸関数 クラス間分散最大の領域は 凸包の境界上に存在 Hand Probing で探索 単純な二分探索は困難 Ｂｒａｎｃｈ ａｎｄ Ｂｏｕｎｄ Ｓｅａｒｃｈ で実用上はＯ（ｌｏｇ Ｍ） Ｓ中データ の目標属性 の値の和 Ｓ中のデータ数

回帰木性能評価 http://www.cs.utoronto.ca/~delve/data/datasets.html 10-fold Cross Validation 誤差二乗平均（予測前と後の比） データベース ﾚｺｰﾄﾞ数 属性数 Ｘ単調 直交凸 矩形 二分割 add10 9792 10 0.141 0.123 0.156 0.185 abalone 4177 8 0.521 0.515 0.534 0.539 kin-8fh 8192 8 0.447 0.433 0.459 0.479 kin-8fm 8192 8 0.225 0.197 0.257 0.249 kin-8nh 8192 8 0.649 0.618 0.619 0.655 kin-8nm 8192 8 0.494 0.449 0.478 0.541 pumadyn-kin-8fh 8192 8 0.412 0.402 0.409 0.410 pumadyn-kin-8fh 8192 8 0.0604 0.0595 0.0653 0.0632 pumadyn-kin-8fh 8192 8 0.347 0.337 0.353 0.355 pumadyn-kin-8fh 8192 8 0.0530 0.0496 0.0550 0.0535

OLETF インシュリン非依存型糖 尿病モデルラット F344 正常のモデルラット 何世代か 交配後のラット Marker(1) = OLETF ホモ接合 Marker(2) = F344 ホモ接合 Marker(3) = OLETF / F344 ヘテロ接合 Intercross

表現型 血糖値, 疾患, 遺伝子型 (3×102列) マーカー接合状態 個体 102 ｜ 103 個

表現型 血糖値, 疾患, 遺伝子発現量, 薬の効果, 副作用, ... 遺伝子型 (102～107列) 遺伝子発現量, SNP, ... 個体 102 ｜ 104 個

Clustering

Five brain tissues of adult mouse Expression Patterns of Genes in Various Tissues Brain in embryo 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

Clusters of genes coding myelin Cluster of genes coding ribosomal proteins

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 Minimizing the maximum value of diameters or intra-class variances of all clusters Optimization criteria

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 =　 Diameter2 Intra-class variance1 　 >> 　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 intra-class variance =209 Clusters of genes coding myelin 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 情報科学的手法 近似アルゴリズム グラフアルゴリズム