【文章內(nèi)容簡介】 set）是普通的集合概念[1，2]。我們使用術語“項目序列（Itemsequence）”來替代其它文獻中出現(xiàn)的“項目集”。所謂項目序列是指項目集中的元素是按特定標準（如出現(xiàn)次數(shù)、字典排序）進行有序排列的。因此，我們首次引入的項目序列集（Set of Itemsequences）概念可以用來表示一類特定的項目序列集合（如頻繁項目序列集）。本文主要的理論研究和成果為：（1）基于項目序列集操作的挖掘模型我們建立了項目序列集的代數(shù)空間描述，并探討了在這個空間上的基本操作算子。在此基礎上，討論了基于項目序列集操作的數(shù)據(jù)挖掘模型（詳見第4章）。（2）約束條件下的數(shù)據(jù)挖掘理論毫無疑問，引進約束條件可以加速數(shù)據(jù)挖掘的過程。但是，約束條件的引入，必須解決諸如適合數(shù)據(jù)挖掘的約束條件的形式化表示以及約束條件在數(shù)據(jù)挖掘特定階段的使用方式等。本文針對時態(tài)約束條件下的數(shù)據(jù)挖掘理論問題進行了探索。在時態(tài)區(qū)間代數(shù)空間上定義了兩個新的時態(tài)區(qū)間變量操作（時態(tài)交∩T和時態(tài)并UT）。基于這樣的時態(tài)約束條件下的數(shù)據(jù)挖掘理論框架，我們可以擴展數(shù)據(jù)挖掘工作到包括數(shù)據(jù)過濾（Data filtrating）、時態(tài)區(qū)間合并等數(shù)據(jù)預處理在內(nèi)的更廣泛的范疇中去（詳見第5章）。（3）數(shù)據(jù)分割下的數(shù)據(jù)挖掘理論隨著數(shù)據(jù)庫容量的增大，使得通過對源數(shù)據(jù)集的分割來處理大容量數(shù)據(jù)庫的數(shù)據(jù)挖掘問題成為必要。本文就數(shù)據(jù)分割下的數(shù)據(jù)挖掘問題進行了討論，引入局部頻繁項目序列集(Local Frequent Set of Itemsequences)和全局項目序列集(Global Frequent Set of Itemsequences)等概念，并解決了局部頻繁項目序列集和全局頻繁項目序列集轉(zhuǎn)換等問題（詳見第6章）。 關聯(lián)規(guī)則挖掘算法設計與實現(xiàn) 把上面的數(shù)據(jù)挖掘理論應用到關聯(lián)規(guī)則的發(fā)現(xiàn)中，我們完成了相應算法的設計，并且通過理論分析和實驗模擬討論了算法的性能。第4章介紹了基于項目序列集操作的ISSDM算法。它是一個一次數(shù)據(jù)庫掃描并且不使用侯選集的高效算法。為了增強對大容量數(shù)據(jù)庫挖掘的適應性和可用性，第5章設計了時態(tài)約束下的TISSDM算法。它是對ISSDM算法的改進，實驗證明它具有較好的數(shù)據(jù)過濾和區(qū)間合并效率，因而能在同樣的處理環(huán)境下挖掘更大容量的數(shù)據(jù)庫（比ISSDM）。第6章提出了另一個ISSDM的改進算法PISSDM。它通過對數(shù)據(jù)庫的分割，減少了對內(nèi)存和CPU等系統(tǒng)資源的占用，而且可以在兩次數(shù)據(jù)庫掃描的情況下完成挖掘工作。 本章小節(jié)本章介紹了數(shù)據(jù)挖掘研究的意義和技術背景、論文的選題依據(jù)、研究背景以及我們的主要研究內(nèi)容等。數(shù)據(jù)挖掘作為二十世紀信息處理的骨干技術之一，正以一種全新的概念改變著我們利用數(shù)據(jù)的方式。經(jīng)過十幾年的研究和實踐，數(shù)據(jù)挖掘技術已經(jīng)融合了許多學科的最新研究成果而形成獨具特色的研究分支。目前的數(shù)據(jù)挖掘研究正處于蓬勃發(fā)展時期，有許多具有挑戰(zhàn)性的課題被提出。數(shù)據(jù)挖掘的研究內(nèi)容是極其豐富的。作為博士論文，我們在充分了解基本概念和主要技術發(fā)展狀況的前提下，有選擇地進行了重點研究。這些研究包括數(shù)據(jù)挖掘系統(tǒng)的體系結構、關聯(lián)規(guī)則挖掘理論和算法等。45第2章 數(shù)據(jù)挖掘技術第2章 數(shù)據(jù)挖掘技術數(shù)據(jù)挖掘作為一個只有十幾年研究歷史的較新研究領域，許多概念和技術是逐步發(fā)展起來的。因此，本章將系統(tǒng)地介紹相關的概念和技術，并力求從不同視點和流派來闡述數(shù)據(jù)挖掘的重要概念、發(fā)展和應用情況。，我們介紹了數(shù)據(jù)挖掘技術產(chǎn)生的商業(yè)和技術背景；，我們從不同視點闡述了數(shù)據(jù)挖掘的概念和主要理論構架；，我們從多種角度對數(shù)據(jù)挖掘系統(tǒng)的分類問題進行了概括；，我們從知識表示模式角度出發(fā)，歸納了主要的數(shù)據(jù)挖掘技術及其研究成果； ；。 數(shù)據(jù)挖掘技術的產(chǎn)生背景 數(shù)據(jù)挖掘技術的商業(yè)需求分析數(shù)據(jù)挖掘之所以吸引專家學者的研究興趣和引起商業(yè)廠家的廣泛關注，主要在于大型數(shù)據(jù)系統(tǒng)的廣泛使用和把數(shù)據(jù)轉(zhuǎn)換成有用知識的迫切需要。60年代，為了適應信息的電子化要求，信息技術一直從簡單的文件處理系統(tǒng)向有效的數(shù)據(jù)庫系統(tǒng)變革。70年代，數(shù)據(jù)庫系統(tǒng)的三個主要模式――層次、網(wǎng)絡和關系型數(shù)據(jù)庫的研究和開發(fā)取得了重要進展。80年代，關系型數(shù)據(jù)庫及其相關的數(shù)據(jù)模型工具、數(shù)據(jù)索引及數(shù)據(jù)組織技術被廣泛采用，并且成為了整個數(shù)據(jù)庫市場的主導。80年代中期開始，關系數(shù)據(jù)庫技術和新型技術的結合成為數(shù)據(jù)庫研究和開發(fā)的重要標志。從數(shù)據(jù)模型上看，諸如擴展關系、面向?qū)ο蟆ο箨P系（ObjectRelation）以及演繹模型等被應用到數(shù)據(jù)庫系統(tǒng)中。從應用的數(shù)據(jù)類型上看，包括空間、時態(tài)、多媒體以及WEB等新型數(shù)據(jù)成為數(shù)據(jù)庫應用的重要數(shù)據(jù)源。同時，事務數(shù)據(jù)庫（Transaction Database）、主動數(shù)據(jù)庫（Active Database）、知識庫（Knowledge Base）、辦公信息庫（Information Base）等技術也得到蓬勃發(fā)展。從數(shù)據(jù)的分布角度看，分布式數(shù)據(jù)庫（Distributed Database）及其透明性、并發(fā)控制、并行處理等成為必須面對的課題。進入90年代，分布式數(shù)據(jù)庫理論上趨于成熟，分布式數(shù)據(jù)庫技術得到了廣泛應用。目前，由于各種新型技術與數(shù)據(jù)庫技術的有機結合，使數(shù)據(jù)庫領域中的新內(nèi)容、新應用、新技術層出不窮，形成了龐大的數(shù)據(jù)庫家族。但是，這些數(shù)據(jù)庫的應用都是以實時查詢處理技術為基礎的。從本質(zhì)上說，查詢是對數(shù)據(jù)庫的被動使用。由于簡單查詢只是數(shù)據(jù)庫內(nèi)容的選擇性輸出，因此它和人們期望的分析預測、決策支持等高級應用仍有很大距離。新的需求推動新的技術的誕生。數(shù)據(jù)挖掘的靈魂是深層次的數(shù)據(jù)分析方法。數(shù)據(jù)分析是科學研究的基礎，許多科學研究都是建立在數(shù)據(jù)收集和分析基礎上的。同時在目前的商業(yè)活動中，數(shù)據(jù)分析總是和一些特殊的人群的高智商行為聯(lián)系起來，因為并不是每個平常人都能從過去的銷售情況預測將來發(fā)展趨勢或作出正確決策的。但是，隨著一個企業(yè)或行業(yè)業(yè)務數(shù)據(jù)的不斷積累，特別是由于數(shù)據(jù)庫的普及，人工去整理和理解如此大的數(shù)據(jù)源已經(jīng)存在效率、準確性等問題。因此，探討自動化的數(shù)據(jù)分析技術，為企業(yè)提供能帶來商業(yè)利潤的決策信息而成為必然。事實上，數(shù)據(jù)（Data）、信息（Information）和知識（Knowledge）可以看作是廣義數(shù)據(jù)表現(xiàn)的不同形式[3]。毫不夸張地說，人們對于數(shù)據(jù)的擁有欲是貪婪的，特別是計算機存儲技術和網(wǎng)絡技術的發(fā)展加速了人們收集數(shù)據(jù)的范圍和容量。這種貪婪的結果導致了“數(shù)據(jù)豐富而信息貧乏（Data Rich amp。 Information Poor）”現(xiàn)象的產(chǎn)生。數(shù)據(jù)庫是目前組織和存儲數(shù)據(jù)的最有效方法之一，但是面對日益膨脹的數(shù)據(jù)，數(shù)據(jù)庫查詢技術已表現(xiàn)出它的局限性。直觀上說，信息或稱有效信息是指對人們有幫助的數(shù)據(jù)。例如，在現(xiàn)實社會中，如果人均日閱讀時間在30分鐘的話，一個人一天最快只能瀏覽一份20版左右的報紙。如果你訂閱了100份報紙，其實你每天也不過只閱讀了一份而已。面對計算機中的海量的數(shù)據(jù)，人們也處于同樣的尷尬境地，缺乏獲取有效信息的手段。知識是一種概念、規(guī)則、模式和規(guī)律等。它不會象數(shù)據(jù)或信息那么具體，但是它卻是人們一直不懈追求的目標。事實上。在我們的生活中，人們只是把數(shù)據(jù)看作是形成知識的源泉。我們是通過正面的或反面的數(shù)據(jù)或信息來形成和驗證知識的，同時又不斷地利用知識來獲得新的信息。因此，隨著數(shù)據(jù)的膨脹和技術環(huán)境的進步，人們對聯(lián)機決策和分析等高級信息處理的要求越來越迫切。在強大的商業(yè)需求的驅(qū)動下，商家們開始注意到有效地解決大容量數(shù)據(jù)的利用問題具有巨大的商機；學者們開始思考如何從大容量數(shù)據(jù)集中獲取有用信息和知識的方法。因此，在二十世紀八十年代后期，產(chǎn)生了數(shù)據(jù)倉庫和數(shù)據(jù)挖掘等信息處理思想。 數(shù)據(jù)挖掘產(chǎn)生的技術背景分析任何技術的產(chǎn)生總是有它的技術背景的。數(shù)據(jù)挖掘技術的提出和普遍接受是由于計算機及其相關技術的發(fā)展為其提供了研究和應用的技術基礎。歸納數(shù)據(jù)挖掘產(chǎn)生的技術背景，下面一些相關技術的發(fā)展起到了決定性的作用：n 數(shù)據(jù)庫、數(shù)據(jù)倉庫和Internet等信息技術的發(fā)展；n 計算機性能的提高和先進的體系結構的發(fā)展；n 統(tǒng)計學和人工智能等方法在數(shù)據(jù)分析中的研究和應用。數(shù)據(jù)庫技術從二十世紀80年代開始，已經(jīng)得到廣泛的普及和應用。在關系型數(shù)據(jù)庫的研究和產(chǎn)品提升過程中，人們一直在探索組織大型數(shù)據(jù)和快速訪問的相關技術。高性能關系數(shù)據(jù)庫引擎以及相關的分布式查詢、并發(fā)控制等技術的使用，已經(jīng)提升了數(shù)據(jù)庫的應用能力。在數(shù)據(jù)的快速訪問、集成與抽取等問題的解決上積累了經(jīng)驗。數(shù)據(jù)倉庫作為一種新型的數(shù)據(jù)存儲和處理手段，被數(shù)據(jù)庫廠商普遍接受并且相關輔助建模和管理工具快速推向市場，成為多數(shù)據(jù)源集成的一種有效的技術支撐環(huán)境。另外，Internet的普及也為人們提供了豐富的數(shù)據(jù)源。據(jù)說，在美國電視達到5000萬戶大約用了15年，而Internet上網(wǎng)達到5000萬戶僅用了4年。而且Internet技術本身的發(fā)展，已經(jīng)不光是簡單的信息瀏覽，以Web計算為核心的的信息處理技術可以處理Internet環(huán)境下的多種信息源。因此，人們已經(jīng)具備利用多種方式存儲海量數(shù)據(jù)的能力。只有這樣，數(shù)據(jù)挖掘技術才能有它的用武之地。這些豐富多彩的數(shù)據(jù)存儲、管理以及訪問技術的發(fā)展，為數(shù)據(jù)挖掘技術的研究和應用提供了豐富的土壤。計算機芯片技術的發(fā)展，使計算機的處理和存儲能力日益提高。大家熟知的摩爾定律告訴我們，計算機硬件的關鍵指標大約以每18個月翻一番的速度在增長，而且現(xiàn)在看來仍有日益加速的趨勢。隨之而來的是硬盤、CPU等關鍵部件的價格大幅度下降，使得人們收集、存儲和處理數(shù)據(jù)的能力和欲望不斷提高。經(jīng)過幾十年的發(fā)展，計算機的體系結構，特別是并行處理技術已經(jīng)逐漸成熟和普遍應用，并成為支持大型數(shù)據(jù)處理應用的基礎。計算機性能的提高和先進的體系結構的發(fā)展使數(shù)據(jù)挖掘技術的研究和應用成為可能。歷經(jīng)了十幾年的發(fā)展，包括基于統(tǒng)計學、人工智能等在內(nèi)的理論與技術性成果已經(jīng)被成功地應用到商業(yè)處理和分析中。這些應用從某種程度上為數(shù)據(jù)挖掘技術的提出和發(fā)展起到了極大地推動作用。數(shù)據(jù)挖掘系統(tǒng)的核心模塊技術和算法都離不開這些理論和技術的支持。從某種意義講，這些理論本身發(fā)展和應用為數(shù)據(jù)挖掘提供了有價值的理論和應用積累。數(shù)理統(tǒng)計是一個有幾百年發(fā)展歷史的應用數(shù)學學科。然而它和數(shù)據(jù)庫技術的結合性研究應該說最近十幾年才被重視。以前的基于數(shù)理統(tǒng)計方法的應用大多都是通過專用程序來實現(xiàn)的。我們知道，大多數(shù)的統(tǒng)計分析技術是基于嚴格的數(shù)學理論和高超的應用技巧的，這使得一般的用戶很難從容地駕馭它。數(shù)據(jù)挖掘技術是數(shù)理統(tǒng)計分析應用的延伸和發(fā)展，假如人們利用數(shù)據(jù)庫的方式從被動地查詢變成了主動發(fā)現(xiàn)知識的話，那么概率論和數(shù)理統(tǒng)計這一古老的學科可以為我們從數(shù)據(jù)歸納知識――數(shù)據(jù)挖掘技術提供理論基礎。人工智能是計算機科學研究中爭議最多但是仍始終保持強大生命的研究領域。機器學習應該說是得到了充分的研究和發(fā)展，并且數(shù)據(jù)挖掘技術繼承了機器學習解決問題的思想。專家系統(tǒng)（Expert System）曾經(jīng)被認為人工智能向著實用性方向發(fā)展的最有希望的技術，但是，這種技術也逐漸表現(xiàn)出投資大、主觀性強、應用面窄等致命弱點。例如，知識獲取被普遍認為是專家系統(tǒng)研究中的瓶頸問題。另外，由于專家系統(tǒng)是主觀整理知識，因此這種機制不可避免地帶有偏見和錯誤。數(shù)據(jù)挖掘繼承了專家系統(tǒng)的高度實用性特點，并且以數(shù)據(jù)為基本出發(fā)點，客觀地挖掘知識。因此，可以說，數(shù)據(jù)挖掘研究在繼承已有的人工智能相關領域的研究成果的基礎上，擺脫了以前象牙塔式研究模式，真正開始客觀地從數(shù)據(jù)集中發(fā)現(xiàn)蘊藏的知識。 數(shù)據(jù)挖掘概念 從商業(yè)角度看數(shù)據(jù)挖掘技術數(shù)據(jù)挖掘從本質(zhì)上說是一種新的商業(yè)信息處理技術。數(shù)據(jù)挖掘技術把人們對數(shù)據(jù)的應用，從低層次的聯(lián)機查詢操作，提高到?jīng)Q策支持、分析預測等更高級應用上。它通過對這些數(shù)據(jù)進行微觀、中觀乃至宏觀的統(tǒng)計、分析、綜合和推理，發(fā)現(xiàn)數(shù)據(jù)間的關聯(lián)性、未來趨勢以及一般性的概括知識等，這些知識性的信息可以用來指導高級商務活動。從決策、分析和預測等高級商業(yè)目的看，原始數(shù)據(jù)只是未被開采的礦山，需要挖掘和提煉才能獲得對商業(yè)目的有用的規(guī)律性知識。這正是數(shù)據(jù)挖掘這個名字的由來。所以，從商業(yè)角度看，數(shù)據(jù)挖掘就是按企業(yè)的既定業(yè)務目標，對大量的企業(yè)數(shù)據(jù)進行深層次分析以揭示隱藏的、未知的規(guī)律性并將其模型化，從而支持商業(yè)決策活動。從商業(yè)應用角度刻畫數(shù)據(jù)挖掘，可以使我們更全面的了解數(shù)據(jù)挖掘的真正含義。它有別于機器學習等其它研究領域，從它的提出之日起就具有很強的商業(yè)應用目的。同時，數(shù)據(jù)挖掘技術只有面向特定的商業(yè)領域才有應用價值。數(shù)據(jù)挖掘并不是要求發(fā)現(xiàn)放之四海而皆準的真理，所有發(fā)現(xiàn)的知識都是相對的，并且對特定的商業(yè)行為才有指導意義。 數(shù)據(jù)挖掘的技術含義談到數(shù)據(jù)挖掘，必須提到數(shù)據(jù)庫中的知識發(fā)現(xiàn)（KDD： Knowledge Discovery in Databases）。關于KDD與Data Mining的關系，有許多不同的看法。我們可以從這些不同的觀點中了解數(shù)據(jù)挖掘的技術含義。(1) KDD看成數(shù)據(jù)挖掘的一個特例既然數(shù)據(jù)挖掘系統(tǒng)可以在關系數(shù)據(jù)庫、事務數(shù)據(jù)庫、數(shù)據(jù)倉庫、空間數(shù)據(jù)庫（Spatial Database）、文本數(shù)據(jù)（Text Data）以及諸如WEB等多種數(shù)據(jù)組織形式中挖掘知識，那么數(shù)據(jù)庫中的知識發(fā)現(xiàn)只是數(shù)據(jù)挖掘的一個方面。這是早期比較流行的觀點，在許多文獻可以看到這種說法[4，5]。因此，從這個意義說，數(shù)據(jù)挖掘就是從數(shù)據(jù)庫、數(shù)據(jù)倉庫以及其它數(shù)據(jù)存儲方式中挖掘有用知識的過程。這種描述強調(diào)了數(shù)據(jù)挖掘在源數(shù)據(jù)形式上的多樣性。(2) 數(shù)據(jù)挖掘是KDD過程的一個步驟例如，在“知識發(fā)現(xiàn)96國際會議” 上，許多學者建議對這兩個名詞加以區(qū)分[6]。核心思想是：KDD是從數(shù)據(jù)庫中發(fā)現(xiàn)知識的全部過程，而Data Mining則是此全部過程的一個特定的、關鍵步驟。這種觀點有它的合理性。雖然我們可以從數(shù)據(jù)倉庫、WEB等源數(shù)據(jù)中挖掘知識，但是這些數(shù)據(jù)源都是和數(shù)據(jù)庫技術相關的。數(shù)據(jù)倉庫是由源數(shù)據(jù)庫集成而來的，即使是像WEB這樣的數(shù)據(jù)源恐怕也離不開數(shù)據(jù)庫技術來組織和存儲抽取的信息。因此KDD是一個更廣義的范疇，它包括數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)選擇、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)挖掘、模式生成及評估等一系列步驟。這樣，我們可以把KDD看作是一些基本功能構件的系統(tǒng)化協(xié)同工作系統(tǒng)，而數(shù)據(jù)挖掘則是