第八章 分类和聚类

第九章分类和聚类分类器•NaïveBayes•kNN方法•神经网络方法NeuralNetworks•支持向量机SVM•基于投票的方法(votingmethod)•Rocchio方法•决策树方法decisiontree•DecisionRuleClassifier•TheWidnow-HoffClassifier分类器学习•训练样本实例：x,c(x)•一个文本实例xX•带有正确的类别标记c(x)•学习的过程是在给定训练样本集合D的前提下，寻找一个分类函数h(x),使得:)()(:)(,xcxhDxcx贝叶斯分类•基于概率理论的学习和分类方法•贝叶斯理论在概率学习及分类中充当重要角色•仅使用每类的先验概率不能对待分的文本提供信息•分类是根据给定样本描述的可能的类别基础上产生的后验概率分布贝叶斯理论)()()|()|(EPHPHEPEHP)()()|(EPEHPEHP)()()|(HPEHPHEP)()|()(HPHEPEHP得到：由条件概率的定义：贝叶斯分类•设各个类别的集合为{c1,c2,…cn}•设E为某个文本实例的描述•确定E的类别•需要知道:•先验概率:P(ci)•条件概率:P(E|ci)•P(ci)容易从数据中获得•如果文档集合D中，属于ci的样例数为ni•则有P(ci)=ni/|D|)()|()()|(EPcEPcPEcPiii朴素贝叶斯分类•假设样例的特征是关联的:•指数级的估计所有的P(E|ci)•如果假定样例的特征是独立的，可以写为：•因此，只需要知道每个特征和类别的P(ej|ci)，大大地减少了计算量meeeE21)|()|()|(121mjijimicePceeePcEP文本分类NaïveBayes算法(训练)设V为文档集合D所有词词表对每个类别ciCDi是文档D中类别Ci的文档集合P(ci)=|Di|/|D|设ni为Di中词的总数对每个词wjV令nij为Di中wij的数量P(wi|ci)=(nij+1)/(ni+|V|)文本分类NaïveBayes算法(测试)•给定测试文档X•设n为X中词的个数•返回的类别:•wi是X中第i个位置的词)|()(argmax1niiiiCiccwPcPNaïveBayes分类举例•C={allergy,cold,well}•e1=sneeze;e2=cough;e3=fever•当前实例是：E={sneeze,cough,fever}ProbWellColdAllergyP(ci)0.90.050.05P(sneeze|ci)0.10.90.9P(cough|ci)0.10.80.7P(fever|ci)0.010.70.4过敏打喷嚏NaïveBayes举例(cont.)•参数计算：•P(well|E)=(0.9)(0.1)(0.1)(0.99)/P(E)=0.0089/P(E)•P(cold|E)=(0.05)(0.9)(0.8)(0.3)/P(E)=0.01/P(E)•P(allergy|E)=(0.05)(0.9)(0.7)(0.6)/P(E)=0.019/P(E)•最大概率类:allergy•P(E)=0.089+0.01+0.019=0.0379•P(well|E)=0.23•P(cold|E)=0.26•P(allergy|E)=0.50Play-tennis例子:估算P(xi|C)OutlookTemperatureHumidityWindyClasssunnyhothighfalseNsunnyhothightrueNovercasthothighfalsePrainmildhighfalsePraincoolnormalfalsePraincoolnormaltrueNovercastcoolnormaltruePsunnymildhighfalseNsunnycoolnormalfalsePrainmildnormalfalsePsunnymildnormaltruePovercastmildhightruePovercasthotnormalfalsePrainmildhightrueNP(p)=9/14P(n)=5/14outlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(true|p)=3/9P(true|n)=3/5P(false|p)=6/9P(false|n)=2/5正例反例Play-tennis例子:分类X•例子X=rain,hot,high,false•P(X|p)·P(p)=P(rain|p)·P(hot|p)·P(high|p)·P(false|p)·P(p)=3/9·2/9·3/9·6/9·9/14=0.010582•P(X|n)·P(n)=P(rain|n)·P(hot|n)·P(high|n)·P(false|n)·P(n)=2/5·2/5·4/5·2/5·5/14=0.018286•样本X被分到n类，即“不适合打网球”讨论•朴素的贝叶斯假定在一个位置上出现的词的概率独立于另外一个位置的单词，这个假定有时并不反映真实情况•虽然独立性假设很不精确，但别无选择，否则计算的概率项将极为庞大•幸运的是，在实践中朴素贝叶斯学习器在许多文本分类中性能非常好，即使独立性假设不成立K近邻（KNN）•最近邻分类规则•对于测试样本点x，在集合中距离它最近的的x1。最近邻分类就是把x分为x1所属的类别•最近邻规则的推广-KNN•没有好的相似度矩阵不能用KNNKNN算法•目标：基于训练集X的对y分类•在训练集中，寻找和y最相似的训练样本x•得到k个最相似的集合A，A为X的一个子集•设n1,n2分别为集合中属于c1,c2的个数•如果p(c1|y)p(c2|y),判为c1,否则判为c2()(,)MAXxNsimyMAXsimxymax{|(,)()}AxNsimxysimy11(|)12npcynn22(|)12npcynnkNN方法•一种基于实例的学习方法新文本k=1,A类k=4，B类k=10，B类带权重计算，计算权重和最大的类。KNN•分类错误是由于：•单个的非典型样例•单个训练样本的噪音•更鲁棒的方法是发现k个最相似的样本，返回k个样本最主要的类别相似度矩阵•最近邻方法依赖于相似度矩阵(或距离).•对连续m维空间最简单的方法采用欧氏距.•对m维二值实例空间最简单的方法是海明距.•对于基于文本tf/idf权重向量的余弦相似度是经常被采用的.影响KNN的因素•K的取值•K一般取15•计算距离的方法•欧式距离•兰式距离（余弦相似度），分类质量和分类效率较高•分类目录中类别的层次关系•基于层次模型的KNN分类比基本的KNN效率高，但是效率也会有所下降KNN和NB比较•从表中看，KNN质量较高，NB的效率较高•从各个类别看，KNN比NB稳定，NB对类别敏感NeuralNetwork.....c1c2cn……InputLayerHiddenLayerOutputLayerBackpropagation其他分类方法•RegressionbasedonLeastSquaresFit(1991)•NearestNeighborClassification(1992)*•BayesianProbabilisticModels(1992)*•SymbolicRuleInduction(1994)•DecisionTree(1994)*•NeuralNetworks(1995)•Rocchioapproach(traditionalIR,1996)*•SupportVectorMachines(1997)•BoostingorBagging(1997)*•HierarchicalLanguageModeling(1998)•First-Order-LogicRuleInduction(1999)•MaximumEntropy(1999)•HiddenMarkovModels(1999)•Error-CorrectingOutputCoding(1999)•...分类的评价•偶然事件表（ContingencyTable）•对一个分类器的度量•准确率(precision)=a/(a+b)•召回率(recall)=a/(a+c)•fallout=b/(b+d)属于此类不属于此类判定属于此类AB判定不属于此类CD第12章聚类分析12.1聚类分析的基本原理12.2层次聚类12.3K-均值聚类学习目标聚类分析的基本思想和原理层次聚类和K-均值聚类的基本过程解释聚类的结果层次聚类和K-均值聚类的差异及应用条件聚类分析的注意事项用SPSS进行聚类分析2008年8月怎样把消费者分类？南京雅兴市场研究有限公司在A城市的14个城区抽取3000个15岁以上具有独立购买能力的消费者样本，研究消费者的生活方式。调查中采用一系列关于对社会活动、价值观念等内容的陈述，请消费者根据自己的情况做出评价。评价结果采用7分评价法，1分表示“非常同意”，7分表示“非常不同意”对调查结果先通过因子分析将一系列的测试语句进行综合，根据消费者的回答情况，将这些语句分为几大类，最后得到5个主要因子，它们的含义分别是：对时尚的观点、个人的事业性与进取性、对经济利益的看法、社交能力与影响力、生活的计划性。根据因子分析的结果对样本的回答按照新的类型进行重新评估打分，然后根据这些评价进行聚类分析根据每一类消费者的因子的特征，最终将消费者的生活方式分为6个类别，即：时尚型、自保型、领袖型、上进型、迷茫型(缺乏生活目标型)和平庸型2008年8月怎样把消费者分类？时尚型：这类消费者约占样本量的约21%，主要特征为：年龄相对较轻，平均年龄在35岁左右，教育程度相对较高，一般具有高中以上文化程度，虽然平均家庭月收入较好，平均在2200元左右，同时也是分散程度最高的，表明喜爱时尚并不是高收入者的专利。这一类型中的三资企业员工的比例最大，未婚的比例较大，约占1/4，女性的比例为55%，高于男性自保型：这类消费者占16%，他们更多的是为自己的生计考虑，考虑自己能否有稳定的经济来源，维持家庭的经济保障是他们最关心的问题。这些人的平均受教育程度较低，中年人的比例较高，平均年龄在44岁左右，家庭月收入较低，平均在1600元左右，国营企业员工以及离退休人员的比例较高。女性的比例高于男性领袖型：这类消费者占13%。教育程度处于社会平均水平，主要为中年人，有较多的生活阅历，年龄多在45-54岁之间。家庭月平均收入一般在1800元左右。在职业上没有显著特征。已婚比例是各类消费者中最高的，这似乎表明有稳定的家庭也是成为领袖的一个条件。男性比例占55%，高于女性2008年8月怎样把消费者分类？上进型：占消费者总人数的不到13%。他们对生活的态度积极，多为未婚青年，平均年龄在28岁左右，25岁以下的占40%，单身未婚的比例占1/2以上。职业上的显著特征是：1/3为学生，三资企业员工的比例达1/10。男性的比例高于女性。这类消费者是受教育程度最高的，他们的平均家庭收入却是最高的，月平均收入在2300元左右迷茫(缺乏生活目标)型：约占15%，他们既不注重经济保障，也不参加培训，生活节奏较缓慢。这类消费者主要为退休人员，约占该类型人员的2/3，剩下的主要为国营企业员工。平均年龄在50岁以上，他们的教育程度是最低的，家庭收入也是最低的，平均不到1600元。在性别分布上，女性的比例远远高于男性，占62