有序决策系统的知识更新理论及其高效算法

摘要

数据挖掘的主要任务是从数据中发现有用知识。粒计算是一种新兴的知识发现范式，已经被广泛地应用到数据挖掘研究中。粗糙集理论是一种重要的粒计算理论。它的基本观点是任一粗糙概念可以被两个清晰概念刻画。这对清晰概念被称为上、下近似集。因此，近似集计算是利用粗糙集理论进行问题求解的一个关键步骤。近年来，日益复杂的数据环境（动态数据、复合数据等等）对近似集计算效率带来了巨大的挑战，加速近似集计算已经引起了许多学者的关注。
　　人们在日常生活中存在着各种各样的偏好，因此，从实际问题中抽象的信息系统往往存在具有偏好属性域的属性（在决策分析研究中，这类属性称为指标）。然而，经典粗糙集理论不能直接用来处理具有偏好属性域的信息。为此，Greco等用一个优势关系代替经典粗糙集理论中的不可区分关系，从而提出了优势关系粗糙集方法。该方法能够有效地应用于多指标分类或多指标决策分析等相关问题求解。加速优势关系粗糙集方法近似集计算有助于提高这类问题求解的效率。因此，本文以优势关系粗糙集方法为研究对象，分析动态信息系统中对象集、属性值和属性集的变化对近似集的影响，利用增量更新策略，通过局部更新过时的相关结果来避免不必要的重复计算，来实现高效地更新近似集的目的。为了便于解决涉及复合数据的多指标分类问题或多指标决策分析问题，本文基于容差关系和优势关系建立了一种新的粗糙集模型，并提出了该模型的近似集增量更新方法。为了采用并行技术实现高效地计算优势关系粗糙集方法近似集的目的，本文提出了一种适用于计算优势关系粗糙集方法近似集的并行策略，并且设计了相关的并行算法等。本文的主要研究成果如下:
　　(1)针对有序决策系统中对象集的动态变化，提出了添加（删除）一个对象时动态维护优势关系粗糙集中近似集的方法，设计了论域中添加（删除）一个对象后更新优势关系粗糙集中近似集的增量算法。实验评估反映了增量算法明显地提高了对象集变化时更新优势关系粗糙集的近似集的效率。
　　(2)针对动态信息系统中局部的属性值变化，提出了属性值变化时动态维护优势关系粗糙集中近似集的方法以及设计了相应的增量算法。采用一个数值化算例说明了属性值变化时增量更新优势关系粗糙集中近似集的可行性。通过实验评估发现属性值变化率小于一个阈值时利用增量算法更新优势关系粗糙集的近似集能够有效地减少计算时间。
　　(3)对于动态信息系统中属性集的变化，提出了同时添加（删除）多个条件属性时动态维护优势关系粗糙集方法中近似集的方法。在此基础上，设计了相应的增量算法。通过实验评估发现同时添加（删除）多个条件属性时运用增量算法更新优势关系粗糙集的近似集能够有效地提高计算效率，并且增量算法的性能与数据集的属性数和对象数密切相关。
　　(4)为了能够应用粗糙集方法对涉及多类型数据的分类问题进行求解，建立了一种基于容差和优势关系的复合粗糙集模型。同时，提出了添加（删除）多个对象时动态维护该模型近似集的方法和设计了相应的增量算法。实验验证了添加（删除）对象时更新近似集使用增量算法都能够提高计算效率。
　　(5)为了采用并行技术加速优势关系粗糙集的近似集计算，给出了优势关系粗糙集近似集的并行计算策略并设计了相应的并行算法。通过实验评估发现在多核环境下并行算法都能节约计算时间。对同一数据集采用并行算法计算优势关系粗糙集近似集时，随着核数增加，并行算法的计算时间递减。

目录

声明

摘要

符号说明

第1章 绪论

1．1 研究背景和问题提出

1．2 国内外研究现状分析

1．2．1 粒计算研究现状分析

1．2．2 粗糙集理论研究现状分析

1．3 本文的研究工作

第2章 预备知识

2．1 经典粗糙集

2．2 优势关系粗糙集及其扩展

2．2．1 优势关系粗糙集方法

2．2．2 泛化决策

2．2．3 基于in-sim-dominance关系的粗糙集方法

2．3 本章小结

第3章 对象集变化时优势关系粗糙集方法近似集动态更新研究

3．1 引言

3．2 对象集变化时优势关系粗糙集方法的近似集动态更新

3．2．1 添加一个对象时优势关系粗糙集方法近似集更新

3．2．2 删加一个对象时优势关系粗糙集方法近似集更新

3．3 算例

3．4 算法设计与分析

3．5 实验评估与分析

3．6 本章小结

第4章 属性值变化时优势关系粗糙集方法近似集动态更新研究

4．1 引言

4．2 优势矩阵

4．3 属性值变化时优势关系粗糙集方法的近似集动态更新

4．3．1 优势关系矩阵的动态变化

4．3．2 知识粒的动态更新

4．3．3 近似集的动态更新

4．4 算例

4．5 算法设计与分析

4．6 实验评估与分析

4．7 本章小结

第5章 属性集变化时优势关系粗糙集方法近似集动态更新研究

5．1 引言

5．2 属性集变化时优势关系粗糙集方法的近似集动态更新

5．2．1 添加属性时优势关系粗糙集方法近似集动态更新

5．2．2 删除属性时优势关系粗糙集方法近似集动态更新

5．3 算例

5．4 算法设计与分析

5．5 实验评估与分析

5．6 本章小结

第6章 基于容差和优势关系的复合粗糙集模型及其近似集动态更新研究

6．1 引言

6．2 一种基于容差和优势关系的复合粗糙集模型

6．3 T-D复合粗糙集模型的近似集动态更新

6．3．1 添加对象时T-D复合粗糙集模型近似集更新

6．3．2 删除对象时T-D复合粗糙集模型近似集更新

6．4 算例

6．5 算法设计与分析

6．6 实验评估与分析

6．7 本章小结

第7章 优势关系粗糙集方法近似集并行计算研究

7．1 引言

7．2 优势关系粗糙集近似集的并行计算原理

7．3 算例

7．4 并行算法和实验评估

7．4．1 计算优势关系粗糙集近似集的并行算法

7．4．2 实验评估与分析

7．5 本章小结

第8章 总结与展望

8．1 本文的主要研究工作及其成果

8．2 下一步工作展望

致谢

参考文献

攻读学位期间发表的论文

攻读博士学位期间参与的科研项目