1、收稿日期:2003-09-281作者簡介:郭秀娟(1961 , 女, 吉林省德惠市人, 副教授, 在讀博士研究生.文章編號:100920185(2004 0120049205數據挖掘方法綜述郭秀娟(, 摘要:數據挖掘方法結合了數據庫技術. 數據挖掘技術的常見方法, 、遺傳算法和統計分析方法被應用到各個領域, .關鍵詞:; ; ; 挖掘理論中圖分類號:N 37文獻標識碼:A數據挖掘(Data Mining 是從大量的、不完全的、有噪聲的、模糊的和隨機的數據中, 提取隱含在其中的、人們事先不知道的, 但又是潛在有用的信息和知識的過程1-2. 人們把原始數據看作是形成知識的源泉, 就像從礦石中采礦一

2、樣, 原始數據可以是結構化的, 如關系數據庫中的數據, 也可以是半結構化的, 如文本、圖形、圖像數據, 甚至是分布在網絡上的異構型數據. 發現知識的方法可以是數學的, 可以是非數學的, 也可以是演繹的或是歸納的. 發現了的知識可以被用于信息管理、查詢優化、決策支持、過程控制等, 還可以用于數據自身的維護. 可以說數據挖掘是一門很廣義的交叉學科, 它匯聚了不同領域的研究者, 尤其是數據庫、人工智能、數理統計、可視化、并行計算等方面的學者和工程技術人員2.數據挖掘技術從一開始就是面向應用領域, 它不僅是面向特定數據庫的簡單檢索查詢調用, 而且, 要對數據進行微觀、中觀乃至宏觀的統計、分析、綜合和推

3、理, 以指定實際問題的求解, 企圖發現事件間的相互關聯, 甚至利用已有的數據對未來的活動進行預測.1數據挖掘的方法研究的對象是大量的隱藏在數據內部的有用信息, 如何獲取信息是我們所要解決的問題. 數據挖掘從一個新的角度把數據庫技術、人工智能、統計學等領域結合起來, 從更深層次發掘存在于數據內部新穎、有效、具有潛在效用的乃至最終可理解的模式. 在數據挖掘中, 數據分為訓練數據、測試數據和應用數據3部分. 數據挖掘的關鍵是在訓練數據中發現事實, 以測試數據作為檢驗和修正理論的依據, 把知識應用到數據中. 數據挖掘利用了分類、關聯規則、序列分析、群體分析、機器學習、知識發現及其他統計方法, 能夠通過

4、數據的分析, 預測未來. 數據挖掘有以下幾種常用方法:111關聯規則挖掘1993年, R 1Agrawal 等人首先提出了關聯規則挖掘問題, 他描述的是數據庫中一組數據項之間某種潛在關聯關系的規則. 一個典型的例子是:在超市中, 90%的顧客在購買面包和黃油的同時, 也會購買牛奶. 直觀的意義是:顧客在購買某種商品時有多大的傾向會購買另外一些商品. 找出所有類似的關聯規則, 對于企業確定生產銷售、產品分類設計、市場分析等多方面是有價值的.關聯規則是數據挖掘研究的主要模式之一, 側重于確定數據中不同領域之間的關系, 找出滿足給定條件下的多個域間的依賴關系. 關聯規則挖掘對象一般是大型數據庫(Tr

5、ansactional Database , 該規則一般表示式為:A 1A 2A m =>B 1B 2B m , 其中, A k (k =1, 2, , m , B j (j =1, 2, , n 是數據庫中的數據項. 有Support (A =>B =P (A B , Confidence (A =>B =P (A|B 1數據項之間的第21卷第1期2004年3月吉林建筑工程學院學報Journal of Jilin Architectural and Civil Engineering Institute Vol. 21No. 1Mar 12004關聯, 即根據一個事務中某些

6、數據項的出現可以導出另一些數據項在同一事務中的出現3-4.在關聯規則挖掘法的研究中, 算法的效率是核心問題, 如何提高算法的效率是所要解決的關鍵. 最有影響的是Apriori 算法, 它探查逐級挖掘, Apriori 的性質是頻繁項集的所有非空子集都必須是頻繁的. 112決策樹方法決策樹(decision tree 根據不同的特征, 以樹型結構表示分類或決策集合, . 利用信息論中的互信息(信息增益 , , 再根據字段的不同取值建立樹的分枝. 在每個分枝子集中, , 即可建立決策樹.決策樹起源于概念學習系統S , , , 然后對每一個子集遞歸調用分枝過程, . 最后得到的決策樹能對新的例子進行

7、分類. CL S 的不足是它處為此, Quinlan 提出了著名的ID3學習算法6, 通過選擇窗口來形成決策樹.從示例學習最優化的角度分析, 理想的決策樹分為3種:葉子數最少; 葉子結點深度最小; 葉結點數最少且葉子結點深度最小. 尋優最優決策樹已被證明是N P 困難問題. ID3算法借用信息論中的互信息(信息增益 , 從單一屬性分辨能力的度量, 試圖減少樹的平均深度, 卻忽略了葉子數目的研究. 其啟發式函數并不是最優的, 存在的主要問題有:(1 互信息的計算依賴于屬性取值的數目多少, 而屬性取值較多的屬性并不一定最優.(2 ID3是非遞增學習算法.(3 ID3決策樹是單變量決策樹(在分枝結點

8、上只考慮單個屬性 , 許多復雜概念表達困難, 屬性間的相互關系強調不夠, 容易導致決策樹中子樹的重復或有些屬性在決策樹的某一路徑上被檢驗多次.(4 抗噪聲性差, 訓練例子中, 正例和反例的比例較難控制.針對上述問題, 出現許多較好的改進算法, 劉曉虎等在選擇一個新屬性時, 并不僅僅計算該屬性引起的信息增益, 而是同時考慮樹的兩層結點, 即選擇該屬性后繼續選擇屬性帶來的信息增益. Schlimmer 和Fisher 設計了ID4遞增式算法, 通過修改ID3算法, 在每個可能的決策樹結點創建一系列表, 每個表由未檢測屬性值及其示例組成, 當處理新例時, 每個屬性值的正例和反例遞增計量. 在ID4的

9、基礎上, Utgoff 提出了ID5算法, 它拋棄了舊的檢測屬性下面的子樹, 從下面選擇屬性構造樹. 此外, 還有許多算法使 用了多變量決策樹的形式, 著名的C415系統也是基于決策樹的.113神經網絡方法模擬人腦神經元方法, 以MP 模型和HEBB 學習規則為基礎, 建立了3大類多種神經網絡模型, 即前饋式網絡、反饋式網絡、自組織網絡. 它是一種通過訓練來學習的非線性預測模型, 可以完成分類、聚類等多種數據挖掘任務.神經網絡(neural network 是由大量的簡單神經元, 通過極其豐富和完善的連接而構成的自適應非線性動態系統, 并具有分布存儲、聯想記憶、大規模并行處理、自組織、自學習、

10、自適應等功能7. 網絡能夠模擬人類大腦的結構和功能, 采用某種學習算法從訓練樣本中學習, 并將獲取的知識存儲于網絡各單元之間的連接權中, 神經網絡和基于符號的傳統A I 技術相比, 具有直觀性、并行性和抗噪聲性. 目前, 已出現了許多網絡模型和學習算法, 主要用于分類、優化、模式識別、預測和控制等領域. 在數據挖掘領域, 主要采用前向神經網絡提取分類規則.神經網絡模擬人的形象直覺思維, 其中, 最大的缺點是“黑箱”性, 人們難以理解網絡的學習和決策過程. 因此, 有必要建立“白化”機制, 用規則解釋網絡的權值矩陣, 為決策支持和數據挖掘提供說明, 使從網絡中提取知識成為自動獲取的手段. 通常有

11、兩種解決方案:建立一個基于規則的系統輔助. 神經網絡運行的同時, 將其輸入和輸出模式給基于規則的系統, 然后用反向關聯規則完成網絡的推理過程. 這種方法把網絡的運行過程和解釋過程用兩套系統實現, 開銷大, 不夠靈活; 直接從訓練好的網絡中提取(分類 規則. 這是當前數據挖掘使用得比較多的方法.05吉林建筑工程學院學報第21卷從網絡中采掘規則, 主要有以下傾向:(1 網絡結構分解的規則提取. 它以神經網絡的隱層結點和輸出層結點為研究對象, 把整個網絡分解為許多單層子網的組合. 這樣研究較簡單的子網, 便于從中挖掘知識. Fu 的KT 算法和Towell 的MofM 算法是有代表性的方法. KT

12、方法的缺點是通用性差, 且當網絡比較復雜時, 要對網絡進行結構的剪枝和刪除冗余結點等預處理工作.(2 神經網絡的非線性映射關系提取規則. , 不考慮網絡的隱層結構, . 以及CSW 算法(將網絡輸入擴展到連續取值 , , 存在許多問題, , 研究提取, 以及及時修正神經網絡并提高神經網絡性能等, .114粗集方法粗集(rough set 理論的特點是不需要預先給定某些特征或屬性的數量描述4,8, 如統計學中的概率分布, 模糊集理論中的隸屬度或隸屬函數等, 而是直接從給定問題出發, 通過不可分辨關系和不可分辨類確定問題的近似域, 從而找出該問題中的內在規律. 粗集理論同模糊集、神經網絡、證據理論

13、等其它理論均成為不確定性計算的一個重要分支.粗集理論是根據目前已有的給定問題的知識, 將問題的論域進行劃分, 然后對劃分后的每一個組成部分確定其對某一概念的支持度, 即肯定支持此概念或不支持此概念. 在粗集理論中, 上述情況分別用3個近似集合來表示正域、負域和邊界.在數據挖掘中, 從實際系統采集到的數據可能包含各種噪聲, 存在許多不確定的因素和不完全信息有待處理. 傳統的不確定信息處理方法, 如模糊集理論、證據理論和概率統計理論等, 因需要數據的附加信息或先驗知識(難以得到 , 有時在處理大量數據的數據庫方面無能為力. 粗集作為一種軟計算方法, 可以克服傳統不確定處理方法的不足, 并且和它們有

14、機結合, 可望進一步增強對不確定、不完全信息的處理能力.粗集理論中, 知識被定義為對事物的分類能力. 這種能力由上近似集、下近似集、等價關系等概念體現. 因為粗集處理的對象是類似二維關系表的信息表(決策表 . 目前, 成熟的關系數據庫管理系統和新發展起來的數據倉庫管理系統, 為粗集的數據挖掘奠定了堅實的基礎.粗集從決策表挖掘規則, 輔助決策, 其關鍵步驟是求值約簡或數據濃縮, 包括屬性約簡Wong SK 和Ziarko W 已經證明求最小約簡是一個N P hard 問題9. 最小約簡的求解需要屬性約簡和值約簡兩個過程, 決策表約簡涉及到核和差別矩陣兩個重要概念. 一般來講, 決策表的相對約簡有

15、許多, 最小約簡(含有最小屬性 是人們期望的. 另一方面, 決策表的核是唯一的, 它定義為所有約簡的交集, 所以, 核可以作為求解最小約簡的起點. 差別矩陣突出屬性的分辨能力, 從中可以求出決策表的核, 以及約簡規則. 借助啟發式搜索解決, 苗奪謙等人從信息論的角度對屬性的重要性作了定義, 并在此基礎上提出了一種新的知識約簡算法M IBAR K , 但其對最小約簡都是不完備的. 此外, 上述方法還只局限于完全決策表. Marzena K 應用差別矩陣, 推廣了等價關系(相似關系 、集合近似等概念, 研究了不完全決策表(屬性的取值含有空值的情況 的規則的發展問題, 從而為粗集的實用化邁出了可喜的

16、一步. Marzena K 還比較了幾種不完全系統的分析方法, 得出如下結論:一個規則是確定的, 如果此規則在原不完全系統的每個完全拓展中是確定的; 刪除從不完全決策表包含空值的對象后, 采掘的知識可能成為偽規則.粗集的數學基礎是集合論, 難以直接處理連續的屬性. 而現實決策表中連續屬性是普遍存在的, 因此, 連續屬性的離散化是制約粗集理論實用化的難點之一, 這個問題一直是人工智能界關注的焦點. 連續屬性的離散化的根本出發點, 是在盡量減少決策表信息損失的前提下(保持決策表不同類對象的可分辨關系 , 得到簡化和濃縮的決策表, 以便用粗集理論分析, 獲得決策所需要的知識. 最優離散化問題(離散的

17、切點數最少 已被證明是N P -hard 問題, 利用一些啟發式算法可以得到滿意的結果. 總體上講, 現有15第1期郭秀娟:數據挖掘方法綜述離散化方法主要分為非監督離散化和監督離散化. 前者包括等寬度(將連續值屬性的值域等份 和等頻率離散化(每個離散化區間所含的對象相同 . 非監督離散化方法簡單, 它忽略了對象的類別信息, 只能用在屬性具有特殊分布的情況. 針對上述問題, 監督離散化方法考慮了分類信息, 提高了離散效果. 目前, 比較有代表性的監督離散化方法有以下幾種:Holte 提出了一種貪婪的單規則離散器(one rule dis 2cretizer 方法; 統計檢驗方法; 信息熵方法等.

18、 這些方法各有特點, , 即每個屬性的離散化過程是相互獨立的, 忽略了屬性之間的關聯, 點. 針對這個問題, , 點和歸納規則數, 而且提高了分類精度. , 即當新的對象加入決策表時, . Mohua Banerjee 等利用集理論獲得初始規則集, 然后, (規則的置信度對應網絡的連接權 10, 訓練后可得到精化的知識. 目前, 基于粗集的數據挖掘在以下方面有待深化.(1粗集和其它軟計算方法的進一步結合問題; (2粗集知識采掘的遞增算法; (3 粗集基本運算的并行算法及硬件實現, 將大幅度改善數據挖掘的效率. 已有的粗集軟件適用范圍還很有限. 決策表中的實例數量和屬性數量受限制. 面對大量的數

19、據, 有必要設計高效的啟發式簡化算法或研究實時性較好的并行算法;(4 擴大處理屬性的類型范圍, 實際數據庫的屬性類型是多樣的, 既有離散屬性, 也有連續屬性; 既有字符屬性, 也有數值屬性. 粗集理論只能處理離散屬性, 因此, 需要設計連續值的離散算法. 115遺傳算法遺傳算法(G A :genetic algorithms 是模擬生物進化過程, 利用復制(選擇 、交叉(重組 和變異(突變 3個基本算子優化求解的技術. 遺傳算法類似統計學, 模型的形式必須預先確定, 在算法實施的過程中, 首先對求解的問題進行編碼, 產生初始群體, 然后計算個體的適應度, 再進行染色體的復制、交換、突變等操作,

20、 優勝劣汰, 適者生存, 直到最佳方案出現為止.遺傳算法在執行過程中, 每一代都有許多不同的種群個體同時存在, 這些染色體中個體的保留與否取決于它們對環境的適應能力, 適應性強的有更多的機會保留下來, 適應性強弱是由計算適應性函數f (x 的值決定的, 這個值稱為適應值(fitness . 適應函數f (x 的構成與目標函數有密切的關系, 這個函數基本上是目標函數的變種.應用遺傳算法解決實際問題, 存在以下幾方面的問題:(1 編碼. 把問題參數按某種形式進行編碼形成個體, 一組個體構成一個種群, 編碼是一項有創造性的工作, 也是遺傳算法應用的關鍵.(2 適應值函數. 適應值是對種群中每個個體的

21、評價. 它涉及到的問題包括:問題的目標函數的確定、目標函數到適應值函數的映射、適應值函數調整等.(3 交叉. 以一定概率P c , 對兩個個體進行交叉. 好的交叉策略能夠使種群迅速收斂到最優解. (4 變異. 以一定概率P c , 對個體上的某種基因(對應于位串上的某位 進行改變. 變異是使當前種群進化的必不可少的條件.遺傳算法的研究方向遺傳算法是多學科結合與滲透的產物, 它已發展成為一種自組織、自適應的綜合技術, 廣泛應用在計算機科學、工程技術和社會科學等領域11. 它的研究工作主要集中在以下幾個方面:(1 基礎理論. 包括進一步發展遺傳算法理論的數學基礎, 從理論和試驗方面研究它們的計算復

22、雜性. 怎樣阻止過早收斂也是人們正在研究的問題之一.(2 分布并行遺傳算法. 遺傳算法在操作上具有高度的并行性, 許多研究人員都在探索在并行機和分25吉林建筑工程學院學報第21卷布式系統上高效執行遺傳算法的策略.(3 分類系統. 分類系統是基于遺傳算法的機器學習中的一類, 它包括一個簡單的基于串規則的并行生成子系統、規則評價子系統和遺傳算法子系統. 分類系統正在被人們越來越多地應用于科學、工程和經濟領域中, 是目前遺傳算法研究領域中一個非常活躍的領域12.(4 遺傳神經網絡. 它包括聯接權、網絡結構和學習規則的進化. , 成功地從時間序列分析來進行財政預算. Muhienbein 絡將會是遺傳

23、神經網絡.(5 進化算法. .除上述方法外, 、統計分析方法、云模型方2結語數據挖掘算法是對上述挖掘方法的具體體現. 數據挖掘研究具有廣泛的應用前景, 它既可應用于決策支持, 也可應用于數據庫管理系統(DBMS 中. 數據挖掘作為決策支持和分析的工具, 可以用于構造知識庫, 在DBMS 中, 數據挖掘可以用于語義查詢優化、完整性約束和不一致檢驗.參考文獻1Han J , K ambr M. Data Mining :Concepts and Techniques M . Beijing Higher Education Press , 2001.2張偉, 廖曉峰, 吳中福1一種基于遺傳算法的聚

24、類新方法J 1計算機科學, 2002, 29(6 :114-11613Agrawal R , Mannila H , Srikant R , et al. Fast discovery of association rules :Advances in knowledge discovery and data mining M . California :MIT Press , 1996:307-328.4Sanjay Soni Unisys , Zhaohui Tang Microsoft Corporation , Jim Y ang Microsoft Corporation Perfo

25、rmance Study of Microsoft Data Mining Algorithms August , 2001.5唐華松, 姚耀文1數據挖掘中決策樹算法的探討J 1計算機應用研究, 2001, (8 :18-2216李德仁, 王樹良, 李德毅, 王新洲1論空間數據挖掘和知識發現的理論與方法J 1武漢大學學報信息科學版, 2002(6 :221-23317周志華, 陳世福1神經網絡集成J 1計算機學報, 2002(6 :587-59018李永敏, 朱善君等1基于粗糙理論的數據挖掘模型J 1清華大學學報(自然科學版 , 1999, 39(1 :110-11319Pawlak Z. Rough Set Theory and its Applications to Data Analysi J . Cybernetics and syst , 1998, 29(7 :661-688.10Tsumoto S. Automated discovery of positive and negative knowledge in clinical database based on rough set model J . IEEE EMB Mag 2azine , 2000, 19(4 :415-422.11糜元根1數據挖掘