數據挖掘算法論文

序論：寫作是一種深度的自我表達。它要求我們深入探索自己的思想和情感，挖掘那些隱藏在內心深處的真相，好投稿為您帶來了一篇數據挖掘算法論文范文，愿它們成為您寫作過程中的靈感催化劑，助力您的創作。

數據挖掘算法論文:基于決策樹的數據挖掘算法研究

摘要：決策樹（Decision Tree）曾在很長的時間里是非常流行的人工智能技術，隨著數據挖掘技術的發展，決策樹作為一個構建決策系統的強有力的技術在數據挖掘和數據分析過程中起到了非常重要的作用。決策樹在數據挖掘中主要用于分類、預測以及數據的預處理等。

關鍵詞：決策樹；數據挖掘；Apriori算法

一、決策樹數據挖掘基本概念

數據分類是數據挖掘中的一個重要問題，是一種有效的KDD分析方法。數據分類通過分析訓練集中的數據，建立分類模型，然后利用這個分類模型，把數據庫中的數據項映射到給定類別中。

圖1.決策樹生成過程Decision tree formation process

決策樹分為分類樹和回歸樹兩種，分類樹針對離散數據集生成決策樹，回歸樹則針對連續變量生成決策樹。決策樹生成過程如圖1所示。

決策樹是一個類似于流程圖的樹結構，決策樹通過把實例從根節點排列到某個葉子節點來分類實例，葉子節點即為實例所屬的分類。樹上的每個節點說明了對實例的某個屬性的測試，并且該節點的每一個后繼分支對應于該屬性的一個可能值。

如圖2所示，給出了一個決策樹的示意描述樣例。該決策樹給了一個用于學生成績分析的模型。利用它可以分析學生成績受什么因素影響，以及會影響到與學生成績相關的那些屬性。決策樹的中間結點通常用矩形表示，而葉子結點常用橢圓表示。

圖2.決策樹示意描述Decision tree motioned description

二、決策樹算法

由于Apriori算法存在必須耗費大量時間處理規模巨大的候選項目集和必須多次掃描數據庫對候選項目集進行匹配篩選的固有缺陷，針對這些缺陷Han等人提出了一種基于FP-Tree的關聯規則算法FP-Growth算法。FP-Growth算法用一種壓縮的數據結構（FP-Tree）可存儲關聯規則挖掘所需的全部數據信息，通過對源數據的兩次掃描，將數據信息存到這種結構里，避開了產生候選項集的步驟，極大地減少了數據交換和頻繁匹配的開銷，這就是無候選項集產生算法（Frequent Patterns Growth，FP-Growth）。

（一）FP-Growth算法原理與相關概念。FP-Growth算法通過如下三方面的改進與創新，脫離了必須產生候選項集的傳統方式，開辟了關聯規則挖掘的新思路。

1.它構造了一種新穎的、緊湊的數據結構FP-Tree。它是一種擴展的前綴樹結構，存儲了關于頻繁模式數量的重要信息。樹中只包含長度為1的頻繁項作為葉節點，并且那些頻度高的節點更靠近樹的根節點，因此，頻度高的項比那些頻度低的項有更多的機會共享同一個節點。

2.開發了基于FP-Tree的模式片斷成長算法，它從長度為1的頻繁模式開始，只檢查它的條件模式基構建它的條件模式樹，并且在這個樹上遞歸地執行挖掘。模式的成長通過聯合條件模式樹新產生的后綴模式實現。由于事務處理中的頻繁項都對應著頻繁樹中的路徑進行編碼，模式的成長確保了結果的完整性。因此，FP-Tree算法不像Apriori類算法那樣需要產生再測試。挖掘的主要操作是計算累加值和調整前綴樹，這種花費通常要遠遠小于Apriori類算法中的候選項集的產生和模式匹配操作。

3.挖掘過程中采用的搜索技術是基于分區的，通過分割再解決的方法，而FP-Tree的結構包括一個標識成“null”的根、一個由頻繁項組成的頭表和一組項的前綴子樹組成了根的子孫。樹中的每個節點包括3個域：項名（itemname）、計數（count）和節點鏈接（node-link）。其中，項名記錄了節點所代表的項；計數記錄了樹中到達這個節點的路徑所代表的事務處理的數目；節點鏈接指向樹中下一個同名節點，如果沒有同名節點則指向空。頭表中的每條記錄包含兩個域：項名和節點鏈接的頭。節點鏈接的頭指向樹中第一個同名的節點。

（二）FP-Growth算法描述。與Apriori算法的不同，FP-Growth算法中頻繁項集的生成分為兩步進行，第一步是構造FP-Tree，第二步在第一步的基礎上對產生的FP-Tree進行挖掘以構造頻繁項集。

FP-Growth方法將發現長頻繁模式的問題轉換成遞歸地發現一些短模式，然后與后綴連接。它使用最不頻繁的項作后綴，提供了好的選擇性。該方法大大降低了搜索開銷。當數據庫很大時，構造基于內存的FP一樹是不現實的。一種有趣的替換是首先將數據庫劃分成投影數據庫的集合，然后在每個投影數據庫上構造FP一樹并挖掘它。該過程可以遞歸地用于投影數據庫，如果它的FP-Tree還不能放進內存。對FP-Tree方法的性能研究表明：對于挖掘長的和短的頻繁模式，它都是有效的和規?；模⑶掖蠹s比Apriori算法快一個數量級。它也比樹-投影算法快。樹-投影算法遞歸地將數據庫投影為投影數據庫樹。

FP-Growth算法開辟了有效挖掘頻繁模式的新途徑。然而，它的時間和空間效率還不足夠高，仍需進一步改進。

數據挖掘算法論文:數據挖掘中聚類算法比較及在武警網絡中的應用研究

摘 要：聚類算法是數據挖掘的核心技術,根據評價聚類算法優劣的幾個標準,對數據挖掘中常用聚類算法做了比較分析,根據各自特點,加以改進,并應用于武警部隊數據挖掘項目中。通過運用改進型Kmeans算法,取得了較好的挖掘結果,為進一步信息的智能化檢索、信息的過濾、分揀提供依據。

關鍵詞：數據挖掘;代表點聚類算法;基于密度的聚類算法;Kmeans聚類算法;指揮自動化

1 引 言

數據挖掘的歷史雖然較短,但從20世紀90年代以來,他的發展速度很快,是多學科綜合的產物。雖然目前還沒有一個完整的定義,但這里認為：數據挖掘就是從海量的數據中挖掘出可能有潛在價值的信息的技術。這些信息是可能有潛在價值的,支持決策,可以有效利用指揮自動化網,為進一步研究尋找突破口。

數據挖掘綜合了各個學科技術,其任務一般可分為2類：描述和預測。描述性挖掘任務刻劃數據庫中數據的一般特性。預測性挖掘任務在當前數據上進行推斷,以進行預測\[1\]。主要功能有分類和預測、聚類分析、關聯規則和序列模式的發現、偏差的檢測等。

把數據庫中的對象分類是數據挖掘的基本操作,根據最大化類內的相似性、最小化類間的相似性的原則進行聚類或分組,從而使屬于同一類的個體間距離盡可能小,而不同類個體間距離盡可能大,為了找到效率高、通用性強的聚類方法人們從不同角度提出近百種聚類方法,典型的有Kmeans方法、Kmedoids方法、CLARANS方法,BIRCH方法等,這些算法適用于特定的問題及用戶。

聚類算法一般分為分割和分層2種。分割聚類算法通過優化評價函數把數據集分割為K個部分,他需要K作為輸人參數。典型的分割聚類算法有Kmeans算法：Kmedoids算法、CLARANS算法。分層聚類由不同層次的分割聚類組成,層次之間的分割具有嵌套的關系。他不需要輸入參數,這是他優于分割聚類算法的一個明顯的優點,其缺點是終止條件必須具體指定。典型的分層聚類算法有BIRCH算法、DBSCAN算法和CURE算法等。根據評價聚類算法優劣的幾個標準\[2\],對常用的聚類算法進行比較分析。

(1) 是否適用于大數據量,算法的效率是否滿足大數據量高復雜性的要求;

(2) 是否能應付不同的數據類型,能否處理符號屬性;

(3) 是否能發現不同類型的聚類;

(4) 是否能應付噪聲數據或異常數據;

(5) 是否對數據的輸入順序不敏感。

2 數據挖掘常用聚類算法比較分析

2.1 BIRCH算法

BIRCH算法即平衡迭代削減聚類法,其核心是用一個聚類特征3元組表示一個簇的有關信息,從而使一簇點的表示可用對應的聚類特征,而不必用具體的一組點來表示。他通過構造滿足分支因子和簇直徑限制的聚類特征樹來求聚類。BIRCH算法通過聚類特征可以方便地進行中心、半徑、直徑及類內、類間距離的運算。算法的聚類特征樹是一個具有2個參數分枝因子B和類直徑T的高度平衡樹。分枝因子規定了樹的每個節點子女的最多個數,而類直徑體現了對一類點的直徑大小的限制即這些點在多大范圍內可以聚為一類,非葉子結點為他的子女的最大關鍵字,可以根據這些關鍵字進行插人索引,他總結了其子女的信息。

聚類特征樹可以動態構造,因此不要求所有數據讀人內存,而可以在外存上逐個讀人。新的數據項總是插人到樹中與該數據距離最近的葉子中。如果插人后使得該葉子的直徑大于類直徑T,則把該葉子節點分裂。其他葉子結點也需要檢查是否超過分枝因子來判斷其分裂與否,直至該數據插入到葉子中,并且滿足不超過類直徑,而每個非葉子節點的子女個數不大于分枝因子。算法還可以通過改變類直徑修改特征樹大小,控制其占內存容量。

BIRCH算法通過一次掃描就可以進行較好的聚類,由此可見,該算法適合于大數據量。BIRCH算法只適用于類的分布呈凸形及球形的情況,并且由于BIRCH算法需提供正確的聚類個數和簇直徑限制,對不可視的高維數據不可行。

2.2 CURE算法

CURE算法即使用代表點的聚類方法。該算法先把每個數據點看成一類,然后合并距離最近的類直至類個數為所要求的個數為止。CURE算法將傳統對類的表示方法進行改進,回避用所有點或用中心和半徑來表示一個類；而是從每一個類中抽取固定數量、分布較好的點作為描述此類的代表點,并將這些點乘以一個適當的收縮因子,使他們更靠近類的中心點。將一個類用代表點表示,使得類的外延可以向非球形的形狀擴展,從而可調整類的形狀以表達那些非球形的類。另外,收縮因子的使用減小嗓音對聚類的影響。CURE算法采用隨機抽樣與分割相結合的辦法提高算法的空間和時間效率,并且在算法中用堆和Kd樹結構來提高算法效率。

2.3 DBSCAN算法

DBSCAN算法即基于密度的聚類算法。該算法利用類的密度連通性可以快速發現任意形狀的類。其基本思想是：對于一個類中的每個對象,在其給定半徑的領域中包含的對象不能少于某一給定的最小數目。在DBSCAN算法中,發現一個類的過程是基于這樣的事實：一個類能夠被其中的任意一個核心對象所確定。為了發現一個類,DBSCAN先從對象集D中找到任意對象P,并查找D中關于關徑Eps和最小對象數Minpts的從P密度可達的所有對象。如果P是核心對象,即半徑為Eps的P的鄰域中包含的對象不少于Minpts,則根據算法,可以找到一個關于參數Eps和Minpts的類。如果P是一個邊界點,則半徑為Eps的P鄰域包含的對象少于Minpts,P被暫時標注為噪聲點。然后,DBSCAN處理D中的下一個對象。

數據挖掘算法論文:數據挖掘算法研究

摘 要：數據挖掘技術是一個不斷發現知識的過程。闡述了目前三種流行的數據挖掘算法的理論模型及算法思想，并從算法時間復雜度、依賴條件和誤差估計等方面進行了比較分析，說明了不同算法的優勢和不足。指出了不同算法的應用前景，提出了一種將不同算法結合以減少誤差率，提高算法效率的思路。

關鍵詞：數據挖掘； 關聯規則； 分類算法； 聚類算法

數據挖掘是指從海量的數據庫中抽取隱含的、具有潛在使用價值信息的過程。它是一種面向應用的技術，不僅針對特定數據庫進行簡單搜索查詢，且對數據進行微觀、中觀乃至宏觀的統計、分析、綜合和推理，進而發現潛在的知識。

數據挖掘的目的是發現知識，而知識發現的過程需要特定數據模型的支持，這使得數據挖掘算法成為研究的關鍵點。本文研究3種經典的數據挖掘算法，即關聯規則挖掘算法、分類算法和聚類算法，并對它們進行了比較分析，指出了各算法的應用前景。

1 關聯規則挖掘算法

關聯規則是通過用戶給定支持度和置信度來尋找規則的過程［1］?；舅枷氚?個過程：

（1） 發現最大頻繁項目集。

通過用戶給定的支持度，尋找數據集中支持度大于或等于給定支持度的所有項目集，即頻繁項目集，再從頻繁項目集中選出所有不被其他項目包含的頻繁項目集，即最大頻繁項目集。

（2） 生成關聯規則。

通過用戶給定的置信度，在發現最大頻繁的項目集中生成置信度大于或等于給定置信度的關聯規則。

思想中支持度是數據集D中包含項目集i1的事務在數據集D上的百分比，公式如下：

ИИSupporti1=|{t∈D&i1t}|/|D|（1）И

式中：t是數據集D上的一個事務。

置信度是指包含i1和i2的事務數與包含i1的事務數的支持度比值，公式如下：

ИИConfidencei1i2=Supporti1∪i2/Supporti1（2）И

式中：i1∩i2=0。

2 分類算法

分類是根據數據集的特點構造一個分類器，利用該分類器將數據集中的數據映射到給定類別中某一類的過程。主要分類算法有k-最鄰近算法、決策樹分類算法和貝葉斯分類算法。

2.1 k-最鄰近算法

k-最鄰近算法（kNN）是一種基于距離的分類算法，距離越近，相似性越大，距離越遠，相似性越?。?］。算法的基本思想是為：計算每個分類樣本到待分類元組的距離，即計算相似度，選取與待分類數據相似度最大的k個數據，將待分類元組劃分到這k個數據分類屬性最集中的類別中。

2.2 決策樹算法

決策樹算法采用自上而下的方法遞歸構造決策樹，分兩個步驟：決策樹生成和決策樹剪枝。典型的決策樹算法有ID3算法、C4.5算法等［3］。

2.2.1 決策樹生成算法

決策樹生成算法采用信息增益來選擇能使樣本最好分類的屬性，信息增益的計算如下：

有n個消息，概率分布為p=(p1,p2，…，pn)，則該樣本SУ鈉諭信息為：

ИI(S)=I(p)=－∑n1pilog2 pi （3）И

對于給定的樣本si∈S，其樣本總數為Si，根據類別屬性值將si劃分為m個子集，每個子集中所包含的樣本數分別為sij(1≤j≤m)，其概率分布為p=(Si1/Si,Si2/Si，…，Sim/Si)。根據公式得樣本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） 以代表訓練樣本的單個結點開始建樹。

（2） 如果樣本S都屬于同一個分類，則將該結點作為葉子結點。

（3） 否則，利用公式計算各個屬性的信息增益，比較計算所得的信息增益值，選取信息增益最大的屬性作為根結點。

（4） 遞歸劃分選取的根結點，直到下面3個條件之一滿足時結束： 給定結點的所有樣本屬于同一分類；沒有多余的屬性可以用來進一步劃分樣本，此時采用多數表決法來創建葉節點；分支屬性樣本為空。

2.2.2 決策樹剪枝算法

理想的決策樹分為3種：葉結點數最少；葉子結點深度最?。蝗~結點數最少，且葉子結點的深度最小［4］。在決策樹生成算法中沒有考慮噪聲等影響的因素，因此可能出現過度擬合現象，使分類預測性能降低，導致生成的決策樹不盡理想。為了避免過度擬合，提出了決策樹剪枝算法，該方法有預先剪枝和后剪枝2種。預先剪枝指在生成決策樹的同時，決定是繼續劃分還是停止劃分。預先剪枝的最大缺點是可能使樹的生長過早停止，導致生成的決策樹不完整，因此應用較少。后剪枝是一種先擬合后化簡的方法，首先采用決策樹生成算法對訓練樣本生成決策樹，然后從樹的葉子結點開始逐步向根的方向進行剪枝，具體的剪枝算法在本文不予以討論。

2.3 貝葉斯分類

貝葉斯分類以貝葉斯定理為基礎［5］，貝葉斯定理是：H為某種假定，P(H)為先驗概率，P(X|H)為H成立條件下X的概率，則后驗概率P(H|X)為：

ИP(H|X)=P(X|H)P(X) （6）И

貝葉斯分類的原理是通過某對象的先驗概率，利用貝葉斯定理計算出其后驗概率，即該對象屬于某一類的概率，選擇具有最大后驗概率的類作為該對象所屬的類。

算法的基本思想：

（1） 根據訓練樣本計算分類屬性的先驗概率P(ci)。

（2） 計算待分類數據每個非分類屬性的條件概率P(x|ci)。

（3） 由于各非分類屬性可視為條件獨立，故P(x|ci)=∏n1(xk|ci)。

（4） 利用式（6）計算ci的后驗概率。

因為P(x)和P(ci)是常數，所以P(x|ci)最大，則后驗概率最大，故將待分類數據劃分到P(x|ci)最大的ci所在類別中。

3 聚類方法

聚類就是將數據對象分成多個簇，簇內有較高的相似性，而簇間差異很大。典型的聚類分析方法有劃分方法和層次方法。

3.1 劃分方法

劃分方法依據數據點在幾何空間的距離來判斷個體間的相似度，距離越近就越相似，就越容易劃分為一類。劃分的原則是在同一個簇中的對象間有較高的相似性，而不同簇間差異很大。

3.1.1 k-平均算法

k-平均算法（k-means）是一種以簇內對象的均值為中心點的劃分方法［6］。算法用歐氏距離來表示點到簇的距離：

Иd(x,y)=∑k1(xi－yi)2 （7）И

算法的準則函數定義為：

ИE=∑k1∑x∈ci|x－xi| （8）И

算法基本思想：

（1） 隨機地選取k個對象，每個對象代表一個簇的初始中心。

（2） 根據式（7）計算剩余對象到中心點的歐氏距離，將每個對象賦給與其歐氏距離最小的簇，即最相似的簇。

（3） 重新選取每個簇的中心點，即重新計算簇內各點的平均值。

（4） 計算平方誤差和E，循環(1)，(2)，(3)直到準則函數E變化不明顯為止。

3.1.2 PAM算法

PAM算法是一種以簇中位置最中心的對象為中心點的劃分方法［7］。中心點被稱為代表對象，其他對象被稱為非代表對象。算法基本思想：

（1） 隨機地選取k個對象，每個對象代表一個簇的初始中心點。

（2） 根據中心點計算每個非中心點y到中心點x的絕對距離|y－x|，將每個對象賦給與其絕對距離最小的簇，即最相似的簇。

（3） 選擇一個未被選過的中心點oi及oi所在簇中的一個未被選過的非中心點oh，計算oh代替oi的總代價Tcih，并記錄在S中。

（4） 如果S中有小于0的記錄，則找出S最小，記錄的非中心點，并用該非中心點代替被選擇的中心點，重新組建k個劃分的簇。

（5） 如果S中所有的記錄都大于等于0，則不再劃分新的簇。

總代價為：Tcih=∑n1cjhi 。 其中n為所有節點數；cjhi表示oj在oi被oh代替后所產生的代價。每一個oi被oh代替后，對于非中心點oj，有四種情況需要考慮(如┩1~圖4所示)。

（1）oj當前在oi所在簇內，但oh代替oi后，oj被劃分到了中心點om所在的簇。此時cjhi=d(j,m)－d(j,i)。

（2） oj當前在oi所在簇內，但oh代替oi后，oj被重新劃分到了中心點oh所在簇，此時cjhi=d(j,h)－d(j,i)。

（3） oj當前在中心點om所在簇內，但oh代替oi后，oj被重新劃分到了中心點oh所在簇，此時cjhi=d(j,h)－d(j,m)。

（4） oj當前在中心點om所在簇內，但oh代替oi后，oj仍在中心點om所在簇，此時cjhi=0。

圖中實線為oh代替oi前oj的所屬關系，虛線為代替后oj的所屬關系。

3.2 層次方法

層次方法是根據某種給定的條件對數據集進行層次的分解，有凝聚和分裂2種方式［8］。

凝聚采用自底向上的策略，先將每個對象作為獨立的簇，然后合并各個簇，滿足用戶指定的終止條件時停止。凝聚方法有AGNES算法等。

分裂采用自頂向下的分類策略，先將所有對象作為一個簇，然后將該簇細分為越來越小的簇，滿足用戶指定的終止條件時停止。分裂方法有DIANA算法等。

3.2.1 AGNES算法

AGNES算法采用對象間的歐氏距離作為評價2個簇間距離的標準［9］。算法基本思想：

（1） 將每個對象作為獨立的初始簇。

（2） 將歐氏距離最小的2個對象所在簇進行合并，組成一個新的簇。

（3） 達到用戶指定的簇的數目時終止。

3.2.2 DIANA算法

DIANA算法以簇的直徑和平均相異度為劃分層次的標準［10］。其中，簇的直徑是指簇中任意兩對象間的最大歐氏距離，平均相異度指平均距離：

ИИdavg(Ci,Cj)=∑x∈Ci∑x∈Cj|x-y|/(ninj)И

式中：ni是Cj中包含屬性的個數;nj是Cj中包含屬性的個數。算法基本思想：

（1） 將所有對象作為一個整體劃分到同一個簇。

（2） 在所有簇中挑選出簇直徑最大的簇，并在該簇中選取一個與其他點平均相異度最大的點作為一個新簇，然后選取原簇中到新簇距離小于等于到原簇距離的點放入新簇中。

（3） 循環(2)直到滿足用戶指定簇的數目為止。

4 幾種算法的比較

關聯規則方法主要用于對事物數據庫進行數據挖掘，在商業領域使用得相對頻繁一些。分類和聚類方法則用于對關系數據庫進行數據挖掘，通過分析有屬性描述的數據庫元組來構造模型。

在實際應用過程中，不同方法有不同的優點和缺點。下面對本文提出幾種算法的時間復雜度、使用范圍、依賴條件、誤差估計進行比較，如表1所示。

表1 幾種算法比較

算法時間復雜度使用范圍依賴條件誤差估計

ApraoriO|Ck||Lk－1|k2小數據集最小支持度較小

kNNO(n)小數據集最臨近數目小

決策樹O(n×n)數據完整性較高的數據類別屬性較大且與評估函數有關

貝葉斯分類O(n×m)完全獨立數據和函數依賴數據先驗概率較小

k-平均O(n×k×t)簇密集數據且簇平均值可計算簇的數目k較大且與孤立點的數目有關

PAMO(k×s×s+k(n－k))小數據集簇的數目k小

AGNESO(n×n)n較小的數據簇的數目k較小

DIANAO(n×n)n較小的數據簇的數目k較小

從表1可以看出，不同算法在不同應用上有各自的優缺點。如kNN算法時間復雜度最小，然而僅限于小數據集，對于數據集較大的情況，則可選用決策樹和貝葉斯分類；k-平均算法對簇密集型數據有很高的效率。在實際應用中可以根據需要將幾種算法結合，以達到更高的效率。

5 結 語

數據挖掘使信息處理技術從簡單的數據存儲轉入更為高級的知識發現階段，它正以一種全新的理念改變著人類信息管理方式。本文分析了3種數據挖掘算法的基本思想，并對不同算法進行了比較，指出了各算法的優缺點及使用范圍，并展望了各算法對不同特征數據集的應用前景。

數據挖掘算法論文:基于粗糙集和遺傳算法的數據挖掘方法

摘要：運用粗糙集和遺傳算法的理論，為大型的數據挖掘提供了一種新的方法。首先通過粗糙集理論對數據進行預處理，然后對屬性簡約，最后通過遺傳算法進行規則提取，尋找最優解。

關鍵詞：粗糙集；遺傳算法；數據挖掘；知識發現

數據挖掘[1]又稱知識發現，是從大量的、不完全的、有躁聲的、模糊的實際數據中，提取隱含在其中的、人們事先不知道的、但又很有用的知識和信息的過程。它的一般步驟如下：提出問題->數據準備->數據整理->建立模型->評價和解釋。它是數據庫研究、開發和應用最活躍的一個分支，是多學科的交叉領域，涉及數據庫技術、人工智能、機器學習、神經網絡、數學、統計學、模式識別、知識庫系統、知識獲取、信息提取、高性能計算、并行計算、數據可視化等多方面的知識。

1 粗糙集與遺傳算法的基本概念

粗糙集(Rough Set, RS)[2]作為一種全新的數學概念,為處理具有不完整、不一致及不確定性特征的信息提供了新的有效工具,它的主要特點之一是無須提供問題所需處理的數據集合之外的任何先驗信息。相對于許多其他處理不確定知識的方法來說更具客觀性,并且和其他分析方法有機結合,進一步增強對不確定問題的處理能力。

定義1：信息系統S可表示為S=(U,A,V,f),其中U是對象的非空有限集合,稱為論域;A是屬性的非空有限集合;V=∪a∈AVa,Va是屬性A的值域,f:U×AV是一個信息函數,他為每個對象的每個屬性賦予一個信息值。

如果屬性集A可以分為條件屬性集C和決策屬性集D ,即C∪D = A ,C∩D =Ф,則該信息系統稱為決策系統或決策表,其中D 一般只含有一個屬性。

定義2：在知識表達系統S 中,對于一屬性集P∈A,對象x,y∈U,二元等價關系IND(P) ={(x,y)∈U×U | 所有的a∈P, f(x,a)=f(y,a)}稱為S 的不可分辨關系。不可分辨關系是一個等價關系,通過一個不可分辨關系,可以得到一個決策系統的劃分。

定義3：給定信息系統S=(U,A),B∈A ,對B中的屬性a,如果IND(B)≠IND(B-{a}),則說屬性a是必要的(Indispensable),否則稱a是不必要的(Dispensable)。

遺傳算法( Genetic Algorithm, GA)[3]起源于對生物系統進行的計算機模擬研究，是模擬生物在環境中的遺傳和進化過程而形成的一種自適應優化概率搜索算法。它的流程主要模仿的 是生物遺傳進化過程中的選擇、交叉和變異操作，從而完成對問題最優解的自適應搜索過程。流程主要包括染色體編碼、產生初始群體、計算適應度、進化操作等幾大部分。

遺傳算法的搜索過程是從一群初始節點開始搜索,而不是從單一的初始點開始搜索,這種機制意味著搜索過程可以有效地跳出局部極值點。既可以完成極值點領域內解的求精,也可以在整個問題空間實施探索,得到問題全局最優解的概率大大提高。

2 粗糙集與遺傳算法在數據挖掘中的應用

粗糙集算法與遺傳算法結合,能有效地提高挖掘效果,具有實際應用的可行性。其基本思想是：首先通過粗糙集對信息表中的數據缺損進行處理；然后對于信息表中的數據，根據已定義的可辯識距陣，通過屬性簡約算法進行屬性簡約和知識發現；最后對知識發現的規則通過遺傳算法進行優化，找出最主要的規則。主要包括以下幾個方面：

2.1 數據預處理

數據預處理用于對原始數據的采樣、收集、整理，對于不同途徑獲取來的數據不一定能夠得到有效的信息，所以數據的預處理是非常必要的。包括連續屬性的離散化和不完備數據的填補，由于粗糙集只能處理離散的數據，所以還必須對連續的數據離散化，而屬性離散化的關鍵在于選取合適的斷點對條件屬性進行劃分[4]，如可采用基于屬性重要性的離散化算法。由于數據采集的不完整性，使數據庫中很大一部分數據都存在缺失，因此對輸入的數據必須進行必要的處理如采用均值法、頻率統計法等對數據進行補齊。

2.2 屬性簡約

粗糙集處理決策表時，數據約簡是核心內容，一般是約去過剩的條件屬性，用最少的屬性區分不同的決策，提供同樣多的信息，使決策表的決策屬性和條件屬性的依賴關系不發生變化。簡約后的屬性集稱為屬性的約簡集，約簡集通常不唯一，找到一個信息表中的約簡集不是在一個多項式時間里能夠解決的問題，求最小約簡集（含屬性個數最少的約簡集）同樣是一個困難的問題，實際上它是一個NP-hard問題，因此根據已定義的可辯識距陣，有如下的屬性簡約算法：

① 計算屬性表的可辯識距陣。

② 對于可辯識距陣中的所有取值為非空集合的元素Cij建立相應的析取邏輯表達式。

③ 將所有析取邏輯表達式進行合取運算，得到一個合取范式。

④ 將合取范式轉換為析取范式形式。

⑤ 輸出屬性約簡結果，其中析取范式中的每個合取項對應一個屬性約簡的結果，每個合取項中所包含的屬性組成的約簡后的條件屬性集合。

2.3 決策規則提取

經過第二步屬性簡約后，屬性個數減少了，但是得出的規則數量依然可能過多，不利于得到用戶最想要，最重要的規則，因此我們會更希望關心具有較多共同特性的規則，必須把簡約后生成的規則集里那些具有大量共同特征的規則再次提取出來，面對這種優化問題，遺傳算法是個強有力的工具。其步驟是編碼產生原始種群，計算個體適應度，選擇個體，交叉，變異操作，然后一代一代進化最后找出最優解。

（1）編碼，是進行遺傳算法的重要步驟，編碼方案的選取很大程度上決定于問題的性質和要求，同時也決定了對隨后的遺傳算子的設計。如可以將數據離散化后的屬性值定義在2的n次方之間[5]，采用二進制編碼方法對每個數字編碼，像屬性值3用編碼表示就是0011；

（2）產生初始種群。隨機選取一些個體作為初始種群；

（3）確定評價函數。數據挖掘的目的是挖掘出具有最多相同特征的規則，因此評價函數的選取時應當把能夠匹配簡約表中最多的屬性的規則評價為最優規則；

（4）遺傳操作。交叉操作是將規則編碼的某幾位互相置換，變異操作是將規則編碼的某些二進制位按位取反。這樣通過規則集中任意的兩兩組合會形成新的規則集。然后經過每個規則的評價函數確定當前的最優規則，這樣經歷數代遺傳之后就可得到相對最優的規則。

3 公司錄取情況數據挖掘應用實例

下面用一個實例來說明本文使用的數據挖掘方法。某公司每年都會收到大量的求職信息表，并從中雇用一定數量的員工，對于員工的雇用，公司以往都是通過面試及給領導的感覺來雇用的，因此公司希望能夠從以前的錄用中找出一個大體的評判標準以便于以后錄用時作為參考，由于以往幾年累計求職的員工太多，情況比較復雜，因此公司希望這個標準能夠簡單明了。通過本文提出的方法，可以很好的解決該公司的需求，以下以該公司求職人員的原始求職表中的一部分作為演示，“?”代表求職表中該屬性沒有寫明情況，如表1所示：

按屬性簡約的算法，通過決策表的可辯識距陣，我們可以得到算法第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)

其中每一個析取項對應于可辯識距陣中的一個元素，d，e，f，a分別對應屬性學歷、經驗、法語、儀表，按算法第4步簡化后可以得到F(d,e,f,a)=(e∧a) ∨(e∧d)。由此可見，在原始決策表給出的這部分信息中與決策有關的是d，e，a。

通過粗糙集的屬性約簡，可以得到以往公司錄用時真正看重的一些屬性，通過這些屬性，再用遺傳算法找出其中最主要的規則。例如約簡表中某一行在學歷、經驗、儀表上的值為201，則編碼就是10,00,01。隨機選取8個個體作為初始種群，評價函數以能夠匹配約簡表中最多行屬性的規則成為當代的最優規則。

算法定義為一個8元組：

SGA=（C，E，P0，M，Ф，Г，Ψ，T）

C表示對個體采用二進制編碼；E表示個體適應度評價函數f(x)；P0表示初始種群隨機選取的8個規則；Ф表示采用輪盤賭按比例選擇算子；Г表示中間位單點交叉算子；Ψ表示基本位變異算子；T表示執行20代上述遺傳算法后停止。

最后得到最佳個體00,01,01，即學歷MBA，經驗水平一般，儀表良好的評判標準，凡在此標準附近或高于此標準的，可以考慮錄用。

4 結語

在數據挖掘中應用粗糙集和遺傳算法，粗糙集可以解決數據不精確、不完整的問題，并進行屬性簡約，遺傳算法可以從大量規則中提取出最優的規則，提高了分析系統的效率。本文將粗糙集和遺傳算法在數據挖掘中相結合，給出實例說明該方法的可行性。在今后的研究中還將繼續結合其他的方法進行研究，提高對知識的發現能力。

數據挖掘算法論文:數據挖掘分類算法研究與探討

摘要：數據挖掘技術是一個年輕且充滿希望的研究領域，商業利益的強大驅動力將會不停地促進它的發展。隨著數據庫應用的不斷深化，數據庫的規模急劇膨脹，數據挖掘已成為當今研究的熱點，每年都有新的數據挖掘方法和模型問世，特別是其中的分類問題，引起了越來越多的關注。

關鍵詞：數據挖掘；分類；算法

隨著計算機技術特別是數據庫技術的迅猛發展，以及人類活動范圍的擴展、生活節奏的加快，人們能以更快速更容易更廉價的方式獲取和存儲數據，這就使得數據及其信息量以指數方式增長。面對這些極度膨脹的數據，人們受到“信息爆炸”和“數據過?！?Data Glut)的巨大壓力。這些海量數據如果不能有效利用起來，將只會成為“數據垃圾”。對人類社會進步起到巨大作用的是知識。 數據挖掘就是從大量數據中發現潛在規律、提取有用知識的方法和技術[1]。數據挖掘包含的內容很多，其中很重要的一個方面是分類規則挖掘。

分類技術在很多領域都有應用，例如可以通過客戶分類構造一個分類模型來對銀行貸款進行風險評估；當前的市場營銷中很重要的一個特點是強調客戶細分。客戶類別分析的功能也在于此，采用數據挖掘中的分類技術，可以將客戶分成不同的類別，比如呼叫中心設計時可以分為：呼叫頻繁的客戶、偶然大量呼叫的客戶、穩定呼叫的客戶、其他，幫助呼叫中心尋找出這些不同種類客戶之間的特征，這樣的分類模型可以讓用戶了解不同行為類別客戶的分布特征；其他分類應用如文獻檢索和搜索引擎中的自動文本分類技術；安全領域有基于分類技術的入侵檢測等等。機器學習、專家系統、統計學和神經網絡等領域的研究人員已經提出了許多具體的分類預測方法。下面對幾種主要的分類方法作簡要的研究與探討：

1 基于判定樹的歸納分類

判定樹是一個類似流程圖的樹結構，其中每個內部節點表示在一個屬性上的測試，每個分支代表一個測試輸出，而每個樹葉節點代表類或類分布。樹的最頂層節點是根節點。由判定樹可以很容易得到“IF-THEN”形式的分類規則。方法是沿著由根節點到樹葉節點的路徑，路徑上的每個屬性-值對形成“IF”部分的一個合取項，樹葉節點包含類預測，形成“THEN”部分。一條路徑創建一個規則。判定樹歸納的基本算法是貪心算法。

算法描述如下：判定樹歸納分類[2]是一種從訓練樣本集中推理出判定樹表示形式的分類規則的方法。它采用自頂向下的遞歸方式，判定樹的最頂節點是根結點，樹的內部結點表示在一個屬性上的測試，從該結點向下的每個分支代表一個測試輸出，在樹的葉結點得到分類預測。從根到葉結點的一條路徑就對應著一條合取規則，整棵判定樹就對應著一組析取表達式規則。判定樹的優點在于它的直觀性和易理解性，判定樹方法不僅能做出分類和預測，而且它的生成過程、分類、預測以及從判定樹所提取的分類規則都具有很強的可理解性。

算法策略如下：①判定樹以代表訓練樣本的單個節點開始；②如果樣本都在同一個類，則該節點成為樹葉，并用該類標記；③否則，基于啟發式或統計式策略選擇能夠最好地將樣本分類的屬性，將樣本分類；④對測試屬性的每個已知的值，創建一個分枝，并以此為根據劃分樣本；⑤使用同樣的過程，遞歸地形成每個劃分上的樣本判定樹。

停止劃分的條件：給定節點的所有樣本屬于同一類：沒有剩余屬性可以用來進一步劃分樣本，此時使用多數表決(用訓練集中的多數所在的類標記它)；沒有樣本剩余。

2 KNN法(K-Nearest Neighbor)

KNN(K Nearest Neighbors)算法[3]又叫K最臨近方法，總體來說KNN算法是相對比較容易理解的算法之一，假設每一個類包含多個樣本數據，而且每個數據都有一個唯一的類標記表示這些樣本是屬于哪一個分類，KNN就是計算每個樣本數據到待分類數據的距離，取和待分類數據最近的K各樣本數據，那么這個K個樣本數據中哪個類別的樣本數據占多數，則待分類數據就屬于該類別。

KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。另外還有一種Reverse KNN法，能降低KNN算法的計算復雜度，提高分類的效率。

該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。

3 VSM法

VSM法即向量空間模型(Vector Space Model)法，由Salton等人于60年代末提出。這是最早也是最出名的信息檢索方面的數學模型。其基本思想是將文檔表示為加權的特征向量：D=D(T1,W1;T2,W2;…;Tn,Wn)，然后通過計算文本相似度的方法來確定待分樣本的類別。當文本被表示為空間向量模型的時候，文本的相似度就可以借助特征向量之間的內積來表示。

在實際應用中，VSM法一般事先依據語料庫中的訓練樣本和分類體系建立類別向量空間。當需要對一篇待分樣本進行分類的時候，只需要計算待分樣本和每一個類別向量的相似度即內積，然后選取相似度最大的類別作為該待分樣本所對應的類別。

由于VSM法中需要事先計算類別的空間向量，而該空間向量的建立又很大程度的依賴于該類別向量中所包含的特征項。根據研究發現，類別中所包含的非零特征項越多，其包含的每個特征項對于類別的表達能力越弱。因此，VSM法相對其他分類方法而言，更適合于專業文獻的分類。

4 Bayes法

Bayes法是一種在已知先驗概率與類條件概率的情況下的模式分類方法，待分樣本的分類結果取決于各類域中樣本的全體。

設訓練樣本集分為M類，記為C={c1,…,ci,…cM}，每類的先驗概率為P(ci)，i=1,2,…,M。當樣本集非常大時，可以認為P(ci)=ci類樣本數/總樣本數。對于一個待分樣本X，其歸于cj類的類條件概率是P(X/ci)，則根據Bayes定理，可得到cj類的后驗概率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）式是最大后驗概率判決準則，將（1）式代入（2）式，則有：

若P(x/ci)P(ci)=Maxj[P(x/cj)P(cj)]，i=1,2,…,M,j=1,2,…,M，則x∈ci，這就是常用到的Bayes分類判決準則。經過長期的研究，Bayes分類方法在理論上論證得比較充分，在應用上也是非常廣泛的。

Bayes方法的薄弱環節在于實際情況下，類別總體的概率分布和各類樣本的概率分布函數(或密度函數)常常是不知道的。為了獲得它們，就要求樣本足夠大。另外，Bayes法要求表達文本的主題詞相互獨立，這樣的條件在實際文本中一般很難滿足，因此該方法往往在效果上難以達到理論上的最大值。

5 神經網絡

人工神經網絡的研究至今已有60多年的歷史。1943年，心理學家McCulloch和數學家Pitts合作，提出了形式神經元的數學模型，即MP模型[4]，從此，神經網絡引起了許多科學家的興趣。但隨著對感知機為代表的神經網絡的功能和局限性的深入分析等原因，使神經網絡的研究陷入低潮。但是仍有一些學者堅持研究，并取得了一些成果，出現了Grossberg的ART模型和Kohonen的SOM模型。1982年，通過引入能量函數的概念，Hopfied研究了網絡的動力學性質，并用電子線路設計出相應的網絡，進而掀起了神經網絡新的研究高潮。1986年，Rumellhart和McCllel-land等提出了PDP理論，尤其是發展了多層前向網絡的BP算法，成為迄今應用最普遍的學習算法。

神經網絡可解決目前數據挖掘存在幾個方面的問題：

1) 數據的量度和維度，面對大量復雜、非線性、時序性與噪音普遍存在的數據；

2) 數據分析的目標具有多樣性，使其在表述和處理上都涉及到領域知識；

3) 在復雜目標下，對海量數據集的分析，目前還沒有現成的且滿足可計算條件的一般性理論的方法。然而，神經網絡在對噪聲數據的高承受能力以及對未經訓練的數據分類模式的能力方面有很大優勢。因此設計出基于神經網絡的數據挖掘方法，并將其用于真實世界問題，是可行且也是必要的。

人工神經網絡可用于數據挖掘的分類、聚類、特征挖掘、預測和模式識別等方面，因此，人工神經網絡在數據挖掘中占有舉足輕重的作用。

總之，數據挖掘技術是一個年輕且充滿希望的研究領域，商業利益的強大驅動力將會不停地促進它的發展。每年都有新的數據挖掘方法和模型問世，人們對它的研究正日益廣泛和深入。盡管如此，數據挖掘技術仍然面臨著許多問題和挑戰：如數據挖掘方法的效率亟待提高，尤其是超大規模數據集中數據挖掘的效率；開發適應多數據類型、容噪的挖掘方法，以解決異質數據集的數據挖掘問題；動態數據和知識的數據挖掘；網絡與分布式環境下的數據挖掘等；另外，近年來多媒體數據庫發展很快，面向多媒體數據庫的挖掘技術和軟件今后將成為研究開發的熱點。

數據挖掘算法論文:數據挖掘技術及算法綜述

摘要:數據挖掘是目前非常熱門的一門交叉學科,涉及到很多學科的研究領域。文中對數據挖掘的概念、實施步驟及各種算法進行了比較詳細的歸納,并且對數據挖掘技術將來的研究方向也進行了預測。

關鍵詞:數據挖掘;聚類算法;關聯規則;決策樹;遺傳算法

1 引言

數據挖掘是一個多學科的交叉領域,這些學科包括數據庫技術、機器學習、統計學、模式識別、信息檢索、神經網絡、基于知識的系統、人工智能、高性能計算和數據可視化等[1]。目前,對于數據挖掘方面的研究已經取得了很大的進展,開發出了許多新的數據挖掘算法、系統和應用。本文將先對數據挖掘的概念及實施步驟進行說明,然后將分類歸納數據挖掘中的各種常見算法,最后對數據挖掘目前的研究方向進行預測。

2 數據挖掘的概念及流程

2.1 數據挖掘的概念

簡單地說,數據挖掘就是從大量的數據中“挖掘”知識,即從大量的、不完全的、有噪聲的、模糊的、隨機的數據中,提取隱含在其中的、人們事先不知道、但又是潛在有用的信息和知識的過程。它是一種決策支持過程,可以從企業數據庫的大量數據中,挖掘出潛在的模式,預測客戶的行為,幫助企業的決策者做出正確的判斷,從而減少投資的風險,獲得更大的利潤。

2.2 數據挖掘的流程

一般來講,數據挖掘的整個過程由五個步驟組成:

1) 數據挖掘的最后結果是不可預測的,但是要探索的問題應該是有預見的,為了數據挖掘而進行數據挖掘,是不可取的。因此,清晰地定義出業務問題,認清數據挖掘的目的是數據挖掘的第一步,也是很重要的一步。

2) 數據準備[2],數據準備又可以分成數據選擇,數據預處理,數據轉化三個步驟。數據選擇,是從大量與業務對象有關的數據中選擇出適合進行數據挖掘的數據;數據預處理,包括進行數據清洗,數據推測,數據轉換等。數據清洗,指的是清除掉一些明顯的噪聲數據,提高數據的質量;數據推測,是因為在前面兩步中,也許會出現數據不全的情形,所以進行適當的推算,補齊所需的數據;數據轉換,是將數據轉換成一個分析模型,這個分析模型是針對數據挖掘算法建立的,建立一個真正適合挖掘算法的分析模型是數據挖掘成功的關鍵;數據轉化,則是在做完前面的步驟以后,適當的縮減即將進行分析的數據庫規模,以上這些工作會直接影響到數據挖掘時的效率和準確性,同樣很重要。

3) 數據挖掘,這是整個數據挖掘過程中最重要的一步,即使用適當的數據挖掘算法對剛才處理出的數據進行分析,進而得到可能的模式模型。根據不同數據的特點以及用戶不同的需求,對同樣的任務,可以選用不同的算法,目前常見的算法包括聚類算法、關聯分析、分類算法、遺傳算法等。

4) 結果評價,通過上述步驟得到的模式模型,并不一定是真實有效的,甚至可能會是和實際情況完全相反的,所以還需要對得到的結果進行評價。這一步使用的方法包括用數據代入進行驗證,也可以根據常規的經驗進行一些判斷,一般由數據挖掘具體操作而定。如果沒有得到合適的模式模型,就需要重新選擇數據,甚至需要選用其他的數據挖掘算法,因此,數據挖掘的過程往往都是一個不斷反復的過程。

5) 知識同化,完成上述步驟后,如果得到了可以接受的模式模型,就需要進一步把得出的模型形象化,運用到所需的信息系統中去。

3 數據挖掘的常見算法

數據挖掘常用的分析方法包括聚類算法(Cluster Algorithm)、關聯規則(Association Rules)、決策樹算法(Decision Tree Algorithm)、遺傳算法(Genetic Algorithm)等。

3.1 聚類算法

聚類是一種常見的數據分析工具,其目的是把大量數據點的集合分成若干類,使得每個類中的數據之間最大程度的相似,而不同類中的數據最大程度的不同。常見的聚類算法主要包括層次聚類算法(Hierarchical Clustering Method)、分割聚類算法 (Partitioning Clustering Method)、基于密度的方法(Density-Based Methods)、基于網格的方法(Grid-Based Methods)等[3]。

1) 層次聚類算法,是通過將給定的數據集組織成若干組數據,并形成一個相應的樹狀圖,進行層次式的分解,直到某種條件滿足為止,具體又可分為“自底向上”和“自頂向下”兩種算法[4]。這兩種算法的思路正好相反,前者是將每個對象都作為一個原子聚類,再進行聚合,最后得到相應的結果,而后者是將所有對象看成一個聚類,再進行分解。CURE算法、CHAMELEON算法、BIRCH算法等是比較常用的層次聚類算法。

2) 分割聚類算法,是先將數據集分成k個分組,每一個分組就代表一個聚類,然后從這k個初始分組開始,然后通過反復迭代的方法改變分組,使得每一次改進之后的分組方案都較前一次好,最終使同一分組中的記錄越來越近,不同分組中的記錄原來越遠,從而得到最優解。使用這一思想的主要算法有K-means算法、K-medoids算法、CLARANS算法等。

3) 基于密度的方法與其它方法的最要區別在于:它不基于各種距離,而是從數據對象的分布密度出發,將密度足夠大的相鄰區域連接起來,從而可以發現具有任意形狀的聚類,并能有效處理異常數據,它的代表算法有DBSCAN算法、OPTICS算法、DENCLUE算法等。

4) 基于網格的方法則是從對數據空間劃分的角度出發,利用屬性空間的多維網格數據結構,將數據空間劃分為有限空間的單元,以構成一個可以進行聚類分析的網格結構。該方法的主要特點是處理時間與數據對象的數目無關,但與每維空間劃分的單元數相關,而且,這種方法還與數據的輸入順序無關,可以處理任意類型的數據,但是聚類的質量和準確性降低了,它的代表算法有STING算法[5]和CLIQUE算法等。

3.2 關聯規則

關聯規則是數據挖掘研究的重要內容,它描述了數據庫中一組對象與另一組對象之間存在的某種關聯關系。從大量商業記錄中挖掘有趣的關聯關系,有助于許多商務決策的制定,如分類設計、交叉購物等。關聯規則是形如A=>B的蘊涵式,表示形式如pen=>ruler [支持度=20%,置信度=60%],支持度和置信度分別反映規則的有用性和確定性,這條規則就意味著所有的顧客中有20%的人同時購買了鋼筆和直尺,而買了鋼筆的顧客的60%也買了直尺。在關聯規則中,所有支持度大于最小支持度的項集稱為頻繁項集,簡稱頻集。如果一條關聯規則同時滿足最小支持度閾值和最小置信度閾值,就認為它是有趣的,并稱為強關聯規則。

關聯規則挖掘一般分為兩步:1) 找出所有頻繁項集,即滿足最小支持度的項集;2) 從頻繁項集中產生強關聯規則。最為著名的關聯規則挖掘算法就是R.Agrawal和R.Srikant于1994年提出的挖掘布爾關聯規則中頻繁項集的原創性算法Apriori。它使用一種稱作逐層搜索的迭代方法,k項集用于探索(k+1)項集。首先,通過掃描數據庫,累積每個項的計數,并收集滿足最小支持度的項,找出頻繁1項集的集合。該集合記作L1。然后,L1用于找頻繁2項集的集合L2,L2用于找L3,如此下去,直到不能找到頻繁k項集。找每個Lk需要一次數據庫全掃描。

但是,Apriori算法也有其不足之處:1) 可能產生大量的候選集;2) 生成每個Lk都需要重復掃描數據庫。后來,陸續出現了一系列Apriori算法的改進算法,以及其他的關聯規則挖掘算法,比如RIApriori算法、Apriori-improve算法、FP-growth算法等,這大大提高了關聯規則挖掘的速度和準確性,也推動了關聯規則挖掘理論的進一步發展。

3.3 決策樹算法

決策樹是一種類似于流程圖的樹結構,每個內部節點(非樹葉節點)表示在一個屬性上測試,每個分支代表一個測試輸出,而每個樹葉節點(或終節點)存放一個類標號。決策樹算法主要圍繞決策樹的兩個階段展開:第一階段,決策樹的構建,通過遞歸的算法將訓練集生成一棵決策樹;第二階段,由測試數據檢驗生成的決策樹,消除由于統計噪聲或數據波動對決策樹的影響,來達到凈化樹的目的,得到一棵正確的決策樹。常見的決策樹算法主要有ID3算法[6]、C4.5算法、CART算法、SPRINT算法等。

3.4 遺傳算法

遺傳算法是基于進化理論,并采用遺傳結合,遺傳變異,自然選擇等設計方法的一種進化計算算法的優化算法。進化計算算法的基礎是生物進化,隨著時間的流逝,進化出更好的或更適應的個體。在數據挖掘中,遺傳算法可以用于評估聚類、關聯規則等算法的適合度。在應用遺傳算法解決問題時,最困難的一步應該是怎樣將問題建模成一組個體的集合,然后在計算中,首先假設一個初始模型,然后對其反復進行雜交技術和變異技術的算法,最后用適應度函數確定初始集合中應該保留的那個最優個體。這個算法的優點在于容易并行化,但是對問題進行建模很困難,雜交變異過程以及適應度函數也很難確定。

4 結束語

隨著數據量的積累和數據庫種類的多樣化,數據挖掘的應用前景非常的廣闊,從上面對各種常見算法的歸納可以看出,每種算法都有局限性,很難采用單一的方法解決相應的問題,因此,多方法融合將成為數據挖掘未來的發展趨勢。

數據挖掘算法論文:遺傳算法與網絡數據挖掘

摘要:計算機網絡發展迅速,網絡數據挖掘已經成為一個重要的研究領域。網絡數據分布范圍廣,數據量大,結構多樣,時間跨度高。如何對這些海量數據進行高效查詢成為研究人員關注的問題。遺傳算法在搜索的過程中采用群體搜索方式,有利于得到最優查詢結果。在數據查詢、查詢優化和分布式數據挖掘等方面使用遺傳算法,能夠從不同角度大大提高查詢效果。

關鍵詞:網絡數據挖掘;遺傳算法;查詢優化

隨著萬維網使用越來越廣泛,網絡數據挖掘已成為一個重要的科學研究領域,得到越來越多的科研人員的重視。設計算法從已有信息中發掘新知識,根據用戶情況定制信息,學習用戶行為是網絡數據挖掘所面臨的主要問題。

在網絡工具中結合使用人工智能可消除網絡檢索中的人為因素。在客戶端和服務器端分別安裝智能系統,使計算機通過Internet在Web服務器上進行高效的知識發掘。通過網絡服務器檢索知識已經引起機器學習、人工智能等領域學者的普遍注意。然而,網絡數據數量大、分布地域廣泛、類型差異大,要開發一個智能工具對這樣的數據進行檢索難度很大。

網絡挖掘技術在智能網絡的發展中發揮著重要的作用。網絡數據具有多樣性、分布廣泛等特點,按照現有的算法對網絡數據進行搜索具有相當局限性。與其他傳統的優化算法相比,遺傳算法在搜索的過程中采用群體搜索方式,有利于達到全局最優。遺傳算法可采用和進化出更優的復合目標函數,以便在動態而負責的網絡環境中實現高效的數據檢索和知識預測。A.Broder等人將網絡看作是一個由無數網頁組成的集合S,這些網頁構成鄰接關系,使用適應性函數f實現對這些網頁的評估[1]。

f:SR+

搜索引擎通過f函數的最優值輸出搜索結果。通過激活基于遺傳算法的應用來使這網絡關聯的搜索更加高效。在本文第二節中主要對網絡數據挖掘進行討論,第三節介紹在網絡數據挖掘中使用遺傳算法的案例。

1 網絡數據挖掘

1.1 網絡數據的特點

S. Chakrabarti.指出網絡數據挖掘即是指在萬維網中應用數據挖掘技術來提取人們感興趣的模式和知識[2]。網絡數據挖掘由于網絡的自身特點已經成為一個獨立而重要的研究方向。對于網絡數據的特點可做以下歸納:未經分類,海量,分布性廣泛,多種媒體類型并存,半結構化,時間跨度大,維度高。

本文用圖1表示網絡。

在圖1中,結點表示網頁,有向邊表示超鏈接,這些超鏈接包含了重要的信息,有助于實現信息的高效檢索。例如,在圖1中,許多結點的鏈接都指向A結點,這就表明,結點A所代表的頁面很可能是某些領域的權威[3]。通常情況下,一個網站被描述成若干網頁的集合,在這個集合中,每個成員包含的對其他成員的連接數遠多于外部網頁。

按照網絡數據挖掘的深度層次,可以將網絡數據挖掘歸為以下幾類:

1)基于內容的數據挖掘:這種數據挖掘方式首先會對頁面中涉及的內容進行歸納總結,生成摘要。而頁面的內容種類很多,諸如文本、圖片、HTML代碼到圖和表等,根據這些內容對網頁進行分類,然后設計相應的算法對這些網頁進行檢索。對搜索結果進行數據挖掘同樣是網絡內容挖掘的一個組成部分。其中包括了對結果進行總結,將他們按照層次、標題和摘要中的短語對文檔進行歸類,以及對多個搜索引擎的搜索結果進行合成和重組。最后將對數據進行元數據挖掘。在信息檢索、文本挖掘、圖像挖掘和自然語言處理等方面的應用都屬于這些類型。

2)基于網絡信息結構的數據挖掘:這種挖掘方式涉及到通過萬維網中文檔之間的超鏈接來提取知識,這一做法往往能夠發現諸多網頁中某方面主題的權威頁面。結構挖掘方面的重要應用包括了查找重要的頁面、關聯頁面和主頁,識別重要的模式和它們之間的相互關系。然而,網頁的信息不單單來自于這個頁面本身所含的內容,還來自于其相鄰的頁面。在這里同時使用基于內容的挖掘和基于結構的挖掘可以達到效果互補的目的。

3)基于網絡數據用途的挖掘:此類數據挖掘從本質上說是對數據用途的挖掘。以網站為例進行說明:在客戶端,通過用戶的瀏覽歷史記錄來搜集數據;在服務器端,通過請求日志搜集數據。通過這樣的數據挖掘,可以發現用戶訪問頁面的類型,訪問的時間和訪問持續的時間,以及這個頁面被引用的次數。此類信息有助于實現對頁面的整理,最終實現高效快速的信息檢索。在商業領域中使用這一技術可以實現客戶價值評估、產品潛力發掘、客戶行為預測等。

1.2 網絡數據挖掘的組成和方法

Etzioni. O.提出可將網絡數據挖掘的過程分成信息檢索、信息提取、知識集成和分析四個部分[4]。圖2對網絡數據挖掘的四個組成部分進行說明:

圖2

信息檢索(Information Retrieval,IR):信息檢索是自動對網絡中相關聯的文檔進行搜索,其過程主要包括對文檔的表示、索引和搜索。

信息提取(Information Extraction,IE):信息提取是在文檔被檢索之后,自動從中提取知識,這一過程主要實現對文檔中主要字段的語義進行識別。

信息集成(Generation):這一過程對已有的文檔進行歸納,得到概要知識。在這里將使用分類、規則關聯等模式識別和機器學習的技術來提取信息。例如,將一個網站的主頁和其他頁面區分開就是一個集成工作。

數據分析(Analysis):這一階段將對信息集成階段所生成的模式進行解釋說明。數據分析是一個數據驅動的問題,必須在數據充足的前提下才可能提取有用的信息。

1.3 網絡數據挖掘面臨的挑戰與局限性

由于網絡數據本身的特身,網絡數據挖掘面臨如下問題:1)由于網絡數據的匿名性和人為破壞而造成了數據的不可靠。2)存在噪聲。3)網絡數據是動態的,且存在時間短暫。3)網絡數據缺乏結構化處理,且類型各異。4)語義存在二義性。5)數據高度冗余。使用我們現有的工具和算法難以應付如此復雜的網絡數據。在下一節中提出在查詢中使用遺傳算法實現對網絡數據的搜索和數據挖掘的優化。

2 在網絡數據挖掘中使用遺傳算法

遺傳算法和相關技術在網絡數據挖掘領域的應用包括信息查詢檢索、查詢優化、文檔表示和分布式數據挖掘等[5],本文就信息查詢和查詢優化方面對遺傳算法的應用進行闡述。

2.1 查詢和檢索

Marghny等人將遺傳算法用于元數據搜尋[6],使用這一方法對標準搜索引擎的搜索結果以一種優化方式進行組合,生成更令用戶感興趣的頁面,在文獻[6]中對適配函數進行如下定義:

(a) 鏈接質量函數

n表示用戶輸入的關鍵字的個數,#Ki表示在鏈接L中關鍵字Ki出現的次數。

(b) 頁面質量函數

m表示每個頁面中總的鏈接數。

(c) 平均質量函數

Fmax(P)和Fmin(P)分別表示采用遺傳算法后頁面質量函數的最大值和最小值。Fmax(P)的最大值是m*n,而Fmin(P)的最小值是0.

研究人員分別使用Yahoo,Google,AltaVista和MSN這四個搜索引擎針對不同的主題下載了300個頁面。在雜交點之后對選中的頁面交換雙親的鏈接,以實現雜交。

2.2 查詢優化

查詢優化使用一種基于適度回饋機制的技術。使用回饋的目的是通過使用相關和無關文檔集合來修改用戶的查詢,使用戶的查詢結果更接近于目標文檔。將之前的查詢得到的關鍵字添加到當前查詢中,同時將早期文檔中不相關的關鍵字刪除,通過這種辦法可以檢索到更多的關聯度更大的結果。

遺傳算法在查詢優化上能夠發揮很大的作用。Z. Z. Nick和P. Themis.通過長期監控用戶的瀏覽習慣創建用戶模型[7]。使用遺傳算法對用戶查詢進行修改,在這里文檔和查詢被表示成向量。每個個體被表示成查詢向量,用染色體表示關鍵字的權重或者關鍵字出現或未出現的頻率。M. Boughanem等人研制了一種新的查詢優化技術,在這一技術中,通過使用遺傳算法生成多個查詢,對文檔的不同區域進行搜索,最終得到最優查詢結果[8]。

Leroy等人在文獻[9]中解釋了在對上下文進行動態查詢時使用基于遺傳算法的優化策略有助于提高偶然用戶的查詢效率。由于偶然用戶在Internet上進行查詢的時候只使用少數的關鍵字,這樣得到的查詢結果很少而且相當不精確。但是,大多數用戶在查詢時使用相同的搜索引擎,在某一主題的查詢方面,可總結大多數用戶的查詢行為,從中提取有價值的信息,從而對偶然用戶的查詢要求能夠進行更高效的處理。在遺傳編程的實現上,每個染色體被設計成一個查詢,它有五個位,每個位由一個適當的關鍵字填充。在計算染色體適應度時,將查詢編碼發送給查詢引擎,查詢引擎將返回十條最主要的文檔。

3 小結

為了充分發揮網絡的潛能,讓網絡查詢更加智能化,需要對查詢進行改進。在網絡數據挖掘及其相關領域的研究在查詢優化方面發揮著十分重要的作用。網絡數據挖掘是一個快速發展的領域,在這個領域,研究人員提出各種方法對計算方法進行改進。在該文中,闡述了網絡數據挖掘過程、組成、特點以及網絡數據挖掘所面臨的挑戰。詳細討論了使用遺傳算法對網絡數據挖掘中不同問題的解決方法。

雖然使用遺傳算法對網絡數據進行挖掘很有發展潛力,但是目前這方面的應用和相關文獻還比較有限,為研究人員的進一步研究留下很大的空間。

數據挖掘算法論文:電子商務中數據挖掘的基本算法與應用分析

摘要：數據挖掘技術是近些年來發展起來的一門新技術，通過該技術，人們可以發現數據后面潛藏的有價值的信息。數據挖掘已經成為解決當前企業信息系統中所面臨的“數據爆炸”狀況的最有效的方法，這也為決策者進行各種商業決策提供了科學的理論支持。該文將對數據挖掘的含義與基本算法進行闡述和分析，并對數據挖掘在電子商務中的具體應用進行分析探討。

關鍵詞：電子商務；數據挖掘；基本算法；應用分析

近些年來，基于電子計算機性能的不斷提高、計算成本的不斷下降以及數據管理技術的成功運用，企業商務往來的電子信息化程度也越來越高。與此同時，這也造成了大量的數據積累，形成了了“數據豐富而知識貧乏”的現象，這使得信息決策者難以從海量的數據中提取出具有信息價值的知識，數據挖掘技術的運用很好的解決了這個問題。

1 數據挖掘的含義

數據挖掘（Data Mining）可以定義為從大量的、不完全的、模糊的或者是隨機的實際應用數據中，提取隱含的、同時又有潛在價值的知識與信息的過程。

數據挖掘可以擴展為以下幾層含義：首先，數據源必須具備包含大量的、真實的數據的特點，數據源可以是不同數據倉庫或者文件等；其次，在數據挖掘中發掘出的知識要可運用并且同時容易被理解。也就說，數據挖掘的本質目的在于尋找有用的知識，但是該知識需要被人們理解和接受；最后，數據挖掘通常是針對某一特定問題而進行的分析，往往不可能發掘出通用的知識，這些知識信息一般都具有相應的針對性，只有在特寫的范圍中才能夠應用。

廣義的角度來說，在數據挖掘中的知識是指具有一定規則的模式或者概念等，而信息與數據則是知識的理論源泉。也就是說對知識的發掘就是是從數據中挖掘出相應的規則與模式的過程，故而稱之為數據挖掘。在數據挖掘中，數據源可以是多樣的也可以是單一的，可以是分布式形態的，也可以是結構化形態的。

2 電子商務中數據挖掘的體系結構

當前電子商務是數據挖掘技術應用比較廣泛的應用，這主要是歸功于電子商務能夠比較容易地滿足數據挖掘所必需的因素，這些因素包括豐富的數據語言、可以自動收集可靠的數據并可將數據挖掘的結果轉化為商務行為。然而，要想充分發揮數據挖掘技術在電子商務應用中的效率，數據挖掘技術需要將事務處理階段的數據轉存到相應的數據倉庫中，并且要與電子商務行為有機結合起來。本文將電子商務中數據挖掘的體系結構概括3個主要部分，即商務數據定義、分析處理和顧客相互作用和。流程圖如圖1所示。

3 電子商務中數據挖掘的基本方法

3.1 路徑分析

這種方法可以被用于確定在一個Web站點中最頻繁訪問的路徑，其它一些與之有關路徑的信息也可以通過路徑分析得出。比如當70%的用戶端在訪問/company/product2的時候，從/company開始,而后經過company/news,/company/products/company/productl；80%的訪問這個站點的顧客是從/company/products而開始的；65%的客戶在瀏覽少于4個頁面后便離開了?？梢灾溃?條規則在/company/roduct2頁面上有具有有用的信息，但是由于客戶對站點進行的是遷回繞行方式的訪問，因而這個有用信息并不十分明顯。第2條規則則說明了客戶訪問站點通常不是從主頁開始的，而是由/company/products開始的，假如這個頁面上包含許多產品的目錄類型的信息，將是一個不錯的想法。第3條規則表明客戶在網站上停留的時間。進過路徑分析后，發現客戶在該網站上瀏覽情況往往不超過4個頁面時，就可以將相對重要的商品信息置于這些頁面中，從而可以改進頁面網站的結構設計。

3.2 關聯規則分析

關聯分析的最終目的是挖掘隱藏在數據間的相互關系，在電子商務中進行關聯規則分析也就是找到客戶對網站上不同文件之間訪問的相互聯系。在進行Web數據挖掘后，可以構建出關聯關系模型，我們可以依據該模型更好地組織站點，從而減少用戶過濾信息的負擔。

3.3 序列模式分析

序列模式分析的重點在于分析不同數據之間的前后或者因果關系，也就是說在時間有序的事務集合中，去發現具有關聯的內部事務模式。發現序列模式有助于電子商務的組織者對客戶的訪問模式進行預測，從而為客戶提供個性化的服務，網站的管理人員可以依據瀏覽模式對訪問者進行分類，而在頁面上只展示出對應的訪問鏈接。當訪問者瀏覽到某一頁面的時候，管理人員可以檢查他的瀏覽所符合的序列模式，并且在比較顯眼的位置進行“訪問該頁面的人員一般接著訪問”的若干頁面。

3.4 分類分析法

分類分析法的輸入集通常是一組記錄集合或者幾種標記，這種分析法首先為每一個記錄賦予一個相應的標記，也就是按標記分類記錄，而后對這些標定的記錄進檢查，從而描述出這些記錄的特征。在電子商務中通過應用數據挖掘，可以對不同消費群體進行分類，從而便于對某一類客戶進行有針對性的商務活動。

3.5 聚類分析法

聚類分析法有別于分類規則法，其輸入集合一般是一組未標定的記錄，這也就是說該輸入記錄并沒有進行任何分類。這種方法的目的是依據一定的規則，對記錄集合進行合理劃分，并且利用顯式或者隱式的方法對不同的類別進行描述。當前已開發出許多聚類分析的工具，在電子商務中，通過對具有相似瀏覽行為的客戶進行聚類，可以使管理員更多地了解客戶信息，從而為其提供更適合、更滿意的服務。

4 電子商務中數據挖掘的應用分析

本文將數據挖掘在電子商務中的典型應用概括為以下幾個方面：

4.1 發現潛在客戶

在對Web的客戶訪問信息進行數據挖掘中，可以利用分類技術在Internet上發現未來潛在的客戶。對于電子商務從業者來說，得到這些潛在客戶一般市場策略是，首先對現已存在的訪問者進行分類，通常分為3種，即:“no customer”、“visitor once”、“visitor regular”。通過Web上的分類發現，管理人員可以識別出新客戶和已經分類的老客戶的一些具有共性的描述，這有助于對該新客戶進行正確的分類。而后，依據其分類來判斷這個新客戶是否屬于潛在的客戶群體，從而決定是否要需要將這個新客戶作為未來潛在的客戶來對待。在確定客戶的類型以后，管理人員就可以動態展示相應的Web頁面，而Web頁面的具體內容主要取決于客戶與銷售商提供的產品以及服務之間的關聯規則。

4.2 駐留客戶

現代電子商務平臺使得傳統客戶與銷售商之間的空間距離已經不存在了，在網絡電子平臺上，每一個客戶來都有選擇不同銷售產品的權利，如何使這些客戶在銷售商自己的銷售站點上駐留比較長的時間、使其對該網頁產品產生更火的興趣，對每一個銷售商來說都是一個挑戰。為客戶在相應的網站上駐留更長的時間，就需要了解客戶的瀏覽行為，掌握客戶的興趣與不同需求所，從而對頁面內容進行動態調整，以此來滿足客戶的需求。對客戶訪問信息進行數據挖掘，就可以掌握客戶的瀏覽行為，從而獲取客戶的興趣及需求。在網絡電子商務平臺中的一個典型的序列，就代表了客戶以頁面的形式在該站點上導航的行為，運用數據挖掘中的序列模式分析技術，可以知道道客戶的實際需求，從而為客戶提供一些特有的商品信推廣信息，從而使客戶能保持對訪問站點的興趣。

4.3 對站點改進的設計

網絡站點上頁面內容的安排與連接，就像超市物品在貨架上的擺設一樣，需要將支持度與信任度較高的關聯物品擺放在一起，從而有助于銷售。通過Web上的關聯規則分析，可以針對不同的客戶對站點的結構進行動態調整，并進行相應的改進設計，從而使與客戶訪問有關聯的文件之間的連接更為直接，這也有助于客戶更容易地訪問到預想的頁面。當電子商務網站具有這樣的便利性的時候，便可以給客戶留下很好的印象，這也就增加了客戶下次訪問的機率。

4.4 對客戶進行聚類

在電子商務中，應用數據挖掘進行客戶聚類是一個十分重要的內容，通過對具有相似瀏覽行為的客戶進行分組，可以分析出組中客戶的共同特征與共性信息，從而可以幫電子商務的組織者更加客觀地了解自己的客戶，這也最后有利于組織者為客戶提供更加適合、更加面向客戶的服務。

5 結束語

數據挖掘盡管只有十多年的發展歷史，但是在電子商務中卻展示出了非常廣闊的應用前景。本文比較詳細地闡述了電子商務中數據挖掘的體系結構、應用方法以及比較典型的應用，期望通過本文的分析與探討，可以為今后數據挖掘技術在電子商務中的廣泛應用提供積極的借鑒參考。

數據挖掘算法論文:數據挖掘中關聯規則算法的研究

摘要：數據挖掘是一個新興的領域，在短短幾年內得到了迅速的發展。關聯規則算法是數據挖掘技術中最活躍的算法之一。該文從關聯規則算法的原理入手，對關聯規則的各種算法進行了深入研究，并總結得出了強關聯規則生成的步驟方法。

關鍵詞：數據挖掘；關聯規則算法；強關聯規則

隨著數據庫技術的發展、改進及相關技術、產品的廣泛應用，數據庫中存儲的數據量日益膨脹。此時，許多人都曾提出疑問：在海量的數據之間是否隱藏著許多具有決策意義的有價值的信息？如果這種信息真的存在，那么把這些信息挖掘出來并應用于現實生活，將會為決策者和管理者提供指導，提高工作效率和工作精度。

數據挖掘(Data- Mining)就是從眾多的、有噪聲的、不完全的、模糊的、隨機的大量數據中，提取隱含在其中人們事先不知道但又是潛在有用的信息和知識的過程[1]。

關聯規則算法是一種在海量數據中找出隱藏的關聯規則的方法。它是數據挖掘中最為活躍的算法之一。

1 關聯規則算法的原理

1.1 背景

關聯規則算法早期應用于“購物籃分析”。通過使用關聯規則算法來對客戶的事務執行購物藍分析，可以知道哪些產品比較熱銷，以及一個特定的產品與另一個產品一起被購買的可能性是多大。如，在數據挖掘應用中最典型的例子“啤酒與尿布”，就是銷售商們通過大量的客戶購買信息，挖掘出的一條關聯規則。即，在購買尿布的用戶中，有很大比例的人還同時購買了啤酒。知道了這條規則，商家就可以采取行動，改變產品的布局來增加銷售和管理庫存?，F在，關聯規則挖掘不僅在零售業，在其它領域也得到了廣泛應用。

關聯規則常常用一個蘊涵式來表示。如“啤酒=>尿布”。

1.2 基本概念

1.2.1 項集（Itemset）

項集也叫項目集合，是由一組項組成。其中每個項都是一個屬性值。通常設I＝{i1,i2，…im}為一個項目集，而事務數據庫D={t1,t2，…tm}是由一系列事務組成，而每個事務ti（i=1,2,…,n）都對應I上的一個子集。在購物籃分析中，項集中包含的是一組由用戶購買的產品，如｛啤酒，尿布，香檳｝。這個項集包含了3個屬性值，大小為3。

1.2.2 支持度（Support）

支持度是指一個項集在全部事務中出現的頻率。項集｛牛奶，面包｝的支持度就是在全部事務數據中，既購買了面包又購買了牛奶的顧客出現的頻率。若項集｛牛奶，面包｝的支持度為0.05，則表明在全部顧客中，只有5%的顧客同時購買了這兩樣。

最小支持度是事先由用戶確定的一個數值。一般來說，用戶只關心那些出現頻率比最小支持度高或與之相等的項集。因此，該數據可以用來對項集進行篩選。

1.2.3 置信度(Confidence)

置信度是關聯規則的屬性。關聯規則“牛奶=>面包”的置信度是使用｛牛奶｝的支持度除項集｛牛奶，面包｝的支持度來計算的。簡單解釋就是，在全部事務數據中，購買牛奶的顧客中有多大比例的人還同時購買了面包。

它是按以下方式來定義的：

Confidence{A=>B}=Support{A,B}/Support{A}

最小置信度也是在運行算法之前由用戶事先指定的一個數值。該數據表明用戶只對那些置信度等于或大于最小置信度的規則感興趣，即那些擁有較高概率的規則。該數據可以用來篩選出有效的關聯規則。

1.2.4 頻繁項目集（Frequent Itemsets）

挖掘頻繁項目集是進行關聯規則算法的核心內容。所有滿足用戶指定的最小支持度的項目集，即大于或等于最小支持度的I的非空子集，就稱為頻繁項目集，簡稱為頻繁項集。即上面提到的用戶感興趣的項集。

1.2.5 強關聯規則(Strong Association Rule)

D在I上同時滿足最小支持度和最小置信度，即在滿足支持度不小于最小支持度的每一個頻繁項集中，置信度大于等于最小置信度的關聯規則。即上面提到的用戶感興趣的規則。這個規則也叫強關聯規則。

1.2.6 相關度（Importance）

相關度是關聯規則中另外一個重要的概念。在一些文獻中相關度也被稱為興趣度分數或者增益（lift）[2]。

相關度的公式可以定義如下。

Importance({A,B})=confidence(A,B)/(confidence(A)*confidence(B))

如果Importance＝1,則A和B是獨立的項。在購物籃分析中，它表示產品A的購買和產品B的購買是兩個獨立的事件。如果Importance1，則A和B是正相關的。這表示如果一個客戶購買了A，則他也可能購買B。

2 關聯規則挖掘的一般過程

通過以上對關聯規則挖掘算法的簡單介紹，可以了解到，關聯規則挖掘就是通過用戶指定的最小支持度，在全部事務數據庫中挖掘出滿足支持度不小于最小支持度的頻繁項目集，再通過用戶指定的最小置信度，在全部頻繁項目集中挖掘出那些置信度不小于最小置信度的強關聯規則。關聯規則挖掘過程由這兩部分共同組成。

在這兩部分中，關聯規則挖掘是否成功主要取決于第一部分，即挖掘頻繁項目集。

3 頻繁項目集的生成算法

挖掘頻繁項目集是使用關聯規則算法的核心部分。自關聯規則挖掘問題提出后，相應的如何快速高效地生成頻繁項目集這個核心問題的算法就不斷的被人研究，并不斷發現、使用。這些算法大多都是通過利用頻繁項集的特性DD即如果一個項目集是頻繁的，那么它的所有子集也都是頻繁的DD來進行操作的。

Apriori算法[5]在關聯規則挖掘領域中有很大的影響力，應用極為廣泛。它的命名源于算法使用了頻繁項集性質的先驗知識。Apriori算法是通過迭代即反復掃描數據項的方式來產生頻繁項集的。它的具體思路是：在第一次迭代時，先產生包含所有數據項的大小為1的候選集，計算出它們的支持度，選擇那些支持度大于等于最小支持度的候選集作為第一次迭代時的頻繁項目集。此時，所有頻繁項目集的大小都為1，被淘汰的項目集被標記為非頻繁子集。接著進行第二次迭代，在第二次迭代的第一步中，將所有成對出現的項集都作為大小為2的候選集，第二步，利用頻繁項集的性質：頻繁項集的子集也都是頻繁的，假若某個項目集的一個子集不是頻繁的，那這個項目集必然不是頻繁項集，將剛才產生的候選集中包含有非頻繁子集的刪去。第三步再計算所有候選集的支持度，將支持度滿足最小支持度的候選集做為第二次迭代產生的大小為2的頻繁項目集。如此通過i次迭代，就可以產生出大小為i的頻繁項集。

Apriori算法是通過項目集元素數目不斷增長的方式來逐步完成頻繁項目集發現的。每增長一次項目數，Apriori算法就至少需要掃描事務數據庫一次，假如頻繁項目集的項目數很大，會造成計算機巨大的I/O負載。并且，因為Apriori算法在每一次迭代時，都將成對出現的項集依次組成新的候選集，因此，可能會產生龐大的候選集。這對計算機運行速度也將是一種挑戰。

因此，逐漸又產生了Apriori算法的改進方法。

如基于數據分割方法的Partition方法。Apriori算法在每一次迭代時只能將項目數增加1,每次產生的候選集也并不都是有效的，無形中降低了算法的效率。而Partition算法是一種基于對數據集進行劃分的挖掘算法，它的思路是：先將事務數據庫劃分為幾個邏輯上互相獨立的區域。在每個區中，利用挖掘算法挖掘出它們各自的頻繁項目集。然后將這些頻繁項目集合成一個候選集。最后，計算出候選集的支持度，挖掘出符合不小于最小支持度的最終的頻繁項目集。Partition方法在第一次劃分時掃描一次數據集，在最后求候選集支持度時再一次掃描數據集，全程只掃描二次數據集，大大減少了I/O操作。Partition算法因為是分別求每個區的頻繁項集，因此可分別同時對各區進行操作，大大提高了算法的效率。

還有與Apriori算法類似的DHP算法[3]。DHP算法也是從Lk-1中生成侯選集Ck。但DHP算法在每次迭代計算候選集的支持度時，會建立并維護一張Hash表。在下一次迭代時，根據Hash表來選擇加入的數據項，而不是像Apriori算法那樣將所有數據項先全部選上之后，再刪去那些非頻繁子集。通過對Hash表的操作，DHP算法可以大大減小侯選集的規模，從而提高算法的計算效率。

隨著數據庫容量的逐步增大，為適應新形勢，新的算法不斷出現。2000年，Han等人提出了一個不用產生候選集，可以直接將數據壓縮成頻繁模式樹的方法，被稱為FP-tree算法[4]。

4 強關聯規則的生成

利用Apriori算法或其它類似的算法挖掘出所有頻繁項集之后，下一步的工作就是生成強關聯規則。這可以在頻繁項目集中逐一測試非空子集的支持度，從而挖掘出所有可以生成的規則。也可以直接測試用戶想要挖掘的規則是否成立。假如用戶打算挖掘出這樣的規則｛A，B，C｝=>D，那么，第一步，先來檢驗｛A,B,C,D｝和｛A,B,C｝是否都是頻繁項集。如果是，接著第二步，利用關聯規則置信度的公式Confidence{A=>B}=support{A,B}/support{A}，計算出規則｛A，B，C｝=>D的置信度的值。若此值大于等于最小置信度，那么規則｛A，B，C｝=>D成立，是強關聯規則。反之，不成立。

5 結論

關聯規則挖掘就是要挖掘出強關聯規則。強關聯規則的生成取決于頻繁項目集，而頻繁項目集的挖掘算法正是關聯規則算法的核心所在。因此，深入研究關聯規則算法，并根據實際情況在應用中選取最合適的算法對強關聯規則的生成非常重要。

數據挖掘算法論文:一種改進的基于密度的離群數據挖掘算法

摘要：利用基于密度的離群數據挖掘算法離群數據不在非離群數據指定的鄰域內的特點，改進了原有的離群數據挖掘算法：首先判斷數據是否在某個非離群數據指定的鄰域內，如果不在，再判斷其鄰域內數據的個數。通過對二維空間數據測試表明，改進的算法能夠快速有效地挖掘出數據集中的離群數據，速度上數倍于原來的算法。

關鍵詞：數據挖掘；離群數據；基于密度

0引言

數據挖掘是從大量的數據中發現正確的、新穎的、潛在有用并能夠被理解的知識的過程?，F有的數據挖掘研究大多集中在發現適用于大部分數據的常規模式。但在一些應用中，如電信和信用卡欺騙、藥物研究、氣象預報、電子商務、貸款審批、客戶分類、金融領域、網絡入侵檢測等領域有關例外情況的信息比常規模式更有價值。目前在數據挖掘中，對偏離常規模式的數據即離群數據的研究正得到越來越多的重視。

目前還沒有關于離群數據的統一的定義，這里采用Hawkins1980年給出的定義：離群數據是在數據集中與眾不同的數據，使人懷疑這些數據并非產生于非隨機偏差，而是產生于完全不同的機制。離群數據的來源有兩類：錯誤的數據，如錄入錯誤、測量錯誤等；數據真實性質的反映，如一個公司的總裁的薪金遠大于該公司一個普通員工的薪金等。所謂的離群數據挖掘指給定一個有n個數據點或數據對象的集合及預期的離群數據數目n′，發現與剩余數據相比顯著相異的、離群的或不一致的前n′個對象的過程[1]。

早期的統計分析領域的基于統計的離群數據挖掘其前提是待處理數據的分布特征是預先知道的（如正態分布、泊松分布等），這種方法需要知道數據的分布及分布的參數等；鄭斌祥等人[2]基于第k個最近鄰居的離群挖掘方法只針對時序數據，而且運算性能也不甚理想；基于偏離的離群數據檢測方法是知道數據特性選取合適的相異函數，但序列離群數據在概念上仍然有一定的缺陷，遺漏了不少的離群數據，因而沒有得到普遍的認可；基于規則的分類離群數據挖掘方法只適合于要求錯誤數據少，分組粒度細的挖掘；基于距離的方法比較接近Hawkins對離群數據本質的定義，它通過實驗確定合適的基準值和距離范圍，難以處理分類數據和周期性時態數據；基于密度的離群數據挖掘（DensityBased Outlier Mining，DBOM）的觀點比基于距離的離群數據挖掘的觀點更貼近Hawkins對離群數據本質的定義，因此能夠檢測出基于距離離群數據挖掘算法所不能識別的一類離群數據，即局部離群數據，而局部離群數據拋棄了以前所有的離群數據定義中非此即彼的絕對離群數據概念，更加符合現實生活中的應用。另外還有基于相似系數的方法、基于聚類的小波變換聚類的方法、高維空間聚類的方法等。本文首先描述了DBOM算法，而后對其進行了改進。

1基于密度的離群數據挖掘

1.1DBOM算法的基本概念

定義1以數據對象o為圓（球）心，半徑ε內的區域稱為o的ε―鄰域。

定義2若數據對象C的ε―鄰域內含有數據對象數目不少于Minpts個，則稱C為核心對象，能產生核心對象的ε是有意義的。其中，Minpts是一個可以人為設定的自然數。

定義3D是數據對象集合，p∈D，C∈D。對于給定的一個自然數Minpts，若C是核心對象，p在C的ε―鄰域內，則稱p是從C出發關于ε和Minpts直接密度可達。

定義4D是數據對象集合，p∈D，p的ε―鄰域內數據對象集合稱為p的ε擦謨蚣，記為Pε―set。

定義5D是數據對象集合，o∈D，對于任意一個核心數據對象C∈D，從C出發，都不能關于ε和Minpts直接密度可達并且|oε―set|≤Minpts，則稱o為關于ε和Minpts的基于密度的離群數據對象。

定義6D是數據對象集合，p∈D，若p的ε擦謨蚰諍有對象數目為零，則稱p是數據集D中關于ε鄰域的孤立點。

1.2DBOM算法的描述

基于密度的離群數據挖掘算法可以發現任意形狀的數據布局中的離群數據，它的基本思想是：對于數據集中的每一個離群數據對象，不能包含在任何一個給定半徑和該半徑鄰域內包含指定數據對象數目的核心對象的鄰域內?；诿芏鹊碾x群數據挖掘為了發現所有的離群數據，需要對每個數據進行處理。DBOM首先從數據集D中任意找一數據對象p，并查找出D中p的關于半徑ε鄰域內包含所有的鄰域對象，若p的ε鄰域內某一個數據對象的ε鄰域內包含Minpts或多于Minpts個數據對象，則p不是離群數據；反之，若p的ε鄰域內所有數據對象的ε鄰域內包含的數據對象個數都少于Minpts，或者p的ε鄰域內沒有數據對象即p是數據集D中關于ε鄰域的孤立點，則p是離群數據。接著處理數據集中的下一個數據，直至數據集中的所有數據都被處理完。相應的算法描述如下：

2改進的基于密度的離群數據挖掘IDBOM

上述的基于密度的離群數據挖掘算法能夠較好地挖掘出數據集中的離群數據，該算法的平均執行時間復雜度為O（n2）（n為數據集中包含的數據對象數目）。它主要是通過對數據集中每個數據對象進行判斷，如果它的鄰域內某一個數據對象是一個核心對象，即它包含在某一個核心對象的鄰域內，該數據對象就不是離群數據，否則是離群數據。從離群數據的特征來看，離群數據往往是比較稀疏的、在數據集中所占比例比較小的數據因此，上述算法對每個數據及其鄰域內的數據進行相關判斷，顯然效率就比較低下。

定理1如果一個數據對象是核心對象，那么該數據的鄰域內的數據都不是離群數據。

證明假設存在一個數據集D，C為D中關于ε和Minpts的核心數據對象，Cε―set為C的ε―鄰域集，那么對Cε―set中的任意一個數據對象p，都有d（C，p）≤ε，即從核心數據對象C出發，可以直接密度到達數據對象p，由定義5可知，數據對象p不是離群數據對象。

定理2某個數據對象是離群數據是其ε―鄰域內數據對象的個數少于Minpts個的充分條件。

證明設存在一個數據集D，o為D中關于ε和Minpts的離群數據對象，oε―set為o的ε―鄰域集，由定義5可知，｜oε―set｜≤Minpts；假設在數據集的邊緣存在一個數據對象q∈｜qεset｜≤Minpts, C為數據集中一個核心數據對象，且有q∈Cε―set，根據定義5可知q不是離群數據對象。

基于上述定理，我們不對數據集中每個數據對象的鄰域內判斷是否存在一個核心數據對象，而是只判斷鄰域內數據對象個數少于Minpts個的數據對象的鄰域內是否存在核心數據對象。如果某一個數據對象p是核心數據對象則將其及其鄰域內的數據對象打上暫不運算的標簽及非離群數據的標簽；反之按下述方式處理其鄰域內的數據對象：若p的鄰域和某個核心數據對象C的鄰域數據對象交集不為空，那么判斷這些交集中的數據對象是否存在核心數據對象，若存在則p不是離群數據。如果和任何核心數據對象的ε擦謨蚪患為空或交集內不含核心數據對象則p就是離群數據對象。改進的算法描述如下：

3算法測試

這里對基于密度的離群數據挖掘算法進行了測試，算法是用Matlab實現的，實驗的環境是一臺P4 2.93G、內存1GB的計算機，通過對網絡中心的某數據集進行測試，在ε＝50和Minpts＝3的條件下，共挖掘出3個離群數據，經過檢測，其中兩個離群點是由病毒造成的網絡不正常，另外一個是由于一個實驗室進行網絡對拷發送廣播報文引起的網絡堵塞造成的。其中優化后的算法的運算時間是優化前的三分之一。在運算的過程中發現，ε和Minpts取值不同，挖掘出的離群數據的個數也可能不同，這說明了基于密度的離群數據挖掘算法對輸入參數有一定的敏感性。