惰性学习法和其他分类方法

惰性学习法和其他分类法

戴奇1惰性学习法急切学习法（前面提到的方法）：给定训练集,在接收待分类的新元祖（如检验元组）之前，构造泛化（即分类）模型。惰性学习法（也称为基于实例的学习法）：给定一个训练元组，简单地存储它(或只是稍加处理)，一直等到给定一个检验元组。仅当看到检验元组时，它才进行泛化，以便根据存储的训练元组的相似性对该元组进行分类。优点：原理简单，实现起来比较方便。支持增量学习。能对超多边形的复杂决策空间建模。缺点：计算开销大，需要有效的存储技术和并行硬件的支撑。属于惰性学习的算法有：KNN分类、基于案例的推理分类2023/9/1521.1k最近邻分类法（KNN分类法）k最近邻分类法是20世纪50年代早期首次引进的。给定大量训练集时，该方法是劳动密集的，直到20世纪60年代计算能力大大增强之后才流行起来。此后被广泛用于模式识别领域。2023/9/1531.1.1KNN算法原理基于类比学习，即通过给定的检验元组与和它相似的训练元组进行比较来学习。训练元组用n个属性描述。每个元组代表n维空间的一个点。这样，所有的训练元组都存放在n维模式空间中。当给定一个未知元组时，k最近邻分类法搜索该模式空间，找出最接近未知元组的k个训练元组。这k个训练元组是未知训练元组的k个“最近邻”。最后取这k个点中的多数类作为检验元组的类别。2023/9/154“邻近性”用距离度量，距离越大，表示两个点越不相似。计算距离的方法：欧几里得距离、曼哈顿距离或其它距离。但多采用欧几里得距离（简单）。

例：两个点或元组X1=（x11,x12,...,x1n）和X2=（x21,x22,...,x2n）的欧几里得距离是：

换言之，对于每个数值属性，取元组X1和X2该属性对应值的差，取差的平方并累计。并取累计距离计数的平方根。

2023/9/155例1：如果它走路像鸭子,叫声也像鸭子,那么他可能就是只鸭子TrainingRecordsTestRecordComputeDistanceChoosekofthe“nearest”records2023/9/156例2：

下图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。2023/9/1571.1.2KNN算法中的细节处理有助于防止具有较大初始值域的属性（如收入）比具有较小初始值域的属性（如二元属性）的权重过大。

例如，可以通过计算下式，使用最小—最大规范化将数值属性A的值v变换到[0,1]区间中的v'其中minA和maxA分别是属性A的最小值和最大值。

属性的数值规范化2023/9/158对于分类属性，一种简单的方法是比较元组X1和X2中对应属性的值。如果二者相同（例如，元组X1和X2都是蓝色），则二者之间的差为0。如果二者不同（例如，元组X1是蓝色，而元组X2是红色），则二者之间的差为1。其他方法可采用更复杂的方案。（例如，对蓝色和白色赋予比蓝色和黑色更大的差值。）比较的属性不是数值类型而是分类类型（如颜色）2023/9/159取最大的可能差。对于分类属性，如果属性A的一个或两个对应值丢失，则取差值为1；如果A是数值属性，若两个比较的元组属性A的值均缺失，则取差值为1，若只有一个缺失，另一个存在并且已经规范化（记作v'），则取差值为｜1-v'｜和｜0-v'｜中的最大者。缺失值的处理2023/9/1510可以通过实验确定。从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次k增值1，允许增加一个近邻。选取产生最小误差率的k。一般，训练元组数越多，k的值越大。确定近邻数k的值2023/9/1511最近邻分类法使用基于距离的比较，本质上赋予每个属性相等的权重。因此，当数据存在噪声或不相关属性时，它们的准确率可能会受到影响。对属性赋予相关性权重w，w越大说明属性对分类的影响越相关。对噪声数据可以将所在的元组直接cut掉。对噪声数据或不相关属性的处理2023/9/15121.1.3KNN算法流程准备数据，对数据进行预处理选用合适的数据结构存储训练数据和测试元组设定参数，如k维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L与优先级队列中的最大距离Lmax进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L<Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列。遍历完毕，计算优先级队列中k个元组的多数类，并将其作为测试元组的类别。测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k值。2023/9/15131.1.4KNN算法的改进策略最近邻分类法在对检验元组分类时可能非常慢。如果D是具有|D|个元组的训练数据库，而k=1，则对一个给定的检验元组分类需要O(|D|)次比较。改进如下：将存储的训练元组预先排序并安排在搜索树中，比较次数可以降低到O(log|D|)。并行实现可以将运行时间降低为常数，即O（1），独立于|D|。部分距离计算，取n个属性的“子集”计算出部分距离，若超过设定的阈值则停止对当前元组作进一步计算。转向下一个元组。剪枝或精简：删除证明是“无用的”元组，可以减少存储元组的总数。2023/9/15141.2基于案例的推理（CBR）CBR分类法使用一个问题解的数据库来求解新问题。不像最近邻分类法将训练元组作为欧几里得空间的点存储，CBR将问题求解元组或“案例”作为复杂的符号描述存储。2023/9/15151.2.1CBR的应用商务应用：诸如顾客服务台问题求解，其中案例描述产品有关的诊断问题。工程和法律领域：其中案例分别是技术设计和合法的裁决。医学教育：其中患者病史和治疗方案用来帮助诊断和治疗新的患者。2023/9/15161.2.2CBR的原理当给定一个待分类的新案例时，CBR首先检查是否存在一个同样的训练案例。如果找到一个，则返回附在该案例上的解。如果找不到同样的案例，则CBR将搜索具有类似于新案例成分的训练案例。概念上讲，这些训练案例可以视为新案例的近邻。如果案例用图表示，则涉及搜索类似于新案例的子图。CBR试图组合近邻训练案例的解，提出新案例的解。如果各解之间出现不相容，则可能需要回溯搜索其他解。2023/9/15171.2.3CBR的挑战找到一个好的相似性度量和组合解的合适的方法。索引训练案例，选择显著的特征和开发有效的索引技术。准确性和有效性之间的折衷随着存储的案例数量增大而演变。2023/9/15182其他分类方法这些方法包括遗传算法、模糊集和粗糙集方法。这些方法不常在商品化数据挖掘系统的分类中使用。但在某些应用中确实表现出了它们的优点。2023/9/15192.1遗传算法遗传算法:模拟生物进化遗传算法分类：就是找到一组能很好拟合训练样本的IF-THEN规则。创建由随机产生的规则组成的初始种群每个规则由一个二进位串表示E.g.,ifA1andNOTA2thenC2可编码为100同理，ifNOTA1andNOTA2thenC1可编码为001若一个属性具有k个值(k>2),则可用k个二进位对该属性的值编码。类可以用类似的方式编码。根据“适者生存”的原则,形成由当前种群中最适合的规则及其后代组成新的种群。在典型情况，规则的拟合度用它在训练样本集的分类准确率评估。2023/9/1520后代通过使用诸如交叉和变异等遗传操作来创建。在交叉操作中，来自规则对的字串交换，形成新的规则对。在变异操作中，规则串中随机选择的位反转。由先前的规则群体产生新的规则群体的过程继续，直到群体P进化，P中的每个规则满足预先指定的拟合度阀值。遗传算法易于并行，并且已用于分类和其他优化问题。在数据挖掘中，还可用于评估其他算法的拟合度。2023/9/15212.2模糊集方法基于规则的分类系统有一个缺点：对于连续属性，它们有陡峭的截断。例如，考虑下面关于顾客信用卡申请审批的规则。该规则本质上说：工作两年以上并且具有较高收入（即至少50000美元）的顾客申请将批准。IF（year_employed≥2）AND(income≥50K)THENcredit=approved根据这个规则，一个至少工作两年的顾客将得到信用卡，如果他的收入是50000美元。但是，如果他的收入是49000美元，他将得不到。这种苛刻的阈值看来不公平。2023/9/15222.2.1模糊逻辑简介经典二值逻辑中，通常以1表示“真”，0表示“假”，一个命题非真即假。在模糊逻辑中，一个命题不再非真即假，它可以被认为是“部分的真”。模糊逻辑取消二值之间非此即彼的对立，用隶属度表示二值间的过渡状态。2023/9/15232.2.2模糊集合与隶属度函数它是美国加利福尼亚大学控制论专家L.A.扎德于1965年首先提出的。在普通集合中，论域中的元素（如a）与集合（如A）之间的关系是属于（

），或者不属于（

），它所描述的是非此即彼的清晰概念。但在现实生活中并不是所有的事物都能用清晰的概念来描述，如:风的强弱

人的胖瘦

年龄大小个子高低2023/9/1524模糊集合（简称模糊集）就是指具有某个模糊概念所描述的属性的对象的全体。由于概念本身不是清晰的、界限分明的，因而对象对集合的隶属关系也不是明确的、非此即彼的。元素属于模糊集合的程度用隶属度来表示。用于计算隶属度的函数称为隶属函数。隶属度的值为[0，1]闭区间上的一个数，其值越大，表示该元素属于模糊集合的程度越高，反之则越低。模糊集完全是由隶属度刻画的，没有明确的边界。2023/9/15252.2.3模糊集分类我们可以将income离散化成分类的，如{low_income,medium_income,high_income}，然后使用模糊逻辑，允许对每个类定义“模糊”阈值或边界。income的模糊真值，表示income值关于类{low,medium,high}的隶属度。每个类表示一个模糊集。注意，给定的收入值x可能隶属于多个模糊集。x在每个模糊集的隶属值的总和不必为12023/9/1526模糊逻辑使用0.0-1.0之间的真值表示一个特定的值是一个给定类成员的隶属程度，而不是用类之间的精确截断。然后，每个类表示一个模糊集。因而，使用模糊逻辑，可以表达这样的概念：在某种程度上，49000美元的收入是高的，尽管没有50000美元的收入高。2023/9/1527不像传统的“明确的”集合，元素或者属于集合S或者属于它的补，在模糊集合论中，元素可以属于多个模糊集。例如，收入值49000美元属于模糊集medium和high，但具有不同的隶属度。使用模糊集概念如上图，可以证明mmedium_income($49K)=0.15且mhigh_income($49K)=0.96其中m是隶属函数，分别对模糊集medium_income和high_income计算。在模糊集理论中，给定元素x（例如49000美元）的隶属值的和不必等于1,。这与传统的概率论不同。传统的概率论受总和公理的约束。2023/9/1528对于进行基于规则的分类的数据挖掘系统来说，模糊集理论是有用的。它提供了模糊度量的操作。假设除了income的模糊集之外，还为属性years_employed定义模糊集junior_employee和senior_employee。假设有一个规则，对给定的雇员x检测规则前件（IF部分）的high_income和senior_employee。如果这两个模糊度量用AND连接在一起，则取它们的最小度量为该规则的度量。换言之，m(high_incomeANDsenior_employee)(x)=min(mhigh_income(x)),msenior_employee(x))这类似于说一条链与它最弱的链接一样结实。2023/9/1529（3）确定模糊输出并去模糊化 规则a和规则c的结论是运转时间为长，规则b和规则d的结论是运转时间为中。故运转时间对“长”的隶属度是规则a和规则c强度较大者0.075，运转时间对“中”的隶属度是规