粗糙集理论在商业数据挖掘中之应用

申请免费试用、咨询电话：400-8352-114

数据挖掘被称为数据库中的知识发现（Knowledge Discover Database，KDD）。在商业智能研究中，对业务数据密集型的大容量商业销售数据的知识挖掘，国内外均有成功案例，但受数据不完备的影响，许多数据挖掘技术在企业中无法取得实际应用。波兰学者Z.Pawlak提出的粗糙集（Rough Set）理论，近年来在知识发现等领域受到广泛关注。面对当前国内企业商业数据普遍不完备的难题，本文改进相关算法，通过粗糙集数据挖掘系统对各种商业数据进行数据预处理，消去冗余属性，抽取决策规则。

1 基于粗糙集理论的商业数据挖掘

CRISP-DM（Cross-Industry Standard Process for Data Mining）项目的实施步骤包括：商业理解、数据理解、数据准备、建模、评估和发布。具体到商业，基于CRIS-DM模型的数据挖掘处理可以细分为7个步骤：目标确定、确认数据源、数据收集、数据筛选、数据预处理、挖掘分析和结果评价。

一个完整的基于粗糙集理论的商业数据挖掘过程包括3个概念层：

（1）数据准备层包括目标确定、确认数据源、数据收集、数据筛选，目的是从数据源中抽取出正确可靠的统一格式的数据。

（2）数据预处理层包括连续属性值离散化、数据过滤、数据完备化，目的是将数据源里提取的数据转化为完备信息系统表。

（3）挖掘评价层是整个挖掘过程的核心层，包括属性约简、规则提取和结果评价。

2 关键环节算法设计

1）算法1：连续属性离散化算法

运用粗糙集理论，必须对商业业务数据库中存在的大量连续属性进行离散化，而常规离散化方法易于导致决策表相容性的降低，使提取规则的能力下降。谢宏等的《基于信息熵的粗糙集连续属性离散化算法》提出基于信息熵的粗糙集连续属性离散化算法，能保持决策表相容性，但该算法对训练数据具有过度适应性，实际应用效果不理想。本文对此算法作相应改进，增设用户控制阙值，以避免过多断点。

P为已选的断点集合，L为P所划分的等价类集合，B为候选断点的集合，决策表信息熵H的初值为H（U）。基于信息嫡的粗糙集离散化算法如下：

 其中XU为子集，其实例个数为︱X︱。

输入：U（Ai，d）；Pi＝｛φ｝（决策属性d，连续属性Ai，Ai的对应断点集合Pi）；用户控制网值t

输出：Pi

step 1：Pi＝｛φ｝；L＝｛U｝；H＝H（U）；

step 2：对 每一个c∈B，计算H（c，L）；

step 3：若 H≤min｛H（c，L）｝，则结束；

step 4：选择使H（c，L）最小的断点Cmin加到P中；

若P中断点个数≥t2，则结束，否则H＝H（c，L）；B＝B－｛c｝；

step 5：对所有X∈L，若Cmin把X划分为X1和X2，则用X1和X2替换L中的X；

step 6：如果L中各个等价类中的实例都具有相同的决策，则结束；否则转到step2。

2）算法2：数据完备化算法

在目前的商业数据挖掘中，面临比较突出的难题就是信息的不完备性。王国胤的《Rough集理论与知识获取》给出一种基于Rough集理论中数据不可分辨关系的ROUSTIDA算法，张振华、刘文齐的《一种基于粗糙集理论不完备数据的改进算法》则以决策规则独立为基本思想，对条件属性和决策属J性区别对待，给出了一种ROUSTIDA改进算法，朱小飞的《一种基于量化容差关系的不完备数据分析方法》提出的VTRIDA算法，在具有缺失值的对象容差类中，找出与该对象最相似且补缺能力较强的对象进行缺失值补充，从而提高决策规则的支持度。本文采用《一种基于量化容差关系的不完备数据分析方法》中的VTRIDA算法。

MASi为对象xi的缺失属性集、MOS为信息系统S的缺失对象集。

输入：不完备信息系统S0＝＜U0，A，V，f0＞

输出：完备信息系统Sr＝＜Ur，A，V，fr＞

step 1：计算初始扩充的量化容差关系矩阵T0，MASi0和MOS0；令r＝0。

step 2：①产生Sr＋1。如果xi无缺失值，则使对象xir＋1与对象xi的属性值均相同：ak（xir＋1）＝ak（xir），k＝1，2，…，m；否则根据扩充的量化容差关系矩阵Tr，找到一个与xi最相似的xj，用其中的属性值对xi中的缺失属性值进行补齐。②如果Sr＋1＝Sr，结束循环，转step3；否则先计算Tr＋1，MASir＋1和MOSr＋1；然后r＝r＋1；最后转step2。

Step 3：如果还有缺失值，则选用其它代价较大的算法（例如直接删除缺失数据对象）。

3）算法3：属性约简算法

属性约简是在保持决策信息系统的分类和决策能力不变的前提下，根据属性之间的依赖关系γ、属性重要度SGF等，找出一个最佳约简集，删除不相关或不重要的属性。

输入：具有条件属性集C和决策属性集D的相容决策信息系统S。

输出：最佳约简集

step 1：计算决策信息系统S的核心集CORE；

step 2：REDU＝CORE；C＇＝C－REDU；

step 3：计算γ（REDU，D）和γ（C，D）；

step 4：if γ（REDU，D）≠γ（C，D）then选择属性α∈C＇，使

SGF（α，REDU，D）＝max（SGF（αi，REDU，D））αi∈C＇，（i＝1，2，…，m）；

REDUR＝REDU∩｛α｝，C＇＝C＇｛α｝；计算新的γ（REDU，D），else转step5。

step 5：︱REDU︱→N；

step 6：for（I＝0 to N－1）｛if（αi不属于CORE）REDU＝REDU－｛αi｝；计算γ（REDU，D）；if（γ（REDU，D）≠γ（C，D）REDU＝REDU∩｛αi｝）｝

4）算法4：规则提取算法

输入：最佳约简集S（C，D），其中C是条件属性集，D是决策属性集。

输出：决策规则集T

step 1：T＝｛φ｝，n＝︱S︱

step 2：for（I＝0，I＜n，I＋＋）｛S中每个条件属性的属性值对，形成规则前件（IF部分）的一个合取项Ci；每个决策属性的属性值对，形成规则后件（THEN部分）的一个合取项从Di ti＝if Ci then Di｝

step 3：简 化、合并决策规则集T