數(shù)據(jù)倉庫與數(shù)據(jù)挖掘

數(shù)據(jù)倉庫與數(shù)據(jù)挖掘數(shù)據(jù)挖掘（DataMining）概念從大量的、不完全的、有噪聲的、模糊的、隨機的實際應用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在價值的信息和知識的過程。簡單的說，數(shù)據(jù)挖掘就是從大量數(shù)據(jù)中提取或“挖掘”知識，因此又被稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)(KnowledgeDiscoveryinDatabase,KDD)數(shù)據(jù)挖掘的類型按方法分：直接數(shù)據(jù)挖掘：對某個變量建立一個模型；包括分類、估值和預測

間接數(shù)據(jù)挖掘：在所有的變量中建立起某種關(guān)系；

如相關(guān)性分組或關(guān)聯(lián)規(guī)則，聚類，描述和可視化，及復雜數(shù)據(jù)挖掘按任務分：PredictionMethods

Usesomevariablestopredictunknownorfuturevaluesofothervariables.

DescriptionMethods

Findhuman-interpretablepatterns/rulesthatdescribegivendata.

數(shù)據(jù)挖掘&知識發(fā)現(xiàn)kDD的關(guān)系：知識發(fā)現(xiàn)（KnowledgeDiscoveryinDatabases）是用數(shù)據(jù)庫管理系統(tǒng)來存儲數(shù)據(jù)，用機器學習的方法來分析數(shù)據(jù)，挖掘大量數(shù)據(jù)背后隱藏的知識，稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)。所謂基于數(shù)據(jù)庫的知識發(fā)現(xiàn)（KDD）是指從大量數(shù)據(jù)中提取有效的、新穎的、潛在有用的、最終可被理解的模式的非平凡過程。(1)KDD是“數(shù)據(jù)挖掘”的一種更廣義的說法；

(2)數(shù)據(jù)挖掘是整個KDD過程的核心。頻繁模式–數(shù)據(jù)庫中出現(xiàn)頻繁的模式(項集,序列,等等)可信度（Confidence）—設W中支持物品集A的事務中，有c％的事務同時也支持物品集B，c％稱為關(guān)聯(lián)規(guī)則A→B的可信度。支持度（Support）—設W中有s％的事務同時支持物品集A和B，s％稱為關(guān)聯(lián)規(guī)則A→B的支持度。最小支持度–表示規(guī)則中的所有項在事務中出現(xiàn)的頻度

最小可信度–表示規(guī)則中左邊的項(集)的出現(xiàn)暗示著右邊的項(集)出現(xiàn)的頻度頻繁集–支持度大于或等于supmin的項集稱為頻繁項集，滿足最小支持度的項集FP-樹構(gòu)建掃描事務數(shù)據(jù)庫D一次,得到頻繁項的集合F及它們的支持度.將F按支持度降序排列成L,L是頻繁項的列表.創(chuàng)建FP-樹的根,標注其為NULL.對D中的每個事務進行以下操作:根據(jù)L中的次序?qū)κ聞罩械念l繁項進行選擇和排序.設事務中的已排序的頻繁項列表為[p|P],其中p表示第一個元素,P表示剩余的列表.調(diào)用insert_Tree([p|P],T).

分類的定義

分類是指把數(shù)據(jù)樣本映射到一個事先定義的類中的學習過程，即給定一組輸入的屬性向量及其對應的類，用基于歸納的學習算法得出分類.

分類過程獲取數(shù)據(jù)：數(shù)據(jù)的表示（圖像—文字、指紋，波形--腦電圖、心電圖、機械振動波等，物理數(shù)據(jù)既包含數(shù)值型數(shù)據(jù)，也包含描述型數(shù)據(jù)，邏輯數(shù)據(jù)--只有兩種取值的描述型的數(shù)據(jù)）輸入數(shù)據(jù)、對數(shù)據(jù)進行量化預處理：去除噪聲數(shù)據(jù)、對缺失值進行處理

數(shù)據(jù)集成或者變換（維數(shù)災難，降維）分類器設計：劃分數(shù)據(jù)集（給定帶類標號的數(shù)據(jù)集，并且把數(shù)據(jù)集劃分為兩個部分：訓練集和測試集）

分類器構(gòu)造（利用訓練集構(gòu)造分類器，也就是建立分類模型）

分類器測試（利用測試集對分類器的分類性能進行評估）分類決策：對未知類標號的數(shù)據(jù)樣本（測試樣本）進行分類分類的評價準則

給定測試集Xtest={(xi,yi)|i=1,2,…,N}

N表示測試集中的樣本個數(shù)

xi表示測試集中的數(shù)據(jù)樣本

yi表示數(shù)據(jù)樣本xi的類標號

對于測試集的第j個類別，假設

被正確分類的樣本數(shù)量為TPj

被錯誤分類的樣本數(shù)量為FNj

其他類別被錯誤分類為該類的樣本數(shù)據(jù)量為FPj精確度：代表測試集中被正確分類的數(shù)據(jù)樣本所占的比例

查全率：表示在本類樣本中被正確分類的樣本所占的比例

查準率：表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例

F-measure：是查全率和查準率的組合表達式

幾何均值：是各個類別的查全率的平方根

決策樹的基本概念適用于離散值屬性、連續(xù)值屬性

采用自頂向下的遞歸方式產(chǎn)生一個類似于流程圖的樹結(jié)構(gòu)

在根節(jié)點和各內(nèi)部節(jié)點上選擇合適的描述屬性，并且根據(jù)該屬性的不同取值向下建立分枝決策樹的優(yōu)點：

1）進行分類器設計時，決策樹分類方法所需時間相對較少

2）決策樹的分類模型是樹狀結(jié)構(gòu)，簡單直觀，比較符合人類的理解方式

3）可以將決策樹中到達每個葉節(jié)點的路徑轉(zhuǎn)換為IF—THEN形式的分類規(guī)則，這種形式更有利于理解

決策樹的難點：

1）如何選擇一個好的分支取值

好的分支取值可以加快決策樹的生長，更重要的是產(chǎn)生結(jié)構(gòu)好的決策樹

相反，差的分支取值不但影響決策樹的生長，更重要的是產(chǎn)生的決策樹分支過細、結(jié)構(gòu)差，難以發(fā)現(xiàn)有用的規(guī)則信息。2）取信息增益（InformationGain）較大的對應劃分

ID3是采用“信息增益”來選擇分裂屬性的。雖然這是一種有效的方法，但其具有明顯的傾向性，即它傾向于選擇取值較多的屬性;

C4.5算法使用信息增益比來選擇分枝屬性，克服了ID3算法使用信息增益時偏向于取值較多的屬性的不足

Whichoneisbetter?B1orB2?Why?

Howdoyoudefinebetter?Findhyperplanemaximizesthemargin=>B1isbetterthanB24種核函數(shù)Simplelinearkernel:K(Xi,Xj)=Xi’*Xj2種多類Multiclass惰性學習與積極學習的概念與區(qū)別Lazyvs.eagerlearning(惰性學習vs.積極學習)

Lazylearning:Simplystorestrainingdata(oronlyminorprocessing)andwaitsuntilitisgivenatesttuple

Eagerlearning:Givenasetoftrainingtuples,constructsaclassificationmodelbeforereceivingnewdatatoclassify

Lazy:lesstimeintrainingbutmoretimeinpredicting

Accuracy

Lazy:effectivelyusesaricherhypothesisspacesinceitusesmanylocallinearfunctionstoformanimplicitglobalapproximationtothetargetfunction

Eager:mustcommittoasinglehypothesisthatcoverstheentireinstancespace

k-NN是惰性、分類、基于instance的學習方法Top10DataMiningAlgorithm1.C4.56.PageRank(網(wǎng)頁排名)2.k-means7.AdaBoost

3.SVM(SupportVectorMachines)8.kNN4.Apriori9.NaiveBayes5.EM(ExpectationMaximization)10.CARTkNNClassification:Advantages1）Simpletechniquethatiseasytobeimplemented

2）Buildingmodelisinexpensive

3）Extremelyflexibleclassificationscheme

doesnotinvolvepreprocessing

4）Wellsuitedfor

Multi-modalclasses(classesofmultipleforms)

Recordswithmultipleclasslabels

5）Cansometimesbethebestmethod

MichihiroKuramochiandGeorgeKarypis,GeneClassificationusingExpressionProfiles:AFeasibilityStudy,InternationalJournalonArtificialIntelligenceTools.Vol.14,No.4,pp.641-660,2005

KnearestneighboroutperformedSVMforproteinfunctionprediction(蛋白質(zhì)功能預測)usingexpressionprofiles

kNNClassification:DisadvantagesClassifyingunknownrecordsarerelativelyexpensive

Requiresdistancecomputationofk-nearestneighbors

Computationallyintensive,especiallywhenthesizeofthetrainingsetgrowsAccuracycanbeseverelydegradedbythepresenceofnoisyorirrelevantfeaturesNNclassificationexpectsclassconditionalprobabilitytobelocallyconstant

biasofhighdimensions

貝葉斯概念，組成貝葉斯網(wǎng)絡：描述隨機變量（事件）之間依賴關(guān)系的一種圖形模式

是一種用來進行推理的模型

網(wǎng)絡結(jié)構(gòu)和條件概率表兩部分組成（網(wǎng)絡結(jié)構(gòu)是一個有向無環(huán)圖結(jié)點和有向?。〣ayesianbeliefnetwork(alsoknownasBayesiannetwork,probabilisticnetwork):allowsclassconditionalindependenciesbetweensubsetsofvariables

Twocomponents:(1)Adirectedacyclicgraph有向無環(huán)圖(calledastructure)(2)asetofconditionalprobabilitytables(CPTs)

貝葉斯決策概念與過程利用貝葉斯定理求得后驗概率，據(jù)以進行決策的方法，稱為貝葉斯決策方法。已具備先驗概率的情況下，貝葉斯決策過程的步驟為：（1）進行預后驗分析，取得條件概率，包括歷史概率和邏輯概率，對歷史概率要加以檢驗，辨明其是否適合計算后驗概率。（2）用概率的乘法定理計算聯(lián)合概率，用概率的加法定理計算邊際概率,用貝葉斯定理計算后驗概率（3）用后驗概率進行決策分析。

第一階段——準備工作階段，這個階段的任務是為樸素貝葉斯分類做必要的準備。

第二階段——分類器訓練階段。

第三階段——應用階段。這個階段的任務是使用分類器對待分類項進行分類，其輸入是分類器和待分類項，輸出是待分類項與類別的映射關(guān)系。

貝葉斯3概率3公式先驗概率：根據(jù)歷史的資料或主觀判斷所確定的各種時間發(fā)生的概率

后驗概率：通過貝葉斯公式，結(jié)合調(diào)查等方式獲取了新的附加信息，對先驗概率修正后得到的更符合實際的概率

條件概率：某事件發(fā)生后該事件的發(fā)生概率

條件概率公式：A1和B表示在一個樣本空間中的兩個事件，給定B條件下A1發(fā)生的條件概率公式為：

全概率公式：B1，B 2,…，Bn為樣本空間中的一組事件，對于每一次試驗，B1，B2,…，Bn中只有一個事件發(fā)生：

貝葉斯公式：獨立互斥且完備的后驗事件概率可以由先驗事件的概率和相應條件概率決定

貝葉斯網(wǎng)絡的3個主要議題

貝葉斯網(wǎng)絡預測：從起因推測一個結(jié)果的推理

貝葉斯網(wǎng)絡診斷：從結(jié)果推測一個起因的推理

貝葉斯網(wǎng)絡學習：由先驗的Bayes網(wǎng)絡得到后驗的Bayes網(wǎng)絡的過程

神經(jīng)網(wǎng)絡概念與結(jié)構(gòu)

Artificialneuralnetwork(ANN)isamachinelearningapproachthatmodelshumanbrainandconsistsofanumberofartificialneurons.

Anartificialneuralnetwork(ANN)consistsofapoolofsimpleprocessingunitswhichcommunicatebysendingsignalstoeachotheroveralargenumberofweightedconnections.

人工神經(jīng)網(wǎng)絡的發(fā)展與類型

人工神經(jīng)網(wǎng)絡的發(fā)展：啟蒙階段：感知器模型

低潮時期：線性不可分問題

復興時期：Hopfield模型

神經(jīng)網(wǎng)絡的類型：前向型反饋型隨機型自組織競爭型

神經(jīng)網(wǎng)絡作為分類器的優(yōu)缺點Strength

1）Hightolerancetonoisydata

2）Abilitytoclassifyuntrainedpatterns

3）Well-suitedforcontinuous-valuedinputsandoutputs

4）Successfulonanarrayofreal-worlddata,e.g.,hand-writtenletters

5）Algorithmsareinherentlyparallel

6）Techniqueshaverecentlybeendevelopedfortheextractionofrulesfromtrainedneuralnetworks

Weakness

1）Longtrainingtime

2）Highcomplexityofthenetworkstructure:requireanumberofparameterstypicallybestdeterminedempirically,e.g.,thenetworktopologyor“structure.”

3）Poorinterpretability:Difficulttointerpretthesymbolicmeaningbehindthelearnedweightsandof“hiddenunits”inthenetwork

人工神經(jīng)網(wǎng)絡特點

1）初步的自適應與自組織能力

在學習或訓練過程中改變突觸權(quán)重值，以適應周圍環(huán)境的要求

2）泛化能力

泛化能力指對沒有訓練過的樣本，有很好的預測能力和控制能力

3）非線性映射能力

系統(tǒng)很復雜，或者系統(tǒng)未知，系統(tǒng)信息量很少時，建立精確的數(shù)學模型很困難時，神經(jīng)網(wǎng)絡的非線性映射能力則表現(xiàn)出優(yōu)勢

4）高度并行性

從功能的模擬角度上看，神經(jīng)網(wǎng)絡也應具備很強的并行性

ComparisonofBrainsandTraditionalComputersBrains

200billionneurons,32trillionsynapses

Elementsize:10-6m

Energyuse:25W

Processingspeed:100Hz

Parallel,Distributed(并行，分布)

FaultTolerant

Learns:Yes

Intelligent/Conscious:Usually

TraditionalComputers1billionbytesRAMbuttrillionsofbytesondisk

Elementsize:10-9m

Energywatt:30-90W(CPU)

Processingspeed:109Hz

Serial,Centralized(串行，集中)

GenerallynotFaultTolerant

Learns:Some

Intelligent/Conscious:GenerallyNo

單、多層解決的問題SingleLayerFeed-forwardNN

LinearNN

Or,AndMulti-LayerFeed-forwardNN

NonlinearNN

XOR

BackPropagation(BP)

遺傳算法相關(guān)概念基因—基因（Gene）是遺傳的基本單位，是個體的基本組成單元。

個體—在生物學中，個體（Individual）由多個基因組成。遺傳算法中，個體代表待優(yōu)化問題的一個解。

編碼—將問題的解轉(zhuǎn)換成基因序列的過程稱為編碼(Encoding)，編碼是由解空間到遺傳算法空間的映射。解碼—將基因型轉(zhuǎn)換成問題的解的過程稱為解碼（Decoding)。

種群—生物的遺傳進化不能僅通過自身進行，而需要在一個群體中進行，這一群體稱為種群(Population)。種群中的單個組成元素是個體。種群規(guī)模是遺傳算法的參數(shù)之一，種群規(guī)模的設置可能會影響到遺傳算法的優(yōu)化效果。

適應度—在研究自然界中生物的遺傳與進化現(xiàn)象時，生物學中使用適應度(Fitness)這個術(shù)語來衡量某個物種對于生存環(huán)境的適應程度。

代—在生物的繁衍過程中，個體從出生到死亡即為一代(Generation)，在遺傳算法中，代的意思為遺傳算法的迭代次數(shù)?？勺鳛檫z傳算法的一個結(jié)束標志。

遺傳算子—指作用在個體上的各種遺傳操作。類型：選擇算子、交叉算子和變異算子。

選擇(Selection)算子：在適應度的基礎(chǔ)上，按照某種規(guī)則或方法從當前代的種群中選擇出一些適應度高的個體遺傳到下一代種群中。

交叉(Crossover)算子：以某一概率（交叉概率）選擇種群中的個體，把兩個父個體的部分基因加以替換、重組而生成新的個體。

變異(Mutation)算子：以某一概率（變異概率）選擇種群中的個體，改變其個體中某些基因的值或?qū)ζ鋫€體進行某種方式的重組。

遺傳算法過程適應度函數(shù)：體現(xiàn)了個體的生存環(huán)境，是通過對目標函數(shù)的轉(zhuǎn)換而形成的。

設計適應度函數(shù)一般主要滿足的條件：

連續(xù)、非負

適應度函數(shù)設計應盡可能簡單

適應度函數(shù)對某一類具體問題，應盡可能通用

One-pointcrossoverTwo-pointcrossover粗糙集等價關(guān)系—設R為定義在集合A上的一個關(guān)系，若R是自反的，對稱的和傳遞的，則稱R為等價關(guān)系。

2)等價類—設R為集合A上的等價關(guān)系，對任何a∈A，集合[a]R={x|x∈A,aRx}稱為元素a形成的R等價類。由等價類的定義可知[a]R是非空的，因為a∈[a]R

3）知識—一種將現(xiàn)實或抽象的對象進行分類的能力

4）知識庫—當給定了一個數(shù)據(jù)上的等價關(guān)系集合，在等價關(guān)系集合下對該數(shù)據(jù)集合進行的劃分，則就會被稱為知識庫

5）族集—論域U上的一族劃分稱為關(guān)于U的一個知識庫

一個知識庫就是一個關(guān)系系統(tǒng)K=(U,R)，其中U是非空有限集，R為U上等價關(guān)系的一個族集

6）不可辨識關(guān)系—若P∈R，且P≠φ，則P中所有等價關(guān)系的交集也是一個等價關(guān)系，稱為P上的不可辨識關(guān)系，記為ind(P)

7）U/ind(P)—表示與等價關(guān)系P相關(guān)的知識，稱為K中關(guān)于U的P基本知識(基本集)，簡稱U/P。（即等價關(guān)系ind(P)的所有等價類）

8）下近似集—一個知識庫K=(U,R)，令XU且R為U上一等價關(guān)系，X的下近似集就是對于知識R能完全確定地歸入集合X的對象的集合，記作R_(X)={x|x∈U,[x]R?X}

9）上近似集—知識R的在U中一定和可能歸入集合X的對象的集合，記作R-(X)={x|x∈U,[x]R∩X≠φ}

10）正域（下近似）—是指知識R和知識U中所有包含在X的對象的集合，記作POSR(X)=R_(X)

11）負域—是指知識U和知識U中肯定能包含在U-X中元素的集合，記作NEGR(X)=U-R-(X)

12）邊界—指的是知識R和知識U中既不能歸入X，也不能肯定歸入U-X的元素的集合，記作BNR(X)=R-(X)-R_(X)

13）由等價關(guān)系R描述的對象集X的近似精度為：如果dR(X)=0，則X是R全部不可定義的；

（2）如果dR(X)=1，則X是R全部可定義的；

（3）如果0<dR(X)<1，則X是R部分可定義的。

分別為X上近似集合、下近似集合中元素的個數(shù)。

X的粗糙度——PR(X)=1-dR(X)反映了定義集合X的粗糙程度，也即不被關(guān)系R所描述的程度。

14）對于知識庫K=(U,R)，如果存在等價關(guān)系r∈R,使得ind(r)=ind(R)，則稱r是可省略的，否則，稱r是不可省略的。

（1）若任意r∈R是不可省略的，則稱R是獨立的

（2）獨立等價關(guān)系的子集也是獨立的15）對于知識庫K=(U,R)，R=(P,S)，將S的P正域定義為

16）如果存在r，使得成立，則稱r為P中相對于S是可省略的，否則稱r為P中相對于S是不可省略的

17）若Q=P-r,POSQ(S)=POSP(S),且Q為最小集，則稱Q為P相對于S的簡化，記作redS(P)。18）P相對于S的核是P相對于S的所有簡化的交集

聚類Attachthesamelabeltodatapointsthatare“close”toeachotheringivenset與分類的區(qū)別如何度量聚類好壞Agoodclusteringmethodwillproducehighqualityclusters

highintra-classsimilarity:compactnesswithinclusters

lowinter-classsimilarity:separationbetweenclustersThequalityofaclusteringmethoddependson

thesimilaritymeasureused

itsimplementation,and

Itsabilitytodiscoversomeoral