第九讲 分类与预测.ppt

第八讲 分类与预测 Classification and Prediction What is classification? What is prediction? Issues regarding classification and prediction Classification by decision tree induction Bayesian classification Rule-based classification（自学） Classification by back propagation Support Vector Machines (SVM) （自学） Associative classification （自学） Lazy learners (or learning from your neighbors) （自学） Other classification methods （自学） Prediction Accuracy and error measures （自学） Ensemble methods （自学） Model selection （自学） Summary 分类 vs. 预测 分类(Classification): 预测分类标号(离散值或名词性词) 建立一个模型，基于训练集的数据和分类属性的值（类标识）来分类，并在新数据中使用该模型。 预测(Prediction): 连续值函数上的建模, 例如，预测未知或缺失的值 典型应用 信用度 目标市场 医疗诊断 分类的两个步骤 模型创建: 描述预定的数据类集或概念集。 假定每个元组或样本属于一个预定义的类，由一个称为类标号属性（class label attribute）的属性确定。 用于建模的元组集称为训练集(training set) 模型表示为：分类规则、判定树或属性公式 模型应用:用于分类未来或未知对象 评估模型的准确率 测试样本的已知标号与根据模型获得的分类结果作比较。 准确率定义为正确被模型分类的测试样本的百分比 测试集独立于训练集，否则，学习模型倾向于过分适合(over-fitting)数据 如果准确率可被接受，使用模型用于分类类标号未知的数据。 Classification Process (1): Model Construction Classification Process (2): Use the Model in Prediction 决策树算法 基本算法(贪心算法)， 树的构建方式：自顶向下递归的各个击破方式 树以代表训练样本的单个节点开始 如果样本都在同一类中，则节点为叶子节点，并用该类标记 否则，选择能够最好地将样本分类的属性(称为测试属性，必须是离散值的) 对测试属性的每个已知值，创建一个分支，并据此划分样本 递归形成每个划分上的样本决策树 递归划分步骤仅当下列条件之一成立时立即停止 给定节点的所有样本属于同一个类 没有剩余属性可作进一步划分样本—— majority voting is employed for classifying the leaf 没有剩余的样本 Attribute Selection: Information Gain Class P: buys_computer = “yes” Class N: buys_computer = “no” means “age =30” has 5 out of 14 samples, with 2 yes’es and 3 no’s. Hence Similarly, Computing Information-Gain for Continuous-Value Attributes Let attribute A be a continuous-valued attribute Must determine the best split point for A Sort the value A in increasing order Typically, the midpoint between each pair of adjacent values is considered as a possible split point (ai+ai+1)/2 is the midpoint between the values of ai and ai+1 The point with the minimum expected information requirement for A is selected as the split-point for A Split: D1 is the set