歸納算法可擴(kuò)展性算法、研究綜述

1、2022-2-191歸納算法可擴(kuò)展性算法研究綜述主講人:蔡偉杰2022-2-192可擴(kuò)展性研究綜述 為什么需要進(jìn)行可擴(kuò)展性研究 1訓(xùn)練集大,準(zhǔn)確率上升 2為了尋找到小事件情況 3其他需要多大的數(shù)據(jù)量? 100M-1G2022-2-193可擴(kuò)展性研究綜述 什么是可擴(kuò)展性? 時(shí)間復(fù)雜度: 和記錄個(gè)數(shù)、屬性之間的關(guān)系。 對(duì)空間的需求： 避免超過(guò)主存的情況。 模型結(jié)果的質(zhì)量： 質(zhì)量不能明顯的降低。2022-2-194可擴(kuò)展性研究綜述 可擴(kuò)展性方法分類(lèi)： 設(shè)計(jì)一個(gè)快速算法 限制模型空間 、強(qiáng)大的啟發(fā)式搜索 、算法、編程上的優(yōu)化 、并行方法 數(shù)據(jù)分片 選擇一個(gè)實(shí)例子空間 、選擇一個(gè)屬性子空間 、對(duì)子空間順

2、序進(jìn)行處理 、對(duì)子空間并行進(jìn)行處理 關(guān)系性表達(dá) 用關(guān)系的方式表達(dá)數(shù)據(jù) 、將數(shù)據(jù)挖掘整合到數(shù)據(jù)庫(kù)管理中 2022-2-195可擴(kuò)展性研究綜述 設(shè)計(jì)一個(gè)快速算法： 算法時(shí)間復(fù)雜度容忍極限 O(e3/2) 數(shù)據(jù)挖掘就是在一個(gè)模型空間中尋找某個(gè)模型，該模型在某些標(biāo)準(zhǔn)下表現(xiàn)得很好。2022-2-196可擴(kuò)展性研究綜述 限制模型搜索的空間 線形回歸方法、簡(jiǎn)單神經(jīng)元、單層決策樹(shù)（decision stumps）。 搜索空間小而且效果也不壞。 2022-2-197可擴(kuò)展性研究綜述 強(qiáng)大的啟發(fā)式搜索： 大數(shù)據(jù)量情況，不允許生成多個(gè)模型之后再進(jìn)行選擇 決策樹(shù)分而治之的方法：ID3、C4.5復(fù)雜度O(ea2)。 規(guī)

3、則集(rule sets)。但是其效率較差O(e3)甚至更高。 MetaDENDRAL-style rule 2022-2-198可擴(kuò)展性研究綜述 算法、編程優(yōu)化 : 使用有效的數(shù)據(jù)結(jié)構(gòu)(bit vectors,hash tables,binary search trees)和聰明的編程技巧 對(duì)MetaDENDRAL-style rule的優(yōu)化 對(duì)決策樹(shù)的優(yōu)化： 充足的統(tǒng)計(jì)信息 2022-2-199可擴(kuò)展性研究綜述 并行處理 : 搜索空間的并行處理 : 使用共享內(nèi)存多處理器很好的實(shí)現(xiàn)了決策樹(shù)的搜索空間的并行處理。 并行匹配： 對(duì)節(jié)點(diǎn)的評(píng)估代價(jià)是很高的，同時(shí)也有很大的并行性。 數(shù)據(jù)分割之后的并行

4、處理 2022-2-1910可擴(kuò)展性研究綜述 數(shù)據(jù)分割： 選擇一個(gè)子集: 只選擇一個(gè)子集進(jìn)行處理 ： 抽樣方法： 抽樣和準(zhǔn)確率的關(guān)系： 主動(dòng)和被動(dòng)抽樣：2022-2-1911可擴(kuò)展性研究綜述 數(shù)據(jù)分割：選擇一個(gè)屬性子空間 當(dāng)前屬性選擇工作的焦點(diǎn) 訓(xùn)練集較小的時(shí)候 ,降低結(jié)果Overfitting 領(lǐng)域?qū)＜业慕换?,選擇屬性 選擇足夠多的屬性 ,再去除2022-2-1912可擴(kuò)展性研究綜述 數(shù)據(jù)分割： 對(duì)子空間順序進(jìn)行處理 并行計(jì)算子空間 2022-2-1913可擴(kuò)展性研究綜述 關(guān)系表達(dá) 挖掘小數(shù)據(jù)的速度更快； 扁平化極大的數(shù)據(jù)集往往不可行 方法：用關(guān)系的方式表達(dá)數(shù)據(jù)數(shù)據(jù)挖掘和數(shù)據(jù)庫(kù)管理系統(tǒng)的結(jié)合2022-2-1914可擴(kuò)展性研究綜述 挖掘關(guān)系數(shù)據(jù)： 對(duì)層次數(shù)據(jù)的直接挖掘 挖掘多表數(shù)據(jù)庫(kù) ILP研究數(shù)據(jù)以關(guān)系方式存的知識(shí)發(fā)現(xiàn) 數(shù)據(jù)挖掘和DBMS結(jié)合 將DBMS作為一個(gè)簡(jiǎn)單的數(shù)據(jù)源 將對(duì)數(shù)據(jù)進(jìn)行計(jì)算的部分放入DBMS Cache-Mine 將數(shù)據(jù)挖掘操作作為一個(gè)函數(shù)(UDF)2022-2-1915四種和數(shù)據(jù)庫(kù)結(jié)合方法的比較2022-2-1916可擴(kuò)展性研究綜述 分