【正文】 ?查找所有的規(guī)則 X amp。 ?– 底層項不會成為頻繁集，如果支持度 太高 ? 丟失底層關(guān)聯(lián)規(guī)則 太低 ? 生成太多的高層關(guān)聯(lián)規(guī)則 ? 支持度遞減 : 隨著層次的降低支持度遞減 ? 4種搜索策略： 層與層獨立 用 k項集跨層過濾 用項跨層過濾 用項進行可控跨層過濾 169。 Han, SSD’95). 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)值屬性的靜態(tài)離散化 ? 在挖掘之前用概念層次先離散化 ? 數(shù)值被替換為區(qū)間范圍 ? 關(guān)系數(shù)據(jù)庫中，要找到所有頻繁 k維詞需要 k或 k+1次表掃描。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 六、序列模式挖掘 169。 Sequence_id Sequence 10 a(abc)(ac)d(cf) 20 (ad)c(bc)(ae) 30 (ef)(ab)(df)cb 40 eg(af)cbc ? 序列 a(bc)df是序列 a(abc)(ac)d(cf)的子序列 ? 序列 (ab)c是長度為 3的序列模式 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 代 特征 數(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è)備的數(shù)據(jù)聯(lián)合 多個算法 數(shù)據(jù)管理、預(yù)言模型、移動系統(tǒng) 移動和各種計算設(shè)備 普遍存在的計算模型 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第三代數(shù)據(jù)挖掘軟件 ? 特點 ? 和預(yù)言模型系統(tǒng)之間能夠無縫的集成，使得由數(shù)據(jù)挖掘軟件產(chǎn)生的模型的變化能夠及時反映到預(yù)言模型系統(tǒng)中 ? 由數(shù)據(jù)挖掘軟件產(chǎn)生的預(yù)言模型能夠自動地被操作型系統(tǒng)吸收，從而與操作型系統(tǒng)中的預(yù)言模型相聯(lián)合提供決策支持的功能 ? 能夠挖掘網(wǎng)絡(luò)環(huán)境下（ Inter/Extra）的分布式和高度異質(zhì)的數(shù)據(jù)，并且能夠有效地和操作型系統(tǒng)集成 ? 缺陷 ? 不能支持移動環(huán)境 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 獨立的數(shù)據(jù)挖掘軟件（ 95年以前） ? 特點 ? 獨立的數(shù)據(jù)挖掘軟件對應(yīng)第一代系統(tǒng)，出現(xiàn)在數(shù)據(jù)挖掘技術(shù)發(fā)展早期，研究人員開發(fā)出一種新型的數(shù)據(jù)挖掘算法，就形成一個軟件。 ? 現(xiàn)實領(lǐng)域的問題是多種多樣的，一種或少數(shù)數(shù)據(jù)挖掘算法難以解決 ? 挖掘的數(shù)據(jù)通常不符合算法的要求，需要有數(shù)據(jù)清洗、轉(zhuǎn)換等數(shù)據(jù)預(yù)處理的配合，才能得出有價值的模型 169。第四代數(shù)據(jù)挖掘原型或商業(yè)系統(tǒng)尚未見報導(dǎo) 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第二代數(shù)據(jù)挖掘軟件 DBMiner 169?？赡苄枰付ㄒ粋€滑動時間窗口，客戶在滑動時間窗口的時間段內(nèi)的所有的購買行為均作為一個事務(wù) ? 缺少分類層次：只能在項目的原始級別上進行挖掘 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 序列模式表示 ? 符號化表示： ? 設(shè) ? = a1a2…a n， ? = b1b2…b m，如果存在整數(shù) 1 = j1 j2 … j n = m，使得 a1 ? bj1， a2 ? bj2， … ， an ? bjn，則稱序列 ?為序列 ?的子序列，又稱序列 ?包含序列 ?，記為 ? ? ? ? 序列 ?在序列數(shù)據(jù)庫 S中的支持?jǐn)?shù)為序列數(shù)據(jù)庫 S中包含序列 ?的序列個數(shù)，記為 Support(?) ? 給定支持度閾值 ?，如果序列 ?在序列數(shù)據(jù)庫中的支持?jǐn)?shù)不低于 ?，則稱序列 ?為序列模式 ? 長度為 l的序列模式記為 l模式 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 關(guān)聯(lián)規(guī)則可視化 Using Plane Graph 169。 2. 帶數(shù)量的關(guān)聯(lián)規(guī)則 ? 根據(jù)數(shù)據(jù)的分布動態(tài)的把數(shù)值屬性離散化到不同的 “ 箱 ” 。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 多層挖掘：深度優(yōu)先 ?自頂向下，深度優(yōu)先的方法： ?先挖掘高層頻繁項： 牛奶 (15%), 面包 (10%) ?再挖掘他們底層的相對較弱的頻繁項： 酸奶 (5%), 白面包 (4%) ?跨層時對支持度的不同處理方法，對應(yīng)了不同的算法 : ?層之間支持度不變： 如果 t的祖先是非頻繁的，則不用考慮 t ?支持度隨層遞減： 則只考慮那些其祖先是頻繁的 /不可忽略的項 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 挖掘多層關(guān)聯(lián)規(guī)則 ?自上而下，深度優(yōu)先的方法： ?先找高層的 “ 強 ” 規(guī)則： 牛奶 ? 面包 [20%, 60%]. ?再找他們底層的 “ 弱 ” 規(guī)則： 酸奶 ? 黃面包 [6%, 50%]. ?多層關(guān)聯(lián)規(guī)則的變種 ?層次交叉的關(guān)聯(lián)規(guī)則： 酸奶 ? 面包房 黃面包 ?不同種分層方法間的關(guān)聯(lián)規(guī)則： 酸奶 ? 面包房 面包 169。 ? 舉例： ? 規(guī)則形式： “ Body ???ead [support, confidence]‖. ? buys(x, ―diapers‖) ?? buys(x, ―beers‖) [%, 60%] ? major(x, ―CS‖) ^ takes(x, ―DB‖) ???grade(x, ―A‖) [1%, 75%] 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 比例標(biāo)度型變量 ? 比例標(biāo)度型變量 （ Ratioscaled variable） : 總是取正的度量值 ， 有一個非線性的標(biāo)度 ， 近似的遵循指數(shù)標(biāo)度 ， 比如 AeBt or AeBt ? 計算相異度的方法 : ? 采用與處理區(qū)間標(biāo)度變量相同的方法 — 不是一個好的選擇 ? 進行對數(shù)變換 ， 對變換得到的值在采用與處理區(qū)間標(biāo)度變量相同的方法 yif = log(xif) ? 將其作為連續(xù)的序數(shù)型數(shù)據(jù) ， 將其秩作為區(qū)間標(biāo)度的值來對待 。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 計算對象之間的相異度 ? 通常使用距離來衡量兩個對象之間的相異度。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 聚類的常規(guī)應(yīng)用 ?模式識別 ?空間數(shù)據(jù)分析 ?在 GIS中，通過聚類發(fā)現(xiàn)特征空間來建立主題索引； ?在空間數(shù)據(jù)挖掘中，檢測并解釋空間中的簇； ?圖象處理 ?經(jīng)濟學(xué) (尤其是市場研究方面 ) ? WWW ?文檔分類 ?分析 WEB日志數(shù)據(jù)來發(fā)現(xiàn)相似的訪問模式 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 其他分類方法 ? k最臨近分類 ? 給定一個未知樣本， k最臨近分類法搜索模式空間，找出最接近未知樣本的 k個訓(xùn)練樣本；然后使用 k個最臨近者中最公共的類來預(yù)測當(dāng)前樣本的類標(biāo)號 ? 基于案例的推理 ? 樣本或案例使用復(fù)雜的符號表示，對于新案例，先檢測是否存在同樣的訓(xùn)練案例；如果找不到，則搜索類似的訓(xùn)練案例 ? 遺傳算法 ? 結(jié)合生物進化思想的算法 ? 粗糙集方法 ? 模糊集方法 ? 允許在分類規(guī)則中定義“模糊的”臨界值或邊界 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 用判定樹歸納分類 ? 什么是判定樹？ ? 類似于流程圖的樹結(jié)構(gòu) ? 每個內(nèi)部節(jié)點表示在一個屬性上的測試 ? 每個分枝代表一個測試輸出 ? 每個樹葉節(jié)點代表類或類分布 ? 判定樹的生成由兩個階段組成 ? 判定樹構(gòu)建 開始時，所有的訓(xùn)練樣本都在根節(jié)點 遞歸的通過選定的屬性，來劃分樣本 （必須是離散值） ? 樹剪枝 許多分枝反映的是訓(xùn)練數(shù)據(jù)中的噪聲和孤立點，樹剪枝試圖檢測和剪去這種分枝 ? 判定樹的使用：對未知樣本進行分類 ? 通過將樣本的屬性值與判定樹相比較 169。 ? 方法 ? 由用戶和專家在模式級顯式的說明屬性的部分序 ? 通過顯式的數(shù)據(jù)分組說明分層結(jié)構(gòu)的一部分 ? 說明屬性集，但不說明他們的偏序 ? 只說明部分的屬性集 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 離散化和概念分層 ? 離散化技術(shù)用來減少給定連續(xù)屬性的個數(shù) ? 通常是遞歸的。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)立方體聚集 ? 尋找感興趣的維度進行再聚集 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)集成 ? 將多個數(shù)據(jù)源中的數(shù)據(jù)結(jié)合起來存放在一個一直得數(shù)據(jù)存貯中。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 分箱 ? 箱的深度：表示不同的箱里有相同個數(shù)的數(shù)據(jù)。 169。這一代系統(tǒng)通過支持?jǐn)?shù)據(jù)挖掘模式（ data mining schema）和數(shù)據(jù)挖掘查詢語言（ DMQL）增加系統(tǒng)的靈活性。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘算法的特征 ?構(gòu)成數(shù)據(jù)挖掘算法的三要素 ?模式記述語言：反映了算法可以發(fā)現(xiàn)什么樣的知識 ?模式評價：反映了什么樣的模式可以稱為知識 ?模式探索：包括針對某一特定模式對參數(shù)空間的探索和對模式空間的探索 169。 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(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. 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘概念 ? 數(shù)據(jù)挖掘 從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，是統(tǒng)計學(xué)、數(shù)據(jù)庫技術(shù)和人工智能技術(shù)的綜合。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 一、數(shù)據(jù)挖掘概述 169。 不能制定合適的決策 ! 數(shù)據(jù) 知識 決策 ? 模式 ? 趨勢 ? 事實 ? 關(guān)系 ? 模型 ? 關(guān)聯(lián)規(guī)則 ? 序列 ? 目標(biāo)市場 ? 資金分配 ? 貿(mào)易選擇 ? 在哪兒做廣告 ? 銷售的地理位置 ? 金融 ? 經(jīng)濟 ? 政府 ? POS. ? 人口統(tǒng)計 ? 生命周期 169。他們的行為與正常的行為有很大不同。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 知識表示：分類樹 分類條件 1 分類條件 2 分類條件 3 類 1 類 2 類 3 類 4 169。例如，第二代系統(tǒng)能夠挖掘大數(shù)據(jù)集、更復(fù)雜的數(shù)據(jù)集、以及高維數(shù)據(jù)。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 為什么需要預(yù)處理