【正文】 程和系統(tǒng)的各部件功能。鑒于目前數(shù)據(jù)挖掘技術(shù)和關(guān)聯(lián)規(guī)則挖掘研究的現(xiàn)狀和發(fā)展趨勢(shì)，在各類基金的支持下，我們選擇了這一課題開展相關(guān)工作。面對(duì)大型數(shù)據(jù)庫，關(guān)聯(lián)規(guī)則挖掘需要在挖掘效率、可用性、精確性等方面得到提升。從目前的現(xiàn)狀看，大部分學(xué)者認(rèn)為數(shù)據(jù)挖掘的研究仍然處于廣泛研究和探索階段，迫切需要在基礎(chǔ)理論、應(yīng)用模式、系統(tǒng)構(gòu)架以及挖掘算法和挖掘語言等方面進(jìn)行創(chuàng)新。特別是最近幾年，一些基本概念和方法趨于清晰，它的研究正向著更深入的方向發(fā)展。蚅螆膄節(jié)蒞蕿肀芁蕆螄羆芀蕿薇袂 工學(xué)博士學(xué)位論文數(shù)據(jù)挖掘技術(shù)與關(guān)聯(lián)規(guī)則挖掘算法研究毛國君北京工業(yè)大學(xué)2003年4月分類號(hào)：TP311 單位代碼：10005 學(xué) 號(hào)：B200007009 密 級(jí)：北京工業(yè)大學(xué)工學(xué)博士學(xué)位論文題 目: 數(shù)據(jù)挖掘技術(shù)與關(guān)聯(lián)規(guī)則挖掘算法研究 英文題目: DATA MINING TECHNIQUES AND ALGORITHMS FOR MINING ASSOCIATION RULES 研究生姓名： 毛國君 專 業(yè)： 計(jì)算機(jī)應(yīng)用技術(shù) 研究方向：人工智能與知識(shí)工程 導(dǎo)師 姓名： 劉椿年 職 稱：教授 論文報(bào)告提交日期：2003. 4 學(xué)位授予日期： 授予單位名稱和地址：北京工業(yè)大學(xué)（北京市朝陽區(qū)平樂園100號(hào)） 摘要摘 要數(shù)據(jù)挖掘是致力于數(shù)據(jù)分析和理解、揭示數(shù)據(jù)內(nèi)部蘊(yùn)藏知識(shí)的技術(shù)，它成為未來信息技術(shù)應(yīng)用的重要目標(biāo)之一。經(jīng)過十幾年的努力，數(shù)據(jù)挖掘產(chǎn)生了許多新概念和方法。像其它新技術(shù)的發(fā)展歷程一樣，數(shù)據(jù)挖掘技術(shù)也必須經(jīng)過概念提出、概念接受、廣泛研究和探索、逐步應(yīng)用和大量應(yīng)用等階段。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中成果頗豐而且比較活躍的研究分支，留給研究者的是更深入的課題。因此，需要探索新的挖掘理論和模型；需要利用用戶的約束等聚焦挖掘目標(biāo)；需要對(duì)一些傳統(tǒng)的算法進(jìn)行改進(jìn)；也需要研究新的更有效的算法等。本文的研究主要包括數(shù)據(jù)挖掘應(yīng)用系統(tǒng)體系結(jié)構(gòu)、關(guān)聯(lián)規(guī)則挖掘理論及其算法等。由于不同的源數(shù)據(jù)類型、不同的應(yīng)用目標(biāo)以及不同的挖掘策略對(duì)數(shù)據(jù)挖掘系統(tǒng)的功能部件要求不同，這些研究主要是從知識(shí)發(fā)現(xiàn)的基本過程出發(fā)，探討系統(tǒng)應(yīng)具備的主要功能部件及其相互聯(lián)系等?；陧?xiàng)目序列集格空間及其操作，我們建立了關(guān)聯(lián)規(guī)則挖掘模型和算法。ISSDM 算法是建立在嚴(yán)格的項(xiàng)目序列集格理論及其操作基礎(chǔ)上，是一個(gè)一次數(shù)據(jù)庫掃描的而且不使用侯選集的高效算法。結(jié)果表明，ISSDM執(zhí)行時(shí)間整體上優(yōu)于Apriori算法，而且隨著數(shù)據(jù)量的增大ISSDM執(zhí)行時(shí)間的增長(zhǎng)幅度也小于Apriori算法。這部分工作還包括對(duì)時(shí)態(tài)區(qū)間、時(shí)態(tài)約束下的數(shù)據(jù)挖掘空間以及時(shí)態(tài)區(qū)間操作等進(jìn)行了形式化，它們是TISSDM的理論基礎(chǔ)。它是針對(duì)大數(shù)據(jù)集挖掘過程中對(duì)內(nèi)存和CPU等系統(tǒng)資源要求較高的情況被提出和設(shè)計(jì)的，采用了數(shù)據(jù)分割的方法來減少資源的占用?？傊疚脑诜治?、歸類現(xiàn)有數(shù)據(jù)挖掘研究成果以及原型系統(tǒng)的基礎(chǔ)上，進(jìn)行了數(shù)據(jù)挖掘應(yīng)用系統(tǒng)體系結(jié)構(gòu)、關(guān)聯(lián)規(guī)則挖掘理論模型以及算法方面的研究。關(guān)鍵詞：數(shù)據(jù)挖掘，知識(shí)發(fā)現(xiàn)，關(guān)聯(lián)規(guī)則，項(xiàng)目序列集，時(shí)態(tài)約束，數(shù)據(jù)分割。經(jīng)過十幾年的研究，產(chǎn)生了許多新概念和方法。數(shù)據(jù)挖掘之所以被稱為未來信息處理的骨干技術(shù)之一，主要在于它以一種全新的概念改變著人類利用數(shù)據(jù)的方式。但是，數(shù)據(jù)庫技術(shù)作為一種基本的信息存儲(chǔ)和管理方式，仍然以聯(lián)機(jī)事務(wù)處理（OLTP：OnLine Transaction Processing）為核心應(yīng)用，缺少對(duì)決策、分析、預(yù)測(cè)等高級(jí)功能的支持機(jī)制。面對(duì)這一挑戰(zhàn)，數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)（Knowledge Discovery）技術(shù)應(yīng)運(yùn)而生，并顯示出強(qiáng)大的生命力。它不僅能對(duì)過去的數(shù)據(jù)進(jìn)行查詢，并且能夠找出過去數(shù)據(jù)之間的潛在聯(lián)系，進(jìn)行更高層次的分析，以便更好地作出理想的決策、預(yù)測(cè)未來的發(fā)展趨勢(shì)等。勿容置疑，數(shù)據(jù)挖掘研究和應(yīng)用具有很大的挑戰(zhàn)性。從目前的現(xiàn)狀看，大部分學(xué)者認(rèn)為數(shù)據(jù)挖掘的研究仍然處于廣泛研究和探索階段。在理論上，一批具有挑戰(zhàn)性和前瞻性的問題被提出，吸引越來越多的研究者。另一方面，目前的數(shù)據(jù)挖掘系統(tǒng)研制也決不是象一些商家為了宣傳自己商品所說的那樣神奇，仍有許多問題需要研究和探索。所謂Chasm階段是說數(shù)據(jù)挖掘技術(shù)在廣泛被應(yīng)用之前仍有許多“鴻溝”需要攀越。這些工具只能給那些熟悉數(shù)據(jù)挖掘技術(shù)的專家或高級(jí)技術(shù)人員使用，僅對(duì)專業(yè)人員開發(fā)對(duì)應(yīng)的應(yīng)用起到加速或橫向解決方案（Horizontal Solution）的作用。大多數(shù)學(xué)者贊成這樣的觀點(diǎn)：數(shù)據(jù)挖掘在商業(yè)上的成功不能期望通用的輔助開發(fā)工具，而應(yīng)該是數(shù)據(jù)挖掘概念與特定領(lǐng)域商業(yè)邏輯相結(jié)合的縱向解決方案（Vertical Solution）[1] 。它包括領(lǐng)域知識(shí)對(duì)行業(yè)或企業(yè)知識(shí)挖掘的約束與指導(dǎo)、商業(yè)邏輯有機(jī)嵌入數(shù)據(jù)挖掘過程等關(guān)鍵課題。不同的數(shù)據(jù)存儲(chǔ)方式會(huì)影響數(shù)據(jù)挖掘的具體實(shí)現(xiàn)機(jī)制、目標(biāo)定位、技術(shù)有效性等。因此，針對(duì)不同數(shù)據(jù)存儲(chǔ)類型的特點(diǎn)，進(jìn)行針對(duì)性研究是目前流行而且也是將來一段時(shí)間所必須面對(duì)的問題。雖然經(jīng)過多年的探索，數(shù)據(jù)挖掘系統(tǒng)的基本構(gòu)架和過程已經(jīng)趨于明朗，但是受應(yīng)用領(lǐng)域、挖掘數(shù)據(jù)類型以及知識(shí)表達(dá)模式等的影響，在具體的實(shí)現(xiàn)機(jī)制、技術(shù)路線以及各階段或部件（如數(shù)據(jù)清洗、知識(shí)形成、模式評(píng)估等）的功能定位等方面仍需細(xì)化和深入研究。這種交互可能發(fā)生在數(shù)據(jù)挖掘的各個(gè)不同階段，從不同角度或不同粒度進(jìn)行交互。n 數(shù)據(jù)挖掘語言與系統(tǒng)的可視化問題。但是，對(duì)于數(shù)據(jù)挖掘技術(shù)而言，由于誕生的較晚，加之它相比OLTP應(yīng)用的復(fù)雜性，開發(fā)相應(yīng)的數(shù)據(jù)挖掘操作語言仍然是一件極賦挑戰(zhàn)性的工作。對(duì)于一個(gè)數(shù)據(jù)挖掘系統(tǒng)來說，它更是重要的。n 數(shù)據(jù)挖掘理論與算法研究。但是，這決不意味著挖掘理論的探索已經(jīng)結(jié)束，恰恰相反它留給了研究者豐富的理論課題。另一方面，隨著數(shù)據(jù)挖掘技術(shù)本身和相關(guān)技術(shù)的發(fā)展，新的挖掘理論的誕生是必然的，而且可能對(duì)特定的應(yīng)用產(chǎn)生推動(dòng)作用。因此，對(duì)數(shù)據(jù)挖掘理論和算法的探討將是長(zhǎng)期而艱巨的任務(wù)。我們正是在這樣的背景下，在以往的研究和各類基金的支持下，開展相關(guān)研究工作的。在分析現(xiàn)有的數(shù)據(jù)挖掘系統(tǒng)（原型系統(tǒng)）的體系結(jié)構(gòu)基礎(chǔ)上，系統(tǒng)化研究了數(shù)據(jù)挖掘系統(tǒng)的基本過程和功能部件。n 數(shù)據(jù)挖掘理論探索。因此，本文對(duì)關(guān)聯(lián)規(guī)則（Association Rule）挖掘理論和模型進(jìn)行了研究，建立了項(xiàng)目序列集格空間和基于項(xiàng)目序列集操作的關(guān)聯(lián)規(guī)則挖掘模型等。關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中研究較早而且至今仍最活躍的研究分支之一。目前的關(guān)聯(lián)規(guī)則挖掘算法仍然需要在這些方面加以創(chuàng)新或改進(jìn)。 創(chuàng)新性工作 本文的創(chuàng)新性工作集中在數(shù)據(jù)挖掘理論和關(guān)聯(lián)規(guī)則挖掘算法設(shè)計(jì)兩個(gè)方面。我們使用術(shù)語“項(xiàng)目序列（Itemsequence）”來替代其它文獻(xiàn)中出現(xiàn)的“項(xiàng)目集”。因此，我們首次引入的項(xiàng)目序列集（Set of Itemsequences）概念可以用來表示一類特定的項(xiàng)目序列集合（如頻繁項(xiàng)目序列集）。在此基礎(chǔ)上，討論了基于項(xiàng)目序列集操作的數(shù)據(jù)挖掘模型（詳見第4章）。但是，約束條件的引入，必須解決諸如適合數(shù)據(jù)挖掘的約束條件的形式化表示以及約束條件在數(shù)據(jù)挖掘特定階段的使用方式等。在時(shí)態(tài)區(qū)間代數(shù)空間上定義了兩個(gè)新的時(shí)態(tài)區(qū)間變量操作（時(shí)態(tài)交∩T和時(shí)態(tài)并UT）。（3）數(shù)據(jù)分割下的數(shù)據(jù)挖掘理論隨著數(shù)據(jù)庫容量的增大，使得通過對(duì)源數(shù)據(jù)集的分割來處理大容量數(shù)據(jù)庫的數(shù)據(jù)挖掘問題成為必要。 關(guān)聯(lián)規(guī)則挖掘算法設(shè)計(jì)與實(shí)現(xiàn) 把上面的數(shù)據(jù)挖掘理論應(yīng)用到關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)中，我們完成了相應(yīng)算法的設(shè)計(jì)，并且通過理論分析和實(shí)驗(yàn)?zāi)M討論了算法的性能。它是一個(gè)一次數(shù)據(jù)庫掃描并且不使用侯選集的高效算法。它是對(duì)ISSDM算法的改進(jìn)，實(shí)驗(yàn)證明它具有較好的數(shù)據(jù)過濾和區(qū)間合并效率，因而能在同樣的處理環(huán)境下挖掘更大容量的數(shù)據(jù)庫（比ISSDM）。它通過對(duì)數(shù)據(jù)庫的分割，減少了對(duì)內(nèi)存和CPU等系統(tǒng)資源的占用，而且可以在兩次數(shù)據(jù)庫掃描的情況下完成挖掘工作。數(shù)據(jù)挖掘作為二十世紀(jì)信息處理的骨干技術(shù)之一，正以一種全新的概念改變著我們利用數(shù)據(jù)的方式。目前的數(shù)據(jù)挖掘研究正處于蓬勃發(fā)展時(shí)期，有許多具有挑戰(zhàn)性的課題被提出。作為博士論文，我們?cè)诔浞至私饣靖拍詈椭饕夹g(shù)發(fā)展?fàn)顩r的前提下，有選擇地進(jìn)行了重點(diǎn)研究。45第2章 數(shù)據(jù)挖掘技術(shù)第2章 數(shù)據(jù)挖掘技術(shù)數(shù)據(jù)挖掘作為一個(gè)只有十幾年研究歷史的較新研究領(lǐng)域，許多概念和技術(shù)是逐步發(fā)展起來的。我們介紹了數(shù)據(jù)挖掘技術(shù)產(chǎn)生的商業(yè)和技術(shù)背景；，我們從不同視點(diǎn)闡述了數(shù)據(jù)挖掘的概念和主要理論構(gòu)架；，我們從多種角度對(duì)數(shù)據(jù)挖掘系統(tǒng)的分類問題進(jìn)行了概括；，我們從知識(shí)表示模式角度出發(fā)，歸納了主要的數(shù)據(jù)挖掘技術(shù)及其研究成果； ；。60年代，為了適應(yīng)信息的電子化要求，信息技術(shù)一直從簡(jiǎn)單的文件處理系統(tǒng)向有效的數(shù)據(jù)庫系統(tǒng)變革。80年代，關(guān)系型數(shù)據(jù)庫及其相關(guān)的數(shù)據(jù)模型工具、數(shù)據(jù)索引及數(shù)據(jù)組織技術(shù)被廣泛采用，并且成為了整個(gè)數(shù)據(jù)庫市場(chǎng)的主導(dǎo)。從數(shù)據(jù)模型上看，諸如擴(kuò)展關(guān)系、面向?qū)ο?、?duì)象關(guān)系（ObjectRelation）以及演繹模型等被應(yīng)用到數(shù)據(jù)庫系統(tǒng)中。同時(shí)，事務(wù)數(shù)據(jù)庫（Transaction Database）、主動(dòng)數(shù)據(jù)庫（Active Database）、知識(shí)庫（Knowledge Base）、辦公信息庫（Information Base）等技術(shù)也得到蓬勃發(fā)展。進(jìn)入90年代，分布式數(shù)據(jù)庫理論上趨于成熟，分布式數(shù)據(jù)庫技術(shù)得到了廣泛應(yīng)用。但是，這些數(shù)據(jù)庫的應(yīng)用都是以實(shí)時(shí)查詢處理技術(shù)為基礎(chǔ)的。由于簡(jiǎn)單查詢只是數(shù)據(jù)庫內(nèi)容的選擇性輸出，因此它和人們期望的分析預(yù)測(cè)、決策支持等高級(jí)應(yīng)用仍有很大距離。數(shù)據(jù)挖掘的靈魂是深層次的數(shù)據(jù)分析方法。同時(shí)在目前的商業(yè)活動(dòng)中，數(shù)據(jù)分析總是和一些特殊的人群的高智商行為聯(lián)系起來，因?yàn)椴⒉皇敲總€(gè)平常人都能從過去的銷售情況預(yù)測(cè)將來發(fā)展趨勢(shì)或作出正確決策的。因此，探討自動(dòng)化的數(shù)據(jù)分析技術(shù)，為企業(yè)提供能帶來商業(yè)利潤(rùn)的決策信息而成為必然。毫不夸張地說，人們對(duì)于數(shù)據(jù)的擁有欲是貪婪的，特別是計(jì)算機(jī)存儲(chǔ)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展加速了人們收集數(shù)據(jù)的范圍和容量。 Information Poor）”現(xiàn)象的產(chǎn)生。直觀上說，信息或稱有效信息是指對(duì)人們有幫助的數(shù)據(jù)。如果你訂閱了100份報(bào)紙，其實(shí)你每天也不過只閱讀了一份而已。知識(shí)是一種概念、規(guī)則、模式和規(guī)律等。事實(shí)上。我們是通過正面的或反面的數(shù)據(jù)或信息來形成和驗(yàn)證知識(shí)的，同時(shí)又不斷地利用知識(shí)來獲得新的信息。在強(qiáng)大的商業(yè)需求的驅(qū)動(dòng)下，商家們開始注意到有效地解決大容量數(shù)據(jù)的利用問題具有巨大的商機(jī)；學(xué)者們開始思考如何從大容量數(shù)據(jù)集中獲取有用信息和知識(shí)的方法。 數(shù)據(jù)挖掘產(chǎn)生的技術(shù)背景分析任何技術(shù)的產(chǎn)生總是有它的技術(shù)背景的。歸納數(shù)據(jù)挖掘產(chǎn)生的技術(shù)背景，下面一些相關(guān)技術(shù)的發(fā)展起到了決定性的作用：n 數(shù)據(jù)庫、數(shù)據(jù)倉庫和Internet等信息技術(shù)的發(fā)展；n 計(jì)算機(jī)性能的提高和先進(jìn)的體系結(jié)構(gòu)的發(fā)展；n 統(tǒng)計(jì)學(xué)和人工智能等方法在數(shù)據(jù)分析中的研究和應(yīng)用。在關(guān)系型數(shù)據(jù)庫的研究和產(chǎn)品提升過程中，人們一直在探索組織大型數(shù)據(jù)和快速訪問的相關(guān)技術(shù)。在數(shù)據(jù)的快速訪問、集成與抽取等問題的解決上積累了經(jīng)驗(yàn)。另外，Internet的普及也為人們提供了豐富的數(shù)據(jù)源。而且Internet技術(shù)本身的發(fā)展，已經(jīng)不光是簡(jiǎn)單的信息瀏覽，以Web計(jì)算為核心的的信息處理技術(shù)可以處理Internet環(huán)境下的多種信息源。只有這樣，數(shù)據(jù)挖掘技術(shù)才能有它的用武之地。計(jì)算機(jī)芯片技術(shù)的發(fā)展，使計(jì)算機(jī)的處理和存儲(chǔ)能力日益提高。隨之而來的是硬盤、CPU等關(guān)鍵部件的價(jià)格大幅度下降，使得人們收集、存儲(chǔ)和處理數(shù)據(jù)的能力和欲望不斷提高。計(jì)算機(jī)性能的提高和先進(jìn)的體系結(jié)構(gòu)的發(fā)展使數(shù)據(jù)挖掘技術(shù)的研究和應(yīng)用成為可能。這些應(yīng)用從某種程度上為數(shù)據(jù)挖掘技術(shù)的提出和發(fā)展起到了極大地推動(dòng)作用。從某種意義講，這些理論本身發(fā)展和應(yīng)用為數(shù)據(jù)挖掘提供了有價(jià)值的理論和應(yīng)用積累。然而它和數(shù)據(jù)庫技術(shù)的結(jié)合性研究應(yīng)該說最近十幾年才被重視。我們知道，大多數(shù)的統(tǒng)計(jì)分析技術(shù)是基于嚴(yán)格的數(shù)學(xué)理論和高超的應(yīng)用技巧的，這使得一般的用戶很難從容地駕馭它。人工智能是計(jì)算機(jī)科學(xué)研究中爭(zhēng)議最多但是仍始終保持強(qiáng)大生命的研究領(lǐng)域。專家系統(tǒng)（Expert System）曾經(jīng)被認(rèn)為人工智能向著實(shí)用性方向發(fā)展的最有希望的技術(shù)，但是，這種技術(shù)也逐漸表現(xiàn)出投資大、主觀性強(qiáng)、應(yīng)用面窄等致命弱點(diǎn)。另外，由于專家系統(tǒng)是主觀整理知識(shí)，因此這種機(jī)制不可避免地帶有偏見和錯(cuò)誤。因此，可以說，數(shù)據(jù)挖掘研究在繼承已有的人工智能相關(guān)領(lǐng)域的研究成果的基礎(chǔ)上，擺脫了以前象牙塔式研究模式，真正開始客觀地從數(shù)據(jù)集中發(fā)現(xiàn)蘊(yùn)藏的知識(shí)。數(shù)據(jù)挖掘技術(shù)把人們對(duì)數(shù)據(jù)的應(yīng)用，從低層次的聯(lián)機(jī)查詢操作，提高到?jīng)Q策支持、分析預(yù)測(cè)等更高級(jí)應(yīng)用上。從決策、分析和預(yù)測(cè)等高級(jí)商業(yè)目的看，原始數(shù)據(jù)只是未被開采的礦山，需要挖掘和提煉才能獲得對(duì)商業(yè)目的有用的規(guī)律性知識(shí)。所以，從商業(yè)角度看，數(shù)據(jù)挖掘就是按企業(yè)的既定業(yè)務(wù)目標(biāo)，對(duì)大量的企業(yè)數(shù)據(jù)進(jìn)行深層次分析以揭示隱藏的、未知的規(guī)律性并將其模型化，從而支持商業(yè)決策活動(dòng)。它有別于機(jī)器學(xué)習(xí)等其它研究領(lǐng)域，從它的提出之日起就具有很強(qiáng)的商業(yè)應(yīng)用目的。數(shù)據(jù)挖掘并不是要求發(fā)現(xiàn)放之四海而皆準(zhǔn)的真理，所有發(fā)現(xiàn)的知識(shí)都是相對(duì)的，并且對(duì)特定的商業(yè)行為才有指導(dǎo)意義。關(guān)于KDD與Data Mining的關(guān)系，有許多不同的看法。(1) KDD看成數(shù)據(jù)挖掘的一個(gè)特例既然數(shù)據(jù)挖掘系統(tǒng)可以在關(guān)系數(shù)據(jù)庫、事務(wù)數(shù)據(jù)庫、數(shù)據(jù)倉庫、空間數(shù)據(jù)庫（Spatial Database）、文本數(shù)據(jù)（Text Data）以及諸如WEB等多種數(shù)據(jù)組織形式中挖掘知識(shí)，那么數(shù)據(jù)庫中的