WSN环境下分布式聚类算法的研究与实现

摘要

随着无线传感器网络的应用越来越广泛,聚类算法被应用于此平台。聚类算法是数据挖掘和机器学习领域的一个重要的分支。无线传感器网络上的数据聚类可以应用于检测温度变化、污染物流动情况、煤气泄漏情况和异常数据簇检测。
　　 本文的第一个算法(DSE)是以数据为中心的分布式聚类算法。该算法是对一种现存的优秀的Elink算法的改进。Elink算法的主要贡献是以有序性的方式选择和使用簇头,这种顺序性体现在四叉树结构中。但顺序性选取簇头节点的方式限制了算法的时间复杂度。我们在DSE算法的使用中取消簇头节点顺序使用,引入虚根和质心两种相对簇头,使得簇头节点在不满足距离度量条件时可以同步开始操作。算法的时间复杂度由原来的O((N)×LogN)变为D((N))。
　　 第二个DHC算法是基于DCDTW技术的时间序列分布式聚类算法。在ICDM2008中有一个DSIC算法也是对时间序列进行处理。DSIC算法中使用k-Haar小波技术对时间序列进行压缩,然后使用FastDWI计算时间序列的相异度。但是使用这种方法计算的相异度会和原始时间序列计算出的相异度有很大的误差。为了弥补误差,我们在DHC算法中把SN-Haar技术和DTW技术联合使用,然后在加入误差补偿值DCs,得到一种基于误差补偿的动态时间弯曲方法(DCDTW)。
　　 最后,DHC算法把IEEE2006中关于异常处理的方法应用于数据簇的聚类。
　　 本文的两个聚类算法都是数据聚类,但这两种算法对时间序列的处理方法是不同的,使用的基础框架也是不同的。DSE算法的优点是时间复杂度进一步变好了,但牺牲了一点聚类质量。DHC算法的优点是有较高的聚类质量且通讯量低、误差小,但时间复杂度略有不足。