基于粗糙集理论的模糊C-means高维数据聚类算法

朱付保， 徐显景， 白庆春， 朱颢东

(郑州轻工业学院 计算机与通信工程学院， 郑州 450002)



基于粗糙集理论的模糊C-means高维数据聚类算法

朱付保， 徐显景， 白庆春， 朱颢东*

(郑州轻工业学院 计算机与通信工程学院， 郑州 450002)

模糊C-means算法是一种重要的聚类分析算法，但是在数据维数较高的情况下，该算法计算量急剧上升从而导致其效率较低.针对这一问题，提出了一种基于粗糙集理论的模糊C-means高维数据聚类算法，该算法在传统模糊C-means算法的基础上引入了粗糙集属性约简的理念，通过对数据集属性的约简，提取出对分类影响较大的属性集而摒弃与分类无关的属性，进而在聚类过程中只计算属性约简结果集中的属性，从而减少聚类过程的工作量、提高聚类效率.理论分析和实验结果表明，该算法在处理高维数据时较高效.

粗糙集； 模糊C均值； 高维数据； 聚类

聚类分析是当前数据挖掘和知识发现的一个重要手段，聚类分析的目的是将数据库中的实体对象划分为由类似对象组成的多个类，使得同一类中的对象具有最大的相似度，不同类中的对象具有最大的相异度.模糊C-means算法是一种常用的聚类分析方法，它被应用于诸多领域并被广泛关注[1-4].模糊C-means算法虽然在处理低维数据方面是有效的，但是由于在每次迭代的过程中都要对整个数据集进行操作，因此对于复杂的高维数据其执行起来效率较低[5].在高度信息化的今天，我们所面对和掌握的数据越来越复杂，数据的维度也越来越高[6]，因此对高维数据聚类执行效率不理想的问题亟待解决.在高维数据诸多的属性中，各个属性对于知识发掘的重要程度是不相同的，其中一部分属性起到了决定性作用，但对于另外一部分属性而言，他们对于分类能力是多余的.粗糙集理论[7]提出了有关属性约简[8-11]的概念，其目的是在保留基本属性及其对各对象分类能力不变的前提下，将那些重复的、多余的属性以及属性值予以删除，从而实现对属性的精简和提炼.对于高维数据而言，属性约简是一项很有意义且有必要的工作，通过对数据库的属性约简可以为数据挖掘和知识发现减少工作量[12-13].同时还能够将那些对目标知识发掘而言无关紧要的属性排除在外，避免这些无关的属性扰乱挖掘的结果.

本文针对模糊C-means算法在处理高维数据时执行效率较低的问题，提出了基于粗糙集理论的模糊C-means高维数据聚类算法.实验表明，在处理高维数据时，该算法在保证聚类效果的基础上，还能够有效提高聚类效率.

1 模糊C-means算法(FCM)基本原理

设样本集合X={x1，x2，…，xn}⊂RD，通过最小化目标函数：

(1)

其中，C表示该样本集合要划分的类别个数，dik=‖vi-xk‖表示样本集合中第k个样本数据到第i个聚类中心的欧几里得距离，m∈[1，+∞)是表示模糊程度的一个加权指数，μik表示第k个样本对象对第i个类的隶属度函数，其满足：

(2)

具体算法如下：

1)确定聚类数目C，同时初始化聚类中心Vi和加权指数m.

2)对第t次迭代，根据当前的聚类中心，用公式

计算出新的隶属度函数；用公式

计算出新的聚类中心.

2 粗糙集理论

粗糙集理论是一种分析、研究不确定及数据不完整或不精确的知识分析方法[14].对于不精确概念，粗糙集用上近似和下近似这一对精确的概念来予以表示.粗糙集理论的主要思想是在保持分类能力不变的情况下，通过对属性的约简导出问题的决策或分类规则[15-17].

2.1 知识表达系统

知识表达系统S可以表示为一个有序的四元组S={U，A，V，F}，其中U={x1，x2，…，xn}是论域，是全体样本的一个非空有限集合.A=C∪D是属性的非空有限集合，且C∩D=φ，C→D，C为条件属性集合，D为决策属性集合.V为属性值的集合，Va表示属性a的取值范围，a∈A.f是一个信息函数，f:U×A→V，用于确定每一个样本对象属性值，即∀a∈A，x∈U，fa(x) ∈Va.

2.2 不可分辨关系

两个对象的不可分辨关系也被称作等价关系，指的是两个对象能够被完全相同的属性所描述.对任意属性子集B⊆A，如果对象xi，xj∈U，∀a∈B当且仅当f(xi，a)=f(xj，a)时，xi与xj是不可分辨关系，记作Ind(B).Ind(B)是样本集合U上的等价关系，它是属性子集B对样本集合U的一个划分.

2.3 知识库和上、下近似集

1)在粗糙集理论中，由不可分辨的对象所组成的样本子集X(X⊆U)表示的是U中的一个概念，同时概念的族集表示的是U中的知识，则样本集合U上的知识库表现为U上的分类族.假设U为非空有限集合，A是U上的等价关系集合，则知识库可定义为K={U，A}.

2)上、下近似集

设特征集R，样本子集X⊆U，满足：

R-(X)={x∈U，[x]R∩X≠φ}，

R-(X)={x∈U，[x]R⊆X}，

其中，[x]R表示的是关于所有知识R的基本集合中，包含x样本对象的集合.分别称R-(X)和R-(X)为样本子集X的R上近似集和R下近似集.R-(X)判断的是基于特征集R论域U中可能属于集合X的元素所组成的集合，R-(X)判断的是基于特征集R论域U中肯定属于集合X的元素所组成的集合.

2.4 属性约简

属性约简其主要目的是确保知识在分类能力基本不变的前提下，去除掉冗余的或不重要的条件属性.假定A是一个等价关系族，a∈A，当Ind(A)=Ind(A-{a})，那么条件属性a被认为是可以省略的，否则a不可被省略.当∀a∈A都不能被省略时，A可被称作是独立的.假设B⊂A，若B是独立的并且Ind(B)=Ind(A)，那么可以称B为A的一个约简.

2.5 区分矩阵

区分矩阵的定义：设U={x1，x2，…，xn}为论域，fa(xi)为对象xi在属性a上的取值，C为条件属性集，D为决策属性集，属性集合A=C∪D.则区分矩阵[Mij]n×n的定义如下：

(3)

由上式可知，Mij表示的是能够区分样本对象xi和xj的所有属性的集合，当xi与xj同属于一个决策类时Mij的取值为空.同时区分矩阵是一个card(U)×card(U)的对称方阵，因此在进行运算时只需考虑区分矩阵的上三角或下三角即可.

核属性就是区分矩阵中所有单个属性元素组成的集合，是进行决策或划分时不可或缺的属性，核属性记作：

(4)

3 高维数据属性约简模型

初始化决策表记作T={U，R，C，D}，C={c1，c2，…，cm}是条件属性集，D={d}是决策属性集，R=C∪D，属性集C的约简结果集记作Reduce.

模型输入数据：决策表T；

模型输出数据：约简结果集Reduce.

定义1Q和R为样本集合U上的等价关系，Q的R正域记作：PosR(Q)=∪R_(Q)，PosR(Q)是论域U中所有根据分类Ind(R)所表达的知识可以准确划分到分类Ind(Q)中的对象的集合.设∀r∈R，若PosR(Q)=PosR-{r}(Q)，则认为属性r是可去除的.

定义2属性的区分度指的是属性对于对象分类的影响程度，区分度越大说明对于对象的影响力越大，反之说明影响力较小，属性的区分度用属性在区分矩阵各元素中的出现频率来标识.设属性a∈A，则属性a的区分度可定义为：

(5)

根据模糊集理论的相关概念，首先生成有关决策表T的区分矩阵[Mij]m×n，进而从区分矩阵中选择元素值为单一属性的元素组成核属性集Core(A)，如果

(6)

则令属性约简结果集Reduce=Core(A)；如果不等，根据属性区分度的定义，求出A-Core(A)中区分度最大的属性加入到Core(A)中，直到两者相等为止；令属性约简结果集Reduce=Core(A)，输出Reduce.

4 基于粗糙集理论的模糊C-means高维数据聚类算法

4.1 算法核心思想

4.2 算法描述

通过对高维数据属性约简模型和算法核心思想的定义说明，基于粗糙集理论的FCM聚类算法具体描述如下：

初始化数据集X={x1，x2，…，xn}，∀xi∈RD，设置聚类中心数目C和阈值ε，初始化各样本到C个聚类中心的隶属度矩阵U(0)；O(|n|*|D|+|n2|+|n|*|C|.

1)依据数据集X生成区分矩阵[Mij]m×n；

2)求属性约简结果集Reduce；

3)依据属性约简结果集Reduce和当前聚类中心V计算新的隶属度矩阵U(t)，t++；

4)依据当前隶属度矩阵更新各聚类中心，t++；

4.3 时空复杂度分析

时间复杂度分析：步骤1.中计算区分矩阵[Mij]的时间复杂度为O(D*n2)；步骤2求属性约简结果集Reduce的时间复杂度是O(n2/2)；步骤3计算隶属度矩阵U(t)的时间复杂度是O(|Reduce|·|n|·|C|)；步骤4更新各聚类中心的时间复杂度是O(|n2|·|C|+|n|·|C|)；步骤5的时间复杂度是O(|t|·(|Reduce|·|n|·|C|))+O(|t|·(|n2|·|C|+|n|·|C|))；因此本文算法的时间复杂度为O(|t|·|n2|·|C|).空间复杂度分析：用于存储初始化数据集合X的空间复杂度为O(|n|·|D|)；求取区分矩阵[Mij]的空间复杂度为O(|n2|)；求取隶属度矩阵U(t)的空间复杂度为O(|C|·|n|)；因此本文算法的空间复杂度为O(|n2|).

5 实验与分析

为了验证本文算法的有效性，算法使用Matlab实现，实验的运行环境：2 GB内存；250 GB硬盘；Microsoft Windows XP操作系统.测试数据是从加州大学提供的机器学习数据库UCI上下载的5个数据集，这5个数据集分别是：Musk(Version 2)数据集、ISOLET数据集、Ionosphere数据集、Dresses_Attribute_Sales数据集和Tic_Tac_Toe数据集，各数据集的详细信息如表1所示.

表1 实验数据Tab.1 Experimental data

本次实验中设计了一个对比实验，将本文所提出的算法与传统的模糊C-means算法进行对比，性能评估主要从算法的执行效率和聚类分析结果的精度两方面进行衡量，其中执行效率主要考虑两种算法对同一数据集在同一实验环境下的执行时间，聚类分析结果的精度则主要考虑聚类结果的准确率.两种算法的实验对比结果如表2所示.

表2 实验结果Tab.2 Experimental results

本文算法与传统的模糊C-means(FCM)算法相比，其主要差异在于本文所提出的算法融入了粗糙集相关理论，在对高维数据集聚类的过程中对属性进行了约简，在保证聚类能力的前提下删除无关属性，进而减少聚类过程中算法的计算量，从而提高算法执行效率.

从表2中的实验对比结果来看，对于五个实验数据集，本文所提出的算法在执行效率方面大都优于传统的FCM算法，平均可以节省大约20%～40%的执行时间，同时聚类结果的准确率也都基本与传统算法持平.对于数据集Ionosphere，本文算法的执行时间略高于传统算法，主要是由于本文算法在执行过程中属性约简也需要耗费一部分时间，对于小量的数据集而言，本文算法虽然能够减少在聚类过程中计算的工作量，但是由于数据集较小，这种工作量的减少在整个时间消耗上体现不明显；对于数据集ISOLET，本文算法不仅在执行时间上优于传统算法，而且在聚类能力方面也略高于FCM算法，由此也说明通过属性约简不仅能够找到对聚类结果起决定性作用的属性，而且还能够剔除掉那些对聚类结果造成干扰的属性.因此，对于高维数据聚类而言，通过引入粗糙集属性约简来对模糊C-means算法所做的改进是行之有效的.

6 结束语

针对模糊C-means算法在处理高维度数据集时聚类效率不高的问题，本文将粗糙集属性约简理念融入到模糊C-means算法之中，以保证在聚类能力不变的情况下，减少算法执行过程中的计算量，进而提高聚类执行效率.通过对不同数据集的测试表明，本文所提出的算法在对高维数据聚类的过程中对于保证聚类结果和降低时间消耗是行之有效的.

[1] 唐德玉， 齐德昱， 蔡先发， 等. 改进的FCM算法在网络入侵检测中的应用[J]. 计算机工程与应用， 2012， 48(6): 5-8．

[2] 范 明， 田 铮， 赵 伟. FCM型聚类算法的统一框架及其核推广[J]. 电子设计工程， 2013， 21(4): 134-136．

[3] 张思发， 刘汭祥. 一种应用分治策略改进的FCM聚类算法[J]. 计算机工程与应用， 2013， 49(22): 194-196．

[4] 柳佳雯， 梁光明， 刘任任， 等. 融合加窗色调直方图的彩色图像FCM分割算法[J]. 计算机工程与应用， 2013， 49(3): 230-232．

[5] 虞倩倩， 戴月明. 基于MapReduce的并行模糊C均值算法[J]. 计算机工程与应用， 2013， 49(14): 133-151．

[6] 贺 玲， 蔡益朝， 杨 征. 高维数据聚类方法综述[J]. 计算机应用研究， 2010， 27(1): 23-26．

[7] Pawalk Z. Rough sets[J]. International Journal of Computer and Information Science， 1982， 11(5): 341-356．

[8] She Y， He X. On the structure of the multigranulation rough set model[J]. Knowledge-Based Systems， 2012， 36(12): 81-92．

[9] He Q， Wu C， Chen D， et al. Fuzzy rough set based attribute reduction for information systems with fuzzy decisions[J]. Knowledge-Based Systems， 2011， 24(5): 689-696．

[10] Qian Y， Liang J， Pedrycz W， et al. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial Intelligence， 2010， 174(10): 597-618．

[11] 王国胤， 姚一豫， 于 洪. 粗糙集理论与应用研究综述[J]. 计算机学报， 2009， 32(7): 1230-1245．

[12] 陈 源， 曾德胜， 谢 冲. 基于聚类的属性约简方法[J]. 计算机系统应用， 2009， 18(5): 173-176．

[13] Li B， Tommy W， Chow S， et al. Analyzing rough set based attribute reductions by extension rule[J]. Neurocomputing， 2014， 123(10): 185-196．

[14] 林 山， 项 菲. 模糊决策表的一种改进的属性约简算法[J]. 计算机工程与应用， 2011， 47(26): 167-169．

[15] 黄治国， 王 端. 基于粗糙集的数据约简方法研究[J]. 计算机工程与设计， 2009， 30(18): 4284-4286．

[16] 徐 山， 杜卫锋， 闵 啸. 一种新的模糊决策表属性约简方法[J]. 计算机工程与应用， 2013， 49(18): 105-107．

[17] 王培吉， 赵玉琳， 吕剑峰. 粗糙集属性约简的方法[J]. 计算机工程与应用， 2012， 48(2): 113-115．

FuzzyC-means clustering algorithm of high-dimensional data based on rough set

ZHU Fubao， XU Xianjing， BAI Qingchun, ZHU Haodong

(School of Computer and Communication Engineering， Zhengzhou University of Light Industry， Zhengzhou 450002)

FuzzyC-means algorithm is an important clustering analysis algorithm， however， larger amount of its calculation result in its lower efficiency in the case of high dimension data. In order to overcome this problem， a fuzzyC-means clustering algorithm of high-dimensional data based on rough set was proposed. This algorithm introduces attribute reduction of rough set into traditional fuzzyC-means algorithm. It firstly extracts a dataset of important attributes and abandons some unrelated attributes， and then only calculates the important attributes to reduce the workload of the clustering process and improve the efficiency of clustering. Theoretic analysis and experimental results show that this method is more efficient on solving high-dimensional data．

rough set; fuzzyC-means; high-dimensional data; clustering

2015-01-11.

国家自然科学基金项目(61201447); 河南省科技攻关项目(122102210492); 河南省教育厅科学技术研究重点项目(13A520368、13A520367)；河南省高等学校青年骨干教师资助计划项目(2014GGJS-084);郑州轻工业学院校级青年骨干教师培养对象资助计划项目(XGGJS02)．

1000-1190(2015)04-0511-04

TP311.131< class="emphasis_bold">文献标识码： A

A

*通讯联系人. E-mail: zhuhaodong80@163.com．