【正文】 ? 現(xiàn)實(shí)領(lǐng)域的問題是多種多樣的，一種或少數(shù)數(shù)據(jù)挖掘算法難以解決 ? 挖掘的數(shù)據(jù)通常不符合算法的要求，需要有數(shù)據(jù)清洗、轉(zhuǎn)換等數(shù)據(jù)預(yù)處理的配合，才能得出有價值的模型 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 橫向的數(shù)據(jù)挖掘工具集（ 95年開始） ? 發(fā)展原因 ? 隨著數(shù)據(jù)挖掘應(yīng)用的發(fā)展，人們逐漸認(rèn)識到數(shù)據(jù)挖掘軟件需要和以下三個方面緊密結(jié)合： 1）數(shù)據(jù)庫和數(shù)據(jù)倉庫； 2）多種類型的數(shù)據(jù)挖掘算法； 3）數(shù)據(jù)清洗、轉(zhuǎn)換等預(yù)處理工作。比如 ，平行坐標(biāo)可視化（ parallelcoordinate visualization）。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 獨(dú)立的數(shù)據(jù)挖掘軟件（ 95年以前） ? 特點(diǎn) ? 獨(dú)立的數(shù)據(jù)挖掘軟件對應(yīng)第一代系統(tǒng)，出現(xiàn)在數(shù)據(jù)挖掘技術(shù)發(fā)展早期，研究人員開發(fā)出一種新型的數(shù)據(jù)挖掘算法，就形成一個軟件。第四代數(shù)據(jù)挖掘原型或商業(yè)系統(tǒng)尚未見報導(dǎo) 169。 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 二、數(shù)據(jù)挖掘軟件的發(fā)展 第四代數(shù)據(jù)挖掘軟件 ? 特點(diǎn) ? 目前移動計算越發(fā)顯得重要，將數(shù)據(jù)挖掘和移動計算相結(jié)合是當(dāng)前的一個研究領(lǐng)域。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第三代數(shù)據(jù)挖掘軟件 ? 特點(diǎn) ? 和預(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ù)挖掘軟件 DBMiner 169。 基于關(guān)聯(lián)規(guī)則的分類算法，能從關(guān)系數(shù)據(jù)或者交易數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則，使用關(guān)聯(lián)規(guī)則進(jìn)行分類和預(yù)測 169。 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)據(jù)挖掘軟件的發(fā)展 代 特征 數(shù)據(jù)挖掘算法 集成 分布計算模型 數(shù)據(jù)模型 第一代 作為一個獨(dú)立的應(yīng)用 支持一個或者多個算法 獨(dú)立的系統(tǒng) 單個機(jī)器 向量數(shù)據(jù) 第二代 和數(shù)據(jù)庫以及數(shù)據(jù)倉庫集成 多個算法：能夠挖掘一次不能放進(jìn)內(nèi)存的數(shù)據(jù) 數(shù)據(jù)管理系統(tǒng)，包括數(shù)據(jù)庫和數(shù)據(jù)倉庫 同質(zhì)、局部區(qū)域的計算機(jī)群集 有些系統(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?？赡苄枰付ㄒ粋€滑動時間窗口，客戶在滑動時間窗口的時間段內(nèi)的所有的購買行為均作為一個事務(wù) ? 缺少分類層次：只能在項(xiàng)目的原始級別上進(jìn)行挖掘 169。例如，一個序列模式可能會發(fā)現(xiàn)客戶在購買了物品 A后的第三年購買物品 B。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 序列模式挖掘算法 ? 序列模式挖掘的主要算法 ? GSP(Generalized Sequential Patterns)算法：類似于 Apriori算法 ? PrefixSpan(Prefixproject Sequential Pattern mining)算法：采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進(jìn)行序列模式挖掘 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è) ? = 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ù)研究所 序列模式表示 ? 符號化表示： ? 項(xiàng)目集 (Itemset)是各種項(xiàng)目組成的集合 ? 序列 (Sequence)是不同項(xiàng)目集 (ItemSet)的有序排列，序列 s可以表示為 s = s1s2…s l， sj(1 = j = l)為項(xiàng)目集(Itemset)，也稱為序列 s的元素 ? 序列的元素 (Element)可表示為 (x1x2…x m)， xk(1 = k = m)為不同的項(xiàng)目，如果一個序列只有一個項(xiàng)目，則括號可以省略 ? 一個序列包含的所有項(xiàng)目的個數(shù)稱為序列的長度。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 序列模式實(shí)例 ? 例 1：在兩年前購買了 Ford 牌轎車的顧客，很有可能在今年采取貼舊換新的購車行動 ? 例 2：在購買了自行車和購物籃的所有客戶中，有 70%的客戶會在兩個月后購買打氣筒 ? 例 3：工業(yè)過程控制領(lǐng)域：過程變量采樣值時時間序列；變量之間的關(guān)系是動態(tài)的；系統(tǒng)故障模式；等等 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 六、序列模式挖掘 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 關(guān)聯(lián)規(guī)則可視化 Using Plane Graph 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 ARCS的局限性 ? 數(shù)值屬性只能出現(xiàn)在規(guī)則的左側(cè) ? 左側(cè)只能有兩個屬性 (2維 ) ? ARCS 的改進(jìn) ? 不用基于柵格的方法 ? 等深分箱 ? 基于 局部完整性 測度的聚集 ? “ Mining Quantitative Association Rules in Large Relational Tables‖ by R. Srikant and R. Agrawal. 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 帶數(shù)量的關(guān)聯(lián)規(guī)則 age(X,”3034”) ? ine(X,”24K 48K”) ? buys(X,”high resolution TV”) ? 動態(tài) 離散化數(shù)值屬性 ? Such that the confidence or pactness of the rules mined is maximized. ? 2維數(shù)量關(guān)聯(lián)規(guī)則： Aquan1 ? Aquan2 ? Acat ? 用 2維表格把 “ 鄰近 ” 的 關(guān)聯(lián)規(guī)則組合起來 ? 例子 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 數(shù)值屬性的靜態(tài)離散化 ? 在挖掘之前用概念層次先離散化 ? 數(shù)值被替換為區(qū)間范圍 ? 關(guān)系數(shù)據(jù)庫中，要找到所有頻繁 k維詞需要 k或 k+1次表掃描。 2. 帶數(shù)量的關(guān)聯(lián)規(guī)則 ? 根據(jù)數(shù)據(jù)的分布動態(tài)的把數(shù)值屬性離散化到不同的 “ 箱 ” 。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 挖掘多維關(guān)聯(lián)的技術(shù) ? 搜索頻繁 k維詞集合： ? 如 : {age, occupation, buys} 是一個 3維詞集合。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 逐步求精空間關(guān)聯(lián)規(guī)則挖掘 ? 空間關(guān)聯(lián)規(guī)則的兩步算法： ? 步驟 1: 粗糙空間計算 (用于過濾 ) 用 MBR 或 Rtree 做粗糙估計 ? 步驟 2: 細(xì)致空間算法 (用于精化 ) 只計算已經(jīng)通過空間計算的對象 169。 Han, SSD’95). 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 多層挖掘：深度優(yōu)先 ?自頂向下，深度優(yōu)先的方法： ?先挖掘高層頻繁項(xiàng)： 牛奶 (15%), 面包 (10%) ?再挖掘他們底層的相對較弱的頻繁項(xiàng)： 酸奶 (5%), 白面包 (4%) ?跨層時對支持度的不同處理方法，對應(yīng)了不同的算法 : ?層之間支持度不變： 如果 t的祖先是非頻繁的，則不用考慮 t ?支持度隨層遞減： 則只考慮那些其祖先是頻繁的 /不可忽略的項(xiàng) 169。 ? 例子 ? 牛奶 ? 白面包 [support = 8%, confidence = 70%] ? 酸奶 ? 白面包 [support = 2%, confidence = 72%] ? 我們稱第一個規(guī)則是第二個規(guī)則的祖先 ? 參考規(guī)則的祖先，如果他的支持度與我們 “ 預(yù)期 ”的支持度近似的話，我們就說這條規(guī)則是冗余的。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 支持度遞減 支持度遞減多層挖掘 酸奶 [support = 6%] 脫脂奶 [support = 4%] 層 1 min_sup = 5% 層 2 min_sup = 3% 牛奶 [support = 10%] 169。 ?– 底層項(xiàng)不會成為頻繁集，如果支持度 太高 ? 丟失底層關(guān)聯(lián)規(guī)則 太低 ? 生成太多的高層關(guān)聯(lián)規(guī)則 ? 支持度遞減 : 隨著層次的降低支持度遞減 ? 4種搜索策略： 層與層獨(dú)立 用 k項(xiàng)集跨層過濾 用項(xiàng)跨層過濾 用項(xiàng)進(jìn)行可控跨層過濾 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 挖掘多層關(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ī)則： 酸奶 ? 面包房 面包 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 關(guān)鍵步驟：挖掘頻繁集 ? 頻繁集 :是指滿足最小支持度的項(xiàng)目集合 ? 頻繁集的子集也一定是頻繁的 如 , 如果 {AB} 是頻繁集，則 {A} {B} 也一定是頻繁集 ? 從 1到 k（ k頻繁集）遞歸查找頻繁集 ? 用得到的頻繁集生成關(guān)聯(lián)規(guī)則 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 關(guān)聯(lián)規(guī)則挖掘：路線圖 ? 布爾 vs. 定量 關(guān)聯(lián) (基于 處理數(shù)據(jù)的類型 ) ? buys(x, ―SQLServer‖) ^ buys(x, ―DMBook‖) ???buys(x, ―DBMiner‖) [%, 60%] ? age(x, ―30..39‖) ^ ine(x, ―42..48K‖) ???buys(x, ―PC‖) [1%, 75%] ? 單維 vs. 多維 關(guān)聯(lián) (例子同上 ) ? 單層 vs. 多層 分析 ? 那個品種牌子的啤酒與那個牌子的尿布有關(guān)系 ? ? 各種擴(kuò)展 ? 相關(guān)性、因果分析 關(guān)聯(lián)并不一定意味著相關(guān)或因果 ? 最大模式和閉合相集 ? 添加約束 如 , 哪些 “ 小東西 ” 的銷售促發(fā)了 “ 大家伙 ” 的買賣？ 169。 Copyright by Song Zhihuan 工業(yè)控制技術(shù)研究所 規(guī)則度量：支持度與可信度 ?查找所有的規(guī)則 X amp。 ? 舉例： ? 規(guī)則形式： “ Bod