這是數(shù)據(jù)挖掘系統(tǒng)ppt，包括了數(shù)據(jù)挖掘概述，數(shù)據(jù)預(yù)處理，數(shù)據(jù)挖掘算法－分類與預(yù)測，數(shù)據(jù)挖掘算法－聚類，數(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類型的PowerPoint.

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

數(shù)據(jù)結(jié)構(gòu)查找ppt：這是數(shù)據(jù)結(jié)構(gòu)查找ppt，包括了基本概念與術(shù)語，靜態(tài)查找表，動態(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ù)庫答辯ppt：這是數(shù)據(jù)庫答辯ppt，包括了數(shù)據(jù)庫用戶管理和安全設(shè)置，數(shù)據(jù)庫日志、作業(yè)與警報管理，復(fù)雜數(shù)據(jù)庫備份和數(shù)據(jù)庫維護(hù)，收獲與體會等內(nèi)容，歡迎點(diǎn)擊下載。