第一篇：數據挖掘與知識發現(講稿7-神經網絡挖掘)

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

第7章

基于神經網絡的數據挖掘技術

人工神經網絡ANN（Artificial Neural Network）是反映人腦結構及功能的一種數學模型，它是由大量的簡單處理單元經廣泛并行互連形成的一種網絡系統。用以模擬人類進行知識的表示與存儲以及利用知識進行推理的行為。它是對人腦系統的簡化、抽象和模擬，具有人腦功能的許多特征。

目前，人工神經網絡已在模式分類、機器視覺、機器聽覺、智能計算、機器人控制、信號處理、組合優化問題求解、聯想記憶、編碼理論、醫學診斷、金融決策、數據挖掘等領域得到廣泛應用。

7.1 基于知識的神經網絡（KBANN）

神經網絡用于數據挖掘的困難之一是，對經過訓練的神經網絡的輸出結果很難給出直觀的解釋。許多學者試圖將專家系統和神經網絡相結合，設計出兼有專家系統和神經網絡優點的混合系統。其中，基于知識的神經網絡就是其中最有代表性的一種系統。

基于知識的神經網絡包含如下四個階段：

① 規則庫表示階段：提取原始的領域知識并將其組織成規則庫；（屬人工智能內容）

② 映射階段：將上述規則庫中的每條規則映射成一個小的子網絡，全體子網絡就構成了一個原始網絡結構；

③ 學習階段：用訓練樣本對上述網絡進行訓練；（應用人工神經網絡學習算法）④ 規則提取階段：將上述訓練好的神經網絡再映射成規則庫。

其典型結構圖為：

圖1 基于知識的神經網絡的信息流程

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

1）原始規則庫轉化為神經網絡結構

（1）合取規則

在與肯定條件相對應的網絡連接權設置為?，在與否定條件相對應的網絡連接權設置為??，在與結論相對應的神經元的閾值設置為(2P?1)?/2，其中P是肯定條件的個數。經驗表明，在KBANN中，?通常設置為4能取得較好的效果。如，規則

A:B,C,D,not(E)

圖2 合取規則轉化為神經網絡示間圖

（2）析取規則

KBANN對與每個析取條件相對應的連接權設置為?，對與結論相對應的神經元閾值設置為?/2。如，規則

圖3 析取規則轉化為神經網絡示意圖

2）知識庫轉化為神經網絡示例

設（a）為規則庫；（b）為規則的層次結構，其中，實線代表必要關系，虛線表示抑制關系；（c）為由規則庫轉化而來的神經網絡，其中，為了處理析取規則而引入X和Y結點，實線連接代表權重均設置為?，它代表規則庫中的依賴關系；細線代表有待進一步學習的連接權，它反映知識的精化。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

7.2 基于KBANN的規則提取方法

基于KBANN在數據挖掘中的作用集中體現在規則提取階段，這一問題在神經網絡研究領域十分活躍。這里，主要給出一些從前饋網絡（如，多層感知器MLP）中提取規則的方法。幾乎所有的規則提取方法都假設經過訓練的神經網絡的神經元，要么處于活躍狀態，要么處于不活躍狀態。

1.有代表性的規則提取方法

（1）LRE方法

用LRE方法對MLP進行規則提取主要兩步：

? 每一步，對網絡中的每個隱層結點和輸出結點搜索不同的輸入組合，使得輸入加權和大于當前結點的閾值；

? 對每一個組合產生一條規則，其前件是各個輸入條件的合取。如，Either、KT和Subset算法就是LRE方法中有代表性的三種方法。它們的特點：生成的規則均較容易理解，但這三種方法有如下缺點：① 搜索空間大，故搜索效率低；② 前后生成的規則有可能發生重復；③ 不能保證所有有用的規則均被產生出來。

針對Subset算法的缺點，Towell等提出了MofN方法，該算法的基本思想是將所有權值分成若干個等價類，在每個等價類中成員的作用基本相似，因而可以相互互換。MofN方法通過六個步驟，從訓練好的神經網絡中提取規則，它們分別是：

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

① 分類---即將連接權分成若干等價類； ②平均---即將每個等價類中的權值平均化； ③ 去除---即去除對神經元的作用較小的等價類；

④ 優化---即在去除了部分連接權后，對神經元的閾值進行優化； ⑤ 提取---即從經優化的神經網絡中提取規則； ⑥ 簡化---即將上述規則簡化，使其更易于理解。

（2）黑箱方法

黑箱方法僅考慮從前饋神經網絡的輸入和輸出的行為來提取規則。所以稱之為黑箱是因為在提取規則時不考慮神經網絡的類型和結構，主要關心輸入和輸出間的映射關系。

（3）提取模糊規則

在模糊神經網絡和神經網絡模糊系統的研究中，有些模糊神經網絡和神經網絡模糊系統中包含模糊規則的提取和精化方法。

（4）從遞歸網絡中提取規則

該方法將遞歸網絡的狀態和有限自動機的狀態相對應，可提高神經網絡的泛化能力。

2.一些新規則的提取方法

本節主要介紹Taha和Ghosh的最新研究工作，其中包含三種規則提取方法：

（1）二值輸入輸出規則提取算法（BIO-RE）

該方法屬于一種簡單的黑箱方法，它對二值輸入的神經網絡進行規則提取，若原始輸入不是二值的，則必須先將其二值化：

yi???1ifxi??i

?0otherwise其中，xi為原始輸入；?i為閾值；yi是與xi相對應的二值化輸入。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

圖4 感知器模型

它的算法為：

輸入：經訓練好的神經網絡

輸出：規則（庫）

步驟：

① 給出對應于各二值輸入模式的神經網絡輸出O(Y)?{oj(Y)|oj?{0,1}}；

② 將二值輸入和輸出相對應，構成一個真值表；

③ 由上式真值表生成相應的布爾函數，即所需的規則（庫）。

BIO-RE算法所提取的規則有如下一般形式：

IF [Not]輸入變量 [[And] [Not]輸入變量]* → 結論j 其中，[·]---表示任選項；[·]*---表示可重復0次或n次。

若最終提取的規則為

IfY1AndNoYt2ThenO1 則必須將其改寫為

IfX1??1AndX2??2ThenO1

由此可見，一個“真”二值輸入變量（如，Y1）表示“X1??1”；一個否定的二值輸入變量（如，NotY2）表示“X2??2”

此法當輸入輸出本來就是二值的，或經二值化后不會顯著影響其性能且輸入變量不太大時，用BIO-RE算法是合適的，否則此方法就不太適用。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

（2）部分規則提取算法（Partial-RE）

針對BIO-RE算法的不足，Partial-RE算法僅關心主要的連接權的組合，對每個隱層結點或輸出層結點j，將輸入結點j的正負連接權按降序排列，形成兩個集合。然后從最大的正連接權開始，比如從第i個結點進入的連接權最大，該算法判斷在不考慮其他結點輸入的情況下，能否使結點j激活。若存在這樣的結點j，則生成一條規則

cf

IfNodei???Nodej

其中，cf表示該條規則的置信度：

1?,若響應函數為Sigmoid型n_??1?exp(?wjixi??j??)?i?1?n_?

cf??min(1,?wjixi??j??),若響應函數為線性閾值函數

i?1??1,若響應函數為階躍函數????這里，wji為輸入xi與結點j間的連接權；?j為結點j的閾值；?稱為置信參數，是一個小正數（0.1???0.3）。

若發現結點i足夠強使得結點j被激活，則結點i即被標記，今后當考察結點j時，結點i將不被考慮。Partial-RE算法繼續檢查剩余的正連接權，直到發現一個帶正連接權的結點不能單獨激活結點j時為止。

必須注意：Partial-RE算法假定所有的輸入均有相同的取值范圍，這樣它們對隱層結點的影響僅由權值決定。因此，必須對原始輸入變量先進行量化：

zi?_1.0x?u1.0?exp(?(i2i))2?i

其中，zi是原始輸入變量xi經量化后的值；?i為輸入X的標準均方差，ui是X的均值。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

此外，該算法還尋找負權結點，在激活時，則產生如下規則：

IfcfNotNodeg???Nodej

不僅如此，該算法還尋找正權和負權的組合，并激活隱層或輸出層結點，則產生如下規則：

cf

IfNodeiAndNotNodeg???Nodej

當所有的規則都生成后，將它們改寫成如下形式：

IfXi??icfAndXg??g???Consequentj

實驗結果表明，Partial-RE算法比較適合于規模較大的問題，因為此時提取所有規則是一個NP-完全問題，而提取一部分最重要的規則是切實可行的辦法。

（3）全部規則提取算法（Full-RE）

Full-RE算法與Partial-RE算法相比，它可以從連續輸入、歸一化輸入及二值化輸入等各種神經網絡中提取規則，具有較好的普適性。

對每個隱層結點j，Full-RE算法首先生成以下中間規則：

cf

If(?wjiXi??j??)???Consequentj

_由于存在一組Xi滿足中間規則，這樣就必須知道Xi的取值范圍。每個輸入特征Xi?(ai,bi)可以用k個小區間來離散化為

Di?{di,0?ai,di,1,?,di,k?1,di,k?bi}

當Full-RE算法發現離散化存在多組解時，它將根據連接權的符號選擇Xi的最大或最小離散化值。若wji是負的，則Full-RE算法選擇Xi的最大離散化值，否則選擇Xi的最小離散化值。離散化后形成下列線性規化問題：

Minimizewj1D1?wj2D2???wjnDn 使得

____

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

___

wj1D1?wj2D2???wjnDn??j?? 且Di?{di,0?ai,di,1,?,di,k?1,di,k?bi}，1?i?n。

可以用任何一種求解線性規劃問題的工具來求解該線性規劃問題，從而得到X的取值范圍。假設一個可行解為x1?e1和x2?e2，從輸入X1和X2到結點j的連接權分別是正數和負數，則Full-RE算法如下規則：

IfX1?e1cfAndX2?e2???hj

其中，ai?ei?bi。隱層和輸出層間提取的規則可以表示為

cf

Ifh1Andh2???Ok

Full-RE算法將中間規則和隱層與輸出層間提取的規則復合形成新的規則，復合的方法是對每個隱層結點hj，將hj替換為中間規則中后件為hj的前件，最終形成的規則的一般形式為

cf

If簡單布爾表達式[And簡單布爾表達式]*???結論j

值得注意的是，由于由Full-RE算法提取的規則中對前提條件的個數不作限制，而僅對相鄰層間規則中的前提條件個數作限制。所以，當輸入特征是二值時，就不需要二值化過程。7.3 基于ANN的數據挖掘示例

《吳一帆,基于模糊神經網絡的數據挖掘算法.caj,長沙電力學院學

報,2002(4)》

第二篇：數據挖掘與知識發現(講稿9--遺傳算法)

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

第九章

基于遺傳算法的數據挖掘

面向屬性的數據挖掘方法是基于邏輯的，神經網絡挖掘方法是基于方程的，而本章要介紹的遺傳算法，則是一種基于十字表的數據挖掘方法。它也是一種典型的知識發現方法。

遺傳算法是模擬生物在自然環境中的遺傳和進化過程而形成的一種自適應全局優化概率搜索算法。它最早由美國密執安大學的Holland教授提出，起源于60年代對自然和人工自適應系統的研究。70年代De Jong基于遺傳算法的思想在計算機上進行了大量的純數值函數優化計算實驗。在此基礎上，由Goldberg在80年代對其進行了歸納總結，形成了遺傳算法的基本框架。9.1 遺傳算法概要

對于一個求函數最大值的優化問題（最小值類同），一般可描述為如下的數學規劃模型：

?maxf(X)?

?s.t.X?R

（9-1）

?R?U?式中，X?[x1,x2,?,xn]T為決策變量；f(X)為目標函數（線性或非線性；離散或連續；單峰或多峰）；U為基本空間；R為U上的一個子集。滿足約束條件的解X稱為可行解，集合R表示由所有滿足約束條件的解組成的一個集合，叫做可行解集合。

圖1 最優優問題的可行解及可行解集合

傳統的求最優解或近似最優解的方法主要有：枚舉法、分枝定界法、1

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

啟發式算法和搜索算法。隨著問題種類的不同，以及問題規模的擴大，要尋找到一種能以有限的代價來解決上述最優化問題的通用方法仍是一個難題。而遺傳算法正好能為此類問題提供一個有效途徑和通用框架，開創了一種新的全局優化搜索算法。

遺傳算法是模擬生物進化過程的計算模型，它是自然遺傳學和計算機科學相互結合滲透而形成的新的計算方法。

生物的進化過程主要是通過染色體之間的交叉和變異來完成的。在遺傳算法中，將n維決策向量X用n個記號Xi,i?1,2,?,n所組成的符號串來表示X：

X?X1X2?Xn?X?[X1,X2,?,Xn]T

把每一個Xi,i?1,2,?,n看作一個遺傳基因，它的所有可能取值稱為等位基因。這樣，X就可看作是由n個遺傳基因所組成的一個染色體（或個體）。對于每個個體，要按照一定的規則確定出其適應度。個體的適應度與其對應的個體表現型X的目標函數值相關聯，X越接近于目標函數的最優點，其適應度越大；反之適應度越小。所有染色體X就組成了問題的搜索空間。

生物的進化是以集團為主體的。與此對應，遺傳算法的運算對象是由M個個體所組成的集合，稱為群體。與生物一代一代的自然進化過程類似，遺傳算法的運算過程也是一個反復迭代過程，第t代群體記為P(t)，經過一代遺傳和進化后，得到第t?1代群體，也是由多個個體組成的集合，記為P(t?1)。這個群體不斷地經過遺傳和進化操作，并且每次都按優勝劣汰的規則將適應度較高的個體更多的遺傳到下一代，這樣最終在群體中將會得到一個優良的個體X，它達到或接近于問題的最優解X*。

遺傳算法中最優解的搜索過程也模仿生物的這種進化過程。使用所謂的遺傳算子作用于群體P(t)中，進行下述的遺傳操作，從而得到新一 2

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

代群體P(t?1)。主要操作有：

? 選擇：根據各個個體的適應度，按照一定的規則或方法，從第t代群體P(t)中選擇出一些優良的個體遺傳到下一代群體P(t?1)中； ? 交叉：將群體P(t)內的各個個體隨機搭配成對，對每一對個體，以某個概率（稱為交叉概率）交換它們之間的部分染色體； ? 變異：對群體P(t)中的每一個個體，以某一概率（稱為變異概率）改變某一個或某一些基因座上的基因值為其他的等位基因。遺傳算法的運算步驟為：

（1）初始化：設置進化代數計數器t?0；設置最大進化代數T；隨機生成M個個體作為初始群體P(0)；

（2）個體評價：計算群體P(t)中各個個體的適應度；（3）選擇運算：將選擇算子作用于群體；（4）交叉運算：將交叉算子作用于群體；

（5）變異運算：將變異算子作用于群體。群體P(t)經過選擇、交叉、變異運算之后得到下一代群體P(t?1)；

（6）終止條件判斷：若t?T，則t?t?1，轉到步驟二；若t?T，則以進化過程中所得到的具有最大適應度的個體作為最優解輸出，終止計算。

遺傳算法的執行過程如下圖所示：

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

圖1 遺傳算法的執行過程

9.2 遺傳算法的特點

與傳統的優化算法：單純形法、梯度法、動態規劃法和分枝定界法相比，遺傳算法是一類可用于復雜系統優化計算的魯棒性搜索算法。其特點主要有：

? 遺傳算法以決策變量的編碼作為運算對象。而傳統的優化算法往往是直接利用決策變量的實際值本身來進行優化計算； ? 遺傳算法直接以目標函數值作為搜索信息。而傳統的優化算法不僅需要利用目標函數值，而且往往需要目標函數的導數值等其他一些輔助信息才能確定搜索方向；

? 遺傳算法同時使用多個搜索點的搜索信息。而傳統的優化算法往往從解空間中的一個初始點開始最優解的迭代搜索過程； ? 遺傳算法使用概率搜索技術。而傳統的優化算法往往使用的是確定性的搜索方法，一個搜索點到另一個搜索點的轉移有確定的轉移方法和轉移關系，這種確定性往往也有可能使得搜索永遠達不到最優點，因而限制了算法的應用范圍。

9.3 遺傳算法的應用

遺傳算法提供了一種求解復雜系統優化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

多學科。

（1）優化函數（2）組合優化（3）生產調度問題（4）自動控制（5）機器人學（6）圖像處理（7）人工生命（8）遺傳編碼（9）機器學習

9.4 遺傳算法的構成要素及形式定義

構成遺傳算法的要素主要有：染色體編碼方法、個體適應度評價、遺傳算子、基本遺傳算法的運行參數。

（1）染色體編碼方法

在實現對一個問題用遺傳算法進行求解之前，必須先對問題的解空間進行編碼，以便于它能夠由遺傳算法進行操作。最常用的編碼方法是二進制編碼、浮點數編碼、格雷碼編碼、符號編碼等。

如，二進制編碼方法是遺傳算法中最常用的一種編碼方法，它使用的編碼符號集是由二進制符號集0和1所組成的二值符號集{0，1}，它所構成的個體基因型是一個二進制編碼符號串。

二進制編碼符號串的長度與問題所要求的求解精度有關。假設某一參數的取值范圍是[Umin,Umax]，若用長度為l的二進制編碼符號串來表示該參數，則它總共能夠產生2l種不同的編碼，即為：

00000000...00000000=0 ——> Umin 00000000...00000001=1 ——> Umin?1

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

.....11111111...11111111=2*2*2…2-1——>Umax 則二進制編碼的編碼精度為：

s?Umax?Umin l2?1假如，對于x∈[0,1023]，若用10位長的二進制編碼來表示該參數的話，則下述符號串：

X:

0 0 1 0 1 0 1 1 1 1

就可表示一個個體，它所對應的參數值為x=175。此時的編碼精度s=1。

（2）適應度函數

在遺傳算法中，模擬自然選擇的過程主要通過評估函數和適應度函數來實現的。前者是用來評估一個染色體的優劣的絕對值，后者是用來評估一個染色體相對于整個群體的優劣的相對值的大小。

但在遺傳算法中，評估函數和適應度函數的計算與應用比較相近，所以一般文獻中常混為一談。

（3）遺傳算子

基本遺傳算法使用下列三種遺傳算子：

? 選擇算子：按照某種策略從父代中挑選個體進入中間群體，如使用比例選擇；

? 交叉算子：隨機地從中間群體中抽取兩個個體，并按照某種交叉策略使兩個個體互相交換部分染色體碼串，從而形成兩個新的個體。如使用單點交叉；

? 變異算子：通常按照一定的概率（一般較小），改變染色體中某些基因的值。

（4）基本遺傳算法的運行參數

基本遺傳算法有下述4個運行參數需要提前設定：（目前無合理的理論依據）

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

? M：群體大小：即群體中所含個體的數量，一般取20-100； ? T：遺傳算法的終止進化代數，一般取為100-500； ? pc：交叉概率：一般取為0.4-0.99； ? pm：變異概率：一般取為0.0001-0.1。基本遺傳算法的形式定義為：

SGA?(C,E,P0,M,?,?,?,T)

其中，C---個體的編碼方法；

E---個體適應度評價函數；

P0---初始群體；

M---群體大小；

?---選擇算子；

?---交叉算子；

?---變異算子；

T---遺優越性運算終止條件。9.5 遺傳算法的數學理論

1.模式

定義：模式表示一些相似的模塊，它描述了在某些位置上具有相似結構特征的個體編碼串的一個子集。

不失一般性，以二進制編碼為例，個體是由二值字符集V={0，1}中的元素所組成的一個編碼串，而模式卻是由三值字符集V??{0,1,*}中的元素所組成的一個編碼串，其中“*”表示通配符，它既可被當作“1”，也可被當作“0”。如，H=1***001*就是一個模式，串A=10100011與B=10110010都是與模式H相匹配的字符串，稱為兩者相似。

定義：模式H的第一個和最后一個常量之間的距離稱為模式的定義長度，記為?(H)。

定義：模式中常量的個數稱為模式的階數，記為O(H)。

如上例中，?(H)?6,O(H)?4。再如?(*****1**)?1，O(*******1)?1 顯然，當字符串的長度固定時，模式的階數越高，能與該模式匹配的字符串（稱為樣本）數就越少，因而該模式的確定性也就越高。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

2.模式定理

在引入模式的概念之后，遺傳算法的實質可看作是對模式的一種運算。對基本遺傳算法而言，也就是某一模式H的各個樣本經過選擇運算、交叉運算、變異運算之后，得到一些新的樣本和新的模式。

假設在進化過程中的第t代時，當前群體P(t)中能與模式H匹配的個體數（樣本數）記為m(H,t)，下一代群體P(t?1)中能與模式H匹配的個體數記為m(H,t?1)。則在選擇算子、交叉算子、變異算子的連續作用下，模式H的樣本數m(H,t)的變化情況分析如下：（1）選擇算子的作用

基本遺傳算法中的選擇算子使用的是比例選擇算子。將當前群體中適應度的總和記為F(t)??F(Ai)，在這個算子作用下，與模式H所匹配

i的各個個體Ai能夠平均復制M?m(H,t?1)?

F(Ai)個個體到下一代群體中，即 F(t)M?f(H,t)?F(t)Ai?H?P(t)M?F(Ai)??F(t)Ai?H?P(t)M?f(H,t)f(H,t)?m(H,t)?m(H,t)_F(t)F(t)

（9-2）

F(t)?式中，f(H,t)是第t代群體中模式H所隱含個體的平均適應度；

_F(t)M是第t代群體的平均適應度。

若再假設模式H的平均適應度總是高出群體平均適應度的倍，則（9-2）式可改寫為

m(H,t?1)?m(H,t)(1?C)

（9-3）由此可見，m(H,t?1)為一等比級數。其通項公式為

m(H,t)?m(H,0)(1?C)t

（9-4）顯然，有

? 若C>0，則m(H,t)呈指數級增長；

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

? 若C<0，則m(H,t)呈指數級減少。

由此可得如下結論：在選擇算子作用下，對于平均適應度高于群體平均適應度的模式，其樣本數將呈指數級增長；反之，呈指數級減少。（2）交叉算子的作用

以單點交叉算子為例，見圖所示的一個模式。

隱含在該模式中的樣本與其他個體進行交叉操作時，根據交叉點的位置不同，有可能破壞該模式，也可能不破壞該模式而使其繼續生存到下一代群體中。下面估算該模式生存概率ps的下界。

顯然，當隨機設置的交叉點在模式的定義長度之內時，將有可能破壞該模式；而當隨機設置的交叉點在模式定義長度之外時，肯定不會破壞該模式。則由交叉概率pc發生時，模式H的生存概率的下界為

ps?1?pc??(H)l?（9-5）

這樣，經過選擇算子和交叉算子作用之后，模式H的樣本數滿足下式：

m(H,t?1)?m(H,t)?(1?C)?[1?pc??(H)l?1]

（9-6）

由式（9-6）知，在其他值固定的情況下（C>0）

? ?(H)越小，則m(H,t)越呈指數增長； ? ?(H)越大，則m(H,t)越不容易呈指數增長。（3）變異算子的作用

這里，以常用的基本位變異算子為例進行研究。

若某一模式被破壞，則必然是模式描述形式中通配符“*”之處的某一基因發生了變化，其發生概率是：

1?(1?pm)O(H)當pm??1時，有：

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

1?(1?pm)O(H)?O(H)?pm

由此可知，在變異算子作用下，模式H的生存概率大約是：

ps?1?O(H)?pm

（9-7）顯然知

? O(H)越小，模式H越易于生存； ? O(H)越大，模式H越易被破壞。

綜合上面的各式，并忽略一些極小項，則比例選擇算子、單點交叉算子、基本位變異算子的連續作用下，群體中模式H的子代樣本數為：

m(H,t?1)?m(H,t)?f(H,t)F(t)_?[1?pc?(H)l?1?O(H)?pm]

（9-8）

[模式定理] 遺傳算法中，在選擇、交叉和變異算子的作用下，具有低價、短的定義長度，并且平均適應度高于群體平均適應度的模式將按指數級增長。

模式定理闡述了遺傳算法的理論基礎，說明了模式的增長規律，同時也給遺傳算法的應用提供指導作用。9.6 積木塊假設與遺傳算法欺騙問題

1.積木塊假設

具有模式定理中所述的呈指數增長的模式稱為積木塊或基因塊。之所以稱為積木塊，是由于遺傳算法的求解過程并不是在搜索空間中逐一地測試各個基因的枚舉組合，而是通過一些較好的模式，像搭積木一樣，將它們拼接在一起，從而逐漸地構造出適應度越來越高的個體編碼串。

模式定理說明了積木塊的樣本呈指數增長，亦即說明了用遺傳算法尋找最優樣本的可能性，但它并未指明遺傳算法一定能夠尋找到最優樣本。

[積木塊假設] 個體的基因塊通過選擇、交叉、變異等遺傳算子作用，能夠拼接在一起，形成適應度更高的個體編碼。

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

注：積木塊假設已得到完整而嚴密的數學證明，但大量的應用實踐也已說明了其有效性。

2.遺傳算法欺騙問題（GA Deceptive Problem）

應用實踐表明，存在著一類用遺傳算法難以求解的問題，這類稱為“GA-難”的問題往往不滿足積木塊假設，即由基因塊之間的拼接，往往會欺騙遺傳算法，使其進化過程偏離最優解。

原因：各種研究結果表明，屬于“GA-難”的問題一般包含有孤立的最優點，即在這個最優點周圍是一些較差的點，從而使得遺傳算法較難通過基因之間的相互拼接而達到這個最優點的模式。實際上，目前也尚無解決這類問題的較好方法或策略。所幸的是，現實所遇到的各種應用問題中，很少有這種奇怪的性質。9.7 基于遺傳算法的數據挖掘示例

【示例】從200名腦出血和腦血栓病例中，按如下屬性：“病人的既往史”、“起病方式”、“局部癥狀”、“病理反射”、“膝腱反射”和“病情發展”等六個方面，找出這兩類病人的識別規則。其中

（1）病人的既往史

包括：高血壓（有01，無00）、動脈硬化（有01，無00）；（2）起病方式

快（01）、慢（00）；（3）局部證狀

偏癱（是01，否00）

瞳孔不等大（是01，否00）

兩便失禁（是01，否00）

語言障礙（是01，否00）

意識障礙（無00，深度01，輕度10）

（4）病理反射

陽（01），陰（00）

┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊

（5）膝腱反射

無（00），活躍（01），不活躍（10）

（6）病情發展

快（01），慢（00）

則可選30個病例作為訓練樣本，100個作為測試樣本。

a)采用二進制編碼方式。每個訓練樣本是由11個特征和1個類別組成，每個特征和類別都由2位二進制字符表示。那么，將樣本編碼成二進制字符串的消息就是一個由22位條件和2位結論組成的二元組。如，消息M=[***00101，01] b)假設訓練集是由15個腦出血和15個腦血栓患者組成30個訓練樣本。本實驗在對30個訓練樣本進行學習后，得到12條規則，學習終止于第170代。

（參見P201《數據倉庫與數據挖掘》，陳文偉、黃金才編，人民郵電出版社，2004）

c)獲取如下的7條主要規則：

（1）if 高血壓=有∧瞳孔不等大=是∧膝腱反射=不活躍 then 腦出血（11）

（2）if 瞳孔不等大=是∧語言障礙=是 then 腦出血（12）

（3）if 高血壓=有∧起病方式=快∧意識障礙=深度 then 腦出血（13）（4）if 高血壓=有∧病情發展=快 then 腦出血（15）

（5）if 高血壓=有∧動脈硬化=有∧起病方式= 慢 then 腦血栓（13）（6）if 動脈硬化=有∧病情發展=慢 then 腦血栓（15）（7）if 動脈硬化=有∧意識障礙=無 then 腦血栓（12）以上括號內的數值表示該規則的適應值。

第三篇：數據挖掘與電子商務

數據挖掘與電子商務

姓名：龔洪虎

學號:X2009230111

[摘 要] 企業的競爭優勢并不取決于信息的擁有量，而是取決于信息的處理利用能力。如何化信息優勢為競爭優勢，是企業制勝于市場的一個法寶。本文論述了一種信息處理利用的有效工具——數據挖掘方法及其在電子商務中的應用。

[關鍵詞] 數據挖掘 方法 電子商務 應用

隨著網絡技術和數據庫技術的成熟，傳統商務正經歷一次重大變革，向電子商務全速挺進。這種商業電子化的趨勢不僅為客戶提供了便利的交易方式和廣泛的選擇，同時也為商家提供了更加深入了解客戶需求信息和購物行為特征的可能性。數據挖掘技術作為電子商務的重要應用技術之一，將為正確的商業決策提供強有力的支持和可靠的保證，是電子商務不可缺少的重要工具。

一、電子商務和數據挖掘簡介。

電子商務是指個人或企業通過Internet網絡，采用數字化電子方式進行商務數據交換和開展商務業務活動。目前國內已有網上商情廣告、電子票據交換、網上訂購，網上銀行、網上支付結算等多種類型的電子商務形式。電子商務正以其成本低廉、方便、快捷、安全、可靠、不受時間和空間的限制等突出優點而逐步在全球流行。

數據挖掘(DataMining)是伴隨著數據倉庫技術的發展而逐步完善起來的。數據挖掘主要是為了幫助商業用戶處理大量存在的數據，發現其后隱含的規律性，同時將其模型化，來完成輔助決策的作用。它要求從大量的、不完全的、有噪聲的、模糊的和隨機的數據中，提取人們事先不知道的但又是潛在有用的信息和知識。數據挖掘的過程有時也叫知識發現的過程。

而電子商務中的數據挖掘即Web挖掘，是利用數據挖掘技術從www的資源(即Web文檔)和行為(即We服務)中自動發現并提取感興趣的、有用的模式和隱含的信息，它是一項綜合技術涉及到Internet技術學、人工智能、計算機語言、信息學、統計學等多個領域。

二、何謂數據挖掘及方法

確切地說，數據挖掘(Data Mining)，又稱數據庫中的知識發現(Knowledge Discovery in Database,KDD)，是指從大型數據庫或數據倉庫中提取隱含的、未知的、非平凡的及有潛在應用價值的信息或模式。它融合了數據庫、人工智能、機器學習、統計學等多個領域的理論和技術。比較典型的數據挖掘方法有關聯分析、序列模式分析、分類分析、聚類分析等。它們可以應用到以客戶為中心的企業決策分析和管理的各個不同領域和階段。

1.關聯分析。關聯分析，即利用關聯規則進行數據挖掘。關聯分析的目的是挖掘隱藏在數據間的相互關系，它能發現數據庫中形如”90%的顧客在一次購買活動中購買商品A的同時購買商品B”之類的知識。

2.序列模式分析。序列模式分析和關聯分析相似，但側重點在于分析數據間的前后序列關系。它能發現數據庫中形如”在某一段時間內，顧客購買商品A，接著購買商品B，而后購買商品C，即序列A→B→C出現的頻度較高”之類的知識，序列模式分析描述的問題是:在給定交易序列數據庫中，每個序列是按照交易時間排列的一組交易集，挖掘序列函數作用在這個交易序列數據庫上，返回該數據庫中出現的高頻序列。在進行序列模式分析時，同樣也需要由用戶輸入最小置信度C和最小支持度S。

3.分類分析。設有一個數據庫和一組具有不同特征的類別(標記)，該數據庫中的每一個②

記錄都賦予一個類別的標記，這樣的數據庫稱為示例數據庫或訓練集。分類分析就是通過分析示例數據庫中的數據，為每個類別做出準確的描述或建立分析模型或挖掘出分類規則，然后用這個分類規則對其他數據庫中的記錄進行分類。

4.聚類分析。聚類分析輸入的是一組未分類記錄，并且這些記錄應分成幾類事先也不知道，通過分析數據庫中的記錄數據，根據一定的分類規則，合理地劃分記錄集合，確定每個記錄所在類別。它所采用的分類規則是由聚類分析工具決定的。采用不同的聚類方法，對于相同的記錄集合可能有不同的劃分結果。

應用數據挖掘技術，較為理想的起點就是從一個數據倉庫開始，數據挖掘可以直接跟蹤數據并輔助用戶快速做出商業決策，用戶還可以在更新數據的時候不斷發現更好的行為模式，并將其運用于未來的決策當中。

三、選擇數據挖掘技術的兩個重要依據。

數據挖掘使用的技術很多，其中主要包括統計方法、機器學習方法、和神經網絡方法和數據庫方法。統計方法可細分為回歸分析、判別分析、聚類分析、探索性分析等。機器學習方法可細分為歸納學習方法（決策樹、規則歸納）、基于范例學習、遺傳算法等。神經網絡方法可細分為錢箱神經網絡（BP算法）、自組織神經網絡等。數據庫方法主要是多維數據分析或OLAP方法，另外還有面向屬性的歸納方法。由于每一種數據挖掘技術都有其自身的特點和實現的步驟，對數據的形式有具體的要求，并且與具體的應用問題密切相關，因此成功的應用數據挖掘技術以達到目標過程本身就是一件很復雜的事情，本文主要從挖掘任務和可獲得的數據兩個角度來討論對數據挖掘技術的選擇。

三、數據挖掘在電子商務中的應用

數據挖掘能發現電子商務客戶的的共性和個性的知識、必然和偶然的知識、獨立和關聯的知識、現實和預測的知識等，所有這些知識經過分析，能對客戶的消費行為如心理、能力、動機、需求、潛能等做出統計和正確地分析，為管理者提供決策依據。具體應用如下：

1.分類與預測方法在電子商務中的應用。在電子商務活動中，分類是一項非常重要的任務，也是應用最多的技術。分類的目的是構造一個分類函數或分類模型，通常稱作分類器。分類器的構造方法通常由統計方法、機器學習方法、神經網絡方法等。這些方法能把數據庫中的數據映射到給定類別中某一個，以便用于預測，也就是利用歷史數據記錄，自動推導出給定數據的推廣描述，從而對未來數據進行預測。

2.聚類方法在電子商務中的應用。聚類是把一組個體按照相似性原則歸成若干類別。對電子商務來說，客戶聚類可以對市場細分理論提供有力的支持。市場細分的目的是使得屬于同一類別的個體之間的距離盡可能小，而不同類別的個體之間的距離盡可能大，通過對聚類的客戶特征的提取，電子商務網站可以為客戶提供個性化的服務。

3.數據抽取方法在電子商務中的應用。數據抽取的目的是對數據進行濃縮，給出它的緊湊描述，如求和值、平均值、方差值、等統計值、或者用直方圖、餅狀圖等圖形方式表示，更主要的是他從數據泛化的角度來討論數據總結。數據泛化是一種把最原始、最基本的信息數據從低層次抽象到高層次上的過程。可采用多維數據分析方法和面向屬性的歸納方法。在電子商務活動中，采用維數據分析方法進行數據抽取，他針對的是電子商務活動中的客戶數據倉庫。在數據分析中經常要用到諸如求和、總計、平均、最大、最小等匯集操作，這類操作的計算量特別大，可把匯集操作結果預先計算并存儲起來，以便用于決策支持系統使用。

4.關聯規則在電子商務中的應用。管理部門可以收集存儲大量的售貨數據和客戶資料，對這些歷史數據進行分析并發現關聯規則。如分析網上顧客的購買行為，幫助管理者規劃市場，確定商品的種類、價格、質量等。通常關聯規則有兩種：有意義的關聯規則和泛化關聯規則，有意義的關聯規則，即滿足最小支持度和最小可信度的規則。最小支持度，它表示一組對象在統計意義上的需滿足的最低程度，如電子商務活動中的客戶數量、客戶消費能力、消費方式等。后者即用戶規定的關聯規則的最低可靠度。第二是泛化規則，這種規則更實用，因為研究對象存在一種層次關系，如面包、蛋糕屬西點類，而西點又屬于食品類，有了層次關系后，可以幫助發現更多的有意義的規則。

5、優化企業資源

節約成本是企業盈利的關鍵。基于數據挖掘技術，實時、全面、準確地掌握企業資源信息，通過分析歷史的財務數據、庫存數據和交易數據, 可以發現企業資源消耗的關鍵點和主要活動的投入產出比例, 從而為企業資源優化配置提供決策依據, 例如降低庫存、提高庫存周轉率、提高資金使用率等。通過對Web數據挖掘，快速提取商業信息，使企業準確地把握市場動態，極大地提高企業對市場變化的響應能力和創新能力，使企業最大限度地利用人力資源、物質資源和信息資源，合理協調企業內外部資源的關系，產生最佳的經濟效益。促進企業發展的科學化、信息化和智能化。

例如:美國運通公司(American Express)有一個用于記錄信用卡業務的數據庫，數據量達到54億字符，并仍在隨著業務進展不斷更新。運通公司通過對這些數據進行挖掘，制定了“關聯結算(Relation ship Billing)優惠”的促銷策略，即如果一個顧客在一個商店用運通卡購買一套時裝，那么在同一個商店再買一雙鞋，就可以得到比較大的折扣，這樣既可以增加商店的銷售量，也可以增加運通卡在該商店的使用率。

6、管理客戶數據

隨著“以客戶為中心”的經營理念的不斷深入人心, 分析客戶、了解客戶并引導客戶的需求已成為企業經營的重要課題。基于數據挖掘技術，企業將最大限度地利用客戶資源，開展客戶行為的分析與預測，對客戶進行分類。有助于客戶盈利能力分析，尋找潛在的有價值的客戶，開展個性化服務，提高客戶的滿意度和忠誠度。通過Web資源的挖掘，了解客戶的購買習慣和興趣，從而改善網站結構設計，推出滿足不同客戶的個性化網頁。利用數據挖掘可以有效地獲得客戶。比如通過數據挖掘可以發現購買某種商品的消費者是男性還是女性,學歷、收入如何, 有什么愛好,是什么職業等等。甚至可以發現不同的人在購買該種商品的相關商品后多長時間有可能購買該種商品, 以及什么樣的人會購買什么型號的該種商品等等。在采用了數據挖掘后, 針對目標客戶發送的廣告的有效性和回應率將得到大幅度的提高, 推銷的成本將大大降低。同時，在客戶數據挖掘的基礎上，企業可以發現重點客戶和評價市場性能，制定個性化營銷策略，拓寬銷售渠道和范圍，為企業制定生產策略和發展規劃提供科學的依據。通過呼叫中心優化與客戶溝通的渠道，提高對客戶的響應效率和服務質量，促

①進客戶關系管理的自動化和智能化。

三、結束語

電子商務是現代信息技術發展的必然結果，也是未來商業運作模式的必然選擇。利用數據挖掘技術，充分發揮企業的獨特優勢，促進管理創新和技術創新，使企業在在電子商務的潮流中立于不敗之地。隨著數據挖掘算法的不斷發展和成熟，數據挖掘一定會有更加廣闊的應用前景。

參考文獻：

(1)《淺談數據挖掘在電子商務中的運用》 鐘連福；

(2)《電子商務中商業數據的挖掘方法》 中國電子商務研究中心；

(3)《在電子商務中如何正確有使用數據挖掘技術》 俠名；

(4)《曾貞:數據挖掘在電子商務中的應用》 甘肅農業,2004（7）；

(5)《馮艷王堅強:數據挖掘在電子商務上的應用》 2002（3）；

(6)《呂延杰徐華飛:中國電子商務發展研究報告》北京郵電大學出版社 ；

(7)《數據挖掘與電子商務》 鄧鯤鵬，周延杰，嚴瑜筱。①

第四篇：數據挖掘心得體會

心得體會

這次數據挖掘實驗結束了，期間我們小組明確分工并積極去完成，雖然有點辛苦，但我感覺充實而有收獲感！

根據老師給的一些資料，我們決定采用SQL Server 2000中的Northwind數據庫里的數據作為我們的實驗數據。根據表Order Details中的數據，我們分別根據ProductID和OrderID字段，并結合我們規定的最小支持度閥值對數據進行篩選。依次篩選出1項頻繁集、2項頻繁集和3項頻繁集，其中還會使用游標的方式來遍歷2項集與3項集的候選集，分別選出2項頻繁集和3項頻繁集。

由于數據較多，因此過程比較復雜，要編寫很多的查詢語句，建立許多數據表，包括臨時表。開始不知道則操作，但經過我們各自多次重復的建表與查詢，逐漸的理解和有了自己的思路。尤其是在運用游標的方法進行遍歷這塊，因為我們比較陌生而不理解，操作時一時無法實現結果，但經過我們在網上查詢了解相關知識，最終得以解決。

經過該次實驗，使我對數據庫的操作更加熟練，而且還使我對課本上的“挖掘頻繁模式”這塊知識有了很好的掌握，今后我會多做實驗，使我在實際操作過程中學得更好！

第五篇：數據挖掘試題

《數據挖掘》總復習題

1．數據挖掘系統可以根據什么標準進行分類？

答：根據挖掘的數據庫類型分類、根據挖掘的知識類型分類、根據挖掘所用的技術分類、根據應用分類

2．知識發現過程包括哪些步驟？

答：數據清理、數據集成、數據選擇、數據變換、數據挖掘、模式評估、知識表示3．什么是概念分層？

答：一個映射序列，將低層概念映射到更一般的較高層概念。4．多維數據模型上的 OLAP 操作包括哪些？

答：上卷、下鉆、切片和切塊、轉軸 / 旋轉、其他OLAP操作5．OLAP 服務器類型有哪幾種？

答：關系 OLAP 服務器(ROLAP)、多維 OLAP 服務器(MOLAP)、混合 OLAP 服務器(HOLAP)、特殊的 SQL 服務器6．數據預處理技術包括哪些？

答：聚集、抽樣、維規約、特征子集選擇、特征創建、離散化和二元化、變量變換。7． 什么是數據清理？

答：填寫缺失的值，平滑噪聲數據，識別、刪除離群點，解決不一致性 8． 什么是數據集成？

答：集成多個數據庫、數據立方體或文件 9．什么是數據歸約？

答：得到數據集的壓縮表示，它小得多，但可以得到相同或相近的結果 10．數據清理的內容包括哪些？

答：缺失值、噪聲數據、數據平滑、聚類、回歸11.將下列縮略語復原

OLAP——on-line analytical processing DM——data mining

KDD——knowledge discovery in databases OLTP——on-line transaction processingDBMS——database management system DWT——discrete wavelet transform

（DMQL）－－Data Mining Query Language 12．什么是數據挖掘？

答：簡單地說，數據挖掘是從大量數據中提取或挖掘知識。具體地說，數據挖掘就是從大量的、不完全的、有噪聲的、模糊的、隨機的實際 應用數據中，提取隱含在其中的、人們事先不知道的、但又是潛在有用的信息和 知識的過程。13．什么是關聯規則？ 答：（關聯規則是形如X→Y的蘊涵式，其中且，X和Y分別稱為關聯規則的先導和后繼。）假設I是項的集合。給定一個交易數據庫，其中每個事務(Transaction)t是I的非空子集，即，每一個交易都與一個唯一的標識符TID(Transaction ID)對應。關聯規則在D中的支持度(support)是D中事務同時包含X、Y的百分比，即概率；置信度(confidence)是包含X的事務中同時又包含Y的百分比，即條件概率。關聯規則是有趣的，如果滿足最小支持度閾值和最小置信度閾值。這些閾值是根據挖掘需要人為設定。

（關聯規則反映一個事物與其它事物之間的相互依存性和關聯性，如果兩個事物或者多個事物之間存在一定的關聯關系，那么其中一個事物就能夠通過其他事物預測到。）15.什么是概念描述？什么是特征化？什么是屬性相關分析？

答：概念描述：用匯總的、簡潔的和精確的方式描述各個類和概念可能是有用的。特征化：是目標類數據的一般特性或特征的匯總。

屬性相關分析：可能需要在分類和預測之前進行，它試圖識別對于分類或預測過程無用的屬性。這些屬性應當排除。

16．什么是數據倉庫？其主要特征是什么？

答：數據倉庫是一個提供決策支持功能的數據庫，它與組織機構的操作數據庫分別維護。它允許將各種應用系統集成在一起，為統一的歷史數據分析提供堅實的平臺，對信息處理提供支持。

特征：面向主題、數據集成、隨時間而變化、數據不易丟失（數據不易丟失是最明顯特征）17．什么是數據集市？

答：數據集市包含企業范圍數據的一個子集，對于特定的用戶群是有用的。其范圍限于選定的主題。

(是完整的數據倉庫的一個邏輯子集，而數據倉庫正是由所有的數據集市有機組合而成的)18．數據庫中的知識發現過程由哪幾個步驟組成？

答：數據清理、數據倉庫、任務相關數據、數據挖掘、模式評估、知識表示 19．典型的數據挖掘系統有哪幾個主要成分？

答：數據庫、數據倉庫、萬維網或其他信息庫；數據庫或數據倉庫服務器；知識庫；數據挖掘引擎；模式評估模塊；用戶界面

20．從軟件工程的觀點來看，數據倉庫的設計和構造包含哪些步驟？

答：規劃、需求研究、問題分析、倉庫設計、數據集成和測試、部署數據倉庫。21．在數據挖掘系統中，為什么數據清理十分重要？

答： 臟數據的普遍存在，使得在大型數據庫中維護數據的正確性和一致性成為一個極其困難的任務。

22．臟數據形成的原因有哪些？

答：濫用縮寫詞、數據輸入錯誤、數據中的內嵌控制信息、不同的的慣用語、重復記錄、丟失值、拼寫變化、不同的計量單位、過時的編碼23．數據清理時，對空缺值有哪些處理方法？

答：忽略元組、人工填寫缺失值、使用一個全局變量填充缺失值、使用屬性的平均值填充缺失值、使用與給定元組屬同一類的所有樣本的屬性均值、使用最可能的值填充缺失值 24．什么是數據變換？包括哪些內容？

答：將數據轉換或統一成適合于挖掘的形式。包括：光滑、聚集、數據泛化、規范化、屬性構造 25． 數據歸約的策略包括哪些？

答：數據立方體聚集、性子集選擇、維度歸約、數值歸約、離散化和概念分層產生 26．提高數據挖掘算法效率有哪幾種思路？

答：減少對數據的掃描次數；縮小產生的候選項集；改進對候選項集的支持度計算方法 27．假定屬性income的最小值與最大值分別為12000和980到區間[0.0，1.0]，根據 min-max 規范化，income的值73600將變為＿3631/551＿。

28．假定屬性income的平均值和標準差分別為54000和16000，使用 Z-score 規范化，值73600被轉換為＿1.225＿。

29．假定A的值由-986到917.A的最大絕對值為986，使用小數定標規范化，-986被規范化為＿-0.986＿

30．從結構角度來看，有哪三種數據倉庫模型。答：企業倉庫、數據集市、虛擬倉庫

31．什么是聚類分析？它與分類有什么區別？

答：將物理或抽象對象的集合分組成為由類似的對象組成的多個類的過程 區別：分類有監督 聚類無監督 分類要靠學習聚類要靠啟發式搜索 32．與數據挖掘類似的術語有哪些?

答：數據庫中挖掘知識、知識提取、數據/模式分析、數據考古和數據捕撈。33．解釋下列術語 34．翻譯下列術語

Data Mining 數據挖掘Data warehousing 數據倉庫Data Mart 數據集市

drill-down 下鉆roll-up上卷OLAP 聯機分析處理Data cube 數據立方體 Association rule 關聯規則Data cleaning數據清理Data integration 數據集成 Data transformation數據變換Data reduction 數據歸約

35．可以對按季度匯總的銷售數據進行___B___，來觀察按月匯總的數據。A 上卷 B 下鉆 C 切片 D 切塊

36．可以對按城市匯總的銷售數據進行____A__，來觀察按國家總的數據。A 上卷 B 下鉆 C 切片 D 切塊

37．通過不太詳細的數據得到更詳細的數據，稱為____B____。A 上卷 B 下鉆 C 細化 D 維規約

38．三層數據倉庫結構中，從底層到尾層分別是_倉庫數據服務器、OLAP服務器、前端客戶層__。

42．常用的四種興趣度的客觀度量。

答：簡單性 確定性 實用性 新穎性43．四種常用的概念分層類型。

答：模式分層、集合分組分層、操作導出的分層、基于規則的分層45．如何理解現實世界的數據是“骯臟的”？答：不完整的、含噪聲的、不一致的、重復的 46．多維數據倉庫有哪幾種概念模型？

答：星形模式、雪花形模式或事實星座形模式。

48.在多路數組聚集算法中，如何盡量少地占用內存？

答：將最小的平面放在內存中，將最大的平面每次只是提取并計算一塊。49.給出方體的維數，會計算各D方體有多少，總的方體個數有多少？2^n50．什么是離群點？離群點都需要刪除嗎？為什么？

答：離群點：一些與數據的一般行為或模型不一致的孤立數據。不需要。通常離群點被作為“噪音”或異常被丟棄，但在欺詐檢測中卻可以通過對罕見事件進行離群點分析而得到結論。

【51.所有模式都是有趣的嗎？

答：一個模式是有趣的，如果(1)它易于被人理解 ；（2）在某種程度上，對于新的或測試數據是有效的；（3）具有潛在效用；（4）新穎的；（5）符合用戶確信的某種假設。】