時(shí)間：2022-05-22 02:59:56
序論：在您撰寫(xiě)數(shù)據(jù)挖掘算法論文時(shí)，參考他人的優(yōu)秀作品可以開(kāi)闊視野，小編為您整理的1篇范文，希望這些建議能夠激發(fā)您的創(chuàng)作熱情，引導(dǎo)您走向新的創(chuàng)作高度。
摘要：決策樹(shù)（Decision Tree）曾在很長(zhǎng)的時(shí)間里是非常流行的人工智能技術(shù)，隨著數(shù)據(jù)挖掘技術(shù)的發(fā)展，決策樹(shù)作為一個(gè)構(gòu)建決策系統(tǒng)的強(qiáng)有力的技術(shù)在數(shù)據(jù)挖掘和數(shù)據(jù)分析過(guò)程中起到了非常重要的作用。決策樹(shù)在數(shù)據(jù)挖掘中主要用于分類、預(yù)測(cè)以及數(shù)據(jù)的預(yù)處理等。
關(guān)鍵詞：決策樹(shù)；數(shù)據(jù)挖掘；Apriori算法
一、決策樹(shù)數(shù)據(jù)挖掘基本概念
數(shù)據(jù)分類是數(shù)據(jù)挖掘中的一個(gè)重要問(wèn)題，是一種有效的KDD分析方法。數(shù)據(jù)分類通過(guò)分析訓(xùn)練集中的數(shù)據(jù)，建立分類模型，然后利用這個(gè)分類模型，把數(shù)據(jù)庫(kù)中的數(shù)據(jù)項(xiàng)映射到給定類別中。
圖1.決策樹(shù)生成過(guò)程Decision tree formation process
決策樹(shù)分為分類樹(shù)和回歸樹(shù)兩種，分類樹(shù)針對(duì)離散數(shù)據(jù)集生成決策樹(shù)，回歸樹(shù)則針對(duì)連續(xù)變量生成決策樹(shù)。決策樹(shù)生成過(guò)程如圖1所示。
決策樹(shù)是一個(gè)類似于流程圖的樹(shù)結(jié)構(gòu)，決策樹(shù)通過(guò)把實(shí)例從根節(jié)點(diǎn)排列到某個(gè)葉子節(jié)點(diǎn)來(lái)分類實(shí)例，葉子節(jié)點(diǎn)即為實(shí)例所屬的分類。樹(shù)上的每個(gè)節(jié)點(diǎn)說(shuō)明了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值。
如圖2所示，給出了一個(gè)決策樹(shù)的示意描述樣例。該決策樹(shù)給了一個(gè)用于學(xué)生成績(jī)分析的模型。利用它可以分析學(xué)生成績(jī)受什么因素影響，以及會(huì)影響到與學(xué)生成績(jī)相關(guān)的那些屬性。決策樹(shù)的中間結(jié)點(diǎn)通常用矩形表示，而葉子結(jié)點(diǎn)常用橢圓表示。
圖2.決策樹(shù)示意描述Decision tree motioned description
二、決策樹(shù)算法
由于Apriori算法存在必須耗費(fèi)大量時(shí)間處理規(guī)模巨大的候選項(xiàng)目集和必須多次掃描數(shù)據(jù)庫(kù)對(duì)候選項(xiàng)目集進(jìn)行匹配篩選的固有缺陷，針對(duì)這些缺陷Han等人提出了一種基于FP-Tree的關(guān)聯(lián)規(guī)則算法FP-Growth算法。FP-Growth算法用一種壓縮的數(shù)據(jù)結(jié)構(gòu)（FP-Tree）可存儲(chǔ)關(guān)聯(lián)規(guī)則挖掘所需的全部數(shù)據(jù)信息，通過(guò)對(duì)源數(shù)據(jù)的兩次掃描，將數(shù)據(jù)信息存到這種結(jié)構(gòu)里，避開(kāi)了產(chǎn)生候選項(xiàng)集的步驟，極大地減少了數(shù)據(jù)交換和頻繁匹配的開(kāi)銷(xiāo)，這就是無(wú)候選項(xiàng)集產(chǎn)生算法（Frequent Patterns Growth，F(xiàn)P-Growth）。
（一）FP-Growth算法原理與相關(guān)概念。FP-Growth算法通過(guò)如下三方面的改進(jìn)與創(chuàng)新，脫離了必須產(chǎn)生候選項(xiàng)集的傳統(tǒng)方式，開(kāi)辟了關(guān)聯(lián)規(guī)則挖掘的新思路。
1.它構(gòu)造了一種新穎的、緊湊的數(shù)據(jù)結(jié)構(gòu)FP-Tree。它是一種擴(kuò)展的前綴樹(shù)結(jié)構(gòu)，存儲(chǔ)了關(guān)于頻繁模式數(shù)量的重要信息。樹(shù)中只包含長(zhǎng)度為1的頻繁項(xiàng)作為葉節(jié)點(diǎn)，并且那些頻度高的節(jié)點(diǎn)更靠近樹(shù)的根節(jié)點(diǎn)，因此，頻度高的項(xiàng)比那些頻度低的項(xiàng)有更多的機(jī)會(huì)共享同一個(gè)節(jié)點(diǎn)。
2.開(kāi)發(fā)了基于FP-Tree的模式片斷成長(zhǎng)算法，它從長(zhǎng)度為1的頻繁模式開(kāi)始，只檢查它的條件模式基構(gòu)建它的條件模式樹(shù)，并且在這個(gè)樹(shù)上遞歸地執(zhí)行挖掘。模式的成長(zhǎng)通過(guò)聯(lián)合條件模式樹(shù)新產(chǎn)生的后綴模式實(shí)現(xiàn)。由于事務(wù)處理中的頻繁項(xiàng)都對(duì)應(yīng)著頻繁樹(shù)中的路徑進(jìn)行編碼，模式的成長(zhǎng)確保了結(jié)果的完整性。因此，F(xiàn)P-Tree算法不像Apriori類算法那樣需要產(chǎn)生再測(cè)試。挖掘的主要操作是計(jì)算累加值和調(diào)整前綴樹(shù)，這種花費(fèi)通常要遠(yuǎn)遠(yuǎn)小于Apriori類算法中的候選項(xiàng)集的產(chǎn)生和模式匹配操作。
3.挖掘過(guò)程中采用的搜索技術(shù)是基于分區(qū)的，通過(guò)分割再解決的方法，而FP-Tree的結(jié)構(gòu)包括一個(gè)標(biāo)識(shí)成“null”的根、一個(gè)由頻繁項(xiàng)組成的頭表和一組項(xiàng)的前綴子樹(shù)組成了根的子孫。樹(shù)中的每個(gè)節(jié)點(diǎn)包括3個(gè)域：項(xiàng)名（itemname）、計(jì)數(shù)（count）和節(jié)點(diǎn)鏈接（node-link）。其中，項(xiàng)名記錄了節(jié)點(diǎn)所代表的項(xiàng)；計(jì)數(shù)記錄了樹(shù)中到達(dá)這個(gè)節(jié)點(diǎn)的路徑所代表的事務(wù)處理的數(shù)目；節(jié)點(diǎn)鏈接指向樹(shù)中下一個(gè)同名節(jié)點(diǎn)，如果沒(méi)有同名節(jié)點(diǎn)則指向空。頭表中的每條記錄包含兩個(gè)域：項(xiàng)名和節(jié)點(diǎn)鏈接的頭。節(jié)點(diǎn)鏈接的頭指向樹(shù)中第一個(gè)同名的節(jié)點(diǎn)。
（二）FP-Growth算法描述。與Apriori算法的不同，F(xiàn)P-Growth算法中頻繁項(xiàng)集的生成分為兩步進(jìn)行，第一步是構(gòu)造FP-Tree，第二步在第一步的基礎(chǔ)上對(duì)產(chǎn)生的FP-Tree進(jìn)行挖掘以構(gòu)造頻繁項(xiàng)集。
FP-Growth方法將發(fā)現(xiàn)長(zhǎng)頻繁模式的問(wèn)題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些短模式，然后與后綴連接。它使用最不頻繁的項(xiàng)作后綴，提供了好的選擇性。該方法大大降低了搜索開(kāi)銷(xiāo)。當(dāng)數(shù)據(jù)庫(kù)很大時(shí)，構(gòu)造基于內(nèi)存的FP一樹(shù)是不現(xiàn)實(shí)的。一種有趣的替換是首先將數(shù)據(jù)庫(kù)劃分成投影數(shù)據(jù)庫(kù)的集合，然后在每個(gè)投影數(shù)據(jù)庫(kù)上構(gòu)造FP一樹(shù)并挖掘它。該過(guò)程可以遞歸地用于投影數(shù)據(jù)庫(kù)，如果它的FP-Tree還不能放進(jìn)內(nèi)存。對(duì)FP-Tree方法的性能研究表明：對(duì)于挖掘長(zhǎng)的和短的頻繁模式，它都是有效的和規(guī)?；?，并且大約比Apriori算法快一個(gè)數(shù)量級(jí)。它也比樹(shù)-投影算法快。樹(shù)-投影算法遞歸地將數(shù)據(jù)庫(kù)投影為投影數(shù)據(jù)庫(kù)樹(shù)。
FP-Growth算法開(kāi)辟了有效挖掘頻繁模式的新途徑。然而，它的時(shí)間和空間效率還不足夠高，仍需進(jìn)一步改進(jìn)。
摘 要：聚類算法是數(shù)據(jù)挖掘的核心技術(shù),根據(jù)評(píng)價(jià)聚類算法優(yōu)劣的幾個(gè)標(biāo)準(zhǔn),對(duì)數(shù)據(jù)挖掘中常用聚類算法做了比較分析,根據(jù)各自特點(diǎn),加以改進(jìn),并應(yīng)用于武警部隊(duì)數(shù)據(jù)挖掘項(xiàng)目中。通過(guò)運(yùn)用改進(jìn)型Kmeans算法,取得了較好的挖掘結(jié)果,為進(jìn)一步信息的智能化檢索、信息的過(guò)濾、分揀提供依據(jù)。
關(guān)鍵詞：數(shù)據(jù)挖掘;代表點(diǎn)聚類算法;基于密度的聚類算法;Kmeans聚類算法;指揮自動(dòng)化
1 引 言
數(shù)據(jù)挖掘的歷史雖然較短,但從20世紀(jì)90年代以來(lái),他的發(fā)展速度很快,是多學(xué)科綜合的產(chǎn)物。雖然目前還沒(méi)有一個(gè)完整的定義,但這里認(rèn)為：數(shù)據(jù)挖掘就是從海量的數(shù)據(jù)中挖掘出可能有潛在價(jià)值的信息的技術(shù)。這些信息是可能有潛在價(jià)值的,支持決策,可以有效利用指揮自動(dòng)化網(wǎng),為進(jìn)一步研究尋找突破口。
數(shù)據(jù)挖掘綜合了各個(gè)學(xué)科技術(shù),其任務(wù)一般可分為2類：描述和預(yù)測(cè)。描述性挖掘任務(wù)刻劃數(shù)據(jù)庫(kù)中數(shù)據(jù)的一般特性。預(yù)測(cè)性挖掘任務(wù)在當(dāng)前數(shù)據(jù)上進(jìn)行推斷,以進(jìn)行預(yù)測(cè)\[1\]。主要功能有分類和預(yù)測(cè)、聚類分析、關(guān)聯(lián)規(guī)則和序列模式的發(fā)現(xiàn)、偏差的檢測(cè)等。
把數(shù)據(jù)庫(kù)中的對(duì)象分類是數(shù)據(jù)挖掘的基本操作,根據(jù)最大化類內(nèi)的相似性、最小化類間的相似性的原則進(jìn)行聚類或分組,從而使屬于同一類的個(gè)體間距離盡可能小,而不同類個(gè)體間距離盡可能大,為了找到效率高、通用性強(qiáng)的聚類方法人們從不同角度提出近百種聚類方法,典型的有Kmeans方法、Kmedoids方法、CLARANS方法,BIRCH方法等,這些算法適用于特定的問(wèn)題及用戶。
聚類算法一般分為分割和分層2種。分割聚類算法通過(guò)優(yōu)化評(píng)價(jià)函數(shù)把數(shù)據(jù)集分割為K個(gè)部分,他需要K作為輸人參數(shù)。典型的分割聚類算法有Kmeans算法：Kmedoids算法、CLARANS算法。分層聚類由不同層次的分割聚類組成,層次之間的分割具有嵌套的關(guān)系。他不需要輸入?yún)?shù),這是他優(yōu)于分割聚類算法的一個(gè)明顯的優(yōu)點(diǎn),其缺點(diǎn)是終止條件必須具體指定。典型的分層聚類算法有BIRCH算法、DBSCAN算法和CURE算法等。根據(jù)評(píng)價(jià)聚類算法優(yōu)劣的幾個(gè)標(biāo)準(zhǔn)\[2\],對(duì)常用的聚類算法進(jìn)行比較分析。
(1) 是否適用于大數(shù)據(jù)量,算法的效率是否滿足大數(shù)據(jù)量高復(fù)雜性的要求;
(2) 是否能應(yīng)付不同的數(shù)據(jù)類型,能否處理符號(hào)屬性;
(3) 是否能發(fā)現(xiàn)不同類型的聚類;
(4) 是否能應(yīng)付噪聲數(shù)據(jù)或異常數(shù)據(jù);
(5) 是否對(duì)數(shù)據(jù)的輸入順序不敏感。
2 數(shù)據(jù)挖掘常用聚類算法比較分析
2.1 BIRCH算法
BIRCH算法即平衡迭代削減聚類法,其核心是用一個(gè)聚類特征3元組表示一個(gè)簇的有關(guān)信息,從而使一簇點(diǎn)的表示可用對(duì)應(yīng)的聚類特征,而不必用具體的一組點(diǎn)來(lái)表示。他通過(guò)構(gòu)造滿足分支因子和簇直徑限制的聚類特征樹(shù)來(lái)求聚類。BIRCH算法通過(guò)聚類特征可以方便地進(jìn)行中心、半徑、直徑及類內(nèi)、類間距離的運(yùn)算。算法的聚類特征樹(shù)是一個(gè)具有2個(gè)參數(shù)分枝因子B和類直徑T的高度平衡樹(shù)。分枝因子規(guī)定了樹(shù)的每個(gè)節(jié)點(diǎn)子女的最多個(gè)數(shù),而類直徑體現(xiàn)了對(duì)一類點(diǎn)的直徑大小的限制即這些點(diǎn)在多大范圍內(nèi)可以聚為一類,非葉子結(jié)點(diǎn)為他的子女的最大關(guān)鍵字,可以根據(jù)這些關(guān)鍵字進(jìn)行插人索引,他總結(jié)了其子女的信息。
聚類特征樹(shù)可以動(dòng)態(tài)構(gòu)造,因此不要求所有數(shù)據(jù)讀人內(nèi)存,而可以在外存上逐個(gè)讀人。新的數(shù)據(jù)項(xiàng)總是插人到樹(shù)中與該數(shù)據(jù)距離最近的葉子中。如果插人后使得該葉子的直徑大于類直徑T,則把該葉子節(jié)點(diǎn)分裂。其他葉子結(jié)點(diǎn)也需要檢查是否超過(guò)分枝因子來(lái)判斷其分裂與否,直至該數(shù)據(jù)插入到葉子中,并且滿足不超過(guò)類直徑,而每個(gè)非葉子節(jié)點(diǎn)的子女個(gè)數(shù)不大于分枝因子。算法還可以通過(guò)改變類直徑修改特征樹(shù)大小,控制其占內(nèi)存容量。
BIRCH算法通過(guò)一次掃描就可以進(jìn)行較好的聚類,由此可見(jiàn),該算法適合于大數(shù)據(jù)量。BIRCH算法只適用于類的分布呈凸形及球形的情況,并且由于BIRCH算法需提供正確的聚類個(gè)數(shù)和簇直徑限制,對(duì)不可視的高維數(shù)據(jù)不可行。
2.2 CURE算法
CURE算法即使用代表點(diǎn)的聚類方法。該算法先把每個(gè)數(shù)據(jù)點(diǎn)看成一類,然后合并距離最近的類直至類個(gè)數(shù)為所要求的個(gè)數(shù)為止。CURE算法將傳統(tǒng)對(duì)類的表示方法進(jìn)行改進(jìn),回避用所有點(diǎn)或用中心和半徑來(lái)表示一個(gè)類；而是從每一個(gè)類中抽取固定數(shù)量、分布較好的點(diǎn)作為描述此類的代表點(diǎn),并將這些點(diǎn)乘以一個(gè)適當(dāng)?shù)氖湛s因子,使他們更靠近類的中心點(diǎn)。將一個(gè)類用代表點(diǎn)表示,使得類的外延可以向非球形的形狀擴(kuò)展,從而可調(diào)整類的形狀以表達(dá)那些非球形的類。另外,收縮因子的使用減小嗓音對(duì)聚類的影響。CURE算法采用隨機(jī)抽樣與分割相結(jié)合的辦法提高算法的空間和時(shí)間效率,并且在算法中用堆和Kd樹(shù)結(jié)構(gòu)來(lái)提高算法效率。
2.3 DBSCAN算法
DBSCAN算法即基于密度的聚類算法。該算法利用類的密度連通性可以快速發(fā)現(xiàn)任意形狀的類。其基本思想是：對(duì)于一個(gè)類中的每個(gè)對(duì)象,在其給定半徑的領(lǐng)域中包含的對(duì)象不能少于某一給定的最小數(shù)目。在DBSCAN算法中,發(fā)現(xiàn)一個(gè)類的過(guò)程是基于這樣的事實(shí)：一個(gè)類能夠被其中的任意一個(gè)核心對(duì)象所確定。為了發(fā)現(xiàn)一個(gè)類,DBSCAN先從對(duì)象集D中找到任意對(duì)象P,并查找D中關(guān)于關(guān)徑Eps和最小對(duì)象數(shù)Minpts的從P密度可達(dá)的所有對(duì)象。如果P是核心對(duì)象,即半徑為Eps的P的鄰域中包含的對(duì)象不少于Minpts,則根據(jù)算法,可以找到一個(gè)關(guān)于參數(shù)Eps和Minpts的類。如果P是一個(gè)邊界點(diǎn),則半徑為Eps的P鄰域包含的對(duì)象少于Minpts,P被暫時(shí)標(biāo)注為噪聲點(diǎn)。然后,DBSCAN處理D中的下一個(gè)對(duì)象。
摘 要：數(shù)據(jù)挖掘技術(shù)是一個(gè)不斷發(fā)現(xiàn)知識(shí)的過(guò)程。闡述了目前三種流行的數(shù)據(jù)挖掘算法的理論模型及算法思想，并從算法時(shí)間復(fù)雜度、依賴條件和誤差估計(jì)等方面進(jìn)行了比較分析，說(shuō)明了不同算法的優(yōu)勢(shì)和不足。指出了不同算法的應(yīng)用前景，提出了一種將不同算法結(jié)合以減少誤差率，提高算法效率的思路。
關(guān)鍵詞：數(shù)據(jù)挖掘； 關(guān)聯(lián)規(guī)則； 分類算法； 聚類算法
數(shù)據(jù)挖掘是指從海量的數(shù)據(jù)庫(kù)中抽取隱含的、具有潛在使用價(jià)值信息的過(guò)程。它是一種面向應(yīng)用的技術(shù)，不僅針對(duì)特定數(shù)據(jù)庫(kù)進(jìn)行簡(jiǎn)單搜索查詢，且對(duì)數(shù)據(jù)進(jìn)行微觀、中觀乃至宏觀的統(tǒng)計(jì)、分析、綜合和推理，進(jìn)而發(fā)現(xiàn)潛在的知識(shí)。
數(shù)據(jù)挖掘的目的是發(fā)現(xiàn)知識(shí)，而知識(shí)發(fā)現(xiàn)的過(guò)程需要特定數(shù)據(jù)模型的支持，這使得數(shù)據(jù)挖掘算法成為研究的關(guān)鍵點(diǎn)。本文研究3種經(jīng)典的數(shù)據(jù)挖掘算法，即關(guān)聯(lián)規(guī)則挖掘算法、分類算法和聚類算法，并對(duì)它們進(jìn)行了比較分析，指出了各算法的應(yīng)用前景。
1 關(guān)聯(lián)規(guī)則挖掘算法
關(guān)聯(lián)規(guī)則是通過(guò)用戶給定支持度和置信度來(lái)尋找規(guī)則的過(guò)程［1］?；舅枷氚?個(gè)過(guò)程：
（1） 發(fā)現(xiàn)最大頻繁項(xiàng)目集。
通過(guò)用戶給定的支持度，尋找數(shù)據(jù)集中支持度大于或等于給定支持度的所有項(xiàng)目集，即頻繁項(xiàng)目集，再?gòu)念l繁項(xiàng)目集中選出所有不被其他項(xiàng)目包含的頻繁項(xiàng)目集，即最大頻繁項(xiàng)目集。
（2） 生成關(guān)聯(lián)規(guī)則。
通過(guò)用戶給定的置信度，在發(fā)現(xiàn)最大頻繁的項(xiàng)目集中生成置信度大于或等于給定置信度的關(guān)聯(lián)規(guī)則。
思想中支持度是數(shù)據(jù)集D中包含項(xiàng)目集i1的事務(wù)在數(shù)據(jù)集D上的百分比，公式如下：
ИИSupporti1=|{t∈D&i1t}|/|D|（1）И
式中：t是數(shù)據(jù)集D上的一個(gè)事務(wù)。
置信度是指包含i1和i2的事務(wù)數(shù)與包含i1的事務(wù)數(shù)的支持度比值，公式如下：
ИИConfidencei1i2=Supporti1∪i2/Supporti1（2）И
式中：i1∩i2=0。
2 分類算法
分類是根據(jù)數(shù)據(jù)集的特點(diǎn)構(gòu)造一個(gè)分類器，利用該分類器將數(shù)據(jù)集中的數(shù)據(jù)映射到給定類別中某一類的過(guò)程。主要分類算法有k-最鄰近算法、決策樹(shù)分類算法和貝葉斯分類算法。
2.1 k-最鄰近算法
k-最鄰近算法（kNN）是一種基于距離的分類算法，距離越近，相似性越大，距離越遠(yuǎn)，相似性越?。?］。算法的基本思想是為：計(jì)算每個(gè)分類樣本到待分類元組的距離，即計(jì)算相似度，選取與待分類數(shù)據(jù)相似度最大的k個(gè)數(shù)據(jù)，將待分類元組劃分到這k個(gè)數(shù)據(jù)分類屬性最集中的類別中。
2.2 決策樹(shù)算法
決策樹(shù)算法采用自上而下的方法遞歸構(gòu)造決策樹(shù)，分兩個(gè)步驟：決策樹(shù)生成和決策樹(shù)剪枝。典型的決策樹(shù)算法有ID3算法、C4.5算法等［3］。
2.2.1 決策樹(shù)生成算法
決策樹(shù)生成算法采用信息增益來(lái)選擇能使樣本最好分類的屬性，信息增益的計(jì)算如下：
有n個(gè)消息，概率分布為p=(p1,p2，…，pn)，則該樣本SУ鈉諭信息為：
ИI(S)=I(p)=－∑n1pilog2 pi （3）И
對(duì)于給定的樣本si∈S，其樣本總數(shù)為Si，根據(jù)類別屬性值將si劃分為m個(gè)子集，每個(gè)子集中所包含的樣本數(shù)分別為sij(1≤j≤m)，其概率分布為p=(Si1/Si,Si2/Si，…，Sim/Si)。根據(jù)公式得樣本si的期望信息為I(si)=I(p)。
樣本集SУ攆匚：
ИE(S)=－∑m1(Si1+Si2+…+Sim)I(si)S（4）И
樣本S的信息增益為：
ИG(S)=I(S)－E(S)（5）И
算法的基本思想：
（1） 以代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開(kāi)始建樹(shù)。
（2） 如果樣本S都屬于同一個(gè)分類，則將該結(jié)點(diǎn)作為葉子結(jié)點(diǎn)。
（3） 否則，利用公式計(jì)算各個(gè)屬性的信息增益，比較計(jì)算所得的信息增益值，選取信息增益最大的屬性作為根結(jié)點(diǎn)。
（4） 遞歸劃分選取的根結(jié)點(diǎn)，直到下面3個(gè)條件之一滿足時(shí)結(jié)束： 給定結(jié)點(diǎn)的所有樣本屬于同一分類；沒(méi)有多余的屬性可以用來(lái)進(jìn)一步劃分樣本，此時(shí)采用多數(shù)表決法來(lái)創(chuàng)建葉節(jié)點(diǎn)；分支屬性樣本為空。
2.2.2 決策樹(shù)剪枝算法
理想的決策樹(shù)分為3種：葉結(jié)點(diǎn)數(shù)最少；葉子結(jié)點(diǎn)深度最小；葉結(jié)點(diǎn)數(shù)最少，且葉子結(jié)點(diǎn)的深度最?。?］。在決策樹(shù)生成算法中沒(méi)有考慮噪聲等影響的因素，因此可能出現(xiàn)過(guò)度擬合現(xiàn)象，使分類預(yù)測(cè)性能降低，導(dǎo)致生成的決策樹(shù)不盡理想。為了避免過(guò)度擬合，提出了決策樹(shù)剪枝算法，該方法有預(yù)先剪枝和后剪枝2種。預(yù)先剪枝指在生成決策樹(shù)的同時(shí)，決定是繼續(xù)劃分還是停止劃分。預(yù)先剪枝的最大缺點(diǎn)是可能使樹(shù)的生長(zhǎng)過(guò)早停止，導(dǎo)致生成的決策樹(shù)不完整，因此應(yīng)用較少。后剪枝是一種先擬合后化簡(jiǎn)的方法，首先采用決策樹(shù)生成算法對(duì)訓(xùn)練樣本生成決策樹(shù)，然后從樹(shù)的葉子結(jié)點(diǎn)開(kāi)始逐步向根的方向進(jìn)行剪枝，具體的剪枝算法在本文不予以討論。
2.3 貝葉斯分類
貝葉斯分類以貝葉斯定理為基礎(chǔ)［5］，貝葉斯定理是：H為某種假定，P(H)為先驗(yàn)概率，P(X|H)為H成立條件下X的概率，則后驗(yàn)概率P(H|X)為：
ИP(H|X)=P(X|H)P(X) （6）И
貝葉斯分類的原理是通過(guò)某對(duì)象的先驗(yàn)概率，利用貝葉斯定理計(jì)算出其后驗(yàn)概率，即該對(duì)象屬于某一類的概率，選擇具有最大后驗(yàn)概率的類作為該對(duì)象所屬的類。
算法的基本思想：
（1） 根據(jù)訓(xùn)練樣本計(jì)算分類屬性的先驗(yàn)概率P(ci)。
（2） 計(jì)算待分類數(shù)據(jù)每個(gè)非分類屬性的條件概率P(x|ci)。
（3） 由于各非分類屬性可視為條件獨(dú)立，故P(x|ci)=∏n1(xk|ci)。
（4） 利用式（6）計(jì)算ci的后驗(yàn)概率。
因?yàn)镻(x)和P(ci)是常數(shù)，所以P(x|ci)最大，則后驗(yàn)概率最大，故將待分類數(shù)據(jù)劃分到P(x|ci)最大的ci所在類別中。
3 聚類方法
聚類就是將數(shù)據(jù)對(duì)象分成多個(gè)簇，簇內(nèi)有較高的相似性，而簇間差異很大。典型的聚類分析方法有劃分方法和層次方法。
3.1 劃分方法
劃分方法依據(jù)數(shù)據(jù)點(diǎn)在幾何空間的距離來(lái)判斷個(gè)體間的相似度，距離越近就越相似，就越容易劃分為一類。劃分的原則是在同一個(gè)簇中的對(duì)象間有較高的相似性，而不同簇間差異很大。
3.1.1 k-平均算法
k-平均算法（k-means）是一種以簇內(nèi)對(duì)象的均值為中心點(diǎn)的劃分方法［6］。算法用歐氏距離來(lái)表示點(diǎn)到簇的距離：
Иd(x,y)=∑k1(xi－yi)2 （7）И
算法的準(zhǔn)則函數(shù)定義為：
ИE=∑k1∑x∈ci|x－xi| （8）И
算法基本思想：
（1） 隨機(jī)地選取k個(gè)對(duì)象，每個(gè)對(duì)象代表一個(gè)簇的初始中心。
（2） 根據(jù)式（7）計(jì)算剩余對(duì)象到中心點(diǎn)的歐氏距離，將每個(gè)對(duì)象賦給與其歐氏距離最小的簇，即最相似的簇。
（3） 重新選取每個(gè)簇的中心點(diǎn)，即重新計(jì)算簇內(nèi)各點(diǎn)的平均值。
（4） 計(jì)算平方誤差和E，循環(huán)(1)，(2)，(3)直到準(zhǔn)則函數(shù)E變化不明顯為止。
3.1.2 PAM算法
PAM算法是一種以簇中位置最中心的對(duì)象為中心點(diǎn)的劃分方法［7］。中心點(diǎn)被稱為代表對(duì)象，其他對(duì)象被稱為非代表對(duì)象。算法基本思想：
（1） 隨機(jī)地選取k個(gè)對(duì)象，每個(gè)對(duì)象代表一個(gè)簇的初始中心點(diǎn)。
（2） 根據(jù)中心點(diǎn)計(jì)算每個(gè)非中心點(diǎn)y到中心點(diǎn)x的絕對(duì)距離|y－x|，將每個(gè)對(duì)象賦給與其絕對(duì)距離最小的簇，即最相似的簇。
（3） 選擇一個(gè)未被選過(guò)的中心點(diǎn)oi及oi所在簇中的一個(gè)未被選過(guò)的非中心點(diǎn)oh，計(jì)算oh代替oi的總代價(jià)Tcih，并記錄在S中。
（4） 如果S中有小于0的記錄，則找出S最小，記錄的非中心點(diǎn)，并用該非中心點(diǎn)代替被選擇的中心點(diǎn)，重新組建k個(gè)劃分的簇。
（5） 如果S中所有的記錄都大于等于0，則不再劃分新的簇。
總代價(jià)為：Tcih=∑n1cjhi 。 其中n為所有節(jié)點(diǎn)數(shù)；cjhi表示oj在oi被oh代替后所產(chǎn)生的代價(jià)。每一個(gè)oi被oh代替后，對(duì)于非中心點(diǎn)oj，有四種情況需要考慮(如┩1~圖4所示)。
（1）oj當(dāng)前在oi所在簇內(nèi)，但oh代替oi后，oj被劃分到了中心點(diǎn)om所在的簇。此時(shí)cjhi=d(j,m)－d(j,i)。
（2） oj當(dāng)前在oi所在簇內(nèi)，但oh代替oi后，oj被重新劃分到了中心點(diǎn)oh所在簇，此時(shí)cjhi=d(j,h)－d(j,i)。
（3） oj當(dāng)前在中心點(diǎn)om所在簇內(nèi)，但oh代替oi后，oj被重新劃分到了中心點(diǎn)oh所在簇，此時(shí)cjhi=d(j,h)－d(j,m)。
（4） oj當(dāng)前在中心點(diǎn)om所在簇內(nèi)，但oh代替oi后，oj仍在中心點(diǎn)om所在簇，此時(shí)cjhi=0。
圖中實(shí)線為oh代替oi前oj的所屬關(guān)系，虛線為代替后oj的所屬關(guān)系。
3.2 層次方法
層次方法是根據(jù)某種給定的條件對(duì)數(shù)據(jù)集進(jìn)行層次的分解，有凝聚和分裂2種方式［8］。
凝聚采用自底向上的策略，先將每個(gè)對(duì)象作為獨(dú)立的簇，然后合并各個(gè)簇，滿足用戶指定的終止條件時(shí)停止。凝聚方法有AGNES算法等。
分裂采用自頂向下的分類策略，先將所有對(duì)象作為一個(gè)簇，然后將該簇細(xì)分為越來(lái)越小的簇，滿足用戶指定的終止條件時(shí)停止。分裂方法有DIANA算法等。
3.2.1 AGNES算法
AGNES算法采用對(duì)象間的歐氏距離作為評(píng)價(jià)2個(gè)簇間距離的標(biāo)準(zhǔn)［9］。算法基本思想：
（1） 將每個(gè)對(duì)象作為獨(dú)立的初始簇。
（2） 將歐氏距離最小的2個(gè)對(duì)象所在簇進(jìn)行合并，組成一個(gè)新的簇。
（3） 達(dá)到用戶指定的簇的數(shù)目時(shí)終止。
3.2.2 DIANA算法
DIANA算法以簇的直徑和平均相異度為劃分層次的標(biāo)準(zhǔn)［10］。其中，簇的直徑是指簇中任意兩對(duì)象間的最大歐氏距離，平均相異度指平均距離：
ИИdavg(Ci,Cj)=∑x∈Ci∑x∈Cj|x-y|/(ninj)И
式中：ni是Cj中包含屬性的個(gè)數(shù);nj是Cj中包含屬性的個(gè)數(shù)。算法基本思想：
（1） 將所有對(duì)象作為一個(gè)整體劃分到同一個(gè)簇。
（2） 在所有簇中挑選出簇直徑最大的簇，并在該簇中選取一個(gè)與其他點(diǎn)平均相異度最大的點(diǎn)作為一個(gè)新簇，然后選取原簇中到新簇距離小于等于到原簇距離的點(diǎn)放入新簇中。
（3） 循環(huán)(2)直到滿足用戶指定簇的數(shù)目為止。
4 幾種算法的比較
關(guān)聯(lián)規(guī)則方法主要用于對(duì)事物數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)挖掘，在商業(yè)領(lǐng)域使用得相對(duì)頻繁一些。分類和聚類方法則用于對(duì)關(guān)系數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)挖掘，通過(guò)分析有屬性描述的數(shù)據(jù)庫(kù)元組來(lái)構(gòu)造模型。
在實(shí)際應(yīng)用過(guò)程中，不同方法有不同的優(yōu)點(diǎn)和缺點(diǎn)。下面對(duì)本文提出幾種算法的時(shí)間復(fù)雜度、使用范圍、依賴條件、誤差估計(jì)進(jìn)行比較，如表1所示。
表1 幾種算法比較
算法時(shí)間復(fù)雜度使用范圍依賴條件誤差估計(jì)
ApraoriO|Ck||Lk－1|k2小數(shù)據(jù)集最小支持度較小
kNNO(n)小數(shù)據(jù)集最臨近數(shù)目小
決策樹(shù)O(n×n)數(shù)據(jù)完整性較高的數(shù)據(jù)類別屬性較大且與評(píng)估函數(shù)有關(guān)
貝葉斯分類O(n×m)完全獨(dú)立數(shù)據(jù)和函數(shù)依賴數(shù)據(jù)先驗(yàn)概率較小
k-平均O(n×k×t)簇密集數(shù)據(jù)且簇平均值可計(jì)算簇的數(shù)目k較大且與孤立點(diǎn)的數(shù)目有關(guān)
PAMO(k×s×s+k(n－k))小數(shù)據(jù)集簇的數(shù)目k小
AGNESO(n×n)n較小的數(shù)據(jù)簇的數(shù)目k較小
DIANAO(n×n)n較小的數(shù)據(jù)簇的數(shù)目k較小
從表1可以看出，不同算法在不同應(yīng)用上有各自的優(yōu)缺點(diǎn)。如kNN算法時(shí)間復(fù)雜度最小，然而僅限于小數(shù)據(jù)集，對(duì)于數(shù)據(jù)集較大的情況，則可選用決策樹(shù)和貝葉斯分類；k-平均算法對(duì)簇密集型數(shù)據(jù)有很高的效率。在實(shí)際應(yīng)用中可以根據(jù)需要將幾種算法結(jié)合，以達(dá)到更高的效率。
5 結(jié) 語(yǔ)
數(shù)據(jù)挖掘使信息處理技術(shù)從簡(jiǎn)單的數(shù)據(jù)存儲(chǔ)轉(zhuǎn)入更為高級(jí)的知識(shí)發(fā)現(xiàn)階段，它正以一種全新的理念改變著人類信息管理方式。本文分析了3種數(shù)據(jù)挖掘算法的基本思想，并對(duì)不同算法進(jìn)行了比較，指出了各算法的優(yōu)缺點(diǎn)及使用范圍，并展望了各算法對(duì)不同特征數(shù)據(jù)集的應(yīng)用前景。
摘要：運(yùn)用粗糙集和遺傳算法的理論，為大型的數(shù)據(jù)挖掘提供了一種新的方法。首先通過(guò)粗糙集理論對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，然后對(duì)屬性簡(jiǎn)約，最后通過(guò)遺傳算法進(jìn)行規(guī)則提取，尋找最優(yōu)解。
關(guān)鍵詞：粗糙集；遺傳算法；數(shù)據(jù)挖掘；知識(shí)發(fā)現(xiàn)
數(shù)據(jù)挖掘[1]又稱知識(shí)發(fā)現(xiàn)，是從大量的、不完全的、有躁聲的、模糊的實(shí)際數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又很有用的知識(shí)和信息的過(guò)程。它的一般步驟如下：提出問(wèn)題->數(shù)據(jù)準(zhǔn)備->數(shù)據(jù)整理->建立模型->評(píng)價(jià)和解釋。它是數(shù)據(jù)庫(kù)研究、開(kāi)發(fā)和應(yīng)用最活躍的一個(gè)分支，是多學(xué)科的交叉領(lǐng)域，涉及數(shù)據(jù)庫(kù)技術(shù)、人工智能、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、數(shù)學(xué)、統(tǒng)計(jì)學(xué)、模式識(shí)別、知識(shí)庫(kù)系統(tǒng)、知識(shí)獲取、信息提取、高性能計(jì)算、并行計(jì)算、數(shù)據(jù)可視化等多方面的知識(shí)。
1 粗糙集與遺傳算法的基本概念
粗糙集(Rough Set, RS)[2]作為一種全新的數(shù)學(xué)概念,為處理具有不完整、不一致及不確定性特征的信息提供了新的有效工具,它的主要特點(diǎn)之一是無(wú)須提供問(wèn)題所需處理的數(shù)據(jù)集合之外的任何先驗(yàn)信息。相對(duì)于許多其他處理不確定知識(shí)的方法來(lái)說(shuō)更具客觀性,并且和其他分析方法有機(jī)結(jié)合,進(jìn)一步增強(qiáng)對(duì)不確定問(wèn)題的處理能力。
定義1：信息系統(tǒng)S可表示為S=(U,A,V,f),其中U是對(duì)象的非空有限集合,稱為論域;A是屬性的非空有限集合;V=∪a∈AVa,Va是屬性A的值域,f:U×AV是一個(gè)信息函數(shù),他為每個(gè)對(duì)象的每個(gè)屬性賦予一個(gè)信息值。
如果屬性集A可以分為條件屬性集C和決策屬性集D ,即C∪D = A ,C∩D =Ф,則該信息系統(tǒng)稱為決策系統(tǒng)或決策表,其中D 一般只含有一個(gè)屬性。
定義2：在知識(shí)表達(dá)系統(tǒng)S 中,對(duì)于一屬性集P∈A,對(duì)象x,y∈U,二元等價(jià)關(guān)系IND(P) ={(x,y)∈U×U | 所有的a∈P, f(x,a)=f(y,a)}稱為S 的不可分辨關(guān)系。不可分辨關(guān)系是一個(gè)等價(jià)關(guān)系,通過(guò)一個(gè)不可分辨關(guān)系,可以得到一個(gè)決策系統(tǒng)的劃分。
定義3：給定信息系統(tǒng)S=(U,A),B∈A ,對(duì)B中的屬性a,如果IND(B)≠I(mǎi)ND(B-{a}),則說(shuō)屬性a是必要的(Indispensable),否則稱a是不必要的(Dispensable)。
遺傳算法( Genetic Algorithm, GA)[3]起源于對(duì)生物系統(tǒng)進(jìn)行的計(jì)算機(jī)模擬研究，是模擬生物在環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)優(yōu)化概率搜索算法。它的流程主要模仿的 是生物遺傳進(jìn)化過(guò)程中的選擇、交叉和變異操作，從而完成對(duì)問(wèn)題最優(yōu)解的自適應(yīng)搜索過(guò)程。流程主要包括染色體編碼、產(chǎn)生初始群體、計(jì)算適應(yīng)度、進(jìn)化操作等幾大部分。
遺傳算法的搜索過(guò)程是從一群初始節(jié)點(diǎn)開(kāi)始搜索,而不是從單一的初始點(diǎn)開(kāi)始搜索,這種機(jī)制意味著搜索過(guò)程可以有效地跳出局部極值點(diǎn)。既可以完成極值點(diǎn)領(lǐng)域內(nèi)解的求精,也可以在整個(gè)問(wèn)題空間實(shí)施探索,得到問(wèn)題全局最優(yōu)解的概率大大提高。
2 粗糙集與遺傳算法在數(shù)據(jù)挖掘中的應(yīng)用
粗糙集算法與遺傳算法結(jié)合,能有效地提高挖掘效果,具有實(shí)際應(yīng)用的可行性。其基本思想是：首先通過(guò)粗糙集對(duì)信息表中的數(shù)據(jù)缺損進(jìn)行處理；然后對(duì)于信息表中的數(shù)據(jù)，根據(jù)已定義的可辯識(shí)距陣，通過(guò)屬性簡(jiǎn)約算法進(jìn)行屬性簡(jiǎn)約和知識(shí)發(fā)現(xiàn)；最后對(duì)知識(shí)發(fā)現(xiàn)的規(guī)則通過(guò)遺傳算法進(jìn)行優(yōu)化，找出最主要的規(guī)則。主要包括以下幾個(gè)方面：
2.1 數(shù)據(jù)預(yù)處理
數(shù)據(jù)預(yù)處理用于對(duì)原始數(shù)據(jù)的采樣、收集、整理，對(duì)于不同途徑獲取來(lái)的數(shù)據(jù)不一定能夠得到有效的信息，所以數(shù)據(jù)的預(yù)處理是非常必要的。包括連續(xù)屬性的離散化和不完備數(shù)據(jù)的填補(bǔ)，由于粗糙集只能處理離散的數(shù)據(jù)，所以還必須對(duì)連續(xù)的數(shù)據(jù)離散化，而屬性離散化的關(guān)鍵在于選取合適的斷點(diǎn)對(duì)條件屬性進(jìn)行劃分[4]，如可采用基于屬性重要性的離散化算法。由于數(shù)據(jù)采集的不完整性，使數(shù)據(jù)庫(kù)中很大一部分?jǐn)?shù)據(jù)都存在缺失，因此對(duì)輸入的數(shù)據(jù)必須進(jìn)行必要的處理如采用均值法、頻率統(tǒng)計(jì)法等對(duì)數(shù)據(jù)進(jìn)行補(bǔ)齊。
2.2 屬性簡(jiǎn)約
粗糙集處理決策表時(shí)，數(shù)據(jù)約簡(jiǎn)是核心內(nèi)容，一般是約去過(guò)剩的條件屬性，用最少的屬性區(qū)分不同的決策，提供同樣多的信息，使決策表的決策屬性和條件屬性的依賴關(guān)系不發(fā)生變化。簡(jiǎn)約后的屬性集稱為屬性的約簡(jiǎn)集，約簡(jiǎn)集通常不唯一，找到一個(gè)信息表中的約簡(jiǎn)集不是在一個(gè)多項(xiàng)式時(shí)間里能夠解決的問(wèn)題，求最小約簡(jiǎn)集（含屬性個(gè)數(shù)最少的約簡(jiǎn)集）同樣是一個(gè)困難的問(wèn)題，實(shí)際上它是一個(gè)NP-hard問(wèn)題，因此根據(jù)已定義的可辯識(shí)距陣，有如下的屬性簡(jiǎn)約算法：
① 計(jì)算屬性表的可辯識(shí)距陣。
② 對(duì)于可辯識(shí)距陣中的所有取值為非空集合的元素Cij建立相應(yīng)的析取邏輯表達(dá)式。
③ 將所有析取邏輯表達(dá)式進(jìn)行合取運(yùn)算，得到一個(gè)合取范式。
④ 將合取范式轉(zhuǎn)換為析取范式形式。
⑤ 輸出屬性約簡(jiǎn)結(jié)果，其中析取范式中的每個(gè)合取項(xiàng)對(duì)應(yīng)一個(gè)屬性約簡(jiǎn)的結(jié)果，每個(gè)合取項(xiàng)中所包含的屬性組成的約簡(jiǎn)后的條件屬性集合。
2.3 決策規(guī)則提取
經(jīng)過(guò)第二步屬性簡(jiǎn)約后，屬性個(gè)數(shù)減少了，但是得出的規(guī)則數(shù)量依然可能過(guò)多，不利于得到用戶最想要，最重要的規(guī)則，因此我們會(huì)更希望關(guān)心具有較多共同特性的規(guī)則，必須把簡(jiǎn)約后生成的規(guī)則集里那些具有大量共同特征的規(guī)則再次提取出來(lái)，面對(duì)這種優(yōu)化問(wèn)題，遺傳算法是個(gè)強(qiáng)有力的工具。其步驟是編碼產(chǎn)生原始種群，計(jì)算個(gè)體適應(yīng)度，選擇個(gè)體，交叉，變異操作，然后一代一代進(jìn)化最后找出最優(yōu)解。
（1）編碼，是進(jìn)行遺傳算法的重要步驟，編碼方案的選取很大程度上決定于問(wèn)題的性質(zhì)和要求，同時(shí)也決定了對(duì)隨后的遺傳算子的設(shè)計(jì)。如可以將數(shù)據(jù)離散化后的屬性值定義在2的n次方之間[5]，采用二進(jìn)制編碼方法對(duì)每個(gè)數(shù)字編碼，像屬性值3用編碼表示就是0011；
（2）產(chǎn)生初始種群。隨機(jī)選取一些個(gè)體作為初始種群；
（3）確定評(píng)價(jià)函數(shù)。數(shù)據(jù)挖掘的目的是挖掘出具有最多相同特征的規(guī)則，因此評(píng)價(jià)函數(shù)的選取時(shí)應(yīng)當(dāng)把能夠匹配簡(jiǎn)約表中最多的屬性的規(guī)則評(píng)價(jià)為最優(yōu)規(guī)則；
（4）遺傳操作。交叉操作是將規(guī)則編碼的某幾位互相置換，變異操作是將規(guī)則編碼的某些二進(jìn)制位按位取反。這樣通過(guò)規(guī)則集中任意的兩兩組合會(huì)形成新的規(guī)則集。然后經(jīng)過(guò)每個(gè)規(guī)則的評(píng)價(jià)函數(shù)確定當(dāng)前的最優(yōu)規(guī)則，這樣經(jīng)歷數(shù)代遺傳之后就可得到相對(duì)最優(yōu)的規(guī)則。
3 公司錄取情況數(shù)據(jù)挖掘應(yīng)用實(shí)例
下面用一個(gè)實(shí)例來(lái)說(shuō)明本文使用的數(shù)據(jù)挖掘方法。某公司每年都會(huì)收到大量的求職信息表，并從中雇用一定數(shù)量的員工，對(duì)于員工的雇用，公司以往都是通過(guò)面試及給領(lǐng)導(dǎo)的感覺(jué)來(lái)雇用的，因此公司希望能夠從以前的錄用中找出一個(gè)大體的評(píng)判標(biāo)準(zhǔn)以便于以后錄用時(shí)作為參考，由于以往幾年累計(jì)求職的員工太多，情況比較復(fù)雜，因此公司希望這個(gè)標(biāo)準(zhǔn)能夠簡(jiǎn)單明了。通過(guò)本文提出的方法，可以很好的解決該公司的需求，以下以該公司求職人員的原始求職表中的一部分作為演示，“?”代表求職表中該屬性沒(méi)有寫(xiě)明情況，如表1所示：
按屬性簡(jiǎn)約的算法，通過(guò)決策表的可辯識(shí)距陣，我們可以得到算法第3步后的合取范式為：
F(d,e,f,a)=(e∨a)∧(d∨e∨a) ∧(d∨e) ∧(e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨a) ∧(d∨e∨a) ∧(d∨e∨a) ∧(d∨a) ∧(e) ∧(e∨a) ∧(d∨e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨f∨a) ∧(d∨e∨f) ∧(d∨e∨a)
其中每一個(gè)析取項(xiàng)對(duì)應(yīng)于可辯識(shí)距陣中的一個(gè)元素，d，e，f，a分別對(duì)應(yīng)屬性學(xué)歷、經(jīng)驗(yàn)、法語(yǔ)、儀表，按算法第4步簡(jiǎn)化后可以得到F(d,e,f,a)=(e∧a) ∨(e∧d)。由此可見(jiàn)，在原始決策表給出的這部分信息中與決策有關(guān)的是d，e，a。
通過(guò)粗糙集的屬性約簡(jiǎn)，可以得到以往公司錄用時(shí)真正看重的一些屬性，通過(guò)這些屬性，再用遺傳算法找出其中最主要的規(guī)則。例如約簡(jiǎn)表中某一行在學(xué)歷、經(jīng)驗(yàn)、儀表上的值為201，則編碼就是10,00,01。隨機(jī)選取8個(gè)個(gè)體作為初始種群，評(píng)價(jià)函數(shù)以能夠匹配約簡(jiǎn)表中最多行屬性的規(guī)則成為當(dāng)代的最優(yōu)規(guī)則。
算法定義為一個(gè)8元組：
SGA=（C，E，P0，M，Ф，Г，Ψ，T）
C表示對(duì)個(gè)體采用二進(jìn)制編碼；E表示個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)f(x)；P0表示初始種群隨機(jī)選取的8個(gè)規(guī)則；Ф表示采用輪盤(pán)賭按比例選擇算子；Г表示中間位單點(diǎn)交叉算子；Ψ表示基本位變異算子；T表示執(zhí)行20代上述遺傳算法后停止。
最后得到最佳個(gè)體00,01,01，即學(xué)歷MBA，經(jīng)驗(yàn)水平一般，儀表良好的評(píng)判標(biāo)準(zhǔn)，凡在此標(biāo)準(zhǔn)附近或高于此標(biāo)準(zhǔn)的，可以考慮錄用。
4 結(jié)語(yǔ)
在數(shù)據(jù)挖掘中應(yīng)用粗糙集和遺傳算法，粗糙集可以解決數(shù)據(jù)不精確、不完整的問(wèn)題，并進(jìn)行屬性簡(jiǎn)約，遺傳算法可以從大量規(guī)則中提取出最優(yōu)的規(guī)則，提高了分析系統(tǒng)的效率。本文將粗糙集和遺傳算法在數(shù)據(jù)挖掘中相結(jié)合，給出實(shí)例說(shuō)明該方法的可行性。在今后的研究中還將繼續(xù)結(jié)合其他的方法進(jìn)行研究，提高對(duì)知識(shí)的發(fā)現(xiàn)能力。
摘要：數(shù)據(jù)挖掘技術(shù)是一個(gè)年輕且充滿希望的研究領(lǐng)域，商業(yè)利益的強(qiáng)大驅(qū)動(dòng)力將會(huì)不停地促進(jìn)它的發(fā)展。隨著數(shù)據(jù)庫(kù)應(yīng)用的不斷深化，數(shù)據(jù)庫(kù)的規(guī)模急劇膨脹，數(shù)據(jù)挖掘已成為當(dāng)今研究的熱點(diǎn)，每年都有新的數(shù)據(jù)挖掘方法和模型問(wèn)世，特別是其中的分類問(wèn)題，引起了越來(lái)越多的關(guān)注。
關(guān)鍵詞：數(shù)據(jù)挖掘；分類；算法
隨著計(jì)算機(jī)技術(shù)特別是數(shù)據(jù)庫(kù)技術(shù)的迅猛發(fā)展，以及人類活動(dòng)范圍的擴(kuò)展、生活節(jié)奏的加快，人們能以更快速更容易更廉價(jià)的方式獲取和存儲(chǔ)數(shù)據(jù)，這就使得數(shù)據(jù)及其信息量以指數(shù)方式增長(zhǎng)。面對(duì)這些極度膨脹的數(shù)據(jù)，人們受到“信息爆炸”和“數(shù)據(jù)過(guò)?！?Data Glut)的巨大壓力。這些海量數(shù)據(jù)如果不能有效利用起來(lái)，將只會(huì)成為“數(shù)據(jù)垃圾”。對(duì)人類社會(huì)進(jìn)步起到巨大作用的是知識(shí)。 數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在規(guī)律、提取有用知識(shí)的方法和技術(shù)[1]。數(shù)據(jù)挖掘包含的內(nèi)容很多，其中很重要的一個(gè)方面是分類規(guī)則挖掘。
分類技術(shù)在很多領(lǐng)域都有應(yīng)用，例如可以通過(guò)客戶分類構(gòu)造一個(gè)分類模型來(lái)對(duì)銀行貸款進(jìn)行風(fēng)險(xiǎn)評(píng)估；當(dāng)前的市場(chǎng)營(yíng)銷(xiāo)中很重要的一個(gè)特點(diǎn)是強(qiáng)調(diào)客戶細(xì)分?？蛻纛悇e分析的功能也在于此，采用數(shù)據(jù)挖掘中的分類技術(shù)，可以將客戶分成不同的類別，比如呼叫中心設(shè)計(jì)時(shí)可以分為：呼叫頻繁的客戶、偶然大量呼叫的客戶、穩(wěn)定呼叫的客戶、其他，幫助呼叫中心尋找出這些不同種類客戶之間的特征，這樣的分類模型可以讓用戶了解不同行為類別客戶的分布特征；其他分類應(yīng)用如文獻(xiàn)檢索和搜索引擎中的自動(dòng)文本分類技術(shù)；安全領(lǐng)域有基于分類技術(shù)的入侵檢測(cè)等等。機(jī)器學(xué)習(xí)、專家系統(tǒng)、統(tǒng)計(jì)學(xué)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域的研究人員已經(jīng)提出了許多具體的分類預(yù)測(cè)方法。下面對(duì)幾種主要的分類方法作簡(jiǎn)要的研究與探討：
1 基于判定樹(shù)的歸納分類
判定樹(shù)是一個(gè)類似流程圖的樹(shù)結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，而每個(gè)樹(shù)葉節(jié)點(diǎn)代表類或類分布。樹(shù)的最頂層節(jié)點(diǎn)是根節(jié)點(diǎn)。由判定樹(shù)可以很容易得到“IF-THEN”形式的分類規(guī)則。方法是沿著由根節(jié)點(diǎn)到樹(shù)葉節(jié)點(diǎn)的路徑，路徑上的每個(gè)屬性-值對(duì)形成“IF”部分的一個(gè)合取項(xiàng)，樹(shù)葉節(jié)點(diǎn)包含類預(yù)測(cè)，形成“THEN”部分。一條路徑創(chuàng)建一個(gè)規(guī)則。判定樹(shù)歸納的基本算法是貪心算法。
算法描述如下：判定樹(shù)歸納分類[2]是一種從訓(xùn)練樣本集中推理出判定樹(shù)表示形式的分類規(guī)則的方法。它采用自頂向下的遞歸方式，判定樹(shù)的最頂節(jié)點(diǎn)是根結(jié)點(diǎn)，樹(shù)的內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，從該結(jié)點(diǎn)向下的每個(gè)分支代表一個(gè)測(cè)試輸出，在樹(shù)的葉結(jié)點(diǎn)得到分類預(yù)測(cè)。從根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條合取規(guī)則，整棵判定樹(shù)就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則。判定樹(shù)的優(yōu)點(diǎn)在于它的直觀性和易理解性，判定樹(shù)方法不僅能做出分類和預(yù)測(cè)，而且它的生成過(guò)程、分類、預(yù)測(cè)以及從判定樹(shù)所提取的分類規(guī)則都具有很強(qiáng)的可理解性。
算法策略如下：①判定樹(shù)以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)開(kāi)始；②如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為樹(shù)葉，并用該類標(biāo)記；③否則，基于啟發(fā)式或統(tǒng)計(jì)式策略選擇能夠最好地將樣本分類的屬性，將樣本分類；④對(duì)測(cè)試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分枝，并以此為根據(jù)劃分樣本；⑤使用同樣的過(guò)程，遞歸地形成每個(gè)劃分上的樣本判定樹(shù)。
停止劃分的條件：給定節(jié)點(diǎn)的所有樣本屬于同一類：沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本，此時(shí)使用多數(shù)表決(用訓(xùn)練集中的多數(shù)所在的類標(biāo)記它)；沒(méi)有樣本剩余。
2 KNN法(K-Nearest Neighbor)
KNN(K Nearest Neighbors)算法[3]又叫K最臨近方法，總體來(lái)說(shuō)KNN算法是相對(duì)比較容易理解的算法之一，假設(shè)每一個(gè)類包含多個(gè)樣本數(shù)據(jù)，而且每個(gè)數(shù)據(jù)都有一個(gè)唯一的類標(biāo)記表示這些樣本是屬于哪一個(gè)分類，KNN就是計(jì)算每個(gè)樣本數(shù)據(jù)到待分類數(shù)據(jù)的距離，取和待分類數(shù)據(jù)最近的K各樣本數(shù)據(jù)，那么這個(gè)K個(gè)樣本數(shù)據(jù)中哪個(gè)類別的樣本數(shù)據(jù)占多數(shù)，則待分類數(shù)據(jù)就屬于該類別。
KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本的不平衡問(wèn)題。另外，由于KNN方法主要靠周?chē)邢薜泥徑臉颖?，而不是靠判別類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。
該方法的不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。另外還有一種Reverse KNN法，能降低KNN算法的計(jì)算復(fù)雜度，提高分類的效率。
該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。
3 VSM法
VSM法即向量空間模型(Vector Space Model)法，由Salton等人于60年代末提出。這是最早也是最出名的信息檢索方面的數(shù)學(xué)模型。其基本思想是將文檔表示為加權(quán)的特征向量：D=D(T1,W1;T2,W2;…;Tn,Wn)，然后通過(guò)計(jì)算文本相似度的方法來(lái)確定待分樣本的類別。當(dāng)文本被表示為空間向量模型的時(shí)候，文本的相似度就可以借助特征向量之間的內(nèi)積來(lái)表示。
在實(shí)際應(yīng)用中，VSM法一般事先依據(jù)語(yǔ)料庫(kù)中的訓(xùn)練樣本和分類體系建立類別向量空間。當(dāng)需要對(duì)一篇待分樣本進(jìn)行分類的時(shí)候，只需要計(jì)算待分樣本和每一個(gè)類別向量的相似度即內(nèi)積，然后選取相似度最大的類別作為該待分樣本所對(duì)應(yīng)的類別。
由于VSM法中需要事先計(jì)算類別的空間向量，而該空間向量的建立又很大程度的依賴于該類別向量中所包含的特征項(xiàng)。根據(jù)研究發(fā)現(xiàn)，類別中所包含的非零特征項(xiàng)越多，其包含的每個(gè)特征項(xiàng)對(duì)于類別的表達(dá)能力越弱。因此，VSM法相對(duì)其他分類方法而言，更適合于專業(yè)文獻(xiàn)的分類。
4 Bayes法
Bayes法是一種在已知先驗(yàn)概率與類條件概率的情況下的模式分類方法，待分樣本的分類結(jié)果取決于各類域中樣本的全體。
設(shè)訓(xùn)練樣本集分為M類，記為C={c1,…,ci,…cM}，每類的先驗(yàn)概率為P(ci)，i=1,2,…,M。當(dāng)樣本集非常大時(shí)，可以認(rèn)為P(ci)=ci類樣本數(shù)/總樣本數(shù)。對(duì)于一個(gè)待分樣本X，其歸于cj類的類條件概率是P(X/ci)，則根據(jù)Bayes定理，可得到cj類的后驗(yàn)概率P(ci/X)：
P(ci/x)=P(x/ci)?P(ci)/P(x) （1）
若 P(ci/X)=MaxjP(cj/X)，i=1,2,…,M，j=1,2,…,M，則有x∈ci（2）
（2）式是最大后驗(yàn)概率判決準(zhǔn)則，將（1）式代入（2）式，則有：
若P(x/ci)P(ci)=Maxj[P(x/cj)P(cj)]，i=1,2,…,M,j=1,2,…,M，則x∈ci，這就是常用到的Bayes分類判決準(zhǔn)則。經(jīng)過(guò)長(zhǎng)期的研究，Bayes分類方法在理論上論證得比較充分，在應(yīng)用上也是非常廣泛的。
Bayes方法的薄弱環(huán)節(jié)在于實(shí)際情況下，類別總體的概率分布和各類樣本的概率分布函數(shù)(或密度函數(shù))常常是不知道的。為了獲得它們，就要求樣本足夠大。另外，Bayes法要求表達(dá)文本的主題詞相互獨(dú)立，這樣的條件在實(shí)際文本中一般很難滿足，因此該方法往往在效果上難以達(dá)到理論上的最大值。
5 神經(jīng)網(wǎng)絡(luò)
人工神經(jīng)網(wǎng)絡(luò)的研究至今已有60多年的歷史。1943年，心理學(xué)家McCulloch和數(shù)學(xué)家Pitts合作，提出了形式神經(jīng)元的數(shù)學(xué)模型，即MP模型[4]，從此，神經(jīng)網(wǎng)絡(luò)引起了許多科學(xué)家的興趣。但隨著對(duì)感知機(jī)為代表的神經(jīng)網(wǎng)絡(luò)的功能和局限性的深入分析等原因，使神經(jīng)網(wǎng)絡(luò)的研究陷入低潮。但是仍有一些學(xué)者堅(jiān)持研究，并取得了一些成果，出現(xiàn)了Grossberg的ART模型和Kohonen的SOM模型。1982年，通過(guò)引入能量函數(shù)的概念，Hopfied研究了網(wǎng)絡(luò)的動(dòng)力學(xué)性質(zhì)，并用電子線路設(shè)計(jì)出相應(yīng)的網(wǎng)絡(luò)，進(jìn)而掀起了神經(jīng)網(wǎng)絡(luò)新的研究高潮。1986年，Rumellhart和McCllel-land等提出了PDP理論，尤其是發(fā)展了多層前向網(wǎng)絡(luò)的BP算法，成為迄今應(yīng)用最普遍的學(xué)習(xí)算法。
神經(jīng)網(wǎng)絡(luò)可解決目前數(shù)據(jù)挖掘存在幾個(gè)方面的問(wèn)題：
1) 數(shù)據(jù)的量度和維度，面對(duì)大量復(fù)雜、非線性、時(shí)序性與噪音普遍存在的數(shù)據(jù)；
2) 數(shù)據(jù)分析的目標(biāo)具有多樣性，使其在表述和處理上都涉及到領(lǐng)域知識(shí)；
3) 在復(fù)雜目標(biāo)下，對(duì)海量數(shù)據(jù)集的分析，目前還沒(méi)有現(xiàn)成的且滿足可計(jì)算條件的一般性理論的方法。然而，神經(jīng)網(wǎng)絡(luò)在對(duì)噪聲數(shù)據(jù)的高承受能力以及對(duì)未經(jīng)訓(xùn)練的數(shù)據(jù)分類模式的能力方面有很大優(yōu)勢(shì)。因此設(shè)計(jì)出基于神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)挖掘方法，并將其用于真實(shí)世界問(wèn)題，是可行且也是必要的。
人工神經(jīng)網(wǎng)絡(luò)可用于數(shù)據(jù)挖掘的分類、聚類、特征挖掘、預(yù)測(cè)和模式識(shí)別等方面，因此，人工神經(jīng)網(wǎng)絡(luò)在數(shù)據(jù)挖掘中占有舉足輕重的作用。
總之，數(shù)據(jù)挖掘技術(shù)是一個(gè)年輕且充滿希望的研究領(lǐng)域，商業(yè)利益的強(qiáng)大驅(qū)動(dòng)力將會(huì)不停地促進(jìn)它的發(fā)展。每年都有新的數(shù)據(jù)挖掘方法和模型問(wèn)世，人們對(duì)它的研究正日益廣泛和深入。盡管如此，數(shù)據(jù)挖掘技術(shù)仍然面臨著許多問(wèn)題和挑戰(zhàn)：如數(shù)據(jù)挖掘方法的效率亟待提高，尤其是超大規(guī)模數(shù)據(jù)集中數(shù)據(jù)挖掘的效率；開(kāi)發(fā)適應(yīng)多數(shù)據(jù)類型、容噪的挖掘方法，以解決異質(zhì)數(shù)據(jù)集的數(shù)據(jù)挖掘問(wèn)題；動(dòng)態(tài)數(shù)據(jù)和知識(shí)的數(shù)據(jù)挖掘；網(wǎng)絡(luò)與分布式環(huán)境下的數(shù)據(jù)挖掘等；另外，近年來(lái)多媒體數(shù)據(jù)庫(kù)發(fā)展很快，面向多媒體數(shù)據(jù)庫(kù)的挖掘技術(shù)和軟件今后將成為研究開(kāi)發(fā)的熱點(diǎn)。
摘要:數(shù)據(jù)挖掘是目前非常熱門(mén)的一門(mén)交叉學(xué)科,涉及到很多學(xué)科的研究領(lǐng)域。文中對(duì)數(shù)據(jù)挖掘的概念、實(shí)施步驟及各種算法進(jìn)行了比較詳細(xì)的歸納,并且對(duì)數(shù)據(jù)挖掘技術(shù)將來(lái)的研究方向也進(jìn)行了預(yù)測(cè)。
關(guān)鍵詞:數(shù)據(jù)挖掘;聚類算法;關(guān)聯(lián)規(guī)則;決策樹(shù);遺傳算法
1 引言
數(shù)據(jù)挖掘是一個(gè)多學(xué)科的交叉領(lǐng)域,這些學(xué)科包括數(shù)據(jù)庫(kù)技術(shù)、機(jī)器學(xué)習(xí)、統(tǒng)計(jì)學(xué)、模式識(shí)別、信息檢索、神經(jīng)網(wǎng)絡(luò)、基于知識(shí)的系統(tǒng)、人工智能、高性能計(jì)算和數(shù)據(jù)可視化等[1]。目前,對(duì)于數(shù)據(jù)挖掘方面的研究已經(jīng)取得了很大的進(jìn)展,開(kāi)發(fā)出了許多新的數(shù)據(jù)挖掘算法、系統(tǒng)和應(yīng)用。本文將先對(duì)數(shù)據(jù)挖掘的概念及實(shí)施步驟進(jìn)行說(shuō)明,然后將分類歸納數(shù)據(jù)挖掘中的各種常見(jiàn)算法,最后對(duì)數(shù)據(jù)挖掘目前的研究方向進(jìn)行預(yù)測(cè)。
2 數(shù)據(jù)挖掘的概念及流程
2.1 數(shù)據(jù)挖掘的概念
簡(jiǎn)單地說(shuō),數(shù)據(jù)挖掘就是從大量的數(shù)據(jù)中“挖掘”知識(shí),即從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中,提取隱含在其中的、人們事先不知道、但又是潛在有用的信息和知識(shí)的過(guò)程。它是一種決策支持過(guò)程,可以從企業(yè)數(shù)據(jù)庫(kù)的大量數(shù)據(jù)中,挖掘出潛在的模式,預(yù)測(cè)客戶的行為,幫助企業(yè)的決策者做出正確的判斷,從而減少投資的風(fēng)險(xiǎn),獲得更大的利潤(rùn)。
2.2 數(shù)據(jù)挖掘的流程
一般來(lái)講,數(shù)據(jù)挖掘的整個(gè)過(guò)程由五個(gè)步驟組成:
1) 數(shù)據(jù)挖掘的最后結(jié)果是不可預(yù)測(cè)的,但是要探索的問(wèn)題應(yīng)該是有預(yù)見(jiàn)的,為了數(shù)據(jù)挖掘而進(jìn)行數(shù)據(jù)挖掘,是不可取的。因此,清晰地定義出業(yè)務(wù)問(wèn)題,認(rèn)清數(shù)據(jù)挖掘的目的是數(shù)據(jù)挖掘的第一步,也是很重要的一步。
2) 數(shù)據(jù)準(zhǔn)備[2],數(shù)據(jù)準(zhǔn)備又可以分成數(shù)據(jù)選擇,數(shù)據(jù)預(yù)處理,數(shù)據(jù)轉(zhuǎn)化三個(gè)步驟。數(shù)據(jù)選擇,是從大量與業(yè)務(wù)對(duì)象有關(guān)的數(shù)據(jù)中選擇出適合進(jìn)行數(shù)據(jù)挖掘的數(shù)據(jù);數(shù)據(jù)預(yù)處理,包括進(jìn)行數(shù)據(jù)清洗,數(shù)據(jù)推測(cè),數(shù)據(jù)轉(zhuǎn)換等。數(shù)據(jù)清洗,指的是清除掉一些明顯的噪聲數(shù)據(jù),提高數(shù)據(jù)的質(zhì)量;數(shù)據(jù)推測(cè),是因?yàn)樵谇懊鎯刹街?也許會(huì)出現(xiàn)數(shù)據(jù)不全的情形,所以進(jìn)行適當(dāng)?shù)耐扑?補(bǔ)齊所需的數(shù)據(jù);數(shù)據(jù)轉(zhuǎn)換,是將數(shù)據(jù)轉(zhuǎn)換成一個(gè)分析模型,這個(gè)分析模型是針對(duì)數(shù)據(jù)挖掘算法建立的,建立一個(gè)真正適合挖掘算法的分析模型是數(shù)據(jù)挖掘成功的關(guān)鍵;數(shù)據(jù)轉(zhuǎn)化,則是在做完前面的步驟以后,適當(dāng)?shù)目s減即將進(jìn)行分析的數(shù)據(jù)庫(kù)規(guī)模,以上這些工作會(huì)直接影響到數(shù)據(jù)挖掘時(shí)的效率和準(zhǔn)確性,同樣很重要。
3) 數(shù)據(jù)挖掘,這是整個(gè)數(shù)據(jù)挖掘過(guò)程中最重要的一步,即使用適當(dāng)?shù)臄?shù)據(jù)挖掘算法對(duì)剛才處理出的數(shù)據(jù)進(jìn)行分析,進(jìn)而得到可能的模式模型。根據(jù)不同數(shù)據(jù)的特點(diǎn)以及用戶不同的需求,對(duì)同樣的任務(wù),可以選用不同的算法,目前常見(jiàn)的算法包括聚類算法、關(guān)聯(lián)分析、分類算法、遺傳算法等。
4) 結(jié)果評(píng)價(jià),通過(guò)上述步驟得到的模式模型,并不一定是真實(shí)有效的,甚至可能會(huì)是和實(shí)際情況完全相反的,所以還需要對(duì)得到的結(jié)果進(jìn)行評(píng)價(jià)。這一步使用的方法包括用數(shù)據(jù)代入進(jìn)行驗(yàn)證,也可以根據(jù)常規(guī)的經(jīng)驗(yàn)進(jìn)行一些判斷,一般由數(shù)據(jù)挖掘具體操作而定。如果沒(méi)有得到合適的模式模型,就需要重新選擇數(shù)據(jù),甚至需要選用其他的數(shù)據(jù)挖掘算法,因此,數(shù)據(jù)挖掘的過(guò)程往往都是一個(gè)不斷反復(fù)的過(guò)程。
5) 知識(shí)同化,完成上述步驟后,如果得到了可以接受的模式模型,就需要進(jìn)一步把得出的模型形象化,運(yùn)用到所需的信息系統(tǒng)中去。
3 數(shù)據(jù)挖掘的常見(jiàn)算法
數(shù)據(jù)挖掘常用的分析方法包括聚類算法(Cluster Algorithm)、關(guān)聯(lián)規(guī)則(Association Rules)、決策樹(shù)算法(Decision Tree Algorithm)、遺傳算法(Genetic Algorithm)等。
3.1 聚類算法
聚類是一種常見(jiàn)的數(shù)據(jù)分析工具,其目的是把大量數(shù)據(jù)點(diǎn)的集合分成若干類,使得每個(gè)類中的數(shù)據(jù)之間最大程度的相似,而不同類中的數(shù)據(jù)最大程度的不同。常見(jiàn)的聚類算法主要包括層次聚類算法(Hierarchical Clustering Method)、分割聚類算法 (Partitioning Clustering Method)、基于密度的方法(Density-Based Methods)、基于網(wǎng)格的方法(Grid-Based Methods)等[3]。
1) 層次聚類算法,是通過(guò)將給定的數(shù)據(jù)集組織成若干組數(shù)據(jù),并形成一個(gè)相應(yīng)的樹(shù)狀圖,進(jìn)行層次式的分解,直到某種條件滿足為止,具體又可分為“自底向上”和“自頂向下”兩種算法[4]。這兩種算法的思路正好相反,前者是將每個(gè)對(duì)象都作為一個(gè)原子聚類,再進(jìn)行聚合,最后得到相應(yīng)的結(jié)果,而后者是將所有對(duì)象看成一個(gè)聚類,再進(jìn)行分解。CURE算法、CHAMELEON算法、BIRCH算法等是比較常用的層次聚類算法。
2) 分割聚類算法,是先將數(shù)據(jù)集分成k個(gè)分組,每一個(gè)分組就代表一個(gè)聚類,然后從這k個(gè)初始分組開(kāi)始,然后通過(guò)反復(fù)迭代的方法改變分組,使得每一次改進(jìn)之后的分組方案都較前一次好,最終使同一分組中的記錄越來(lái)越近,不同分組中的記錄原來(lái)越遠(yuǎn),從而得到最優(yōu)解。使用這一思想的主要算法有K-means算法、K-medoids算法、CLARANS算法等。
3) 基于密度的方法與其它方法的最要區(qū)別在于:它不基于各種距離,而是從數(shù)據(jù)對(duì)象的分布密度出發(fā),將密度足夠大的相鄰區(qū)域連接起來(lái),從而可以發(fā)現(xiàn)具有任意形狀的聚類,并能有效處理異常數(shù)據(jù),它的代表算法有DBSCAN算法、OPTICS算法、DENCLUE算法等。
4) 基于網(wǎng)格的方法則是從對(duì)數(shù)據(jù)空間劃分的角度出發(fā),利用屬性空間的多維網(wǎng)格數(shù)據(jù)結(jié)構(gòu),將數(shù)據(jù)空間劃分為有限空間的單元,以構(gòu)成一個(gè)可以進(jìn)行聚類分析的網(wǎng)格結(jié)構(gòu)。該方法的主要特點(diǎn)是處理時(shí)間與數(shù)據(jù)對(duì)象的數(shù)目無(wú)關(guān),但與每維空間劃分的單元數(shù)相關(guān),而且,這種方法還與數(shù)據(jù)的輸入順序無(wú)關(guān),可以處理任意類型的數(shù)據(jù),但是聚類的質(zhì)量和準(zhǔn)確性降低了,它的代表算法有STING算法[5]和CLIQUE算法等。
3.2 關(guān)聯(lián)規(guī)則
關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘研究的重要內(nèi)容,它描述了數(shù)據(jù)庫(kù)中一組對(duì)象與另一組對(duì)象之間存在的某種關(guān)聯(lián)關(guān)系。從大量商業(yè)記錄中挖掘有趣的關(guān)聯(lián)關(guān)系,有助于許多商務(wù)決策的制定,如分類設(shè)計(jì)、交叉購(gòu)物等。關(guān)聯(lián)規(guī)則是形如A=>B的蘊(yùn)涵式,表示形式如pen=>ruler [支持度=20%,置信度=60%],支持度和置信度分別反映規(guī)則的有用性和確定性,這條規(guī)則就意味著所有的顧客中有20%的人同時(shí)購(gòu)買(mǎi)了鋼筆和直尺,而買(mǎi)了鋼筆的顧客的60%也買(mǎi)了直尺。在關(guān)聯(lián)規(guī)則中,所有支持度大于最小支持度的項(xiàng)集稱為頻繁項(xiàng)集,簡(jiǎn)稱頻集。如果一條關(guān)聯(lián)規(guī)則同時(shí)滿足最小支持度閾值和最小置信度閾值,就認(rèn)為它是有趣的,并稱為強(qiáng)關(guān)聯(lián)規(guī)則。
關(guān)聯(lián)規(guī)則挖掘一般分為兩步:1) 找出所有頻繁項(xiàng)集,即滿足最小支持度的項(xiàng)集;2) 從頻繁項(xiàng)集中產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。最為著名的關(guān)聯(lián)規(guī)則挖掘算法就是R.Agrawal和R.Srikant于1994年提出的挖掘布爾關(guān)聯(lián)規(guī)則中頻繁項(xiàng)集的原創(chuàng)性算法Apriori。它使用一種稱作逐層搜索的迭代方法,k項(xiàng)集用于探索(k+1)項(xiàng)集。首先,通過(guò)掃描數(shù)據(jù)庫(kù),累積每個(gè)項(xiàng)的計(jì)數(shù),并收集滿足最小支持度的項(xiàng),找出頻繁1項(xiàng)集的集合。該集合記作L1。然后,L1用于找頻繁2項(xiàng)集的集合L2,L2用于找L3,如此下去,直到不能找到頻繁k項(xiàng)集。找每個(gè)Lk需要一次數(shù)據(jù)庫(kù)全掃描。
但是,Apriori算法也有其不足之處:1) 可能產(chǎn)生大量的候選集;2) 生成每個(gè)Lk都需要重復(fù)掃描數(shù)據(jù)庫(kù)。后來(lái),陸續(xù)出現(xiàn)了一系列Apriori算法的改進(jìn)算法,以及其他的關(guān)聯(lián)規(guī)則挖掘算法,比如RIApriori算法、Apriori-improve算法、FP-growth算法等,這大大提高了關(guān)聯(lián)規(guī)則挖掘的速度和準(zhǔn)確性,也推動(dòng)了關(guān)聯(lián)規(guī)則挖掘理論的進(jìn)一步發(fā)展。
3.3 決策樹(shù)算法
決策樹(shù)是一種類似于流程圖的樹(shù)結(jié)構(gòu),每個(gè)內(nèi)部節(jié)點(diǎn)(非樹(shù)葉節(jié)點(diǎn))表示在一個(gè)屬性上測(cè)試,每個(gè)分支代表一個(gè)測(cè)試輸出,而每個(gè)樹(shù)葉節(jié)點(diǎn)(或終節(jié)點(diǎn))存放一個(gè)類標(biāo)號(hào)。決策樹(shù)算法主要圍繞決策樹(shù)的兩個(gè)階段展開(kāi):第一階段,決策樹(shù)的構(gòu)建,通過(guò)遞歸的算法將訓(xùn)練集生成一棵決策樹(shù);第二階段,由測(cè)試數(shù)據(jù)檢驗(yàn)生成的決策樹(shù),消除由于統(tǒng)計(jì)噪聲或數(shù)據(jù)波動(dòng)對(duì)決策樹(shù)的影響,來(lái)達(dá)到凈化樹(shù)的目的,得到一棵正確的決策樹(shù)。常見(jiàn)的決策樹(shù)算法主要有ID3算法[6]、C4.5算法、CART算法、SPRINT算法等。
3.4 遺傳算法
遺傳算法是基于進(jìn)化理論,并采用遺傳結(jié)合,遺傳變異,自然選擇等設(shè)計(jì)方法的一種進(jìn)化計(jì)算算法的優(yōu)化算法。進(jìn)化計(jì)算算法的基礎(chǔ)是生物進(jìn)化,隨著時(shí)間的流逝,進(jìn)化出更好的或更適應(yīng)的個(gè)體。在數(shù)據(jù)挖掘中,遺傳算法可以用于評(píng)估聚類、關(guān)聯(lián)規(guī)則等算法的適合度。在應(yīng)用遺傳算法解決問(wèn)題時(shí),最困難的一步應(yīng)該是怎樣將問(wèn)題建模成一組個(gè)體的集合,然后在計(jì)算中,首先假設(shè)一個(gè)初始模型,然后對(duì)其反復(fù)進(jìn)行雜交技術(shù)和變異技術(shù)的算法,最后用適應(yīng)度函數(shù)確定初始集合中應(yīng)該保留的那個(gè)最優(yōu)個(gè)體。這個(gè)算法的優(yōu)點(diǎn)在于容易并行化,但是對(duì)問(wèn)題進(jìn)行建模很困難,雜交變異過(guò)程以及適應(yīng)度函數(shù)也很難確定。
4 結(jié)束語(yǔ)
隨著數(shù)據(jù)量的積累和數(shù)據(jù)庫(kù)種類的多樣化,數(shù)據(jù)挖掘的應(yīng)用前景非常的廣闊,從上面對(duì)各種常見(jiàn)算法的歸納可以看出,每種算法都有局限性,很難采用單一的方法解決相應(yīng)的問(wèn)題,因此,多方法融合將成為數(shù)據(jù)挖掘未來(lái)的發(fā)展趨勢(shì)。
摘要:計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展迅速,網(wǎng)絡(luò)數(shù)據(jù)挖掘已經(jīng)成為一個(gè)重要的研究領(lǐng)域。網(wǎng)絡(luò)數(shù)據(jù)分布范圍廣,數(shù)據(jù)量大,結(jié)構(gòu)多樣,時(shí)間跨度高。如何對(duì)這些海量數(shù)據(jù)進(jìn)行高效查詢成為研究人員關(guān)注的問(wèn)題。遺傳算法在搜索的過(guò)程中采用群體搜索方式,有利于得到最優(yōu)查詢結(jié)果。在數(shù)據(jù)查詢、查詢優(yōu)化和分布式數(shù)據(jù)挖掘等方面使用遺傳算法,能夠從不同角度大大提高查詢效果。
關(guān)鍵詞:網(wǎng)絡(luò)數(shù)據(jù)挖掘;遺傳算法;查詢優(yōu)化
隨著萬(wàn)維網(wǎng)使用越來(lái)越廣泛,網(wǎng)絡(luò)數(shù)據(jù)挖掘已成為一個(gè)重要的科學(xué)研究領(lǐng)域,得到越來(lái)越多的科研人員的重視。設(shè)計(jì)算法從已有信息中發(fā)掘新知識(shí),根據(jù)用戶情況定制信息,學(xué)習(xí)用戶行為是網(wǎng)絡(luò)數(shù)據(jù)挖掘所面臨的主要問(wèn)題。
在網(wǎng)絡(luò)工具中結(jié)合使用人工智能可消除網(wǎng)絡(luò)檢索中的人為因素。在客戶端和服務(wù)器端分別安裝智能系統(tǒng),使計(jì)算機(jī)通過(guò)Internet在Web服務(wù)器上進(jìn)行高效的知識(shí)發(fā)掘。通過(guò)網(wǎng)絡(luò)服務(wù)器檢索知識(shí)已經(jīng)引起機(jī)器學(xué)習(xí)、人工智能等領(lǐng)域?qū)W者的普遍注意。然而,網(wǎng)絡(luò)數(shù)據(jù)數(shù)量大、分布地域廣泛、類型差異大,要開(kāi)發(fā)一個(gè)智能工具對(duì)這樣的數(shù)據(jù)進(jìn)行檢索難度很大。
網(wǎng)絡(luò)挖掘技術(shù)在智能網(wǎng)絡(luò)的發(fā)展中發(fā)揮著重要的作用。網(wǎng)絡(luò)數(shù)據(jù)具有多樣性、分布廣泛等特點(diǎn),按照現(xiàn)有的算法對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行搜索具有相當(dāng)局限性。與其他傳統(tǒng)的優(yōu)化算法相比,遺傳算法在搜索的過(guò)程中采用群體搜索方式,有利于達(dá)到全局最優(yōu)。遺傳算法可采用和進(jìn)化出更優(yōu)的復(fù)合目標(biāo)函數(shù),以便在動(dòng)態(tài)而負(fù)責(zé)的網(wǎng)絡(luò)環(huán)境中實(shí)現(xiàn)高效的數(shù)據(jù)檢索和知識(shí)預(yù)測(cè)。A.Broder等人將網(wǎng)絡(luò)看作是一個(gè)由無(wú)數(shù)網(wǎng)頁(yè)組成的集合S,這些網(wǎng)頁(yè)構(gòu)成鄰接關(guān)系,使用適應(yīng)性函數(shù)f實(shí)現(xiàn)對(duì)這些網(wǎng)頁(yè)的評(píng)估[1]。
f:SR+
搜索引擎通過(guò)f函數(shù)的最優(yōu)值輸出搜索結(jié)果。通過(guò)激活基于遺傳算法的應(yīng)用來(lái)使這網(wǎng)絡(luò)關(guān)聯(lián)的搜索更加高效。在本文第二節(jié)中主要對(duì)網(wǎng)絡(luò)數(shù)據(jù)挖掘進(jìn)行討論,第三節(jié)介紹在網(wǎng)絡(luò)數(shù)據(jù)挖掘中使用遺傳算法的案例。
1 網(wǎng)絡(luò)數(shù)據(jù)挖掘
1.1 網(wǎng)絡(luò)數(shù)據(jù)的特點(diǎn)
S. Chakrabarti.指出網(wǎng)絡(luò)數(shù)據(jù)挖掘即是指在萬(wàn)維網(wǎng)中應(yīng)用數(shù)據(jù)挖掘技術(shù)來(lái)提取人們感興趣的模式和知識(shí)[2]。網(wǎng)絡(luò)數(shù)據(jù)挖掘由于網(wǎng)絡(luò)的自身特點(diǎn)已經(jīng)成為一個(gè)獨(dú)立而重要的研究方向。對(duì)于網(wǎng)絡(luò)數(shù)據(jù)的特點(diǎn)可做以下歸納:未經(jīng)分類,海量,分布性廣泛,多種媒體類型并存,半結(jié)構(gòu)化,時(shí)間跨度大,維度高。
本文用圖1表示網(wǎng)絡(luò)。
在圖1中,結(jié)點(diǎn)表示網(wǎng)頁(yè),有向邊表示超鏈接,這些超鏈接包含了重要的信息,有助于實(shí)現(xiàn)信息的高效檢索。例如,在圖1中,許多結(jié)點(diǎn)的鏈接都指向A結(jié)點(diǎn),這就表明,結(jié)點(diǎn)A所代表的頁(yè)面很可能是某些領(lǐng)域的權(quán)威[3]。通常情況下,一個(gè)網(wǎng)站被描述成若干網(wǎng)頁(yè)的集合,在這個(gè)集合中,每個(gè)成員包含的對(duì)其他成員的連接數(shù)遠(yuǎn)多于外部網(wǎng)頁(yè)。
按照網(wǎng)絡(luò)數(shù)據(jù)挖掘的深度層次,可以將網(wǎng)絡(luò)數(shù)據(jù)挖掘歸為以下幾類:
1)基于內(nèi)容的數(shù)據(jù)挖掘:這種數(shù)據(jù)挖掘方式首先會(huì)對(duì)頁(yè)面中涉及的內(nèi)容進(jìn)行歸納總結(jié),生成摘要。而頁(yè)面的內(nèi)容種類很多,諸如文本、圖片、HTML代碼到圖和表等,根據(jù)這些內(nèi)容對(duì)網(wǎng)頁(yè)進(jìn)行分類,然后設(shè)計(jì)相應(yīng)的算法對(duì)這些網(wǎng)頁(yè)進(jìn)行檢索。對(duì)搜索結(jié)果進(jìn)行數(shù)據(jù)挖掘同樣是網(wǎng)絡(luò)內(nèi)容挖掘的一個(gè)組成部分。其中包括了對(duì)結(jié)果進(jìn)行總結(jié),將他們按照層次、標(biāo)題和摘要中的短語(yǔ)對(duì)文檔進(jìn)行歸類,以及對(duì)多個(gè)搜索引擎的搜索結(jié)果進(jìn)行合成和重組。最后將對(duì)數(shù)據(jù)進(jìn)行元數(shù)據(jù)挖掘。在信息檢索、文本挖掘、圖像挖掘和自然語(yǔ)言處理等方面的應(yīng)用都屬于這些類型。
2)基于網(wǎng)絡(luò)信息結(jié)構(gòu)的數(shù)據(jù)挖掘:這種挖掘方式涉及到通過(guò)萬(wàn)維網(wǎng)中文檔之間的超鏈接來(lái)提取知識(shí),這一做法往往能夠發(fā)現(xiàn)諸多網(wǎng)頁(yè)中某方面主題的權(quán)威頁(yè)面。結(jié)構(gòu)挖掘方面的重要應(yīng)用包括了查找重要的頁(yè)面、關(guān)聯(lián)頁(yè)面和主頁(yè),識(shí)別重要的模式和它們之間的相互關(guān)系。然而,網(wǎng)頁(yè)的信息不單單來(lái)自于這個(gè)頁(yè)面本身所含的內(nèi)容,還來(lái)自于其相鄰的頁(yè)面。在這里同時(shí)使用基于內(nèi)容的挖掘和基于結(jié)構(gòu)的挖掘可以達(dá)到效果互補(bǔ)的目的。
3)基于網(wǎng)絡(luò)數(shù)據(jù)用途的挖掘:此類數(shù)據(jù)挖掘從本質(zhì)上說(shuō)是對(duì)數(shù)據(jù)用途的挖掘。以網(wǎng)站為例進(jìn)行說(shuō)明:在客戶端,通過(guò)用戶的瀏覽歷史記錄來(lái)搜集數(shù)據(jù);在服務(wù)器端,通過(guò)請(qǐng)求日志搜集數(shù)據(jù)。通過(guò)這樣的數(shù)據(jù)挖掘,可以發(fā)現(xiàn)用戶訪問(wèn)頁(yè)面的類型,訪問(wèn)的時(shí)間和訪問(wèn)持續(xù)的時(shí)間,以及這個(gè)頁(yè)面被引用的次數(shù)。此類信息有助于實(shí)現(xiàn)對(duì)頁(yè)面的整理,最終實(shí)現(xiàn)高效快速的信息檢索。在商業(yè)領(lǐng)域中使用這一技術(shù)可以實(shí)現(xiàn)客戶價(jià)值評(píng)估、產(chǎn)品潛力發(fā)掘、客戶行為預(yù)測(cè)等。
1.2 網(wǎng)絡(luò)數(shù)據(jù)挖掘的組成和方法
Etzioni. O.提出可將網(wǎng)絡(luò)數(shù)據(jù)挖掘的過(guò)程分成信息檢索、信息提取、知識(shí)集成和分析四個(gè)部分[4]。圖2對(duì)網(wǎng)絡(luò)數(shù)據(jù)挖掘的四個(gè)組成部分進(jìn)行說(shuō)明:
圖2
信息檢索(Information Retrieval,IR):信息檢索是自動(dòng)對(duì)網(wǎng)絡(luò)中相關(guān)聯(lián)的文檔進(jìn)行搜索,其過(guò)程主要包括對(duì)文檔的表示、索引和搜索。
信息提取(Information Extraction,IE):信息提取是在文檔被檢索之后,自動(dòng)從中提取知識(shí),這一過(guò)程主要實(shí)現(xiàn)對(duì)文檔中主要字段的語(yǔ)義進(jìn)行識(shí)別。
信息集成(Generation):這一過(guò)程對(duì)已有的文檔進(jìn)行歸納,得到概要知識(shí)。在這里將使用分類、規(guī)則關(guān)聯(lián)等模式識(shí)別和機(jī)器學(xué)習(xí)的技術(shù)來(lái)提取信息。例如,將一個(gè)網(wǎng)站的主頁(yè)和其他頁(yè)面區(qū)分開(kāi)就是一個(gè)集成工作。
數(shù)據(jù)分析(Analysis):這一階段將對(duì)信息集成階段所生成的模式進(jìn)行解釋說(shuō)明。數(shù)據(jù)分析是一個(gè)數(shù)據(jù)驅(qū)動(dòng)的問(wèn)題,必須在數(shù)據(jù)充足的前提下才可能提取有用的信息。
1.3 網(wǎng)絡(luò)數(shù)據(jù)挖掘面臨的挑戰(zhàn)與局限性
由于網(wǎng)絡(luò)數(shù)據(jù)本身的特身,網(wǎng)絡(luò)數(shù)據(jù)挖掘面臨如下問(wèn)題:1)由于網(wǎng)絡(luò)數(shù)據(jù)的匿名性和人為破壞而造成了數(shù)據(jù)的不可靠。2)存在噪聲。3)網(wǎng)絡(luò)數(shù)據(jù)是動(dòng)態(tài)的,且存在時(shí)間短暫。3)網(wǎng)絡(luò)數(shù)據(jù)缺乏結(jié)構(gòu)化處理,且類型各異。4)語(yǔ)義存在二義性。5)數(shù)據(jù)高度冗余。使用我們現(xiàn)有的工具和算法難以應(yīng)付如此復(fù)雜的網(wǎng)絡(luò)數(shù)據(jù)。在下一節(jié)中提出在查詢中使用遺傳算法實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)數(shù)據(jù)的搜索和數(shù)據(jù)挖掘的優(yōu)化。
2 在網(wǎng)絡(luò)數(shù)據(jù)挖掘中使用遺傳算法
遺傳算法和相關(guān)技術(shù)在網(wǎng)絡(luò)數(shù)據(jù)挖掘領(lǐng)域的應(yīng)用包括信息查詢檢索、查詢優(yōu)化、文檔表示和分布式數(shù)據(jù)挖掘等[5],本文就信息查詢和查詢優(yōu)化方面對(duì)遺傳算法的應(yīng)用進(jìn)行闡述。
2.1 查詢和檢索
Marghny等人將遺傳算法用于元數(shù)據(jù)搜尋[6],使用這一方法對(duì)標(biāo)準(zhǔn)搜索引擎的搜索結(jié)果以一種優(yōu)化方式進(jìn)行組合,生成更令用戶感興趣的頁(yè)面,在文獻(xiàn)[6]中對(duì)適配函數(shù)進(jìn)行如下定義:
(a) 鏈接質(zhì)量函數(shù)
n表示用戶輸入的關(guān)鍵字的個(gè)數(shù),#Ki表示在鏈接L中關(guān)鍵字Ki出現(xiàn)的次數(shù)。
(b) 頁(yè)面質(zhì)量函數(shù)
m表示每個(gè)頁(yè)面中總的鏈接數(shù)。
(c) 平均質(zhì)量函數(shù)
Fmax(P)和Fmin(P)分別表示采用遺傳算法后頁(yè)面質(zhì)量函數(shù)的最大值和最小值。Fmax(P)的最大值是m*n,而Fmin(P)的最小值是0.
研究人員分別使用Yahoo,Google,AltaVista和MSN這四個(gè)搜索引擎針對(duì)不同的主題下載了300個(gè)頁(yè)面。在雜交點(diǎn)之后對(duì)選中的頁(yè)面交換雙親的鏈接,以實(shí)現(xiàn)雜交。
2.2 查詢優(yōu)化
查詢優(yōu)化使用一種基于適度回饋機(jī)制的技術(shù)。使用回饋的目的是通過(guò)使用相關(guān)和無(wú)關(guān)文檔集合來(lái)修改用戶的查詢,使用戶的查詢結(jié)果更接近于目標(biāo)文檔。將之前的查詢得到的關(guān)鍵字添加到當(dāng)前查詢中,同時(shí)將早期文檔中不相關(guān)的關(guān)鍵字刪除,通過(guò)這種辦法可以檢索到更多的關(guān)聯(lián)度更大的結(jié)果。
遺傳算法在查詢優(yōu)化上能夠發(fā)揮很大的作用。Z. Z. Nick和P. Themis.通過(guò)長(zhǎng)期監(jiān)控用戶的瀏覽習(xí)慣創(chuàng)建用戶模型[7]。使用遺傳算法對(duì)用戶查詢進(jìn)行修改,在這里文檔和查詢被表示成向量。每個(gè)個(gè)體被表示成查詢向量,用染色體表示關(guān)鍵字的權(quán)重或者關(guān)鍵字出現(xiàn)或未出現(xiàn)的頻率。M. Boughanem等人研制了一種新的查詢優(yōu)化技術(shù),在這一技術(shù)中,通過(guò)使用遺傳算法生成多個(gè)查詢,對(duì)文檔的不同區(qū)域進(jìn)行搜索,最終得到最優(yōu)查詢結(jié)果[8]。
Leroy等人在文獻(xiàn)[9]中解釋了在對(duì)上下文進(jìn)行動(dòng)態(tài)查詢時(shí)使用基于遺傳算法的優(yōu)化策略有助于提高偶然用戶的查詢效率。由于偶然用戶在Internet上進(jìn)行查詢的時(shí)候只使用少數(shù)的關(guān)鍵字,這樣得到的查詢結(jié)果很少而且相當(dāng)不精確。但是,大多數(shù)用戶在查詢時(shí)使用相同的搜索引擎,在某一主題的查詢方面,可總結(jié)大多數(shù)用戶的查詢行為,從中提取有價(jià)值的信息,從而對(duì)偶然用戶的查詢要求能夠進(jìn)行更高效的處理。在遺傳編程的實(shí)現(xiàn)上,每個(gè)染色體被設(shè)計(jì)成一個(gè)查詢,它有五個(gè)位,每個(gè)位由一個(gè)適當(dāng)?shù)年P(guān)鍵字填充。在計(jì)算染色體適應(yīng)度時(shí),將查詢編碼發(fā)送給查詢引擎,查詢引擎將返回十條最主要的文檔。
3 小結(jié)
為了充分發(fā)揮網(wǎng)絡(luò)的潛能,讓網(wǎng)絡(luò)查詢更加智能化,需要對(duì)查詢進(jìn)行改進(jìn)。在網(wǎng)絡(luò)數(shù)據(jù)挖掘及其相關(guān)領(lǐng)域的研究在查詢優(yōu)化方面發(fā)揮著十分重要的作用。網(wǎng)絡(luò)數(shù)據(jù)挖掘是一個(gè)快速發(fā)展的領(lǐng)域,在這個(gè)領(lǐng)域,研究人員提出各種方法對(duì)計(jì)算方法進(jìn)行改進(jìn)。在該文中,闡述了網(wǎng)絡(luò)數(shù)據(jù)挖掘過(guò)程、組成、特點(diǎn)以及網(wǎng)絡(luò)數(shù)據(jù)挖掘所面臨的挑戰(zhàn)。詳細(xì)討論了使用遺傳算法對(duì)網(wǎng)絡(luò)數(shù)據(jù)挖掘中不同問(wèn)題的解決方法。
雖然使用遺傳算法對(duì)網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行挖掘很有發(fā)展?jié)摿?但是目前這方面的應(yīng)用和相關(guān)文獻(xiàn)還比較有限,為研究人員的進(jìn)一步研究留下很大的空間。
摘要：數(shù)據(jù)挖掘技術(shù)是近些年來(lái)發(fā)展起來(lái)的一門(mén)新技術(shù)，通過(guò)該技術(shù)，人們可以發(fā)現(xiàn)數(shù)據(jù)后面潛藏的有價(jià)值的信息。數(shù)據(jù)挖掘已經(jīng)成為解決當(dāng)前企業(yè)信息系統(tǒng)中所面臨的“數(shù)據(jù)爆炸”狀況的最有效的方法，這也為決策者進(jìn)行各種商業(yè)決策提供了科學(xué)的理論支持。該文將對(duì)數(shù)據(jù)挖掘的含義與基本算法進(jìn)行闡述和分析，并對(duì)數(shù)據(jù)挖掘在電子商務(wù)中的具體應(yīng)用進(jìn)行分析探討。
關(guān)鍵詞：電子商務(wù)；數(shù)據(jù)挖掘；基本算法；應(yīng)用分析
近些年來(lái)，基于電子計(jì)算機(jī)性能的不斷提高、計(jì)算成本的不斷下降以及數(shù)據(jù)管理技術(shù)的成功運(yùn)用，企業(yè)商務(wù)往來(lái)的電子信息化程度也越來(lái)越高。與此同時(shí)，這也造成了大量的數(shù)據(jù)積累，形成了了“數(shù)據(jù)豐富而知識(shí)貧乏”的現(xiàn)象，這使得信息決策者難以從海量的數(shù)據(jù)中提取出具有信息價(jià)值的知識(shí)，數(shù)據(jù)挖掘技術(shù)的運(yùn)用很好的解決了這個(gè)問(wèn)題。
1 數(shù)據(jù)挖掘的含義
數(shù)據(jù)挖掘（Data Mining）可以定義為從大量的、不完全的、模糊的或者是隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取隱含的、同時(shí)又有潛在價(jià)值的知識(shí)與信息的過(guò)程。
數(shù)據(jù)挖掘可以擴(kuò)展為以下幾層含義：首先，數(shù)據(jù)源必須具備包含大量的、真實(shí)的數(shù)據(jù)的特點(diǎn)，數(shù)據(jù)源可以是不同數(shù)據(jù)倉(cāng)庫(kù)或者文件等；其次，在數(shù)據(jù)挖掘中發(fā)掘出的知識(shí)要可運(yùn)用并且同時(shí)容易被理解。也就說(shuō)，數(shù)據(jù)挖掘的本質(zhì)目的在于尋找有用的知識(shí)，但是該知識(shí)需要被人們理解和接受；最后，數(shù)據(jù)挖掘通常是針對(duì)某一特定問(wèn)題而進(jìn)行的分析，往往不可能發(fā)掘出通用的知識(shí)，這些知識(shí)信息一般都具有相應(yīng)的針對(duì)性，只有在特寫(xiě)的范圍中才能夠應(yīng)用。
廣義的角度來(lái)說(shuō)，在數(shù)據(jù)挖掘中的知識(shí)是指具有一定規(guī)則的模式或者概念等，而信息與數(shù)據(jù)則是知識(shí)的理論源泉。也就是說(shuō)對(duì)知識(shí)的發(fā)掘就是是從數(shù)據(jù)中挖掘出相應(yīng)的規(guī)則與模式的過(guò)程，故而稱之為數(shù)據(jù)挖掘。在數(shù)據(jù)挖掘中，數(shù)據(jù)源可以是多樣的也可以是單一的，可以是分布式形態(tài)的，也可以是結(jié)構(gòu)化形態(tài)的。
2 電子商務(wù)中數(shù)據(jù)挖掘的體系結(jié)構(gòu)
當(dāng)前電子商務(wù)是數(shù)據(jù)挖掘技術(shù)應(yīng)用比較廣泛的應(yīng)用，這主要是歸功于電子商務(wù)能夠比較容易地滿足數(shù)據(jù)挖掘所必需的因素，這些因素包括豐富的數(shù)據(jù)語(yǔ)言、可以自動(dòng)收集可靠的數(shù)據(jù)并可將數(shù)據(jù)挖掘的結(jié)果轉(zhuǎn)化為商務(wù)行為。然而，要想充分發(fā)揮數(shù)據(jù)挖掘技術(shù)在電子商務(wù)應(yīng)用中的效率，數(shù)據(jù)挖掘技術(shù)需要將事務(wù)處理階段的數(shù)據(jù)轉(zhuǎn)存到相應(yīng)的數(shù)據(jù)倉(cāng)庫(kù)中，并且要與電子商務(wù)行為有機(jī)結(jié)合起來(lái)。本文將電子商務(wù)中數(shù)據(jù)挖掘的體系結(jié)構(gòu)概括3個(gè)主要部分，即商務(wù)數(shù)據(jù)定義、分析處理和顧客相互作用和。流程圖如圖1所示。
3 電子商務(wù)中數(shù)據(jù)挖掘的基本方法
3.1 路徑分析
這種方法可以被用于確定在一個(gè)Web站點(diǎn)中最頻繁訪問(wèn)的路徑，其它一些與之有關(guān)路徑的信息也可以通過(guò)路徑分析得出。比如當(dāng)70%的用戶端在訪問(wèn)/company/product2的時(shí)候，從/company開(kāi)始,而后經(jīng)過(guò)company/news,/company/products/company/productl；80%的訪問(wèn)這個(gè)站點(diǎn)的顧客是從/company/products而開(kāi)始的；65%的客戶在瀏覽少于4個(gè)頁(yè)面后便離開(kāi)了?？梢灾溃?條規(guī)則在/company/roduct2頁(yè)面上有具有有用的信息，但是由于客戶對(duì)站點(diǎn)進(jìn)行的是遷回繞行方式的訪問(wèn)，因而這個(gè)有用信息并不十分明顯。第2條規(guī)則則說(shuō)明了客戶訪問(wèn)站點(diǎn)通常不是從主頁(yè)開(kāi)始的，而是由/company/products開(kāi)始的，假如這個(gè)頁(yè)面上包含許多產(chǎn)品的目錄類型的信息，將是一個(gè)不錯(cuò)的想法。第3條規(guī)則表明客戶在網(wǎng)站上停留的時(shí)間。進(jìn)過(guò)路徑分析后，發(fā)現(xiàn)客戶在該網(wǎng)站上瀏覽情況往往不超過(guò)4個(gè)頁(yè)面時(shí)，就可以將相對(duì)重要的商品信息置于這些頁(yè)面中，從而可以改進(jìn)頁(yè)面網(wǎng)站的結(jié)構(gòu)設(shè)計(jì)。
3.2 關(guān)聯(lián)規(guī)則分析
關(guān)聯(lián)分析的最終目的是挖掘隱藏在數(shù)據(jù)間的相互關(guān)系，在電子商務(wù)中進(jìn)行關(guān)聯(lián)規(guī)則分析也就是找到客戶對(duì)網(wǎng)站上不同文件之間訪問(wèn)的相互聯(lián)系。在進(jìn)行Web數(shù)據(jù)挖掘后，可以構(gòu)建出關(guān)聯(lián)關(guān)系模型，我們可以依據(jù)該模型更好地組織站點(diǎn)，從而減少用戶過(guò)濾信息的負(fù)擔(dān)。
3.3 序列模式分析
序列模式分析的重點(diǎn)在于分析不同數(shù)據(jù)之間的前后或者因果關(guān)系，也就是說(shuō)在時(shí)間有序的事務(wù)集合中，去發(fā)現(xiàn)具有關(guān)聯(lián)的內(nèi)部事務(wù)模式。發(fā)現(xiàn)序列模式有助于電子商務(wù)的組織者對(duì)客戶的訪問(wèn)模式進(jìn)行預(yù)測(cè)，從而為客戶提供個(gè)性化的服務(wù)，網(wǎng)站的管理人員可以依據(jù)瀏覽模式對(duì)訪問(wèn)者進(jìn)行分類，而在頁(yè)面上只展示出對(duì)應(yīng)的訪問(wèn)鏈接。當(dāng)訪問(wèn)者瀏覽到某一頁(yè)面的時(shí)候，管理人員可以檢查他的瀏覽所符合的序列模式，并且在比較顯眼的位置進(jìn)行“訪問(wèn)該頁(yè)面的人員一般接著訪問(wèn)”的若干頁(yè)面。
3.4 分類分析法
分類分析法的輸入集通常是一組記錄集合或者幾種標(biāo)記，這種分析法首先為每一個(gè)記錄賦予一個(gè)相應(yīng)的標(biāo)記，也就是按標(biāo)記分類記錄，而后對(duì)這些標(biāo)定的記錄進(jìn)檢查，從而描述出這些記錄的特征。在電子商務(wù)中通過(guò)應(yīng)用數(shù)據(jù)挖掘，可以對(duì)不同消費(fèi)群體進(jìn)行分類，從而便于對(duì)某一類客戶進(jìn)行有針對(duì)性的商務(wù)活動(dòng)。
3.5 聚類分析法
聚類分析法有別于分類規(guī)則法，其輸入集合一般是一組未標(biāo)定的記錄，這也就是說(shuō)該輸入記錄并沒(méi)有進(jìn)行任何分類。這種方法的目的是依據(jù)一定的規(guī)則，對(duì)記錄集合進(jìn)行合理劃分，并且利用顯式或者隱式的方法對(duì)不同的類別進(jìn)行描述。當(dāng)前已開(kāi)發(fā)出許多聚類分析的工具，在電子商務(wù)中，通過(guò)對(duì)具有相似瀏覽行為的客戶進(jìn)行聚類，可以使管理員更多地了解客戶信息，從而為其提供更適合、更滿意的服務(wù)。
4 電子商務(wù)中數(shù)據(jù)挖掘的應(yīng)用分析
本文將數(shù)據(jù)挖掘在電子商務(wù)中的典型應(yīng)用概括為以下幾個(gè)方面：
4.1 發(fā)現(xiàn)潛在客戶
在對(duì)Web的客戶訪問(wèn)信息進(jìn)行數(shù)據(jù)挖掘中，可以利用分類技術(shù)在Internet上發(fā)現(xiàn)未來(lái)潛在的客戶。對(duì)于電子商務(wù)從業(yè)者來(lái)說(shuō)，得到這些潛在客戶一般市場(chǎng)策略是，首先對(duì)現(xiàn)已存在的訪問(wèn)者進(jìn)行分類，通常分為3種，即:“no customer”、“visitor once”、“visitor regular”。通過(guò)Web上的分類發(fā)現(xiàn)，管理人員可以識(shí)別出新客戶和已經(jīng)分類的老客戶的一些具有共性的描述，這有助于對(duì)該新客戶進(jìn)行正確的分類。而后，依據(jù)其分類來(lái)判斷這個(gè)新客戶是否屬于潛在的客戶群體，從而決定是否要需要將這個(gè)新客戶作為未來(lái)潛在的客戶來(lái)對(duì)待。在確定客戶的類型以后，管理人員就可以動(dòng)態(tài)展示相應(yīng)的Web頁(yè)面，而Web頁(yè)面的具體內(nèi)容主要取決于客戶與銷(xiāo)售商提供的產(chǎn)品以及服務(wù)之間的關(guān)聯(lián)規(guī)則。
4.2 駐留客戶
現(xiàn)代電子商務(wù)平臺(tái)使得傳統(tǒng)客戶與銷(xiāo)售商之間的空間距離已經(jīng)不存在了，在網(wǎng)絡(luò)電子平臺(tái)上，每一個(gè)客戶來(lái)都有選擇不同銷(xiāo)售產(chǎn)品的權(quán)利，如何使這些客戶在銷(xiāo)售商自己的銷(xiāo)售站點(diǎn)上駐留比較長(zhǎng)的時(shí)間、使其對(duì)該網(wǎng)頁(yè)產(chǎn)品產(chǎn)生更火的興趣，對(duì)每一個(gè)銷(xiāo)售商來(lái)說(shuō)都是一個(gè)挑戰(zhàn)。為客戶在相應(yīng)的網(wǎng)站上駐留更長(zhǎng)的時(shí)間，就需要了解客戶的瀏覽行為，掌握客戶的興趣與不同需求所，從而對(duì)頁(yè)面內(nèi)容進(jìn)行動(dòng)態(tài)調(diào)整，以此來(lái)滿足客戶的需求。對(duì)客戶訪問(wèn)信息進(jìn)行數(shù)據(jù)挖掘，就可以掌握客戶的瀏覽行為，從而獲取客戶的興趣及需求。在網(wǎng)絡(luò)電子商務(wù)平臺(tái)中的一個(gè)典型的序列，就代表了客戶以頁(yè)面的形式在該站點(diǎn)上導(dǎo)航的行為，運(yùn)用數(shù)據(jù)挖掘中的序列模式分析技術(shù)，可以知道道客戶的實(shí)際需求，從而為客戶提供一些特有的商品信推廣信息，從而使客戶能保持對(duì)訪問(wèn)站點(diǎn)的興趣。
4.3 對(duì)站點(diǎn)改進(jìn)的設(shè)計(jì)
網(wǎng)絡(luò)站點(diǎn)上頁(yè)面內(nèi)容的安排與連接，就像超市物品在貨架上的擺設(shè)一樣，需要將支持度與信任度較高的關(guān)聯(lián)物品擺放在一起，從而有助于銷(xiāo)售。通過(guò)Web上的關(guān)聯(lián)規(guī)則分析，可以針對(duì)不同的客戶對(duì)站點(diǎn)的結(jié)構(gòu)進(jìn)行動(dòng)態(tài)調(diào)整，并進(jìn)行相應(yīng)的改進(jìn)設(shè)計(jì)，從而使與客戶訪問(wèn)有關(guān)聯(lián)的文件之間的連接更為直接，這也有助于客戶更容易地訪問(wèn)到預(yù)想的頁(yè)面。當(dāng)電子商務(wù)網(wǎng)站具有這樣的便利性的時(shí)候，便可以給客戶留下很好的印象，這也就增加了客戶下次訪問(wèn)的機(jī)率。
4.4 對(duì)客戶進(jìn)行聚類
在電子商務(wù)中，應(yīng)用數(shù)據(jù)挖掘進(jìn)行客戶聚類是一個(gè)十分重要的內(nèi)容，通過(guò)對(duì)具有相似瀏覽行為的客戶進(jìn)行分組，可以分析出組中客戶的共同特征與共性信息，從而可以幫電子商務(wù)的組織者更加客觀地了解自己的客戶，這也最后有利于組織者為客戶提供更加適合、更加面向客戶的服務(wù)。
5 結(jié)束語(yǔ)
數(shù)據(jù)挖掘盡管只有十多年的發(fā)展歷史，但是在電子商務(wù)中卻展示出了非常廣闊的應(yīng)用前景。本文比較詳細(xì)地闡述了電子商務(wù)中數(shù)據(jù)挖掘的體系結(jié)構(gòu)、應(yīng)用方法以及比較典型的應(yīng)用，期望通過(guò)本文的分析與探討，可以為今后數(shù)據(jù)挖掘技術(shù)在電子商務(wù)中的廣泛應(yīng)用提供積極的借鑒參考。
摘要：數(shù)據(jù)挖掘是一個(gè)新興的領(lǐng)域，在短短幾年內(nèi)得到了迅速的發(fā)展。關(guān)聯(lián)規(guī)則算法是數(shù)據(jù)挖掘技術(shù)中最活躍的算法之一。該文從關(guān)聯(lián)規(guī)則算法的原理入手，對(duì)關(guān)聯(lián)規(guī)則的各種算法進(jìn)行了深入研究，并總結(jié)得出了強(qiáng)關(guān)聯(lián)規(guī)則生成的步驟方法。
關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則算法；強(qiáng)關(guān)聯(lián)規(guī)則
隨著數(shù)據(jù)庫(kù)技術(shù)的發(fā)展、改進(jìn)及相關(guān)技術(shù)、產(chǎn)品的廣泛應(yīng)用，數(shù)據(jù)庫(kù)中存儲(chǔ)的數(shù)據(jù)量日益膨脹。此時(shí)，許多人都曾提出疑問(wèn)：在海量的數(shù)據(jù)之間是否隱藏著許多具有決策意義的有價(jià)值的信息？如果這種信息真的存在，那么把這些信息挖掘出來(lái)并應(yīng)用于現(xiàn)實(shí)生活，將會(huì)為決策者和管理者提供指導(dǎo)，提高工作效率和工作精度。
數(shù)據(jù)挖掘(Data- Mining)就是從眾多的、有噪聲的、不完全的、模糊的、隨機(jī)的大量數(shù)據(jù)中，提取隱含在其中人們事先不知道但又是潛在有用的信息和知識(shí)的過(guò)程[1]。
關(guān)聯(lián)規(guī)則算法是一種在海量數(shù)據(jù)中找出隱藏的關(guān)聯(lián)規(guī)則的方法。它是數(shù)據(jù)挖掘中最為活躍的算法之一。
1 關(guān)聯(lián)規(guī)則算法的原理
1.1 背景
關(guān)聯(lián)規(guī)則算法早期應(yīng)用于“購(gòu)物籃分析”。通過(guò)使用關(guān)聯(lián)規(guī)則算法來(lái)對(duì)客戶的事務(wù)執(zhí)行購(gòu)物藍(lán)分析，可以知道哪些產(chǎn)品比較熱銷(xiāo)，以及一個(gè)特定的產(chǎn)品與另一個(gè)產(chǎn)品一起被購(gòu)買(mǎi)的可能性是多大。如，在數(shù)據(jù)挖掘應(yīng)用中最典型的例子“啤酒與尿布”，就是銷(xiāo)售商們通過(guò)大量的客戶購(gòu)買(mǎi)信息，挖掘出的一條關(guān)聯(lián)規(guī)則。即，在購(gòu)買(mǎi)尿布的用戶中，有很大比例的人還同時(shí)購(gòu)買(mǎi)了啤酒。知道了這條規(guī)則，商家就可以采取行動(dòng)，改變產(chǎn)品的布局來(lái)增加銷(xiāo)售和管理庫(kù)存?，F(xiàn)在，關(guān)聯(lián)規(guī)則挖掘不僅在零售業(yè)，在其它領(lǐng)域也得到了廣泛應(yīng)用。
關(guān)聯(lián)規(guī)則常常用一個(gè)蘊(yùn)涵式來(lái)表示。如“啤酒=>尿布”。
1.2 基本概念
1.2.1 項(xiàng)集（Itemset）
項(xiàng)集也叫項(xiàng)目集合，是由一組項(xiàng)組成。其中每個(gè)項(xiàng)都是一個(gè)屬性值。通常設(shè)I＝{i1,i2，…im}為一個(gè)項(xiàng)目集，而事務(wù)數(shù)據(jù)庫(kù)D={t1,t2，…tm}是由一系列事務(wù)組成，而每個(gè)事務(wù)ti（i=1,2,…,n）都對(duì)應(yīng)I上的一個(gè)子集。在購(gòu)物籃分析中，項(xiàng)集中包含的是一組由用戶購(gòu)買(mǎi)的產(chǎn)品，如｛啤酒，尿布，香檳｝。這個(gè)項(xiàng)集包含了3個(gè)屬性值，大小為3。
1.2.2 支持度（Support）
支持度是指一個(gè)項(xiàng)集在全部事務(wù)中出現(xiàn)的頻率。項(xiàng)集｛牛奶，面包｝的支持度就是在全部事務(wù)數(shù)據(jù)中，既購(gòu)買(mǎi)了面包又購(gòu)買(mǎi)了牛奶的顧客出現(xiàn)的頻率。若項(xiàng)集｛牛奶，面包｝的支持度為0.05，則表明在全部顧客中，只有5%的顧客同時(shí)購(gòu)買(mǎi)了這兩樣。
最小支持度是事先由用戶確定的一個(gè)數(shù)值。一般來(lái)說(shuō)，用戶只關(guān)心那些出現(xiàn)頻率比最小支持度高或與之相等的項(xiàng)集。因此，該數(shù)據(jù)可以用來(lái)對(duì)項(xiàng)集進(jìn)行篩選。
1.2.3 置信度(Confidence)
置信度是關(guān)聯(lián)規(guī)則的屬性。關(guān)聯(lián)規(guī)則“牛奶=>面包”的置信度是使用｛牛奶｝的支持度除項(xiàng)集｛牛奶，面包｝的支持度來(lái)計(jì)算的。簡(jiǎn)單解釋就是，在全部事務(wù)數(shù)據(jù)中，購(gòu)買(mǎi)牛奶的顧客中有多大比例的人還同時(shí)購(gòu)買(mǎi)了面包。
它是按以下方式來(lái)定義的：
Confidence{A=>B}=Support{A,B}/Support{A}
最小置信度也是在運(yùn)行算法之前由用戶事先指定的一個(gè)數(shù)值。該數(shù)據(jù)表明用戶只對(duì)那些置信度等于或大于最小置信度的規(guī)則感興趣，即那些擁有較高概率的規(guī)則。該數(shù)據(jù)可以用來(lái)篩選出有效的關(guān)聯(lián)規(guī)則。
1.2.4 頻繁項(xiàng)目集（Frequent Itemsets）
挖掘頻繁項(xiàng)目集是進(jìn)行關(guān)聯(lián)規(guī)則算法的核心內(nèi)容。所有滿足用戶指定的最小支持度的項(xiàng)目集，即大于或等于最小支持度的I的非空子集，就稱為頻繁項(xiàng)目集，簡(jiǎn)稱為頻繁項(xiàng)集。即上面提到的用戶感興趣的項(xiàng)集。
1.2.5 強(qiáng)關(guān)聯(lián)規(guī)則(Strong Association Rule)
D在I上同時(shí)滿足最小支持度和最小置信度，即在滿足支持度不小于最小支持度的每一個(gè)頻繁項(xiàng)集中，置信度大于等于最小置信度的關(guān)聯(lián)規(guī)則。即上面提到的用戶感興趣的規(guī)則。這個(gè)規(guī)則也叫強(qiáng)關(guān)聯(lián)規(guī)則。
1.2.6 相關(guān)度（Importance）
相關(guān)度是關(guān)聯(lián)規(guī)則中另外一個(gè)重要的概念。在一些文獻(xiàn)中相關(guān)度也被稱為興趣度分?jǐn)?shù)或者增益（lift）[2]。
相關(guān)度的公式可以定義如下。
Importance({A,B})=confidence(A,B)/(confidence(A)*confidence(B))
如果Importance＝1,則A和B是獨(dú)立的項(xiàng)。在購(gòu)物籃分析中，它表示產(chǎn)品A的購(gòu)買(mǎi)和產(chǎn)品B的購(gòu)買(mǎi)是兩個(gè)獨(dú)立的事件。如果Importance1，則A和B是正相關(guān)的。這表示如果一個(gè)客戶購(gòu)買(mǎi)了A，則他也可能購(gòu)買(mǎi)B。
2 關(guān)聯(lián)規(guī)則挖掘的一般過(guò)程
通過(guò)以上對(duì)關(guān)聯(lián)規(guī)則挖掘算法的簡(jiǎn)單介紹，可以了解到，關(guān)聯(lián)規(guī)則挖掘就是通過(guò)用戶指定的最小支持度，在全部事務(wù)數(shù)據(jù)庫(kù)中挖掘出滿足支持度不小于最小支持度的頻繁項(xiàng)目集，再通過(guò)用戶指定的最小置信度，在全部頻繁項(xiàng)目集中挖掘出那些置信度不小于最小置信度的強(qiáng)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘過(guò)程由這兩部分共同組成。
在這兩部分中，關(guān)聯(lián)規(guī)則挖掘是否成功主要取決于第一部分，即挖掘頻繁項(xiàng)目集。
3 頻繁項(xiàng)目集的生成算法
挖掘頻繁項(xiàng)目集是使用關(guān)聯(lián)規(guī)則算法的核心部分。自關(guān)聯(lián)規(guī)則挖掘問(wèn)題提出后，相應(yīng)的如何快速高效地生成頻繁項(xiàng)目集這個(gè)核心問(wèn)題的算法就不斷的被人研究，并不斷發(fā)現(xiàn)、使用。這些算法大多都是通過(guò)利用頻繁項(xiàng)集的特性DD即如果一個(gè)項(xiàng)目集是頻繁的，那么它的所有子集也都是頻繁的DD來(lái)進(jìn)行操作的。
Apriori算法[5]在關(guān)聯(lián)規(guī)則挖掘領(lǐng)域中有很大的影響力，應(yīng)用極為廣泛。它的命名源于算法使用了頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)。Apriori算法是通過(guò)迭代即反復(fù)掃描數(shù)據(jù)項(xiàng)的方式來(lái)產(chǎn)生頻繁項(xiàng)集的。它的具體思路是：在第一次迭代時(shí)，先產(chǎn)生包含所有數(shù)據(jù)項(xiàng)的大小為1的候選集，計(jì)算出它們的支持度，選擇那些支持度大于等于最小支持度的候選集作為第一次迭代時(shí)的頻繁項(xiàng)目集。此時(shí)，所有頻繁項(xiàng)目集的大小都為1，被淘汰的項(xiàng)目集被標(biāo)記為非頻繁子集。接著進(jìn)行第二次迭代，在第二次迭代的第一步中，將所有成對(duì)出現(xiàn)的項(xiàng)集都作為大小為2的候選集，第二步，利用頻繁項(xiàng)集的性質(zhì)：頻繁項(xiàng)集的子集也都是頻繁的，假若某個(gè)項(xiàng)目集的一個(gè)子集不是頻繁的，那這個(gè)項(xiàng)目集必然不是頻繁項(xiàng)集，將剛才產(chǎn)生的候選集中包含有非頻繁子集的刪去。第三步再計(jì)算所有候選集的支持度，將支持度滿足最小支持度的候選集做為第二次迭代產(chǎn)生的大小為2的頻繁項(xiàng)目集。如此通過(guò)i次迭代，就可以產(chǎn)生出大小為i的頻繁項(xiàng)集。
Apriori算法是通過(guò)項(xiàng)目集元素?cái)?shù)目不斷增長(zhǎng)的方式來(lái)逐步完成頻繁項(xiàng)目集發(fā)現(xiàn)的。每增長(zhǎng)一次項(xiàng)目數(shù)，Apriori算法就至少需要掃描事務(wù)數(shù)據(jù)庫(kù)一次，假如頻繁項(xiàng)目集的項(xiàng)目數(shù)很大，會(huì)造成計(jì)算機(jī)巨大的I/O負(fù)載。并且，因?yàn)锳priori算法在每一次迭代時(shí)，都將成對(duì)出現(xiàn)的項(xiàng)集依次組成新的候選集，因此，可能會(huì)產(chǎn)生龐大的候選集。這對(duì)計(jì)算機(jī)運(yùn)行速度也將是一種挑戰(zhàn)。
因此，逐漸又產(chǎn)生了Apriori算法的改進(jìn)方法。
如基于數(shù)據(jù)分割方法的Partition方法。Apriori算法在每一次迭代時(shí)只能將項(xiàng)目數(shù)增加1,每次產(chǎn)生的候選集也并不都是有效的，無(wú)形中降低了算法的效率。而Partition算法是一種基于對(duì)數(shù)據(jù)集進(jìn)行劃分的挖掘算法，它的思路是：先將事務(wù)數(shù)據(jù)庫(kù)劃分為幾個(gè)邏輯上互相獨(dú)立的區(qū)域。在每個(gè)區(qū)中，利用挖掘算法挖掘出它們各自的頻繁項(xiàng)目集。然后將這些頻繁項(xiàng)目集合成一個(gè)候選集。最后，計(jì)算出候選集的支持度，挖掘出符合不小于最小支持度的最終的頻繁項(xiàng)目集。Partition方法在第一次劃分時(shí)掃描一次數(shù)據(jù)集，在最后求候選集支持度時(shí)再一次掃描數(shù)據(jù)集，全程只掃描二次數(shù)據(jù)集，大大減少了I/O操作。Partition算法因?yàn)槭欠謩e求每個(gè)區(qū)的頻繁項(xiàng)集，因此可分別同時(shí)對(duì)各區(qū)進(jìn)行操作，大大提高了算法的效率。
還有與Apriori算法類似的DHP算法[3]。DHP算法也是從Lk-1中生成侯選集Ck。但DHP算法在每次迭代計(jì)算候選集的支持度時(shí)，會(huì)建立并維護(hù)一張Hash表。在下一次迭代時(shí)，根據(jù)Hash表來(lái)選擇加入的數(shù)據(jù)項(xiàng)，而不是像Apriori算法那樣將所有數(shù)據(jù)項(xiàng)先全部選上之后，再刪去那些非頻繁子集。通過(guò)對(duì)Hash表的操作，DHP算法可以大大減小侯選集的規(guī)模，從而提高算法的計(jì)算效率。
隨著數(shù)據(jù)庫(kù)容量的逐步增大，為適應(yīng)新形勢(shì)，新的算法不斷出現(xiàn)。2000年，Han等人提出了一個(gè)不用產(chǎn)生候選集，可以直接將數(shù)據(jù)壓縮成頻繁模式樹(shù)的方法，被稱為FP-tree算法[4]。
4 強(qiáng)關(guān)聯(lián)規(guī)則的生成
利用Apriori算法或其它類似的算法挖掘出所有頻繁項(xiàng)集之后，下一步的工作就是生成強(qiáng)關(guān)聯(lián)規(guī)則。這可以在頻繁項(xiàng)目集中逐一測(cè)試非空子集的支持度，從而挖掘出所有可以生成的規(guī)則。也可以直接測(cè)試用戶想要挖掘的規(guī)則是否成立。假如用戶打算挖掘出這樣的規(guī)則｛A，B，C｝=>D，那么，第一步，先來(lái)檢驗(yàn)｛A,B,C,D｝和｛A,B,C｝是否都是頻繁項(xiàng)集。如果是，接著第二步，利用關(guān)聯(lián)規(guī)則置信度的公式Confidence{A=>B}=support{A,B}/support{A}，計(jì)算出規(guī)則｛A，B，C｝=>D的置信度的值。若此值大于等于最小置信度，那么規(guī)則｛A，B，C｝=>D成立，是強(qiáng)關(guān)聯(lián)規(guī)則。反之，不成立。
5 結(jié)論
關(guān)聯(lián)規(guī)則挖掘就是要挖掘出強(qiáng)關(guān)聯(lián)規(guī)則。強(qiáng)關(guān)聯(lián)規(guī)則的生成取決于頻繁項(xiàng)目集，而頻繁項(xiàng)目集的挖掘算法正是關(guān)聯(lián)規(guī)則算法的核心所在。因此，深入研究關(guān)聯(lián)規(guī)則算法，并根據(jù)實(shí)際情況在應(yīng)用中選取最合適的算法對(duì)強(qiáng)關(guān)聯(lián)規(guī)則的生成非常重要。
摘要：利用基于密度的離群數(shù)據(jù)挖掘算法離群數(shù)據(jù)不在非離群數(shù)據(jù)指定的鄰域內(nèi)的特點(diǎn)，改進(jìn)了原有的離群數(shù)據(jù)挖掘算法：首先判斷數(shù)據(jù)是否在某個(gè)非離群數(shù)據(jù)指定的鄰域內(nèi)，如果不在，再判斷其鄰域內(nèi)數(shù)據(jù)的個(gè)數(shù)。通過(guò)對(duì)二維空間數(shù)據(jù)測(cè)試表明，改進(jìn)的算法能夠快速有效地挖掘出數(shù)據(jù)集中的離群數(shù)據(jù)，速度上數(shù)倍于原來(lái)的算法。
關(guān)鍵詞：數(shù)據(jù)挖掘；離群數(shù)據(jù)；基于密度
0引言
數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中發(fā)現(xiàn)正確的、新穎的、潛在有用并能夠被理解的知識(shí)的過(guò)程?，F(xiàn)有的數(shù)據(jù)挖掘研究大多集中在發(fā)現(xiàn)適用于大部分?jǐn)?shù)據(jù)的常規(guī)模式。但在一些應(yīng)用中，如電信和信用卡欺騙、藥物研究、氣象預(yù)報(bào)、電子商務(wù)、貸款審批、客戶分類、金融領(lǐng)域、網(wǎng)絡(luò)入侵檢測(cè)等領(lǐng)域有關(guān)例外情況的信息比常規(guī)模式更有價(jià)值。目前在數(shù)據(jù)挖掘中，對(duì)偏離常規(guī)模式的數(shù)據(jù)即離群數(shù)據(jù)的研究正得到越來(lái)越多的重視。
目前還沒(méi)有關(guān)于離群數(shù)據(jù)的統(tǒng)一的定義，這里采用Hawkins1980年給出的定義：離群數(shù)據(jù)是在數(shù)據(jù)集中與眾不同的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)并非產(chǎn)生于非隨機(jī)偏差，而是產(chǎn)生于完全不同的機(jī)制。離群數(shù)據(jù)的來(lái)源有兩類：錯(cuò)誤的數(shù)據(jù)，如錄入錯(cuò)誤、測(cè)量錯(cuò)誤等；數(shù)據(jù)真實(shí)性質(zhì)的反映，如一個(gè)公司的總裁的薪金遠(yuǎn)大于該公司一個(gè)普通員工的薪金等。所謂的離群數(shù)據(jù)挖掘指給定一個(gè)有n個(gè)數(shù)據(jù)點(diǎn)或數(shù)據(jù)對(duì)象的集合及預(yù)期的離群數(shù)據(jù)數(shù)目n′，發(fā)現(xiàn)與剩余數(shù)據(jù)相比顯著相異的、離群的或不一致的前n′個(gè)對(duì)象的過(guò)程[1]。
早期的統(tǒng)計(jì)分析領(lǐng)域的基于統(tǒng)計(jì)的離群數(shù)據(jù)挖掘其前提是待處理數(shù)據(jù)的分布特征是預(yù)先知道的（如正態(tài)分布、泊松分布等），這種方法需要知道數(shù)據(jù)的分布及分布的參數(shù)等；鄭斌祥等人[2]基于第k個(gè)最近鄰居的離群挖掘方法只針對(duì)時(shí)序數(shù)據(jù)，而且運(yùn)算性能也不甚理想；基于偏離的離群數(shù)據(jù)檢測(cè)方法是知道數(shù)據(jù)特性選取合適的相異函數(shù)，但序列離群數(shù)據(jù)在概念上仍然有一定的缺陷，遺漏了不少的離群數(shù)據(jù)，因而沒(méi)有得到普遍的認(rèn)可；基于規(guī)則的分類離群數(shù)據(jù)挖掘方法只適合于要求錯(cuò)誤數(shù)據(jù)少，分組粒度細(xì)的挖掘；基于距離的方法比較接近Hawkins對(duì)離群數(shù)據(jù)本質(zhì)的定義，它通過(guò)實(shí)驗(yàn)確定合適的基準(zhǔn)值和距離范圍，難以處理分類數(shù)據(jù)和周期性時(shí)態(tài)數(shù)據(jù)；基于密度的離群數(shù)據(jù)挖掘（DensityBased Outlier Mining，DBOM）的觀點(diǎn)比基于距離的離群數(shù)據(jù)挖掘的觀點(diǎn)更貼近Hawkins對(duì)離群數(shù)據(jù)本質(zhì)的定義，因此能夠檢測(cè)出基于距離離群數(shù)據(jù)挖掘算法所不能識(shí)別的一類離群數(shù)據(jù)，即局部離群數(shù)據(jù)，而局部離群數(shù)據(jù)拋棄了以前所有的離群數(shù)據(jù)定義中非此即彼的絕對(duì)離群數(shù)據(jù)概念，更加符合現(xiàn)實(shí)生活中的應(yīng)用。另外還有基于相似系數(shù)的方法、基于聚類的小波變換聚類的方法、高維空間聚類的方法等。本文首先描述了DBOM算法，而后對(duì)其進(jìn)行了改進(jìn)。
1基于密度的離群數(shù)據(jù)挖掘
1.1DBOM算法的基本概念
定義1以數(shù)據(jù)對(duì)象o為圓（球）心，半徑ε內(nèi)的區(qū)域稱為o的ε―鄰域。
定義2若數(shù)據(jù)對(duì)象C的ε―鄰域內(nèi)含有數(shù)據(jù)對(duì)象數(shù)目不少于Minpts個(gè)，則稱C為核心對(duì)象，能產(chǎn)生核心對(duì)象的ε是有意義的。其中，Minpts是一個(gè)可以人為設(shè)定的自然數(shù)。
定義3D是數(shù)據(jù)對(duì)象集合，p∈D，C∈D。對(duì)于給定的一個(gè)自然數(shù)Minpts，若C是核心對(duì)象，p在C的ε―鄰域內(nèi)，則稱p是從C出發(fā)關(guān)于ε和Minpts直接密度可達(dá)。
定義4D是數(shù)據(jù)對(duì)象集合，p∈D，p的ε―鄰域內(nèi)數(shù)據(jù)對(duì)象集合稱為p的ε擦謨蚣，記為Pε―set。
定義5D是數(shù)據(jù)對(duì)象集合，o∈D，對(duì)于任意一個(gè)核心數(shù)據(jù)對(duì)象C∈D，從C出發(fā)，都不能關(guān)于ε和Minpts直接密度可達(dá)并且|oε―set|≤Minpts，則稱o為關(guān)于ε和Minpts的基于密度的離群數(shù)據(jù)對(duì)象。
定義6D是數(shù)據(jù)對(duì)象集合，p∈D，若p的ε擦謨蚰諍有對(duì)象數(shù)目為零，則稱p是數(shù)據(jù)集D中關(guān)于ε鄰域的孤立點(diǎn)。
1.2DBOM算法的描述
基于密度的離群數(shù)據(jù)挖掘算法可以發(fā)現(xiàn)任意形狀的數(shù)據(jù)布局中的離群數(shù)據(jù)，它的基本思想是：對(duì)于數(shù)據(jù)集中的每一個(gè)離群數(shù)據(jù)對(duì)象，不能包含在任何一個(gè)給定半徑和該半徑鄰域內(nèi)包含指定數(shù)據(jù)對(duì)象數(shù)目的核心對(duì)象的鄰域內(nèi)?；诿芏鹊碾x群數(shù)據(jù)挖掘?yàn)榱税l(fā)現(xiàn)所有的離群數(shù)據(jù)，需要對(duì)每個(gè)數(shù)據(jù)進(jìn)行處理。DBOM首先從數(shù)據(jù)集D中任意找一數(shù)據(jù)對(duì)象p，并查找出D中p的關(guān)于半徑ε鄰域內(nèi)包含所有的鄰域?qū)ο螅魀的ε鄰域內(nèi)某一個(gè)數(shù)據(jù)對(duì)象的ε鄰域內(nèi)包含Minpts或多于Minpts個(gè)數(shù)據(jù)對(duì)象，則p不是離群數(shù)據(jù)；反之，若p的ε鄰域內(nèi)所有數(shù)據(jù)對(duì)象的ε鄰域內(nèi)包含的數(shù)據(jù)對(duì)象個(gè)數(shù)都少于Minpts，或者p的ε鄰域內(nèi)沒(méi)有數(shù)據(jù)對(duì)象即p是數(shù)據(jù)集D中關(guān)于ε鄰域的孤立點(diǎn)，則p是離群數(shù)據(jù)。接著處理數(shù)據(jù)集中的下一個(gè)數(shù)據(jù)，直至數(shù)據(jù)集中的所有數(shù)據(jù)都被處理完。相應(yīng)的算法描述如下：
2改進(jìn)的基于密度的離群數(shù)據(jù)挖掘IDBOM
上述的基于密度的離群數(shù)據(jù)挖掘算法能夠較好地挖掘出數(shù)據(jù)集中的離群數(shù)據(jù)，該算法的平均執(zhí)行時(shí)間復(fù)雜度為O（n2）（n為數(shù)據(jù)集中包含的數(shù)據(jù)對(duì)象數(shù)目）。它主要是通過(guò)對(duì)數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象進(jìn)行判斷，如果它的鄰域內(nèi)某一個(gè)數(shù)據(jù)對(duì)象是一個(gè)核心對(duì)象，即它包含在某一個(gè)核心對(duì)象的鄰域內(nèi)，該數(shù)據(jù)對(duì)象就不是離群數(shù)據(jù)，否則是離群數(shù)據(jù)。從離群數(shù)據(jù)的特征來(lái)看，離群數(shù)據(jù)往往是比較稀疏的、在數(shù)據(jù)集中所占比例比較小的數(shù)據(jù)因此，上述算法對(duì)每個(gè)數(shù)據(jù)及其鄰域內(nèi)的數(shù)據(jù)進(jìn)行相關(guān)判斷，顯然效率就比較低下。
定理1如果一個(gè)數(shù)據(jù)對(duì)象是核心對(duì)象，那么該數(shù)據(jù)的鄰域內(nèi)的數(shù)據(jù)都不是離群數(shù)據(jù)。
證明假設(shè)存在一個(gè)數(shù)據(jù)集D，C為D中關(guān)于ε和Minpts的核心數(shù)據(jù)對(duì)象，Cε―set為C的ε―鄰域集，那么對(duì)Cε―set中的任意一個(gè)數(shù)據(jù)對(duì)象p，都有d（C，p）≤ε，即從核心數(shù)據(jù)對(duì)象C出發(fā)，可以直接密度到達(dá)數(shù)據(jù)對(duì)象p，由定義5可知，數(shù)據(jù)對(duì)象p不是離群數(shù)據(jù)對(duì)象。
定理2某個(gè)數(shù)據(jù)對(duì)象是離群數(shù)據(jù)是其ε―鄰域內(nèi)數(shù)據(jù)對(duì)象的個(gè)數(shù)少于Minpts個(gè)的充分條件。
證明設(shè)存在一個(gè)數(shù)據(jù)集D，o為D中關(guān)于ε和Minpts的離群數(shù)據(jù)對(duì)象，oε―set為o的ε―鄰域集，由定義5可知，｜oε―set｜≤Minpts；假設(shè)在數(shù)據(jù)集的邊緣存在一個(gè)數(shù)據(jù)對(duì)象q∈｜qεset｜≤Minpts, C為數(shù)據(jù)集中一個(gè)核心數(shù)據(jù)對(duì)象，且有q∈Cε―set，根據(jù)定義5可知q不是離群數(shù)據(jù)對(duì)象。
基于上述定理，我們不對(duì)數(shù)據(jù)集中每個(gè)數(shù)據(jù)對(duì)象的鄰域內(nèi)判斷是否存在一個(gè)核心數(shù)據(jù)對(duì)象，而是只判斷鄰域內(nèi)數(shù)據(jù)對(duì)象個(gè)數(shù)少于Minpts個(gè)的數(shù)據(jù)對(duì)象的鄰域內(nèi)是否存在核心數(shù)據(jù)對(duì)象。如果某一個(gè)數(shù)據(jù)對(duì)象p是核心數(shù)據(jù)對(duì)象則將其及其鄰域內(nèi)的數(shù)據(jù)對(duì)象打上暫不運(yùn)算的標(biāo)簽及非離群數(shù)據(jù)的標(biāo)簽；反之按下述方式處理其鄰域內(nèi)的數(shù)據(jù)對(duì)象：若p的鄰域和某個(gè)核心數(shù)據(jù)對(duì)象C的鄰域數(shù)據(jù)對(duì)象交集不為空，那么判斷這些交集中的數(shù)據(jù)對(duì)象是否存在核心數(shù)據(jù)對(duì)象，若存在則p不是離群數(shù)據(jù)。如果和任何核心數(shù)據(jù)對(duì)象的ε擦謨蚪患為空或交集內(nèi)不含核心數(shù)據(jù)對(duì)象則p就是離群數(shù)據(jù)對(duì)象。改進(jìn)的算法描述如下：
3算法測(cè)試
這里對(duì)基于密度的離群數(shù)據(jù)挖掘算法進(jìn)行了測(cè)試，算法是用Matlab實(shí)現(xiàn)的，實(shí)驗(yàn)的環(huán)境是一臺(tái)P4 2.93G、內(nèi)存1GB的計(jì)算機(jī)，通過(guò)對(duì)網(wǎng)絡(luò)中心的某數(shù)據(jù)集進(jìn)行測(cè)試，在ε＝50和Minpts＝3的條件下，共挖掘出3個(gè)離群數(shù)據(jù)，經(jīng)過(guò)檢測(cè)，其中兩個(gè)離群點(diǎn)是由病毒造成的網(wǎng)絡(luò)不正常，另外一個(gè)是由于一個(gè)實(shí)驗(yàn)室進(jìn)行網(wǎng)絡(luò)對(duì)拷發(fā)送廣播報(bào)文引起的網(wǎng)絡(luò)堵塞造成的。其中優(yōu)化后的算法的運(yùn)算時(shí)間是優(yōu)化前的三分之一。在運(yùn)算的過(guò)程中發(fā)現(xiàn)，ε和Minpts取值不同，挖掘出的離群數(shù)據(jù)的個(gè)數(shù)也可能不同，這說(shuō)明了基于密度的離群數(shù)據(jù)挖掘算法對(duì)輸入?yún)?shù)有一定的敏感性。
