论文研究-基于量化误差与分形理论的高计算效率无监督聚类研究.pdf

所需积分/C币:6 2019-07-22 22:17:38 1.91MB .PDF

已有的矢量聚类算法需学习较多的复杂数据方可获得较好的聚类效果,而对于多维的大数据性能较弱,为此提出一种基于量化误差与分形理论的高计算效率无监督聚类算法。首先,为数据集建立量化误差的参数化模型,基于数据集的空间结构获得数据集的率失真曲线;然后通过对率失真曲线的估算,获得数据空间的有效维度;最终利用分形理论,通过搜索数据集的量化模型参数获得目标数据集的最优类簇数量。实验结果表明,该量化误差参数化模型可较好地估算数据集的有效维度,同时,本算法对数值型数据集的最优类簇估算与计算效率优于已有的矢量聚类算法。
第10期 胡国生,等:基于量化误差与分形理论的高计算效率无监督聚类研究 2921 κ ernie、 Fourier,其维度范围为4~67,由此可测试本算法对高、WDBC,本文算法也获得了两个最小点M1=2与M2=5,结合上 低维度数据的性能。另外采用三个图像数据集来測试木文参述三个UCⅠ数据集的性质,木文算法估算的数据集局部最小值 数化成本函数PCF的性能,表1所示为两种数据集的简要介可成功地反映数据集的结构,将数据集分为一级类簇与二级子 绍。对于UCⅠ数据集,其类簇的数量M。为凵知值,各数据集类,本文算法估算的类簇中心与数据集的结构较为配。 的维度范围(D)为1-67,类簇数量Mc范用为I~15;对于图 参数a与类簇数量依赖于区间[I,M灬],该区间与模型参 像数据,其主颜色特征为未知值,首先使用 K-means算法进行数的计算直接相关。对于上界M,其范围应该覆盖最优的 处理,获得每个图像的主颜色特征。 类簇数量,此外,当类簇数量m等于数据点数量N时,误差W。 表1实验中使用的UCI数据集与图像数据的简妄介绍 等于0,因此本文算法的估算结果可等于0。 数据集 数据类型 D 本文建议使用几个M值来寻找目标区间中最稳定的最 真实数据 50 真实数据 小化两数值,将全局或局部最小值M。作为可行解。例如,图4 Pageblock真实数据 5473 3752 屮,对于数据集Gas,成本函数PCF对不同的M值(Mn WDBC 真实数据 10,15,20,25,30)具有不同的结果。第二个稳定的最小值为点 zernike 真实数据 000 M,=7,而该次优解为正确的类簇数量。 真实数据 2000 LenA 图像 00未未 图像 400300 Parro 768512 3.1量化误差的参数化模型实验 图3所示为测试数据集的参数化模型R-D函数。从图中 可看出,本文参数化模型较好地描述了测试数据集的量化误 差。因此可将量化误差参数化模型的参数a作为数据X的维 1520 类簇数量m 度与一致性的度量。 图4五种M下数据集Clas的PCF曲线 将本文算法与四个性能较好的矢量量化聚类算法进行比 铰,比铰各算法估算最优类簇数量的性能,结果如图5~8以及 表2所 10 Fourier:a= 7. 19 「.7 10.8 三0.7 0.6 10310 0.5 类簇数量 类簇数量m (a)UC数据集 h)图像数据集 43210 0 4321 图3UC数据集与图像数据集的率失真曲线 3.2参数化成本函数PCF 边古青14可D lris数据集 (b)Gla数据集 将本算法与已有的矢量量化聚类算法进行对比,包括文献 09 [6](ASC)、文献[7](T)、文献[8](UC)、文献[9](DC 三0.7 RDC)。使用五种算法计算测试数据集的最优类簇数量,表2 所示为不同算法佔算的最优类簇数量的结果统计。 表2各种算沄处理数据集获得的类簇数量M 区02 数集Mc UCDC-RDC本文算法 簇内数量m 簇内数量m !o、(cP2 genlock数据集 d)WDBC数据集 108 Pageblock 32 1.46 0.7 0.7 0.6 WDBC 2.5 1.37 N05 ernie 10 922*75 5 :04 1.10 7.19 0.2 0.2 1.03 468101214161820 101214161820 1.50 簇内数量m 簇内数量 1.77 数据集 注:4c为预知的类簇数量;¨*”表示该算法未成功获得结果:¨a”表示本算法率 图5各算法对LCI数据集的测试结果(对最优类簇数量的计算 失真曲线模型的参数 对于六个UCI数据集,ST算法仅获得了数据集Iris的正 3.2.1UCI数据集的实验结果 确类簇数量,算法UC与UC-HDC仅获得了 Glass数据集的正 图5所示为各矢量聚类算法对UCI数据集的最优类簇估确类簇数量。而本文算法对大多数真实数据集均可获得正 算结果统计。对于数据集 Glass与 Fourier,除了全局最小的数确的类簇数量,对于数据集 Pageblock,本文算法佔算的结果与 据点M1,本文算法乜获得了第二个局部最小点M2。例如,本真实值极为接近:Mc=5,M1=6,对于数据集 Zernike,木算法 文算法对于 Fourier与(lass数据集,不仅获得了全局最小的M1的全局最小点为M2=5,局部最小点为M3-10,而正确的类簇 =1,同时也获得了局部最小点M2(15,15,7,10)。对于数据集数量为Mc=10。 ernie数据集由手写的数字“0~9”组成其 0 计算机应用研究 第33卷 特征空间,最优的最小点M1=5可解释为: Zernike矩阵对于几于本文算法不需要学习大量的样本数据,所以计算效率最佳 个手写数字(0,3,6,8,9)的特征不敏感。囚此,若需要硏究数而DC-RDC算法需要学习较多的复杂数据,其计算效率最低。 据集 Zernike的9个特征,应该考虑成本函数PCF的次优值,可以看出本文算法对最优类簇数量的估算在准确率与时间效率 M. 上均具有一定的优势,同时本文算法可处理各种复杂情况的数 3.2.2图像数据集的实验结釆 值型数据集。本文算法通过R-D曲线模型的参数a估算数据 从图6~8可以看出,本文算法对图像数据集也可获得较集的有效维度,通过有限的计算量获得了较为准确的数据集的 好的聚类结果,而其他矢量聚类算法的性能较差。对比文献大有效维度(数据空间的结构),囚此貝有较好的聚类性能。 多基于数据空间的维度D与有效维度a相等的假设,当两者 表3各个欠量聚类算汏运行时间结朱统计 确实相等时,则上述欠量聚类算法均可获得较好的娶类结果;数据集 DC-RDC本算法 而当两者不等时,则无法获得较好的聚类结果。本文算法通过 0.05630.62330.2183.161 0.401 标准偏差(±0.041)(±0.050)(±0.041)(±0.525)(±0.093) R-D曲线模型的参数a佔算数据集的有效维度,通过有限的计 1.3683 0.476 3.647 算量获得了较为准确的数据集的有效维度(数据空间的结 枟准偏差(±0.041)(±0.137)(±0.149)(±0.0090)(±0.086) Pagehloek 0.287 5.193 1.495 0.902 构),因此具有较好的懸类性能。 标准偏差(±0.043)(±0.329)(±0.191)(±0.583)(±0.102) WDBC 0.160 3.204 0.688 3.929 0.854 标准偏差( )(±0.875)(±0.217)(±1.106)(±0.201) 枟准偏差(±0.038)(±0.667)(±0.32)(±0.898)(±0 Fourier 4.663 0.401 标准偏差(+0.041)(+0.050)(+0.041)(+0.525)(+0.03) 7.073 10.303 标准偏差(±0.041)(±0.137)(±0.179)(±0.600)(±0.086) 1538.465 标准偏差 (+0.191)(+0.583)(+0.102) 10.034 a)输入图像 标准偏差(+0.055)(+1.853)(+0.594)(+0.654)(+0.102) 0 4结束语 工0 06 本文为多维数据集的矢量聚类算法提出了新的方法,通过 04 量化误差樸型提高了计算效率,本算法并非通过复杂的数据分 析,而是基于数据集的空间结构以及对失真的数值型衡量。木 68101214 簇内数量m 文算法通过率失頁曲线模型的参数a估算数据集的有效维度, (c)种矢量秉类算法的聚类结果 通过有限的计算量获得∫较为准确的数据集的有效维度(数 图6灰度图像Icna的直方图数据1=1) 据空间的结构),因此具有较好的聚类性能。本算法在计算效 率、聚类准确率以及对各种数值型聚类问题的覆盖率方面均获 得了较好的性能。 参考文献 [Ⅰ]赵梦玲,刘红卫,刘拮辰基于谴传模拟退火算法的矢量量化码书 设计[J.数学的实践与认识,2015,45(1):209-218 L2」修驰,宋柔.基于无监督学习的专业领域分词歧义消解方法LJ」 a)输入彩色图像 (a)输入彩色图像 计算机应用,2013,33(3):780-783. [3. Ilosseininasab S, Ershadi M J. Optimization of the number of clusters lion[J]. International Journal of Advanced Manufacturing Tech- 2013,64(5-8):1049-1055 M C. An examination of ning the number of clusters in a data setL J. Psychometrika, 1985 b)个主色的量化图像M2=4) (b)10个主色的量化剂像(M1=10 50(2):159-179 L5」张晓丹,黄海燕.基于免瘕克隆算法的LVQ聚类算法砇值优化 J」.计算机科学,2013,40(6A):27-28. 口 0.7 L 6 Tasdemir K. Vector quantization based approximate spectral cluster 長0 0.5 of large datasets J. Pattern Recognition, 2012, 45(8): 3034-3044 [7 Thepade S D, Mhaske V, Kurhade V New clustering algorithm for vec tor quantization using slant transform[ C]//Proe of the 1 st Internation- 2468101214 al Conference on Emerging Trends and Applications in Compu-ter Sci- 族内数量m 簇内数量n erce.[S.1.]:IEEs,2013:161-166 (五种矢量聚类算法的聚类结果 ()种失量菜类算法的类结果[81 Breaban m, Luchian h. A unifying criterion for unsupervised cluste 图7彩色图像 Waterlilies的 图8彩色图像 Parrots的 ring and feature selection J. Pattern Recognition, 2011, 44(4) 直方图数据(D=3) 直方图数据O=3) 3.3矢量聚类算法的计算效率比较 [9 Kolesnikov A, Kauranne T Unsupervised segmentation and approxima- tion of digital curves with rate-distortion curve modeling[ J]. Pattern 将各欠量聚类算法的计算时间进行比较,结果如表3所示。 Recognition,2014,47(2):623-633

...展开详情
img

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐