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

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

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

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

Usesomevariablestopredictunknownorfuturevaluesofothervariables.

DescriptionMethods

Findhuman-interpretablepatterns/rulesthatdescribegivendata.

數(shù)據(jù)挖掘&知識發(fā)現(xiàn)kDD的關(guān)系：知識發(fā)現(xiàn)（KnowledgeDiscoveryinDatabases）是用數(shù)據(jù)庫管理系統(tǒng)來存儲數(shù)據(jù)，用機(jī)器學(xué)習(xí)的方法來分析數(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)頻繁的模式(項(xiàng)集,序列,等等)可信度（Confidence）—設(shè)W中支持物品集A的事務(wù)中，有c％的事務(wù)同時也支持物品集B，c％稱為關(guān)聯(lián)規(guī)則A→B的可信度。支持度（Support）—設(shè)W中有s％的事務(wù)同時支持物品集A和B，s％稱為關(guān)聯(lián)規(guī)則A→B的支持度。最小支持度–表示規(guī)則中的所有項(xiàng)在事務(wù)中出現(xiàn)的頻度

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

分類的定義

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

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

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

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

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

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

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

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

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

對于測試集的第j個類別，假設(shè)

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

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

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

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

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

F-measure：是查全率和查準(zhǔn)率的組合表達(dá)式

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

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

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

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

1）進(jìn)行分類器設(shè)計(jì)時，決策樹分類方法所需時間相對較少

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

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

決策樹的難點(diǎn)：

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

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

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

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

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

Whichoneisbetter?B1orB2?Why?

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

Lazylearning:Simplystorestrainingdata(oronlyminorprocessing)andwaitsuntilitisgivenatesttuple

Eagerlearning:Givenasetoftrainingtuples,constructsaclassificationmodelbeforereceivingnewdatatoclassify

Lazy:lesstimeintrainingbutmoretimeinpredicting

Accuracy

Lazy:effectivelyusesaricherhypothesisspacesinceitusesmanylocallinearfunctionstoformanimplicitglobalapproximationtothetargetfunction

Eager:mustcommittoasinglehypothesisthatcoverstheentireinstancespace

k-NN是惰性、分類、基于instance的學(xué)習(xí)方法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ì)功能預(yù)測)usingexpressionprofiles

kNNClassification:DisadvantagesClassifyingunknownrecordsarerelativelyexpensive

Requiresdistancecomputationofk-nearestneighbors

Computationallyintensive,especiallywhenthesizeofthetrainingsetgrowsAccuracycanbeseverelydegradedbythepresenceofnoisyorirrelevantfeaturesNNclassificationexpectsclassconditionalprobabilitytobelocallyconstant

biasofhighdimensions

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

是一種用來進(jìn)行推理的模型

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

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

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

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

第二階段——分類器訓(xùn)練階段。

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

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

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

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

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

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

貝葉斯公式：獨(dú)立互斥且完備的后驗(yàn)事件概率可以由先驗(yàn)事件的概率和相應(yīng)條件概率決定

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

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

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

貝葉斯網(wǎng)絡(luò)學(xué)習(xí)：由先驗(yàn)的Bayes網(wǎng)絡(luò)得到后驗(yàn)的Bayes網(wǎng)絡(luò)的過程

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

Artificialneuralnetwork(ANN)isamachinelearningapproachthatmodelshumanbrainandconsistsofanumberofartificialneurons.

Anartificialneuralnetwork(ANN)consistsofapoolofsimpleprocessingunitswhichcommunicatebysendingsignalstoeachotheroveralargenumberofweightedconnections.

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

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

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

復(fù)興時期：Hopfield模型

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

神經(jīng)網(wǎng)絡(luò)作為分類器的優(yōu)缺點(diǎn)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)絡(luò)特點(diǎn)

1）初步的自適應(yīng)與自組織能力

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

2）泛化能力

泛化能力指對沒有訓(xùn)練過的樣本，有很好的預(yù)測能力和控制能力

3）非線性映射能力

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

4）高度并行性

從功能的模擬角度上看，神經(jīng)網(wǎng)絡(luò)也應(yīng)具備很強(qiá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）是遺傳的基本單位，是個體的基本組成單元。

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

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

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

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

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

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

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

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

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

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

設(shè)計(jì)適應(yīng)度函數(shù)一般主要滿足的條件：

連續(xù)、非負(fù)

適應(yīng)度函數(shù)設(shè)計(jì)應(yīng)盡可能簡單

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

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

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

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

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

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）負(fù)域—是指知識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是獨(dú)立的

（2）獨(dú)立等價關(guān)系的子集也是獨(dú)立的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