渐进式算法的索引优化及改进

通过对模糊概念格渐进式算法的分析，在数据量较少时，以上算法是非常有效的，但是当数据量比较多时，特别是在土地利用这种海量数据的情况下，根据以上算法实现的程序的运行速度很慢。对已有的研究，谢志鹏(2002)认为是没有建立节点之间的索引，在进行运算的过程中需要通过依次比较所有的节点进行遍历，降低了运算效率。针对这一问题Lhouari Nourine(1999)、谢志鹏(2002)等人已经进行了很好的研究，并提出通过建立索引的方法可以提高概念格的构建速度，秦昆(2004)又在吸取前人研究的基础上对该算法进行改进。在上述研究的基础上，参考基于辞典序的索引树的构建算法，提出了模糊概念格的快速构建算法，该算法不但在格的构建过程中表现出较高的效率，而且对规则的获取也具有较大的优势，主要是减少了冗余规则的生成。算法的特点是：使用渐进式算法，在建立索引树的同时，将概念节点分层存放，并计算模糊参数E和δ以利于关联规则的获取。下面对于建立基于辞典序的索引树相关问题进行简要的解释说明，然后重点描述该算法构造模糊概念格的过程。

1.基于辞典序的模糊概念格构造

(1)索引树的生成

按照辞典中的字母顺序建立索引，用其顺序组织模糊概念节点的集合。在索引树中，每条边表示一个特征，假设两个节点之间存在父子关系，边的特征是用字母顺序中的c表示的，则称子节点是父节点的第c个子节点。每个树节点对应一个单词λ，从全体来看这个从根节点到任何一个节点所经过的边的排列都可以用一个单词λ表示。这样就可以根据内涵的情况把模糊概念格中的节点分为：有效树节点、辅助树节点和祖先节点(Lhouari Nourine，1999；谢志鹏，2002)。

根据以上原则，谢志鹏设计了构建索引树的关键函数：对新插入的节点的内涵D中的特征按照升序排列，按照从下到上的规则，从根部节点开始分析，如果对于D中根节点的第d个子节点存在，则直接将该子节点赋予节点IndexNode，并进行概念格的更新，否则产生一个新的索引树节点，并把该节点赋给IndexNode节点。

(2)索引树的遍历方式

遍历索引树及其子树的顺序是由大到小，即从上到下、从右向左，也就是说在进行遍历的时候先访问树根，再依次遍历它的所有子树，最终达到对整个概念格进行遍历的目的。从这种遍历方式来看可以有以下几个特征：

①任意一个节点的父节点总是先于该节点被访问；

②产生子节点的内涵不可能是新产生节点内涵的子集；

③对于某新生格节点，除了其产生子格节点外，其他旧节点都不可能成为其子节点；

④对新生格节点，它不可能成为其后生成的格节点的子节点。

根据以上四个特征，为了达到“由大到小，即从右到左遍历子树的顺序”，本研究提出了节点的数据结构(CCLVertex，见本章3.3.3)和索引节点堆栈数据结构(IndexNodeArray)。

在模糊概念格的构建过程还定义了索引节点的结构，可以描述为：首先定义一个索引节点的链表，在索引节点中包含是否辅助节点、索引节点的内涵和内涵集中的子项的可能取值。这样的结构可以较好地描述索引节点的内容。

(3)模糊概念格构建基本思想

对于任一树节点，如果从树根到它的路径集合是新增对象内涵的子集，则该节点被称为更新树节点。显然，如果格节点是更新节点，那么它的充分必要条件就是它所对应的树节点是更新节点。在添加新的数据项时，需要对索引树中的每一个节点进行判断，面临以下几种情况：(www.xing528.com)

①如果新加的数据属于辅助树节点，继续进行比较，不对该节点处理；

②如果该节点是更新节点，其外延基数加1；

③对于产生子格节点，第一步应该先求出样本点与候选节点内涵之间的交集；然后以该交集为内涵，在索引树中按顺序进行遍历；接下来判断内涵为该交集的节点类型，经过判断如果该节点属于辅助节点，说明原有概念格中不存在这样的节点；最后产生一个新的节点，并添加到相应的层中，确定层号并更新模糊概念格中的父子关系。

如何确定新生节点与原有节点之间的父子关系是在建格过程中的一个关键问题。对于新生节点来说，新生节点是其产生子的父节点，新生节点的父节点只可能存在于更新节点以及其他新生节点中，因此newnodes为一个层数等于最大内涵基数的临时层对象，主要用于临时存放更新节点以及新生节点。若产生子格节点记为pCandVex，新生格节点记为pCNewVex，则函数UpdataPCRelation(pCandVex，pCNewVex)可用于表示更新父子关系。

2.算法描述

根据以上原理，设计了如下基于索引树的模糊概念格生成算法。所有的原始数据存放在关系数据库中。下面详细介绍该算法：

算法3-2：基于辞典序的模糊概念格构造。输入数据库中的记录，构成模糊概念格。

BEGIN

连接已经整合的空间数据库，获取记录指针m_pRecordset。

对模糊概念格的初始化，这个过程包括三项工作：产生具有nMax层的空模糊概念格CClattece、构造顶层节点以及最底层节点。

读入记录获取样本点的内涵值(每次读入一条记录)。

在索引树节点数组IndexNodeArray中加入根节点m_pCLRootVertex。

标注m_pCLRootVertex为更新树节点。