-
- 素材大。
- 2.4 MB
- 素材授權(quán):
- 免費(fèi)下載
- 素材格式:
- .ppt
- 素材上傳:
- lipeier
- 上傳時(shí)間:
- 2019-03-17
- 素材編號(hào):
- 226301
- 素材類(lèi)別:
- 課件PPT
-
素材預(yù)覽
這是數(shù)據(jù)挖掘系統(tǒng)ppt,包括了數(shù)據(jù)挖掘概述,數(shù)據(jù)預(yù)處理,數(shù)據(jù)挖掘算法-分類(lèi)與預(yù)測(cè),數(shù)據(jù)挖掘算法-聚類(lèi),數(shù)據(jù)挖掘算法-關(guān)聯(lián)分析,序列模式挖掘,數(shù)據(jù)挖掘軟件,數(shù)據(jù)挖掘應(yīng)用等內(nèi)容,歡迎點(diǎn)擊下載。
數(shù)據(jù)挖掘系統(tǒng)ppt是由紅軟PPT免費(fèi)下載網(wǎng)推薦的一款課件PPT類(lèi)型的PowerPoint.
自動(dòng)化前沿 第四講 數(shù)據(jù)挖掘技術(shù)及其應(yīng)用 宋執(zhí)環(huán) 浙江大學(xué)工業(yè)控制研究所 主要內(nèi)容 數(shù)據(jù)挖掘概述 數(shù)據(jù)預(yù)處理 數(shù)據(jù)挖掘算法-分類(lèi)與預(yù)測(cè) 數(shù)據(jù)挖掘算法-聚類(lèi) 數(shù)據(jù)挖掘算法-關(guān)聯(lián)分析 序列模式挖掘 數(shù)據(jù)挖掘軟件 數(shù)據(jù)挖掘應(yīng)用 一、數(shù)據(jù)挖掘概述 數(shù)據(jù)挖掘概念 數(shù)據(jù)挖掘--從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù),是統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫(kù)技術(shù)和人工智能技術(shù)的綜合。 數(shù)據(jù)挖掘是從數(shù)據(jù)中自動(dòng)地抽取模式、關(guān)聯(lián)、變化、異常和有意義的結(jié)構(gòu); 數(shù)據(jù)挖掘大部分的價(jià)值在于利用數(shù)據(jù)挖掘技術(shù)改善預(yù)測(cè)模型。 數(shù)據(jù)挖掘與KDD 知識(shí)發(fā)現(xiàn)(KD) 輸出的是規(guī)則 數(shù)據(jù)挖掘(DM) 輸出的是模型 共同點(diǎn) 兩種方法輸入的都是學(xué)習(xí)集(learning sets) 目的都是盡可能多的自動(dòng)化數(shù)據(jù)挖掘過(guò)程 數(shù)據(jù)挖掘過(guò)程并不能完全自動(dòng)化,只能半自動(dòng)化 異常檢測(cè) 異常檢測(cè)是數(shù)據(jù)挖掘中一個(gè)重要方面,用來(lái)發(fā)現(xiàn)”小的模式”(相對(duì)于聚類(lèi)),即數(shù)據(jù)集中間顯著不同于其它數(shù)據(jù)的對(duì)象。 異常探測(cè)應(yīng)用 電信和信用卡欺騙 貸款審批 藥物研究 氣象預(yù)報(bào) 金融領(lǐng)域 客戶(hù)分類(lèi) 網(wǎng)絡(luò)入侵檢測(cè) 故障檢測(cè)與診斷等 什么是異常(outlier)? Hawkins(1980)給出了異常的本質(zhì)性的定義:異常是在數(shù)據(jù)集中與眾不同的數(shù)據(jù),使人懷疑這些數(shù)據(jù)并非隨機(jī)偏差,而是產(chǎn)生于完全不同的機(jī)制。 聚類(lèi)算法對(duì)異常的定義:異常是聚類(lèi)嵌于其中的背景噪聲。 異常檢測(cè)算法對(duì)異常的定義:異常是既不屬于聚類(lèi)也不屬于背景噪聲的點(diǎn)。他們的行為與正常的行為有很大不同。 異常檢測(cè)方法的分類(lèi) 基于統(tǒng)計(jì)(statistical-based)的方法 基于距離 (distance-based)的方法 基于偏差(deviation-based)的方法 基于密度(density-based)的方法 高維數(shù)據(jù)的異常探測(cè) 數(shù)據(jù)挖掘系統(tǒng)的特征 數(shù)據(jù)的特征 知識(shí)的特征 算法的特征 數(shù)據(jù)的特征 大容量 POS數(shù)據(jù)(某個(gè)超市每天要處理高達(dá)2000萬(wàn)筆交易) 衛(wèi)星圖象(NASA的地球觀測(cè)衛(wèi)星以每小時(shí)50GB的速度發(fā)回?cái)?shù)據(jù)) 互聯(lián)網(wǎng)數(shù)據(jù) 含噪音(不完全、不正確) 異質(zhì)數(shù)據(jù)(多種數(shù)據(jù)類(lèi)型混合的數(shù)據(jù)源,來(lái)自互聯(lián)網(wǎng)的數(shù)據(jù)是典型的例子) 系統(tǒng)的特征 知識(shí)發(fā)現(xiàn)系統(tǒng)需要一個(gè)前處理過(guò)程 數(shù)據(jù)抽取 數(shù)據(jù)清洗 數(shù)據(jù)選擇 數(shù)據(jù)轉(zhuǎn)換 知識(shí)發(fā)現(xiàn)系統(tǒng)是一個(gè)自動(dòng)/半自動(dòng)過(guò)程 知識(shí)發(fā)現(xiàn)系統(tǒng)要有很好的性能 知識(shí)(模式)的特征 知識(shí)發(fā)現(xiàn)系統(tǒng)能夠發(fā)現(xiàn)什么知識(shí)? 計(jì)算學(xué)習(xí)理論COLT(Computational Learning Theory) 以FOL為基礎(chǔ)的以發(fā)現(xiàn)關(guān)系為目的的歸納邏輯程序設(shè)計(jì) 現(xiàn)行的知識(shí)發(fā)現(xiàn)系統(tǒng)只能發(fā)現(xiàn)特定模式的知識(shí) 規(guī)則 分類(lèi) 關(guān)聯(lián) 知識(shí)表示:規(guī)則 IF 條件 THEN 結(jié)論 條件和結(jié)論的粒度(抽象度)可以有多種 單值 區(qū)間 模糊值 規(guī)則可以有確信度 精確規(guī)則 概率規(guī)則 知識(shí)表示:分類(lèi)樹(shù) 數(shù)據(jù)挖掘算法的特征 構(gòu)成數(shù)據(jù)挖掘算法的三要素 模式記述語(yǔ)言:反映了算法可以發(fā)現(xiàn)什么樣的知識(shí) 模式評(píng)價(jià):反映了什么樣的模式可以稱(chēng)為知識(shí) 模式探索:包括針對(duì)某一特定模式對(duì)參數(shù)空間的探索和對(duì)模式空間的探索 數(shù)據(jù)挖掘的主要方法 分類(lèi)(Classification) 聚類(lèi)(Clustering) 相關(guān)規(guī)則(Association Rule) 回歸(Regression) 其他 數(shù)據(jù)挖掘系統(tǒng) 數(shù)據(jù)挖掘系統(tǒng) 第一代數(shù)據(jù)挖掘系統(tǒng) 支持一個(gè)或少數(shù)幾個(gè)數(shù)據(jù)挖掘算法,這些算法設(shè)計(jì)用來(lái)挖掘向量數(shù)據(jù)(vector-valued data),這些數(shù)據(jù)模型在挖掘時(shí)候,一般一次性調(diào)進(jìn)內(nèi)存進(jìn)行處理。許多這樣的系統(tǒng)已經(jīng)商業(yè)化。 第二代數(shù)據(jù)挖掘系統(tǒng) 目前的研究,是改善第一代數(shù)據(jù)挖掘系統(tǒng),開(kāi)發(fā)第二代數(shù)據(jù)挖掘系統(tǒng)。第二代數(shù)據(jù)挖掘系統(tǒng)支持?jǐn)?shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù),和它們具有高性能的接口,具有高的可擴(kuò)展性。例如,第二代系統(tǒng)能夠挖掘大數(shù)據(jù)集、更復(fù)雜的數(shù)據(jù)集、以及高維數(shù)據(jù)。這一代系統(tǒng)通過(guò)支持?jǐn)?shù)據(jù)挖掘模式(data mining schema)和數(shù)據(jù)挖掘查詢(xún)語(yǔ)言(DMQL)增加系統(tǒng)的靈活性。 數(shù)據(jù)挖掘系統(tǒng) 第三代數(shù)據(jù)挖掘系統(tǒng) 第三代的特征是能夠挖掘Internet/Extranet的分布式和高度異質(zhì)的數(shù)據(jù),并且能夠有效地和操作型系統(tǒng)集成。這一代數(shù)據(jù)挖掘系統(tǒng)關(guān)鍵的技術(shù)之一是提供對(duì)建立在異質(zhì)系統(tǒng)上的多個(gè)預(yù)言模型以及管理這些預(yù)言模型的元數(shù)據(jù)提供第一級(jí)別(first class)的支持。 第四代數(shù)據(jù)挖掘系統(tǒng) 第四代數(shù)據(jù)挖掘系統(tǒng)能夠挖掘嵌入式系統(tǒng)、移動(dòng)系統(tǒng)、和普遍存在(ubiquitous)計(jì)算設(shè)備產(chǎn)生的各種類(lèi)型的數(shù)據(jù) 。 二、數(shù)據(jù)預(yù)處理 為什么需要預(yù)處理 數(shù)據(jù) 不完整 含觀測(cè)噪聲 不一致 包含其它不希望的成分 數(shù)據(jù)清理通過(guò)填寫(xiě)空缺值,平滑噪聲數(shù)據(jù),識(shí)別刪除孤立點(diǎn),并解決不一致來(lái)清理數(shù)據(jù)。 污染數(shù)據(jù)形成的原因 濫用縮寫(xiě)詞 數(shù)據(jù)輸入錯(cuò)誤 數(shù)據(jù)中的內(nèi)嵌控制信息 不同的慣用語(yǔ) 重復(fù)記錄 丟失值 拼寫(xiě)變化 不同的計(jì)量單位 過(guò)時(shí)的編碼 含有各種噪聲 數(shù)據(jù)清理的重要性 污染數(shù)據(jù)的普遍存在,使得在大型數(shù)據(jù)庫(kù)中維護(hù)數(shù)據(jù)的正確性和一致性成為一個(gè)及其困難的任務(wù)。 垃圾進(jìn)、垃圾出 數(shù)據(jù)清理處理內(nèi)容 格式標(biāo)準(zhǔn)化 異常數(shù)據(jù)清除 錯(cuò)誤糾正 重復(fù)數(shù)據(jù)的清除 數(shù)據(jù)規(guī)約 數(shù)據(jù)集的壓縮表示,但是能和原始數(shù)據(jù)集達(dá)到相同或基本相同的分析結(jié)果 主要策略: 數(shù)據(jù)聚集 維規(guī)約 數(shù)據(jù)壓縮 數(shù)值規(guī)約 空缺值 忽略元組 人工填寫(xiě)空缺值 使用固定值 使用屬性平均值 使用最有可能值 噪聲數(shù)據(jù) 如何平滑數(shù)據(jù),去掉噪聲 數(shù)據(jù)平滑技術(shù) 分箱 聚類(lèi) 計(jì)算機(jī)和人工檢查相結(jié)合 回歸 分箱 箱的深度:表示不同的箱里有相同個(gè)數(shù)的數(shù)據(jù)。 箱的寬度:每個(gè)箱值的取值區(qū)間是個(gè)常數(shù)。 平滑方法: 按箱平均值平滑 按箱中值平滑 按箱邊界值平滑 聚類(lèi) 每個(gè)簇中的數(shù)據(jù)用其中心值代替 忽略孤立點(diǎn) 先通過(guò)聚類(lèi)等方法找出孤立點(diǎn)。這些孤立點(diǎn)可能包含有用的信息。 人工再審查這些孤立點(diǎn) 回歸 通過(guò)構(gòu)造函數(shù)來(lái)符合數(shù)據(jù)變化的趨勢(shì),這樣可以用一個(gè)變量預(yù)測(cè)另一個(gè)變量。 線性回歸 多線性回歸 數(shù)據(jù)集成 將多個(gè)數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來(lái)存放在一個(gè)一直得數(shù)據(jù)存貯中。 實(shí)體識(shí)別 實(shí)體和模式的匹配 冗余:某個(gè)屬性可以由別的屬性推出。 相關(guān)分析 相關(guān)性rA,B . rA,B>0,正相關(guān)。A隨B的值得增大而增大 rA,B>0,正相關(guān)。AB無(wú)關(guān) rA,B>0,正相關(guān)。A隨B的值得增大而減少 重復(fù) 同一數(shù)據(jù)存儲(chǔ)多次 數(shù)據(jù)值沖突的檢測(cè)和處理 數(shù)據(jù)變換 平滑 聚集 數(shù)據(jù)概化 規(guī)范化 屬性構(gòu)造(特征構(gòu)造) 最小 最大規(guī)范化 小數(shù)定標(biāo)規(guī)范化 屬性構(gòu)造 由給定的屬性構(gòu)造和添加新的屬性,以幫助提高精度和對(duì)高維數(shù)據(jù)結(jié)構(gòu)的理解 數(shù)據(jù)立方體聚集 尋找感興趣的維度進(jìn)行再聚集 維規(guī)約 刪除不相關(guān)的屬性(維)來(lái)減少數(shù)據(jù)量。 屬性子集選擇 找出最小屬性集合,使得數(shù)據(jù)類(lèi)的概率分布盡可能地接近使用所有屬性的原分布 如何選? 貪心算法 逐步向前選擇 逐步后向刪除 向前選擇和后向刪除相結(jié)合 判定樹(shù)歸納 數(shù)據(jù)壓縮 有損,無(wú)損 小波變換 將數(shù)據(jù)向量D轉(zhuǎn)換成為數(shù)值上不同的小波系數(shù)的向量D’. 對(duì)D’進(jìn)行剪裁,保留小波系數(shù)最強(qiáng)的部分。 數(shù)值規(guī)約 回歸和對(duì)數(shù)線形模型 線形回歸 對(duì)數(shù)線形模型 直方圖 等寬 等深 V-最優(yōu) maxDiff 數(shù)值規(guī)約 聚類(lèi) 多維索引樹(shù) : 對(duì)于給定的數(shù)據(jù)集合,索引樹(shù)動(dòng)態(tài)的劃分多維空間。 選樣 簡(jiǎn)單選擇n個(gè)樣本,不放回 簡(jiǎn)單選擇n個(gè)樣本,放回 聚類(lèi)選樣 分層選樣 離散化和概念分層 離散化技術(shù)用來(lái)減少給定連續(xù)屬性的個(gè)數(shù) 通常是遞歸的。 大量時(shí)間花在排序上。 對(duì)于給定的數(shù)值屬性,概念分層定義了該屬性的一個(gè)離散化的值。 分箱 直方圖分析 數(shù)值數(shù)據(jù)離散化 聚類(lèi)分析 基于熵的離散化 通過(guò)自然劃分分段 3-4-5規(guī)則 如果一個(gè)區(qū)間最高有效位上包括3 6 9 個(gè)不同的值,劃分為3個(gè)等寬區(qū)間。 7個(gè)不同值,按2-3-3劃分為3個(gè)區(qū)間 最高位包含2,4,8個(gè)不同值,劃分為4個(gè)等寬區(qū)間 最高位包含1 ,5,10個(gè)不同值,劃分為5個(gè)等寬區(qū)間 最高分層一般在第5個(gè)百分位到第95個(gè)百分位上進(jìn)行 分類(lèi)數(shù)據(jù)的概念分層生成 分類(lèi)數(shù)據(jù)是離散數(shù)據(jù)。一個(gè)分類(lèi)屬性可能有有限個(gè)不同的值。 方法 由用戶(hù)和專(zhuān)家在模式級(jí)顯式的說(shuō)明屬性的部分序 通過(guò)顯式的數(shù)據(jù)分組說(shuō)明分層結(jié)構(gòu)的一部分 說(shuō)明屬性集,但不說(shuō)明他們的偏序 只說(shuō)明部分的屬性集 三、數(shù)據(jù)挖掘算法-分類(lèi)與預(yù)測(cè) 分類(lèi) VS. 預(yù)測(cè) 分類(lèi): 預(yù)測(cè)分類(lèi)標(biāo)號(hào)(或離散值) 根據(jù)訓(xùn)練數(shù)據(jù)集和類(lèi)標(biāo)號(hào)屬性,構(gòu)建模型來(lái)分類(lèi)現(xiàn)有數(shù)據(jù),并用來(lái)分類(lèi)新數(shù)據(jù) 預(yù)測(cè): 建立連續(xù)函數(shù)值模型,比如預(yù)測(cè)空缺值 典型應(yīng)用 信譽(yù)證實(shí) 目標(biāo)市場(chǎng) 醫(yī)療診斷 性能預(yù)測(cè) 數(shù)據(jù)分類(lèi):兩步過(guò)程 第一步,建立一個(gè)模型,描述預(yù)定數(shù)據(jù)類(lèi)集和概念集 假定每個(gè)元組屬于一個(gè)預(yù)定義的類(lèi),由一個(gè)類(lèi)標(biāo)號(hào)屬性確定 基本概念 訓(xùn)練數(shù)據(jù)集:由為建立模型而被分析的數(shù)據(jù)元組形成 訓(xùn)練樣本:訓(xùn)練數(shù)據(jù)集中的單個(gè)樣本(元組) 學(xué)習(xí)模型可以用分類(lèi)規(guī)則、判定樹(shù)或數(shù)學(xué)公式的形式提供 第二步,使用模型,對(duì)將來(lái)的或未知的對(duì)象進(jìn)行分類(lèi) 首先評(píng)估模型的預(yù)測(cè)準(zhǔn)確率 對(duì)每個(gè)測(cè)試樣本,將已知的類(lèi)標(biāo)號(hào)和該樣本的學(xué)習(xí)模型類(lèi)預(yù)測(cè)比較 模型在給定測(cè)試集上的準(zhǔn)確率是正確被模型分類(lèi)的測(cè)試樣本的百分比 測(cè)試集要獨(dú)立于訓(xùn)練樣本集,否則會(huì)出現(xiàn)“過(guò)分適應(yīng)數(shù)據(jù)”的情況 第一步:建立模型 第二步:用模型進(jìn)行分類(lèi) 準(zhǔn)備分類(lèi)和預(yù)測(cè)的數(shù)據(jù) 通過(guò)對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,可以提高分類(lèi)和預(yù)測(cè)過(guò)程的準(zhǔn)確性、有效性和可伸縮性 數(shù)據(jù)清理 消除或減少噪聲,處理空缺值,從而減少學(xué)習(xí)時(shí)的混亂 相關(guān)性分析 數(shù)據(jù)中的有些屬性可能與當(dāng)前任務(wù)不相關(guān);也有些屬性可能是冗余的;刪除這些屬性可以加快學(xué)習(xí)步驟,使學(xué)習(xí)結(jié)果更精確 數(shù)據(jù)變換 可以將數(shù)據(jù)概化到較高層概念,或?qū)?shù)據(jù)進(jìn)行規(guī)范化 比較分類(lèi)方法 使用下列標(biāo)準(zhǔn)比較分類(lèi)和預(yù)測(cè)方法 預(yù)測(cè)的準(zhǔn)確率:模型正確預(yù)測(cè)新數(shù)據(jù)的類(lèi)編號(hào)的能力 速度:產(chǎn)生和使用模型的計(jì)算花銷(xiāo) 魯棒性:給定噪聲數(shù)據(jù)或有空缺值的數(shù)據(jù),模型正確預(yù)測(cè)的能力 可伸縮性:對(duì)大量數(shù)據(jù),有效的構(gòu)建模型的能力 可解釋性:學(xué)習(xí)模型提供的理解和洞察的層次 用判定樹(shù)歸納分類(lèi) 什么是判定樹(shù)? 類(lèi)似于流程圖的樹(shù)結(jié)構(gòu) 每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試 每個(gè)分枝代表一個(gè)測(cè)試輸出 每個(gè)樹(shù)葉節(jié)點(diǎn)代表類(lèi)或類(lèi)分布 判定樹(shù)的生成由兩個(gè)階段組成 判定樹(shù)構(gòu)建 開(kāi)始時(shí),所有的訓(xùn)練樣本都在根節(jié)點(diǎn) 遞歸的通過(guò)選定的屬性,來(lái)劃分樣本 (必須是離散值) 樹(shù)剪枝 許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點(diǎn),樹(shù)剪枝試圖檢測(cè)和剪去這種分枝 判定樹(shù)的使用:對(duì)未知樣本進(jìn)行分類(lèi) 通過(guò)將樣本的屬性值與判定樹(shù)相比較 判定歸納樹(shù)算法 判定歸納樹(shù)算法(一個(gè)貪心算法) 自頂向下的分治方式構(gòu)造判定樹(shù) 樹(shù)以代表訓(xùn)練樣本的單個(gè)根節(jié)點(diǎn)開(kāi)始 使用分類(lèi)屬性(如果是量化屬性,則需先進(jìn)行離散化) 遞歸的通過(guò)選擇相應(yīng)的測(cè)試屬性,來(lái)劃分樣本,一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上,就不在該節(jié)點(diǎn)的任何后代上出現(xiàn) 測(cè)試屬性是根據(jù)某種啟發(fā)信息或者是統(tǒng)計(jì)信息來(lái)進(jìn)行選擇(如:信息增益) 遞歸劃分步驟停止的條件 給定節(jié)點(diǎn)的所有樣本屬于同一類(lèi) 沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本——使用多數(shù)表決 沒(méi)有剩余的樣本 貝葉斯分類(lèi) 貝葉斯分類(lèi)利用統(tǒng)計(jì)學(xué)中的貝葉斯定理,來(lái)預(yù)測(cè)類(lèi)成員的概率,即給定一個(gè)樣本,計(jì)算該樣本屬于一個(gè)特定的類(lèi)的概率。 樸素貝葉斯分類(lèi):假設(shè)每個(gè)屬性之間都是相互獨(dú)立的,并且每個(gè)屬性對(duì)非類(lèi)問(wèn)題產(chǎn)生的影響都是一樣的。 后向傳播分類(lèi) 后向傳播是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法;神經(jīng)網(wǎng)絡(luò)是一組連接的輸入/輸出單元,每個(gè)連接都與一個(gè)權(quán)相連。在學(xué)習(xí)階段,通過(guò)調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán),使得能夠預(yù)測(cè)輸入樣本的正確標(biāo)號(hào)來(lái)學(xué)習(xí)。 優(yōu)點(diǎn) 預(yù)測(cè)精度總的來(lái)說(shuō)較高 健壯性好,訓(xùn)練樣本中包含錯(cuò)誤時(shí)也可正常工作 輸出可能是離散值、連續(xù)值或者是離散或量化屬性的向量值 對(duì)目標(biāo)進(jìn)行分類(lèi)較快 缺點(diǎn) 訓(xùn)練(學(xué)習(xí))時(shí)間長(zhǎng) 蘊(yùn)涵在學(xué)習(xí)的權(quán)中的符號(hào)含義很難理解 很難根專(zhuān)業(yè)領(lǐng)域知識(shí)相整合 其他分類(lèi)方法 k-最臨近分類(lèi) 給定一個(gè)未知樣本,k-最臨近分類(lèi)法搜索模式空間,找出最接近未知樣本的k個(gè)訓(xùn)練樣本;然后使用k個(gè)最臨近者中最公共的類(lèi)來(lái)預(yù)測(cè)當(dāng)前樣本的類(lèi)標(biāo)號(hào) 基于案例的推理 樣本或案例使用復(fù)雜的符號(hào)表示,對(duì)于新案例,先檢測(cè)是否存在同樣的訓(xùn)練案例;如果找不到,則搜索類(lèi)似的訓(xùn)練案例 遺傳算法 結(jié)合生物進(jìn)化思想的算法 粗糙集方法 模糊集方法 允許在分類(lèi)規(guī)則中定義“模糊的”臨界值或邊界 什么是預(yù)測(cè)? 預(yù)測(cè)是構(gòu)造和使用模型評(píng)估無(wú)樣本類(lèi),或評(píng)估給定樣本可能具有的屬性或值空間。 預(yù)測(cè)和分類(lèi)的異同 相同點(diǎn) 兩者都需要構(gòu)建模型 都用模型來(lái)估計(jì)未知值 預(yù)測(cè)當(dāng)中主要的估計(jì)方法是回歸分析 線性回歸和多元回歸 非線性回歸 不同點(diǎn) 分類(lèi)法主要是用來(lái)預(yù)測(cè)類(lèi)標(biāo)號(hào)(分類(lèi)屬性值) 預(yù)測(cè)法主要是用來(lái)估計(jì)連續(xù)值(量化屬性值) 回歸方法 線性回歸:Y = + X 其中和是回歸系數(shù),可以根據(jù)給定的數(shù)據(jù)點(diǎn),通過(guò)最小二乘法來(lái)求得 多元回歸:Y = + 1X1 + 2 X2 線性回歸的擴(kuò)展,設(shè)計(jì)多個(gè)預(yù)測(cè)變量,可以用最小二乘法求得上式中的,1 和2 非線性回歸:Y = + 1X1 + 2 X22+ 3 X33 對(duì)不呈線性依賴(lài)的數(shù)據(jù)建模 使用多項(xiàng)式回歸建模方法,然后進(jìn)行變量變換,將非線性模型轉(zhuǎn)換為線性模型,然后用最小二乘法求解 評(píng)估分類(lèi)法的準(zhǔn)確性 導(dǎo)出分類(lèi)法后,再使用訓(xùn)練數(shù)據(jù)評(píng)估分類(lèi)法,可能錯(cuò)誤的導(dǎo)致樂(lè)觀的估計(jì) 保持方法 給定數(shù)據(jù)隨機(jī)劃分為兩個(gè)集合:訓(xùn)練集(2/3)和測(cè)試集(1/3) 訓(xùn)練集導(dǎo)出分類(lèi)法,測(cè)試集對(duì)其準(zhǔn)確性進(jìn)行評(píng)估 隨機(jī)子選樣:保持方法的一個(gè)變形,將保持方法重復(fù)k次,然后取準(zhǔn)確率的平均值 k-折交叉確認(rèn) 初始數(shù)據(jù)被劃分為k個(gè)不相交的,大小大致相同的子集S1,S2…Sk 進(jìn)行k次訓(xùn)練和測(cè)試,第i次時(shí),以Si做測(cè)試集,其他做訓(xùn)練集 準(zhǔn)確率為k次迭代正確分類(lèi)數(shù)除以初始數(shù)據(jù)集樣本總數(shù) 提高分類(lèi)法的準(zhǔn)確性 Bagging技術(shù)和boosting技術(shù)都通過(guò)將T個(gè)學(xué)習(xí)得到的分類(lèi)法C1,C2…CT組合起來(lái),從而創(chuàng)造一個(gè)改進(jìn)的分類(lèi)法C* Bagging技術(shù) 對(duì)訓(xùn)練集S進(jìn)行T次迭代,每次通過(guò)放回取樣選取樣本集St,通過(guò)學(xué)習(xí)St得到分類(lèi)法Ct 對(duì)于未知樣本X,每個(gè)分類(lèi)法返回其類(lèi)預(yù)測(cè),作為一票 C*統(tǒng)計(jì)得票,并將得票最高的預(yù)測(cè)賦予X Boosting技術(shù) 每個(gè)訓(xùn)練樣本賦予一個(gè)權(quán)值 Ct的權(quán)值取決于其錯(cuò)誤率 四、數(shù)據(jù)挖掘算法-聚類(lèi) 聚類(lèi)分析 什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要聚類(lèi)分析方法分類(lèi) 劃分方法(Partitioning Methods) 分層方法 基于密度的方法 基于表格的方法 基于模型(Model-Based)的聚類(lèi)方法 異常分析 總結(jié) 什么是聚類(lèi)分析? 簇(Cluster):一個(gè)數(shù)據(jù)對(duì)象的集合 在同一個(gè)類(lèi)中,對(duì)象之間0具有相似性; 不同類(lèi)的對(duì)象之間是相異的。 聚類(lèi)分析 把一個(gè)給定的數(shù)據(jù)對(duì)象集合分成不同的簇; 聚類(lèi)是一種無(wú)監(jiān)督分類(lèi)法: 沒(méi)有預(yù)先指定的類(lèi)別; 典型的應(yīng)用 作為一個(gè)獨(dú)立的分析工具,用于了解數(shù)據(jù)的分布; 作為其它算法的一個(gè)數(shù)據(jù)預(yù)處理步驟; 聚類(lèi)的常規(guī)應(yīng)用 模式識(shí)別 空間數(shù)據(jù)分析 在GIS中,通過(guò)聚類(lèi)發(fā)現(xiàn)特征空間來(lái)建立主題索引; 在空間數(shù)據(jù)挖掘中,檢測(cè)并解釋空間中的簇; 圖象處理 經(jīng)濟(jì)學(xué) (尤其是市場(chǎng)研究方面) WWW 文檔分類(lèi) 分析WEB日志數(shù)據(jù)來(lái)發(fā)現(xiàn)相似的訪問(wèn)模式 應(yīng)用聚類(lèi)分析的例子 市場(chǎng)銷(xiāo)售: 幫助市場(chǎng)人員發(fā)現(xiàn)客戶(hù)中的不同群體,然后用這些知識(shí)來(lái)開(kāi)展一個(gè)目標(biāo)明確的市場(chǎng)計(jì)劃; 土地使用: 在一個(gè)陸地觀察數(shù)據(jù)庫(kù)中標(biāo)識(shí)那些土地使用相似的地區(qū); 保險(xiǎn): 對(duì)購(gòu)買(mǎi)了汽車(chē)保險(xiǎn)的客戶(hù),標(biāo)識(shí)那些有較高平均賠償成本的客戶(hù); 城市規(guī)劃: 根據(jù)類(lèi)型、價(jià)格、地理位置等來(lái)劃分不同類(lèi)型的住宅; 地震研究: 根據(jù)地質(zhì)斷層的特點(diǎn)把已觀察到的地震中心分成不同的類(lèi); 聚類(lèi)方法性能評(píng)價(jià) 一個(gè)好的聚類(lèi)方法要能產(chǎn)生高質(zhì)量的聚類(lèi)結(jié)果——簇,這些簇要具備以下兩個(gè)特點(diǎn): 高的簇內(nèi)相似性 低的簇間相似性 聚類(lèi)結(jié)果的好壞取決于該聚類(lèi)方法采用的相似性評(píng)估方法以及該方法的具體實(shí)現(xiàn); 聚類(lèi)方法的好壞還取決與該方法是能發(fā)現(xiàn)某些還是所有的隱含模式; 聚類(lèi)方法性能評(píng)價(jià) 可伸縮性 能夠處理不同類(lèi)型的屬性 能發(fā)現(xiàn)任意形狀的簇 在決定輸入?yún)?shù)的時(shí)候,盡量不需要特定的領(lǐng)域知識(shí); 能夠處理噪聲和異常 對(duì)輸入數(shù)據(jù)對(duì)象的順序不敏感 能處理高維數(shù)據(jù) 能產(chǎn)生一個(gè)好的、能滿足用戶(hù)指定約束的聚類(lèi)結(jié)果 結(jié)果是可解釋的、可理解的和可用的 兩種數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)矩陣 (two modes) 差異度矩陣 (one mode) 評(píng)價(jià)聚類(lèi)質(zhì)量 差異度/相似度矩陣: 相似度通常用距離函數(shù)來(lái)表示; 有一個(gè)單獨(dú)的質(zhì)量評(píng)估函數(shù)來(lái)評(píng)判一個(gè)簇的好壞; 對(duì)不同類(lèi)型的變量,距離函數(shù)的定義通常是不同的,這在下面有詳細(xì)討論; 根據(jù)實(shí)際的應(yīng)用和數(shù)據(jù)的語(yǔ)義,在計(jì)算距離的時(shí)候,不同的變量有不同的權(quán)值相聯(lián)系; 很難定義“足夠相似了”或者“足夠好了” 只能憑主觀確定; 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 區(qū)間標(biāo)度變量(Interval-scaled variables): 二元變量(Binary variables): 標(biāo)稱(chēng)型,序數(shù)型和比例型變量(Nominal, ordinal, and ratio variables): 混合類(lèi)型變量(Variables of mixed types): 區(qū)間標(biāo)度變量 數(shù)據(jù)標(biāo)準(zhǔn)化 計(jì)算絕對(duì)偏差的平均值: 其中 計(jì)算標(biāo)準(zhǔn)度量值 (z-score) 使用絕對(duì)偏差的平均值比使用標(biāo)準(zhǔn)偏差更健壯(robust) 計(jì)算對(duì)象之間的相異度 通常使用距離來(lái)衡量?jī)蓚(gè)對(duì)象之間的相異度。 常用的距離度量方法有: 明考斯基距離( Minkowski distance): 其中 i = (xi1, xi2, …, xip) 和 j = (xj1, xj2, …, xjp) 是兩個(gè)p維的數(shù)據(jù)對(duì)象, q是一個(gè)正整數(shù)。 當(dāng)q = 1時(shí), d 稱(chēng)為曼哈坦距離( Manhattan distance) 計(jì)算對(duì)象之間的相異度 當(dāng)q=2時(shí), d 就成為歐幾里德距離: 距離函數(shù)有如下特性: d(i,j) 0 d(i,i) = 0 d(i,j) = d(j,i) d(i,j) d(i,k) + d(k,j) 可以根據(jù)每個(gè)變量的重要性賦予一個(gè)權(quán)重 序數(shù)型變量 一個(gè)序數(shù)型變量可以是離散的也可以是連續(xù)的 離散的序數(shù)型變量類(lèi)似于標(biāo)稱(chēng)變量,除了它的M個(gè)狀態(tài)是以有意義的序列排序的,比如職稱(chēng) 連續(xù)的序數(shù)型變量類(lèi)似于區(qū)間標(biāo)度變量,但是它沒(méi)有單位,值的相對(duì)順序是必要的,而其實(shí)際大小并不重要。 序數(shù)型變量 相異度的計(jì)算 與區(qū)間標(biāo)度變量的計(jì)算方法相類(lèi)似 將xif 用它對(duì)應(yīng)的秩代替 將每個(gè)變量的值域映射到[0.0,1.0]上,使得每個(gè)變量都有相同的權(quán)重。這通過(guò)用zif來(lái)替代rif來(lái)實(shí)現(xiàn) 用前面所述的區(qū)間標(biāo)度變量的任一種距離計(jì)算方法來(lái)計(jì)算 比例標(biāo)度型變量 比例標(biāo)度型變量(Ratio-scaled variable) : 總是取正的度量值,有一個(gè)非線性的標(biāo)度,近似的遵循指數(shù)標(biāo)度,比如 AeBt or Ae-Bt 計(jì)算相異度的方法: 采用與處理區(qū)間標(biāo)度變量相同的方法 — 不是一個(gè)好的選擇 進(jìn)行對(duì)數(shù)變換,對(duì)變換得到的值在采用與處理區(qū)間標(biāo)度變量相同的方法 yif = log(xif) 將其作為連續(xù)的序數(shù)型數(shù)據(jù),將其秩作為區(qū)間標(biāo)度的值來(lái)對(duì)待。 混合類(lèi)型的變量 一個(gè)數(shù)據(jù)庫(kù)可能包含了所有這6中類(lèi)型的變量 用以下公式計(jì)算對(duì)象i,j之間的相異度. 其中,p為對(duì)象中的變量個(gè)數(shù) 如果xif或xjf 缺失(即對(duì)象i或?qū)ο骿沒(méi)有變量f的值),或者xif = xjf =0,且變量f是不對(duì)稱(chēng)的二元變量,則指示項(xiàng)δij(f)=0;否則δij(f)=1 混合類(lèi)型的變量 f 是二元變量或標(biāo)稱(chēng)變量: if xif = xjf dij(f) = 0, else dij(f) = 1 f 是區(qū)間標(biāo)度變量: dij(f) = | xif-xjf |/maxhxhf-minhxhf 其中h遍取變量f的所有非空缺對(duì)象 f 是序數(shù)型或比例標(biāo)度型 計(jì)算秩 rif 計(jì)算 zif并將其作為區(qū)間標(biāo)度變量值對(duì)待 主要聚類(lèi)方法 Partitioning algorithms: Construct various partitions and then evaluate them by some criterion Hierarchy algorithms: Create a hierarchical decomposition of the set of data (or objects) using some criterion Density-based: based on connectivity and density functions Grid-based: based on a multiple-level granularity structure Model-based: A model is hypothesized for each of the clusters and the idea is to find the best fit of that model to each other 五、數(shù)據(jù)挖掘算法-關(guān)聯(lián) 什么是關(guān)聯(lián)挖掘? 關(guān)聯(lián)規(guī)則:基本概念 規(guī)則度量:支持度與可信度 關(guān)聯(lián)規(guī)則挖掘:路線圖 關(guān)聯(lián)規(guī)則挖掘—一個(gè)例子 關(guān)鍵步驟:挖掘頻繁集 多層關(guān)聯(lián)規(guī)則 項(xiàng)通常具有層次 底層的項(xiàng)通常支持度也低 某些特定層的規(guī)則可能更有意義 交易數(shù)據(jù)庫(kù)可以按照維或?qū)泳幋a 可以進(jìn)行共享的多維挖掘 挖掘多層關(guān)聯(lián)規(guī)則 自上而下,深度優(yōu)先的方法: 先找高層的“強(qiáng)”規(guī)則: 牛奶 ® 面包 [20%, 60%]. 再找他們底層的“弱”規(guī)則: 酸奶 ® 黃面包 [6%, 50%]. 多層關(guān)聯(lián)規(guī)則的變種 層次交叉的關(guān)聯(lián)規(guī)則: 酸奶 ® 面包房 黃面包 不同種分層方法間的關(guān)聯(lián)規(guī)則: 酸奶 ® 面包房面包 多層關(guān)聯(lián)規(guī)則 支持度不變: 在各層之間使用統(tǒng)一的支持度 + 一個(gè)最小支持度閾值. 如果一個(gè)項(xiàng)集的父項(xiàng)集不具有最小支持度,那他本身也不可能滿足最小支持度。 – 底層項(xiàng)不會(huì)成為頻繁集,如果支持度 太高 丟失底層關(guān)聯(lián)規(guī)則 太低 生成太多的高層關(guān)聯(lián)規(guī)則 支持度遞減: 隨著層次的降低支持度遞減 4種搜索策略: 層與層獨(dú)立 用k-項(xiàng)集跨層過(guò)濾 用項(xiàng)跨層過(guò)濾 用項(xiàng)進(jìn)行可控跨層過(guò)濾 支持度不變 支持度遞減 多層關(guān)聯(lián):冗余過(guò)濾 由于“祖先”關(guān)系的原因,有些規(guī)則可能是多余的。 例子 牛奶 白面包 [support = 8%, confidence = 70%] 酸奶 白面包 [support = 2%, confidence = 72%] 我們稱(chēng)第一個(gè)規(guī)則是第二個(gè)規(guī)則的祖先 參考規(guī)則的祖先,如果他的支持度與我們“預(yù)期”的支持度近似的話,我們就說(shuō)這條規(guī)則是冗余的。 多層挖掘:深度優(yōu)先 自頂向下,深度優(yōu)先的方法: 先挖掘高層頻繁項(xiàng): 牛奶 (15%), 面包 (10%) 再挖掘他們底層的相對(duì)較弱的頻繁項(xiàng): 酸奶 (5%), 白面包 (4%) 跨層時(shí)對(duì)支持度的不同處理方法,對(duì)應(yīng)了不同的算法: 層之間支持度不變: 如果t的祖先是非頻繁的,則不用考慮t 支持度隨層遞減: 則只考慮那些其祖先是頻繁的/不可忽略的項(xiàng) 數(shù)據(jù)挖掘查詢(xún)的逐步精化 為什么要逐步精化 挖掘操作的代價(jià)可能高或低,結(jié)果可能細(xì)致或粗糙 在速度和質(zhì)量之間折衷:逐步精化 超集覆蓋特征: 預(yù)存儲(chǔ)所有正面答案—允許進(jìn)一步正確性驗(yàn)證,而不必驗(yàn)證已經(jīng)錯(cuò)誤的 2或多步挖掘: 先執(zhí)行粗糙的、容易的操作 (超集覆蓋) 然后在減少后的候選集上進(jìn)行計(jì)算量大的算法 (Koperski & Han, SSD’95). 逐步求精空間關(guān)聯(lián)規(guī)則挖掘 逐步求精空間關(guān)聯(lián)規(guī)則挖掘 空間關(guān)聯(lián)規(guī)則的兩步算法: 步驟 1: 粗糙空間計(jì)算 (用于過(guò)濾) 用 MBR 或 R-tree 做粗糙估計(jì) 步驟 2: 細(xì)致空間算法 (用于精化) 只計(jì)算已經(jīng)通過(guò)空間計(jì)算的對(duì)象 多維關(guān)聯(lián)規(guī)則:概念 單維規(guī)則: buys(X, “milk”) buys(X, “bread”) 多維規(guī)則: 2個(gè)以上維/謂詞 維間關(guān)聯(lián)規(guī)則 (維詞不重復(fù)) age(X,”19-25”) occupation(X,“student”) buys(X,“coke”) 混合維關(guān)聯(lián)規(guī)則 (維詞重復(fù)) age(X,”19-25”) buys(X, “popcorn”) buys(X, “coke”) 類(lèi)別屬性 有限個(gè)值, 值之間無(wú)順序關(guān)系 數(shù)量屬性 數(shù)字的,值之間隱含了順序關(guān)系 挖掘多維關(guān)聯(lián)的技術(shù) 搜索頻繁k-維詞集合: 如: {age, occupation, buys} 是一個(gè)3-維詞集合。 按照對(duì) age 處理方式的不同,分為: 1. 用靜態(tài)方法把數(shù)值屬性離散化 數(shù)值屬性可用預(yù)定義的概念層次加以離散化。 2. 帶數(shù)量的關(guān)聯(lián)規(guī)則 根據(jù)數(shù)據(jù)的分布動(dòng)態(tài)的把數(shù)值屬性離散化到不同的“箱”。 3. 基于距離的關(guān)聯(lián)規(guī)則 用數(shù)據(jù)點(diǎn)之間的距離動(dòng)態(tài)的離散化 數(shù)值屬性的靜態(tài)離散化 帶數(shù)量的關(guān)聯(lián)規(guī)則 ARCS (關(guān)聯(lián)規(guī)則聚集系統(tǒng)) ARCS 流程 1. 分箱 2. 查找頻繁維詞 集合 3. 聚集 4. 優(yōu)化 ARCS的局限性 基于距離的關(guān)聯(lián)規(guī)則挖掘 分箱的方法沒(méi)有體現(xiàn)數(shù)據(jù)間隔的語(yǔ)義 基于距離的分割是更有“意義”的離散化方法,考慮: 區(qū)間內(nèi)密度或點(diǎn)的個(gè)數(shù) 區(qū)間內(nèi)點(diǎn)的“緊密程度 聚集和距離度量 聚集和距離度量 六、序列模式挖掘 序列模式概念 序列模式的概念最早是由Agrawal和Srikant 提出的 序列模式定義:給定一個(gè)由不同序列組成的集合,其中,每個(gè)序列由不同的元素按順序有序排列,每個(gè)元素由不同項(xiàng)目組成,同時(shí)給定一個(gè)用戶(hù)指定的最小支持度閾值,序列模式挖掘就是找出所有的頻繁子序列,即該子序列在序列集中的出現(xiàn)頻率不低于用戶(hù)指定的最小支持度閾值 序列模式實(shí)例 例1:在兩年前購(gòu)買(mǎi)了Ford 牌轎車(chē)的顧客,很有可能在今年采取貼舊換新的購(gòu)車(chē)行動(dòng) 例2:在購(gòu)買(mǎi)了自行車(chē)和購(gòu)物籃的所有客戶(hù)中,有70%的客戶(hù)會(huì)在兩個(gè)月后購(gòu)買(mǎi)打氣筒 例3:工業(yè)過(guò)程控制領(lǐng)域:過(guò)程變量采樣值時(shí)時(shí)間序列;變量之間的關(guān)系是動(dòng)態(tài)的;系統(tǒng)故障模式;等等 序列模式應(yīng)用領(lǐng)域 應(yīng)用領(lǐng)域: 客戶(hù)購(gòu)買(mǎi)行為模式預(yù)測(cè) Web訪問(wèn)模式預(yù)測(cè) 疾病診斷 自然災(zāi)害預(yù)測(cè) DNA序列分析 工業(yè)控制 序列模式表示 符號(hào)化表示: 項(xiàng)目集(Itemset)是各種項(xiàng)目組成的集合 序列(Sequence)是不同項(xiàng)目集(ItemSet)的有序排列,序列s可以表示為s =
數(shù)據(jù)結(jié)構(gòu)查找ppt:這是數(shù)據(jù)結(jié)構(gòu)查找ppt,包括了基本概念與術(shù)語(yǔ),靜態(tài)查找表,動(dòng)態(tài)查找表,哈希表查找,小結(jié)與習(xí)題等內(nèi)容,歡迎點(diǎn)擊下載。
數(shù)據(jù)結(jié)構(gòu)ppt最短路徑:這是數(shù)據(jù)結(jié)構(gòu)ppt最短路徑,包括了最短路徑的定義,Dijkstra算法,F(xiàn)loyd算法,F(xiàn)loyd算法——C++描述等內(nèi)容,歡迎點(diǎn)擊下載。
數(shù)據(jù)庫(kù)答辯ppt:這是數(shù)據(jù)庫(kù)答辯ppt,包括了數(shù)據(jù)庫(kù)用戶(hù)管理和安全設(shè)置,數(shù)據(jù)庫(kù)日志、作業(yè)與警報(bào)管理,復(fù)雜數(shù)據(jù)庫(kù)備份和數(shù)據(jù)庫(kù)維護(hù),收獲與體會(huì)等內(nèi)容,歡迎點(diǎn)擊下載。