论文研究-基于逐级均值聚类的信息熵的离散化算法.pdf

所需积分/C币:13 2019-07-22 22:53:11 765KB .PDF
收藏 收藏
举报

目前基于Rough集的离散化算法很难做到高效率和高识别率兼顾,针对粗糙集给出了基于逐级均值聚类的信息熵的离散化算法。首先使用改进的逐级均值聚类算法分别对单个属性的候选断点按其信息熵值进行聚类分析,生成新的规模更小的候选断点集,然后用基于信息熵的离散化算法完成断点的选取并对连续值属性进行离散化。实验结果表明,该方法在识别率相当的情况下比传统的离散化方法的时间代价更低。
3370 计算机应用研究 弃了K均值聚类算法随机选取初始中心的方法,采用了逐步0<m1<…<n=r,则候选断点可取为 增加聚类数目、均匀取相应的值作为类别屮心,逐级进行聚类 n,=(tn-1+tn)/2;m=1,2,…,na (3) 分析。该方法不仅解决了解的局部最优问题,还解决了聚类数 设XCU为子集,其实例个数为X1,决策属性为j(j= 日的问题。 ,…,r(d))的实例个数为k。因此属于集合X且属性为a的 2.3基于逐级均值聚类的信息熵的离散化算法 断点cn可以将集合X分成两个子集X和X,且有 从文献2]中可知基于信息熵的全局离散化方法的运行 (e") 时间主要消耗在从大规模的侯选断点中不断反复筛选,而最终 H(Xn=-2Aylog2Pj,P/I(ca) 得到的结果断点集规模往往却很小。例如表1中的数据集离 散化前后断点规模差别很大,如果能在保持候选断点本身的分 ∑q10:,4-r(e“) (5) 布规律的同时通过聚类分析减小候选断点集的规模,那么整个因此定义断点c针对集合X的信息熵为 离散化算法的时间代价就会大大减少。 X H(c2)=,H(X1)+u1H(X 为此,本文对部分数据集中断点的分布规律进行「硏究。 将一些数据集的单个属性的各个断点的信息熵值按其断点值 假设L={1,Y2,…,Ym}是决策表已经被选取的断点的集 升序排列,得到如图1所示的分布统计结果。从图1中得到如 合P划分得到的等价类,那么加入新的断点cP后新的信息 下统计分析结果:(a)将单个属性的断点值按升序排列,其信嫡为 息熵值的分布曲线呈近似的对称凹型;(b)信息熵值分布相似 H(e,L)=H1(c)+H2(c)+…+H3m(c) 的断点以簇的形式存在。 H(c,L)越小,说明加入此断点后将使划分的新的等类子集的 1.05 决策属性值趋于单一,因此,(c,D)体现∫断点c的重要性程 0.9 度。由此,可以得基于逐级均值聚类的信息熵离散化算法。 迴樱密嶇 0.90 0.85 0.8 基于逐级聚类的信息熵的离散化算法(聚类信息熵算法) 0.80 075 0.7 如下 0.70 06 Input:S=(U,R,v,/)and C 46810 10 15 属性的断点值 属性的断点值 Output: P and L a)i数据集一属性断点集信息熵值b)winc数据集一属性断点集信息 的分布趋势图 熵值的分布趋势图 a)用式(2)计算数据集的相容度; 1.02 b)用式(6)计算候选断点集C中每个断点的信息熵且按 0.98 1.05 信息熵的大小排序,从中选取信息熵最小的断点,将候选断点 0.96 m0.94 把慢 集分为两个部分; 0.92 画0.95 名0.9 c)用本文的RMDC算法分别将上述两个部分的候选断点 运0.86 0.85 进行聚类分析,在形成的类别中分别选取信息熵值最大的断点 0.84 0.82 10 生成新的候选断点集C,且将a中得到的最小信息熵的断点 属性的岈点值 属性的断点值 (o)glas数据集一属性断点集信息熵值(d) ecolis据集一属性断点集信息 加入到C"; 的分布趋势图 熵值的分布趋势图 d)对C"中每个断点计算H(c,L),选取使H(c,L)最小的 1.005 断点c。加到P中,在选取过程如果两断点的信息熵值相同, 60 应优先选取断点所在属性的断点总数少的断点; 证0.99 e)对所有的X∈L,如果cm将等价类X划分为X1和H2 齿098 那么,从L中去掉x,将等价类X和X2加到L中; 0.975 f)如果L中每个等价类中的实例都具有相同的决策,则结 属性的断点值 ( pima数据集一属性断点集信息熵值的分布趋势图 束;否则转到d) 图1不同数据集属性断点的信息熵值分布趋势图 g)重新计算相容度,并与a)的值进行比较,如不同,扫描 根据以上分析可得:在进行断点选取之前,可以根据断点有冲突的实例,添加相应的断点,直到相容度前后一致 的信息熵对初始断点集进行初次聚类。根据其分析特征,在进 行聚类分析之前先找到信息熵值最小的断点,该断点将断点集3算法复杂度分析 分成两个子集,再用本文提出的逐级均值聚类算法分别对这两 设决策系统中实例个数为n,条件属性个数为m,每个属 个部分进行聚类分析。 性候选断点取值个数平均为h,采用逐级均值聚类时平均迭代 设信息系统S=(U,R,V如前所述,对每一个连续型条次数为k(k<h),最坏时间复杂度为O(k2m2),基于信息熵 件属性a∈C,论域中其有限个属性值经过排序后为=的离散化算法的时间复杂度为O(km2n),因此,本算法的时 第9期 刘静,等:基于逐级均值聚类的信息熵的离散化算法 3371· 问复杂度仍为O(h2m2n)。由于经聚类后候选断点规模枚大 b)基于逐毀均值的信息熵的离散化算法能有效减小候选 减少,时间代价大幅下降,空间复杂度为h 断点规模。 c)基于逐级均值的信息熵的窝散化算法虽然时间复杂度与 4仿真实验结果及分析 基于信息熵的离散化算法相同,但经过聚类后形成的新的候选断 为了验证本文算法的有效性,从UCI数据库(hp:/ar点数目很少,因此时间代价远少于仿真实验中的其他算法。 chive.ics.mrsi.trlu/ml/ datasets.hml)中选出几组数据集进行了 表3数据集使用不同离散化 表4数据集用聚类信息熵算法 算法的执行时间/s 离散化时断点数的变化 离散化,并与贪心算法、基于信息熵的离散化算法进行了 信息熵聚类 对比实验。实验的硬件环境是:CPU为 Intel pentiumd4数据集贪心算法 类信息数据集候使 断聚类后最终 点数断点数断点数 240GHz;内存为256WB;操作系统为 Windows XP;开发平台1 为ⅤC++6.0。 wIlle 2 wine 1 263 表1散化前后断点数的对比 表2数据集基本信息 921 l16 离散化 条件 coli oli 356 55 数据样本 决策 性 austra 效据集前的断的断点 austra 1 153 点数 集数 类数 点数 人数 segment 16 795 1 05 119 1504 segment 13981 477 ITIs wartorn 768 wareform 17 078 204 18 21 17813 ecoli 336 7 7 5结束语 ausa11531819 ausua 690 14 2 本文给出了基丁逐级均值聚类的信息熵的离散化算法,并 pima 1 246 7 segement 13 981 24 wareform 1 000 40 使用U(I数据进行了仿真。该算法对K均值聚类方法进行了 wareform 17 078 15 18 segment 2310 19 改进,并与基于信息熵的离散化算法相结合,实现了连续值属 首先进行了识别率的实验仿真。实验过程分以下步骤进性的离散化。该算法在大大降低了时间代价的同时保持了与 行:a)将数据集分别用所选的方法进行离散化:b)选择基于信 典离散化算法相当的识別率,计算结果符合实际情况。 息熵算法进行属性约简,用归纳值约简算法进行值约简得到规参考文献 则,最后对所获得的知识进行测试。将每个数据集随机选取11夺谦,王珏。粗糙集理论中概念与运算的信息表示[J]。较件 50%作为训练集用于学习,利用所获得的推理规则对其余 学,1999,10(2):113-116 [2]谢宏,程浩忠,牛东晓.基于信息熵的粗糙集迕续属性离散化算 50%进行识别测试,一共进行了5次的随机抽取,取5次的均 法[冂].计算机学报,2005,28(9):1570-1574 值作为识别率。实验结果如图2~4所示。 [3 FAYYAD L M, IRANI B M. Inlerv al discrelizaliun uf continuous val 为了验证本文算法的时间代价,进行了离散化计算时间测 ued a tributes for classification leaming[C]//Proc of the 13th Inter- 试。图5和表3给出了数据集使用不同离散化算法的执行时 national Joint Conference on Artificial Intelligence. 1993: 1022-1027 间表4给出了使用本文算法对整个数据离散化过中,断点规4HD,YUxH, FENG Y F. A new discretization algorithm based on the entropy relation[C//Proe of the 5th International Conference on 模的变化情况结果。 Fuzzy Systems and Knowledge Discovery. 2008: 164-168 100 [5]白根柱,装志利,基于粗糙集理论与信息熵的属性离散化方法 [J].计算机应用研究,2008,25(6):1701-1703. k [6] WU Da-peng, HOU Yi-wei, ZHANG Ya-qin. Transporting real-time 10 video over the Intemet challenges and approaches[ J. Proceeding of segment 测试数据集 测试数据集 the IeeE,2000,88(12):1855-1875 图2正确识别率 图3错误识别率 [7 PENA J, LOZANO J, LARRANAGE P. An empirical comparison of 18000 four initialization methods for the K-means algorithm[ J. Patlern 14000 Recognition Letters, 1999. 20(10): 1027-1040 [8 FAHIM A M, SALEM A M, TORKEY F A. et al. An efficient en- 求4000 hanced K-means clustering algorithm[ J] Journal of Zhejiang Uni- 测试数据集 测试数据集 图5数据集使用不同离散化 versity: Science A.2006,7(10):1626-1633 图4拒识别率 算法的执行时间 L9」王囯胤. Rough集理论与知识获取LM」.西安:西安交通大学出版 实验结果表明 [10 NGUYEN S H, SKOWRON A. Quantization of real-valued attri )基于逐级均值的信息熵的离散化算法的识别率与仿真 butes, rough set and Boolean reasoning approaches[ C]//Proc of the 实验中的其他算法大体相当。 2nd Joint Annual Conference on Inform ation Sciences. 1995: 34-37

...展开详情
试读 4P 论文研究-基于逐级均值聚类的信息熵的离散化算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于逐级均值聚类的信息熵的离散化算法.pdf 13积分/C币 立即下载
    1/4
    论文研究-基于逐级均值聚类的信息熵的离散化算法.pdf第1页
    论文研究-基于逐级均值聚类的信息熵的离散化算法.pdf第2页

    试读已结束,剩余2页未读...

    13积分/C币 立即下载 >