【正文】 ] [ 7 , 7 ]20 [ 1 1 , 2 0 ] [ 2 2 , 5 0 ] [ 2 0 , 2 2 ]22 [ 2 1 , 3 0 ] [ 5 1 , 5 3 ] [ 5 0 , 5 3 ]50 [ 3 1 , 4 0 ]51 [ 4 1 , 5 0 ]53 [ 5 1 , 6 0 ]169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 關聯(lián)規(guī)則可視化 Using Plane Graph 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 關聯(lián)規(guī)則可視化 Using Rule Graph 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 六、序列模式挖掘 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式概念 ? 序列模式的概念最早是由 Agrawal和 Srikant 提出的 ? 序列模式定義：給定一個由不同序列組成的集合，其中，每個 序列由不同的元素按順序有序排列，每個 元素 由不同 項目 組成，同時給定一個用戶指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現(xiàn)頻率不低于用戶指定的最小支持度閾值 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式實例 ? 例 1：在兩年前購買了 Ford 牌轎車的顧客，很有可能在今年采取貼舊換新的購車行動 ? 例 2：在購買了自行車和購物籃的所有客戶中，有 70%的客戶會在兩個月后購買打氣筒 ? 例 3：工業(yè)過程控制領域：過程變量采樣值時時間序列；變量之間的關系是動態(tài)的；系統(tǒng)故障模式；等等 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式應用領域 ? 應用領域： ? 客戶購買行為模式預測 ? Web訪問模式預測 ? 疾病診斷 ? 自然災害預測 ? DNA序列分析 ? 工業(yè)控制 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式表示 ? 符號化表示： ? 項目集 (Itemset)是各種項目組成的集合 ? 序列 (Sequence)是不同項目集 (ItemSet)的有序排列，序列 s可以表示為 s = s1s2…s l， sj(1 = j = l)為項目集(Itemset)，也稱為序列 s的元素 ? 序列的元素 (Element)可表示為 (x1x2…x m)， xk(1 = k = m)為不同的項目，如果一個序列只有一個項目，則括號可以省略 ? 一個序列包含的所有項目的個數(shù)稱為序列的長度。長度為 l的序列記為 l序列 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式表示 ? 符號化表示： ? 設 ? = a1a2…a n， ? = b1b2…b m，如果存在整數(shù) 1 = j1 j2 … j n = m，使得 a1 ? bj1， a2 ? bj2， … ， an ? bjn，則稱序列 ?為序列 ?的子序列，又稱序列 ?包含序列 ?，記為 ? ? ? ? 序列 ?在序列數(shù)據(jù)庫 S中的支持數(shù)為序列數(shù)據(jù)庫 S中包含序列 ?的序列個數(shù)，記為 Support(?) ? 給定支持度閾值 ?，如果序列 ?在序列數(shù)據(jù)庫中的支持數(shù)不低于 ?，則稱序列 ?為序列模式 ? 長度為 l的序列模式記為 l模式 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式表示 ? 例子：設序列數(shù)據(jù)庫如下圖所示，并設用戶指定的最小支持度 minsupport = 2。 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ù)據(jù)庫和最小支持度閾值，序列模式挖掘就是要找出序列數(shù)據(jù)庫中所有的序列模式 ? 系統(tǒng)規(guī)定：由于同一個元素中的項目之間排列沒有順序，為了表達的唯一性，我們將同一個元素內部的不同項目按照字典順序排列 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式挖掘算法 ? 序列模式挖掘的主要算法 ? GSP(Generalized Sequential Patterns)算法：類似于 Apriori算法 ? PrefixSpan(Prefixproject Sequential Pattern mining)算法：采用分治的思想，不斷產生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進行序列模式挖掘 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 序列模式挖掘算法 ? 上述算法存在的主要問題： ? 缺少時間限制：用戶可能需要指定序列模式的相鄰元素之間的時間間隔。例如，一個序列模式可能會發(fā)現(xiàn)客戶在購買了物品 A后的第三年購買物品 B。我們需要的卻是給定時間間隔內用戶的購買意向 ? 事務的定義過于嚴格：一個事務中包含在客戶的一次購買行為中所購買的所有物品?？赡苄枰付ㄒ粋€滑動時間窗口，客戶在滑動時間窗口的時間段內的所有的購買行為均作為一個事務 ? 缺少分類層次：只能在項目的原始級別上進行挖掘 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 七、數(shù)據(jù)挖掘軟件 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 代 特征 數(shù)據(jù)挖掘算法 集成 分布計算模型 數(shù)據(jù)模型 第一代 作為一個獨立的應用 支持一個或者多個算法 獨立的系統(tǒng) 單個機器 向量數(shù)據(jù) 第二代 和數(shù)據(jù)庫以及數(shù)據(jù)倉庫集成 多個算法：能夠挖掘一次不能放進內存的數(shù)據(jù) 數(shù)據(jù)管理系統(tǒng)，包括數(shù)據(jù)庫和數(shù)據(jù)倉庫 同質、局部區(qū)域的計算機群集 有些系統(tǒng)支持對象 ,文本和連續(xù)的媒體數(shù)據(jù) 第三代 和預言模型系統(tǒng)集成 多個算法 數(shù)據(jù)管理和預言模型系統(tǒng) intra/extra網絡計算 支持半結構化數(shù)據(jù)和 web數(shù)據(jù) 第四代 和移動數(shù)據(jù) /各種計算設備的數(shù)據(jù)聯(lián)合 多個算法 數(shù)據(jù)管理、預言模型、移動系統(tǒng) 移動和各種計算設備 普遍存在的計算模型 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第一代數(shù)據(jù)挖掘軟件 ? 特點 ? 支持一個或少數(shù)幾個數(shù)據(jù)挖掘算法 ? 挖掘向量數(shù)據(jù)（ vectorvalued data） ? 數(shù)據(jù)一般一次性調進內存進行處理 ? 典型的系統(tǒng)如 Salford Systems公司早期的 CART系統(tǒng)() ? 缺陷 ? 如果數(shù)據(jù)足夠大，并且頻繁的變化，這就需要利用數(shù)據(jù)庫或者數(shù)據(jù)倉庫技術進行管理，第一代系統(tǒng)顯然不能滿足需求。 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第一代數(shù)據(jù)挖掘軟件 CBA 新加坡國立大學。 基于關聯(lián)規(guī)則的分類算法，能從關系數(shù)據(jù)或者交易數(shù)據(jù)中挖掘關聯(lián)規(guī)則，使用關聯(lián)規(guī)則進行分類和預測 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 二、數(shù)據(jù)挖掘軟件的發(fā)展 第二代數(shù)據(jù)挖掘軟件 ? 特點 ? 與數(shù)據(jù)庫管理系統(tǒng)（ DBMS）集成 ? 支持數(shù)據(jù)庫和數(shù)據(jù)倉庫，和它們具有高性能的接口，具有高的可擴展性 ? 能夠挖掘大數(shù)據(jù)集、以及更復雜的數(shù)據(jù)集 ? 通過支持數(shù)據(jù)挖掘模式（ data mining schema）和數(shù)據(jù)挖掘查詢語言增加系統(tǒng)的靈活性 ? 典型的系統(tǒng)如 DBMiner，能通過 DMQL挖掘語言進行挖掘操作 ? 缺陷 ? 只注重模型的生成，如何和預言模型系統(tǒng)集成導致了第三代數(shù)據(jù)挖掘系統(tǒng)的開發(fā) 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第二代數(shù)據(jù)挖掘軟件 DBMiner 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第二代軟件 SAS Enterprise Miner 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第三代數(shù)據(jù)挖掘軟件 ? 特點 ? 和預言模型系統(tǒng)之間能夠無縫的集成，使得由數(shù)據(jù)挖掘軟件產生的模型的變化能夠及時反映到預言模型系統(tǒng)中 ? 由數(shù)據(jù)挖掘軟件產生的預言模型能夠自動地被操作型系統(tǒng)吸收，從而與操作型系統(tǒng)中的預言模型相聯(lián)合提供決策支持的功能 ? 能夠挖掘網絡環(huán)境下（ Inter/Extra）的分布式和高度異質的數(shù)據(jù)，并且能夠有效地和操作型系統(tǒng)集成 ? 缺陷 ? 不能支持移動環(huán)境 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 第三代軟件 SPSS Clementine 以 PMML的格式提供與預言模型系統(tǒng)的接口 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 二、數(shù)據(jù)挖掘軟件的發(fā)展 第四代數(shù)據(jù)挖掘軟件 ? 特點 ? 目前移動計算越發(fā)顯得重要，將數(shù)據(jù)挖掘和移動計算相結合是當前的一個研究領域。 ? 第四代軟件能夠挖掘嵌入式系統(tǒng)、移動系統(tǒng)、和普遍存在（ ubiquitous）計算設備產生的各種類型的數(shù)據(jù) 第四代數(shù)據(jù)挖掘原型或商業(yè)系統(tǒng)尚未見報導， PKDD2022上Kargupta發(fā)表了一篇在移動環(huán)境下挖掘決策樹的論文，Kargupta是馬里蘭巴爾的摩州立大學（ University of Maryland Baltimore County）正在研制的 CAREER數(shù)據(jù)挖掘項目的負責人，該項目研究期限是 2022年 4月到 2022年 4月，目的是開發(fā)挖掘分布式和異質數(shù)據(jù)（ Ubiquitous設備）的第四代數(shù)據(jù)挖掘系統(tǒng)。 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 ? 第一代系統(tǒng)與第二代相比因為不具有和數(shù)據(jù)管理系統(tǒng)之間有效的接口，所以在數(shù)據(jù)預處理方面有一定缺陷 ? 第三、四代系統(tǒng)強調預測模型的使用和操作型環(huán)境的部署 ? 第二代系統(tǒng)提供數(shù)據(jù)管理系統(tǒng)和數(shù)據(jù)挖掘系統(tǒng)之間的有效接口 ? 第三代系統(tǒng)另外還提供數(shù)據(jù)挖掘系統(tǒng)和預言模型系統(tǒng)之間的有效的接口 ? 目前，隨著新的挖掘算法的研究和開發(fā)，第一代數(shù)據(jù)挖掘系統(tǒng)仍然會出現(xiàn)，第二代系統(tǒng)是商業(yè)軟件的主流，部分第二代系統(tǒng)開發(fā)商開始研制相應的第三代數(shù)據(jù)挖掘系統(tǒng)，比如 IBM Intelligent Score Service。第四代數(shù)據(jù)挖掘原型或商業(yè)系統(tǒng)尚未見報導 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 數(shù)據(jù)挖掘軟件發(fā)展的三個階段 ? 獨立的數(shù)據(jù)挖掘軟件 ? 橫向的數(shù)據(jù)挖掘工具集 ? 縱向的數(shù)據(jù)挖掘解決方案 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 獨立的數(shù)據(jù)挖掘軟件（ 95年以前） ? 特點 ? 獨立的數(shù)據(jù)挖掘軟件對應第一代系統(tǒng)，出現(xiàn)在數(shù)據(jù)挖掘技術發(fā)展早期，研究人員開發(fā)出一種新型的數(shù)據(jù)挖掘算法，就形成一個軟件。 ? 這類軟件要求用戶對具體的算法和數(shù)據(jù)挖掘技術有相當?shù)牧私?，還要負責大量的數(shù)據(jù)預處理工作。比如 ，平行坐標可視化（ parallelcoordinate visualization）。 169。 Copyright by Song Zhihuan 工業(yè)控制技術研究所 數(shù)據(jù)挖掘軟件的發(fā)展 橫向的數(shù)據(jù)挖掘工具集（ 95年開始） ? 發(fā)展原因 ? 隨著數(shù)據(jù)挖掘應用的發(fā)展，人們逐漸認識到數(shù)據(jù)挖掘軟件需要和以下三個方面緊密結合： 1）數(shù)據(jù)庫和數(shù)據(jù)倉庫； 2）多種類型的數(shù)據(jù)挖掘算法； 3）數(shù)據(jù)清洗、轉換等預處理工作。 ? 隨著數(shù)據(jù)量的增加，需要利用數(shù)據(jù)庫或者數(shù)據(jù)倉庫技術進行管理，所以數(shù)據(jù)挖掘系統(tǒng)與數(shù)據(jù)庫和數(shù)據(jù)倉庫結合是自然的發(fā)展。 ? 現(xiàn)實領域的問題是多種多樣的，一種或少數(shù)數(shù)據(jù)挖掘算法難以解決 ? 挖掘的數(shù)據(jù)通常不符合算法的要求，需要有數(shù)據(jù)清洗、轉換等數(shù)據(jù)預處理的配合，才能得出有價值的模型 169。 Copyr