【正文】 于 金 霞 計算機科學(xué)與技術(shù)學(xué)院 信息管理與信息系統(tǒng)專業(yè) 課程 第三講 數(shù)據(jù)挖掘技術(shù) 主要內(nèi)容 ? 一、數(shù)據(jù)挖掘概述 ? 二、數(shù)據(jù)預(yù)處理 ? 三、數(shù)據(jù)挖掘算法－分類與預(yù)測 ? 四、數(shù)據(jù)挖掘算法－聚類 ? 五、數(shù)據(jù)挖掘算法－關(guān)聯(lián)分析 ? 六、序列模式挖掘 ? 七、數(shù)據(jù)挖掘軟件 ? 八、數(shù)據(jù)挖掘應(yīng)用 一、數(shù)據(jù)挖掘概述 數(shù)據(jù)挖掘概念 ? 數(shù)據(jù)挖掘 從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，是統(tǒng)計學(xué)、數(shù)據(jù)庫技術(shù)和人工智能技術(shù)的綜合。 ? 數(shù)據(jù)挖掘是從數(shù)據(jù)中自動地抽取模式、關(guān)聯(lián)、變化、異常和有意義的結(jié)構(gòu) ； ? 數(shù)據(jù)挖掘大部分的價值在于利用數(shù)據(jù)挖掘技術(shù)改善預(yù)測模型 。 數(shù)據(jù)挖掘與 KDD 數(shù)據(jù)挖掘與 KDD ? 知識發(fā)現(xiàn)（ KD） ? 輸出的是規(guī)則 ? 數(shù)據(jù)挖掘（ DM） ? 輸出的是模型 ? 共同點 ? 兩種方法輸入的都是學(xué)習(xí)集（ learning sets） ? 目的都是盡可能多的自動化數(shù)據(jù)挖掘過程 ? 數(shù)據(jù)挖掘過程并不能完全自動化，只能半自動化 數(shù)據(jù)挖掘的社會需求 國民經(jīng)濟和社會的信息化 ? 社會信息化后，社會的運轉(zhuǎn)是軟件的運轉(zhuǎn) ? 社會信息化后，社會的歷史是數(shù)據(jù)的歷史 數(shù)據(jù)挖掘的社會需求 數(shù)據(jù)挖掘 數(shù)據(jù)庫越來越大 有價值的知識 可怕的數(shù)據(jù) 數(shù)據(jù)挖掘的社會需求 數(shù)據(jù)爆炸，知識貧乏 苦惱 : 淹沒在數(shù)據(jù)中 。 不能制定合適的決策 ! 數(shù)據(jù) 知識 決策 ? 模式 ? 趨勢 ? 事實 ? 關(guān)系 ? 模型 ? 關(guān)聯(lián)規(guī)則 ? 序列 ? 目標(biāo)市場 ? 資金分配 ? 貿(mào)易選擇 ? 在哪兒做廣告 ? 銷售的地理位置 ? 金融 ? 經(jīng)濟 ? 政府 ? POS. ? 人口統(tǒng)計 ? 生命周期 數(shù)據(jù)挖掘的發(fā)展 ? 1989 IJCAI會議： 數(shù)據(jù)庫中的知識發(fā)現(xiàn)討論專題 ? Knowledge Discovery in Databases (G. PiatetskyShapiro and W. Frawley, 1991) ? 19911994 KDD討論專題 ? Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. PiatetskyShapiro, P. Smyth, and R. Uthurusamy, 1996) ? 19951998 KDD國際會議 (KDD’9598) ? Journal of Data Mining and Knowledge Discovery (1997) ? 1998 ACM SIGKDD, SIGKDD’19992022 會議 ,以及 SIGKDD Explorations ? 數(shù)據(jù)挖掘方面更多的國際會議 ? PAKDD, PKDD, SIAMData Mining, (IEEE) ICDM, DaWaK, SPIEDM, etc. 數(shù)據(jù)挖掘技術(shù) ? 技術(shù)分類 ? 預(yù)言（ Predication）：用歷史預(yù)測未來 ? 描述（ Description）：了解數(shù)據(jù)中潛在的規(guī)律 ? 數(shù)據(jù)挖掘技術(shù) ? 關(guān)聯(lián)分析 ? 序列模式 ? 分類（ 預(yù)言 ） ? 聚集 ? 異常檢測 異常檢測 ? 異常檢測是數(shù)據(jù)挖掘中一個重要方面，用來發(fā)現(xiàn) ” 小的模式 ” (相對于聚類 )，即數(shù)據(jù)集中間顯著不同于其它數(shù)據(jù)的對象。 ? 異常探測應(yīng)用 ?電信和信用卡欺騙 ?貸款審批 ?藥物研究 ?氣象預(yù)報 ?金融領(lǐng)域 ?客戶分類 ?網(wǎng)絡(luò)入侵檢測 ?故障檢測與診斷等 什么是異常（ outlier）？ ? Hawkins(1980)給出了異常的本質(zhì)性的定義： 異常是在數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非隨機偏差，而是產(chǎn)生于完全不同的機制。 ? 聚類算法對異常的定義： 異常是聚類嵌于其中的背景噪聲。 ? 異常檢測算法對異常的定義： 異常是既不屬于聚類也不屬于背景噪聲的點。他們的行為與正常的行為有很大不同。 異常檢測方法的分類 ? 基于統(tǒng)計（ statisticalbased)的方法 ? 基于距離 (distancebased)的方法 ? 基于偏差 (deviationbased)的方法 ? 基于密度 (densitybased)的方法 ? 高維數(shù)據(jù)的異常探測 數(shù)據(jù)挖掘系統(tǒng)的特征 ?數(shù)據(jù)的特征 ?知識的特征 ?算法的特征 礦山（數(shù)據(jù)） 挖掘工具（算法） 金子（知識） 數(shù)據(jù)的特征 ?大容量 ? POS數(shù)據(jù)（某個超市每天要處理高達 2022萬筆交易） ? 衛(wèi)星圖象（ NASA的地球觀測衛(wèi)星以每小時 50GB的速度發(fā)回數(shù)據(jù)） ? 互聯(lián)網(wǎng)數(shù)據(jù) ?含噪音（不完全、不正確） ?異質(zhì)數(shù)據(jù)（多種數(shù)據(jù)類型混合的數(shù)據(jù)源，來自互聯(lián)網(wǎng)的數(shù)據(jù)是典型的例子） 系統(tǒng)的特征 ?知識發(fā)現(xiàn)系統(tǒng)需要一個前處理過程 ? 數(shù)據(jù)抽取 ? 數(shù)據(jù)清洗 ? 數(shù)據(jù)選擇 ? 數(shù)據(jù)轉(zhuǎn)換 ?知識發(fā)現(xiàn)系統(tǒng)是一個自動 /半自動過程 ?知識發(fā)現(xiàn)系統(tǒng)要有很好的性能 知識（模式）的特征 ?知識發(fā)現(xiàn)系統(tǒng)能夠發(fā)現(xiàn)什么知識？ ?計算學(xué)習(xí)理論 COLT（ Computational Learning Theory） ?以 FOL為基礎(chǔ)的以發(fā)現(xiàn)關(guān)系為目的的歸納邏輯程序設(shè)計 ?現(xiàn)行的知識發(fā)現(xiàn)系統(tǒng)只能發(fā)現(xiàn)特定模式的知識 ?規(guī)則 ?分類 ?關(guān)聯(lián) 知識表示：規(guī)則 ? IF 條件 THEN 結(jié)論 ? 條件和結(jié)論的粒度（抽象度）可以有多種 ? 單值 ? 區(qū)間 ? 模糊值 ? 規(guī)則可以有確信度 ? 精確規(guī)則 ? 概率規(guī)則 知識表示：分類樹 分類條件 1 分類條件 2 分類條件 3 類 1 類 2 類 3 類 4 數(shù)據(jù)挖掘算法的特征 ?構(gòu)成數(shù)據(jù)挖掘算法的三要素 ?模式記述語言：反映了算法可以發(fā)現(xiàn)什么樣的知識 ?模式評價：反映了什么樣的模式可以稱為知識 ?模式探索：包括針對某一特定模式對參數(shù)空間的探索和對模式空間的探索 數(shù)據(jù)挖掘的主要方法 ?分類（ Classification） ?聚類 (Clustering) ?相關(guān)規(guī)則 (Association Rule) ?回歸 (Regression) ?其他 數(shù)據(jù)挖掘系統(tǒng) 代 特征 數(shù)據(jù)挖掘算法 集成 分布計算模型 數(shù)據(jù)模型 第一代 數(shù)據(jù)挖掘作為一個獨立的應(yīng)用 支持一個或者多個算法 獨立的系統(tǒng) 單個機器 向量數(shù)據(jù) 第二代 和數(shù)據(jù)庫以及數(shù)據(jù)倉庫集成 多個算法：能夠挖掘一次不能放進內(nèi)存的數(shù)據(jù) 數(shù)據(jù)管理系統(tǒng) ， 包括數(shù)據(jù)庫和數(shù)據(jù)倉庫 同質(zhì) /局部區(qū)域的計算機群集 有些系統(tǒng)支持對象 、 文本 、 和連續(xù)的媒體數(shù)據(jù) 第三代 和預(yù)言模型系統(tǒng)集成 多個算法 數(shù)據(jù)管理和預(yù)言模型系統(tǒng) intra/extra 網(wǎng)絡(luò)計算 支持半結(jié)構(gòu)化數(shù)據(jù)和web數(shù)據(jù) 第四代 和移動數(shù)據(jù) /各種計算數(shù)據(jù)聯(lián)合 多個算法 數(shù)據(jù)管理 、預(yù)言模型 、移動系統(tǒng) 移動和各種計算設(shè)備 普遍存在的計算模型 數(shù)據(jù)挖掘系統(tǒng) ? 第一代數(shù)據(jù)挖掘系統(tǒng) ? 支持一個或少數(shù)幾個數(shù)據(jù)挖掘算法 ， 這些算法設(shè)計用來挖掘向量數(shù)據(jù) （ vectorvalued data） ， 這些數(shù)據(jù)模型在挖掘時候 ， 一般一次性調(diào)進內(nèi)存進行處理 。 許多這樣的系統(tǒng)已經(jīng)商業(yè)化 。 ? 第二代數(shù)據(jù)挖掘系統(tǒng) ? 目前的研究，是改善第一代數(shù)據(jù)挖掘系統(tǒng)，開發(fā)第二代數(shù)據(jù)挖掘系統(tǒng)。第二代數(shù)據(jù)挖掘系統(tǒng)支持?jǐn)?shù)據(jù)庫和數(shù)據(jù)倉庫，和它們具有高性能的接口，具有高的可擴展性。例如，第二代系統(tǒng)能夠挖掘大數(shù)據(jù)集、更復(fù)雜的數(shù)據(jù)集、以及高維數(shù)據(jù)。這一代系統(tǒng)通過支持?jǐn)?shù)據(jù)挖掘模式（ data mining schema）和數(shù)據(jù)挖掘查詢語言（ DMQL）增加系統(tǒng)的靈活性。 數(shù)據(jù)挖掘系統(tǒng) ? 第三代數(shù)據(jù)挖掘系統(tǒng) ? 第三代的特征是能夠挖掘 Inter/Extra的分布式和高度異質(zhì)的數(shù)據(jù)，并且能夠有效地和操作型系統(tǒng)集成。這一代數(shù)據(jù)挖掘系統(tǒng)關(guān)鍵的技術(shù)之一是提供對建立在異質(zhì)系統(tǒng)上的多個預(yù)言模型以及管理這些預(yù)言模型的元數(shù)據(jù)提供第一級別（ first class）的支持。 ? 第四代數(shù)據(jù)挖掘系統(tǒng) ? 第四代數(shù)據(jù)挖掘系統(tǒng)能夠挖掘嵌入式系統(tǒng)、移動系統(tǒng)、和普遍存在（ ubiquitous）計算設(shè)備產(chǎn)生的各種類型的數(shù)據(jù) 。 二、數(shù)據(jù)預(yù)處理 為什么需要預(yù)處理 ? 數(shù)據(jù) ? 不完整 ? 含觀測噪聲 ? 不一致 ? 包含其它不希望的成分 ? 數(shù)據(jù)清理通過填寫空缺值，平滑噪聲數(shù)據(jù)，識別刪除孤立點，并解決不一致來清理數(shù)據(jù)。 污染數(shù)據(jù)形成的原因 ? 濫用縮寫詞 ? 數(shù)據(jù)輸入錯誤 ? 數(shù)據(jù)中的內(nèi)嵌控制信息 ? 不同的慣用語 ? 重復(fù)記錄 ? 丟失值 ? 拼寫變化 ? 不同的計量單位 ? 過時的編碼 ? 含有各種噪聲 數(shù)據(jù)清理的重要性 1. 污染數(shù)據(jù)的普遍存在，使得在大型數(shù)據(jù)庫中維護數(shù)據(jù)的正確性和一致性成為一個及其困難的任務(wù)。 2. 垃圾進、垃圾出 數(shù)據(jù)清理處理內(nèi)容 ? 格式標(biāo)準(zhǔn)化 ? 異常數(shù)據(jù)清除 ? 錯誤糾正 ? 重復(fù)數(shù)據(jù)的清除 數(shù)據(jù)規(guī)約 ? 數(shù)據(jù)集的壓縮表示，但是能和原始數(shù)據(jù)集達到相同或基本相同的分析結(jié)果 ? 主要策略 : ? 數(shù)據(jù)聚集 ? 維規(guī)約 ? 數(shù)據(jù)壓縮 ? 數(shù)值規(guī)約 空缺值 ? 忽略元組 ? 人工填寫空缺值 ? 使用固定值 ? 使用屬性平均值 ? 使用最有可能值 噪聲數(shù)據(jù) ? 如何平滑數(shù)據(jù)，去掉噪聲 ? 數(shù)據(jù)平滑技術(shù) ? 分箱 ? 聚類 ? 計算機和人工檢查相結(jié)合 ? 回歸 分箱 ? 箱的深度：表示不同的箱里有相同個數(shù)的數(shù)據(jù)。 ? 箱的寬度：每個箱值的取值區(qū)間是個常數(shù)。 ? 平滑方法 : ? 按箱平均值平滑 ? 按箱中值平滑 ? 按箱邊界值平滑 聚類 ? 每個簇中的數(shù)據(jù)用其中心值代替 ? 忽略孤立點 ? 先通過聚類等方法找出孤立點。這些孤立點可能包含有用的信息。 ? 人工再審查這些孤立點 回歸 ? 通過構(gòu)造函數(shù)來符合數(shù)據(jù)變化的趨勢，這樣可以用一個變量預(yù)測另一個變量。 ? 線性回歸 ? 多線性回歸 數(shù)據(jù)集成 ? 將多個數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來存放在一個一直得數(shù)據(jù)存貯中。 ? 實體識別 實體和模式的匹配 ? 冗余：某個屬性可以由別的屬性推出。 ?相關(guān)分析 ?相關(guān)性 rA,B . rA,B0,正相關(guān)。 A隨 B的值得增大而增大 rA,B0,正相關(guān)。 AB無關(guān) rA,B0,正相關(guān)。 A隨 B的值得增大而減少 ? 重復(fù) 同一數(shù)據(jù)存儲多次 ? 數(shù)據(jù)值沖突的檢測和處理 數(shù)據(jù)變換 ? 平滑 ? 聚集 ? 數(shù)據(jù)概化 ? 規(guī)范化 ? 屬性構(gòu)造 (特征構(gòu)造 ) ? 最小 最大規(guī)范化 ? 小數(shù)定標(biāo)規(guī)范化 ? 屬性構(gòu)造 ? 由給定的屬性構(gòu)造和添加新的屬性，以幫助提高精度和對高維數(shù)據(jù)結(jié)構(gòu)的理解 規(guī)范化 數(shù)據(jù)立方體聚集 ? 尋找感興趣的維度進行再聚集 維規(guī)約 ? 刪除不相關(guān)的屬性（維）來減少數(shù)據(jù)量。 ? 屬性子集選擇 ? 找出最小屬性集合，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布 ? 如何選??？ 貪心算法 逐步向前選擇 逐步后向刪除 向前選擇和后向刪除相結(jié)合 判定樹歸納 數(shù)據(jù)壓縮 ? 有損，無損 ? 小波變換 ? 將數(shù)據(jù)向量 D轉(zhuǎn)換成為數(shù)值上不同的小波系數(shù)的向量D’. ? 對 D’進行剪裁，保留小波系數(shù)最強的部分。 ?主要成分分析 數(shù)值規(guī)約 ? 回歸和對數(shù)線形模型 ? 線形回歸 ? 對數(shù)線形模型 ? 直方圖 ? 等寬 ? 等深 ? V最優(yōu) ? maxDiff 數(shù)值規(guī)約 ? 聚類 ? 多維索引樹 ： 對于給定的數(shù)據(jù)集合，索引樹動態(tài)的劃分多維空間。 ? 選樣 ? 簡單選擇 n個樣本，不放回 ? 簡單選擇 n個樣本，放回 ? 聚類選樣 ? 分層選樣 離散化和概念分層 ? 離散化技術(shù)用來減少給定連續(xù)屬性的個數(shù) ? 通常是遞歸的。 ? 大量時間花在排序上。 ? 對于給定的數(shù)值屬性，概念分層定義了該屬性的一個離散化的值。 ? 分箱 ? 直方圖分析 數(shù)值數(shù)據(jù)離散化 ?聚類