面向屬性歸納綜述.doc

面向屬性歸納綜述摘要 面向屬性的歸納是新近提出的一種廣泛用于數(shù)據(jù)庫中知識發(fā)現(xiàn)的方法。本文綜合敘述了面向屬性歸納的概念、主要思想和面向屬性歸納的基本方法以及算法；對面向屬性歸納的應用例子進行了簡單的綜合描述。1、 引言在“數(shù)據(jù)爆炸但知識貧乏”的網(wǎng)絡時代，人們希望能夠對數(shù)據(jù)進行更高層次的分析，以便更好地利用這些數(shù)據(jù)或者說可以用于決策的知識，基于此，知識發(fā)現(xiàn)或者數(shù)據(jù)挖掘技術產生了，并顯示出強大的生命力?；跀?shù)據(jù)庫的知識發(fā)現(xiàn)（KDD）一詞最早是在1989年8月于美國底特律市召開的第一屆KDD國際學術會議上正式形成的；1996年，F(xiàn)ayyad, Piatetsky-Shapio和Smyth將KDD過程定義為:從數(shù)據(jù)集中識別出有效的、新穎的、潛在有用的、以及最終可理解的模式的非平凡過程；并指出數(shù)據(jù)挖掘是知識發(fā)現(xiàn)的核心部分，是重要步驟，是采用機器學習、統(tǒng)計等方法進行知識學習的階段，其中數(shù)據(jù)挖掘技術就包含面向歸納方法。面向屬性的歸納(AOI, Attribute Oriented Induction) 是一種面向關系數(shù)據(jù)庫查詢的、基于概化的、聯(lián)機的數(shù)據(jù)分析處理技術, 是用于數(shù)據(jù)庫的知識發(fā)現(xiàn)方法。最早于1989年Jiawei Han等人提出, 并對此作了比較全面的介紹。這種方法在知識發(fā)現(xiàn)中發(fā)揮著重要的作用。2、 面向屬性的歸納面向屬性的歸納使用概念分層，通過以高層概念替換低層數(shù)據(jù)概化訓練數(shù)據(jù)，目前是數(shù)據(jù)挖掘主要技術之一。面向屬性歸納方法是面向查詢的、基于泛化的聯(lián)機數(shù)據(jù)分析處理技術。為了有效地進行知識發(fā)現(xiàn)，為了使用戶得到高層次、適當概括的簡化信息，通常采用面向屬性的歸納技術，通過屬性泛化和屬性約簡，對原始數(shù)據(jù)作必要的處理；面向屬性的歸納是目前主要的數(shù)據(jù)歸約方法。其主要思想是: 首先使用關系數(shù)據(jù)庫查詢收集任務相關的數(shù)據(jù); 然后通過考察任務相關數(shù)據(jù)中每個屬性的不同值的數(shù)量, 進行屬性概化。生成的結果廣義關系可以映射到不同形式, 如圖表或規(guī)則, 提供給用戶。AOI主要用來歸納數(shù)據(jù)，應用于大數(shù)據(jù)集，一方面能夠讓用戶在一個更有意義的概念層來觀察數(shù)據(jù)，另一方面AOI極大地縮小了數(shù)據(jù)的向量空間；減少了數(shù)據(jù)的讀寫次數(shù)，節(jié)省了空間。這種多維多層次的數(shù)據(jù)概化分析與數(shù)據(jù)倉庫中的多維數(shù)據(jù)分析，即在線分析處理(簡稱OLAP)功能相似，但是存在著的區(qū)別是：（1）目前許多OLAP所處理的屬性只能是非數(shù)值類型的，而處理功能也僅能用于對數(shù)值數(shù)據(jù)的處理；而在概念描述形成過程中，數(shù)據(jù)庫中的數(shù)據(jù)可以足各種類型，其中包括:數(shù)值型、非數(shù)值型、文本型、圖像；數(shù)據(jù)庫概念描述則能夠處理復雜數(shù)據(jù)類型和對復雜數(shù)據(jù)進行處理；（2）數(shù)據(jù)倉庫中在線分析處理過程完全是一個用戶控制驅使的過程，選擇所分析維(屬性)和有關OLAP操作均是由用戶控制的；與此相比，概念描述則是一個更加自動化的數(shù)據(jù)挖掘過程，它的目的就是幫助用戶找到更有趣的數(shù)據(jù)。3、 面向屬性歸納的方法以及基本的算法3.1 面向屬性歸納的基本方法是屬性聚焦，屬性刪除，屬性概化，屬性概化閾值控制，概化 關系閾值控制，概化的表示。（1） 屬性聚焦選擇和當前分析相關的數(shù)據(jù)，包括屬性和維，選擇相關的數(shù)據(jù)集可以提高挖掘效果，還能夠產生更有意義的規(guī)則，我們可以從描述過程中刪除些不相關的或弱相關的屬性來提高概化的效率。執(zhí)行數(shù)據(jù)挖掘查詢語言后收集到的任務相關的數(shù)據(jù)集被稱為初始工作關系。（2） 屬性刪除如果某個屬性包含大量的不同值，那么，在下列兩種情況下，該屬性就應該被刪除：（1）在該屬性上沒有概化操作；如果保留該屬性，就會產生不簡潔的規(guī)則；（2）它的較高層概念己經有其他屬性表示，在這種情況下，刪除該屬性等價于使用了概化操作。（3） 屬性概化“屬性具有大量不同的值”的度取決于屬性或應用；如果屬性概化得過高，會導致過分概化;如果屬性不能在足夠高的層次概化，會導致概化不足。過分概化和概化不足都會使產生的規(guī)則包含的信息量不夠。因此需要對屬性概化過程進行有效的控制。常用的控制方法有兩種:屬性概化閾值控制和概化關系閾值控制。（4）屬性概化閾值控制屬性概化閾值規(guī)定屬性不同值的個數(shù)可以允許的上限?？梢詫γ總€屬性設置一個閾值，也可以對所有的屬性設置同一個閾值。通常情況下，數(shù)據(jù)挖掘系統(tǒng)都有一個缺省的屬性概化閾值，取位范圍為2-8.屬性概化閾值也可以由用戶或專家指定或調整，加大閩值可以降低概化的層次，減小閩值可以提高概化的層次。（5） 概化關系閾值控制概化關系閾值也可以由用戶或專家指定或調整，加大閾值可以降低概化的層次，減小閾值可以提高概化的層次。在實際的操作中，可以根據(jù)用戶調整這兩種控制方法的順序。（6） 概化的表示方式通過概化處理可以得到原始數(shù)據(jù)集的概化關系。通常，直接向用戶提供概化關系作為最終的概念描述，有時也以交叉表、餅狀圖、柱狀圖、曲線、數(shù)據(jù)立方體或量化規(guī)則等更加直觀或抽象的形式描述概化果。3.2 面向屬性歸納的基本算法輸入: (i)關系數(shù)據(jù)庫DB;(ii)數(shù)據(jù)挖掘查詢DM Query;( iii)屬性表t list(包含屬性ti等); (iv)屬性ti上的概念分層或概化操作符的集合Gen(ti);(v)每個屬性ti的概化閾值genthresh(ti)。輸出: 主概化關系P。方法: 方法概述如下。1. W get task relevant data (DM Query,DB); 2. PREPARE FOR GENERALIZATION (W); (a) 掃描W , 收集每個屬性ti的不同值。(注意: 如果W很大,可以通過考察W的樣本來做。)(b) 對于每個屬性ti根據(jù)給定的或缺省的屬性閾值, 確定ti是否應當刪除;如果不刪除,則計算它的最小期望層次Li, 并確定映射對(v, v) , 其中,v是W中ti的不同值, 而v是其在層Li。對應的概化值。3. Pgeneralization (W )。通過用其在映射中對應的v替換W中的每個值v,累計計數(shù)并計算所有聚集值, 導出主概化關系P。這一步可以用下面兩種方法有效地實現(xiàn):(1) 對于每個概化元組, 通過二分檢索將它插入主關系P中。如果元組已在P 中, 則簡單地增加它的計數(shù)值并相應地處理其他的聚集值; 否則, 將它插入P。(2) 在大部分情況下, 由于主關系層不同值的個數(shù)很少, 可以將主關系編碼, 作為m - 維數(shù)組, 其中m 是P 中的屬性數(shù), 而每個維包含對應的概化屬性值。數(shù)組的每個元素存放對應的計數(shù)和其他聚集值(如果有的話)。概化元組的插入通過對應的數(shù)組元素上的度量聚集進行。4、 面向屬性歸納的相關應用隨著數(shù)據(jù)庫技術的廣泛應用, 各行各業(yè)都積累了大量的數(shù)據(jù), 這些數(shù)據(jù)的內在聯(lián)系可能就是有價值的知識, 應用數(shù)據(jù)挖掘面向屬性的歸納方法發(fā)現(xiàn)并提取這些知識, 有十分重要的現(xiàn)實意義，目前這種技術已經用于各行業(yè)中，比如農業(yè)、工業(yè)和服務業(yè)等行業(yè)中，為各個行業(yè)的決策提供更好的信息更有力的數(shù)據(jù)信息。由于面向屬性歸納技術不是很完善的，存在著一些不足之處；例如面向屬性的歸納方法用于在關系數(shù)據(jù)庫中發(fā)現(xiàn)知識,這種方法沒有分析屬性數(shù)據(jù)間的依賴關系,因而產生的規(guī)則不精確,帶有一定的冗余信息等，這就使得面向屬性歸納方法可以和其他技術想結合，比如與K-means方法，與概念聚類方法結合形成更加有效的獲取知識的方法，能更好的運用到各個行業(yè)中，形成了更有效的決策途徑。5、 總結本文主要對面向屬性歸納進行綜合的講述，面向屬性歸納是數(shù)據(jù)挖掘的主要技術之一；綜上所述，數(shù)據(jù)挖掘的主要對象一般是具有極其大量數(shù)據(jù)的關系數(shù)據(jù)庫.由于數(shù)據(jù)量大，所以有很多噪音數(shù)據(jù).而原有的挖掘方法大多對噪音數(shù)據(jù)處理不了.因而使很多有用的知識挖掘不出來，為了提高數(shù)據(jù)提取效率，獲得更加有價值的知識，面向屬性歸納技術出現(xiàn)了。面向屬性歸納的基本方法是數(shù)據(jù)收集，屬性刪除，屬性概化，閾值控制；由于面向屬性歸納存在著一些不足，可以與其他技術相結合形成更加有效的知識獲取方法；目前面向屬性的歸納與各應用行業(yè)數(shù)據(jù)的結合的方式并不完善，仍然值得我們去深入的探索和研究從大量的數(shù)據(jù)中提取隱含的、未知的、對決策有潛在價值的知識和規(guī)則。參考文獻1、黃紅艷，才秀鳳面向屬性的歸納方法研究J科技信息，2007（24）；2、伍小榮，謝立宏面向屬性的歸納與概念聚類J計算機工程，2003，29(5)；3、孫華梅，郭茂祖，焦杰，黃梯云一種新的面向屬性歸納中概念層次技術研究J.管理科學學報，2004，7(1);4、吳蓉運用SQL實現(xiàn)面向屬性歸納的算法J電腦知識與技術，2008,4(1):4-6;5、薛軍，陳英.基于AOI的客戶行為分析方法J. 計算機應用與軟件，2008,25 (6);6、周曉潔，白楊，孫艷華，孫恩昌，張延華.基于數(shù)據(jù)歸約和面向屬性歸納的網(wǎng)絡流量分析系統(tǒng)J. 中國電子科學研究院學報，2009(4);7、田揚戈，邊馥苓.基于概念聚類和面向屬性歸納的區(qū)劃分析J. 武漢大學學報(信息科學報)，2005(30);8、Jiawei Han ,Micheline Kamber. Data Mining Conce