分类算法综述

能力之间寻求最佳折衷，以期获得最好的推广能力。SVM是从线性可分情况下的最优分类面发展而来的，使分类间隔最大实际上就是对推广能力的控制，这是SVM的核心思想之一。

由于统计学习理论和支持向量机建立了一套较好的在小样本下机器学习的理论框架和通用方法，既有严格的理论基础，又能较好地解决小样本、高维和局部极小点等实际问题，因此成为继神经网络之后的又一个研究方向。

但是，处理大规模数据集时，SVM速度慢，往往需要较长的训练时间。而且，SVM方法需要计算和存储核函数矩阵，当样本数目较大时，需要很大的内存。其次，SVM在二次型寻优过程中要进行大量的矩阵运算，多数情况下，寻优算法是占用算法时间的主要部分。

2.7 基于软计算的分类方法

在数据挖掘领域，软计算的用途越来越广泛：模糊逻辑用于处理不完整、不精确的数据以及近似答案等；神经网络用于高分线性决策、泛化学习、自适应、自组织和模式识别；遗传算法用于动态环境下的高效搜索、复杂目标对象的自适应和优化；粗糙集根据“核”属性获得对象的近似描述，能有效处理不精确、不一致、不完整等各种不完备信息。当数据集表现出越来越多的无标签性、不确定性、不完整性、非均匀性和动态性特点时，传统数据挖掘算法对此往往无能为力，软计算却为此提供一种灵活处理数据的能力，软计算内的融合与传统数据挖掘方法的结合逐渐成为数据挖掘领域的研究趋势。

2.7.1 粗糙集（rough set）

粗糙集理论是一种刻划不完整和不确定性数据的数学工具，不需

要先验知识，能有效地处理各种不完备信息，从中发现隐含的知识，并和各种分类技术相结合建立起来能够对不完备数据进行分类的算法。粗糙集理论将分类能力和知识联系在一起，使用等价关系来形式化地表示分类，知识因而表示为等价关系集R对离散空间U的划分。粗糙集理论还包括求取数据中最小不变集合最小规则集的额理论，即简约算法（即分类中属性简约和规则生成），其基本原理是通过求属性的重要性并排序，在泛化关系中找出与原始数据具有同一决策或分辨能力的相关属性的最小集合，以此实现信息简约，这也是粗糙集理论在分类中的应用。

简约主要借助于信息表达这样一种有效的知识表达形式；在保持信息表中决策属性和条件属性依赖关系不变时进行的信息表简约，具体包括属性简约和值简约。

属性简约在一定程度上对信息表中的非必要的冗余信息进行简约，但对每一个实例而言仍可能存在不必要的属性，因此在不引起冲突的条件下可将每一个实例的不必要属性删除，即为值简约。值简约的最终结果就是分类所需要的规则，常见的值简约算法包括归纳值简约、启发式值简约、基于决策矩阵的值简约算法、增量式规则获取算法和其他一些改进算法。

粗糙集本身限制条件较强，在实际应用中，可以模态逻辑和概率统计信息对基本粗糙集模型进行扩展，从而形成了代数粗糙集模型和概率统计粗糙集模型。

2.7.2 遗传算法

遗传算法在解决多峰值、非线性、全局优化等高复杂度问题时具

备独特优势，它是以基于进化论原理发展起来的高效随机搜索与优化方法。它以适应函数为依据，通过对群体、个体施加遗传操作来实现群体内个体结构的优化重组。在全局范围内逼近最优解。遗传算法综合了定向搜索与随机搜索的优点。避免了大多数经典优化方法基于目标函数的梯度或高阶导数而易陷入局部最优的缺陷，可以取得较好的区域搜索与空间扩展的平衡。在运算时随机的多样性群体和交叉运算利于扩展搜索空间；随着高适应值得获得，交叉运算利于在这些解周围搜索。遗传算法由于通过保持一个潜在解的群体进行多方向的搜索而有能力跳出局部最优解。

遗传算法的应用主要集中在分类算法等方面。而基本思路如下：数据分类问题看成是在搜索问题，数据库看作是搜索空间，分类算法看作搜索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组分类规则进行进化，直到数据库能被该组分类规则覆盖，从而挖掘出隐含在数据库中的分类规则。应用遗传算法进行数据分类，首先要对实际问题进行编码；然后定义遗传算法的适应度函数，由于算法用于规则归纳，因此，适应度函数有规则覆盖的正例和反例来定义。1978年Holland实现了第一个基于遗传算法的机器学习系统CS-1(cognitive system level one)，其后又提出了桶队（Bucket Brigade）算法。1981年Smith实现了与CS-1有重大区别的分类器LS-1, 以此为基础，人们又提出了基于遗传算法的分类系统，如GCLS(genetic classifier learning system)等算法。

2.7.3 模糊逻辑

模糊数学是研究模糊现象数学。模糊数学最基本概念是隶属函数，

即以一个值域在[0,1]之间的隶属函数来描述论域中对象属于某一个类别的程度，并以此为基础确定模糊集的运算法则、性质、分解和扩展原理、算子、模糊的、模糊集的近似程度等度量概念和算法。 分类操作离不开向量相似程度的计算，而模糊分类操作也需要向量模糊相似系数的计算。在模糊分类方法中，首先要建立模糊相似矩阵，表示对象的模糊相似程度其元素称为模糊相似系数，其确定方法主要有：数量积法、夹角余弦法、相关系数法、最大最小法、算术平均最小法、几何平均最小法、绝对值指数法、指数相似系数法、绝对值倒数法、绝对值减数法、参数法、贴近度法。

模糊分类方法可以很好地处理客观事物类别属性的不明确性，主要包括传达闭包法、最大树法、编网法、基于摄动的模糊方法等。但人们更多地将模糊方法与其他分类算法结合起来，既有与传统分类算法，如模糊决策树、模糊关联规则挖掘等的结合，也有与软计算在内其他算法，如模糊神经网络等的结合。

2.7.4 人工神经网络算法

神经网络是分类技术中重要方法之一。人工神经网络（Artificial Neural Networks，ANN）是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。在这种模型中，大量的节点（或称”神经元”，或”单元”）之间相互联接构成网络，即”神经网络”，以达到处理信息的目的。神经网络通常需要进行训练，训练的过程就是网络进行学习的过程。训练改变了网络节点的连接权的值使其具有分类的功能，经过训练的网络就可用于对象的识别。神经网络的优势在于：（1）可以任意精度逼近任意函数；（2）神经网络方法本身属于非线性模型，