| 1996年，Fayyad、Piatetsky-Shapiro和Smyth [FPS96] 对KDD（Knowledge Discovery from Databases）和数据挖掘的关系进行了阐述。他们指出，KDD是识别出存在于数据库中有效的、新颖的、具有潜在效用的、最终可理解的模式的非平凡过程，而数据挖掘则是该过程中的一个特定步骤。但是，随着该领域研究的发展，研究者们目前趋向于认为KDD和数据挖掘具有相同的含义，即认为数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识。
数据挖掘的困难主要存在于三个方面 [GW98]：首先，巨量数据集的性质往往非常复杂，非线性、时序性与噪音普遍存在；其次，数据分析的目标具有多样性，而复杂目标无论在表述还是在处理上均与领域知识有关；第三，在复杂目标下，对巨量数据集的分析，目前还没有现成的且满足可计算条件的一般性理论与方法。但是，由于现实世界数据库中存在着大量有待利用的信息，在潜在的巨大利益驱动下，数据挖掘研究目前成为了机器学习、数据库等领域的研究热点。在早期工作中，研究者们主要是将符号型机器学习方法与数据库技术相结合，但由于真实世界的数据关系相当复杂，非线性程度相当高，而且普遍存在着噪音数据，因此这些方法在很多场合都不适用 [Wu95]。如果能将神经计算技术用于数据挖掘，将可望借助神经网络的非线性处理能力和容噪能力，较好地解决这一问题。另一方面，从挖掘出的知识种类来看，目前数据挖掘研究主要着重于关联规则、特征规则、分类规则、聚类规则、时序规则、模式相似性、Web浏览路径等方面。虽然利用神经计算挖掘关联规则具有较大难度，但其完全可以胜任其他种类知识的挖掘。因此，设计出基于神经网络的数据挖掘方法并将其用于真实世界问题，不仅是可行的，而且也是必要的。
研究进展
一些研究者 [LSL95, CS97] 指出，将神经计算技术应用于数据挖掘主要存在两大障碍。首先，神经网络学到的知识难于理解。其次，学习时间太长，不适于大型数据集。如果这两个问题得以解决，基于神经网络的数据挖掘将具有广泛的应用前景。
针对上述问题，基于神经网络的数据挖掘主要有两方面的研究内容，即增强网络的可理解性以及提高网络学习速度。目前，前者的解决方案是从神经网络中抽取易于理解的规则，后者的解决方案则是设计快速学习算法。由该思路出发，Lu等人 [LSL95] 设计了一个数据挖掘系统NeuroRule，并对Agrawal等人 [AIS93] 提出的数据挖掘基准测试问题进行了实验；本文作者 [ZCC99] 则利用规则抽取算法SPT [ZHYC00] 和快速学习算法FTART [CZLC96, CLZC97]，成功地对台风数据库进行了分类规则挖掘。
值得注意的是，在试图将神经计算用于数据挖掘，甚至在数据挖掘产生之前，就已经有研究者对神经网络规则抽取以及快速学习算法进行了研究，他们的工作为基于神经网络的数据挖掘的发展奠定了良好的基础。
规则抽取
神经网络规则抽取的研究最早开始于80年代末。1988年，Gallant [Gal88] 设计了一个可以用if-then规则解释推理结论的神经网络专家系统。在此之后，很多研究者进行了这方面的研究，并取得了大量成果。1998年，IEEE Transaction on Neural Networks专门为神经网络规则抽取出版了一期专刊，Tickle和Andrews [TA98] 在首篇文章中明确指出，从神经网络中抽取规则已经是当前神经网络界急需解决的问题，这充分说明该领域已经成为了神经计算研究的热点。
根据设计思想的不同，目前的方法大致可以分成两大类，即基于结构分析的方法和基于性能分析的方法。本节后续部分将对这两大类中的典型算法进行介绍和分析。值得注意的是，有的研究者 [ZLZ99] 将神经网络规则抽取作为一种机器学习方法进行研究，他们所关注的是抽取出的规则的泛化精度，而非规则对网络的保真度。由于这些方法的目的和作用并不是增强神经网络的可理解性，因此本文没有对它们进行介绍。
A. 基于结构分析的方法
基于结构分析的神经网络规则抽取方法把规则抽取视为一个搜索过程，其基本思想是把已训练好的神经网络结构映射成对应的规则。由于搜索过程的计算复杂度和神经网络输入分量之间呈指数级关系，当输入分量很多时，会出现组合爆炸。因此，此类算法一般采用剪枝聚类等方法来减少网络中的连接以降低计算复杂度。
1988年，Gallant [Gal88] 设计了一个神经网络专家系统，并提出了一个简单的规则抽取算法用于解释专家系统所做的推理。该算法通过抽取单个规则来解释神经网络如何为某个给定事例（case）得出结论。其基本思想就是从当前已知的信息集中选择一个能有效地产生该结论的最小信息集合，也就是说，不管其他未知输入分量的取值为多少，只要满足该最小信息集合的取值要求就可以得出结论。由于该算法非常简单，只适用于连接权较少的小型的神经网络。
1991年，Fu [Fu91] 提出了KT算法。该算法将网络中结点的激活值通过近似处理为0和1，将属性分为“正属性”和“负属性”，前者对某结论起到确认作用，后者则起否定作用。在所有的“负属性”都不出现的情况下，找出所有最多由k个“正属性”组合的集合。然后从该集合中找出最多有k个前件（相应于k个“正属性”）的规则，这些规则在 “负属性” 部分或全部出现的情况下，仍然使某结论成立。对单层网络，通过上述处理就可以抽取出规则。对多层网络，KT将隐结点视为“隐属性”，然后按处理单层网络的方法一层一层地抽取出规则，最后通过“代入”等方法重写这些规则，直到规则中只出现输入属性和输出结论为止。值得注意的是，虽然KT算法对“正”、“负”属性的区分降低了规则搜索复杂度，但这也限制了算法的规则抽取能力，使得抽取出的规则无法精确地描述原神经网络。
1992年，Towell和Shavlik [TS92] 为基于知识的神经网络（Knowledge Based Artificial Neural Networks, KBANN）[TS94] 设计了一种规则抽取算法，即MOFN算法。该算法先用标准聚类算法合并KBANN中权值接近的连接以创建等价类，并将每个等价类的权值设为该组连接权的平均值，然后去掉那些对结果影响不大的等价类，在不调整权值的前提下对神经网络重新进行训练，最后直接根据网络结构和权值抽取出形如式28的MOFN规则。
if (M of N antecedents are true) then … (28)
MOFN规则形式不仅减少了抽取的规则数，还使得规则集比较简单易懂。另外，由于对连接进行了聚类，也使得规则搜索空间大为减少，从而较大地降低了规则抽取的时间开销。图2给出了一个典型的抽取MOFN规则的例子：
值得注意的是，在普通的神经网络中，由于连接权大多发散地分布在权值空间中，不象在KBANN中那样容易聚为等价类，因此一般来说，MOFN算法仅适用于KBANN。1993年，Craven和Shavlik [CS93] 提出，可以用柔性权共享（soft weight-sharing）方法 [NH92] 训练网络，然后用MOFN算法抽取规则。由于柔性权共享方法会促进连接权在训练中聚类，这样就使得MOFN算法的适用范围有所扩大。但是，由于MOFN算法对神经网络的结构有一些很强的要求，例如要求神经元激活值为二值模式、每个神经元表示唯一的概念、网络输入为离散值等，这使其适用范围始终受到很大的限制。
1993年，Sestito和Dillon [SD93] 提出了一种利用抑制性单层网络为神经网络中每个输出神经元抽取相应规则的算法。他们首先将网络的输出神经元作为附加输入神经元，利用扩展后的输入神经元、初始的输出神经元以及一个隐含层建立多层网络，用BP算法对其进行训练。训练完成之后，对所有输入和附加输入神经元，根据式29计算它们之间的误差平方和SSE，其中a为输入神经元，b为附加输入神经元（即输出神经元），waj和wbj分别为神经元a、b与隐层神经元j之间的连接权。SSE实际上度量了输入神经元a和输出神经元b之间的接近程度，SSEab越小则说明输入a对输出b的作用越大。
(29)
然后，利用扩展后的输入神经元以及初始的输出神经元建立一个单层抑制性网络，用Hebb规则确定神经元间的抑制性连接权Weightab，该权值实际上度量了输入神经元与输出神经元之间的相关度，值越小则说明某输入与某输出的关系越密切。在此基础上，对每一个输入神经元a和输出神经元b，根据式30计算其SSE和抑制性连接权Weightab的积。最后，将乘积Productab从大到小排序。对某个特定的输出，先找出乘积表中的截断点，即乘积表中的某一个位置，从该处断开的两个乘积在数值上至少相差两到三倍。然后以截断点以下的所有输入属性为规则前件，以输出为规则后件构造出合取规则。
(30)
Sestito和Dillon的算法对前馈网络相当有效，可以抽取出较好的规则。但由于在规则抽取过程中需要额外地构造并训练两个神经网络，其时间代价相当高。
1995年，Setiono和Liu [SL95] 提出了一种从神经网络中抽取规则的三阶段算法。他们首先用权衰减（weight-decay）方法训练一个BP网络，该网络中较大的连接权反映了较重要的连接；然后对网络进行修剪，在预测精度不变的情况下删掉不重要的连接；最后通过对隐层神经元的激活值进行离散化，进而为每个输出结点抽取相应的规则。该算法中离散化隐层神经元激活值的处理别具一格，这使其摆脱了很多规则抽取方法对激活值类型的限制，可以处理非二值模式的激活值。但是，由于无法保证网络的功能在离散化处理和修剪处理前后的一致性，因此该算法抽取的规则在保真度上有一定的缺陷。
1997年，Setiono [Set97] 提出了一种适用于三层前馈网络的通用型规则抽取算法。该算法不仅使用了Setiono和Liu [SL95] 设计的激活值离散化技术，还使用了一种独特的隐层神经元分裂技术，即当某个隐层神经元的输入连接数较多时，将其分裂为若干个输出神经元，并通过引入新的隐层神经元来构建子网络，从而递归地进行规则抽取处理。该算法可以产生相当精确的规则，但由于要训练多个子网络，其时间开销相当大。另一方面，该算法只适用于规模较小的网络，这是因为在输入神经元较多时，待分裂的隐层神经元数以及递归分裂的次数极大。
1997年，Setiono和Liu [SL97] 还提出了一种从三层前馈网络中抽取倾斜规则（oblique rule）的算法NeuroLinear。与普通的规则相比，倾斜规则通常可以更好地表示边界与属性空间轴非垂直的判定域，从而较大地减少规则前件数。NeuroLinear抽取的规则前件形式为：
(31)
NeuroLinear首先通过修剪网络去除冗余连接，并对隐层神经元激活值进行聚类以降低组合复杂度。然后用隐层神经元聚类后的离散激活值表示输出层神经元的输出，用输入层神经元的激活值表示隐层神经元聚类后的离散激活值，从而得到层次形式的规则。再对这些规则进行合并，从而得到直接用输入属性表示网络输出的规则。
2000年，Setiono[Set00]又最新提出了快速规则抽取算法。所谓快速是相对于其他的基于结构的规则抽取算法而言，一般地说，为了避免组合爆炸的问题，大多数规则抽取算法都要对原神经网络进行剪枝操作，去掉一些不重要的连接，但为了保证神经网络的精度，需要对剪枝后的神经网络进行再训练，这增加了算法的开销，降低了算法的效率。为此，Setiono提出了FERNN算法，该算法无需对神经网络进行多次训练，可以抽取MOFN规则或是DNF规则。
B. 基于性能分析的方法
与基于结构分析的方法不同，基于性能分析的神经网络规则抽取方法并不对神经网络结构进行分析和搜索，而是把神经网络作为一个整体来处理，这类方法更注重的是抽取出的规则在功能上对网络的重现能力，即产生一组可以替代原网络的规则。
1990年，Saito和Nakano [SN90] 提出了RN算法。该算法先从少数正例中抽取规则，然后根据未被覆盖的正例扩展规则，根据覆盖的反例缩减规则，直到规则覆盖了所有的正例，并且不覆盖任何反例为止。抽取的规则表示为析合范式形式。虽然该算法并不对网络结构进行分析和搜索，但其要搜索正、反例空间，因此该算法在示例空间较大时将面临组合爆炸问题。
1994年，Craven和Shavlik [CS94] 为神经网络规则抽取任务下了一个定义：给定一个训练好的神经网络以及用于其训练的训练集，为网络产生一个简洁而精确的符号描述。显然，该定义来自于性能分析的角度。在该定义的基础上，Craven和Shavlik将规则抽取视为一个目标概念为网络计算功能的学习任务，提出了一种基于学习的规则抽取算法。该算法使用了两个外部调用（Oracle），其中EXAMPLES的作用是为规则学习算法产生训练例，SUBSET的作用则是判断被某个规则覆盖的示例是否都属于某个指定类。算法为每个分类产生各自的DNF表达式，它反复地通过EXAMPLES产生训练例，如果某训练例没有被当前该类的DNF表达式覆盖，则新规则被初始化为该训练例所有属性值的合取，然后反复尝试去掉该规则的一些前件，并且调用SUBSET来判断该规则是否与网络保持一致，从而使规则得以一般化。该算法不需使用特殊的网络训练方法，也不需将隐层神经元近似为阈值单元，但其计算量较大。
1995年，Thrun [Thr95] 为前馈神经网络提出了一种基于有效区间分析（Validity Interval Analysis）的规则抽取算法。该算法的关键是为所有或部分神经元找出激活区间，即有效区间。算法通过检查有效区间集合的一致性而不断排除导致不一致的区间。Thrun描述了两种不同的操作方式，即从特殊到一般和从一般到特殊。前者是从一个随机选择的示例开始，通过不断扩大相应的有效区间，逐渐得到一般的规则；后者则是从一个未加验证的假设集开始，通过有效区间来验证假设集中的规则。利用该算法可以抽取出精度较高的规则，但其以区间形式表示的规则前件使得规则的可理解性较差。另外，由于该算法的计算开销非常大，因此其只适用于对规则进行理论验证，难以完成实际的神经网络规则抽取任务。
在 [CS94] 的基础上，1996年，Craven和Shavlik [CS96] 提出了TREPAN算法。该算法首先用训练好的神经网络对示例集进行分类，然后将该集合作为训练集提供给类似于ID2-of-3 [MP91] 的决策树学习算法，从而构造出一棵与原网络功能接近的、使用MOFN表达式作为内部划分的决策树。与 [CS94] 的算法相比，TREPAN的计算量较低，但由于决策树的可理解性不如一阶逻辑表达式 [Wu95]，TREPAN抽取出的规则的可理解性也有所降低。1997年，Craven和Shavlik [CS97a] 将TREPAN用于一个噪音时序任务，即美元–马克汇率预测，取得了比现有方法更好的效果。 | 
博客登陆
我的分类（专题）
最新日志
最新评论
留 言 板
友情链接
日志信息
[Nirvana 发表于 2004-12-27 20:34:51]
