資料挖掘技術的算法與應用

研究方向前沿讀書報告 資料挖掘技術的算法與應用 目錄 第一章 資料倉庫 1.1 概論 1.2 資料倉庫體系結構 1.3 資料倉庫規劃、設計與開發 1.3.1 确定範圍 1.3.2 環境評估 1.3.3 分析 1.3.4 設計 1.3.5 開發 1.3.5 測試 1.3.6 運作 1.4 小結 第二章 資料挖掘 2.1 概論 2.2 資料挖掘研究的内容和本質 2.2.1 廣義知識 2.2.2 關聯知識 2.2.3 分類知識 2.2.4 預測型知識 2.3 資料挖掘流程 2.3.1 确定業務對象 2.3.2 資料準備 2.3.3 資料挖掘 2.3.4 結果分析 2.3.5 知識的同化 2.4 資料挖掘的方法 2.4.1 神經網絡方法 2.4.2 遺傳算法 2.4.3 決策樹方法 2.4.4 粗集方法 2.4.5 覆寫正例排斥反例方法 2.4.6 統計分析方法 2.4.7 模糊集方法 2.6 資料挖掘工具的現狀 2.7 資料挖掘未來研究方向及熱點 2.4.1 網站的資料挖掘 2.4.2 生物資訊或基因資料挖掘 2.4.3 文本的資料挖掘 2.4.4 2005年十大熱點問題 2.5 小結 第三章 關聯規則 3.1 概論 3.2 基本概念 3.3 關聯規則種類 3.4 主要研究方向和典型算法分析 3.4.1 多循環方式的采掘算法 3.4.2 增量式更新算法 3.4.3 并行發現算法 3.5 頻集算法的幾種優化方法 3.4.1 基于劃分的方法 3.4.2 基于Hash的方法 3.4.3 基于采樣的方法 3.4.4 減少交易的個數 3.4.5 其他的頻集挖掘方法 3.4.6 提高效率的幾種方法說明 3.6 多層和多元關聯規則的挖掘 3.7 關聯規則價值衡量的方法 3.6.1 系統客觀層面 3.6.2 使用者主觀層面 3.8 選擇規則的方法 3.9 小結 第四章 正負關聯規則研究 4.1 概述 4.2 研究現狀 4.3 關聯規則具體研究 4.3.1 關聯規則挖掘的矩陣算法 4.3.2 基于相關系數的正、負關聯規則 4.3.3 項集的相關性判斷正負關聯規則 4.3.4 正、負關聯規則間的置信度關系研究 4.3.5 挖掘正負關聯規則 4.3.6 布爾權重關聯規則的幾種開采算法及比較 4.3.6 關聯規則的增量式更新 4.3.7 并行化的分組關聯規則算法 4.3.8 分布式的資料挖掘 4.6 研究方向的理論意義和實用價值 4.7 小結 第五章 可視化研究 5.1 概述 5.2 研究現狀 5.3 研究方向的理論意義和實用價值 5.4 可視化具體研究 5.4.1 矩陣表示 5.4.2 規則多邊形 5.4.3 平行坐标系 5.5 小結 參考資料： 本報告的組織 第一章 資料倉庫的内容 第二章 資料挖掘的内容 第三章 關聯規則的内容 第四章 正負關聯規則的研究，各種方法的具體算法 實作。 第五章 可視化研究 第一章 資料倉庫 1.1 概論 傳統資料庫在日常的管理事務進行中獲得了巨大的成功，但是對管理人員的決策分析要求卻無法滿足。因為，管理人員常常希望能夠對組織中的大量資料進行分析，了解業務的發展趨勢。而傳統資料庫隻保留了目前的業務處理資訊，缺乏決策分析所需要的大量曆史資訊。為滿足管理人員的決策分析需要，就需要在資料庫的基礎上産生适應決策分析的資料環境——資料倉庫（DW，Data Warehouse）。[1] 目前，資料倉庫一詞尚沒有一個統一的定義，著名的資料倉庫專家W。H。Inmon在其著作《Building the Data Warehouse》一書中給予如下描述：資料倉庫（Data Warehouse）是一個面向主題的（Subject Oriented）、內建的（Integrate）、相對穩定的（Non-Volatile）、反映曆史變化（Time Variant）的資料集合，用于支援管理決策。對于資料倉庫的概念我們可以從兩個層次予以了解，首先，資料倉庫用于支援決策，面向分析型資料處理，它不同于企業現有的操作型資料庫；其次，資料倉庫是對多個異構的資料源有效內建，內建後按照主題進行了重組，并包含曆史資料，而且存放在資料倉庫中的資料一般不再修改。 根據資料倉庫概念的含義，資料倉庫擁有以下四個特點： 1、面向主題。操作型資料庫的資料組織面向事務處理任務，各個業務系統之間各自分離，而資料倉庫中的資料是按照一定的主題域進行組織。主題是一個抽象的概念，是指使用者使用資料倉庫進行決策時所關心的重點方面，一個主題通常與多個操作型資訊系統相關。 2、內建的。面向事務處理的操作型資料庫通常與某些特定的應用相關，資料庫之間互相獨立，并且往往是異構的。而資料倉庫中的資料是在對原有分散的資料庫資料抽取、清理的基礎上經過系統加工、彙總和整理得到的，必須消除源資料中的不一緻性，以保證資料倉庫内的資訊是關于整個企業的一緻的全局資訊。 3、相對穩定的。操作型資料庫中的資料通常實時更新，資料根據需要及時發生變化。資料倉庫的資料主要供企業決策分析之用，所涉及的資料操作主要是資料查詢，一旦某個資料進入資料倉庫以後，一般情況下将被長期保留，也就是資料倉庫中一般有大量的查詢操作，但修改和删除操作很少，通常隻需要定期的加載、重新整理。 4、反映曆史變化。操作型資料庫主要關心目前某一個時間段内的資料，而資料倉庫中的資料通常包含曆史資訊，系統記錄了企業從過去某一時點(如開始應用資料倉庫的時點)到目前的各個階段的資訊，通過這些資訊，可以對企業的發展曆程和未來趨勢做出定量分析和預測。 通過利用資料倉庫系統，人們可以獲得許多方面的知識。[7] 1.2 資料倉庫體系結構 企業資料倉庫的建設，是以現有企業業務系統和大量業務資料的積累為基礎。資料倉庫不是靜态的概念，隻有把資訊及時交給需要這些資訊的使用者，供他們做出改善其業務經營的決策，資訊才能發揮作用，資訊才有意義。而把資訊加以整理歸納和重組，并及時提供給相應的管理決策人員，是資料倉庫的根本任務。是以，從産業界的角度看，資料倉庫建設是一個工程，是一個過程。整個資料倉庫系統是一個包含四個層次的體系結構，具體由下圖表示: ·資料源：是資料倉庫系統的基礎，是整個系統的資料源泉。通常包括企業内部資訊和外部資訊。内部資訊包括存放于RDBMS中的各種業務處理資料和各類文檔資料。外部資訊包括各類法律法規、市場資訊和競争對手的資訊等等。 ·資料的存儲與管理：是整個資料倉庫系統的核心。資料倉庫的真正關鍵是資料的存儲和管理。資料倉庫的組織管理方式決定了它有别于傳統資料庫，同時也決定了其對外部資料的表現形式。要決定采用什麼産品和技術來建立資料倉庫的核心，則需要從資料倉庫的技術特點着手分析。針對現有各業務系統的資料，進行抽取、清理，并有效內建，按照主題進行組織。資料倉庫按照資料的覆寫範圍可以分為企業級資料倉庫和部門級資料倉庫（通常稱為資料集市）。 ·OLAP伺服器：對分析需要的資料進行有效內建，按多元模型予以組織，以便進行多角度、多層次的分析，并發現趨勢。其具體實作可以分為：ROLAP、MOLAP和HOLAP。ROLAP基本資料和聚合資料均存放在RDBMS之中；MOLAP基本資料和聚合資料均存放于多元資料庫中；HOLAP基本資料存放于RDBMS之中，聚合資料存放于多元資料庫中。 ·前端工具：主要包括各種報表工具、查詢工具、資料分析工具、資料挖掘工具以及各種基于資料倉庫或資料集市的應用開發工具。其中資料分析工具主要針對OLAP伺服器，報表工具、資料挖掘工具主要針對資料倉庫。[8] 1.3 資料倉庫規劃、設計與開發 對企業自身來說，資料倉庫的建設是一個系統工程，是一個不斷建立、發展、完善的過程，通常需要較長的時間。這就要求各企業對整個系統的建設提出一個全面、清晰的遠景規劃及技術實施藍圖，将整個項目的實施分成若幹個階段，以“總體規劃、分步實施、步步見效”為原則，不僅可迅速從目前投資中獲得收益，而且可以在已有的基礎上，結合其他已有的業務系統，逐漸建構起完整、健壯的資料倉庫系統。 企業資料倉庫的建設通常按照快速原型法予以實施，主要包括：确定範圍、環境評估、分析、設計、開發、測試和運作等幾個階段。同時企業資料倉庫又是一個在原型的基礎上進行不斷疊代的過程。 1.3.1 确定範圍 确定範圍的主要任務包括了解方向性分析處理需求，确定資訊需求，确定資料覆寫範圍。方向性需求包括：決策類型、決策者感興趣的問題（或對象）等。在确定範圍時應該重視的因素是必須使用者驅動和資料驅動相結合，同時可以借鑒國内外已有的成功經驗。 1.3.2 環境評估 環境評估是對企業資料倉庫系統建設的硬體環境和軟體環境進行選型和準備。在硬體平台選擇中需要選擇與資料倉庫系統規模相适應的核心伺服器，同時我們認為資料倉庫系統平台與業務處理平台應該相分離。軟體平台的選擇主要包括資料倉庫引擎、OLAP引擎、前端分析展現工具的選擇。産品進行測試是軟體選型的一種有效方法，各個企業可以根據自身的資料狀況對各類産品進行測試。 1.3.3 分析 分析階段主要包括兩個方面的任務是深入了解資料源和分析資料倉庫系統所包含的主題域及其互相之間的關系。分析階段必須堅持使用者參與，并且與原有系統開發或維護人員進行深入的溝通。 需求分析包括一下的工作：确定資料倉庫的粒度；确定候選的衡量名額（Candidate Measure）、事實表以及次元，包括确定次元的層次結構；建構初始的多元模型。[5] 1.3.4 設計 資料倉庫設計的主要任務包括與操作型系統接口的設計和資料倉庫本身的設計兩個部分的内容。其中與操作型系統接口的設計主要是指資料抽取、清理、轉換和重新整理政策的設計。從多個不同的資料源中抽取資料，需要解決資料的不一緻性，保證資料的品質。其中的不一緻性主要包含模式沖突和語義沖突。從操作型資料庫模型到資料倉庫模型的轉變需要大量細緻的工作，例如：－消除純粹是操作型的資料；－将包含在多個表中的有關資料進行合理合并；－适當增加部分導出資料；－在碼值中增加時間關鍵字；－按照合适的資料粒度進行綜合。 資料倉庫本身的設計包括資料倉庫邏輯資料模型的設計、資料倉庫實體資料模型的設計。由于目前資料倉庫産品尚未形成一套統一的标準，是以在資料倉庫設計階段必須要有資料倉庫專家和資料倉庫系統産品提供商的參與。 目前，主流的資料倉庫模組化技術分為兩種：實體關系模組化（Entity-Relationship Modeling）以及維模組化（Dimension Modeling）。其中，維模組化又分為星型結構以及雪花型結構等。[5] 資料倉庫設計工具的選擇有： EDA/SQL。(SAS Institute Inc。)SAS研究所 (Sybase,Inc。)Sysbase有限公司[3] CA公司的Erwin[5] 1.3.5 開發 開發階段所要完成的主要内容包括資料倉庫模組化、資料抽取和加載子產品、資料通路子產品以及開發實際應用。實際應用開發建議采用撌緣銛的方法，從急需的業務開始進行，應該重視的因素包括必須有行業專家的參與，同時必須有資料倉庫專家的參與。 1.3.5 測試 測試是保證系統可靠性的重要手段。資料倉庫測試與一般軟體系統測試不同的是資料倉庫的測試不僅包括對軟體系統的測試，同時包括對資料的測試。在測試階段必須保證測試的充分性，同時注意測試資料的覆寫範圍。 1.3.6 運作 系統運作主要包括使用者教育訓練、資料加載、資料通路及應用等。在資料倉庫系統的運作過程中，不斷收集使用者新的需求。 資料倉庫系統的建設不可能一蹴而就，它是一個不斷建立、完善、健全的過程。這個過程是随着業務量、業務範圍和客戶的不斷發展而發展的，其成長的速度非常之快，同時随着業務的發展，資料倉庫的價值也将随之增長。[8] 1.4 小結 本章主要介紹說明資料倉庫的相關概念、體系結構和設計開發等。為資料挖掘的前期工作做準備。為資料挖掘提供良好的環境。當然，資料倉庫并不是資料挖掘的先決條件，因為有很多資料挖掘可直接從操作資料源中挖掘資訊。 第二章 資料挖掘 2.1 概論 資料挖掘（Data Mining）是發現資料中有用模式的過程。資料挖掘會話的目的是确定資料的趨勢和模式。[4] 資料挖掘強調對大量觀測到的資料庫的處理。它是涉及資料庫管理，人工智能，機器學習，模式識别，及資料可視化等學科的邊緣學科。用統計的觀點看，它可以看成是通過計算機對大量的複雜資料集的自動探索性分析。 顧名思義, 資料挖掘就是從大量的資料中挖掘出有用的資訊。它是根據人們的特定要求，從浩如煙海的資料中找出所需的資訊來，供人們的特定需求使用。2000年7月，IDC釋出了有關資訊存取工具市場的報告。1999年，資料挖掘市場大概約為7。5億美元，估計在下個5年内市場的年增長率為32。4%，其中亞太地區為26。6%。到2002年，該市場會發展到22億美元。據國外專家預測，随着資料量的日益積累和計算機的廣泛應用，在今後的5—10年内，資料挖掘将在中國形成一個新型的産業。 資料挖掘技術是人們長期對資料庫技術進行研究和開發的結果。起初各種商業資料是存儲在計算機的資料庫中的，然後發展到可對資料庫進行查詢和通路，進而發展到對資料庫的即時周遊。資料挖掘使資料庫技術進入了一個更進階的階段，它不僅能對過去的資料進行查詢和周遊，并且能夠找出過去資料之間的潛在聯系，進而促進資訊的傳遞。現在資料挖掘技術在商業應用中已經可以馬上投入使用，因為對這種技術進行支援的三種基礎技術已經發展成熟，他們是：(1) 海量資料搜集；(2)強大的多處理器計算機；(3)資料挖掘算法。Friedman[1997]列舉了四個主要的技術理由激發了資料挖掘的開發、應用和研究的興趣：（1）超大規模資料庫的出現，例如商業資料倉庫和計算機自動收集的資料記錄；（2）先進的計算機技術，例如更快和更大的計算能力和并行體系結構；（3）對巨大量資料的快速通路；（4） 對這些資料應用精深的統計方法計算的能力。 商業資料庫現在正在以一個空前的速度增長，并且資料倉庫正在廣泛地應用于各種行業；對計算機硬體性能越來越高的要求，也可以用現在已經成熟的并行多處理機的技術來滿足；另外資料挖掘算法經過了這10多年的發展也已經成為一種成熟，穩定，且易于了解和操作的技術。 随着在80年代末一個新的術語，它就是資料庫中的知識發現，簡稱KDD(Knowledge discovery in database)。它泛指所有從源資料中發掘模式或聯系的方法，人們接受了這個術語，并用KDD來描述整個資料發掘的過程，包括最開始的制定業務目标到最終的結果分析，而用資料挖掘（data mining）來描述使用挖掘算法進行資料挖掘的子過程。[9] 資料挖掘與傳統的資料分析(如查詢、報表、聯機應用分析)的本質差別是資料挖掘是在沒有明确假設的前提下去挖掘資訊、發現知識。資料挖掘所得到的資訊應具有先未知,有效和可實用三個特征。 基于并行系統的資料庫管理系統也給資料挖掘技術的應用帶來了便利。如果你有一個龐大而複雜的資料挖掘問題要求通過通路資料庫取得資料，那麼效率最高的辦法就是利用一個本地的并行資料庫。 現在面臨一個尴尬的境地——資料豐富資訊匮乏（data rich but information poor）！快速增長的海量資料，已經遠遠的超過了人們的了解能力，如果不借助強有力的工具，很難弄清大堆資料中所蘊含的知識。結果，重要決策隻是基于制定決策者的個人經驗，而不是基于資訊豐富的資料。資料挖掘就這樣應運而生，資料挖掘填補了資料和資訊之間的鴻溝。[11] 2.2 資料挖掘研究的内容和本質 随着DM/KDD研究逐漸走向深入，資料挖掘和知識發現的研究已經形成了三根強大的技術支柱：資料庫、人工智能和數理統計。是以，KDD大會程式委員會曾經由這三個學科的權威人物同時來任主席。目前DM/KDD的主要研究内容包括基礎理論、發現算法、資料倉庫、可視化技術、定性定量互換模型、知識表示方法、發現知識的維護和再利用、半結構化和非結構化資料中的知識發現以及網上資料挖掘等。 資料挖掘所發現的知識最常見的有以下四類： 2.2.1 廣義知識 廣義知識指類别特征的概括性描述知識。根據資料的微觀特性發現其表征的、帶有普遍性的、較高層次概念的、中觀和宏觀的知識，反映同類事物共同性質，是對資料的概括、精煉和抽象。 廣義知識的發現方法和實作技術有很多，如資料立方體、面向屬性的歸約等。資料立方體還有其他一些别名，如“多元資料庫”、“實作視圖”、“OLAP"等。該方法的基本思想是實作某些常用的代價較高的聚集函數的計算，諸如計數、求和、平均、最大值等，并将這些實作視圖儲存在多元資料庫中。既然很多聚集函數需經常重複計算，那麼在多元資料立方體中存放預先計算好的結果将能保證快速響應，并可靈活地提供不同角度和不同抽象層次上的資料視圖。另一種廣義知識發現方法是加拿大SimonFraser大學提出的面向屬性的歸約方法。這種方法以類SQL語言表示資料挖掘查詢，收集資料庫中的相關資料集，然後在相關資料集上應用一系列資料推廣技術進行資料推廣，包括屬性删除、概念樹提升、屬性門檻值控制、計數及其他聚集函數傳播等。 2.2.2 關聯知識 它反映一個事件和其他事件之間依賴或關聯的知識。如果兩項或多項屬性之間存在關聯，那麼其中一項的屬性值就可以依據其他屬性值進行預測。最為著名的關聯規則發現方法是R。Agrawal提出的Apriori算法。關聯規則的發現可分為兩步。第一步是疊代識别所有的頻繁項目集，要求頻繁項目集的支援率不低于使用者設定的最低值；第二步是從頻繁項目集中構造可信度不低于使用者設定的最低值的規則。識别或發現所有頻繁項目集是關聯規則發現算法的核心，也是計算量最大的部分。 2.2.3 分類知識 它反映同類事物共同性質的特征型知識和不同僚物之間的差異型特征知識。最為典型的分類方法是基于決策樹的分類方法。它是從執行個體集中構造決策樹，是一種有指導的學習方法。該方法先根據訓練子集（又稱為視窗）形成決策樹。如果該樹不能對所有對象給出正确的分類，那麼選擇一些例外加入到視窗中，重複該過程一直到形成正确的決策集。最終結果是一棵樹，其葉結點是類名，中間結點是帶有分枝的屬性，該分枝對應該屬性的某一可能值。　　資料分類還有統計、粗糙集（RoughSet）等方法。線性回歸和線性辨識分析是典型的統計模型。為降低決策樹生成代價，人們還提出了一種區間分類器。最近也有人研究使用神經網絡方法在資料庫中進行分類和規則提取。 2.2.4 預測型知識 它根據時間序列型資料，由曆史的和目前的資料去推測未來的資料，也可以認為是以時間為關鍵屬性的關聯知識。 目前，時間序列預測方法有經典的統計方法、神經網絡和機器學習等。1968年Box和Jenkins提出了一套比較完善的時間序列模組化理論和分析方法，這些經典的數學方法通過建立随機模型，如自回歸模型、自回歸滑動平均模型、求和自回歸滑動平均模型和季節調整模型等，進行時間序列的預測。由于大量的時間序列是非平穩的，其特征參數和資料分布随着時間的推移而發生變化。是以，僅僅通過對某段曆史資料的訓練，建立單一的神經網絡預測模型，還無法完成準确的預測任務。為此，人們提出了基于統計學和基于精确性的再訓練方法，當發現現存預測模型不再适用于目前資料時，對模型重新訓練，獲得新的權重參數，建立新的模型。也有許多系統借助并行算法的計算優勢進行時間序列預測。 此外，還可以發現其他類型的知識，如偏差型知識(Deviation)，它是對差異和極端特例的描述，揭示事物偏離正常的異常現象，如标準類外的特例，資料聚類外的離群值等。所有這些知識都可以在不同的概念層次上被發現，并随着概念層次的提升，從微觀到中觀、到宏觀，以滿足不同使用者不同層次決策的需要。[9] 2.3 資料挖掘流程 　　資料挖掘是指一個完整的過程,該過程從大型資料庫中挖掘先前未知的,有效的,可實用的資訊,并使用這些資訊做出決策或豐富知識。 　　資料挖掘環境可示意如下圖: 　　　下圖描述了資料挖掘的基本過程和主要步驟 資料挖掘的基本過程和主要步驟： 在資料挖掘中被研究的業務對象是整個過程的基礎,它驅動了整個資料挖掘過程,也是檢驗最後結果和指引分析人員完成資料挖掘的依據和顧問。 過程中各步驟的大體内容如下: 2.3.1 确定業務對象 清晰地定義出業務問題,認清資料挖掘的目的是資料挖掘的重要一步。挖掘的最後結構是不可預測的,但要探索的問題應是有預見的,為了資料挖掘而資料挖掘則帶有盲目性,是不會成功的。 2.3.2 資料準備 (1) 資料的選擇 搜尋所有與業務對象有關的内部和外部資料資訊,并從中選擇出适用于資料挖掘應用的資料。 (2) 資料的預處理 研究資料的品質,為進一步的分析作準備。并确定将要進行的挖掘操作的類型。 (3) 資料的轉換 将資料轉換成一個分析模型。這個分析模型是針對挖掘算法建立的。建立一個真正适合挖掘算法的分析模型是資料挖掘成功的關鍵。 2.3.3 資料挖掘 　　對所得到的經過轉換的資料進行挖掘。除了完善從選擇合适的挖掘算法外,其餘一切工作都能自動地完成。 2.3.4 結果分析 　　解釋并評估結果。其使用的分析方法一般應作資料挖掘操作而定,通常會用到可視化技術。 2.3.5 知識的同化 　将分析所得到的知識內建到業務資訊系統的組織結構中去。 　　資料挖掘過程的分步實作,不同的步會需要是有不同專長的人員,他們大體可以分為三類。 業務分析人員:要求精通業務,能夠解釋業務對象,并根據各業務對象确定出用于資料定義和挖掘算法的業務需求。 資料分析人員:精通資料分析技術,并對統計學有較熟練的掌握,有能力把業務需求轉化為資料挖掘的各步操作,并為每步操作選擇合适的技術。 資料管理人員:精通資料管理技術,并從資料庫或資料倉庫中收集資料。 　　從上可見,資料挖掘是一個多種專家合作的過程,也是一個在資金上和技術上高投入的過程。這一過程要反複進行牞在反複過程中，不斷地趨近事物的本質，不斷地優先問題的解決方案。資料重組和細分添加和拆分記錄選取資料樣本可視化資料探索聚類分析神經網絡、決策樹數理統計、時間序列結論綜合解釋評價資料知識資料取樣資料探索資料調整模型化評價。[9] 2.4 資料挖掘的方法 2.4.1 神經網絡方法 神經網絡由于本身良好的健壯性、自組織自适應性、并行處理、分布存儲和高度容錯等特性非常适合解決資料挖掘的問題，是以近年來越來越受到人們的關注。典型的神經網絡模型主要分3大類：以感覺機、BP反向傳播模型、函數型網絡為代表的，用于分類、預測和模式識别的前饋式神經網絡模型；以Hopfield的離散模型和連續模型為代表的，分别用于聯想記憶和優化計算的回報式神經網絡模型；以ART模型、Koholon模型為代表的，用于聚類的自組織映射方法。神經網絡方法的缺點是"黑箱"性，人們難以了解網絡的學習和決策過程。 2.4.2 遺傳算法 遺傳算法是一種基于生物自然選擇與遺傳機理的随機搜尋算法，是一種仿生全局優化方法。遺傳算法具有的隐含并行性、易于和其它模型結合等性質使得它在資料挖掘中被加以應用。 Sunil已成功地開發了一個基于遺傳算法的資料挖掘工具，利用該工具對兩個飛機失事的真實資料庫進行了資料挖掘實驗，結果表明遺傳算法是進行資料挖掘的有效方法之一[4]。遺傳算法的應用還展現在與神經網絡、粗集等技術的結合上。如利用遺傳算法優化神經網絡結構，在不增加錯誤率的前提下，删除多餘的連接配接和隐層單元；用遺傳算法和BP算法結合訓練神經網絡，然後從網絡提取規則等。但遺傳算法的算法較複雜，收斂于局部極小的較早收斂問題尚未解決。 2.4.3 決策樹方法 決策樹是一種常用于預測模型的算法，它通過将大量資料有目的分類，從中找到一些有價值的，潛在的資訊。它的主要優點是描述簡單，分類速度快，特别适合大規模的資料處理。最有影響和最早的決策樹方法是由Quinlan提出的著名的基于資訊熵的ID3算法。它的主要問題是：ID3是非遞增學習算法；ID3決策樹是單變量決策樹，複雜概念的表達困難；同性間的互相關系強調不夠；抗噪性差。針對上述問題，出現了許多較好的改進算法，如 Schlimmer和Fisher設計了ID4遞增式學習算法;鐘鳴，陳文偉等提出了IBLE算法等。 2.4.4 粗集方法 粗集理論是一種研究不精确、不确定知識的數學工具。粗集方法有幾個優點：不需要給出額外資訊；簡化輸入資訊的表達空間；算法簡單，易于操作。粗集處理的對象是類似二維關系表的資訊表。目前成熟的關系資料庫管理系統和新發展起來的資料倉庫管理系統，為粗集的資料挖掘奠定了堅實的基礎。但粗集的數學基礎是集合論，難以直接處理連續的屬性。而現實資訊表中連續屬性是普遍存在的。是以連續屬性的離散化是制約粗集理論實用化的難點。現在國際上已經研制出來了一些基于粗集的工具應用軟體，如加拿大Regina大學開發的KDD-R;美國Kansas大學開發的LERS等。 2.4.5 覆寫正例排斥反例方法 它是利用覆寫所有正例、排斥所有反例的思想來尋找規則。首先在正例集合中任選一個種子，到反例集合中逐個比較。與字段取值構成的選擇子相容則舍去，相反則保留。按此思想循環所有正例種子，将得到正例的規則(選擇子的合取式)。比較典型的算法有Michalski的AQ11方法、洪家榮改進的AQ15方法以及他的AE5方法。 2.4.6 統計分析方法 在資料庫字段項之間存在兩種關系：函數關系(能用函數公式表示的确定性關系)和相關關系(不能用函數公式表示，但仍是相關确定性關系)，對它們的分析可采用統計學方法，即利用統計學原理對資料庫中的資訊進行分析。可進行常用統計(求大量資料中的最大值、最小值、總和、平均值等)、回歸分析(用回歸方程來表示變量間的數量關系)、相關分析(用相關系數來度量變量間的相關程度)、差異分析(從樣本統計量的值得出差異來确定總體參數之間是否存在差異)等。 2.4.7 模糊集方法 即利用模糊集合理論對實際問題進行模糊評判、模糊決策、模糊模式識别和模糊聚類分析。系統的複雜性越高，模糊性越強，一般模糊集合理論是用隸屬度來刻畫模糊事物的亦此亦彼性的。李德毅等人在傳統模糊理論和機率統計的基礎上，提出了定性定量不确定性轉換模型--雲模型，并形成了雲理論。 2.5 如何評價資料挖掘軟體 越來越多的軟體供應商加入了資料挖掘這一領域的競争。使用者如何正确評價一個商業軟體，選擇合适的軟體成為資料挖掘成功應用的關鍵。 評價一個資料挖掘軟體主要應從以下四個主要方面： ⑴計算性能：如該軟體能否在不同的商業平台運作；軟體的架構；能否連接配接不同的資料源；操作大資料集時，性能變化是線性的還是指數的;算的效率；是否基于元件結構易于擴充；運作的穩定性等； ⑵功能性：如軟體是否提供足夠多樣的算法；能否避免挖掘過程黑箱化；軟體提供的算法能否應用于多種類型的資料；使用者能否調整算法和算法的參數；軟體能否從資料集随機抽取資料建立預挖掘模型；能否以不同的形式表現挖掘結果等； ⑶可用性：如使用者界面是否友好；軟體是否易學易用；軟體面對的使用者：初學者，進階使用者還是專家？錯誤報告對使用者調試是否有很大幫助；軟體應用的領域：是專攻某一專業領域還是适用多個領域等； ⑷輔助功能：如是否允許使用者更改資料集中的錯誤值或進行資料清洗；是否允許值的全局替代；能否将連續資料離散化；能否根據使用者制定的規則從資料集中提取子集；能否将資料中的空值用某一适當均值或使用者指定的值代替；能否将一次分析的結果回報到另一次分析中，等等。 2.6 資料挖掘工具的現狀 比較著名的有IBM Intelligent Miner、SAS Enterprise Miner、SPSS Clementine等，它們都能夠提供正常的挖掘過程和挖掘模式。 (1) Intelligent Miner 由美國IBM公司開發的資料挖掘軟體Intelligent Miner是一種分别面向資料庫和文本資訊進行資料挖掘的軟體系列,它包括Intelligent Miner for Data和Intelligent Miner for Text。Intelligent Miner for Data可以挖掘包含在資料庫、資料倉庫和資料中心中的隐含資訊,幫助使用者利用傳統資料庫或普通檔案中的結構化資料進行資料挖掘。它已經成功應用于市場分析、詐騙行為監測及客戶聯系管理等；Intelligent Miner for Text允許企業從文本資訊進行資料挖掘，文本資料源可以是文本檔案、Web頁面、電子郵件、Lotus Notes資料庫等等。 (2) Enterprise Miner 這是一種在我國的企業中得到采用的資料挖掘工具，比較典型的包括上海寶鋼配礦系統應用和鐵路部門在春運客運研究中的應用。SAS Enterprise Miner是一種通用的資料挖掘工具，按照"抽樣--探索--轉換--模組化--評估"的方法進行資料挖掘。可以與SAS資料倉庫和OLAP內建，實作從提出資料、抓住資料到得到解答的"端到端"知識發現。 (3) SPSS Clementine SPSS Clementine是一個開放式資料挖掘工具，曾兩次獲得英國政府SMART 創新獎，它不但支援整個資料挖掘流程，從資料擷取、轉化、模組化、評估到最終部署的全部過程，還支援資料挖掘的行業标準--CRISP-DM。Clementine的可視化資料挖掘使得"思路"分析成為可能，即将集中精力在要解決的問題本身，而不是局限于完成一些技術性工作（比如編寫代碼）。提供了多種圖形化技術，有助了解資料間的關鍵性聯系，指導使用者以最便捷的途徑找到問題的最終解決辦法。 其它常用的資料挖掘工具還有LEVEL5 Quest 、MineSet (SGI) 、Partek 、SE-Learn 、SPSS 的資料挖掘軟體Snob、Ashraf Azmy 的SuperQuery 、WINROSA 、XmdvTool 等[26]。 2.7 資料挖掘未來研究方向及熱點 目前，DM/KDD研究方興未艾，其研究與開發的總體水準相當于資料庫技術在70年代所處的地位，迫切需要類似于關系模式、DBMS系統和SQL查詢語言等理論和方法的指導，才能使DM/KDD的應用得以普遍推廣。預計在本世紀，DM/KDD的研究還會形成更大的高潮，研究焦點可能會集中到以下幾個方面： 發現語言的形式化描述，即研究專門用于知識發現的資料挖掘語言，也許會像SQL語言一樣走向形式化和标準化； 尋求資料挖掘過程中的可視化方法，使知識發現的過程能夠被使用者了解，也便于在知識發現的過程中進行人機互動； 研究在網絡環境下的資料挖掘技術（WebMining），特别是在網際網路上建立DM/KDD伺服器，并且與資料庫伺服器配合，實作WebMining； 加強對各種非結構化資料的開采（DataMiningforAudio＆Video），如對文本資料、圖形資料、視訊圖像資料、聲音資料乃至綜合多媒體資料的開采； 處理的資料将會涉及到更多的資料類型，這些資料類型或者比較複雜，或者是結構比較獨特。為了處理這些複雜的資料，就需要一些新的和更好的分析和建立模型的方法，同時還會涉及到為處理這些複雜或獨特資料所做的費時和複雜資料準備的一些工具和軟體。 互動式發現； 知識的維護更新。 但是，不管怎樣，需求牽引與市場推動是永恒的，DM/KDD将首先滿足資訊時代使用者的急需，大量的基于DM/KDD的決策支援軟體産品将會問世。 就目前來看，将來的幾個熱點包括網站的資料挖掘（Web site data mining）、生物資訊或基因（Bioinformatics/genomics）的資料挖掘及其文本的資料挖掘（Textual mining）。下面就這幾個方面加以簡單介紹。 2.4.1 網站的資料挖掘 需求随着Web技術的發展，各類電子商務網站風起雲湧，建立起一個電子商務網站并不困難，困難的是如何讓您的電子商務網站有效益。要想有效益就必須吸引客戶，增加能帶來效益的客戶忠誠度。電子商務業務的競争比傳統的業務競争更加激烈，原因有很多方面，其中一個因素是客戶從一個電子商務網站轉換到競争對手那邊，隻需點選幾下滑鼠即可。網站的内容和層次、用詞、标題、獎勵方案、服務等任何一個地方都有可能成為吸引客戶、同時也可能成為失去客戶的因素。而同時電子商務網站每天都可能有上百萬次的線上交易，生成大量的記錄檔案（Logfiles）和登記表，如何對這些資料進行分析和挖掘，充分了解客戶的喜好、購買模式，甚至是客戶一時的沖動，設計出滿足于不同客戶群體需要的個性化網站，進而增加其競争力，幾乎變得勢在必行。若想在競争中生存進而獲勝，就要比您的競争對手更了解客戶。 電子商務網站資料挖掘，在對網站進行資料挖掘時，所需要的資料主要來自于兩個方面：一方面是客戶的背景資訊，此部分資訊主要來自于客戶的登記表；而另外一部分資料主要來自浏覽者的點選流（Click-stream），此部分資料主要用于考察客戶的行為表現。但有的時候，客戶對自己的背景資訊十分珍重，不肯把這部分資訊填寫在登記表上，這就會給資料分析和挖掘帶來不便。在這種情況之下，就不得不從浏覽者的表現資料中來推測客戶的背景資訊，進而再加以利用。 就分析和建立模型的技術和算法而言，網站的資料挖掘和原來的資料挖掘差别并不是特别大，很多方法和分析思想都可以運用。所不同的是網站的資料格式有很大一部分來自于點選流，和傳統的資料庫格式有差別。因而對電子商務網站進行資料挖掘所做的主要工作是資料準備。目前，有很多廠商正在緻力于開發專門用于網站挖掘的軟體。 2.4.2 生物資訊或基因資料挖掘 　　生物資訊或基因資料挖掘則完全屬于另外一個領域，在商業上很難講有多大的價值，但對于人類卻受益非淺。例如，基因的組合千變萬化，得某種病的人的基因和正常人的基因到底差别多大？能否找出其中不同的地方，進而對其不同之處加以改變，使之成為正常基因？這都需要資料挖掘技術的支援。 對于生物資訊或基因的資料挖掘和通常的資料挖掘相比，無論在資料的複雜程度、資料量還有分析和建立模型的算法而言，都要複雜得多。從分析算法上講，更需要一些新的和好的算法。現在很多廠商正在緻力于這方面的研究。但就技術和軟體而言，還遠沒有達到成熟的地步。 （1） 2.4.3 文本的資料挖掘 人們很關心的另外一個話題是文本資料挖掘。舉個例子，在客戶服務中心，把同客戶的談話轉化為文本資料，再對這些資料進行挖掘，進而了解客戶對服務的滿意程度和客戶的需求以及客戶之間的互相關系等資訊。從這個例子可以看出，無論是在資料結構還是在分析處理方法方面，文本資料挖掘和前面談到的資料挖掘相差很大。文本資料挖掘并不是一件容易的事情，尤其是在分析方法方面，還有很多需要研究的專題。目前市場上有一些類似的軟體，但大部分方法隻是把文本移來移去，或簡單地計算一下某些詞彙的出現頻率，并沒有真正的分析功能。 随着計算機計算能力的發展和業務複雜性的提高，資料的類型會越來越多、越來越複雜，資料挖掘将發揮出越來越大的作用。[9] 2.4.4 2005年十大熱點問題 在2005ICDM的大會上，給出了一下10個挑戰性的問題： （1） 發展統一的資料挖掘理論 （2） 多元的資料挖掘和高速流的資料挖掘 （3） 時序系列的資料挖掘 （4） 從複雜資料中的複雜知識的挖掘 （5） 網絡的資料挖掘 （6） 分布式資料挖掘和多代理的資料挖掘 （7） 生物和環境問題的資料挖掘 （8） 相關問題的資料挖掘過程 （9） 安全，隐私和資料一緻性 （10） 動态、不均衡和權值資料的資料挖[12] 2.5 小結 本章主要介紹資料挖掘的相關知識。看看是否發現有什麼可以研究的，并了解其過程以及未來研究的方向熱點等問題。通過對資料挖掘的了解，可以在以後的挖掘過程中互相采用比較好的算法，實作綜合應用。或對自己的思想有所啟發。創造更好的挖掘算法。 第三章 關聯規則 3.1 概論 資料關聯是資料庫中存在的一類重要的可被發現的知識。若兩個或多個變量的取值之間存在某種規律性，就稱為關聯。關聯可分為簡單關聯、時序關聯、因果關聯。關聯分析的目的是找出資料庫中隐藏的關聯網。有時并不知道資料庫中資料的關聯函數，即使知道也是不确定的，是以關聯分析生成的規則帶有可信度。 關聯規則挖掘發現大量資料中項集之間有趣的關聯或相關聯系。它在資料挖掘中是一個重要的課題，最近幾年已被業界所廣泛研究。關聯規則挖掘的一個典型例子是購物籃分析。關聯規則研究有助于發現交易資料庫中不同商品（項）之間的聯系，找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。分析結果可以應用于商品貨架布局、貨存安排以及根據購買模式對使用者進行分類。 Agrawal等于1993年首先提出了挖掘顧客交易資料庫中項集間的關聯規則問題[20]，以後諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。他們的工作包括對原有的算法進行優化，如引入随機采樣、并行的思想等，以提高算法挖掘規則的效率；對關聯規則的應用進行推廣。 最近也有獨立于Agrawal的頻集方法的工作，以避免頻集方法的一些缺陷，探索挖掘關聯規則的新方法。也有一些工作注重于對挖掘到的模式的價值進行評估，他們提出的模型建議了一些值得考慮的研究方向。 3.2 基本概念 在1993年，R.Agrawal等人首次提出了關聯規則的概念。其一般定義如下：J={ I1, I2, …, Im }是一項目集，D是一事務資料庫，其中每個事務T J。每個事務都有一個辨別符，稱之為TID。若A一是項目集，當且僅當A T時，我們說事務T包含了A。一條關聯規則就是形如A B的蘊含關系，其中A J，B J且A B= 。如果D中包含A B的比例是s，就稱關聯規則A B在D中的支援度為s，也可以表示為機率P（A B）；如果D中包含A的同時也包含B的比例是c ，則說關聯規則A B的置信度為c，表示為條件機率P（B|A）。就是： Support（A B）= P（A B） Confidence（A B）= P（B|A） 支援度（support）和置信度（confidence）兩個門檻值是描述關聯規則的兩個重要概念，支援度反映關聯規則在資料庫中的重要性，置信度衡量關聯規則的可信程度。如果某條規則同時滿足最小支援度（min-support）和最小置信度（min-confidence），則稱它為強關聯規則。 3.3 關聯規則種類 我們将關聯規則按不同的情況進行分類： (1) 基于規則中處理的變量的類别，關聯規則可以分為布爾型和數值型。布爾型關聯規則處理的值都是離散的、種類化的，它顯示了這些變量之間的關系；而數值型關聯規則可以和多元關聯或多層關聯規則結合起來，對數值型字段進行處理，将其進行動态的分割，或者直接對原始的資料進行處理，當然數值型關聯規則中也可以包含種類變量。例如：性别=“女”=>職業=“秘書” ，是布爾型關聯規則；性别=“女”=>avg（收入）=2300，涉及的收入是數值類型，是以是一個數值型關聯規則。 (2) 基于規則中資料的抽象層次，可以分為單層關聯規則和多層關聯規則。在單層的關聯規則中，所有的變量都沒有考慮到現實的資料是具有多個不同的層次的；而在多層的關聯規則中，對資料的多層性已經進行了充分的考慮。例如：IBM桌上型電腦=>Sony列印機，是一個細節資料上的單層關聯規則；桌上型電腦=>Sony列印機，是一個較高層次和細節層次之間的多層關聯規則。 (3) 基于規則中涉及到的資料的維數，關聯規則可以分為單維的和多元的。在單維的關聯規則中，我們隻涉及到資料的一個維，如使用者購買的物品；而在多元的關聯規則中，要處理的資料将會涉及多個維。換成另一句話，單維關聯規則是處理單個屬性中的一些關系；多元關聯規則是處理各個屬性之間的某些關系。例如：啤酒=>尿布，這條規則隻涉及到使用者的購買的物品；性别=“女”=>職業=“秘書”，這條規則就涉及到兩個字段的資訊，是兩個維上的一條關聯規則。 4 關聯規則挖掘的算法 (1) 經典頻集方法 Agrawal等于1993年首先提出了挖掘顧客交易資料庫中項集間的關聯規則問題，其核心方法是基于頻集理論的遞推方法。以後諸多的研究人員對關聯規則的挖掘問題進行了大量的研究。他們的工作包括對原有的算法進行優化，如引入随機采樣、并行的思想等，以提高算法挖掘規則的效率；提出各種變體，如泛化的關聯規則、周期關聯規則等，對關聯規則的應用進行推廣。 (2) 核心算法 Agrawal等在1993年設計了一個基本算法，提出了挖掘關聯規則的一個重要方法 — 這是一個基于兩階段頻集思想的方法，将關聯規則挖掘算法的設計可以分解為兩個子問題： (1)找到所有支援度大于最小支援度的項集（Itemset），這些項集稱為頻集（Frequent Itemset）。 (2)使用第1步找到的頻集産生期望的規則。這裡的第2步相對簡單一點。如給定了一個頻集Y=I1I2...Ik，k³2，Ij∈I，産生隻包含集合{I1，I2，...，Ik}中的項的所有規則(最多k條)，其中每一條規則的右部隻有一項，(即形如[Y-Ii]ÞIi，"1£i£k)，這裡采用的是中規則的定義。一旦這些規則被生成，那麼隻有那些大于使用者給定的最小可信度的規則才被留下來。為了生成所有頻集，使用了遞推的方法。其核心思想如下： (1) L1 = {large 1-itemsets}; (2) for (k=2; Lk-1¹F; k++) do begin (3) Ck=Apriori-gen(Lk-1); //新的候選集 (4) for all transactions tÎD do begin (5) Ct=subset(Ck,t); //事務t中包含的候選集 (6) for all candidates cÎ Ct do (7) c.count++; (8) end (9) Lk={cÎ Ck |c.count³minsup} (10) end (11) Answer=ÈkLk; 首先産生頻繁1-項集L1，然後是頻繁2-項集L2，直到有某個r值使得Lr為空，這時算法停止。這裡在第k次循環中，過程先産生候選k-項集的集合Ck，Ck中的每一個項集是對兩個隻有一個項不同的屬于Lk-1的頻集做一個(k-2)-連接配接來産生的。Ck中的項集是用來産生頻集的候選集，最後的頻集Lk必須是Ck的一個子集。Ck中的每個元素需在交易資料庫中進行驗證來決定其是否加入Lk，這裡的驗證過程是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的交易資料庫，即如果頻集最多包含10個項，那麼就需要掃描交易資料庫10遍，這需要很大的I/O負載。 在論文中，Agrawal等引入了修剪技術（Pruning）來減小候選集Ck的大小，由此可以顯著地改進生成所有頻集算法的性能。算法中引入的修剪政策基于這樣一個性質：一個項集是頻集當且僅當它的所有子集都是頻集。那麼，如果Ck中某個候選項集有一個(k-1)-子集不屬于Lk-1，則這個項集可以被修剪掉不再被考慮，這個修剪過程可以降低計算所有的候選集的支援度的代價。文[6]中，還引入雜湊樹（Hash Tree）方法來有效地計算每個項集的支援度。 3.4 主要研究方向和典型算法分析 R.Agrawal等人提出了關聯規則的采掘問題以後，該問題的研究得到了長足地發展。到目前為止，其主要的研究方向有： 3.4.1 多循環方式的采掘算法 此類算法包括Agrawal等人提出的AIS[28]，Apriori、AprioriTid和AprioriHybrid[29]、Park 等人提出的DHP[30]，Savasere等人的PARTITION[31]以及Toivonen提出的抽樣算法Sampling[32]等等。其中最有效和有影響的算法為：Apriori，DHP和PARTITION。 在算法AIS中，候選大項集是在掃描資料庫的過程中産生的。具體地說，在對資料庫進行第k 次掃描時，候選大項集(其中每一個元素的元素個數不一定是k個，可以大于k)是由第k-1次掃描所産生的邊界集(Frontierset)通過增加目前事務中的項得到，同時計算候選大項集中的元素的支援數，直到某一次掃描所産生的邊界集為空時停止運算。應該注意的是，第k次掃描所産生的邊界集要大于本次掃描生成的大項集。本算法的缺點在于生成的候選大項集太大。 算法Apriori和AprioriTid利用“在給定的事務資料庫D中，任意大項集的子集都是大項集； 任意弱項集的超集都是弱項集”這一原理對事務資料庫進行多遍掃描，第一次掃描得出大1項集L1，第k(k>1)次掃描前先利用第k-1次掃描的結果(即大k-1項集Lk-1)和函數Apriori_gen[29]産生候選大k項集Ck，然後在掃描過程中确定Ck中每一進制素的支援數，最後在每一遍掃 描結束時計算出大k項集Lk，算法在當候選大k項集Ck為空時結束。由于充分利用的上述原理 ，這兩個算法所産生的候選大項集要比算法AIS小得多，進而提高了算法的效率。算法AprioriTid還有另外一個特點，即僅在第一次掃描時用事務資料庫D計算候選大項集的支援數，其 它各次掃描用其上一次掃描生成的候選事務資料庫D'來計算候選大項集的支援數。在最後的 幾次掃描中，D'的大小要遠遠小于D，減小了I/O操作時間，提高了算法的效率。算法Aprio riHybrid是算法Apriori與算法AprioriTid的結合，當候選事務資料庫D'不能完全容納于内 存時用算法Apriori，當記憶體能夠完全容納候選事務資料庫D'時，則用算法AprioriTid。 算法DHP利用哈希(Hashing)技術有效地改進了候選大項集的生成過程，産生了比前述算法更小的候選大項集(對大2候選集尤為明顯)，同時也縮減了事務資料庫的大小，減小了I/O操作時間，其效率比算法Apriori有明顯提高。 算法PARTION分為兩個部分。在第一部分中，算法首先将要在其中發現關聯規則的事務資料 庫D分為n個互不相交的事務資料庫D1，D2，...，Dn，Di(i=1,2,...,n)的大小要求 能夠容納在記憶體之中，然後将每一個分事務資料庫Di(i=1,2,...,n)讀入記憶體并發現其 中的大項集Li，最後在第一部分結束時将所有分事務資料庫的大項集合并成為一個在事務數 據庫D中的潛在大項集 算法第二部分計算潛在大項集PL在事務資料庫D中的支援數，并得出大項集L。該算法隻對事務資料庫D掃描兩次，大大減少了I/O操作，進而提高了算法的效率。 算法Sampling設計思想為：對事務資料庫D進行随機抽樣得到抽樣事務資料庫D'，先以小于 使用者給定的最小支援度的支援度發現存在于D'中大項集L'，再在剩下的資料庫D-D'中繼續計 算L'中各元素的支援數，最後以使用者給定的最小支援度計算出大項集L。在大部分情況下，可以用此方法發現正确的大項集，但有時可能會漏掉一些大項集，這時可以對D進行第二次 掃描以得出漏掉的大項集。此算法在大部分情況下可以隻對D進行一次掃描就得出大項集， 最壞的情況對D進行兩次掃描，因而算法效率較高。 3.4.2 增量式更新算法 關聯規則的增量式更新問題主要有兩個：①在給定的最小支援度和最小置信度下，當一個新 的事物資料集db添加到舊的事物資料庫DB中時，如何生成db(DB中的關聯規則；②給定事物 資料庫DB，在最小支援度和最小可信度發生變化時，如何生成資料庫DB中的關聯規則。文[33]考慮了關聯規則更新的第一類問題，給出了一個基本架構與算法Apriori相一緻的算法FUP。文[34]針對關聯規則更新的第二類問題進行了研究，設計出了相應的算法IUA和PIUA。 算法FUP的基本思想為：對任意一個k(k 1)項集，若其在DB和db中都是大項集，則其一定是 大項集；若其在DB和db中都是弱項集，則其一定是弱項集；若其僅在DB(db)中是大項集，則 其支援數應加上其在db(DB)中的支援數以确定它是否為大項集。算法FUP假設在DB中發現的 大項集 (n為L中最大元素的元素個數)已被儲存下來。它需要對DB和db進行多次掃描，在第 1次掃描中，算法先掃描db，将L1中的元素仍為db(DB中的大項集的元素記入L'1，并生成候 選大1項集C1，C1中的元素為db中的大1項集且不包含在L1中；然後掃描DB以決定C1中的元素 是否為db(DB中的大項集，并将是db(DB中的大項集的元素記入L'1中。在第k(k>1)次掃描前 ，先對L'k-1用Apriori_Gen()函數生成候選大k項集Ck，并除去Lk中的元素，即Ck=Ck-Lk， 對Lk進行剪枝，即對于X∈Lk，若存在Y∈Lk-1-L'k-1，則X肯定不會是db∪DB中的大k項集，應将其在Lk中删除；然後掃描db，将Lk中的元素仍為db∪DB中的大項集的元素記入L'k，記錄候選大k項集Ck中的元素在db中的支援數；最後掃描DB，記錄Ck中的元素在DB中的支援數，掃描結束時，将Ck中是db∪DB中大項集 的元素記入L'k中。算法在Lk和Ck均為空時結束。由于利用了對DB進行采掘的結果，本算法的效率比再一次利用算法Apriori或DHP對db∪DB進行采掘的效率要高得多。 　　算法IUA采用了一個獨特的候選大項集生成算法iua_gen，在每一次對資料庫DB掃描之前生成 較小的候選大項集，進而提高了算法的效率。它也要求上一次對資料庫DB進行采掘時發現的 大項集 (n為L中最大元素的元素個數)在本次采掘時是可得到的。因為人們在發現關聯規則時，常常需要不斷地調整最小支援度和最小可信度來聚集到那些真正令其感興趣關聯規則上 ，因而本算法具有很重要的意義。 3.4.3 并行發現算法 目前已經提出的并行采掘關聯規則的算法有：Agrawal等人提出的CD(Count Distribution) 、CaD(Candidate Distribution)、DD(Data Distribution)[35]，Park等人提出的PDM[36]。Chueng等人提出的算法DMA[37]和FDM[38]雖然是基于分布式資料庫的采掘算法，但也可 适用于并行采掘。 算法CD具有速度較快、容易實作、要求各計算機間同步次數較少等優點，但它有通信量大和 候選大項集大等缺點。算法CaD、DD及PDM的執行效果都不如CD[37]。算法DMA雖克服了算法C D的一些弱點，但它要求各計算機間同步次數較多。算法FDM與算法DMA基本一緻，差別在于F DM中增加了全局剪枝技術。 這些算法都是基于無共享體系結構，即并行計算的n台計算機之間除了用網絡連接配接起來以外 ，其它都是完全獨立的。每台計算機Pi(i=1,2,...,n)上都有自己的分事務資料庫DBi，總的事務資料庫 。 算法CD是算法Apriori在并行環境下的應用，它要求計算機Pi(i=1,2,...,n)對DBi進行多遍掃描。在第k次掃描，當k>1時，計算機Pi(i=1,2,...,n)首先利用第k-1次掃描所得 的大項集Lk-1和Apriori_Gen()函數生成候選大項集Ck，當k=1時，計算機Pi先掃描DBi得出 其中的大1項集，再與其它計算機得到的大1項集進行交換并進行合并，進而生成候選大1項 集C1；然後掃描DBi計算Ck中的元素在DBi中的支援數，計算機Pi廣播Ck中元素的支援數，并 接收從其它計算機 傳來的Ck中元素的支援數，并對這些支援數進行累加，得出Ck中 元素的全局支援數；最後計算出大k項集Lk，若Lk中元素個數為1，則算法結束。 算法DMA是基于“若項集X在DB中是大項集，則其必在某一個DBi也是大項集”的原理進行設計。算法中采用局部剪枝技術(Local pruning)，使其生成的候選大項集比算法CD要小。算法各個站點進行支援數交換時采用輪詢站點技術(polling site)，使每一個項集X的通訊代 價由算法CD的o(n2)降為o(n)，其中n為站點個數。它可分為如下幾步：①生成候選大k項集CHiK。根據計算機Pi(i=1，2，...，n)在k-1次循環所生成的稠密集HLiK-1，生成循環k所需用的候選大k項集CHiK，即 ②支援數計算。掃描DBi計算候選大k項集中的每個元素X的局部支援數X.supi。③交換支援數。采用輪詢站點技術與其它計算機交換候選大k項集中的 元素的支援數，并計算它的全局支援數。④生成大項集Lk和稠密集。中的元素具有下列性質：它在DBi和DB中都是大項集。 (4)采掘一般或多層關聯規則 在研究采掘關聯規則的過程中，許多學者發現在一些實際應用中，由于資料比較少，要想在 原始的概念層次上發現強的(Strong)和有趣的(Interesting)關聯規則是比較困難的，因為 好多項集往往沒有足夠的支援數。由于概念層次在要采掘的資料庫中經常是存在的，比如在 一個連鎖店會存在這樣概念層次：光明牌牛奶是牛奶，牛奶是食品等，我們稱高層次的項是 低層次項的父親，這種概念層次關系通常用一個有向非循環圖(DAG)來表示。于是我們就可 以在較高的概念層次上發現關聯規則。基于要采掘的資料庫中的概念層次和發現單一概念層 次中的關聯規則的算法，學者們提出了許多高效發現一般或多層關聯規則的算法，主要有： Han等人的ML_T2L1及其變種ML_T1LA、ML_TML1、ML_T2LA[39]和R.Srikant等人的Cumulate、 Stratify及其變種Estimate、EstMerge[40]等。 算法ML_T2L1的基本思想是首先根據要發現的任務從原事務資料庫生成一個根據概念層次信 息進行編碼的事務資料庫，利用這個具有概念層次資訊的新生成的資料庫，自頂向下逐層遞 進地在不同層次發現相應的關聯規則。它實際上是算法Apriori在多概念層次環境中的擴充 。根據對在發現高層關聯規則過程中所用的資料結構和所生成的中間結果共享方式的不同， 算法ML_T2L1有三個變種：ML_T1LA、ML_TML1、ML_T2LA。 算法Cumulate的基本思想與Apriori完全一樣，隻是在掃描到事務資料庫某一事務時，将此 事務中所有項的祖先加入到本事務中，并加入三個優化：①對加入到事務中的祖先進行過濾 。②預先計算概念關系T中的每一個項的祖先，得到項集與其祖先的對照表T*。③對既包含 項集X又包含X的祖先的項集進行剪枝。 算法Stratify基于“若項集X的父親不是大項集，則X肯定不會是大項集”的事實進行設計。其基本思想為：在概念層次有向非循環圖中，定義沒有父親的項集X的深度depth(X)=0，其 它項集的深度為： 算法要對事務資料庫進行多遍掃描，第k k(0)次掃描計算深度為k k(0)的所有項集Ck的支援數，并得出深度為k k(0)的大項集Lk，在第k k(1)次掃描之前，對Ck進行剪枝，即删除Ck中那些祖先包含在Ck-1-Lk-1中的元素。圍繞着怎樣及早決定某些深度較大的項集是否是大項集問題，文獻[40]用抽樣技術對算 法Stratify進行擴充，形成算法Estimate和EstMerge。 (5)采掘多值屬性關聯規則 關聯規則可分為布爾型關聯規則和多值屬性關聯規則。多值屬性又可分為數量屬性和類别屬 性。多值屬性關聯規則采掘問題首先在文獻[41]中提出。目前提出的采掘多值屬性關聯規則的算法大多是将多值屬性關聯規則采掘問題轉化為布爾型關聯規則采掘問題，即将多值屬性 的值劃分為多個區間，每個區間算作一個屬性，将類别屬性的每一個類别當作一個屬性。 文[41]中發現的多值屬性關聯規則的形式為：x=qx y=qy，其前件和後件對應的都是單一的 數值，而不是一個區間，文中提出的算法比較簡單，但當我們需要發現所有屬性之間的關聯 規則時，我們将遇到屬性組合的爆炸問題。 文[42]用“偏完整性度量（partial completenessmeasure）”原則将數量屬性劃分為相等的幾個區段，當某一區段的支援數小于使用者給定的最小支援數時，我們就将其與其鄰近的區段 進行合并。為了使發現的關聯規則更具有趣性，文中采用了“大于期望的值（greater-than- expected-value）”準則。 文[43]認為文[42]中的屬性劃分方法不能很好地表示資料的分布，尤其是屬性值分布不均勻 的時候，于是提出了一個聚類算法，根據資料庫中資料的分布情況決定屬性值如何劃分區段 ，并可将相關的區段進行合并。在此基礎上發現的多值關聯規則更具有效性和可了解性。 (6)基于限制的關聯規則采掘 基于限制的關聯規則采掘的主要目的是發現更有趣的、更實用的和更特别的關聯規則，這方 面的研究主要有[44～51]。 文[44]研究了在提供布爾表達式限制情況下的關聯規則發現問題。這種布爾表達式限制允許 使用者指定他所感興趣的關聯規則的集合，這種限制不僅可以用來對事務資料庫進行預加工， 而且可以把它內建在采掘算法内部，進而提高算法的執行效率，文中根據這種內建方式的不 同給出了三種不同的算法：MultipleJoins、Reorder、Direct。 文[45]提出并分析了使用者所給出的限制的兩個對發現算法的剪枝步驟非常重要的屬性：反單 調性(anti-monotonicity)和簡潔性(succinctness)，提出了一個高效的基于限制的關聯規 則采掘算法CAP。 另一種類型的基于限制的關聯規則采掘方法是元模式制導的關聯規則采掘算法[49～51]。這 種類型的發現算法首先由使用者給定要發現的關聯規則的元模式或模闆，然後根據這些模闆在 資料庫中發現與模闆相适應的實際存在的關聯規則。例如文[50]就是基于這種模式提出了兩 個相應的算法：大謂詞增長算法(largepredicate-growing)和直接p-謂詞測試算法(Direct p-predicatetesting)。 (7)其它方向 　　除了以上列舉的比較常見的研究方向外，還有其它一些研究方向，如：發現關聯規則的語言 [52,53]、采掘長模式和密集資料集[48,54]、采掘相關性和因果關系[55,56]、發現比例 規則[57]、發現周期(cyclic)和月曆(calendric)關聯規則[58,59]、采掘多元關聯規則[59] 等等[60]。 3.5 頻集算法的幾種優化方法 雖然Apriori算法自身已經進行了一定的優化，但是在實際的應用中，還是存在不令人滿意的地方，于是人們相繼提出了一些優化的方法。 3.4.1 基于劃分的方法 Savasere等[14]設計了一個基于劃分(partition)的算法，這個算法先把資料庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻集，然後把産生的頻集合并，用來生成所有可能的頻集，最後計算這些項集的支援度。這裡分塊的大小選擇要使得每個分塊可以被放入主存，每個階段隻需被掃描一次。而算法的正确性是由每一個可能的頻集至少在某一個分塊中是頻集保證的。上面所讨論的算法是可以高度并行的，可以把每一分塊分别配置設定給某一個處理器生成頻集。産生頻集的每一個循環結束後，處理器之間進行通信來産生全局的候選k-項集。通常這裡的通信過程是算法執行時間的主要瓶頸；而另一方面，每個獨立的處理器生成頻集的時間也是一個瓶頸。其他的方法還有在多處理器之間共享一個雜湊樹來産生頻集。更多的關于生成頻集的并行化方法可以在中找到。 3.4.2 基于Hash的方法 一個高效地産生頻集的基于雜湊(hash)的算法由Park等提出來。通過實驗我們可以發現尋找頻集主要的計算是在生成頻繁2-項集Lk上，Park等就是利用了這個性質引入雜湊技術來改進産生頻繁2-項集的方法。 3.4.3 基于采樣的方法 基于前一遍掃描得到的資訊，對此仔細地作組合分析，可以得到一個改進的算法，Mannila等先考慮了這一點，他們認為采樣是發現規則的一個有效途徑。随後又由Toivonen進一步發展了這個思想，先使用從資料庫中抽取出來的采樣得到一些在整個資料庫中可能成立的規則，然後對資料庫的剩餘部分驗證這個結果。Toivonen的算法相當簡單并顯著地減少了I/O代價，但是一個很大的缺點就是産生的結果不精确，即存在所謂的資料扭曲(data skew)。分布在同一頁面上的資料時常是高度相關的，可能不能表示整個資料庫中模式的分布，由此而導緻的是采樣5%的交易資料所花費的代價可能同掃描一遍資料庫相近。Lin和Dunham在中讨論了反扭曲(Anti-skew)算法來挖掘關聯規則，在那裡他們引入的技術使得掃描資料庫的次數少于2次，算法使用了一個采樣處理來收集有關資料的次數來減少掃描遍數。Brin等提出的算法使用比傳統算法少的掃描遍數來發現頻集，同時比基于采樣的方法使用更少的候選集，這些改進了算法在低層的效率。具體的考慮是，在計算k-項集時，一旦我們認為某個(k+1)-項集可能是頻集時，就并行地計算這個(k+1)-項集的支援度，算法需要的總的掃描次數通常少于最大的頻集的項數。這裡他們也使用了雜湊技術，并提出産生“相關規則”（Correlation Rules）的一個新方法，這是基于他們的工作基礎上的。 3.4.4 減少交易的個數 減少用于未來掃描的事務集的大小。一個基本的原理就是當一個事務不包含長度為k的大項集，則必然不包含長度為k+1的大項集。進而我們就可以将這些事務移去，這樣在下一遍的掃描中就可以要進行掃描的事務集的個數。這個就是AprioriTid的基本思想 3.4.5 其他的頻集挖掘方法 上面我們介紹的都是基于Apriori的頻集方法。即使進行了優化，但是Apriori方法一些固有的缺陷還是無法克服： (1)可能産生大量的候選集。當長度為1的頻集有10000個的時候，長度為2的候選集個數将會超過10M。還有就是如果要生成一個很長的規則的時候，要産生的中間元素也是巨大量的。 (2)無法對稀有資訊進行分析。由于頻集使用了參數minsup，是以就無法對小于minsup的事件進行分析；而如果将minsup設成一個很低的值，那麼算法的效率就成了一個很難處理的問題。 下面将介紹兩種方法，分别用于解決以上兩個問題。 在[18]中提到了解決問題1的一種方法。采用了一種FP-growth的方法。他們采用了分而治之的政策：在經過了第一次的掃描之後，把資料庫中的頻集壓縮進一棵頻繁模式樹（FP-tree），同時依然保留其中的關聯資訊。随後我們再将FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關。然後再對這些條件庫分别進行挖掘。當原始資料量很大的時候，也可以結合劃分的方法,使得一個FP-tree可以放入主存中。實驗表明，FP-growth對不同長度的規則都有很好的适應性，同時在效率上較之Apriori算法有巨大的提高。 第二個問題是基于這個的一個想法：Apriori算法得出的關系都是頻繁出現的，但是在實際的應用中，我們可能需要尋找一些高度相關的元素，即使這些元素不是頻繁出現的。在Apriori算法中，起決定作用的是支援度，而我們現在将把可信度放在第一位，挖掘一些具有非常高可信度的規則。在[19]中介紹了對于這個問題的一個解決方法。整個算法基本上分成三個步驟：計算特征、生成候選集、過濾候選集。在三個步驟中，關鍵的地方就是在計算特征時Hash方法的使用。在考慮方法的時候，有幾個衡量好壞的指數：時空效率、錯誤率和遺漏率。基本的方法有兩類：Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：将一條記錄中的頭k個為1的字段的位置作為一個Hash函數。Locality_Sentitive_Hashing的基本想法是：将整個資料庫用一種基于機率的方法進行分類，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。我們再對這兩個方法比較一下。MH的遺漏率為零，錯誤率可以由k嚴格控制，但是時空效率相對的較差。LSH的遺漏率和錯誤率是無法同時降低的，但是它的時空效率卻相對的好很多。是以應該視具體的情況而定。最後的實驗資料也說明這種方法的确能産生一些有用的規則。 3.4.6 提高效率的幾種方法說明 影響算法效率的因素主要有事務資料庫的規模，掃描事務資料庫的次數。所生成候選規則的數量．是以提高算法效率的各種算法都是從這三個方面考慮，另外可以使用一些能夠并發執行的算法． 1 減少事務資料庫規模的方法首先是減少事務資料庫的規模，這裡有兩種情況：第一，直接對事務資料庫的規模消減；第二，在挖掘過程中對資料庫的規模進行消減．直接對事務資料庫的規模進行消減的算法首先是抽樣算法。這在對算法的效率要求高的情況下經常使用，對資料庫規模的消減必然造成所挖掘規則品質的損失，但是結果是效率的顯著提高．為了減少這種損失，我們可以降低rain—sup的取值，這樣得到的高頻項集會多一些，進而在整個資料庫中進行驗證，如果不合适，可以進行第二遍的掃描．總之。對資料庫的掃描時間要少許多．另一種方法對資料庫中某些項進行抽象，提高概念層次，例如不同品牌的商品在不關注其品牌的時候，那麼可以認為不同品牌的東西是相同的，這樣就可以減少項集的規模，對資料庫進行處理，同樣可以減少資料庫的規模．在挖掘過程中對資料庫規模進行消減，對生成的候選項集進行驗證的時候，把無用或不相關的事務删掉，這樣可以提高掃描的速度．删除可以依據前面給出的定理1～3．在判斷志一候選項集的時候，如果事務的規模小于k，或者事務不包含任何(志一1)一高頻項集，則該事務可以從資料庫中删除．不會影響挖掘的結果，而減少了資料庫的掃描，進而提高了算法的效率．另外在掃描資料庫判斷某個候選高頻項集x 是否為高頻項集的時候，如果根據掃描過的事務已經可以判斷X，那麼對X 的處理就可以完成，這樣也可以減少資料庫掃描時間，進而提高效率． 2 減少掃描次數的方法 第一種方法：首先掃描一遍資料庫，找出所有的1一高頻項集，在每個高頻項集中記錄包含該高頻項集的事務的Tid，然後根據Tid計算所有的k一高頻項集，k>1．關聯規則挖掘算法Apriori的一種改進算法AprioriTid就使用了這種思想，隻需要對資料庫進行一次掃描． 第二種方法：把資料庫劃分成”個互不相交的部分，求出每一部分的高頻項集，再掃描一次資料庫得到高頻項集，可以減少對資料庫的掃描次數． 上面兩種方法的結合可以産生另外一種方法，隻需要對資料庫進行兩次掃描就可以找到高頻項集．分兩個階段：首先，算法把資料庫分成n個互不相交的部分．根據rain—sup，找出局部項集支援數，可以找出局部高頻項集．這個過程使用一種特殊的資料結構，每個項集記錄包含該項集的事務記錄的Tid．隻需要掃描一次資料庫就可以找到所有的局部高頻走一項集，k=1，2，⋯．局部高頻項集可能是也可能不是全局高頻項集，全局高頻項集最少會出現在某一個局部高頻項集中，是以得到的所有局部高頻項集就是候選全局高頻項集，進行第二次 資料庫掃描就可以得到所有高頻項集． 3 還有一種動态項集計數方法：把資料庫分成很 多塊，每一塊都有一個起始點，可以在任何起點加 人新的候選項集，與劃分資料找候選項集的方法有 些相似． 3.6 多層和多元關聯規則的挖掘 随着資料倉庫和OLAP技術研究的深入，可以預見大量的資料将經過整合、預處理，進而存入資料倉庫之中。在目前，大多數的資料倉庫的應用都是進行統計、建立多元以及OLAP的分析工作。随着資料挖掘研究的深入，已經有了OLAP和資料挖掘相結合的方法[20,21]。 首先一個有效的資料挖掘方法應該可以進行探索性的資料分析。使用者往往希望能在資料庫中穿行，選擇各種相關的資料，在不同的細節層次上進行分析，以各種不同的形式呈現知識。基于OLAP的挖掘就可以提供在不同資料集、不同的細節上的挖掘，可以進行切片、切塊、展開、過濾等各種對規則的操作。然後再加上一些可視化的工具，就能大大的提高資料挖掘的靈活性和能力。接着，我們來看一下多層和多元關聯規則的定義。 多層關聯規則：對于很多的應用來說，由于資料分布的分散性，是以很難在資料最細節的層次上發現一些強關聯規則。當我們引入概念層次後，就可以在較高的層次上進行挖掘。雖然較高層次上得出的規則可能是更普通的資訊，但是對于一個使用者來說是普通的資訊，對于另一個使用者卻未必如此。是以資料挖掘應該提供這樣一種在多個層次上進行挖掘的功能。 多層關聯規則的分類：根據規則中涉及到的層次，多層關聯規則可以分為同層關聯規則和層間關聯規則。 多層關聯規則的挖掘基本上可以沿用“支援度-可信度”的架構。不過，在支援度設定的問題上有一些要考慮的東西。 同層關聯規則可以采用兩種支援度政策： (1)統一的最小支援度。對于不同的層次，都使用同一個最小支援度。這樣對于使用者和算法實作來說都比較的容易，但是弊端也是顯然的。 (2)遞減的最小支援度。每個層次都有不同的最小支援度，較低層次的最小支援度相對較小。同時還可以利用上層挖掘得到的資訊進行一些過濾的工作。層間關聯規則考慮最小支援度的時候，應該根據較低層次的最小支援度來定。 以上我們研究的基本上都是同一個字段的值之間的關系，比如使用者購買的物品。用多元資料庫的語言就是單維或者叫維内的關聯規則，這些規則一般都是在交易資料庫中挖掘的。但是對于多元資料庫而言，還有一類多元的關聯規則。例如：年齡（X，“20...30”）Ù職業（X,“學生”） 購買(X，“筆記本電腦”)在這裡我們就涉及到三個維上的資料：年齡、職業、購買。根據是否允許同一個維重複出現，可以又細分為維間的關聯規則（不允許維重複出現）和混合維關聯規則（允許維在規則的左右同時出現）。年齡（X，“20...30”）Ù購買(X，“筆記本電腦”) 購買(X，“列印機”)這個規則就是混合維關聯規則。 在挖掘維間關聯規則和混合維關聯規則的時候，還要考慮不同的字段種類：種類型和數值型。對于種類型的字段，原先的算法都可以處理。而對于數值型的字段，需要進行一定的處理之後才可以進行。處理數值型字段的方法基本上有以下幾種： (1)數值字段被分成一些預定義的層次結構。這些區間都是由使用者預先定義的。得出的規則也叫做靜态數量關聯規則。 (2)數值字段根據資料的分布分成了一些布爾字段。每個布爾字段都表示一個數值字段的區間，落在其中則為1，反之為0。這種分法是動态的。得出的規則叫布爾數量關聯規則。 (3)數值字段被分成一些能展現它含義的區間。它考慮了資料之間的距離的因素。得出的規則叫基于距離的關聯規則。 (4)直接用數值字段中的原始資料進行分析。使用一些統計的方法對數值字段的值進行分析，并且結合多層關聯規則的概念，在多個層次之間進行比較進而得出一些有用的規則。得出的規則叫多層數量關聯規則。 在OLAP中挖掘多層、多元的關聯規則是一個很自然的過程。因為OLAP本身的基礎就是一個多層多元分析的工具，隻是在沒有使用資料挖掘技術之前，OLAP隻能做一些簡單的統計，而不能發現其中一些深層次的有關系的規則。當我們将OLAP和DataMining技術結合在一起就形成了一個新的體系OLAM（On-Line Analytical Mining）[20]。 3.7 關聯規則價值衡量的方法 當我們用資料挖掘的算法得出了一些結果之後，資料挖掘系統如何知道哪些規則對于使用者來說是有用的、有價值的？這裡有兩個層面：使用者主觀的層面和系統客觀的層面。 3.6.1 系統客觀層面 很多的算法都使用“支援度-可信度”的架構。這樣的結構有時會産生一些錯誤的結果。看如下的一個例子：假設一個提供早餐的零售商調查了4000名學生在早晨進行什麼運動，得到的結果是2200名學生打籃球，2750名學生晨跑，1800名學生打籃球、晨跑。那麼如果設minsup為40%，minconf為60%，我們可以得到如下的關聯規則：打籃球Þ晨跑（1）這條規則其實是錯誤的，因為晨跑的學生的比例是68%，甚至大于60%。然而打籃球和晨跑可能是否定關聯的，即當我們考慮如下的關聯時：打籃球Þ（不）晨跑 （2）雖然這條規則的支援度和可信度都比那條蘊涵正向關聯的規則（1）低，但是它更精确。 然而，如果我們把支援度和可信度設得足夠低，那麼我們将得到兩條沖突的規則。但另一方面，如果我們把那些參數設得足夠高，我們隻能得到不精确的規則。總之，沒有一對支援度和可信度的組合可以産生完全正确的關聯。 于是人們引入了興趣度，用來修剪無趣的規則，即避免生成“錯覺”的關聯規則。一般一條規則的興趣度是在基于統計獨立性假設下真正的強度與期望的強度之比，然而在許多應用中已發現，隻要人們仍把支援度作為最初的項集産生的主要決定因素，那麼要麼把支援度設得足夠低以使得不丢失任何有意義的規則，或者冒丢失一些重要規則的風險；對前一種情形計算效率是個問題，而後一種情形則有可能丢失從使用者觀點來看是有意義的規則的問題。 在[12]中作者給出了感興趣的規則的定義（R-interesting），在[13]中他們又對此作了改進。在[10]中把事件依賴性的統計定義擴充到興趣度的定義上來；[15]定義了否定關聯規則的興趣度。 除了把興趣度作為修剪無價值規則的工具，現在已有許多其他的工作來重新認識項集，如Brin等[3]考慮的相關規則。在[4]中讨論了蘊涵規則(implication rule)，規則的蘊涵強度在[0,¥]之間變化，其中蘊涵強度為1表示完全無關的規則，¥表示完備的規則，如果蘊涵強度大于1則表示更大的期望存在性。 另一個路徑成本——“收集強度”(collective strength)在[22]中被定義，他們設想使用“大于期望值”來發現有意義的關聯規則。項集的“收集強度”是[0,¥]之間的一個數值，其中0表示完備的否定相關性，而值¥表示完備的正相關性。詳細的讨論可以在[10]中找到。 3.6.2 使用者主觀層面 上面的讨論隻是基于系統方面的考慮，但是一個規則的有用與否最終取決于使用者的感覺。隻有使用者可以決定規則的有效性、可行性。是以我們應該将使用者的需求和系統更加緊密的結合起來。 可以采用一種基于限制(consraint-based)[21]的挖掘。具體限制的内容可以有： (1)資料限制。使用者可以指定對哪些資料進行挖掘，而不一定是全部的資料。 (2)指定挖掘的維和層次。使用者可以指定對資料哪些維以及這些維上的哪些層次進行挖掘。 (3)規則限制。可以指定哪些類型的規則是我們所需要的。引入一個模闆（template）的概念，使用者使用它來确定哪些規則是令人感興趣的而哪些則不然：如果一條規則比對一個包含的模闆（inclusive template），則是令人感興趣的，然而如果一條規則比對一個限制的模闆（rextrictive template），則被認為是缺乏興趣的。 其中有些條件可以和算法緊密的結合，進而即提高了效率，又使挖掘的目的更加的明确化了。其他的方法還有：Kleinberg等人的工作是希望建立一套理論來判斷所得模式的價值，他們認為這個問題僅能在微觀經濟學架構裡被解決，他們的模型提出了一個可以發展的方向。他們引入并研究了一個新的優化問題——分段(Segmentation)問題，這個架構包含了一些标準的組合分類問題。這個模型根據基本的目标函數，對“被挖掘的資料”的價值提供一個特殊的算法的視角，顯示了從這方面導出的具體的優化問題的廣泛的應用領域。 在[5]中Korn等就利用猜測誤差(這裡他們使用“均方根”來定義)來作為一些從給定的資料集所發現的規則的“好處”(goodness)的度量，他們所定義的比例規則就是如下的規則：顧客大多數分别花費 1 : 2 : 5的錢在“面包”:“牛奶”:“奶油”上通過确定未知的(等價的，被隐藏的，丢失的)值，比例規則可以用來作決策支援。如果資料點線性地相關的話，那麼比例規則能達到更緊湊的描述，即關聯規則更好地描述了相關性。 3.8 選擇規則的方法 規則的選取主要根據規則的重要性，可從主觀和客觀兩個方面來進行度量，進而産生不同的選擇方法．主觀方法又可分為定性方法和定量方法． 第一種方法：通過規則的可視化Ll ]．屬于主觀定性方法，也是研究較多的方法．挖掘過程是自動進行的，挖掘結束應該把對結果進行處理，根據需要選擇感興趣的規則，删除不感興趣的規則，進而達到選擇感興趣規則的目的．但是這種方法在挖掘過程中生成很多使用者所不感興趣的規則，對算法的效率有一定的影響．同時如果生成規則的數量過大，通過人工的方法不能夠選擇的話，使用者可以把自己對于規則的一些經驗知識輸人給系統，系統根據使用者的需求進行規則的選擇，最後把結果顯示給使用者． 第二種方法：通過規則模闆可以選擇感興趣的規則．也是一種主觀定性的方法．使用者可以使用背景知識來指定所要挖掘的規則形式和不希望得到的規則形式．模闆可以分為兩類：含概模闆與限定模闆，前者用來描述使用者所希望得到的規則形式，後者用來描述不希望得到的規則形式．使用規則模闆可以減少挖掘過程中産生規則的數量，同時由于在挖掘過程中生成的規則數量少，減少了挖掘時間，提高了挖掘效率，也可以認為是一種提高效率的方法． 第三種方法：根據對規則的關注程度來選擇，把規則的重要性進行量化．對規則的重要性的量化描述可以有主觀和客觀兩種．一般文獻中對于客觀關注程度的描述較多，而對于規則重要性的主觀量化描述較少．在文獻[2]中，作者給出了一種度量主觀關注程度的方法，應用在挖掘中取得了好的效果．在挖掘過程中使用主觀關注程度來減少無用規則的選擇，僅僅使用客觀關注程度有時候不能反映規則的重要程度，因為屬性之間的重要性不會完全一樣，對于不同的挖掘任務，各種屬性的作用不會相同，需要使用者指定屬性的重要程度，在挖 掘的過程中可以減少生成的規則的數量，同時提高算法的效率． 第四種方法：利用對規則的客觀關注程度．目前對規則的關注程度的研究主要是對規則的客觀關注程度的研究．對于規則A B，主要使用支援度和置信度來描述，Agrawal提出了置信度P(B／A)、Piatesket—Shapiro提出了事件獨立性P(A，B)／P(A)P(B)、Symth提出了J—Measure函數等．Toivonen提出了根據規則的後件，對挖掘出的關聯規則集合進行分組，選取分組的覆寫集合(cover rules)作為所關注的規則． 第五種方法：通過設定足夠大的支援度和置信度，例如R—interesting方法，可以避免大量規則集．但是由于選擇過大的支援度和置信度，可能會造成重要資訊的丢失．Hoschka和Klosgen通過屬性及屬性集部分排序來避免産生幾種類型的備援知識，如層次項目造成的備援．第六種方法，通過計算規則之間的相關性消除備援規則，例如生成規則{Milk} {Bread，Butter}和{Milk}(Bread)，後者就是備援規則，因為前者已經包含了後者．可以通過考察規則之間的關系，對規則進行選擇，消除備援規則．還可以通過設定生成的規則的數量來直接限制生成的規則，進而實作間接選擇規則．可以利用以往的挖掘結果作為目前挖掘的先驗知識确定客觀關注程度，進而達到選擇規則的目的[21]。 3.9 小結 本章主要介紹關聯規則的内容及基本概念和基本算法，還有評價關聯規則的方法。由于關于關聯規則研究方向的文章比較多，已經沒有太多的可以研究的空間。要取得突破，就必須有新的發現，最近負關聯被提出來，而關于此研究的文章則不是太多，有一定的空間。 第四章 正負關聯規則研究 4.1 概述 很多的算法都使用“支援度-可信度”的架構。這樣的結構有時會産生一些錯誤的結果。看如下表的一個例子。支援度與可信度的： ％ 買咖啡 不買咖啡 合計 買牛奶 20 5 25 不買牛奶 70 5 75 合計 90 l0 l00 由表可以了解到，如果設定最小支援度和最小可信度分别為0．2和0、6，按照Agrawal的定義得到關聯規則“買牛奶= 買咖啡(s=0.2，c=0.8)” ，即80％的人買了牛奶就會買咖啡。但同時也可以得到“90％的人肯定會買咖啡”。換句話說，買牛奶這個事件對于買咖啡這個事件的刺激作用(80％)并沒有想象中的(90％)那麼大。反而是規則“買咖啡->不買牛奶(s=0.7，c=0.78)” 更具有實際的指導意義。 4.2 研究現狀 (1)基于Apriori架構的算法往往效率不夠高，但伸縮性好。基于FP-growth架構的算法效率高，伸縮性卻不好。如何能結合這兩者的長處是一個吸引人而又極富挑戰性的問題。 (2)資料挖掘既然是處理海量的資料，些許的誤差應該是可以接受的。能不能找到能允許在一定的誤差範圍内但大大加速挖掘的算法是一個已經有人在研究但還遠未完善的方向。 (3)關聯規則所挖掘的資料經常包含着使用者隐密的資訊。怎樣在挖掘過程中保護使用者的隐私進而讓使用者更願提供真實資料是極有價值的研究問題。 (4)基于最大頻繁項日集的關聯規則挖掘算法和基于精簡集的挖掘算法能否結合，使兩者的長處同時發揮作用，這是我正在繼續研究的問題。 (5)更好的關聯規則的興趣度量标準是一個老問題，但遠未解決，值得探讨。 (6)如何對事務資料庫建立某種索引來加速挖掘應該是一種可行而又高效的力法，是一個重要的研究方向。 (7)如何建立對資料集的特征描述的名額，進而有針對性地對不同特征的資料集選用不同的算法是一個很好而又很難的問題。 4.3 關聯規則具體研究 4.3.1 關聯規則挖掘的矩陣算法 本算法通過建構新的矩陣結構來改進算法，對在其中出現的标為1，未出現的标為0，同時添加行和、列和。通過此減少了對資料庫的少描次數。同時通過行和減少對高頻集的較快挖掘發現，提高了效率。假設有如下的交易資料，具體應用如下： 則具體過程如下： 時間複雜度的定性分析：矩陣算法跨越了由低次到高次逐漸杏找頻繁子集的限制，在不知道低次k一1頻繁項的前提下同樣可以直接計算k項集，而且k越大，搜尋的記錄範圍越小，岡此效率越高，相反，低次頻繁子集的查找速度相對高次而言相對較慢。是以矩陣算法相對而言适合k較大時的情況。 空間複雜度的定性分析：由于存儲的是0和I這種布爾資料(以位方式存儲即可)，因而在樣本記錄集較大時通常會占用更少的空間[13]。 4.3.2 基于相關系數的正、負關聯規則 相關系數是兩個随機變量間線性相關程度的一個度量。設 X，Y為兩個變量，相關系數定義為： 其中，cov(X ，Y)為變量 X，Y的協方差，√D(X)√D(Y)為變量X ，Y的标準差。|ρx.y|≤1，如果ρx.y =O，則變量 X，Y不相關；如果ρx.y =+1，則變量 X，Y充分正相關；同樣如果ρx.y =一1，則變量X ，Y充分負相關[14]。 4.3.3 項集的相關性判斷正負關聯規則 有人提出項集A 和B的關聯規則的相關性]可由式： 度量corrAB ， 有三種可能的情況：如果corrAB>1，那麼 A和B正相關；如果corrAB=1，那麼 A和B互相獨立；如果corrAB<1，那麼 A和B負相關．容易證明項集 A，B間4種形式關聯規則的相關性之間存在這樣的關系：如果corrAB>1，則有corrA┐B < 1；corr┐AB <1；corr┐A┐B> 1；反之亦反之．是以在挖掘正、負關聯規則時隻要對項集的相關性進行判斷就可以避免沖突規則的出現，即當corrAB> 1時僅挖掘規則A B和┐A ┐B；當corrAB <1時僅挖掘規則┐A B和A ┐B；當corrAB=1時不挖掘規則[19]． 4.3.4 正、負關聯規則間的置信度關系研究 當同時研究項集A、B間的正、負關聯規則(A B 、A ┐B 、┐A B 及┐A ┐B)時，置信度的設定問題變得非常重要。當A，B的支援度變化時，四種關聯規則的置信度如何變化，它們之間有着怎樣的聯系，對此進行了詳細讨論，結論對置信度的設定有重要價值。 為了讨論的友善，設s(A)，s(B)很小時取值0．1，很大時取值0．9，下面按四種情況分别讨論。 (1)s(A)，s(B)都很小 conf(A B)的值域是[0，1] conf(A ┐B)的值域是[0，1] conf(┐A B)的值域是[0，0．1 1] conf(┐A ┐B)的值域是[0．89，1] (2)s(A)，s(B)都很大 conf(A B)的值域是[0．89，1] conf(A ┐B)的值域是[0，0．11] conf(┐A B)的值域是[0，1] conf(┐A ┐B)的值域是[0，1] (3)s(A)很小，s(B)很大 conf(A B)的值域是[0，1] conf(A ┐B)的值域是[0，1] conf(┐A B)的值域是[0．89，1] conf(┐A ┐B)的值域是[0，0．11] (4)s(A)很大，s(B)很小 conf(A B)的值域是[0，0．11] conf(┐A B)的值域是[0．89，1] conf(┐A B)的值域是[0，1] conf(┐A ┐B)的值域是[0，1] 總上所述，當同時研究正、負關聯規則後，置信度的設定問題變得非常重要，它直接影響到結果中關聯規則的數量，進而影響到使用者選擇所需規則的難易程度，單一的置信度限制已經不符合要求，而應根據實際應用為四種形式關聯規則分别設定置信度；同時，四種形式關聯規則的置信度之間存在着制約關系，在為其設定置信度時應綜合考慮[15]。 4.3.5 挖掘正負關聯規則 本文除了支援度－可信度外添加了相關系數來挖掘同時對其資料進行了如下編碼[16]。 4.3.6 布爾權重關聯規則的幾種開采算法及比較 關聯規則挖掘在許多領域已有廣泛的應用，目前存在許多發現關聯規則的算法。這些算法都認為每個項目對規則的重要性相同。但在實際應用中，使用者會比較看重一些項目，是以，為了加強這些項目對規則的影響，提出了一些權重關聯規則的算法，介紹了幾種存在的算法，并對它們進行了分析比較。 4.3.6 關聯規則的增量式更新 在關聯規則挖掘的實際應用中存在着如下情況： (1)資料庫或資料倉庫是随時間而不斷變化的，因而存在于其中的關聯規則也是随之變化的，這就要求人們能夠适時地更新已發現的關聯規則。 (2)使用者在一個固定的資料庫或資料倉庫中挖掘關聯規則時，為了得到真正令其感興趣的關聯規則，必然會不斷調整最小支援度與最小置信度，此時同樣需要對關聯規則進行更新。 把以上兩種情況歸納為三個關聯規則增量更新的主要問題： (1)在給定的最小支援度和最小置信度下，當一個新的資料集db添加到舊的資料庫DB中時，如何生成db∪DB中的關聯規則。 (2)在給定的最小支援度和最小置信度下，當一個資料集db從舊的資料庫DB中删除時，如何生成DB∪db中的關聯規則。 (3)給定資料庫DB，在最小支援度和最小置信度發生變化時，如何生成資料庫DB中的關聯規則。所有的關聯規則更新問題都可以歸結為以上三種情況或它們的組合[24]。 D．W．Cheung等人首先考慮了關聯規則的高效更新同題．他們考慮的同題是給定交易資料庫DB，候定最小支援度不變，當一個新的交易資料集db添加到DB中去時，如何生成DB∪db中的關聯規則．他們提出了增量式更新算法FUP，FUP的基本架構和Apriori是一緻的[22]． 4.3.6.1 FUP算法 算法FUP的基本思想為：對任意一個k(k≥1)項集，若其在DB和如中都是頻繁項集，則其在db∪DB中同樣是頻繁項集；若其在DB和db中都是非頻繁項集，則其在db∪DB同樣是非頻繁項集；若其僅在DB(db)中是頻繁項集，則其支援數應該加上db(DB)中的支援數以決定它在db ∪DB是否為頻繁項集。算法FUP假設在DB中發現的頻繁項集 (n為L中最大元素的元素個數)已被儲存下來。它需要對DB和db進行n次掃描，在第一次掃描時，FUP算法首先掃描db，将L1中的元素仍為db∪DB 中的頻繁項集的元素記入L1’ ，并生成候選頻繁l項集C1，C1中的元素為db中的頻繁1項集減去L1；然後掃描DB以決定C1中的元素是否為db∪DB中的頻繁項集，并将是db∪DB中頻繁項集的元素記入L1’中。在第k(k>1)次掃描前，先對L’k-1用Apriori—Gen函數生成候選頻繁k項集Ck，并除去Lk中的元素，即Ck=Ck - Lk，對Lk進行剪枝，即對于X∈L ，若存在Y X且Y∈Lk-1 - L k-1 ‘，則X肯定不是db∪DB中的頻繁項集，應将其在Lk中删除；然後掃描db，将Lk中的元素仍為db∪DB中的頻繁項集的元素記入Lk ‘，記錄候選頻繁k項集Ck中的元素在db中的支援數；最後掃描DB，記錄Ck中的元素在db∪DB中的支援數，掃描結束時，将Ck中是db∪DB中的頻繁項集的元素記入Lk ‘中。算法在Lk和Ck均為空時結束。 4.3.6.2 改進算法EFUP 這裡首先聲明算法中需要用到的符号定義。│X│表示對象的大小，若X為項集，則表示項集中的元素個數；若X為資料庫，則表示資料庫中記錄的數目。DB為舊的資料庫，db為新添加的資料庫，D 和d分别代表新舊資料庫中記錄數目。n為DB中最大的頻繁項集的元素個數。 (1≤i≤n)表示DB中的頻繁i項集的集合。 表示DB 中所有頻繁項集的集合。m為db中最大的頻繁項集的元素個數。 表示db中的頻繁i項集的集合。 (1≤ ≤m)表示db中的候選頻繁i項集的集合。 表示db中所有頻繁項集的集合。P為db∪DB中最大的頻繁項集的元素個數。 表示db∪DB中的頻繁項集的集合。 表示db∪DB中所有頻繁項集的集合。X.sup表示項集的支援數。min_sup和min_conf分别代表最小支援度和最小置信度。 當db添加到DB時，會發生以下兩種情況： (1)一些DB 中的頻繁項集變為db∪DB中的非頻繁項集； (2)一些DB中的非頻繁項集變為db∪DB中的頻繁項集。 根據頻繁項集的定義，可以知道： (1)對任意一個項集X∈L，X不是db∪DB中的頻繁項集(即X L’)，當且僅當 在db∪DB中的支援數小于(D+d)×min_sup。 (2)對任意一個項集X L，若X ∈L ，則X在db中的支援數必然大于等于d×min_sup。 (3)對任意一個項集X∈L，若X L ，則對任意項集Y X,Y∈L，必有Y L 。 EFUP算法要求可以得到前一次對DB挖掘的結果(即頻繁項集和其中元素的支援數)。由以上分析可知： (1)要驗證，J中的項集 是否為db∪DB中的頻繁項集，隻需知道X在db中的支援數。 (2)db添加到DB後新産生的頻繁項集LN(LN LL，但LN L’)的候選頻繁項集為db中的頻繁項集Ldb。 是以可以對db采用類似于Apriori的算法，一方面驗證L中的元素是否為db∪DB中的頻繁項集，另一方面生成其中的頻繁項集Ldb，然後對DB進行一次掃描，驗證Ldb中的元素是否為db∪DB中的頻繁項集。 4.3.7 并行化的分組關聯規則算法 分組的構造以及分組後因連接配接步和剪枝步的簡化而達到的效率的提高。 (1) 設Apriol i中的頻繁一項目集記為L，改進算法将原來的頻繁項L集進行分組，組數可以為大于2的數。 (2) Apriori算法的剪枝思想：對候選k項目集，生成它的所有k-1項子集，判斷是否是頻繁項目集，每次判斷都必須掃描頻繁k—l項目集的元素。分組後可以改進判斷時所需掃描的頻繁k-l項目集元索的數目[25]。 劃分方法的資料挖掘： 通過劃分方法進行資料挖掘的過程如下所示,系統的總體設計包含三部分： (1) 在伺服器端第一次掃描超市事務資料庫中的表，按照超市事務資料庫中不同項集的數量，以及兼顧用戶端計算機硬體配置，對其進行資料分塊，分塊的大小選擇要使得每個分塊可以被放入主存。 (2) 在各個用戶端計算機上，利用并行技術分别通路伺服器上的資料分塊，求出各資料分塊所對應的局部頻繁項集，并将所求局部頻繁項集存入伺服器的一個指定表中。 (3) 在伺服器端，彙總各個分塊資料生成的局部頻繁項集，第二次掃描超市事務資料庫中的總表，最終生成全局頻繁項集。 4.3.8 分布式的資料挖掘 1 方案一 為了找出所有全局頻繁項目集，需要經過兩個步驟來完成。過程如下： (1)全局頻繁1項集可以通過掃描各局部資料庫，并在各局部站點之間交換支援數得到。 (2)挖掘全局頻繁k項集(k>1)時，分為以下幾個步驟：①采用Apnon_gen算法基于局部資料庫産生局部頻繁k項集。②求各局部頻繁k項集的超集，并把它作為全局頻繁k項集的候選資料集。③采用Hash技術。将某個候選資料集映射到某個唯一的站點，在該站點對其他各站點發送輪詢請求，收集并計算該候選資料集的全局支援合計數，根據使用者給定的最小支援度最終确定該候選資料集是否是全局大的。④将在某個站點得到的全局頻繁k項集及其全局支援合計數向其他所有站點進行廣播。⑤ 各個局部站點根據各自的局部資料庫對全局頻繁k項集的支援來确定是否進行下一重挖掘。 其體系結構如下圖所示。 方案中由于采用了Hash技術，使各個站點之間的通信量得到了優化，平衡了各個局部站點的通信負荷。但因為采用了局部一局部的通信模式，為了統計某個候選資料集的全局支援合計數，每個站點都要向其他所有站點發送輪詢請求。雖然每個站點的通信負荷比較均衡，但每個站點的通信量都較大，進而導緻整體網絡通信開銷較大。為了進一步減少站點間的通信量，節約網絡通信開銷，提出了方案二。 2 方案二 方案二與方案一的不同之處在于引入了全局知識庫的存儲結構，并采用了局部一全局的通信模式。各個局部站點基于各個局部資料庫産生局部頻繁項目集，全局站點負責求出各局部頻繁項目集的超集，統計其中每個項目的全局支援合計數，并最終确定全局頻繁項目集。最後根據求出的全局頻繁項目集和使用者給定的最小可信度得出基于全局資料庫的關聯規則，并把它存儲到全局知識庫中。具體實作步驟如下： (1)全局頻繁1項集可以通過掃描各局部資料庫，并在各局部場地之間交換支援數得到。 (2)挖掘全局頻繁k項集(k>1)時，可分為以下步驟：①在各局部站點采用Apfiofi～gen算法基于各局部資料庫産生局部頻繁項目集；②各局部站點向全局站點發送各自的局部頻繁項目集及其支援數；③全局站點将各局部站點發送的頻繁項目集進行合并，得到全局頻繁項目集的候選資料集；④全局站點将得到的候選資料集廣播到各個局部站點，在各個局部站點确定本地的新增項目集(在候選資料集中但不在本地頻繁項目集中的項目集)及其局部支援數；⑤ 各局部站點向全局站點發送各自的新增項目集及其局部支援數，并在全局站點進行相應的累加，求出全局頻繁項目集的候選資料集中各個項目集的全局支援合計數。⑥ 全局站點根據使用者給定的最小支援度篩選出全局頻繁項目集。根據在全局站點求得的全局頻繁項目集和使用者給定的最小可信度，生成全局關聯規則，并把它儲存到全局知識庫中，進而完成關聯規則的整個挖掘過程。其體系結構如下圖所示。 3 兩種方案的比較 兩種方案的相似之處在于兩者均采用Apriori—gen算法生成局部頻繁項目集，并且都把各局部頻繁項目集的超集作為求全局頻繁項目集的候選資料集；兩者的不同之處在于計算候選全局頻繁項目集的全局支援合計數的方法和實作過程不同：①方案一是通過引入Hash技術，将各候選資料集映射到某個唯一的場地，并在該場地向其他所有場地發送輪詢請求，從其他所有場地回傳該資料集的各局部支援數，在該場地進行相應的累加，進而求出該項目集的全局支援合計數的；②方案二是各局部站點首先向全局站點發送各自的局部頻繁項目集及其局部支援數，然後在全局站點進行合并求出其超集，并向各局部站點進行廣播，确定各局部站點的新增資料集，各局部站點向全局站點發送各自的新增項目集及其局部支援數，在全局站點進行累加，進而确定其全局支援合計數。兩種方案的另一個不同之處在于兩者的通信模式不同。方案一采用的是局部一局部的通信模式，在求局部頻繁項目集時各局部站點可以是并行的、異步的，而在求候選項目集的全局支援合計數時則要求各站點同步。方案二采用的是局部一全局的通信模式，各個局部站點負責求出本地的頻繁項目集，并與全局站點進行通信，實作了各局部站點的完全異步的通信模式。 方案二中由于采用了局部一全局的通信模式，大大減少了各個局部站點的通信量，比方案一)具有更少的網絡通信開銷和更高的靈活性，但由于全局站點在關聯規則挖掘的整個過程中具有核心地位，因而它對全局站點的安全、可靠和運作速度等性能要求較高[26]。 4.6 研究方向的理論意義和實用價值 關聯規則是發現交易資料庫中不同商品（項）之間的聯系，這些規則找出顧客購買行為模式，如購買了某一商品對購買其他商品的影響。發現這樣的規則可以應用于商品貨架設計、貨存安排以及根據購買模式對使用者進行分類。 4.7 小結 通過對上面的學習，認為可以對矩陣算法進一步優化，可以和負關聯規則聯系起來，添加非出現項，同樣進行編碼。用1表示出現，0沒有。用編碼進行壓縮，比如01011000用88代替。在計算時，也可以用與位的方法觀看是那些位出現了。同樣的數值代表了相同的頻繁集。最後比較數值就可以。可以同時挖掘正負關聯規則。可以與下面的矩陣的可視化結合。 由于實際中有大量的資料，是否可以用稀疏矩陣來存貯的問題。也值得探究。同時也可以用來擴充到多元資料中。用另外的維表示權值等。 第五章 可視化研究 5.1 概述 資訊可視化和資料挖掘是兩個可互為補充利用的相關研究領域。當資訊可視化作為資料挖掘的技術之一時，同其它技術相比，它有一個獨特之處：能極大地發揮使用者的主動參預性。由于對資料進行了可視化，使用者願意進行探索（Explore），在探索過程中有可能發現意外的知識。 5.2 研究現狀 (1)基于表的可視化技術：該方法的基本思想就是用表結構文字化描述關聯規則。表中的每一行描述一條關聯規則，每一列分别描述關聯規則中的參數，包括規則的前項、後項、支援度和置信度。此方法的優點是能夠利用表的基本操作，對感興趣的列(如支援度)進行排序，或者過濾出前項和後項中包含特定項目的規則。但它存在的缺點是十分類似于關聯規則原始的文字描述形式，不能利用圖形和圖像的表達能力以及人對于色彩和形狀敏銳的感覺能力，不利于使用者友善深入地對結果進行觀察和分析。 (2)基于二維矩陣的可視化技術：該方法的基本思想是用一個二維矩陣的行和列分别表示規則的前項和後項，并在對應的矩陣單元畫圖，可以是柱狀圖或條形圖等，。不同的圖形元素(如顔色或高度)可以用來描述關聯規則的不同參數，如規則的支援度和置信度。二維矩陣法的優點是易于可視化一對一布爾關系的關聯。 (3)基于有向圖的可視化技術：有向圖法是另一種流行的關聯規則可視化技術J。其基本思想是有向圖中的結點代表項目，有向圖中連接配接兩個結點的邊代表項目問的關聯。當隻需顯示少量項目(結點)和少量關聯規則(邊)，此方法非常有效。但當項目數和關聯規則數量增多時，有向圖很快變得十分紊亂。此外，有向圖法不能清楚地标注支援度和置信度等關聯規則參數值。 5.3 研究方向的理論意義和實用價值 更有直覺性。 5.4 可視化具體研究 5.4.1 矩陣表示 矩陣的行代表項，列代表項的關聯。每列中不同顔色的塊分别代表規則的先行項和結果項，項的名稱被标注在矩陣的右側。規則的支援度和信任度用相應的條狀圖以不同的比例顯示在陣列的末端[17]。 5.4.2 規則多邊形 前面所介紹的方法都是針對一維關聯規則的，不能或者不能高效地顯示多元關聯規則。一種新的可視化技術— —規則多邊形表示法非常适用于多元關聯規則挖掘結果的顯示。例如有以下多元關聯規則：age(“30-40”)人income(“40K~50K”)A ccupation(“businessman”)= buy(“laptop”)用規則多邊形表示法可視化，所示。該方法可以清楚地表示關聯規則的各個維，從圖中使用者能夠簡單直覺地獲知從特定條件最終會得到哪種後續結果。然而，規則多邊形表示法當在需要同時顯示多條多元關聯規則時，效果會明顯降低。此外支援度、信任度等中繼資料的标注也不太友善[17]。 5.4.3 平行坐标系 用一系列等間隔的水準軸分别表示關聯規則中出現的所有不同的項目，而每一條連接配接相應水準軸的垂直線段則表示一條關聯規則。此外，利用圖形和色彩資訊清晰地描述規則的前項和後項，以及支援度和置信度的取值。圖中，用原點表示前件，方形表示後件[18]。 5.5 小結 通過挖掘，将其結果可視化。 參考資料： [1] 陳京民編著.資料倉庫原理、設計與應用.中國水利水電出版社,2004,1 [2] 資料挖掘實踐 (美)Olivia Parr Rud著.朱揚勇等譯 [3] 資料倉庫與資料挖掘技術 夏火松主編.70-71, [4] 資料挖掘教程 (美)Richard J。Roiger，(美)Michael W。Geatz著.翁敬農譯。 4 [5] 資料倉庫及其在電信領域中的應用 段雲峰等編著. 39,47,56 [6] SQL Server 2000資料倉庫應用與開發 羅運模等編著 [7] 資料倉庫技術指南 (美)Lou Agosta著.潇湘工作室譯 258 [8] http://www.pku-ht.com/ [9] http://www.stcsm.gov.cn/learning/lesson/xinxi/20021125/lesson.Asp [10] 蔡偉傑 張曉輝 朱建秋 朱揚勇. 關聯規則挖掘綜述 2004 [11] 邊有兵 孫張亞. 一種改進的關聯規則快速算法及其應用 [12] http://www.cs.ust.hk [13] 曾萬聃 周緒波 戴勃 常桂然 李春平. 關聯規則挖掘的矩陣算法 計算機工程 2006年1月, 45-47 [14] 張倩王治和 張國治 基于相關系數的正、負關聯規則挖掘算法 陝西理工學報 2005，12 35－38 [15] 董祥軍 陳建斌 崔林 宋瀚濤 陸玉昌. 正、負關聯規則間的置信度關系研究 計算機應用及研究 2005 第七期 34 [16] Maria-Luiza Antonie Osmar R. Za¨ıane. Mining Positive and Negative Association Rules. Department of Computing Science, University of Alberta Edmonton, Alberta, Canada [17] 郎璟 王保保. 關聯規則挖掘結果的可視化技術研究 電子科技2004年第10期 [18] 吉根林 韋索雲 曲維光. 基于平行坐标的關聯規則可視化新技術 計算機工程 2005年12月第24期 [19] Brin S，Motwani R，Silverstein C．Beyond market：Generalizing association rules to correlations[A]．Processing of the ACM SIGM OD Conference 1 997[C]．New York：ACM Press，1997．265—2 [20] Agrawal Data Mining association rules between sets of items in large databases．In：Proceedings of ACM SIGMOD Conference on Management of Data，Washington，DC May 1993．207～216 [21] 潘立武 王保保 李緒成 零售業銷售資料關聯規則挖掘算法關鍵思想研究 信陽師範學院學報(自然科學版) 第l6卷第1期2003年1月 90-92 [22] Cheung D W et at．Maintenance of discovered association rules in large databases；an incremental updating technique In：Proceed of the 12th International Conference on Data Engineering，New Orleans Louisana，1999．106~ 114 [23] 肖勁橙，林子禹，毛超 關聯規則在零售商業的應用 計算機工程 2004年2月 301-306 [24] 李寶東 宋瀚濤 關聯規則增量更新算法研究 計算機工程與應用 2002 23 6-8 [25] 張偉，鄭濤，李輝 一種并行化的分組關聯規則算法計算機工程 2004年11月 84-86 [26] 李逸波 于吉紅 白曉明 合理選擇資料挖掘工具 計算機與資訊技術 2005-08 [27] 鄒麗 孫輝 李浩 分布式系統下挖掘關聯規則的兩種方案 計算機應用研究 2006年第一期 77-78 [28] R. Agrawal, et al. Mining association rules between sets of items in large databases. Proc. ACM SIGMOD int'l conf. management of data, Washington, DC, May 1993, 207～216 [29] R. Agrawal, R. Srikant. Fast algorithms for mining association rules. Proc. 20th int'l conf. very large databases, Santiago, Chile, Sept. 1994, 487～499 [30] J. S. Park, et al. Using a hash-based method with transaction trimming for mining association rules. IEEE Transactions on knowledge and data engineering, 1997, 9(5), 813～825 [31] A. Savasere, E. Omiecinski and S. Navathe. An efficient algorithm for mining association rules. Proceedings of the 21st international conference on very large databases, Zurich, Switzerland, Sept. 1995, 432～444 [32] Hannu Toivonen. Sampling large databases for association rules. Proceedings of the 22nd international conference on very large databases, Bombay, India, 1996, 134～145 [33] D. W. Cheung, et al. Maintenance of discovered association rules in large databases: an incremental updating technique. In: Proceedings of the 12th international conference on data engineering, New Orleans Louisiana, 1995, 106～114 [34] 馮玉才, 馮劍林. 關聯規則的增量式更新算法. 軟體學報, 1998, 9(4),301～306 [35] R. Agrawal, et al. Parallel mining of association rules. IEEE Transactions on knowledge and data engineering, 1996, 8(6), 962～969 [36] J. S. Park, et al. Efficient parallel data mining for association rules. Proc. Fourth int'l conf. information and Knowledge management, Baltimore, Nov. 1995 [37] D. W. Cheung, et al. efficient mining of association rules in distributed databases. IEEE Transactions on knowledge and data engineering, 1996, 8(6), 910～921 [38] D. W. Cheung, et al. A fast distributed algorithm for mining association rules. Proc. of 1996 Int'l Conf. on Parallel and Distributed Information Systems (PDIS'96), Miami Beach, Florida, USA, Dec. 1996 [39] J. Han, Y. Fu. Discovery of multiple-level association rules from large databases. Proc. of the 21st international conference on very large databases, Zurich, Switzerland, Sept. 1995, 420～431 [40] R. Srikant, R. Agrawal. Mining generalized association rules. In: Proceedings of the 21st international conference on very large databases, Zurich, Switzerland, Sept. 1995, 407～419 [41] G. Piatetsky-Shapiro. Discovery, Analysis, and Presentation of strong rules. In: G. Piatetsky Shapiro and W. J. Frawley eds. Knowledge discovery in database. AAAI/MIT Press. 1991, 229～248 [42] R. Srikant, R. Agrawal. Mining quantitative association rules in large relational tables. In: Proc. 1996 ACM SIGMOD int'l Conf. Management Data, Montreal, Canada, 1996, 1～12 [43] 張朝晖, 陸玉昌, 張 钹. 發掘多值屬性的關聯規則. 軟體學報, 1998, 9(11), 801～805 [44] R. Srikant, R. Agrawal. Mining association rules with item constrains. Proc. of the 3rd Int'l Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, August 1997, 67～73 [45] R. Ng, L. V. S. Lakshmanan, J. Han and A. Pang, Exploratory Mining and Pruning Optimizations of Constrained Associations Rules, Proc. of 1998 ACM-SIGMOD Conf. on Management of Data, Seattle, Washington, June 1998, 13～24 [46] L. V. S. Lakshmanan, R. Ng, J. Han and A. Pang, Optimization of Constrained Frequent Set Queries with 2-Variable Constraints, Proc. 1999 ACM-SIGMOD Conf. on Management of Data, Philadelphia, PA, June 1999 [47] R. Ng, L. V. S. Lakshmanan, J. Han and T. Mah, Exploratory Mining via Constrained Frequent Set Queries, Proc. 1999 ACM-SIGMOD Conf. on Management of Data, Philadelphia, PA, June 1999 [48] R. J. Bayardo Jr., R. Agrawal, and D. Gunopulos. Constraint-Based Rule Mining in Large, Dense Databases. In Proc. of the 15th Int'l Conf. on Data Engineering, 1999, 188～197 [49] Micheline Kamber, Jiawei Han, Jenny Y. Chiang, Metarule-Guided Mining of Multi-Dimensional Association Rules Using Data Cubes, Proceeding of the 3rd International Conference on Knowledge Discovery and Data Mining, Newport Beach, California, Aug. 1997, 207～210 [50] Y. Fu and J.Han, Meta-Rule-Guided Mining of Association Rules in Relational Databases, Proc. 1995 Int'l Workshop. on Knowledge Discovery and Deductive and Object-Oriented Databases(KDOOD'95), Singapore, December 1995, pp.39～46 [51] Wei-Min Shen, et al. Metaqueries for data mining. In: U. M. Fayyad, G. Piatetsky-Shapiro, et al eds. Advances in knowledge discovery and data mining. AAAI/MIT Press. 1996, 375～398 [52] R. Meo, G. Psaila, and S. Ceri. A new SQL-like operator for mining association rules. Proc. of the 22nd int. Conf. on very large databases, Bombay, India, 1996, 122～133 [53] J. Han, Y. Fu, K. Koperski, W. Wang, and O. Zaiane, DMQL: A Data Mining Query Language for Relational Databases, 1996 SIGMOD'96 Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'96), Montreal, Canada, June 1996 [54] R. J. Bayardo Jr., Efficiently Mining Long Patterns from Databases, Proc. of the ACM SIGMOD Conference on Management of Data, Seattle, Washington, June 1998, 85～93 [55] S. Brin, R.Motwani, and C. Silverstein. Beyond market basket: generalizing association rules to correlation. Proc. 1997 ACM-SIGMOD int. conf. management of data, Tucson, Arizona, May 1997, 265～276 [56] C. Silverstein, S. Brin, R. Motwani, and J. Ullman. Scalable techniques for mining causal structures. Proc. 1998 int. conf. Very Large Data Bases, New York, NY, August 1998, 594～605 [57] F. Korn, et al. Ratio rules: A new paradigm for fast, quantifiable data mining. Proc. 1998 int. conf. Very Large Data Bases, New York, NY, August 1998, 582～593 [58] B. Ozden, et al. Cylic association rules. Proc 1998 int. conf. Data Engineering, Orlando, FL, Feb. 1998, 412～421 [59] S. Ramaswamy, et al. On the discovery of interesting patterns in association rules, Proc. 1998 int. conf. Very Large Data Bases, New York, NY, August 1998, 368～379 [60] 鐵治欣 陳奇 俞瑞钊 關聯規則采掘綜述 計算機應用研究 2000 Vol.17 No.1 P.1-5 from:http://blog.csdn.net/longronglin/archive/2010/04/10/5469632.aspx#_Toc135108268