惰性学习法和其他分类方法课件.pptVIP

惰性学习法和其他分类法 戴 奇 1 惰性学习法 急切学习法（前面提到的方法）：给定训练集, 在接收待分类的新元祖（如检验元组）之前，构造泛化（即分类）模型。 惰性学习法（也称为基于实例的学习法）：给定一个训练元组，简单地存储它 (或只是稍加处理) ，一直等到给定一个检验元组。仅当看到检验元组时，它才进行泛化，以便根据存储的训练元组的相似性对该元组进行分类。 优点：原理简单，实现起来比较方便。支持增量学习。能对超多边形的复杂决策空间建模。 缺点：计算开销大，需要有效的存储技术和并行硬件的支撑。 属于惰性学习的算法有：KNN分类、基于案例的推理分类 1.1 k最近邻分类法（KNN分类法） k最近邻分类法是20世纪50年代早期首次引进的。给定大量训练集时，该方法是劳动密集的，直到20世纪60年代计算能力大大增强之后才流行起来。此后被广泛用于模式识别领域。 1.1.1 KNN算法原理 基于类比学习，即通过给定的检验元组与和它相似的训练元组进行比较来学习。 训练元组用n个属性描述。每个元组代表n维空间的一个点。 这样，所有的训练元组都存放在n维模式空间中。 当给定一个未知元组时，k最近邻分类法有哪些信誉好的足球投注网站该模式空间，找出最接近未知元组的k个训练元组。这k个训练元组是未知训练元组的k个“最近邻”。最后取这k个点中的多数类作为检验元组的类别。 “邻近性”用距离度量，距离越大，表示两个点越不相似。 计算距离的方法：欧几里得距离、曼哈顿距离或其它距离。 但多采用欧几里得距离（简单）。 例：两个点或元组X1=（x11,x12,...,x1n）和X2=（x21,x22,...,x2n）的欧几里得距离是： 换言之，对于每个数值属性，取元组X1和X2该属性对应值的差，取差的平方并累计。并取累计距离计数的平方根。 例2： 下图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。 1.1.2 KNN算法中的细节处理 有助于防止具有较大初始值域的属性（如收入）比具有较小初始值域的属性（如二元属性）的权重过大。 例如，可以通过计算下式，使用最小—最大规范化将数值属性A的值v变换到[0,1]区间中的v 其中minA和maxA分别是属性A的最小值和最大值。 对于分类属性，一种简单的方法是比较元组X1和X2中对应属性的值。如果二者相同（例如，元组X1和X2都是蓝色），则二者之间的差为0。如果二者不同（例如，元组X1是蓝色，而元组X2是红色），则二者之间的差为1。 其他方法可采用更复杂的方案。（例如，对蓝色和白色赋予比蓝色和黑色更大的差值。） 取最大的可能差。 对于分类属性，如果属性A的一个或两个对应值丢失，则取差值为1； 如果A是数值属性，若两个比较的元组属性A的值均缺失，则取差值为1，若只有一个缺失，另一个存在并且已经规范化（记作v），则取差值为｜1-v｜和｜0-v｜中的最大者。 可以通过实验确定。 从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次k增值1，允许增加一个近邻。选取产生最小误差率的k。 一般，训练元组数越多，k的值越大。 最近邻分类法使用基于距离的比较，本质上赋予每个属性相等的权重。因此，当数据存在噪声或不相关属性时，它们的准确率可能会受到影响。 对属性赋予相关性权重w，w越大说明属性对分类的影响越相关。对噪声数据可以将所在的元组直接cut掉。 1.1.3 KNN算法流程 准备数据，对数据进行预处理 选用合适的数据结构存储训练数据和测试元组 设定参数，如k 维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组 随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列 遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L与优先级队列中的最大距离Lmax进行比较。若L=Lmax，则舍弃该元组，遍历下一个元组。若L Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列。 遍历完毕，计算优先级队列中k个元组的多数类，并将其作为测试元组的类别。 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k值。 1.1.4 KNN算法的改进策略 最近邻分类法在对检验元组分类时可能非常慢。如果D是具有|D|个元组的训练数据库，而k=1，则对一个给定的