山东大学基于web的信息检索和知识发现chap9.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * C4.5的改进 1)缺少值的预测属性仍然可用 C4.5对于缺值的处理是基于概率分布的想法，在某一步分裂时，如果发现了某一条数据的某个属性缺值或为非法数据,则将该实例按照缺值属性的所有可能取值进行分裂，将其分裂为多个实例归属于不同的类别,并赋以不同的权值，该权值为某个可能的取值在该分类中的出现概率。而其他实例的权值为1。以此来计算该属性的信息增益。 2)有连续值的预测属性可用 C4.5中对连续属性的处理采用了二值离散的方法，即对某个连续属性A．找到一个最佳阈值T，根据A 的取值与阈值的比较结果，建立两个分支AT(左枝)和A=T(右枝)，T为分割点。从而用一个二值离散属性A’(只有两种取值AT、A=T)替代A．将问题又归为离散属性的处理。 一棵完全决策树能非常准确地反映训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象一般称为“过分拟合或过适应(over-fitting)。” ID3, C4.5是开放源码，可到Quanlan个人主页上下载 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 应用例子（根据婚姻和收入把客户分成能偿还贷款或不能两类） 因素 Refund (有房子了） Marriage Divorce （离婚） Evade (拖欠贷款） How to Estimate Probabilities from Data? Class: P(C) = Nc/N e.g., P(evade=No) = 7/10,  P(evade=Yes) = 3/10 For discrete attributes:  P(Ai | Ck) = |Aik|/ |Cc| where |Aik| is number of instances having attribute Ai and belongs to class Ck Examples: P(Status=Married|No) = 4/7P(Refund=Yes|Yes)=0 分类是否拖欠贷款(Yes/no) Example of Na?ve Bayes Classifier P(X|Class=No) = P(Refund=No|Class=No) ? P(Married| Class=No) ? P(Income=120K| Class=No) = 4/7 ? 4/7 ? 0.0072 = 0.0024 P(X|Class=Yes) = P(Refund=No| Class=Yes) ? P(Married| Class=Yes) ? P(Income=120K| Class=Yes) = 1 ? 0 ? 1.2 ? 10-9 = 0 Since P(X|No)P(No) P(X|Yes)P(Yes) Therefore P(No|X) P(Yes|X) = Class = No Given a Test Record: Na?ve Bayes Classifier If one of the conditional probability is zero, then the entire expression becomes zero Probability estimation: c: number of classes p: prior probability m: parameter Example of Na?ve Bayes Classifier A: attributes M: mammals N: non-mammals P(A|M)P(M) P(A|N)P(N) = Mammals no 匹配的情形 哺乳类（yes/no) Na?ve Bayes (Summary) Robust to isolated noise points Handle missing values by ignoring the instance during probability estimate calculations Robust to irrelevant attributes Independence assumption may not hold for some attributes U