论文研究-基于商空间粒度的覆盖聚类算法.pdf

所需积分/C币:15 2019-07-22 22:48:17 303KB .PDF
0
收藏 收藏
举报

介绍了覆盖算法的基本思想,给出了商空间粒度的基本原理,提出了基于商空间粒度的覆盖聚类算法。通过实验验证了该算法的有效性和可行性,它适合处理大规模的数据样本。
第1期 严莉莉,等:基于商空间粒度的覆盖聚类算法 4 9 据专业知识和实际情况调幣确定合适的粒度,此时指的是相似本点包含九个类别。 度阈值s,最终得到最后的聚类结果。 3实验和结果分析 a)为了验证算法的可行性,本文对UcI网站上的乳腺癌 原样本点 数据库进行聚类。该数据库有699条记录。其中良性肿瘤记 图谱系图 图不同粒度下的聚类效果图 录444条,恶性肿瘤记录239条,还有16条为错误记录,即实 际需要聚类的数据样本为683条。样本共有11个属性。属性 从上述的实验结果可以看出,算法在正确性上有明显提 1为样本属国性11良性或恶性标志。因此需要聚类的属高。分析原因,本文认为: 性为2~10的这9个属性,即该数据样本为一个9维的数据 a)k-均值法对中小规模球状数据样本较适用,对孤立点聚 库。分别用传统的k-均值法和商空问粒度覆盖法对其聚类, 类比较敏感; DBSCAN法对噪声有自然的抵制作用,但由于使 得到的结果如表1所示。其中聚类结果一栏为得到的每一类用了全局参数,没有考虑密度和类别距离大小的不均匀性。这 数据的个数,括号中为恶性记录。 两种算法的参数设置,如聚类中心、期望的聚类效日等对聚类 表1对乳腺癌数据库的聚类 结果有显著的影响,因此聚类效果都不太理想。 聚类方法 聚类结果 拒识个数 误识率/% b)本文提出的商空问粒度算法建立在覆盖算法的基础 k-均值法 382(213) 13.177 上,覆盖算浤对大规模、高维的数据分类具有很好的效果6 粒度覆盖法432(251) 3.514 该算法事先无须知道要聚类的数目,而是按照距离或相似度 观察表1可以看出,通过k-均值法得出的良性记录为382值小于粒度阈值进行合并,完全根据样本属性的性质以及实际 条,恶性记录213条。它不仅有许多拒识样本,误识率也很高。需要确定聚类数口。这样就避免了参数设置对聚类结果造成 采用南空间粒度覆盖法,聚类结果为良性记录432条,恶性记的影响,更易于得到仝局最优解。算法在已知的聚类结果上计 录251条。其中良性样本错误记录6个,恶性样本错误记录18算,不需要对整个样本空间再次重新计算,在一定程度上缩短 个,误识率仅为3.514%,正确率有了明显提高。 了聚类时间,提高了聚类速度。由于引入了粒度的概念,选择 b)对文本的聚类。为了验证算法对高维数据样本聚类的不同粒度计算时,可以直观地从不同角度理解样本类内和类间 有效性,从加://w.l.ahu. edu. cn上选取了180篇文本来的物理意义,对间题有实际的指导意义。 实现聚类。这些文本由专家根据先验知识预先分成计算机、生 物数学、经济、管理、医学、教育、历史、艺术等九个大类,每类4结束语 20篇文章。对文本进行预处理,主要包括摘要、关键词、文个 分词、高频滤词、低频滤词、选择名词和主要动词作为矢量空间 本文根据覆盖算法和商空间的理论,针对大规模、高维数 的基,计算词频并计算词条文本矢量矩阵中各个元素的权据集聚类效率不高的题提出了一种基于尚空间粒度的覆盖 值,最终得到126个特征词。首先分别用k均值法、 DBSCAN聚类算法。此算法运用粒度的分析使聚类在一个非均匀粒度 法、商空间粒度覆盖法三种方法对其进行聚类,得出的实验结下进行,从不同角度对样本进行理解,具有一定的实际意义。 果如表2所示。 算法的仿真实验也表明此方法可以达到很好的聚类效果,具 表2不同聚类方法对文本的聚类 有降低计算时间复杂度、适于处理样本数较多的情况等诸多优 类方法聚类时间/s 点,具有一定的应用价值。 k-均值法 DBSCAN沄 2.6 91.3 参考文献 粒度覆盖法 2.8 9 [1]张钤,张钹,殷海风。多层前向网络的交叉覆盖设计算法[J].欹件 从表2可以看出,在聚类时间上,商空间粒度覆盖法要珞 学报,1999,10(7):737-742 多于k-均值法,它与 DBSCAN算法的时间差不多,这是因为要[2]卜东坡,白硕,李国杰聚类、分类中的粒度原理[].计算机学报, 进行两次粒度分析对结果进行调整的缘故;在聚类结果上 2002,25(8):810-816 k-均值法所得到的聚类个数是8,而 DBSCAN法和商空间粒度[3]张钱,张铃问题求解型论与应用[M],北京:清华大学出版社, 覆盖法得到9个聚类数,后者在聚类正确率上有了明显的提 1990:1-34 高,达到了96.1%。显然其结果更接近于先验知识得出的[4]赵,张燕平,张铃,等,覆盖聚类算法[安徽大学学报:自然科 结论 学版,2005,29(2):28-32 接着对同一样本选择不同的粒度进行聚类,分别取粒度 [5]王伦文.聚类的粒度分析[J].计算机工程与应用,2006,42(5) 9-31,65 (此处即d)为0.2、0.5和0.8。图2所示即原样本点以及在不 [6]张燕平提取特征规则的重复覆盖算法[J].安徽大学学报:自然 同聚类粒度下的聚类效果图。可以看出,选择合适的粒度进行 果类对结果具有很大的影响。聚类粒度较小,即聚类半径较小(71 Han J, KAMBER M. Dala mining concepts aud lech 时,样本的划分就比较细,形成的簇较多,显示的是样本点之间 L M. Beijing China Machine Press, 2001 较细微的差别;聚类粒度较大,即类半径较大时,样本的划分[8 ZHANG Yan-qig, SHTEYNBERG M, PRASAD S K,eta. Sunderra 又比较粗,形成的簇较少,展现的就是样本点间较粗的轮廓。 man granular fuzzy Web intelligence techniques for profitable data 只有选择合适的粒度才能反映样本点的真实情况,如本次实验 mining[ C]//Proc of the 12 th IEEE International Conference on Fuzzy 中取d=0.5得到的聚类结果就与预先分类结果相一致。此样 Systems.2003:1462-1464

...展开详情
试读 3P 论文研究-基于商空间粒度的覆盖聚类算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_39840588 如果觉得有用,不妨留言支持一下
2019-07-22
上传资源赚积分or赚钱
    最新推荐
    论文研究-基于商空间粒度的覆盖聚类算法.pdf 15积分/C币 立即下载
    1/3
    论文研究-基于商空间粒度的覆盖聚类算法.pdf第1页

    试读结束, 可继续阅读

    15积分/C币 立即下载 >