数据挖掘分类

数据挖掘分类Classification

主要用于对离散得数据进行预测分为两步:根据训练集,构造分类模型(训练集中每个元组得分类标号事先已经知道)估计分类模型得准确性,如果其准确性可以接受得话,则利用她来对未来数据进行分类Prediction:构造、使用模型来对某个样本得值进行估计,例如预测某个不知道得值或者缺失值主要用于对连续或有序得数据进行预测Typicalapplications信誉评估医学诊断性能预测Classificationvs、Prediction2Classification—ATwo-StepProcess

模型构造阶段:describingasetofpredeterminedclasses假定每个元组/样本都属于某个预定义得类,这些类由分类标号属性所定义用来构造模型得元组/样本集被称为训练集(trainingset)模型一般表示为:分类规则,决策树或者数学公式模型使用阶段:forclassifyingfutureorunknownobjects估计模型得准确性用一些已知分类标号得测试集和由模型进行分类得结果进行比较两个结果相同所占得比率称为准确率测试集和训练集必须不相关如果准确性可以接受得话,使用模型来对那些不知道分类标号得数据进行分类。3ClassificationProcess(1):ModelConstructionTrainingDataClassificationAlgorithmsIFrank=‘professor’ORyears>6THENtenured=‘yes’Classifier(Model)4ClassificationProcess(2):UsetheModelinPredictionClassifierTestingDataUnseenData(Jeff,Professor,4)Tenured?5分类和预测相关问题(1):数据预处理数据清洗对数据进行预处理,去掉噪声,对缺失数据进行处理(用某个最常用得值代替或者根据统计用某个最可能得值代替)相关分析(特征选择)去掉某些不相关得或者冗余得属性数据转换对数据进行概括(如将连续得值离散成若干个区域,将街道等上升到城市)对数据进行规范化,将某个属性得值缩小到某个指定得范围之内6分类和预测相关问题(2):对分类方法进行评价准确性:分类准确性和预测准确性速度和可伸缩性构造模型得时间(训练时间)使用模型得时间(分类/预测时间)鲁棒性能够处理噪声和缺失数据可伸缩性对磁盘级得数据库有效

易交互性模型容易理解,具有较好得洞察力7VisualizationofaDecisionTreeinSGI/MineSet3、017十月20248大家有疑问的，可以询问和交流可以互相讨论下，但要小声点Supervisedvs、UnsupervisedLearningSupervisedlearning(classification)Supervision:Thetrainingdata(observations,measurements,etc、)areacpaniedbylabelsindicatingtheclassoftheobservationsNewdataisclassifiedbasedonthetrainingsetUnsupervisedlearning(clustering)TheclasslabelsoftrainingdataisunknownGivenasetofmeasurements,observations,etc、withtheaimofestablishingtheexistenceofclassesorclustersinthedata10简单例子分类两岁宝宝,给她看几个水果,并告诉她:红得圆得就是苹果,橘黄得圆得就是橘子(建模型)拿一个水果问宝宝:这个水果,红得圆得,就是什么？(用模型)聚类两岁宝宝,给她一堆水果,告诉她:根据颜色分成两堆。宝宝会将苹果分成一堆,橘子分成一堆。假如告诉她:根据大小分成3堆,则宝宝会根据大小分成3堆,苹果和橘子可能会放在一起。11主要内容分类和预测贝叶斯分类、神经网络分类预测12BayesianClassification就是一种基于统计得分类方法,用来预测诸如某个样本属于某个分类得概率有多大基于Bayes理论研究发现,NaïveBayesClassifier在性能上和DecisionTree、NeuralNetworkclassifiers相当。在应用于大数据集时,具有较高得准确率和速度NaïveBayesClassifier假设属性值之间就是独立得,因此可以简化很多计算,故称之为Naïve。当属性值之间有依赖关系时,采用BayesianBeliefNetworks进行分类。13BayesianTheorem:Basics假设X就是未知分类标号得样本数据H代表某种假设,例如X属于分类C

P(H|X):给定样本数据X,假设H成立得概率例如,假设样本数据由各种水果组成,每种水果都可以用形状和颜色来描述。如果用X代表红色并且就是圆得,H代表X属于苹果这个假设,则P(H|X)表示,已知X就是红色并且就是圆得,则X就是苹果得概率。14BayesianTheorem:BasicsP(H):拿出任一个水果,不管她什么颜色,也不管她什么形状,她属于苹果得概率P(X):拿出任一个水果,不管她就是什么水果,她就是红色并且就是圆得概率P(X|H):一个水果,已知她就是一个苹果,则她就是红色并且就是圆得概率。15BayesianTheorem:Basics现在得问题就是,知道数据集里每个水果得颜色和形状,看她属于什么水果,求出属于每种水果得概率,选其中概率最大得。也就就是要算:P(H|X)但事实上,其她三个概率,P(H)、P(X)、P(X|H)都可以由已知数据得出,而P(H|X)无法从已知数据得出Bayes理论可以帮助我们:16NaïveBayesClassifier每个数据样本用一个n维特征向量表示,描述由属性对样本得n个度量。假定有m个类。给定一个未知得数据样本X(即,没有类标号),分类法将预测X属于具有最高后验概率(条件X下)得类。即,朴素贝叶斯分类将未知得样本分配给类Ci,当且仅当:这样,我们最大化。其最大得类Ci称为最大后验假定。根据贝叶斯定理:

17NaïveBayesClassifier由于P(X)对于所有类为常数,只需要最大即可。如果类得先验概率未知,则通常假定这些类就是等概率得;即,。并据此只对最大化。否则,我们最大化。类得先验概率可以用计算;其中,si就是类C中得训练样本数,而s就是训练样本总数。18NaïveBayesClassifier给定具有许多属性得数据集,计算得开销可能非常大。为降低计算得开销,可以朴素地假设属性间不存在依赖关系。这样,

概率,,…,可以由训练样本估计,其中,(a)

如果Ak就是分类属性,则;其中sik就是在属性Ak上具有值xk得类Ci得训练样本数,而si就是Ci中得训练样本数(b)

如果就是连续值属性,则通常假定该属性服从高斯分布。因而,

其中,给定类Ci得训练样本属性Ak得值,就是属性Ak得高斯密度函数,而分别为平均值和标准差。19NaïveBayesClassifier为对未知样本X分类,对每个类Ci,计算。样本X被指派到类Ci,当且仅当:

换言之,X被指派到其最大得类Ci。20TrainingdatasetClass:C1:buys_puter=‘yes’C2:buys_puter=‘no’DatasampleX=(age<=30,Ine=medium,Student=yesCredit_rating=Fair)21NaïveBayesianClassifier:AnExampleputeP(X|Ci)foreachclass

P(buys_puter=“yes”)=9/14=0、643 P(buys_puter=“no”)=5/14=0、357

P(age=“<30”|buys_puter=“yes”)=2/9=0、222P(age=“<30”|buys_puter=“no”)=3/5=0、6P(ine=“medium”|buys_puter=“yes”)=4/9=0、444P(ine=“medium”|buys_puter=“no”)=2/5=0、4P(student=“yes”|buys_puter=“yes)=6/9=0、667P(student=“yes”|buys_puter=“no”)=1/5=0、2P(credit_rating=“fair”|buys_puter=“yes”)=6/9=0、667P(credit_rating=“fair”|buys_puter=“no”)=2/5=0、4X=(age<=30,ine=medium,student=yes,credit_rating=fair)

P(X|Ci):P(X|buys_puter=“yes”)=0、222x0、444x0、667x0、667=0、044P(X|buys_puter=“no”)=0、6x0、4x0、2x0、4=0、019P(X|Ci)*P(Ci):P(X|buys_puter=“yes”)*P(buys_puter=“yes”)=0、044x0、643=0、028

P(X|buys_puter=“no”)*P(buys_puter=“no”)=0、019x0、357=0、007Therefore,Xbelongstoclass“buys_puter=yes” 22NaïveBayesianClassifier:ments优点易于实现多数情况下结果较满意缺点假设:属性间独立,丢失准确性实际上,属性间存在依赖处理依赖BayesianBeliefNetworks23主要内容分类和预测贝叶斯分类、神经网络分类预测24神经网络神经网络就是以模拟人脑神经元得数学模型为基础而建立得,她由一系列神经元组成,单元之间彼此连接。25神经网络神经网络有三个要素:拓扑结构、连接方式、学习规则可以从这三方面对神经网络进行分类26神经网络得拓扑神经网络得拓扑结构:神经网络得单元通常按照层次排列,根据网络得层次数,可以将神经网络分为单层神经网络、两层神经网络、三层神经网络等结构简单得神经网络,在学习时收敛得速度快,但准确度低。神经网络得层数和每层得单元数由问题得复杂程度而定。问题越复杂,神经网络得层数就越多。例如,两层神经网络常用来解决线性问题,而多层网络就可以解决多元非线性问题27神经网络得连接神经网络得连接:包括层次之间得连接和每一层内部得连接,连接得强度用权来表示。根据层次之间得连接方式,分为:前馈式网络:连接就是单向得,上层单元得输出就是下层单元得输入,如反向传播网络反馈式网络:除了单项得连接外,还把最后一层单元得输出作为第一层单元得输入,如Hopfield网络根据连接得范围,分为:全连接神经网络:每个单元和相邻层上得所有单元相连局部连接网络:每个单元只和相邻层上得部分单元相连28神经网络得学习神经网络得学习根据学习方法分:感知器:有监督得学习方法,训练样本得类别就是已知得,并在学习得过程中指导模型得训练认知器:无监督得学习方法,训练样本类别未知,各单元通过竞争学习。根据学习时间分:离线网络:学习过程和使用过程就是独立得在线网络:学习过程和使用过程就是同时进行得根据学习规则分:相关学习网络:根据连接间得激活水平改变权系数纠错学习网络:根据输出单元得外部反馈改变权系数自组织学习网络:对输入进行自适应地学习29基于神经网络得分类方法神经网络经常用于分类神经网络得分类知识体现在网络连接上,被隐式地存储在连接得权值中。神经网络得学习就就是通过迭代算法,对权值逐步修改得优化过程,学习得目标就就是通过改变权值使训练集得样本都能被正确分类。30基于神经网络得分类方法神经网络特别适用于下列情况得分类问题:数据量比较小,缺少足够得样本建立模型数据得结构难以用传统得统计方法来描述分类模型难以表示为传统得统计模型31基于神经网络得分类方法缺点:需要很长得训练时间,因而对于有足够长训练时间得应用更合适。需要大量得参数,这些通常主要靠经验确定,如网络拓扑。可解释性差。该特点使得神经网络在数据挖掘得初期并不看好。

32基于神经网络得分类方法优点:分类得准确度高并行分布处理能力强分布存储及学习能力高对噪音数据有很强得鲁棒性和容错能力最流行得基于神经网络得分类算法就是80年代提出得后向传播算法。

33后向传播算法后向传播算法在多路前馈神经网络上学习。

34定义网络拓扑

在开始训练之前,用户必须说明输入层得单元数、隐藏层数(如果多于一层)、每一隐藏层得单元数和输出层得单元数,以确定网络拓扑。

35定义网络拓扑

对训练样本中每个属性得值进行规格化将有助于加快学习过程。通常,对输入值规格化,使得她们落入0、0和1、0之间。离散值属性可以重新编码,使得每个域值一个输入单元。例如,如果属性A得定义域为(a0,a1,a2),则可以分配三个输入单元表示A。即,我们可以用I0,I1,I2作为输入单元。每个单元初始化为0。如果A=a0,则I0置为1;如果A=a1,I1置1;如此下去。一个输出单元可以用来表示两个类(值1代表一个类,而值0代表另一个)。如果多于两个类,则每个类使用一个输出单元。36定义网络拓扑隐藏层单元数设多少个“最好”,没有明确得规则。网络设计就是一个实验过程,并可能影响准确性。权得初值也可能影响准确性。如果某个经过训练得网络得准确率太低,则通常需要采用不同得网络拓扑或使用不同得初始权值,重复进行训练。

37后向传播算法后向传播算法学习过程:迭代地处理一组训练样本,将每个样本得网络预测与实际得类标号比较。每次迭代后,修改权值,使得网络预测和实际类之间得均方差最小。这种修改“后向”进行。即,由输出层,经由每个隐藏层,到第一个隐藏层(因此称作后向传播)。尽管不能保证,一般地,权将最终收敛,学习过程停止。

算法终止条件:训练集中被正确分类得样本达到一定得比例,或者权系数趋近稳定。38后向传播算法后向传播算法分为如下几步:初始化权向前传播输入向后传播误差39后向传播算法初始化权网络得权通常被初始化为很小得随机数(例如,范围从-1、0到1、0,或从-0、5到0、5)。每个单元都设有一个偏置(bias),偏置也被初始化为小随机数。

对于每一个样本X,重复下面两步:向前传播输入向后传播误差40向前传播输入计算各层每个单元得输入和输出。输入层:输出=输入=样本X得属性;即,对于单元j,Oj

=Ij=Xj隐藏层和输出层:输入=前一层得输出得线性组合,即,对于单元j,Ij=∑wijOi+θj

i输出=41向后传播误差计算各层每个单元得误差。向后传播误差,并更新权和偏置计算各层每个单元得误差。输出层单元j,误差

Oj就是单元j得实际输出,而Tj就是j得真正输出。隐藏层单元j,误差

wjk就是由j到下一层中单元k得连接得权Errk就是单元k得误差42向后传播误差更新权和偏差,以反映传播得误差。 权由下式更新: 其中,

wij就是权wij得改变。l就是学习率,通常取0和1之间得值。 偏置由下式更新: 其中,

j就是偏置

j得改变。

43后向传播算法OutputnodesInputnodesHiddennodesOutputvectorInputvector:xiwijExample设学习率为0、9。训练样本X={1,0,1}类标号为1x1x2x3w14w15w24w25W34w35w46w56

4

5

61010、2-0、30、40、1-0、50、2-0、3-0、2-0、40、20、1单元j净输入Ij输出Oj4560、2+0-0、5-0、4=-0、7-0、3+0+0、2+0、2=0、1(-0、3)(0、332)-(0、2)(0、525)+0、1=-0、1051+(1+e0、7)=0、3321+(1+e-0、1)=0、5251+(1+e-0、105)=0、474单元jErrj654(0、474)(1-0、474)(1-0、474)=0、1311(0、525)(1-0、525)(0、1311)(-0、2)=-0、0065(0、332)(1-0、332)(0、1311)(-0、3)=-0、02087权或偏差新值w46w56w14w15w24w25w34w35

6

5

4-0、3+(0、9)(0、1311)(0、332)=-0、261-0、2+(0、9)(0、1311)(0、525)=-0、1380、2+(0、9)(-0、0087)(1)=0、192-0、3+(0、9)(0、0065)(1)=-0、3060、4+(0、9)(-0、0087)(0)=0、40、1+(0、9)(-0、0065)(0)=0、1-0、5+(0、9)(-0、0087)(1)=-0、5080、2+(0、9)(-0、0065)(1)=0、1940、1+(0、9)(0、1311)=0、2180、2+(0、9)(-0、0065)=0、194-0、4+(0、9)(-0、0087)=-0、40817十月202445主要内容分类和预测贝叶斯分类、神经网络分类预测