數(shù)據(jù)挖掘算法(wangye 2006.8)

數(shù)據(jù)挖掘算法 WangYe2006 8 一 概念和術(shù)語 1 1數(shù)據(jù)挖掘 知識發(fā)現(xiàn) 1 數(shù)據(jù)挖掘是從存放在數(shù)據(jù)集中的大量數(shù)據(jù)挖掘出有趣知識的過程 2 數(shù)據(jù)挖掘 又稱為數(shù)據(jù)庫中知識發(fā)現(xiàn) KnowledgeDiscoveryinDatabases 或知識發(fā)現(xiàn) 它是一個從大量數(shù)據(jù)中抽取挖掘出未知的 有價值的模式或規(guī)律等知識的非平凡過程 它與數(shù)據(jù)倉庫有著密切的聯(lián)系 3 廣義的數(shù)據(jù)挖掘是指知識發(fā)現(xiàn)的全過程 狹義的數(shù)據(jù)挖掘是指統(tǒng)計分析 機器學(xué)習(xí)等發(fā)現(xiàn)數(shù)據(jù)模式的智能方法 即偏重于模型和算法 4 數(shù)據(jù)庫查詢系統(tǒng)和專家系統(tǒng)不是數(shù)據(jù)挖掘 在小規(guī)模數(shù)據(jù)上的統(tǒng)計分析和機器學(xué)習(xí)過程也不應(yīng)算作數(shù)據(jù)挖掘 1 2機器學(xué)習(xí) 1 對于某類任務(wù)T和性能度量P 如果一個計算機程序在T上以P衡量的性能隨著經(jīng)驗E而自我完善 那么這個計算機程序被稱為在從經(jīng)驗E學(xué)習(xí) 2 機器學(xué)習(xí)是知識發(fā)現(xiàn)的一種方法 是指一個系統(tǒng)通過執(zhí)行某種過程而改進它處理某一問題的能力 1 3數(shù)據(jù)挖掘的對象 1 關(guān)系型數(shù)據(jù)庫 事務(wù)型數(shù)據(jù)庫 面向?qū)ο蟮臄?shù)據(jù)庫 2 數(shù)據(jù)倉庫 多維數(shù)據(jù)庫 3 空間數(shù)據(jù) 如地圖信息 4 工程數(shù)據(jù) 如建筑 集成電路的信息 5 文本和多媒體數(shù)據(jù) 如文本 圖象 音頻 視頻數(shù)據(jù) 6 時間相關(guān)的數(shù)據(jù) 如歷史數(shù)據(jù)或股票交換數(shù)據(jù) 7 萬維網(wǎng) 如半結(jié)構(gòu)化的HTML 結(jié)構(gòu)化的XML以及其他網(wǎng)絡(luò)信息 1 4數(shù)據(jù)挖掘的步驟 1 數(shù)據(jù)清理 消除噪音或不一致數(shù)據(jù) 補缺 2 數(shù)據(jù)集成 多種數(shù)據(jù)源可以組合在一起 3 數(shù)據(jù)選擇 從數(shù)據(jù)庫中提取相關(guān)的數(shù)據(jù) 4 數(shù)據(jù)變換 變換成適合挖掘的形式 5 數(shù)據(jù)挖掘 使用智能方法提取數(shù)據(jù)模式 6 模式評估 識別提供知識的真正有趣模式 7 知識表示 可視化和知識表示技術(shù) 1 5支持數(shù)據(jù)挖掘的關(guān)鍵技術(shù) 1 數(shù)據(jù)庫 數(shù)據(jù)倉庫 OLAP 2 數(shù)學(xué) 統(tǒng)計 回歸分析 多元回歸 自回歸 判別分析 Bayes判別 Fisher判別 非參數(shù)判別 主成分分析 相關(guān)性分析 模糊集 粗糙集 3 機器學(xué)習(xí) 聚類分析 關(guān)聯(lián)規(guī)則 決策樹 范例推理 貝葉斯網(wǎng)絡(luò) 神經(jīng)網(wǎng)絡(luò) 支持向量機 遺傳算法 4 可視化 將數(shù)據(jù) 知識和規(guī)則轉(zhuǎn)化為圖形表現(xiàn)的形式 1 6數(shù)據(jù)倉庫 1 數(shù)據(jù)倉庫是一個面向主題的 集成的 隨時間變化的 非易失性數(shù)據(jù)的集合 用于支持管理人員的決策 2 數(shù)據(jù)倉庫是一種多個異種數(shù)據(jù)源在單個站點以統(tǒng)一的模式組織的存儲 以支持管理決策 數(shù)據(jù)倉庫技術(shù)包括數(shù)據(jù)清理 數(shù)據(jù)集成和聯(lián)機分析處理 OLAP 3 數(shù)據(jù)倉庫的邏輯結(jié)構(gòu)是多維數(shù)據(jù)庫 數(shù)據(jù)倉庫的實際物理結(jié)構(gòu)可以是關(guān)系數(shù)據(jù)存儲或多維數(shù)據(jù)方 Cube 4 數(shù)據(jù)方是由維度 Dimension 和度量 Measure 定義的一種數(shù)據(jù)集 度量存放在由維度索引的數(shù)據(jù)方單元中 維度對應(yīng)于模式中的屬性組 度量對應(yīng)于與主題相關(guān)的事實數(shù)據(jù) 數(shù)據(jù)方的物化是指預(yù)計算并存儲全部或部分單元中的度量 1 7數(shù)據(jù)倉庫的模型 1 星形模式 最常見模型 其中數(shù)據(jù)倉庫包括一個大的 包含大批數(shù)據(jù) 不含冗余的中心表 事實表 一組小的附屬表 維表 每維一個 2 雪花模式 雪花模式是星型模式的變種 其中某些維表是規(guī)范化的 因而把數(shù)據(jù)進一步分解到附加的表中 3 星系模式 多個事實表共享維表 這種模式可以看作星形模式集 因此稱為星系模式 或事實星座 1 8典型的OLAP操作 1 OLAP是一種多維數(shù)據(jù)分析技術(shù) 包括匯總 合并和聚集等功能 以及從不同的角度觀察信息的能力 2 上卷 從某一維度的更高概念層次觀察數(shù)據(jù)方 獲得更概要的數(shù)據(jù) 它通過沿維的概念分層向上或維歸約來實現(xiàn) 3 下鉆 下鉆是上卷的逆操作 它從某一維度的更低概念層次觀察數(shù)據(jù)方 獲得更詳細的數(shù)據(jù) 下鉆可以通過沿維的概念分層向下或引入新的維來實現(xiàn) 4 切片和切塊 切片操作在給定的數(shù)據(jù)方的選擇一個維的部分屬性 獲得一個較小的子數(shù)據(jù)方 切塊操作通過對選擇兩個或多個維的部分屬性 獲得一個較小的子數(shù)據(jù)方 5 轉(zhuǎn)軸 是一種改變數(shù)據(jù)方二維展現(xiàn)形式的操作 它將數(shù)據(jù)方的二維展現(xiàn)中的某些維度由行改為列 或由列改為行 二 數(shù)據(jù)準備 現(xiàn)實世界的數(shù)據(jù)是不完整的 有些感興趣的屬性缺少屬性值 或僅包含聚集數(shù)據(jù) 含噪音的 包含錯誤 或存在偏離期望的異常值 不一致的 例如 用于商品分類的部門編碼存在差異 需要數(shù)據(jù)清理 數(shù)據(jù)集成 數(shù)據(jù)選擇 數(shù)據(jù)變換等技術(shù)對數(shù)據(jù)進行處理 2 1維歸約 特征提取2 1 1決策樹歸約 1 決策樹歸約構(gòu)造一個類似于流程圖的結(jié)構(gòu) 其每個非葉子結(jié)點表示一個屬性上的測試 每個分枝對應(yīng)于測試的一個輸出 每個葉子結(jié)點表示一個決策類 2 在每個結(jié)點 算法選擇 當(dāng)前對分類最有幫助 的屬性 出現(xiàn)在樹中的屬性形成歸約后的屬性子集 2 1 2粗糙集歸約 1 粗糙集理論在數(shù)學(xué)意義上描述了知識的不確定性 它的特點是把用于分類的知識嵌入集合內(nèi) 使分類與知識聯(lián)系在一起 2 知識的粒度 不可分辨關(guān)系 上近似 下近似 邊界等概念見下圖 2 1 2粗糙集歸約 續(xù) 3 令Q代表屬性的集合 q Q是一個屬性 如果IND Q q IND Q 則q在S中不是獨立的 否則稱q在S中是獨立的 4 若集合滿足IND R IND Q 且R中的每一個屬性都是獨立的 則R被稱為Q的一個 約簡 記作R RED Q 5 約簡可以通過刪除冗余的 不獨立的 屬性而獲得 約簡包含的屬性即為 對分類有幫助 的屬性 2 2數(shù)據(jù)變換2 2 1歸一化與模糊化有限區(qū)間的歸一化 無限區(qū)間的歸一化 模糊隸屬度 2 2 2核函數(shù) 1 核函數(shù)的基本思想是將在低維特征向量線性不可分的數(shù)據(jù)映射到線性可分的高維特征空間中去 2 映射可以是顯式的 也可以是隱式的 顯式映射即找到一個映射關(guān)系f 使高維空間的特征向量f x 可以被直接計算出來 3 隱式映射 即引入一個核函數(shù)進行整體處理 就避免了對的直接求f x 的計算困難 核函數(shù)即某高維特征空間中向量的內(nèi)積 是核矩陣中的一個元素 4 并不是所有的實值函數(shù)f x 都可以作為空間映射的核函數(shù) 只有f x 是某一特征空間的內(nèi)積時 即符合Mercer條件 它才能成為核函數(shù) 2 2 2核函數(shù) 續(xù) 多項式函數(shù) 高斯 RBF 函數(shù) 多層感知機函數(shù) 低維空間向量映射到高維空間向量舉例 2 3數(shù)據(jù)壓縮2 3 1離散化離散化的用途 1 適應(yīng)某些僅接受離散值的算法 2 減小數(shù)據(jù)的尺度 離散化的方法包括幾下幾種 1 等距分割 2 聚類分割 3 直方圖分割 4 基于熵的分割 5 基于自然屬性的分割 2 3 2回歸回歸和對數(shù)線性模型可以用來近似給定的數(shù)據(jù) 在線性回歸中 用一條直線來模擬數(shù)據(jù)的生成規(guī)則 多元回歸是線性回歸的擴展 涉及多個預(yù)測變量 在多項式回歸中 通過對變量進行變換 可以將非線性模型轉(zhuǎn)換成線性的 然后用最小平方和法求解 2 3 2回歸 續(xù) 利用線性回歸可以為連續(xù)取值的函數(shù)建模 廣義線性模型則可以用于對離散取值變量進行回歸建模 在廣義線性模型中 因變量Y的變化速率是Y均值的一個函數(shù) 這一點與線性回歸不同 常見的廣義線性模型有 對數(shù)回歸和泊松回歸 對數(shù)回歸模型是利用一些事件發(fā)生的概率作為自變量所建立的線性回歸模型 泊松回歸模型主要是描述數(shù)據(jù)出現(xiàn)次數(shù)的模型 因為它們常常表現(xiàn)為泊松分布 2 3 3主成分分析 PCA PCA算法搜索c個最能代表數(shù)據(jù)的k 維正交向量 這里c k 這樣 原來的數(shù)據(jù)投影到一個較小的空間 導(dǎo)致數(shù)據(jù)壓縮 步驟如下 1 對輸入數(shù)據(jù)歸一化 使得每個屬性都落入相同的區(qū)間 2 PCA計算c個規(guī)范正交向量 作為歸一化輸入數(shù)據(jù)的基 這些是單位向量 每一個都垂直于另一個 稱為主成分 輸入數(shù)據(jù)是主要成分的線性組合 3 對主成分按 意義 或強度降序排列 選擇部分主成分充當(dāng)數(shù)據(jù)的一組新坐標軸 2 3 4離散小波變換 DWT 離散小波變換是一種線性信號處理技術(shù) 該技術(shù)方法可以將一個數(shù)據(jù)向量轉(zhuǎn)換為另一個數(shù)據(jù)向量 為小波相關(guān)系數(shù) 且兩個向量具有相同長度 可以舍棄轉(zhuǎn)換后的數(shù)據(jù)向量中的一些小波相關(guān)系數(shù) 保留所有大于用戶指定閾值的小波系數(shù) 而將其它小波系數(shù)置為0 以幫助提高數(shù)據(jù)處理的運算效率 這一技術(shù)方法可以在保留數(shù)據(jù)主要特征情況下除去數(shù)據(jù)中的噪聲 因此該方法可以有效地進行數(shù)據(jù)清洗 給定一組小波相關(guān)系數(shù) 利用離散小波變換的逆運算還可以近似恢復(fù)原來的數(shù)據(jù) 2 3 4離散小波變換 續(xù) 常用的小波函數(shù)包括Haar系列 Daubechies系列 Moret系列 Sym系列 Meyer系列 Coif系列 2 3 5潛在語義分析潛在語義分析將樣本映射到語義概念空間以發(fā)現(xiàn)樣本數(shù)據(jù)之間的潛在語義聯(lián)系 1 構(gòu)造 特征 樣本 矩陣 特征 樣本 矩陣中的每一列是對應(yīng)于第i個樣本特征向量 2 對該矩陣進行奇異值分解 SVD 3 用最大的k個奇異值所對應(yīng)的 特征 語義 矩陣Uk和 樣本 語義 矩陣Vk以及最大的k個奇異值重構(gòu) 特征 樣本 矩陣 下面兩式分別代表在語義空間特征與特征之間的距離和在語義空間樣本與樣本之間的距離 2 3 6聚類分析聚類技術(shù)將數(shù)據(jù)元組視為對象 它將對象劃分為聚類 使在一個聚類中的對象 類似 但與其它聚類中的對象 不類似 通常 類似性基于距離 用對象在空間中的 接近 程度定義 聚類的 質(zhì)量 可以用 直徑 表示 而直徑是一個聚類中兩個任意對象的最大距離 質(zhì)心距離是聚類質(zhì)量的另一種度量 它定義為由聚類質(zhì)心 表示 平均對象 或聚類空間中的平均點 到每個聚類對象的平均距離 2 3 6聚類分析 續(xù) k means算法 k medoids算法 三 數(shù)據(jù)挖掘算法 數(shù)據(jù)挖掘算法按挖掘目的可分為 1 概念描述 總結(jié) 對比等 2 關(guān)聯(lián)規(guī)則分析 3 分類與預(yù)測 信息自動分類 信息過濾 圖像識別等 4 聚類分析 5 異常分析 入侵檢測 金融安全等 6 趨勢 演化分析 回歸 序列模式挖掘 按訓(xùn)練方式 機器學(xué)習(xí)可分為 1 有監(jiān)督的學(xué)習(xí) 有訓(xùn)練樣本 學(xué)習(xí)機通過學(xué)習(xí)獲得訓(xùn)練樣本包含的知識 并用其作為判斷測試樣本的類別的依據(jù) 2 無監(jiān)督的學(xué)習(xí) 無訓(xùn)練樣本 僅根據(jù)測試樣本的在特征空間分布情況判斷其類別 3 半監(jiān)督的學(xué)習(xí) 有少量訓(xùn)練樣本 學(xué)習(xí)機以從訓(xùn)練樣本獲得的知識為基礎(chǔ) 結(jié)合測試樣本的分布情況逐步修正已有知識 并判斷測試樣本的類別 4 強化學(xué)習(xí) 沒有訓(xùn)練樣本 但有對學(xué)習(xí)機每一步是否更接近目標的獎懲措施 有監(jiān)督的學(xué)習(xí) 半監(jiān)督的學(xué)習(xí) 無監(jiān)督的學(xué)習(xí) 3 1關(guān)聯(lián)規(guī)則挖掘關(guān)聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系 設(shè)I i1 i2 im 是項的集合 設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合 其中每個事務(wù)T是項的集合 使得T I 設(shè)A是一個項集 事務(wù)T包含A當(dāng)且僅當(dāng)A T 關(guān)聯(lián)規(guī)則是形如A B的蘊涵式 其中A I B I 并且A B 規(guī)則A B在事務(wù)集D中成立 具有支持度s 其中s是D中事務(wù)包含A B的百分比 即 P A B 規(guī)則A B在事務(wù)集D中具有置信度c 如果D中包含A的事務(wù)同時也包含B的百分比是c 這是條件概率P B A 即support A B P A B confidence A B P B A 3 1關(guān)聯(lián)規(guī)則挖掘 續(xù) Apriori性質(zhì) 頻繁項集的所有非空子集都必須也是頻繁的 Apriori性質(zhì)基于如下觀察 根據(jù)定義 如果項集I不滿足最小支持度閾值s 則I不是頻繁的 即P I s 如果項A添加到I 則結(jié)果項集 即I A 不可能比I更頻繁出現(xiàn) 因此 I A也不是頻繁的 即P I A s 該性質(zhì)表明如果一個集合不能通過測試 則它的所有超集也都不能通過相同的測試 將Apriori性質(zhì)應(yīng)用于算法 下面算法的兩個主要步過程由連接和剪枝組成 3 1關(guān)聯(lián)規(guī)則挖掘 續(xù) 連接步 為找Lk 通過Lk 1與自己連接產(chǎn)生候選k 項集的集合 該候選項集的集合記作Ck Ck是Lk的超集 掃描數(shù)據(jù)庫 確定Ck中每個候選的計數(shù) 將令計數(shù)值不小于最小支持度計數(shù)的 頻繁的 所有候選加入Lk 剪枝步 但Ck可能很大 這樣所涉及的計算量就很大 根據(jù)Apriori性質(zhì)如果一個候選k 項集的 k 1 子集不在Lk 1中 則該候選也不可能是頻繁的 從而可以由Ck中刪除 Apriori性質(zhì) 逆反描述 任何非頻繁的 k 1 項集都不是可能是頻繁k 項集的子集 3 2決策樹決策樹學(xué)習(xí)是歸納推理算法 它是一種逼近離散函數(shù)的方法 且對噪聲數(shù)據(jù)有很好的健壯性 在這種方法中學(xué)習(xí)到的知識被表示為決策樹 決策樹也能再被表示為多個if then的規(guī)則 以提高可讀性 基本決策樹算法就是一個貪心算法 它采用自上而下 分而制之的遞歸方式來構(gòu)造一個決策樹通常 決策樹是一種自頂向下增長樹的貪婪算法 在每個結(jié)點選取能最好地分類樣例的屬性 繼續(xù)這個過程直到這棵樹能完美分類訓(xùn)練樣例 或所有的屬性都使用過了 信息增益 用于衡量屬性的價值 熵 entropy 是一種度量信息增益的指標 它描述了樣本的純度 purity 下面是熵的定義 Entropy Pilog2Pi 3 2決策樹 續(xù) 注意點 1 避免過度擬合 應(yīng)該適度剪枝 2 連續(xù)值的離散化 3 處理缺失值的方法 最常見值 按概率分配 4 處理權(quán)重不同的屬性常用實現(xiàn)算法 CART ID3 ASSISTANT C4 5 3 3人工神經(jīng)網(wǎng)絡(luò)人工神經(jīng)網(wǎng)絡(luò) ArtificialNeuralNetworks 提供了一種普遍而且實用的方法 來從樣例中學(xué)習(xí)值為實數(shù) 離散或向量的函數(shù) 反向傳播 BackPropagation 這樣的算法使用梯度下降來調(diào)節(jié)網(wǎng)絡(luò)參數(shù)以最佳擬合由輸入 輸出對組成的訓(xùn)練集合 BP網(wǎng)絡(luò)的學(xué)習(xí)方法和目標 對網(wǎng)絡(luò)的連接權(quán)值進行調(diào)整 使得對任一輸入都能得到所期望的輸出 常用的非線性作用函數(shù)是Sigmoid函數(shù) 即f x 1 1 e x 在神經(jīng)網(wǎng)絡(luò)模型中 大量神經(jīng)元節(jié)點按一定體系結(jié)構(gòu)連接成網(wǎng)狀 神經(jīng)網(wǎng)絡(luò)一般都具有輸入層 隱層和輸出層 每個神經(jīng)元都是一個結(jié)構(gòu)相似的獨立單元 它接受前一層傳來的數(shù)據(jù) 并將這些數(shù)據(jù)的加權(quán)和輸入非線性作用函數(shù)中 最后將非線性作用函數(shù)的輸出結(jié)果傳遞給后一層 誤差反向傳播的過程 3 3人工神經(jīng)網(wǎng)絡(luò) 續(xù) 自適應(yīng)共振理論模型 ART 聚類連續(xù) 離散Hopfield神經(jīng)網(wǎng)絡(luò) 求近似最優(yōu)解 識別與分類雙向聯(lián)想記憶模型 BAM 識別玻爾茲曼機 BM 求最優(yōu)解腦中盒模型 BSB 識別與分類自組織映射模型 SOM 識別與分類對向傳播網(wǎng)絡(luò)模型 CPN 識別與分類小腦模型 CMAC 快速識別 3 4樸素貝葉斯 NaiveBayes 分類器樸素貝葉斯分類器是一種基于貝葉斯理論的分類器 它的特點是以概率形式表達所有形式的不確定 學(xué)習(xí)和推理都由概率規(guī)則實現(xiàn) 學(xué)習(xí)的結(jié)果可以解釋為對不同可能的信任程度 P H 是先驗概率 或H的先驗概率 P H X 是后驗概率 或條件X下 H的后驗概率 后驗概率P H X 比先驗概率P H 基于更多的信息 P H 是獨立于X的 假定數(shù)據(jù)樣本世界由水果組成 用它們的顏色和形狀描述 假定X表示紅色和圓的 H表示假定X是蘋果 則P H X 反映當(dāng)我們看到X是紅色并是圓的時 我們對X是蘋果的確信程度 樸素貝葉斯分類能夠奏效的前提是 P X H 相對比較容易計算 假定X表示紅色和圓的 H表示假定X是蘋果 則P X H 表示已知蘋果 它既紅又圓的概率 3 5期望最大化 EM 期望最大化 EM 方法和樸素貝葉斯方法有著共同的理論基礎(chǔ) 期望最大化是一種基于循環(huán)過程的最大似然參數(shù)估計方法 用于解決帶缺失數(shù)據(jù)的參數(shù)估計問題 樣本數(shù)據(jù)分為標記樣本和未標記樣本 按照統(tǒng)計的觀點 對于每一個樣本的產(chǎn)生 其背后都有一個模型 即樣本生成模型 樣本生成模型的參數(shù)先由標記樣本確定 再通過標記樣本和利用當(dāng)前模型判斷標記的未標記樣本共同調(diào)整 3 5期望最大化 續(xù) 如果參數(shù)適當(dāng) EM算法能得到較好的分類結(jié)果 但計算速度相對較慢 其具體的步驟如下 一 初始參數(shù)估計 將未標記的樣本按樸素貝葉斯分類方法進行類標注 二 反復(fù)迭代E步驟和M步驟 直到收斂 三 E步驟 對于每個未標記的樣本 按下式計算類標記的期望值 四 M步驟 利用E步驟計算出的期望值 按下式用已標記樣本和未標記樣本重新估計新的分類器參數(shù) 3 6K 最近鄰分類K 近鄰 K NN 分類是基于范例的分類方法 它的基本思想是 給定待分類樣本后 考慮在訓(xùn)練樣本集中與該待分類樣本距離最近 最相似 的K個樣本 根據(jù)這K個樣本中大多數(shù)樣本所屬的類別判定待分類樣本的類別 它的特例是1 NN 即分類時選出待分類樣本的最近鄰 并以此最近鄰的類標記來判斷樣本的類 K NN算法的優(yōu)點在于它有較高的精確程度 研究表明 K NN的分類效果要明顯好于樸素貝葉斯分類 決策樹分類 3 6K 最近鄰分類 續(xù) 最近鄰分類的算法步驟如下 一 以向量空間模型的形式描述各訓(xùn)練樣本 二 在全部訓(xùn)練樣本集中選出與待分類樣本最相似的K個樣本 K值的確定目前沒有很好的方法 一般采用先定一個100左右的初始值 然后再調(diào)整 三 將待分類樣本標記為其K個鄰居中所屬最多的那個類別中 3 7遺傳算法遺傳算法易于并行處理 其依據(jù)是自然界進化和適者生存的原則 遺傳學(xué)習(xí)開始如下 創(chuàng)建若干個由隨機產(chǎn)生的個體組成的初始群體 每個個體用一個二進位串表示 形成由當(dāng)前群體中最適合的個體組成新的群體 以及這些規(guī)則的子女 個體的適合度用某一目標函數(shù)來評估 子女通過使用諸如交叉和變異等遺傳操作來創(chuàng)建 在交叉操作中 來自個體對的子串交換 形成新的個體對 在變異操作中 個體中隨機選擇的位被反轉(zhuǎn) 3 7遺傳算法 續(xù) Fitness 適應(yīng)度評分函數(shù) 為給定假設(shè)賦予一個評估得分 Fitness threshold 指定終止判據(jù)的閾值 p 群體中包含的假設(shè)數(shù)量 r 每一步中通過交叉取代群體成員的比例 m 變異率 初始化群體 P 隨機產(chǎn)生的p個假設(shè)評估 對于P中的每一個h 計算Fitness h 當(dāng) Fitness h Fitness threshold 做 產(chǎn)生新的一代PS 3 7遺傳算法 續(xù) 選擇 用概率方法選擇P的 1 r p個成員加入PS 從P中選擇假設(shè)hi的概率P hi 通過下面公式計算 交叉 根據(jù)上面給出的P hi 從P中按概率選擇r p 2對假設(shè) 對于每一對假設(shè)應(yīng)用交叉算子產(chǎn)生兩個后代 把所有的后代加入PS 變異 使用均勻的概率從PS中選擇m百分比的成員 對于選出的每個成員 在它的表示中隨機選擇一個位取反 更新 P PS 評估 對于P中的每一個h計算Fitness h 從P中返回適應(yīng)度最高的假設(shè) 3 8聚類分析為達到全局最優(yōu) 基于劃分的聚類會要求窮舉所有可能的劃分 聚類技術(shù)將數(shù)據(jù)元組視為對象 它將對象劃分為群或聚類 使得在一個聚類中的對象 類似 但與其它聚類中的對象 不類似 絕大多數(shù)應(yīng)用采用了以下兩個比較流行的基于劃分的方法 這些基于劃分的聚類方法對在中小規(guī)模的數(shù)據(jù)庫中發(fā)現(xiàn)球狀簇很適用 1 k means算法 在該算法中 每個簇用該簇中對象的平均值來表示 2 k medoids算法 在該算法中 每個簇用接近聚類中心的一個對象來表示 3 8聚類分析 續(xù) 常用的相似程度度量余弦夾角 Dice系數(shù) Jaccard系數(shù) 3 8聚類分析 續(xù) 基于層次的方法 層次的方法對給定數(shù)據(jù)集合進行層次的分解 根據(jù)層次的分解如何形成 層次的方法可以被分為凝聚或分裂方法 Chameleon CURE BIRCH 基于密度的方法 只要臨近區(qū)域的密度超過某個閾值 就繼續(xù)聚類 避免僅生成球狀聚類 DBSCAN OPTICS DENCLUE 基于網(wǎng)格的方法 基于網(wǎng)格的方法把對象空間量化為有限數(shù)目的單元 所有的聚類操作都在這個量化的空間上進行 這種方法的主要優(yōu)點是它的處理速度很快 STING CLIQUE WaveCluster 基于模型的方法 為每個簇假設(shè)一個模型 發(fā)現(xiàn)數(shù)據(jù)對模型的最好匹配 COBWEB CLASSIT AutoClass 3 9隱馬爾可夫模型對于一個隨機事件 有一個觀察值序列 O1 OT 該事件隱含著一個狀態(tài)序列 X1 XT假設(shè)1 馬爾可夫性 P Xi Xi 1 X1 P Xi Xi 1 假設(shè)2 不動性 P Xi 1 Xi P Xj 1 Xj 對任意i j成立假設(shè)3 輸出獨立性 P O1 OT X1 XT P Ot Xt 一個隱馬爾可夫模型是一個五元組 X O A B 其中 X Q1 QN 狀態(tài)的有限集合 O V1 VM 觀察值的有限集合 A aij aij P Xt 1 Qj Xt Qi 轉(zhuǎn)移概率 B bik bik P Ot Vk Xt Qi 輸出概率 i i P X1 Qi 初始狀態(tài)分布 3 9隱馬爾可夫模型 續(xù) 令 A B 為給定HMM的參數(shù) 令 O1 OT為觀察值序列 隱馬爾可夫模型的三個基本問題 評估問題 對于給定模型 求某個觀察值序列的概率P 向前 向后算法 定義向前 向后變量 采用動態(tài)規(guī)劃算法 復(fù)雜度O N2T 解碼問題 對于給定模型和觀察值序列 求可能性最大的狀態(tài)序列 Viterbi算法 采用動態(tài)規(guī)劃算法 復(fù)雜度O N2T 學(xué)習(xí)問題 對于給定的一個觀察值序列 調(diào)整參數(shù) 使得觀察值出現(xiàn)的概率P 最大 向前EM算法的一個特例 帶隱變量的最大似然估計 Baum Welch算法 3 9隱馬爾可夫模型 續(xù) 向前 向后算法 定義向前 向后變量 初始化 遞歸 終結(jié) 3 9隱馬爾可夫模型 續(xù) Viterbi算法初始化 遞歸 終結(jié) 求S序列 3 9隱馬爾可夫模型 續(xù) Baum Welch算法主要步驟 1 初始模型 待訓(xùn)練模型 l0 2 基于l0以及觀察值序列s 訓(xùn)練新模型l 3 如果logP X l log P X l0 Delta 說明訓(xùn)練已經(jīng)達到預(yù)期效果 算法結(jié)束 4 否則 令l0 l 繼續(xù)第2步工作 3 10支持向量機支持向量機基本模型是針對線性可分情況下的最優(yōu)分界面提出的 在這一條件下 正類和反類訓(xùn)練樣本可用超平面完全正確地分開 設(shè)線性可分樣本集合為 xi yi i 1 n x Rd y 1 1 是類別標記 支持向量機工作的機理可描述為 尋找一個超平面w x b 0 該平面把兩類訓(xùn)練樣本點完全正確地分開 即滿足且 同時滿足兩類訓(xùn)練點到此超平面的最近距離之和 即 間隔 Margin 達到最大 滿足上述條件的分界面就是最優(yōu)分界面 經(jīng)過兩類樣本中距離最優(yōu)分類面最近的點 且平行于最優(yōu)分界面的超平面H1 H2 邊界超平面 上的訓(xùn)練樣本稱為支持向量 即圖中帶圈的點 3 10支持向量機 續(xù) 根據(jù)最近距離之和最大以及正確分離兩類樣本這兩個條件 可以構(gòu)造約束極值問題 見 1 式 通過拉格朗日乘數(shù)法并引入拉格朗日乘數(shù) 該約束極值問題就可以轉(zhuǎn)化成一個求解較為簡單的對偶問題 通過尋求該對偶問題的最優(yōu)解 就可以得到原問題的最優(yōu)解 構(gòu)造分類器判決函數(shù) 見 2 式 2 式中 sgn 是取符號函數(shù) 產(chǎn)生 1或 1兩種結(jié)果 當(dāng)測試無標記的測試數(shù)據(jù)時 根據(jù)上式的計算結(jié)果就可判斷無標記測試數(shù)據(jù)屬于正類還是反類 1 2 3 10支持向量機 續(xù) 由于噪聲或其他因素的影響 兩類數(shù)據(jù)可能有少數(shù)的融合或交叉 引入松弛變量x使得分類器在訓(xùn)練后仍可以存在一些錯分樣本 不但要使兩類樣本之間的間隔盡量大 同時還要使錯分的樣本的松弛變量之和盡可能的小 即 其中 x為松弛變量 滿足xi 0 C為大于零的折衷因子 它調(diào)和了間隔距離和錯分樣本數(shù)之間的關(guān)系 C趨近于無窮大時即為線性可分的形式 為了提高支持向量機的推廣能力 C通常取為較大的數(shù) 3 10支持向量機 續(xù) 解決線性不可分數(shù)據(jù)問題的方法是將低維空間的線性不可分數(shù)據(jù)映射到高維的線性可分空間中 支持向量機通過非線性映射f x 把數(shù)據(jù)由低維空間向高維空間映射 在高維空間為低維數(shù)據(jù)構(gòu)造線性分離超平面 該分離超平面對應(yīng)著原特征空間上的一個分割超曲面 在高維特征空間上所有涉及f x 的計算及判決函數(shù)都以f x 的內(nèi)積形式出現(xiàn) 因而可以引入一個核函數(shù)進行整體處理從而避免了對f x 的直接計算 使所有的計算仍在原空間進行 3 10支持向量機 續(xù) 統(tǒng)計學(xué)習(xí)理論認為 學(xué)習(xí)機誤判未知數(shù)據(jù)類別的實際風(fēng)險與學(xué)習(xí)機的訓(xùn)練誤差并不完全一致 對于兩類分類問題 實際風(fēng)險與學(xué)習(xí)機的訓(xùn)練誤差之間至少以1 h的概率 0 h 1 滿足下式 根據(jù)統(tǒng)計學(xué)習(xí)的理論 對于兩類分類的支持向量機 在線性可分的情況下 它的推廣誤差的上界 以1 d的概率 0 d 1 保證 為 其中 m是連續(xù)分類正確的樣本數(shù) g 1 w 是間隔距離的一半 R是一個特征空間球的半徑 它將全部樣本包含在其中 3 11關(guān)系學(xué)習(xí)關(guān)系學(xué)習(xí)所涉及的問題比傳統(tǒng)機器學(xué)習(xí)中涉及到的問題高一個層次 該類問題的假設(shè)空間龐大 結(jié)構(gòu)復(fù)雜 需要加入領(lǐng)域知識反映問題的內(nèi)在結(jié)構(gòu) 關(guān)系學(xué)習(xí)中知識的表示 原子 析取 合取 蘊含 非 驗證 等價 涵蘊等 句子由上述元素組成 一階Horn子句 僅包含一個肯定文字的子句 有三種類型的Horn子句 單一原子 事實 一個蘊涵 規(guī)則 一個否定文字的集合 目標 3 11關(guān)系學(xué)習(xí) 續(xù) 歸納邏輯編程 InductiveLogicProgramming ILP 是處理關(guān)系學(xué)習(xí)領(lǐng)域問題的重要方法 它是歸納學(xué)習(xí)和邏輯程序結(jié)合的產(chǎn)物 ILP用于一階邏輯的概念學(xué)習(xí)和邏輯程序的合成 ILP系統(tǒng)處理分類任務(wù)時主要采用兩種方式 覆蓋方法和分治方法 子句空間由形如 H L1 L2 Lm的一階子句構(gòu)成 包容關(guān)系 假設(shè)c和c 是兩個程序子句 子句c 包容子句c 如果存在一個替換 使得c c 基于ILP的常用方法有 Progol FOIL TLIDE ICL 四 模型上的模型 4 1裝袋 提升給定s個樣本的集合S 裝袋 Bagging 過程如下 對于迭代t t 1 2 T 訓(xùn)練集St采用放回選樣 由原始樣本集S選取 由于使用放回選樣 S的某些樣本可能不在St中 而其它的可能出現(xiàn)多次 由每個訓(xùn)練集St學(xué)習(xí) 得到一個分類法Ct 為對一個未知的樣本X分類 每個分類法Ct返回它的類預(yù)測 算作一票 裝袋的分類法C 統(tǒng)計得票 并將得票最高的類賦予X 通過取得票的平均值 裝袋也可以用于連續(xù)值的預(yù)測 4 1裝袋 提升 續(xù) 提升 Boosting 過程如下 每個訓(xùn)練樣本賦予一個權(quán) 并學(xué)習(xí)得到一系列分類法 對于迭代t t 1 2 T 學(xué)習(xí)得到分類法Ct后 更新權(quán) 使得隨后的分類法Ct 1 更關(guān)注 Ct的分類錯誤 最終的提升分類法C 組合每個分類法的表決 這里每個分類法的表決是其準確率的函數(shù) 通過取得票的平均值 提升算法也可以擴充到連續(xù)值預(yù)測 4 2共同訓(xùn)練 Co Training 共同訓(xùn)練算法用兩個不同的 視圖 即特征集合 來描述文本的特征 基本思路 每個視圖對應(yīng)一個學(xué)習(xí)機 而每個學(xué)習(xí)機都根據(jù)自身已學(xué)到的規(guī)律來標記 最有把握 的無標記樣本 然后將這個 或這幾個 新標記的樣本加入訓(xùn)練樣本 并擴展后的訓(xùn)練樣本提供給另一個學(xué)習(xí)機進行學(xué)習(xí) 如此反復(fù) 直到滿足一定的條件為止 該算法中所用到的兩個視圖需要滿足以下兩個條件 首先 每個特征集合對文本分類學(xué)習(xí)來說都是充分的 其次 在給定類別標記的條件下 兩個特征集合相互獨立 4 3主動學(xué)習(xí) 被動學(xué)習(xí)主動學(xué)習(xí)在學(xué)習(xí)過程中可以根據(jù)學(xué)習(xí)進程 選擇最有利于分類器性能的樣本來進一步訓(xùn)練分類器 它能有效地減少評價樣本的數(shù)量 被動學(xué)習(xí)只是隨機地選擇訓(xùn)練樣本 被動地接受這些樣本的信息進行學(xué)習(xí) 主動學(xué)習(xí)是實現(xiàn)監(jiān)督學(xué)習(xí)過程的一個有效的方法 在主動學(xué)習(xí)過程中 分類器主動地選擇對其 最有幫助 的一組子樣本進行學(xué)習(xí) 而不是被動地接受訓(xùn)練集 最有幫助 的樣本指的是對當(dāng)前分類器來說 歸屬最不確定的樣本 即當(dāng)前分類器最難以區(qū)分的樣本 通常情況下 主動學(xué)習(xí)的計算復(fù)雜度比一般的監(jiān)督學(xué)習(xí)過程要顯著得低 4 3主動學(xué)習(xí) 被動學(xué)習(xí) 續(xù) 初始狀態(tài)下 候選樣本集中所有的樣本都未帶類別標注 根據(jù)先驗知識或者隨機地從候選樣本集中選擇少量樣本并標注它們的類別 構(gòu)造初始訓(xùn)練樣本集 確保初始訓(xùn)練樣本集中至少包含有一個正例樣本和一個負例樣本 在上述初始訓(xùn)練樣本集上訓(xùn)練一個分類器 并采用某種針對該分類器采樣算法 從候選樣本集中選擇最有利于提高分類器性能的樣本 手工標注其類別并加入訓(xùn)練樣本集 再重新訓(xùn)練分類器 重復(fù)以上過程 直到候選樣本集為空或達到某種要求 主動學(xué)習(xí)是一個循環(huán)反復(fù)的過程 在主動學(xué)習(xí)的模型中 全部數(shù)據(jù)被分為兩部分 一部分是帶標簽的樣本集X 另一部分是無標簽的樣本集U 主動學(xué)習(xí)的模型還包括了一個在帶標簽的樣本集X上訓(xùn)練的學(xué)習(xí)機L和一個決策模塊q 決策模塊q用來決定U中的哪一些樣本應(yīng)該被選出標記標簽 并加入帶標簽的樣本集X 更新后的X將在下一個輪次被用于訓(xùn)練學(xué)習(xí)機L 主動學(xué)習(xí)的框架模型如圖 根據(jù)決策模塊q的不同工作機理 主動學(xué)習(xí)方法又可以被分為兩大類 其一是不確定取樣方法 另一是委員會咨詢方法 4 4直推式學(xué)習(xí)直推式學(xué)習(xí)的思想來源于前面提到的機器學(xué)習(xí)的困境 一方面獲取已知標簽的樣本代價高昂 另一方面獲取無標簽的樣本要相對容易得多 直推式學(xué)習(xí)的學(xué)習(xí)過程恰恰可以將大量無標簽的測試集樣本所攜帶的分類信息 通過迭代逐步轉(zhuǎn)移到了最終的分類器中去 由于測試樣本易于獲得 數(shù)量較多 直推式學(xué)習(xí)機能夠更好地描述整體樣本空間上的數(shù)據(jù)分布特性 使測試樣本的分類結(jié)果更為準確 4 4直推式學(xué)習(xí) 續(xù) 在多數(shù)情況下 人們只對測試文本的分類結(jié)果感興趣 這時就沒有必要非得尋求具有良好泛化能力的規(guī)則 而只要求分類器能對這些特定的文本做出正確分類即可 它在目前已知標簽樣本十分緊缺 而未知標簽樣本易于獲得的條件下 有著非常重要的現(xiàn)實意義 4 5廣義EM算法EM算法可用于許多問題框架 其中需要估計一組描述基準概率分布的參數(shù) 只給定了由此分布產(chǎn)生的全部數(shù)據(jù)中能觀察到的一部分 一般地 令X 代表在同樣的實例中未觀察到的數(shù)據(jù) 并令Y X Z代表全體數(shù)據(jù) 注意到未觀察到的Z可被看作隨機變量 它的概率分布依賴于未知參數(shù) 和已知數(shù)據(jù)X 類似地 Y是一隨機變量 因為它是由隨機變量Z來定義的 在EM算法的一般形式中 用h來代表參數(shù) 的假設(shè)值 而h 代表在EM的每次迭代中修改的假設(shè) 4 5廣義EM算法 續(xù) EM算法通過搜尋使E lnP Y h 最大的h 來尋找極大似然假設(shè)h 此期望值是在Y所遵循的概率分布上計算 此分布由未知參數(shù) 確定 首先 P Y h 是給定假設(shè)h 下全部數(shù)據(jù)Y的似然性 其合理性在于我們要尋找一個h 使該量的某函數(shù)值最大化 其次 使該量的對數(shù)lnP Y h 最大化也使P Y h 最大化 第三 引入期望值E lnP Y h 是因為全部數(shù)據(jù)Y本身也是一隨機變量 已知全部數(shù)據(jù)Y是觀察到的X和未觀察到的Z的合并 我們必須在未觀察到的Z的可能值上取平均 并以相應(yīng)的概率為權(quán)值 4 5廣義EM算法 續(xù) 在EM算法的一般形式里 重復(fù)以下兩個步驟直至收斂 步驟1 估計 E 步驟 使用當(dāng)前假設(shè)h和觀察到的數(shù)據(jù)X來估計Y上的概率分布以計算Q h h 步驟2 最大化 M 步驟 將假設(shè)h替換為使Q函數(shù)最大化的假設(shè)h 4 6強化學(xué)習(xí)強化學(xué)習(xí)的模型如圖所示通過Agent與環(huán)境的交互進行學(xué)習(xí) Agent與環(huán)境的交互接口包括行動 Action 回報 Reward 和狀態(tài) State 交互過程可以表述為如下形式 每一步 Agent根據(jù)策略選擇一個行動執(zhí)行 然后感知下一步狀態(tài)和即時回報 通過經(jīng)驗再修改自己的策略 Agent的目標就是最大化長期回報 4 6強化學(xué)習(xí) 續(xù) 馬爾可夫過程是四元組M 其中S是狀態(tài)集 A是行動集 A s 表示狀態(tài)s下可執(zhí)行的行動 T S A S 0 1 是狀態(tài)轉(zhuǎn)換模型 T s a s 表示狀態(tài)s下執(zhí)行行動a到達狀態(tài)s 的概率 且滿足 s T s a s 1 R S A S R是即時回報函數(shù) R s a s 表示狀態(tài)s下執(zhí)行行動a到達狀態(tài)s 后可以得到的即時回報 4 6強化學(xué)習(xí) 續(xù) 轉(zhuǎn)換模型和回報函數(shù)是環(huán)境的一部分 描述了環(huán)境模型 且只與當(dāng)前狀態(tài)和行動有關(guān) 與以前的狀態(tài)和行動都沒有關(guān)系 體現(xiàn)了馬爾可夫特性 Agent為了完成任務(wù) 必須知道每個行動的長遠回報 而不僅僅是即時回報 而長遠回報必須經(jīng)過一定時間的延遲之后才可以獲得 有終任務(wù)和持續(xù)任務(wù)可以統(tǒng)一起來 他們的長期回報是或 4 6強化學(xué)習(xí) 續(xù) Agent與環(huán)境交互的學(xué)習(xí)中選擇行動的方法稱為策略 S A 0 1 s a 表示在狀態(tài)s下選擇行動a的概率 策略的一個退化形式為 S A 稱為確定性策略 表示在狀態(tài)s下行動a的執(zhí)行概率為1 其它行動均為0 Q學(xué)習(xí)是最常用的強化學(xué)習(xí)技術(shù) 值函數(shù) Q函數(shù) 4 6強化學(xué)習(xí) 續(xù) 學(xué)習(xí)的目的是找到一個最優(yōu)策略 設(shè)有策略 和 若對所有狀態(tài)s S都有V s V s 則稱策略 比策略 好 這樣就總存在一個策略 它比其它所有策略都好 稱為最優(yōu)策略 若最優(yōu)策略對應(yīng)的狀態(tài)評價函數(shù)記為V 則對所有狀態(tài)s S 有V s maxV s 對所有狀態(tài)s S 所有行動a A s 有Q s maxQ s 4 6強化學(xué)習(xí) 續(xù) 三種計算 值函數(shù) V s 方法 動態(tài)規(guī)劃法 已知環(huán)境模型T和R 每步進行迭代 MonteCarlo法 沒有環(huán)境模型 根據(jù)經(jīng)驗學(xué)習(xí) 只考慮有終任務(wù) 任務(wù)結(jié)束后對所有的回報進行平均 時序差分法 沒有環(huán)境模型 根據(jù)經(jīng)驗學(xué)習(xí) 每步進行迭代 不需要等任務(wù)完成 4 6強化學(xué)習(xí) 續(xù) 在多Agent系統(tǒng)中 環(huán)境在多個Agent的聯(lián)合動作下進行狀態(tài)的遷移 對于單個Agent來講 由于其只能確定自身Agent的行為動作 因此體現(xiàn)出一種行為動作上的 部分感知 從而產(chǎn)生出另一種形式的非標準馬爾可夫環(huán)境 多Agent強化學(xué)習(xí)的技術(shù)包括 合作多Agent強化學(xué)習(xí) 適用于分布 同構(gòu) 合作環(huán)境 基于平衡解多Agent強化學(xué)習(xí) 適用于同構(gòu)或異構(gòu) 合作或競爭環(huán)境 最佳響應(yīng)多Agent強化學(xué)習(xí) 適用于異構(gòu) 競爭環(huán)境 多Agent強化學(xué)習(xí)機制被廣泛應(yīng)用到