一种基于K_means的自适应聚类算法的研究 (1)

2012年第02
期
0.引言
聚类(Clustering)是数据挖掘中的一种主要技术，是按照一定要求和规律对一组个体进行区分和分类的过程，主要目的是使的属于同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大，聚类属于无监督分类的范畴。

划分聚类(Partitioning Methods)是聚类中的重要方法，指对于一个给定包含n 个对象或元组的数据库，通过基于划分的方法由用户给定构建数据的k 个划分，每个划分表示一个簇，并且k<=n 。

1.K-means 算法
K-means 算法是重要的划分方法，由J.B.MacQueen 提出，具有广泛的影响力。

其基本原理是，首先指定聚类数k ，从含有n 个对象的数据集合中随机地选择k 个对象作为一个簇的初始平均值或中心。

计算剩余的各个对象到这些簇中心的距离，然后根据其与各个簇中心的距离，将它赋给最近的簇。

然后重新计算每个簇的平均值作为该簇新的聚类中心，如果相邻的聚类中心没有任何变化，则样本调整结束，聚类准则函数E 己经收敛。

准则函数的作用是使生成的结果簇尽可能地紧凑和独立。

虽然K-means 算法应用在很多方面，但仍然存在缺陷：(1)在K-means 算法中k 值必须事先给定，无法确定这个K 值。

(2)K-means 聚类算法对初始质心严重依赖，初始聚类中心直接影响着聚类结果，随机选取不同的初始聚类中心点，产生的聚类结果往往都不相同。

(3)K-means 算法的另一个缺点是通常涉及到所有的变量且认为这些变量对距离影响的程度是等同的，容易引发“维数陷阱”。

2.改进的算法AK-menas(Adativek-means)
2.1质心的确定
为弥补k-means 算法的缺陷，本文在k-means 算法的基础上先提出二分k 均值算法，即在算法初始时选出距离最远的两个对象，作为初始中心，形成两个初始簇，从这些簇中选取一个继续分裂，如此下去，直到产生k 个簇，这种方法使得二分k-means 不太受初始化的困扰，因为它执行每步只有两个质心。

这样就可以保证在后续的处理中同一类内的对象有极大的相似性，而不同类之间有极低的相似性。

2.2聚类个数k 值的确定借鉴最大、最小距离法的基本思想，来确定后续聚类的中心，同时在聚类过程中引入Davies —BouldinIndex 指标来确定聚类个数k 。

Davies-BouldinIndex 又称为DBI 指标，一种非模糊型的集群评估指标(clusteringvalidityIndex)，主要是利用几何原理进行运算，分别以聚类间离散程度与位于同一类内的数据对象的紧密程度作为依据，当类内各数据对象间距离越小而类间距离越大，DBI 值也就越小，就代表各聚类内的数据对象越紧密且聚类间的差异大，表明此聚类数目下的聚类结果最佳。

具体算法步骤如下：
(l)通过3.1节的思想确定两个最佳的初始聚类中心cl ，c2。

(2)查找新的聚类中心，分别计算数据集口中剩余的数据对象到cl ，c2的距离d(c1，j)和d(c2，j)。

(3)D=max{min(d(c1，j)，d(c2，j))}，j=l ，2，……，n 。

得到xj ，利用DBI 公式判断是否是要找的最佳聚类中心，如何判断在下面介绍：
好的聚类结果应该是同一类间的各数据对象间相似度大，而不同类之间的相似度小，DBI 能够满足这个条件，即分子越小，分母越大时，DBI 的值越小，则代表各聚类内数据相似度大而类间的相似度小，从这个值可以确定通过D=max{min(d(c1，j)，d(c2，j)}，查找到的xj 是否是最佳中心，既而确定最佳的聚类数目。

找到新聚类中心xj ，进行聚类，重新计算聚类的中心。

对目前形成的k 个聚类，计算其DBI 和前一次计算的DBI 进行比较，如果DBInew<DBIold ，则xj 可以作为聚类中心，同时k 在原来的基础上加
1，否则算法终止。

(4)如果找到的数据对象是中心，则计算D=max{min(d(c1，j)，d(c2，j)，d(c3，j))}，j ’=1，2，…，n 。

存在这样的数据对象，转到(3)。

依次类推直到跳出循环。

从确定的过程可以看出，减少了人为的干预，避免了由于参数设定不当对聚类结果造成的影响。

2.3对改进k-means 算法的描述
结合以上分析，给出改进的k-means 算法流程如下：输入：数据集O 输出：聚类对象
l)扫描数据集0，计算出数据集中最远的两个对象：x1，x2。

2)将数据集剩下的数据对象分别计算到xl ，x2的距离，将其划分到距离小的那个中心的类中，标记，同时记下最小的距离。

3)划分完成后，重新计算聚类中心，得到c1，c2。

4)借鉴最大、最小距离法的基本思想，max{min(d(c1，j)，d(c2，j))}，查找到的xj 。

5)转入2)，对整个数据集进行重新划分。

6)根据DBI 公式，计算DBInew 并比较，和上次计算出来的DBIold 进行比较，如果DBInew<DBIold ，也就是说找到xj 合理的，k 值在上次的基础上增加1，否则就是再也找不到满足条件的新的聚类中心，聚类结束。

7)依次类推，直到无法找到满足条件的新的聚类中心，最终输出聚类结果。

2.4仿真实验及分析
为了更加直观的验证本文AK-means 算法的有效性，对于同一组数据分别用经典的k-means 算法和本文改进后的算法分别进行5次聚类实验，取结果的平均值。

其中实验中用到的数据是随机生成的，数目为100000个，数据维度为2维，数据值在0-260之间。

结果见下表：
下图分别是k-means 聚类算法和AK-means 聚类算法的同一组数据的两次聚类效果图。

（下转第265页）
一种基于K-means 的自适应聚类算法的研究
唐燕雯
（广西工商职业技术学院广西
南宁
530003）
【摘要】聚类(Clustering)是数据挖掘中的一种主要技术，K-means 算法是一种重要的经典的划分方法，但该算法在K 值的确定、质心的选取、对维数的依赖上存在问题，本文提出了一种改进的自适应算法，用于解决K 值的确定、质心的选取等问题，聚类效果较好。

【关键词】聚类;K-means;自适应;算法
作者简介:唐燕雯（1982—），女，汉族，广西南宁人，广西工商职业技术学院，讲师，研究方向为数据库、数据挖掘。

◇职业教育◇
2012年第02
期
（上接第143页）（a)(b)(c)
其中AK-means 聚类算法两次的聚类效果都如图(a)所示，(b)和(c)是两次k-means 聚类的结果，可以明显看出AK-means 聚类算法由于初始聚类中心的确定使得聚类效果稳定，视觉上更加符合人的视觉需
求，聚类结果令人比较满意。

3.结语
通过提出改进的自适应算法，能有效的克服传统的K-means 算法对于K 值和质心确定的弊端
，实验结果证明，该算法能对样本起到更好的凝聚作用。

科
【参考文献】
［1］陆微微，刘晶,一种提高K 一近邻算法效率的新算法[J].计算机工程与应用，2008，44(4):163-165.
［2］黄晓斌，万建伟，张燕.一种改进的自适应K 近邻聚类算法[J].计算机工程与应用，2004，40(15):76-78.
［3］邵峰晶,于忠清.数据挖掘原理与算法[M].中国水利邮电出版社,2003.［4］朱明.数据挖掘[M].合肥：中国科学技术大学出版社,2002.
●
1．原因分析
⑴斜屋面变坡交接处、老虎窗与屋面连接处，由于受力钢筋配置不足，不能满足板块支座弯矩应力的要求。

⑵构造设计不当
为了追求建筑形式而将泛水高度过分的降低，使屋面与屋面连接处、屋面与墙身交接处的防水高度，低于下暴雨瞬时积水高度；屋面变坡处、老虎窗与屋面连接等处防水处理不当，也是形成屋面渗漏的一大隐患。

⑶波形瓦铺贴不实
主要表现在贴瓦砂浆没有挤满瓦缝，砂浆和板面基层结合不牢，波瓦出现空鼓现象；其次是波瓦上下接缝搭接尺寸不足，因而造成屋面雨水渗入基层。

若基层混凝土板出现裂缝，极易导致渗漏。

⑷施工缝位置留设不当
如将施工缝位置留设在屋面变坡处、屋面与屋面的交接处，这些都是结构应力转换的部位，容易产生裂缝而导致屋面渗漏。

⑸现浇钢筋混凝土板施工坍落度选择不当
如施工时用水量过多，混凝土在凝固水化过程中，由于内部多余的水分蒸发后，在混凝土中形成微小的空隙，而混凝土体积减小产生收缩，这些空隙连在一起便形成毛细孔隙，成为雨水渗入的通道，从而引发裂缝产生。

⑹施工方法不当
斜屋面的坡度在30°以上时，如仍采用板底支模法灌筑，则容易造成施工质量事故，如局部板厚不满足设计要求，致使结构出现裂缝；钢筋配置不到位，负筋很容易被踩低，无法和混凝土一起抵挡弯矩而使板产生裂缝；混凝土振捣不密实，也是屋面渗漏的隐患。

2.预防措施
⑴设计时，应考虑整个斜屋面板、板与梁之间相互变形的影响，合理的考虑结构约束形式。

在斜板边界部位，如屋面变坡处、老虎窗与屋面交接处，除按要求配置负筋外，在板面上部板接缝两侧，还应各加配筋200mm 宽的φ4@200双向钢筋网片，以增强斜屋面板整体刚度，提高抗裂性。

⑵加强防渗措施是在屋面渗漏的隐患部位，除结构上增置钢筋网片外，在整个板面再做一层15mm 厚、比例为1:2.5的防水砂浆（内掺5％防水剂），并在板缝两侧各贴300mm 厚宽柔性高分子布胎卷材。

做好泛水构造，屋面板与板连接由过去的锐角断面连接改为梯形断面，以减少板的连接应力，且便于卷材铺贴。

烟囱与屋面交接处在迎水面中部应抹出分水线，高出两侧30mm 。

铺贴1.2mm 厚合成高分子卷材或3mm 厚的高聚物改性沥青防水卷材，上抹聚合物水泥砂浆。

⑶保证钢筋混凝土屋面板的施工质量是模型板采用双面支模灌
筑混凝土斜板，并将模板支撑牢固，以防走模。

板的厚度，施工前认真校对检查钢筋型号、规格、数量，防止错用，每隔500mm 放一个50mm ×50mm ×15mm 的混凝土垫块，与板筋绑扎牢，保证受力筋位置正确。

在绑扎构造负筋时，用φ6钢筋完成Ω形的钢筋凳，每隔500mm 放一个，与负筋绑扎，以免踩低，使之与混凝土形成骨架，以抵抗负弯矩，从而避免表面裂缝的出现。

同时应做好混凝土施工技术管理工作。

施工时，水泥、砂、石、水、外加剂等材料要严格按混凝土强度设计的配合比配置；根据施工季节和屋面倾角大小，选择最佳坍落度，并且加强振捣。

对已灌筑好的混凝土斜板，应在灌筑10～12h 及时进行浇水养护，保证混凝土处在足够的湿润状态，连续养护期不少于15d ，以提高混凝土斜板抗拉强度剂及抗裂性。

⑷波形瓦(以下简称波瓦)屋面施工
采用坐浆挤压法贴实波瓦，要求灰浆挤满瓦缝，以防波瓦空鼓；为使波瓦与混凝土板面结合牢固，施工时基层板面洒水湿润，波瓦要充分吸水待用，在板上先刷一道纯水泥结合层，再用1:2.5水泥砂浆铺贴波瓦，并按要求做好泛水、屋面变坡等部位的瓦面搭接，以增强屋面整体的防渗能力。

波瓦的搭接要求：相邻两瓦应顺主导风向搭接；大波瓦和中波瓦搭接宽度不应小于半个波，小波瓦不应少于一个波；上下两排波瓦的搭接长度应根据屋面坡度而定，但不应少于100mm ；如采用上下两排瓦长边搭接缝错开的方法铺设时，一般以错开半张瓦为宜，但大波瓦和中波瓦至少应错开一个波，小波瓦至少错开两个波；当采用上下两排瓦长边搭接缝不错开的方法铺设时，在相邻四块瓦的搭接处，应随盖瓦方向的不同，事先对波瓦进行割角（玻璃钢波瓦可不割角），对角缝隙不宜大于5mm 。

波瓦的固定：波瓦采用带防水垫圈的镀锌弯钩螺栓固定在金属檩条或混凝土檩条上，或用镀锌螺钉固定在木檩条上，螺栓或螺钉设在靠近波瓦搭接部分的盖瓦波峰上。

在上下两排波瓦搭接处的檩条上，每张盖瓦的螺栓或螺钉为两个，在每排波瓦当中的檩条上，相邻两波瓦搭接处的盖瓦，都应设有一个螺栓或螺钉；在大风地区采用螺钉固定波瓦时，应适当增加螺钉数量；波瓦上的钉孔应钻成孔，孔径比螺栓（螺钉）的直径大2～3mm 固定波瓦的螺栓或螺钉不应拧得太紧，以垫圈稍能转动为度；玻璃钢波瓦铺设时应用木螺丝或对拧螺栓固定，并加橡胶垫衬，每张瓦至少要有六处和檩条固定。

波瓦在异表部位应严格做好密封处理。

屋脊、斜脊用脊瓦铺盖，亦可用镀锌薄钢板铺盖，脊瓦与波瓦之间的空隙，用麻刀灰等嵌封严密；屋面如有天沟、檐沟时，波瓦应伸入沟内至少50mm ，沟底防水层与波瓦间的空隙，用麻刀灰等嵌填严密；屋面与突出屋面的墙或烟囱的连接处采用镀锌薄钢板做泛水时，波瓦与泛水的搭接宽度不小于
150mm ，波瓦与泛水间的空隙，用麻刀灰等嵌填严密。

科
浅谈现浇钢筋混凝土斜屋面渗漏原因分析及预防措施
王可欣1王军2王发3
（1.哈尔滨立奇房地产开发有限公司黑龙江哈尔滨150000；
2.黑龙江水利第五工程处黑龙江绥化152000；
3.黑龙江省轻工建设监理有限公司黑龙江哈尔滨150000）
●
◇建工论坛◇。