开题报告 硕博论文 经济论文 管理论文 教育论文 医学论文 法律论文 英语论文 计算机论文 机械论文 建筑工程论文电子通信论文 理学论文 文学论文 哲学论文 农林学论文 社会学论文 政治论文 艺术论文 公文文秘
返回首页
当前位置: 主页 > 论文库 > 电子通信论文 >

基于近似骨架的不确定数据聚类算法(2)

本站业务:代发论文、代写论文、代写公文、文献翻译;保证质量、保证原创、保证通过;
联系邮箱: admin@bsdaixie.com  联系电话:15271810038  QQ:610299452

x’满足x’=x*(1+y*a) y∈[-1,1];在它的alpha*100%片段构造的不确定数据点x’满足
x’=x*(1+y*a+b) y∈[-1,1]。当然,不确定数据点还有其他的构造方法,如抽样法等。下面给
出构造不确定数据对象的UDataGen 算法的具体实现步骤:
算法:UDataGen
输入:UCI 数据集
输出:不确定数据集Udata
Begin
1. UCI 数据集读取object_num,object_size,object_dims,a,b,alpha;
2. 将1 中读取的参数以“,”分格作为不确定数据集UData 的文件名;
3. 将原点和不确定数据写入不确定数据集Udata
for(int i=0;i<object_size;i++)
3.1 将UCI 数据集的原始点前加标识并将其打乱;
3.2生成不确定数据;
for(int i=0;i<object_size * alpha;i++)
for(int j=0;j<object_dims;j++)
3.2.1.不确定数据的第j 维=x*(1+y*a + b)其中x 对应原始点在第j
维上的值,y 为[-1,1]随机数;
end for
end for
for(int k=0;k<object_size * (1-alpha);k++)
for(int j=0;j<object_dims;j++)
3.2.2.不确定数据的第j 维=x*(1+y*a)其中x:对应原始点在第k 维
上的值;y:-1 到1 之间的随机值;
end for
end for
end for
4. 返回不确定数据集UData
End
实验中,我们定义每个UObject 包含50 条URecord,每个数据集的类数目k 与原始UCI
数据库中给定k 值一致。
5. 实验分析
算法程序采用C++语言编写,开发工具为Microsoft Visual C++ 6.0,程序运行环境为:
CPU Intel Atom 双核1.7GHz/1GB/160G,操作系统是Microsoft Windows XP。
将不确定数据对象的构造作为预处理算法,生成的四个数据集仍然保留原有UCI 数据
库中的名字。
实验1 目的:ABAUDC 算法和UKMeans 算法性能测试
(1)分别使用ABAUDC 算法和UKMeans 算法对四个数据集进行聚类,对同一数据集
算法各运行20 次(用trials 表示),算法每次运行所使用的局部最优解(用bk-times 表示)取
值为50,并记录每次运行产生的聚类评估质量标准bk-counts、uk-counts 值及其平均值。
表2 平均质量标准的比较
Tab.2 Comparison with bk-counts and uk-counts
HabermanSurvival Wine Glass Soybean
counts counts counts counts
Trials bk uk bk uk bk uk bk uk
1 6811 6811 3105 3105 888 888 134 143
2 6811 6811 5324 3105 847 828 127 135
3 7649 6814 4656 3574 843 843 192 192
4 6791 5254 3105 3105 869 869 140 133
5 6101 6811 4656 3105 920 920 121 117
6 6101 6811 3105 3105 859 859 121 117
7 6867 6101 4656 3105 896 915 137 137
8 7504 6814 5324 3105 937 937 110 110
9 7488 7488 4656 3105 812 814 141 142
10 7488 7488 3105 3105 847 909 141 1 116
11 7488 6101 4656 3105 940 921 173 173
12 7488 5979 5324 3105 891 875 110 115
13 5253 6811 4656 3105 957 878 110 115
14 6101 6101 4656 3574 877 877 148 148
15 6101 6101 3464 3464 930 915 130 146
16 6101 6811 4656 3574 912 912 276 148
17 6101 6811 3105 3105 1049 901 114 119
18 6867 6101 4656 3105 926 936 131 131
19 6867 6101 3465 3105 948 937 123 129
20 6101 6811 4656 3574 862 906 128 138
Avg. 6707 6546 4249 3216 900 892 140 135
从上表可以看出,平均质量标准是可以反映算法聚类效果好坏与否的普遍情况。在20
次跌代过程中,bk-counts 取值很大程度上是大于或等于uk-counts 的取值,表格最后一行是
对20 次counts 值取平均值,它显示出无论数据集规模如何,ABAUDC 算法在四个数据集
上的聚类效果都明显优于无监督UKMeans 算法。
(2)给定参数trials=20,bk-times=40 前提下,我们对四个数据集分别调用10 次ABAUDC
算法和无监督UKMeans 算法。并记录每次算法输出的平均质量标准bk-counts 和uk-counts
的取值之比,它可以反映出两个算法的性能优劣。
图1 ABAUDC 算法和UKMeans 算法聚类效果比较
Fig.1 The comparison with ABAUDC and UKMeans
通过图1 可知,ABAUDC 算法在Wine 数据集上的聚类效果最佳,这是因为Wine 数据
集中的数据是线性可分的,且数据点的类划分本身较明显。而Haberman Survival 数据集的
聚类效果最差,即算法运行10 次中有4 次出现了bk-counts 取值小于uk-counts 的情况,即
使这样,ABAUDC 算法在大多数情况下的聚类效果还是优于UKMeans 算法的;在Glass 数
据集上,bk-counts 的值90%情况下大于uk-counts 值,而对于Soybean 数据集来说,ABAUDC
算法聚类效果虽然没有取得Wine 数据集上那么显著的提升,但他的优势也是显而易见的。
实验2 目的:验证算法所使用的局部最优解的个数对聚类效果的影响
在ABAUDC 算法中,我们设定参数bk-times 表示算法每次运行所使用的局部最优解
(Local Optimal Solution)的个数。
设定trials=20,bk-times 取值为{10,20,30,40,50,60,70,80,90,100}的条件下,
分别使用ABAUDC 算法和无监督UKMeans 算法对Soybean、Glass、Wine、Haberman Survival
四个数据集中的不确定数据对象进行聚类。
图2-5 分别是对Soybean、Glass、Wine、Haberman Survival 数据集进行实验的结果。

图2 Soybean 数据集测试结果
Fig.2 Test result of Soybean dataset
图3 Glass 数据集测试结果
Fig.3 Test result of Glass dataset
http://中国科技论文在线 www.paper.edu.cn
-8-
图4 Haberman Survival 数据集测试结果
Fig.4 Test result of Haberman Survivaldataset
图5 Wine 数据集测试结果
Fig.5 Test result of Wine dataset
综合上述四个数据集的实验结果,可以看出:(1)使用近似骨架后,ABAUDC 算法质
量普遍提高。(2)随着使用的局部最优解的个数增加,获得的近似骨架的纯度越来越大,
与此相反,应用到半监督聚类的约束的数量却在逐渐减少,从而导致了半监督聚类的优势在
不断减少。这说明存在着骨架的纯度和半监督强度平衡。(3)局部最优解个数的变化对新
算法的聚类结果虽然是有影响的,对不同的数据集而言,我们不能得到局部最优解个数的统
一标准,即确定近似骨架所使用的局部最优解个数取何值时,聚类效果最佳。
我们还发现,聚类结果有其不可预见性,对于不同数据集合,同一算法的聚类正确率可
能会大不相同;对于同一数据集合,采用不同的聚类算法,其聚类结果和效率也会有很大差
异。因此在实际应用中,应根据待聚类数据集的数据类型、聚类结构(若可得到的话)选择
相应的聚类算法,以取得最佳聚类效果。
实验3
目的:测试距离度量函数的变化对新算法的影响。
聚类过程中,相似度度量标准不同常常对聚类结果产生重大的影响,在经典k-means 算
法聚类问题上,常用的相似性度量标准都是基于欧几里德距离的。对于不确定数据的
uk-means 算法而言,也采用这种度量方式。
本实验设置参数如下:trials=20,bk-times=50,分别在四个数据上各调用ABAUDC 算
法和无监督UKMeans 算法进行聚类,与前两个实验不同的是,算法改变了聚类相似性度量,
即取欧氏距离
2 1
2
1
( )
m
ij ik jk
k
d x x
=
= Σ − 为距离度量标准,对输出的质量标准bk-counts 和
uk-counts 值及平均值比较。
表3 平均质量标准的比较
Tab. 3 Comparison with bk-counts and uk-counts
HabermanSurvival Wine Glass Soybean
counts counts counts counts
Trials bk uk bk uk bk uk bk uk
1 6867 6492 4656 3574 2045 2045 165 130
2 7501 6492 3105 3105 1533 1533 189 189
3 7370 6492 3105 3105 2278 2272 164 124
4 5104 6492 4143 3574 2193 2282 157 160
5 4242 6492 4656 3105 1815 1819 166 166
6 7261 6492 5324 3105 2817 2809 125 121
7 5922 6492 4656 3105 1708 1884 138 138
8 5753 6492 4656 3105 3055 3055 138 138
9 6709 6492 4656 3105 2018 2018 131 141
10 6101 6492 3105 3461 2140 2140 159 1 159
11 6606 5174 3105 3207 2012 1520 131 131
12 6101 6492 4656 3105 2668 2668 113 113
13 7646 6492 4656 3105 2609 2695 132 132
14 7646 6492 3105 3105 1453 1712 156 147
15 5753 6492 4656 3105 2612 1648 156 147
16 6315 6492 4656 3105 2370 2242 281 147
17 6603 6436 3105 3105 1758 1557 150 151
18 6603 6436 3105 3105 2105 2104 123 126
19 6061 6492 4656 3105 2210 2166 147 147
20 6818 6492 4656 3105 2226 1649 127 127
Avg. 6449 6420 4120 3174 2181 2090 152 141
通过对比20 次迭代后两算法的平均质量标准,我们发现,即使改变了距离度量函数,
新算法ABAUDC 的聚类准确度仍然高于无监督UKMeans 算法,也就是说我们提出的算法
框架的聚类效果没有因距离度量方法的改变更变坏。
6. 结论
不确定数据挖掘技术的研究已经成为数据挖掘领域的研究热点,目前在对不确定数据的
聚类算法主要是根据确定数据的聚类算法扩展而来的。本文将近似骨架的思想引入到不确定

------分隔线----------------------------
推荐内容