【正文】 = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 3% 牛奶 [support = 10%] 多層關(guān)聯(lián)：冗余過濾 ? 由于 “ 祖先 ” 關(guān)系的原因，有些規(guī)則可能是多余的。 ? 舉例： ? 規(guī)則形式： “ Body ???ead [support, confidence]‖. ? buys(x, ―diapers‖) ?? buys(x, ―beers‖) [%, 60%] ? major(x, ―CS‖) ^ takes(x, ―DB‖) ???grade(x, ―A‖) [1%, 75%] 關(guān)聯(lián)規(guī)則：基本概念 ? 給定 : (1)交易數(shù)據(jù)庫 (2)每筆交易是：一個項目列表 (消費者一次購買活動中購買的商品 ) ? 查找 : 所有 描述一個項目集合與其他項目集合相關(guān)性的規(guī)則 ? ., 98% of people who purchase tires and auto accessories also get automotive services done ? 應(yīng)用 ? * ? 護理用品 (商店應(yīng)該怎樣提高護理用品的銷售？ ) ? 家用電器 ? * (其他商品的庫存有什么影響 ?) ? 在產(chǎn)品直銷中使用 附加郵寄 ? Detecting ―pingpong‖ing of patients, faulty ―collisions‖ 規(guī)則度量：支持度與可信度 ?查找所有的規(guī)則 X amp。 混合類型的變量 ? 一個數(shù)據(jù)庫可能包含了所有這 6中類型的變量 用以下公式計算對象 i， j之間的相異度 . 其中， p為對象中的變量個數(shù) 如果 xif或 xjf 缺失（即對象 i或?qū)ο?j沒有變量 f的值），或者 xif = xjf =0，且變量 f是不對稱的二元變量，則指示項 δij(f)=0；否則δij(f)=1 )(1)()(1),(fijpffijfijpf djid???????混合類型的變量 ? f 是二元變量或標稱變量 : if xif = xjf dij(f) = 0, else dij(f) = 1 ? f 是區(qū)間標度變量 : dij(f) = | xifxjf |/maxhxhfminhxhf 其中 h遍取變量 f的所有非空缺對象 ? f 是序數(shù)型或比例標度型 計算秩 rif 計算 zif并將其作為區(qū)間標度變量值對待 11???fifMrz if主要聚類方法 ? Partitioning algorithms: Construct various partitions and then evaluate them by some criterion ? Hierarchy algorithms: Create a hierarchical deposition of the set of data (or objects) using some criterion ? Densitybased: based on connectivity and density functions ? Gridbased: based on a multiplelevel granularity structure ? Modelbased: 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ī)則挖掘： ? 在交易數(shù)據(jù)、關(guān)系數(shù)據(jù)或其他信息載體中，查找存在于項目集合或?qū)ο蠹现g的頻繁模式、關(guān)聯(lián)、相關(guān)性、或因果結(jié)構(gòu)。 序數(shù)型變量 ?相異度的計算 與區(qū)間標度變量的計算方法相類似 ?將 xif 用它對應(yīng)的秩代替 ?將每個變量的值域映射到 [， ]上，使得每個變量都有相同的權(quán)重。 ? 常用的距離度量方法有 : 明考斯基距離 （ Minkowski distance） : 其中 i = (xi1, xi2, … , xip) 和 j = (xj1, xj2, … , xjp) 是兩個 p維的數(shù)據(jù)對象 , q是一個正整數(shù)。 ? 優(yōu)點 ? 預(yù)測精度總的來說較高 ? 健壯性好，訓(xùn)練樣本中包含錯誤時也可正常工作 ? 輸出可能是離散值、連續(xù)值或者是離散或量化屬性的向量值 ? 對目標進行分類較快 ? 缺點 ? 訓(xùn)練（學(xué)習(xí)）時間長 ? 蘊涵在學(xué)習(xí)的權(quán)中的符號含義很難理解 ? 很難根專業(yè)領(lǐng)域知識相整合 其他分類方法 ? k最臨近分類 ? 給定一個未知樣本， k最臨近分類法搜索模式空間，找出最接近未知樣本的 k個訓(xùn)練樣本；然后使用 k個最臨近者中最公共的類來預(yù)測當前樣本的類標號 ? 基于案例的推理 ? 樣本或案例使用復(fù)雜的符號表示，對于新案例，先檢測是否存在同樣的訓(xùn)練案例；如果找不到，則搜索類似的訓(xùn)練案例 ? 遺傳算法 ? 結(jié)合生物進化思想的算法 ? 粗糙集方法 ? 模糊集方法 ? 允許在分類規(guī)則中定義“模糊的”臨界值或邊界 什么是預(yù)測？ ? 預(yù)測是構(gòu)造和使用模型評估無樣本類，或評估給定樣本可能具有的屬性或值空間。 )()()|()|(DPhPhDPDhP ?后向傳播分類 ? 后向傳播是一種神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法；神經(jīng)網(wǎng)絡(luò)是一組連接的輸入 /輸出單元，每個連接都與一個權(quán)相連。 ? 方法 ? 由用戶和專家在模式級顯式的說明屬性的部分序 ? 通過顯式的數(shù)據(jù)分組說明分層結(jié)構(gòu)的一部分 ? 說明屬性集，但不說明他們的偏序 ? 只說明部分的屬性集 三、數(shù)據(jù)挖掘算法 －分類與預(yù)測 分類 VS. 預(yù)測 ?分類： ?預(yù)測分類標號（或離散值） ?根據(jù)訓(xùn)練數(shù)據(jù)集和類標號屬性，構(gòu)建模型來分類現(xiàn)有數(shù)據(jù)，并用來分類新數(shù)據(jù) ?預(yù)測： ?建立連續(xù)函數(shù)值模型，比如預(yù)測空缺值 ?典型應(yīng)用 ?信譽證實 ?目標市場 ?醫(yī)療診斷 ?性能預(yù)測 數(shù)據(jù)分類：兩步過程 ? 第一步，建立一個模型，描述預(yù)定數(shù)據(jù)類集和概念集 ? 假定每個元組屬于一個預(yù)定義的類，由一個類標號屬性確定 ? 基本概念 訓(xùn)練數(shù)據(jù)集 ：由為建立模型而被分析的數(shù)據(jù)元組形成 訓(xùn)練樣本 ：訓(xùn)練數(shù)據(jù)集中的單個樣本（元組） ? 學(xué)習(xí)模型可以用分類規(guī)則、判定樹或數(shù)學(xué)公式的形式提供 ? 第二步，使用模型，對將來的或未知的對象進行分類 ? 首先評估模型的預(yù)測準確率 對每個測試樣本，將已知的類標號和該樣本的學(xué)習(xí)模型類預(yù)測比較 模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比 測試集要獨立于訓(xùn)練樣本集，否則會出現(xiàn)“過分適應(yīng)數(shù)據(jù)”的情況 第一步：建立模型 訓(xùn)練數(shù) 據(jù)集 N A M E RANK Y E A R S T E N U R E DM ik e A s s is t a n t P r o f 3 noM a r y A s s is t a n t P r o f 7 y e sB il l P r o f e s s o r 2 y e sJ im A s s o c ia t e P r o f 7 y e sD a v e A s s is t a n t P r o f 6 noA n n e A s s o c ia t e P r o f 3 no分類算法 IF rank = ‘professor’ OR years 6 THEN tenured = ‘yes’ 分類規(guī)則 第二步：用模型進行分類 分類規(guī)則 測試集 N A M E RANK Y E A R S T E N U R E DT o m A s s i s t a n t P r o f 2 noM e r l i s a A s s o c i a t e P r o f 7 noG e o r g e P r o f e s s o r 5 y e sJ o s e p h A s s i s t a n t P r o f 7 y e s未知數(shù)據(jù) (Jeff, Professor, 4) Tenured? 準備分類和預(yù)測的數(shù)據(jù) ? 通過對數(shù)據(jù)進行預(yù)處理，可以提高分類和預(yù)測過程的準確性、有效性和可伸縮性 ? 數(shù)據(jù)清理 消除或減少噪聲，處理空缺值，從而減少學(xué)習(xí)時的混亂 ? 相關(guān)性分析 數(shù)據(jù)中的有些屬性可能與當前任務(wù)不相關(guān)；也有些屬性可能是冗余的；刪除這些屬性可以加快學(xué)習(xí)步驟，使學(xué)習(xí)結(jié)果更精確 ? 數(shù)據(jù)變換 可以將數(shù)據(jù)概化到較高層概念，或?qū)?shù)據(jù)進行規(guī)范化 比較分類方法 ? 使用下列標準比較分類和預(yù)測方法 ? 預(yù)測的準確率：模型正確預(yù)測新數(shù)據(jù)的類編號的能力 ? 速度：產(chǎn)生和使用模型的計算花銷 ? 魯棒性：給定噪聲數(shù)據(jù)或有空缺值的數(shù)據(jù)，模型正確預(yù)測的能力 ? 可伸縮性：對大量數(shù)據(jù)，有效的構(gòu)建模型的能力 ? 可解釋性：學(xué)習(xí)模型提供的理解和洞察的層次 用判定樹歸納分類 ? 什么是判定樹？ ? 類似于流程圖的樹結(jié)構(gòu) ? 每個內(nèi)部節(jié)點表示在一個屬性上的測試 ? 每個分枝代表一個測試輸出 ? 每個樹葉節(jié)點代表類或類分布 ? 判定樹的生成由兩個階段組成 ? 判定樹構(gòu)建 開始時，所有的訓(xùn)練樣本都在根節(jié)點 遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） ? 樹剪枝 許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝 ? 判定樹的使用：對未知樣本進行分類 ? 通過將樣本的屬性值與判定樹相比較 判定歸納樹算法 ? 判定歸納樹算法（一個貪心算法） ? 自頂向下的分治方式構(gòu)造判定樹 ? 樹以代表訓(xùn)練樣本的單個根節(jié)點開始 ? 使用分類屬性（如果是量化屬性，則需先進行離散化） ? 遞歸的通過選擇相應(yīng)的 測試屬性 ，來劃分樣本，一旦一個屬性出現(xiàn)在一個節(jié)點上，就不在該節(jié)點的任何后代上出現(xiàn) ? 測試屬性是根據(jù)某種啟發(fā)信息或者是統(tǒng)計信息來進行選擇（如：信息增益） ? 遞歸劃分步驟停止的條件 ? 給定節(jié)點的所有樣本屬于同一類 ? 沒有剩余屬性可以用來進一步劃分樣本 —— 使用多數(shù)表決 ? 沒有剩余的樣本 貝葉斯分類 ? 貝葉斯分類利用統(tǒng)計學(xué)中的貝葉斯定理，來預(yù)測類成員的概率，即給定一個樣本，計算該樣本屬于一個特定的類的概率。 7個不同值，按 233劃分為 3個區(qū)間 ?最高位包含 2， 4， 8個不同值，劃分為 4個等寬區(qū)間 ?最高位包含 1 ， 5， 10個不同值，劃分為 5個等寬區(qū)間 ?最高分層一般在第 5個百分位到第 95個百分位上進行 分類數(shù)據(jù)的概念分層生成 ? 分類數(shù)據(jù)是離散數(shù)據(jù)。 ? 對于給定的數(shù)值屬性，概念分層定義了該屬性的一個離散化的值。 ? 選樣 ? 簡單選擇 n個樣本，不放回 ? 簡單選擇 n個樣本，放回 ? 聚類選樣 ? 分層選樣 離散化和概念分層 ? 離散化技術(shù)用來減少給定連續(xù)屬性的個數(shù) ? 通常是遞歸的。 ? 屬性子集選擇 ? 找出最小屬性集合，使得數(shù)據(jù)類的概率分布盡可能地接近使用所有屬性的原分布 ? 如何選??？ 貪心算法 逐步向前選擇 逐步后向刪除 向前選擇和后向刪除相結(jié)合 判定樹歸納 數(shù)據(jù)壓縮 ? 有損，無損 ? 小波變換 ? 將數(shù)據(jù)向量 D轉(zhuǎn)換成為數(shù)值上不同的小波系數(shù)的向量D’. ? 對 D’進行剪裁，保留小波系數(shù)最強的部分。 AB無關(guān) rA,B0,正相關(guān)。 ?相關(guān)分析 ?相關(guān)性 rA,B . rA,B0,正相關(guān)。 ? 線性回歸 ? 多線性回歸 數(shù)據(jù)集成 ? 將多個數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來存放在一個一直得數(shù)據(jù)存貯中。這些孤立點可能包含有用的信息。 ? 箱的寬度：每個箱值的取值區(qū)間是個常數(shù)。 污染數(shù)據(jù)形成的原因 ? 濫用縮寫詞 ? 數(shù)據(jù)輸入錯誤 ? 數(shù)據(jù)中的內(nèi)嵌控制信息 ? 不同的慣用語 ? 重復(fù)記錄 ? 丟失值 ? 拼寫變化 ? 不同的計量單位 ? 過時的編碼 ? 含有各種噪聲 數(shù)據(jù)清理的重要性 1. 污染數(shù)據(jù)的普遍存在，使得在大型數(shù)據(jù)庫中維護數(shù)據(jù)的正確性和一致性成為一個及其困難的任務(wù)。 ? 第四代數(shù)據(jù)挖掘系統(tǒng) ? 第四代數(shù)據(jù)挖掘系統(tǒng)能夠挖掘嵌入式系統(tǒng)、移動系統(tǒng)、和普遍存在（ ubiquitous）計算設(shè)備產(chǎn)生的各種類型的數(shù)據(jù) 。 數(shù)據(jù)挖掘系統(tǒng) ? 第三代數(shù)據(jù)挖掘系統(tǒng) ? 第三代的特征是能夠挖掘 Inter/Extra的分布式和高度異質(zhì)的數(shù)據(jù)，并且能夠有效地和操作型系統(tǒng)集成。例如，第二代系統(tǒng)能夠挖掘大數(shù)據(jù)集、更復(fù)雜的數(shù)據(jù)集、以及高維數(shù)據(jù)。 ? 第二代數(shù)據(jù)挖掘系統(tǒng) ? 目