1.2 数据挖掘中的软计算技术概述

上面已列出许多数据挖掘方法，有些是有效的，但有些并不令人满意。这是由于：

（1）大量积累的数据的自然不精确性；

（2）大量积累的多属性数据的内在复杂性[14]。

软计算可以为数据挖掘提供有效的技术。

1.2.1 软计算的发展状况

在物理、工程、技术应用、经济等领域中常常出现由多变量和多参数模型描述的物理系统，它们具有非线性耦合性。在处理这样的系统时，人们面临着高度的不确定性和不精确性。而软计算正是以放弃高精度而追求近优解或可行解为目的的。

Zadeh把基于二元逻辑、精确（Crisp）系统、数值分析和精确软件的计算称为硬计算，以区别于基于模糊逻辑、神经网络、概率推理的软计算。前者具有准确性和绝对性，而后者具有逼近性和不精确性（Dispositionality）。在硬计算中不精确性和不确定性是不期望的性质，而在软计算中则不然。软计算是一个汇集不同方法的学科。其宗旨不同于传统的硬计算，它的目标是适应真实世界的普遍深入的不精确性。因此，软计算的指导原则是用容忍不精确性、不确定性和部分真实来获得易处理性、稳健性、低处理代价及与现实较好的融合。软计算把人脑作为其角色模型。

软计算主要包含模糊逻辑（FL）、神经元计算（NC）和概率推理（PR），近来还包括遗传算法（GA）、混沌理论、信任网络（Belief Networks）、粗糙集等。它们是相互补充而不是相互竞争的。这些独特且相关的方法目前得到广泛的注意，并且已经找到大量的实际应用领域，如工业过程控制、故障诊断、语音辨识和不确定状态下的计划安排等。从这个角度来看，模糊逻辑的主要贡献是其逼近推理的能力，是字符计算的一种方法；神经网络理论提供了系统辨识、学习和自适应的有效方法；概率推理提供了在复杂的推理网络中对于表示和传播可能性和可信度（Beliefs）进行计算的有效方法；而GA则是系统化的随机搜索和优化方法。软计算是不精确性、不确定性和部分真实方法论的聚合体，这些方法结合起来比单独使用的效果更好。由此得到的结果具有易处理性、稳健性及与现实相一致性，并且这些结果常常好于只用传统的（硬）计算方法得到的结果[14][15][16]。

软计算是混合的智能化计算方法，它不以精确解为目标。高精度对于实际应用有时是没有意义的，大部分情况下可牺牲精度来换取效率。

1.2.2 KDD中的软计算技术简介

KDD是抽取数据库中隐含的知识，把软计算应用到KDD中涉及接受不精确性，这种不精确性体现在数据、数据结构及挖掘出的信息中[14]。在许多方面，软计算表示对计算目标的有意义的模式转变，此转变反映了如下事实：人脑拥有非凡的存储和处理普遍深入的不精确、不确定和缺乏绝对性信息的能力。软计算为处理KDD中的不精确性和不确定性提供了有效的技术，其中各种方法的混合使用构成了KDD中独特的挖掘技术。下面仅简单介绍几种。

1.遗传算法

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，其内部表现（基因型）是某种基因组合，它决定了个体的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，一开始需要实现从表现型到基因型的映射，即编码工作。由于仿照基因编码的工作很复杂，我们往往对此进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化出越来越好的近似解。在每一代，根据问题域中个体的适应度选择个体，并借助自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致后代种群比前代种群更加适应环境，末代种群中的最优个体经过解码，可以作为问题的近似最优解。该算法主要分为以下步骤。

（1）种群初始化。首先随机生成初始种群，一般该种群的数量为100～500，采用二进制将一个染色体编码为基因型。随后用进制转化，将二进制的基因型转化成十进制的表现型。

（2）适应度计算。将目标函数值作为个体的适应度。

（3）选择操作。将适应度高的个体从当前种群中选出来，即以与适应度成正比的概率来确定各个个体遗传到下一代群体中的数量[17]。

2.支持向量机

支持向量机（Support Vector Machine，SVM）是一类按监督学习（Supervised Learning）方式对数据进行二元分类（Binary Classification）的广义线性分类器（Generalized Linear Classifier），其决策边界是对学习样本求解的最大边距超平面。该算法在解决小样本、非线性及高维模式识别等问题时具有优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机建立在统计学习理论和结构风险最小原理基础上，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳解，以期获得最好的推广能力。在机器学习中，支持向量机是监督学习模型，可以分析数据，识别模式，用于分类和回归分析[17]。

3.模糊神经网络

将模糊逻辑与神经网络相结合，即把模糊逻辑中的不精确性引入神经网络中。M.Ayoubi 和R.Isermann[18]提出了混合的神经元模糊网络，用于自适应规则提取，其结构如图1.4所示。此结构由三层网络组成，与三步模糊推理相对应：第一层为先行层（Antecedent Layer），完成输入的模糊化。这层的输出表示输入子集的模糊隶属度。第二层为关系层，它估计规则的成分，研究规则实现的等级。第三层为结论层，聚集规则库和计算反模糊值，进行精确输出。

此网络由给出的数据自动抽取IF-THEN规则，然后基于Hebbian学习规则来简化需要的规则。

文献[19]提出的模糊神经网络用于时间序列预测。时间序列的神经网络模型为

其中，εn是均值，fw是以权值矢量W为参数的函数。

模糊规则Rj：如果x1是A1j，…，xN是ANj，则

Aij(i=1,2,…,N;j=1,2,…,K)是模糊子集，K是模糊规则个数。为隶属函数。上述模糊推理可以由组合神经网络输出为

其中，gj为门限神经网络的输出，计算式为

训练此网络采用动态模糊聚类来实现。

4.概率推理与演化算法的结合

Bayesian信任网络（Bayesian Belief Networks，BBN）是概率推理中典型的方法，在实际应用中它对不确定性条件下的决策支持问题获得可能的解是有效的，能够表示和处理传统的方法不能实现的复杂模型，并且能基于部分或不确定的数据预测事件，如机械故障诊断、医疗诊断等。它的理论基础为概率论。在数据挖掘技术中采用BBN可以进行模糊信息回溯，取代传统的布尔逻辑。BBN是一个表示变量间概率关系的图网，是具有关联概率表的图，如图1.5所示。BBN由节点和有向弧组成，节点表示随机变量或不确定量，有向弧表示变量间的因果/相关关系，变量间的影响程度由前条件概率定量地表示。表1.1为节点概率表，表1.2为条件概率表[20][21]。

文献[22]把GA算法用于BBN来描述典型的诊断问题。di(i=1,2,…,6)表示疾病名称，sj(j=1,2,…,5)表示症状，把所对应的BBN映射为线性结构：

上面的串表示的网络中d2、d3和s1的状态存在，其他节点的状态不存在。与之相应的概率可以计算出来。随机地产生这样的网络的种群，然后对此种群把概率作为适值函数引导实施遗传操作，找到的最大概率状态超过随机概率取样获得的状态。

5.P-CLASSIC概率描述逻辑法

P-CLASSIC概率描述逻辑法[23]利用描述逻辑和Bayesian网络，给出了一个P-CLASSIC语义和有效的概率包容推理，它能够表示不确定性，其原理是把概率加到一阶逻辑中并用Bayesian网络作为表示工具。图1.6为自然界事物的部分Bayesian网络，该网络中的节点包含每个初始概念：动物、蔬菜、哺乳动物、肉食动物、草食动物。每个节点的值依据一个对象是否属于此概念为真或假，网络定义了一个连接概率分布，例如，考虑（动物，非蔬菜，非哺乳动物，肉食动物，非草食动物），其概率为：P(动物)×P(非蔬菜|动物)×P(非哺乳动物|动物)×P(肉食动物|动物,非哺乳动物)×P(非草食动物|动物,肉食动物)=0.5×1×0.7×0.2×1=0.07。

6.模糊逻辑与演化算法的结合

文献[24]为了发现数据库中由欺诈者留下的“指纹”，利用模糊逻辑与演化算法的结合来进行模式分类，采用遗传程序设计去演化模糊规则，实现准确和智能的分类。其实现是由模糊规则演化器来完成的。图1.7为模糊规则演化器的结构图。

系统开始时对训练数据的每一列用一维聚类算法进行聚类，聚类得到的最大、最小值用于模糊系统的隶属函数的域。四个适值函数确保误分类的概率尽可能小，强制对区分怀疑的数据类和正常的数据类进行演化，要求怀疑项的值比正常值大，所有演化得到的规则是短的。选取交叉概率为0.8，变异概率为0.4，种群大小为100。

7.粗糙神经网络法

粗糙集在数据挖掘中的应用已经显示出其处理不确定信息的优越性，粗糙集与神经网络结合后，其网络性能在某些情况下优于传统的神经网络。P.Lingras[25]描述的用于粗糙模式预测的粗糙神经网络是由传统的神经元与粗糙神经元结合在一起构成的网络，能够处理粗糙模式，每个粗糙神经元存储输入和输出的上下界值。依据应用的特性，神经网络中的两个粗糙神经元能够使用两条或四条线相互连接起来，上界和下界神经元的重叠表明它们之间的信息交流，其连接方式如图1.8所示。一个粗糙神经元也能与传统的神经元使用两条线相互连接起来。

一个神经元（传统的、粗糙下界的或粗糙上界的）的输入用加权和来计算：

其中，i和j代表神经元。

一个粗糙神经元r的输出用变换函数按如下公式来计算：

一个传统的神经元i的输出可以简单地按下式计算：

使用如下的sigmoid变换函数：

其中，gain是由设计者确定的参数，以决定sigmoid函数在零点处的陡度。

权值的修正由如下的规则来确定：

其中，α为学习参数。

若网络由三层结构构成，可以采用两种形式：一种为输入层由粗糙神经元组成，隐含层及输出层由传统神经元组成；另一种为输入层及隐含层由粗糙神经元组成，输出层由传统神经元组成。其中的连接均采用全连接方式。

8.讨论

上面仅介绍了几种常见的软计算方法，在实际应用中还有许多其他有效的方法，比如文献[26]中给出的用于预测渗透性的混合软计算系统是一个模糊逻辑、神经网络和遗传算法的混合方法，文献[27]中给出了混沌模拟退火神经网络法，这些混合智能方法吸取了各类方法的优点，不同方法相互补充，变化出多种使用效果良好的方法。大部分模糊逻辑的应用涉及模糊规则的提取，在实际应用中模糊规则与人的直觉非常接近，所以模糊逻辑在软计算中起着重要作用。神经网络技术的主要工具为梯度程序设计，而遗传算法、模拟退火和随机搜索方法的应用没有梯度存在的假设。梯度程序设计和无梯度方法的相互补充提供了神经元遗传系统概念和设计的基础。它们的结合主要表现为神经元模糊系统、模糊遗传系统、神经元遗传系统和神经元模糊遗传系统。

在信息化时代，对信息的收集、存储、处理、利用是势在必行的，而各种相应的工具的开发及研制是受科技发展水平制约的。目前，为使数据的利用率和潜在的效益得以发挥，对数据挖掘的方法及系统提出了更高的要求，而现有方法和系统不完善和不够有效是促使我们在此方面进行研究的驱动力。

现实生活中不确定性是一个本质特征，因此，在不确定性的条件下进行推理和决策是智能行为的核心内容[28]。软计算技术在处理不确定性、不精确性知识方面的优势为知识发现过程提供了智能化方法，不论是神经元模糊技术和演化算法的结合，还是演化算法、混沌理论与其他方法的结合，都为数据挖掘提供了更好的智能挖掘工具，使机器本身能在数据库中有效地找到有价值的但未被识别的数据模式，这种机器智能的实现，离不开软计算技术的使用和发展。