面向?qū)傩詺w納綜述.doc

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