基于知识粒度和非矩阵方法的动态属性约简算法

对于较小数据集，当对象发生变化时，基于矩阵方法的动态属性约简算法是有效的，但是对于较大数据集，基于矩阵方法的动态属性约简算法在获取决策信息系统的属性约简时，需要耗费大量的计算机内存和计算时间而导致运行速度较慢.为了克服这个缺陷，本节提出了对象变化时基于非矩阵方法的动态属性约简算法.

3.1.2.1　对象增加时基于知识粒度和非矩阵方法的动态属性约简原理

为了便于理解下面计算知识粒度的增量更新机制，先通过一个实例解释当对象增加时基于非矩阵方法的计算决策信息系统知识粒度的增量更新原理.假设S＝（U，A＝C∪D，V，f）是给定的决策信息系统，U/C＝{X1，X2，…，Xm}.UX是增量对象集，UX/C＝{Y1，Y2，…，Ym＇}，由于在 U/C 和UX/C 之间可能存在相同的等价类，根据上面的等价类，可得：

在U∪UX/C等价类中，＝Xi∪Yi（i＝1，2，…，k）表示Xi和 Yi 是能够合并的等价类，换句话说，Xi和 Yi 中对象的属性值是一样的；另外，Xi∊U/C（i＝k+1，k+ 2，…，m）和Yi∊UX/ C（i＝k+1，k+ 2，…，m＇）是不能够合并的等价类.

例3.2 假设S＝（U，A＝C∪D，V，f）是一个决策信息系统，U＝{x1，x2，x3，x4，x5，x6，x7}，U/C＝{{x1，x3}，{x2，x4}，{x5}，{x6，x7}}；假设UX是增加的对象集，UX＝{y1，y2，y3，y4}，UX/C＝{{y1，y2}，{y3}，{y4}}.另外，{x5}和{y4}、{x2，x4}和{y3}是能够合并的等价类.则：

显然，m＝4，m＇＝3，k＝2.

定理3.7 已知决策信息系统S＝（U，A＝C∪D，V，f），U/C＝{X1，X2，…，Xm}.假设UX是增量对象集，UX/C＝{Y1，Y2，…，Ym＇}，根据上面等价类可得：

决策信息系统增加对象后条件属性的知识粒度为：

证明 由定义2.6 可得：

因为＝Xi∪Yi（i＝1，2，…，k），可得：

定理3.7 得证.

定理 3.8 已知决策信息系统S＝（U，A＝C∪D，V，f），U/C∪D＝{M1，M2，…，Mn}.假设UX是增量对象集，UX/C∪D＝{N1，N2，…，Nn＇}，根据上面等价类可得：

决策信息系统增加对象后条件属性和决策属性的知识粒度为：

证明 定理3.8 的证明过程与定理3.7 的证明过程相似，略.

定理 3.9 已知决策信息系统S＝（U，A＝C∪D，V，f），U/C＝{X1，X2，…，Xm}且U/C∪D＝{M1，M2，…，Mn}.假设UX是增量对象集，UX/C＝{Y1，Y2，…，Ym＇}且UX/C∪D＝{N1，N2，…，Nn＇}.U∪UX/C和U∪UX/C∪D分别为增加对象后的等价类.决策信息系统增加对象后决策属性D 关于条件属性C 的相对知识粒度为：

证明 由定义2.7 可得：

(www.xing528.com)

定理3.9 得证.

定理3.10 已知决策信息系统S＝（U，A＝C∪D，V，f），

假设UX是增量对象集，

U∪UX/C，U∪UX/C∪D，U∪UX/C-{a}和U∪UX/（C-{a}∪D）分别为增加对象后的等价类.∀a∊C，属性a 关于条件属性集C 相对于决策属性集D 的重要性为：

定理3.11 已知决策信息系统S＝（U，A＝C∪D，V，f），令B⊆C，

假设UX是增量对象集，

U∪UX/B，U∪UX/B∪D，U∪UX/（B∪{a}）和U∪UX/（B∪{a}∪D）分别为增加对象后的等价类.∀ a∊（C-B），属性a 关于属性集B 相对于决策属性集D 的重要性为：

3.1.2.2　对象增加时基于知识粒度和非矩阵方法的动态属性约简算法

当决策信息系统中对象增加时，根据3.1.2.1 基于非矩阵方法的计算知识粒度的增量更新原理，设计了对象增加时基于知识粒度和非矩阵方法的动态属性约简算法，具体步骤如算法3.2 所述.

下面通过实例来说明基于知识粒度和非矩阵方法的动态属性约简算法的具体过程：

例3.3 运用非动态属性约简算法计算表2-1 的属性约简为 B ={b，f}，假设UX＝{10，11，12}是增加的对象集，其中，

计算联合等价类：

计算对象添加到决策信息系统后的知识粒度为，增加数据集相对知识粒度为（D|C）＝0，因为（D|C）≠（D|B），需要不断从属性集C-B中选取最大属性重要度的属性添加到B 中.

计算决策信息系统增加对象后的属性约简，把属性 a，e 增加到约简B中，得到：

从约简B 中删除冗余属性，对象添加到决策信息系统后的属性约简为B ={b，f，a，e} .