【導(dǎo)讀】成為未來信息技術(shù)應(yīng)用的重要目標(biāo)之一。經(jīng)過十幾年的努力，數(shù)據(jù)挖掘產(chǎn)生。特別是最近幾年，一些基本概念和方法趨于清晰，它。的研究正向著更深入的方向發(fā)展。從目前的現(xiàn)狀看，大部分學(xué)者認為數(shù)據(jù)挖掘的研究仍然處于廣泛。和挖掘語言等方面進行創(chuàng)新。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中成果頗豐而且比較。面對大型數(shù)據(jù)庫，關(guān)聯(lián)規(guī)。則挖掘需要在挖掘效率、可用性、精確性等方面得到提升。了這一課題開展相關(guān)工作。過程出發(fā)，探討系統(tǒng)應(yīng)具備的主要功能部件及其相互聯(lián)系等。基于項目序列集格空間及其操作，我們建立了關(guān)聯(lián)規(guī)則。數(shù)據(jù)分割下的關(guān)聯(lián)規(guī)則挖掘算法PISS-DM。ISS-DM算法是建立在嚴(yán)格的項。我們選擇目前引用率較高的Apriori算法和ISS-DM進行了對。結(jié)果表明，ISS-DM執(zhí)行時間整體上優(yōu)于Apriori算法，而且隨著數(shù)。及時態(tài)區(qū)間操作等進行了形式化，它們是TISS-DM的理論基礎(chǔ)。本文解決了數(shù)據(jù)分割下局部頻繁項目序列集和全局頻繁項目序

　　

【正文】 框架 下， 數(shù)據(jù) 挖掘技 術(shù)被 看作 是對 數(shù)據(jù) 的壓縮的 過程 [ 10 ] 。 按 著 這種 觀點 ，關(guān) 聯(lián)規(guī) 則、 決策 樹 、聚 類等算法實際 上都是對 大型數(shù) 據(jù)集的 不斷概念 化或抽 象的壓 縮過程。按 C ha krabarti 等人的描 述，最小 描述長 度（ MD L Mi ni mum Descriptio n Le ngth ）原 理可以評 價一個 壓縮方法 的優(yōu)劣 ，即最好的 壓 縮方法應(yīng) 該是概 念本身 的描述和 把它作 為預(yù)測 器的編碼長度都最小 [ 10]。 (6) 基 于 歸 納 數(shù) 據(jù)庫 （ Inductive Database）理論 在這種 理論 框架 下， 數(shù)據(jù) 挖掘技 術(shù)被 看作 是對 數(shù)據(jù) 庫的第 2 章 數(shù)據(jù)挖掘技術(shù) 15 歸納 的問 題 [1， 11 ] 。 一個 數(shù)據(jù) 挖 掘系 統(tǒng)必 須 具有 原始 數(shù) 據(jù)庫和模式庫 ，數(shù)據(jù)挖 掘的過 程就是 歸納的數(shù) 據(jù)查詢 過程。 這種構(gòu)架也是目前研究者和系統(tǒng)研制者傾向的理論框架。 (7) 可 視 化 數(shù) 據(jù) 挖掘 （ Visual Data Mining） 1997 年， Kei m 等 對可視化 數(shù)據(jù)挖 掘的相關(guān) 技術(shù)給 出了綜述 [ 1 2]。雖然可 視化數(shù) 據(jù)挖掘必 須結(jié)合 其它技 術(shù) 和方法 才有意義，但 是，以可 視化數(shù) 據(jù)處理 為中心來 實現(xiàn)數(shù) 據(jù)挖掘 的交互式過程 以及更好 地展示 挖掘結(jié) 果等，已 經(jīng)成為 數(shù)據(jù)挖 掘中的一個重要方面。這類研究的上升趨勢可以通過 AC M SOGMOD?02 會議的相關(guān)論 文數(shù)量 得到驗證 [ 1 3]。 當(dāng)然，上面 所述的 理論框架 不是孤 立的，更 不是互 斥的。對于特定 的研究和 開發(fā)領(lǐng) 域來說 ，它們是 相互交 叉并且 有所側(cè)重的。 從上面的 敘述中 ，我們 也可以看 出，數(shù) 據(jù)挖掘 的研究是在相 關(guān)學(xué)科充 分發(fā)展 的基礎(chǔ) 上提出并 不斷發(fā) 展的， 它的概念和理 論仍在發(fā) 展中。 為了弄 清相關(guān)的 概念和 技術(shù)路 線，仍有大量的工作等待我們?nèi)ヌ剿骱蛧L 試。 數(shù)據(jù)挖掘技術(shù)的分類問題 數(shù)據(jù)挖掘涉 及的學(xué) 科領(lǐng)域和 方法很 多，有多 種分類 方法。 根據(jù)挖 掘任 務(wù)可 以分 為： 分類或 預(yù)測 模型 發(fā)現(xiàn) 、數(shù) 據(jù)總結(jié)與聚類 發(fā)現(xiàn)、關(guān) 聯(lián)規(guī)則 發(fā)現(xiàn)、 序列模式 發(fā)現(xiàn)、 相似模 式發(fā)現(xiàn)、混沌 模式發(fā)現(xiàn) 、依賴 關(guān)系或 依賴模型 發(fā)現(xiàn)、 異常和 趨勢發(fā)現(xiàn)等。 根據(jù)挖 掘?qū)?象可 以分 為： 關(guān)系數(shù) 據(jù)庫 、面 向?qū)?象數(shù) 據(jù)庫(ObjectOriented Database)、空 間數(shù)據(jù) 庫、時 態(tài)數(shù)據(jù) 庫、文本數(shù)據(jù) 源、多媒 體數(shù)據(jù) 庫、異 質(zhì)數(shù)據(jù)庫 、遺產(chǎn) 數(shù)據(jù)庫 以及w eb 等對象的挖掘。 根據(jù)挖 掘方 法可 以分 為： 機器學(xué) 習(xí)方 法、 統(tǒng)計 方法 、聚類分 析方 法 、 探 索性 分析 、 神經(jīng) 網(wǎng)絡(luò) （ Ne ural Ne tw or k）方法、遺傳 算法（ Ge ne tic Al gorithm）、數(shù)據(jù) 庫方法 、近似 推理和不確定 性推理方 法、基 于證據(jù) 理論和元 模式的 方法、 現(xiàn)代數(shù)學(xué)分析方法、粗糙集（ Rough Set）方法、集成方法等。 根據(jù)數(shù)據(jù)挖 掘所能 發(fā)現(xiàn)的知 識可以 分為 ： :廣義型知 識挖掘、差異 型知識挖 掘、關(guān) 聯(lián)型知 識挖掘、 預(yù)測型 知識挖 掘、第 2 章 數(shù)據(jù)挖掘技術(shù) 16 偏離型（異常）知識挖掘、不確定性知識等。 當(dāng)然， 這些 分類 方法 都從 不同角 度， 刻畫 了數(shù) 據(jù)挖 掘研究的策略 和范疇， 他們是 互相交 叉而相互 補充的 。下面 我們將從幾個 不同的角 度來進 一步闡 述目前所 研究的 問題和 所采用的主要方法。 數(shù)據(jù)挖掘 常用的知識表示模式與方法 數(shù)據(jù)挖 掘的 目的 是發(fā) 現(xiàn)知 識，知 識要 通過 一定 的模 式給出?？捎?于數(shù)據(jù)挖 掘系統(tǒng) 的知識 表示模式 是豐富 的，通 過對數(shù)據(jù)挖掘 中知識表 示模式 及其所 采用方法 的分析 ，可以 更清楚地了解 數(shù)據(jù)挖掘 系統(tǒng)的特點。 廣義知識 挖掘 廣義知 識（ Ge neraliza tio n） 是 指描 述類 別特征 的概 括性知識。 我 們知道， 在源數(shù) 據(jù)（如 數(shù)據(jù)庫） 中存放 的一般 是細節(jié)性數(shù)據(jù) ，而人們 有時希 望能從 較高層次 的視圖 上處理 或觀察這些數(shù) 據(jù)，通過 數(shù)據(jù)進 行不同 層次上的 泛化來 尋找數(shù) 據(jù)所蘊 涵的概 念或邏輯 ，以適 應(yīng)數(shù)據(jù) 分析的要 求。數(shù) 據(jù)挖掘 的目的之一就 是 根據(jù) 這些 數(shù)據(jù) 的微觀 特性發(fā)現(xiàn) 有普遍 性的、 更高層次概念 的中觀和 宏觀的 知識 。 因此，這 類數(shù)據(jù) 挖掘系 統(tǒng)是對 數(shù)據(jù)的 所蘊涵的 概念特 征信息 、匯總信 息和比 較信息 等的概括、精 煉和抽象 的過程 。 被挖 掘出的 廣 義知識 可以結(jié) 合可視化技術(shù) 以直觀的 圖表（ 如餅圖 、柱狀圖 、曲線 圖、立 方體等）形式 展示給用 戶，也 可以作為 其它應(yīng) 用（如 分類、預(yù) 測）的基礎(chǔ)知識。 （ 1） 概念描述 （ Concept Description）方法 概念描 述本 質(zhì)上 就是 對某 類對象 的內(nèi) 涵特 征進 行概 括。概 念 描 述 分 為 特 征 性 （ Charac teri zatio n ） 描 述 和 區(qū) 別 性（ Discri mi natio n） 描述 。 前者 描述某 類對象的 共同特 征，后者描述不同類對象之間的區(qū)別。 概念描 述 是 廣義 知識 挖掘 的重要 方法 ，目 前已 經(jīng)得 到廣泛研究。歸納起來有下面一些有代表性的方法： 第 2 章 數(shù)據(jù)挖掘技術(shù) 17 ? 概念 歸納（ Concept Induction）方法 這種方 法來 源于 機器 學(xué)習(xí) 。我們 知道 ，典 型的 示例 學(xué)習(xí)把樣本分 成正樣本 和負樣 本，學(xué) 習(xí)的結(jié)果 就是形 成覆蓋 所有正樣本但 不覆蓋任 何負樣 本的概 念描述。 關(guān)于這 類學(xué)習(xí) 算法可以在經(jīng)典 的機器 學(xué)習(xí)的教 程中找 到，這 里不再贅 述。但 是，要把這種思 想應(yīng)用 到數(shù)據(jù)挖 掘中要 解決兩個 關(guān)鍵問 題。第 一，必須擴大 樣本集的 容量和 范圍。 傳統(tǒng)的機 器學(xué)習(xí) 希望是 精練的小樣本 集，而數(shù) 據(jù)挖掘 系統(tǒng)必 須忠實于 源數(shù)據(jù) ，是面 向大容量數(shù)據(jù) 庫等存儲 數(shù)據(jù)集 的。所 以，擴大 后的樣 本集可 能難于有效地 精確實現(xiàn) “覆蓋 所有正 樣本但不 覆蓋任 何負樣 本”的概念歸 納目標(biāo)。 要結(jié)合 概率統(tǒng) 計方法， 在檢驗 部分正 樣本或負樣本 情況下得 到概念 的描述 。因此， 最大限 度地使 用樣本進行歸 納就是必 須解決 的關(guān)鍵 問題之一 。第二 ，對于 數(shù)據(jù)挖掘系統(tǒng) 來說，正 樣本來 自于源 數(shù)據(jù)庫， 而負樣 本是不 可能在源數(shù)據(jù) 庫中直接 存儲的 ，但是 缺乏對比 類信息 的概念 歸納是不可 靠 的。因此 ，從源 數(shù)據(jù)庫 中形成負 樣本（ 或區(qū)別 性信息）以及 相關(guān)的評 價區(qū)別 的度量 方法等也 是要解 決的另 一個重要問題。 ? 多 維 數(shù) 據(jù) 分 析可 以看作 是一 種廣義 知識挖 掘的 有效方法 數(shù)據(jù)分析的 經(jīng)常性 工作是數(shù) 據(jù)的聚 集， 諸如 計數(shù)、求和、平均、最 大值等 。 既然很 多聚集 函數(shù)需經(jīng) 常重復(fù) 計算， 而且這類操作的 計算量 一般又特 別大 ，因此一 種很自 然的想法 是，把這些匯 總的操作 結(jié)果預(yù) 先計算 并存儲起 來，以 便于高 級數(shù)據(jù)分析使 用。最流 行的存 儲匯集 數(shù)據(jù)類的 方法是 多維數(shù) 據(jù)庫（ Mul ti di me nsio n Da tabase）技 術(shù)。 多 維數(shù)據(jù)庫 總是 提 供不同抽象層 次上 的數(shù) 據(jù)視圖 。 例如 ，可以存 放每周 的數(shù)據(jù) ，也可在月底 形成月數(shù) 據(jù)，月 數(shù)據(jù)又 能形成年 數(shù)據(jù) 。 關(guān)于多 維數(shù)據(jù)模型的操 作，已 經(jīng)被很 好研究 ，許多文 獻可能 和數(shù)據(jù)倉 庫、O LAP 聯(lián)系 起來 [ 14， 15]。其實 ，這種模 型，特別 是它操 作的 完備性（如上鉆、下鉆等），可以成為廣義知識發(fā)現(xiàn)的基礎(chǔ)。 ? 面 向 數(shù) 據(jù) 庫 的概 化方法 數(shù)據(jù)庫 ，特 別是 關(guān)系 型數(shù) 據(jù)庫是 數(shù)據(jù) 挖掘 的主 要源 數(shù)據(jù)類型。近 年來，在 面向數(shù) 據(jù)庫的 廣義知識 挖掘方 面進行 了有第 2 章 數(shù)據(jù)挖掘技術(shù) 18 針對性的研 究。值 得一提的 是， 加 拿大 Si mo nFraser 大 學(xué)提出的面向?qū)?性的 概念 歸約方 法 [ 1 6, 17 ]。 它 直接對用 戶感興 趣 的數(shù)據(jù)視圖 (用 一般的 S Q L 查詢語 言即可獲 得 )進行泛 化，而不是像多維 數(shù)據(jù)分析 方法那 樣預(yù)先 就存儲好 了泛化 數(shù)據(jù)。 原始關(guān)系經(jīng)過 泛化操作 后得到 的是一 個泛化關(guān) 系，它 從較高 的層次上總結(jié) 了在低層 次上的 原始關(guān) 系。有了 泛化關(guān) 系后， 就可以對它進 行各種深 入的操 作而生 成滿足用 戶需要 的知識 ，如在泛化關(guān) 系基礎(chǔ)上 生成特 性規(guī)則 、判別規(guī) 則、分 類規(guī)則 以及關(guān)聯(lián)規(guī)則等 。 這 種方法以 類 S Q L 語 言表示 數(shù)據(jù)挖掘 查詢 ，收集數(shù)據(jù)庫 中的相關(guān) 數(shù)據(jù)集 ，然后 在相關(guān)數(shù) 據(jù)集上 應(yīng)用一 系列數(shù)據(jù)推廣 技術(shù)進行 數(shù)據(jù)推 廣，包 括屬性刪 除、概 念樹提 升、屬性閾值控制、計數(shù)及其他聚集函數(shù)傳播 等。 （ 2） 多 層 次 概念 描述 問題 由數(shù)據(jù)歸納 出的概 念是有層 次的 ，例如 ， loca tio n 是“北京 工 業(yè) 大 學(xué) ”， 那 么 我 們 可 能 通 過 背 景 知 識 （ Bac kgro und K now ledge）歸 納 出 “北 京 市”、“ 中國 ”、“ 亞 洲” 等 不 同層次的更高 級概念。 這些不 同層次 的概念在 是對原 始數(shù)據(jù) 的不同粒度上 的概念抽 象。因 此，探 索多層次 概念的 描述機 制是必要的 。目前 ，廣泛 討論 的概念 分層（ Co ncep t Hierarchy）技術(shù)就 是為了 解決 這個問 題 [ 1 ]。 所謂概 念分 層實際 上就 是將低層概念 集映射到 高層概 念集的 方法。在 任何形 式的源 數(shù)據(jù)組織形式 下，被 存 儲的細 節(jié)數(shù)據(jù) 總是作用 在一個 特定的 范疇內(nèi)。例如，一個 記錄銷 售人員銷 售情況 的數(shù)據(jù)庫 的表 S A LES（ EN O， E NA ME， E A GE， VA L UE， DEP T）， 它的 每個 屬性的定義域 都可能存 在蘊涵 于領(lǐng)域 知識內(nèi)的 概念延 伸。例 如，所在部 門 DE PT 可能在 特定的條 件下需 要知道它 所在的 公司CO MPA NY、城市 C IT Y 或國 家 C O UNT RY，因為 更高層 次的數(shù)據(jù)綜合和分析是決策的基礎(chǔ)。 目前使用較多的概念分層方法有： ? 模式分層（ Sche ma Hie rarchy） 利用屬 性在 特定 背景 知識 下的語 義層 次形 成不 同層 次的模式關(guān)聯(lián) 。這種關(guān) 聯(lián)是一 種 的全 序或偏序 關(guān)系。 例如， 作為一個跨國公司的銷售部門 DEPT 的模 式分層 結(jié)構(gòu)可能 是： DEPT→ COMPAN Y→ C IT Y→ C O UNT RY。 第 2 章 數(shù)據(jù)挖掘技術(shù) 19 這 種 結(jié) 構(gòu) 定 義 了 一 個 屬 性 由 低 層 概 念 向 高 層 概 念 的 轉(zhuǎn) 化 路徑，為從源數(shù)據(jù)庫中挖掘廣義知識提供領(lǐng)域知識支撐。 ? 集 合 分 組 分 層（ SetGrouping Hie rarchy） 將屬性 在特 定背 景知 識下 的取值 范圍 合理 分割 ，形 成替代的離散值 或區(qū)間 集合。例如，上 面提到 的銷售 年齡 E AG E，可以抽象成 {[20， 29]， [30， 39]， [40， 49]， [50， 59]}或者 {青年，中年，老年 }； VA LUE 可以 抽象成 {[0， 10 00], [1000, 2020), [2020,3000), [300 0， 4000), [40 00， 500 0)，┄ }或者 {低， 中，高 }。 ? 操 作 導(dǎo) 出 分 層（ Ope rationDrive d Hie rarchy） 有些屬 性可 能是 復(fù)雜 對象 ，包含 多類 信息 。例 如， 一個跨國公司 的雇員號 可能包 含這個 雇員的所 在的部 門、城 市、國家和雇 傭的時間 等。對 這類對 象可以作 為背景 知識定 義它的結(jié)構(gòu)， 在數(shù)據(jù)挖 掘的過 程中可 以根據(jù)具 體的抽 象層次 通過編碼解析等操作完成概念的抽象。 ? 基 于 規(guī) 則 分 層（ Rule Base d Hie rarchy） 通過定 義背 景知 識的 抽象 規(guī)則， 在數(shù) 據(jù)挖 掘的 過程 中利用這些規(guī)則形成不同層次上的概念的抽象。 概念分 層結(jié) 構(gòu)應(yīng) 該由 特定 的背景 知識 決定 ，由 領(lǐng)域 專家或知識工程 師整理 成合適的 形式（ 如概念 樹、隊 列或規(guī)則 等）并輸入到 模式庫中 。數(shù)據(jù) 挖掘系 統(tǒng)將在特 定的概 念層次 上依據(jù)分層結(jié)構(gòu)自動從數(shù)據(jù)庫中歸納出對應(yīng)的廣義知識。 關(guān)聯(lián)知識 挖掘 關(guān)聯(lián) 知 識（ Associatio n） 反 映 一個 事 件和 其它 事 件 之間的 依賴或 關(guān)聯(lián)。數(shù) 據(jù)庫中 的 數(shù)據(jù) 關(guān)聯(lián)是 現(xiàn) 實世界 中事物 聯(lián)系的表現(xiàn)。 數(shù)據(jù)庫作 為一種 結(jié)構(gòu)化 的數(shù)據(jù)組 織形式 ，利用 其依附的數(shù)據(jù) 模型可能 刻畫了 數(shù)據(jù)間 的關(guān)聯(lián)（ 如關(guān)系 數(shù)據(jù)庫 的主鍵和外鍵）。但是 ，數(shù)據(jù)之 間的關(guān) 聯(lián)是復(fù) 雜的，不 僅是