模糊概念格构建及算法解析

渐进式构造模糊概念格就是在给定原始模糊形式背景K＝(U，A，R～)所对应的原始概念格L以及新增对象x∗的情况下，求解形式背景K＝(X∪{x∗}，A，R～)所对应的模糊概念格L∗。在渐进式生成模糊概念格的求解过程中，要解决的问题主要有三个：①所有新节点的生成；②避免已有格节点的重复生成；③边的更新。为了有效地解决上述三个问题，对于原有模糊概念格中的每个节点，根据它和新增对象的内涵描述之间的关系，可以定义它们的不同类型：不变节点、更新节点、产生子格节点和新生格节点(R.Godin，1995；谢志鹏，2001)。

1.基本思想

Godin最先提出了渐进式算法，他认为在四类节点中找出所有的产生子格节点是渐进式算法中生成所有新生格节点的关键。在模糊概念格的构建过程中，不同的产生子格节点所对应的新生格节点是互不相同的，因此必须在算法中处理这个问题。下面对模糊概念格构建的基本思想进行说明。

根据模糊形式背景的对象和属性初始化一个仅有顶节点和底节点的模糊概念格。在模糊形式背景中取出一个对象定义为新增节点，如果它不是已有节点内涵的子集，则将节点的内涵和外延加入模糊概念格，计算模糊参数E和δ的中间结果kd、hd。继续扫描模糊概念格中的所有节点，找出所有内涵小于或等于新增对象内涵的节点，则该节点为更新节点，对每个更新节点的内涵和外延进行更新，但是边不更新，更新E和δ的中间结果kd、hd。如果格中已有节点与新增节点的内涵交集与格中任意节点的内涵不等，则在这样的节点中取外延最大的一个，称之为产生子节点，将每个产生子节点与新增节点一起作为新生成节点加入到模糊概念格中。如果格中存在新生成节点的更新节点，则对这些节点进行更新，否则加入新生成节点到模糊概念格中，并连接新生成节点到它的子节点和父节点，更新E和δ的中间结果kd、hd，直到所有的对象加入格中。对已完成构造的模糊概念格中的每个节点，计算模糊参数E和δ。

在模糊形式背景中使用渐进式构建概念格也可以先初始化一个空的模糊概念格。在将所有的对象加入格后采用下面的方式形成顶节点和底节点(也称为根节点)来搜索模糊概念格中所有没有子节点的节点，如果这样的节点只有一个则将其定义为底节点，如果有多个则生成底节点并加入到模糊概念格中，增加这些点到底节点的边。搜索模糊概念格中所有没有父节点的节点，如果这样的节点只有一个则将其定义为顶节点，如果有多个则生成顶节点并加入到模糊概念格中，增加顶节点到这些点的边。

2.算法描述

基于上述算法思想，首先对数据库中的数据进行提取并做数据预处理形成模糊背景，对应每个属性确定阈值φdj(0≤φdj≤1)，通过概念定标或逻辑定标，将多值背景转换为单值背景，采用算法3-1来处理。下面用伪码的方式介绍算法3-1。

算法3-1：模糊概念格的构造。输入经过预处理的记录，构成单值模糊形式背景T。

BEGIN(www.xing528.com)

确定阈值φdj(0≤φdj≤1)

C.larernum＝0，C.Ext_count＝0，C.Intension＝所有项目集合，C.y＝yStart；//构建最低层节点

将C加入到模糊概念格CLLattice中

C.layernum＝l，C.Ext_count＝0，C.Intension＝Φ，C.y＝yStart＋DeltaY；//构建最高层节点

将C加入到模糊概念格CLLattice中

FOR输入的每条记录DO

算法中，定义y方向上的起始坐标为yStart；相邻层之间的y方向上的间隔为DeltaY；为了便于构建父子节点之间的联系，VertexID用来记录节点的编号(标识码)；layernum用于记录某一节点的层号，进一步也可用于计算y坐标；定义了用于记录节点的内涵集的数组Intension；定义了用于记录外延的基数的整型变量Ext_count；用于记录该模糊概念节点的子节点标识码和父节点标识码的两个动态数组SonVertexIDs和ParVertexID；定义了变量x和y用于记录坐标的函数；定义了两个结构体对象：CLStructureVertex用于记录从数据库中读取的记录的数据，CLStructureVertexNew用于记录从数据库中读取的记录数据与模糊概念格中的某个节点相交所产生的新的节点；定义了用于记录整个概念格的动态数组CLLatlice。

与传统的概念格构造算法比较，该算法的优势主要表现在可以直接用模糊参数E和δ来提取规则，也可以通过对记录节点的层号来生成Hasse图。