数据仓库与数据挖掘

数据仓库与数据挖掘数据挖掘（DataMining）概念从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在价值的信息和知识的过程。简单的说，数据挖掘就是从大量数据中提取或“挖掘”知识，因此又被称为数据库中的知识发现(KnowledgeDiscoveryinDatabase,KDD)数据挖掘的类型按方法分：直接数据挖掘：对某个变量建立一个模型；包括分类、估值和预测

间接数据挖掘：在所有的变量中建立起某种关系；

如相关性分组或关联规则，聚类，描述和可视化，及复杂数据挖掘按任务分：PredictionMethods

Usesomevariablestopredictunknownorfuturevaluesofothervariables.

DescriptionMethods

Findhuman-interpretablepatterns/rulesthatdescribegivendata.

数据挖掘&知识发现kDD的关系：知识发现（KnowledgeDiscoveryinDatabases）是用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后隐藏的知识，称为数据库中的知识发现。所谓基于数据库的知识发现（KDD）是指从大量数据中提取有效的、新颖的、潜在有用的、最终可被理解的模式的非平凡过程。(1)KDD是“数据挖掘”的一种更广义的说法；

(2)数据挖掘是整个KDD过程的核心。频繁模式–数据库中出现频繁的模式(项集,序列,等等)可信度（Confidence）—设W中支持物品集A的事务中，有c％的事务同时也支持物品集B，c％称为关联规则A→B的可信度。支持度（Support）—设W中有s％的事务同时支持物品集A和B，s％称为关联规则A→B的支持度。最小支持度–表示规则中的所有项在事务中出现的频度

最小可信度–表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度频繁集–支持度大于或等于supmin的项集称为频繁项集，满足最小支持度的项集FP-树构建扫描事务数据库D一次,得到频繁项的集合F及它们的支持度.将F按支持度降序排列成L,L是频繁项的列表.创建FP-树的根,标注其为NULL.对D中的每个事务进行以下操作:根据L中的次序对事务中的频繁项进行选择和排序.设事务中的已排序的频繁项列表为[p|P],其中p表示第一个元素,P表示剩余的列表.调用insert_Tree([p|P],T).

分类的定义

分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类.

分类过程获取数据：数据的表示（图像—文字、指纹，波形--脑电图、心电图、机械振动波等，物理数据既包含数值型数据，也包含描述型数据，逻辑数据--只有两种取值的描述型的数据）输入数据、对数据进行量化预处理：去除噪声数据、对缺失值进行处理

数据集成或者变换（维数灾难，降维）分类器设计：划分数据集（给定带类标号的数据集，并且把数据集划分为两个部分：训练集和测试集）

分类器构造（利用训练集构造分类器，也就是建立分类模型）

分类器测试（利用测试集对分类器的分类性能进行评估）分类决策：对未知类标号的数据样本（测试样本）进行分类分类的评价准则

给定测试集Xtest={(xi,yi)|i=1,2,…,N}

N表示测试集中的样本个数

xi表示测试集中的数据样本

yi表示数据样本xi的类标号

对于测试集的第j个类别，假设

被正确分类的样本数量为TPj

被错误分类的样本数量为FNj

其他类别被错误分类为该类的样本数据量为FPj精确度：代表测试集中被正确分类的数据样本所占的比例

查全率：表示在本类样本中被正确分类的样本所占的比例

查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例

F-measure：是查全率和查准率的组合表达式

几何均值：是各个类别的查全率的平方根

决策树的基本概念适用于离散值属性、连续值属性

采用自顶向下的递归方式产生一个类似于流程图的树结构

在根节点和各内部节点上选择合适的描述属性，并且根据该属性的不同取值向下建立分枝决策树的优点：

1）进行分类器设计时，决策树分类方法所需时间相对较少

2）决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式

3）可以将决策树中到达每个叶节点的路径转换为IF—THEN形式的分类规则，这种形式更有利于理解

决策树的难点：

1）如何选择一个好的分支取值

好的分支取值可以加快决策树的生长，更重要的是产生结构好的决策树

相反，差的分支取值不但影响决策树的生长，更重要的是产生的决策树分支过细、结构差，难以发现有用的规则信息。2）取信息增益（InformationGain）较大的对应划分

ID3是采用“信息增益”来选择分裂属性的。虽然这是一种有效的方法，但其具有明显的倾向性，即它倾向于选择取值较多的属性;

C4.5算法使用信息增益比来选择分枝属性，克服了ID3算法使用信息增益时偏向于取值较多的属性的不足

Whichoneisbetter?B1orB2?Why?

Howdoyoudefinebetter?Findhyperplanemaximizesthemargin=>B1isbetterthanB24种核函数Simplelinearkernel:K(Xi,Xj)=Xi’*Xj2种多类Multiclass惰性学习与积极学习的概念与区别Lazyvs.eagerlearning(惰性学习vs.积极学习)

Lazylearning:Simplystorestrainingdata(oronlyminorprocessing)andwaitsuntilitisgivenatesttuple

Eagerlearning:Givenasetoftrainingtuples,constructsaclassificationmodelbeforereceivingnewdatatoclassify

Lazy:lesstimeintrainingbutmoretimeinpredicting

Accuracy

Lazy:effectivelyusesaricherhypothesisspacesinceitusesmanylocallinearfunctionstoformanimplicitglobalapproximationtothetargetfunction

Eager:mustcommittoasinglehypothesisthatcoverstheentireinstancespace

k-NN是惰性、分类、基于instance的学习方法Top10DataMiningAlgorithm1.C4.56.PageRank(网页排名)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(蛋白质功能预测)usingexpressionprofiles

kNNClassification:DisadvantagesClassifyingunknownrecordsarerelativelyexpensive

Requiresdistancecomputationofk-nearestneighbors

Computationallyintensive,especiallywhenthesizeofthetrainingsetgrowsAccuracycanbeseverelydegradedbythepresenceofnoisyorirrelevantfeaturesNNclassificationexpectsclassconditionalprobabilitytobelocallyconstant

biasofhighdimensions

贝叶斯概念，组成贝叶斯网络：描述随机变量（事件）之间依赖关系的一种图形模式

是一种用来进行推理的模型

网络结构和条件概率表两部分组成（网络结构是一个有向无环图结点和有向弧）Bayesianbeliefnetwork(alsoknownasBayesiannetwork,probabilisticnetwork):allowsclassconditionalindependenciesbetweensubsetsofvariables

Twocomponents:(1)Adirectedacyclicgraph有向无环图(calledastructure)(2)asetofconditionalprobabilitytables(CPTs)

贝叶斯决策概念与过程利用贝叶斯定理求得后验概率，据以进行决策的方法，称为贝叶斯决策方法。已具备先验概率的情况下，贝叶斯决策过程的步骤为：（1）进行预后验分析，取得条件概率，包括历史概率和逻辑概率，对历史概率要加以检验，辨明其是否适合计算后验概率。（2）用概率的乘法定理计算联合概率，用概率的加法定理计算边际概率,用贝叶斯定理计算后验概率（3）用后验概率进行决策分析。

第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备。

第二阶段——分类器训练阶段。

第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。

贝叶斯3概率3公式先验概率：根据历史的资料或主观判断所确定的各种时间发生的概率

后验概率：通过贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率修正后得到的更符合实际的概率

条件概率：某事件发生后该事件的发生概率

条件概率公式：A1和B表示在一个样本空间中的两个事件，给定B条件下A1发生的条件概率公式为：

全概率公式：B1，B 2,…，Bn为样本空间中的一组事件，对于每一次试验，B1，B2,…，Bn中只有一个事件发生：

贝叶斯公式：独立互斥且完备的后验事件概率可以由先验事件的概率和相应条件概率决定

贝叶斯网络的3个主要议题

贝叶斯网络预测：从起因推测一个结果的推理

贝叶斯网络诊断：从结果推测一个起因的推理

贝叶斯网络学习：由先验的Bayes网络得到后验的Bayes网络的过程

神经网络概念与结构

Artificialneuralnetwork(ANN)isamachinelearningapproachthatmodelshumanbrainandconsistsofanumberofartificialneurons.

Anartificialneuralnetwork(ANN)consistsofapoolofsimpleprocessingunitswhichcommunicatebysendingsignalstoeachotheroveralargenumberofweightedconnections.

人工神经网络的发展与类型

人工神经网络的发展：启蒙阶段：感知器模型

低潮时期：线性不可分问题

复兴时期：Hopfield模型

神经网络的类型：前向型反馈型随机型自组织竞争型

神经网络作为分类器的优缺点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

人工神经网络特点

1）初步的自适应与自组织能力

在学习或训练过程中改变突触权重值，以适应周围环境的要求

2）泛化能力

泛化能力指对没有训练过的样本，有很好的预测能力和控制能力

3）非线性映射能力

系统很复杂，或者系统未知，系统信息量很少时，建立精确的数学模型很困难时，神经网络的非线性映射能力则表现出优势

4）高度并行性

从功能的模拟角度上看，神经网络也应具备很强的并行性

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)

遗传算法相关概念基因—基因（Gene）是遗传的基本单位，是个体的基本组成单元。

个体—在生物学中，个体（Individual）由多个基因组成。遗传算法中，个体代表待优化问题的一个解。

编码—将问题的解转换成基因序列的过程称为编码(Encoding)，编码是由解空间到遗传算法空间的映射。解码—将基因型转换成问题的解的过程称为解码（Decoding)。

种群—生物的遗传进化不能仅通过自身进行，而需要在一个群体中进行，这一群体称为种群(Population)。种群中的单个组成元素是个体。种群规模是遗传算法的参数之一，种群规模的设置可能会影响到遗传算法的优化效果。

适应度—在研究自然界中生物的遗传与进化现象时，生物学中使用适应度(Fitness)这个术语来衡量某个物种对于生存环境的适应程度。

代—在生物的繁衍过程中，个体从出生到死亡即为一代(Generation)，在遗传算法中，代的意思为遗传算法的迭代次数。可作为遗传算法的一个结束标志。

遗传算子—指作用在个体上的各种遗传操作。类型：选择算子、交叉算子和变异算子。

选择(Selection)算子：在适应度的基础上，按照某种规则或方法从当前代的种群中选择出一些适应度高的个体遗传到下一代种群中。

交叉(Crossover)算子：以某一概率（交叉概率）选择种群中的个体，把两个父个体的部分基因加以替换、重组而生成新的个体。

变异(Mutation)算子：以某一概率（变异概率）选择种群中的个体，改变其个体中某些基因的值或对其个体进行某种方式的重组。

遗传算法过程适应度函数：体现了个体的生存环境，是通过对目标函数的转换而形成的。

设计适应度函数一般主要满足的条件：

连续、非负

适应度函数设计应尽可能简单

适应度函数对某一类具体问题，应尽可能通用

One-pointcrossoverTwo-pointcrossover粗糙集等价关系—设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则称R为等价关系。

2)等价类—设R为集合A上的等价关系，对任何a∈A，集合[a]R={x|x∈A,aRx}称为元素a形成的R等价类。由等价类的定义可知[a]R是非空的，因为a∈[a]R

3）知识—一种将现实或抽象的对象进行分类的能力

4）知识库—当给定了一个数据上的等价关系集合，在等价关系集合下对该数据集合进行的划分，则就会被称为知识库

5）族集—论域U上的一族划分称为关于U的一个知识库

一个知识库就是一个关系系统K=(U,R)，其中U是非空有限集，R为U上等价关系的一个族集

6）不可辨识关系—若P∈R，且P≠φ，则P中所有等价关系的交集也是一个等价关系，称为P上的不可辨识关系，记为ind(P)

7）U/ind(P)—表示与等价关系P相关的知识，称为K中关于U的P基本知识(基本集)，简称U/P。（即等价关系ind(P)的所有等价类）

8）下近似集—一个知识库K=(U,R)，令XU且R为U上一等价关系，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）由等价关系R描述的对象集X的近似精度为：如果dR(X)=0，则X是R全部不可定义的；

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

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

分别为X上近似集合、下近似集合中元素的个数。

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

14）对于知识库K=(U,R)，如果存在等价关系r∈R,使得ind(r)=ind(R)，则称r是可省略的，否则，称r是不可省略的。

（1）若任意r∈R是不可省略的，则称R是独立的

（2）独立等价关系的子集也是独立的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与分类的区别如何度量聚类好坏Agoodclusteringmethodwillproducehighqualityclusters

highintra-classsimilarity:compactnesswithinclusters

lowinter-classsimilarity:separationbetweenclustersThequalityofaclusteringmethoddependson

thesimilaritymeasureused

itsimplementation,and

Itsabilitytodiscoversomeoral