粗糙集理论最小属性约简算法MATLAB实现

资 源 简 介

本项目利用粗糙集理论（Rough Set Theory）的核心算法，针对包含条件属性和决策属性的信息系统（决策表）进行最小属性约简。功能涵盖了计算属性的不可分辨关系、下近似集、正域以及属性重要度。算法通过构建分辨矩阵（Discernibility Matrix）或利用依赖度函数，系统地检测并删除冗余属性，旨在寻找基数最小的属性子集（Minimum Reduct），该子集在保持原系统分类能力（即决策分类质量）不变的前提下，实现了维度的最大化缩减。该代码对于理解粗糙集数学原理以及应用于数据挖掘预处理、特征选择和模式识别领域具有重要的参考价值，能够有效解决高维数据的特征冗余问题。

详 情 说 明

基于粗糙集理论的最小属性约简 MATLAB 实现

项目简介

本项目是一个基于 MATLAB 开发的算法实现，专注于利用粗糙集理论 (Rough Set Theory) 对决策表信息系统进行最小属性约简 (Minimum Attribute Reduction)。

在数据挖掘和机器学习预处理阶段，高维数据往往包含大量冗余或无关的特征，这会降低模型的训练效率和分类精度。粗糙集理论提供了一种无需先验知识（如概率分布）的数学工具，能够客观地从数据中发现属性间的依赖关系。本项目通过构建分辨矩阵和计算属性依赖度，提取出能够保持原系统决策分类能力不变的最小特征子集（Reduct）。

功能特性

本项目完全基于提供的 main.m 源码实现，具备以下核心功能：

• 决策表数据处理：能够处理包含条件属性和决策属性的离散化数据决策表（目前通过代码内置矩阵初始化）。
• 依赖度计算：实现了粗糙集中的核心概念——依赖度 $gamma(C, D)$ 的计算，用于衡量条件属性集对决策属性的分类近似质量。
• 核属性 (Core) 提取：自动识别系统中不可或缺的属性集合，即去掉该属性会导致系统分类质量下降的关键特征。
• 分辨矩阵构建：构建所有样本对的分辨矩阵 (Discernibility Matrix)，识别区分不同决策类别样本所需的属性集合。
• 贪心策略约简：结合核属性初始化和贪心算法，迭代选择区分能力最强的属性，以覆盖所有分辨矩阵中的非空项。
• 冗余检验 (Backward Elimination)：在贪心算法之后，通过后向剔除策略进一步检测并移除多余属性，确保最终结果满足“最小化”要求。
• 属性重要度分析：计算每个条件属性的独立重要度（Significance），即该属性对系统依赖度的贡献值。
• 结果可视化：生成属性重要度的柱状图，以及最终约简结果的掩码图，直观展示特征选择结果。

系统要求

• MATLAB R2016b 或更高版本
• 无需任何第三方工具箱，仅使用 MATLAB 基础函数库。

使用方法

1. 准备环境：确保计算机已安装 MATLAB 软件。
2. 运行程序：

* 将 main.m 文件放置在 MATLAB 的工作路径中。 * 在 MATLAB 命令窗口输入 main 并回车，或直接点击编辑器中的“运行”按钮。

1. 观察结果：

* 命令行输出：程序将依次打印样本数量、原始依赖度、检测到的核属性、最终的最小约简集合以及约简后的数据集预览。 * 图形窗口：弹出一个图形窗口，包含两个子图： * 上方子图展示各属性的重要度，并特别标记核属性。 * 下方子图展示最终特征选择的掩码矩阵（绿色代表保留，灰色代表剔除）。

算法实现细节与逻辑

代码主要逻辑流程如下：

1. 数据初始化

程序内部硬编码了一个经典的 12 样本、6 条件属性、1 决策属性的离散数据集。该部分负责分离条件属性矩阵 $X$ 和决策属性向量 $y$，并初始化相关索引。

2. 计算原始依赖度

调用辅助函数计算全条件属性集对决策属性的依赖度 $gamma_{total}$。如果依赖度为 0，程序将终止，表明属性间完全独立。

3. 核属性 (Core) 计算

算法遍历每一个条件属性，将其临时从属性集中移除，并重新计算剩余属性集的依赖度。如果移除某属性导致依赖度下降（$gamma_{temp} < gamma_{total}$），则判定该属性为核属性。核属性是任何约简集合的必要组成部分。

4. 最小约简计算 (核心逻辑)

这是本项目最关键的部分，采用分辨矩阵 (Discernibility Matrix) 结合贪心策略：

• 构建分辨矩阵：生成一个 $N times N$ 的单元数组。对于任意两个样本 $i$ 和 $j$，如果它们的决策属性值不同，则记录下所有在条件属性上值也不同的属性索引。这代表了如果要区分这两个样本，必须保留这些属性中的至少一个。
• 初始化约简集：将计算出的核属性直接加入初始约简集合 $Reduct$。
• 贪心迭代：

1. 找出所有尚未被当前 $Reduct$ 区分的样本对（即分辨矩阵中非空，且其属性集与 $Reduct$ 无交集的项）。 2. 统计剩余候选属性在这些未覆盖项中出现的频率。 3. 选择出现频率最高（区分能力最强）的属性加入 $Reduct$。 4. 更新未覆盖样本对列表，重复直至所有需要区分的样本对都被覆盖。

5. 冗余检验 (后向剔除)

由于贪心算法可能引入局部最优但非全局必须的属性，代码最后执行一次后向检查。依次尝试移除约简集合中的非核属性，验证移除后依赖度是否保持不变。如果依赖度无损失（误差小于 $1e-10$），则永久移除该属性，从而保证结果的“最小性”。

6. 可视化

• 重要度柱状图：计算公式为 $Sig(a) = gamma(C, D) - gamma(C-{a}, D)$，直观反映每个属性对分类系统的贡献。
• 结果掩码：使用 imagesc 绘制特征选择结果，便于快速查看保留了哪些特征。

关键函数说明

以下是对 main.m 中包含的函数功能的具体分析：

main (主函数)

控制整个程序的执行流。负责数据的定义、逻辑控制、循环迭代、结果输出和绘图调用。它不仅是程序的入口，还直接在脚本内部实现了基于分辨矩阵的贪心搜索逻辑。

calculate_dependency (辅助函数)

功能：计算给定条件属性子集对决策属性的依赖度 $gamma$。 逻辑：

1. 计算决策属性产生的等价类划分 $U/D$。
2. 计算条件属性子集产生的等价类划分 $U/C$。
3. 计算正域 (Positive Region)：遍历 $U/C$ 中的每个等价类 $X$，检查 $X$ 是否完全包含于 $U/D$ 中的某个等价类 $Y$。如果是，则 $X$ 中的样本属于正域。
4. $gamma = frac{|POS_C(D)|}{|U|}$，即正域内样本数占总样本数的比例。

compute_equivalence_classes (辅助函数)

功能：根据输入的数据子集，将样本划分为不可分辨的等价类。 逻辑：利用 MATLAB 的 unique 函数处理矩阵行，找出具有相同属性值的样本索引，返回这些索引构成的集合列表。这是粗糙集运算的基础步骤。