数据仓库与数据挖掘

数据仓库与数据挖掘1.数据挖掘（DataMining）概念从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在价值的信息和知识的过程。简单的说，数据挖掘就是从大量数据中提取或“挖掘”知识，因此又被称为数据库中的知识发现(KnowledgeDiscoveryinDatabase,KDD)2.数据挖掘的类型按方法分：直接数据挖掘：对某个变量建立一个模型；包括分类、估值和预测间接数据挖掘：在所有的变量中建立起某种关系；如相关性分组或关联规则，聚类，描述和可视化，及复杂数据挖掘按任务分：PredictionMethodsUsesomevariablestopredictunknownorfuturevaluesofothervariables.DescriptionMethodsFindhuman-interpretablepatterns/rulesthatdescribegivendata.3.数据挖掘&知识发现kDD的关系：知识发现（KnowledgeDiscoveryinDatabases）是用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后隐藏的知识，称为数据库中的知识发现。所谓基于数据库的知识发现（KDD）是指从大量数据中提取有效的、新颖的、潜在有用的、最终可被理解的模式的非平凡过程。(1)KDD是“数据挖掘”的一种更广义的说法；(2)数据挖掘是整个KDD过程的核心。4.频繁模式–数据库中出现频繁的模式(项集,序列,等等)可信度（Confidence）—设W中支持物品集A的事务中，有c％的事务同时也支持物品集B，c％称为关联规则A→B的可信度。支持度（Support）—设W中有s％的事务同时支持物品集A和B，s％称为关联规则A→B的支持度。最小支持度–表示规则中的所有项在事务中出现的频度最小可信度–表示规则中左边的项(集)的出现暗示着右边的项(集)出现的频度频繁集–支持度大于或等于supmin的项集称为频繁项集，满足最小支持度的项集5.FP-树构建1）扫描事务数据库D一次,得到频繁项的集合F及它们的支持度.将F按支持度降序排列成L,L是频繁项的列表.2）创建FP-树的根,标注其为NULL.对D中的每个事务进行以下操作:3）根据L中的次序对事务中的频繁项进行选择和排序.设事务中的已排序的频繁项列表为[p|P],其中p表示第一个元素,P表示剩余的列表.调用insert_Tree([p|P],T).6.分类的定义分类是指把数据样本映射到一个事先定义的类中的学习过程，即给定一组输入的属性向量及其对应的类，用基于归纳的学习算法得出分类.7.分类过程获取数据：数据的表示（图像—文字、指纹，波形--脑电图、心电图、机械振动波等，物理数据---既包含数值型数据，也包含描述型数据，逻辑数据--只有两种取值的描述型的数据）输入数据、对数据进行量化预处理：去除噪声数据、对缺失值进行处理数据集成或者变换（维数灾难，降维）分类器设计：划分数据集（给定带类标号的数据集，并且把数据集划分为两个部分：训练集和测试集）分类器构造（利用训练集构造分类器，也就是建立分类模型）分类器测试（利用测试集对分类器的分类性能进行评估）分类决策：对未知类标号的数据样本（测试样本）进行分类8.分类的评价准则给定测试集Xtest={(xi,yi)|i=1,2,…,N}N表示测试集中的样本个数xi表示测试集中的数据样本yi表示数据样本xi的类标号对于测试集的第j个类别，假设被正确分类的样本数量为TPj被错误分类的样本数量为FNj其他类别被错误分类为该类的样本数据量为FPj精确度：代表测试集中被正确分类的数据样本所占的比例查全率：表示在本类样本中被正确分类的样本所占的比例查准率：表示被分类为该类的样本中，真正属于该类的样本所占的比例F-measure：是查全率和查准率的组合表达式几何均值：是各个类别的查全率的平方根9.决策树的基本概念适用于离散值属性、连续值属性采用自顶向下的递归方式产生一个类似于流程图的树结构在根节点和各内部节点上选择合适的描述属性，并且根据该属性的不同取值向下建立分枝10.决策树的优点：1）进行分类器设计时，决策树分类方法所需时间相对较少2）决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式3）可以将决策树中到达每个叶节点的路径转换为IF—THEN形式的分类规则，这种形式更有利于理解决策树的难点：1）如何选择一个好的分支取值好的分支取值可以加快决策树的生长，更重要的是产生结构好的决策树相反，差的分支取值不但影响决策树的生长，更重要的是产生的决策树分支过细、结构差，难以发现有用的规则信息。2）取信息增益（InformationGain）较大的对应划分11.ID3是采用“信息增益”来选择分裂属性的。虽然这是一种有效的方法，但其具有明显的倾向性，即它倾向于选择取值较多的属性;C4.5算法使用信息增益比来选择分枝属性，克服了ID3算法使用信息增益时偏向于取值较多的属性的不足12.Whichoneisbetter?B1orB2?Why?Howdoyoudefinebetter?Findhyperplanemaximizesthemargin=B1isbetterthanB213.14.4种核函数Simplelinearkernel:K(Xi,Xj)=Xi’*Xj15.2种多类Multiclass16.惰性学习与积极学习的概念与区别Lazyvs.eagerlearning(惰性学习vs.积极学习)Lazylearning:Simplystorestrainingdata(oronlyminorprocessing)andwaitsuntilitisgivenatesttupleEagerlearning:Givenasetoftrainingtuples,constructsaclassificationmodelbeforereceivingnewdatatoclassifyLazy:lesstimeintrainingbutmoretimeinpredictingAccuracyLazy:effectivelyusesaricherhypothesisspacesinceitusesmanylocallinearfunctionstoformanimplicitglobalapproximationtothetargetfunctionEager:mustcommittoasinglehypothesisthatcoverstheentireinstancespace17.k-NN是惰性、分类、基于instance的学习方法18.Top10DataMiningAlgorithm1.C4.56.PageRank(网页排名)2.k-means7.AdaBoost3.SVM(SupportVectorMachines)8.kNN4.Apriori9.NaiveBayes5.EM(ExpectationMaximization)10.CART19.kNNClassification:Advantages1）Simpletechniquethatiseasytobeimplemented2）Buildingmodelisinexpensive3）Extremelyflexibleclassificationschemedoesnotinvolvepreprocessing4）WellsuitedforMulti-modalclasses(classesofmultipleforms)Recordswithmultipleclasslabels5）CansometimesbethebestmethodMichihiroKuramochiandGeorgeKarypis,GeneClassificationusingExpressionProfiles:AFeasibilityStudy,InternationalJournalonArtificialIntelligenceTools.Vol.14,No.4,pp.641-660,2005KnearestneighboroutperformedSVMforproteinfunctionprediction(蛋白质功能预测)usingexpressionprofileskNNClassification:Disadvantages1）ClassifyingunknownrecordsarerelativelyexpensiveRequiresdistancecomputationofk-nearestneighborsComputationallyintensive,especiallywhenthesizeofthetrainingsetgrows2）Accuracycanbeseverelydegradedbythepresenceofnoisyorirrelevantfeatures3）NNclassificationexpectsclassconditionalprobabilitytobelocallyconstantbiasofhighdimensions20.贝叶斯概念，组成贝叶斯网络：描述随机变量（事件）之间依赖关系的一种图形模式是一种用来进行推理的模型网络结构和条件概率表两部分组成（网络结构是一个有向无环图结点和有向弧）Bayesianbeliefnetwork(alsoknownasBayesiannetwork,probabilisticnetwork):allowsclassconditionalindependenciesbetweensubsetsofvariablesTwocomponents:(1)Adirectedacyclicgraph有向无环图(calledastructure)(2)asetofconditionalprobabilitytables(CPTs)21.贝叶斯决策概念与过程利用贝叶斯定理求得后验概率，据以进行决策的方法，称为贝叶斯决策方法。已具备先验概率的情况下，贝叶斯决策过程的步骤为：（1）进行预后验分析，取得条件概率，包括历史概率和逻辑概率，对历史概率要加以检验，辨明其是否适合计算后验概率。（2）用概率的乘法定理计算联合概率，用概率的加法定理计算边际概率,用贝叶斯定理计算后验概率（3）用后验概率进行决策分析。第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备。第二阶段——分类器训练阶段。第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。22.贝叶斯3概率3公式先验概率：根据历史的资料或主观判断所确定的各种时间发生的概率后验概率：通过贝叶斯公式，结合调查等方式获取了新的附加信息，对先验概率修正后得到的更符合实际的概率条件概率：某事件发生后该事件的发生概率条件概率公式：A1和B表示在一个样本空间中的两个事件，给定B条件下A1发生的条件概率公式为：全概率公式：B1，B2,…，Bn为样本空间中的一组事件，对于每一次试验，B1，B2,…，Bn中只有一个事件发生：贝叶斯公式：独立互斥且完备的后验事件概率可以由先验事件的概率和相应条件概率决定23.贝叶斯网络的3个主要议题贝叶斯网络预测：从起因推测一个结果的推理贝叶斯网络诊断：从结果推测一个起因的推理贝叶斯网络学习：由先验的Bayes网络得到后验的Bayes网络的过程24.神经网络概念与结构Artificialneuralnetwork(ANN)isamachinelearningapproachthatmodelshumanbrainandconsistsofanumberofartificialneurons.Anartificialneuralnetwork(ANN)consistsofapoolofsimpleprocessingun