文档介绍：西安科技大学
题 目 院、系（部） 专业及班级 姓 名 指导教师
毕业设计（论文）文献翻译
聚类分析
计算机科学与技术学院
计算机科学与技术1002
李倩
杨君锐
介绍
如今，很多行业都对数据进行收集，而且，聚类分析也密度函数表示。我们的目标是研究在 改编传统的不确定性数据聚类的K-means算法中的计算问题，并且设计出高效的 算法来解决这一问题。
作为一个积极的例子，让我们一起来讨论移动设备的聚类问题。在很多无 线网络应用程序中，移动设备定期的向远程设备报告它们的位置。每一个设备可
以和周边的设备进行低耗能近距离的通信，或者直接地和远程设备进行高耗能远 距离的通信。为了减少耗能，出现了批处理协议。在这些协议中，某些设备被选 来做指导设备，它们的工作是通过近距离通讯收集来自周围设备的消息。这些指 导设备然后通过远距离通信（）将收集到的消息采用批处理的方式发送到 服务器。通过批处理消息，很多远距离消息被近距离消息所代替。本地指导者的 选举可以被描述为一个聚类问题。目的是为了减小每个设备和与之对应的作为聚 集代表的本地指导者之间的距离。这个聚类问题有别于传统环境下存在的数据不 确定性。
•物理设备用来确定设备的位置，到达一定的精度才会准确。
•设备的当前位置只有基于最近的报告值才能估计。换句话说，数据常常老化。 其他的实际性问题，比如，数据包的丢失，也会增加数据的不确定性程度。
•数据的不确定性也可以由用户引进去保护他们的位置隐私。特别地，数据隐 身这一想法在发送到服务器提供者之前就被研究，数据隐身就是用户的位置 被转换成更大的范围。
由于不确定性，一个移动设备的踪迹只能通过在它的最新报告位置强加不 确定模型来粗略估计。一个典型的不确定模型需要关于设备的移动速度和它的运 动是否受限制（一个在公路网上运动的小车）或不受限制（比如一个追踪装置安 装在在平原上运动的动物身上）的知识。通常，一个定义在有界区域的二维概 率密度分布函数模拟数据的不确定性。在聚类中，从移动设备的最新报告位置得 到的集群很明显的区别于那些好像可以得到的实际位置得到的集群。如果我们仅 仅依赖报告位置，很多移动设备会被放入错误的集群。通过合并不确定信息，比 如，不确定性数据的概率密度分布函数放入现存的聚类算法，聚类结果可能更加 接近已知的信息，就可以认为聚类适用于并且使用实际（精确）数据。
不确定性数据聚类问题首次在UK-means算法提出的时候得到解决。 UK-means算法在聚类过程中考虑了数据的不确定性。该算法提出遵循传统的 K-means算法，除了只有一个变化。这个变化是，在UK-means算法中用路程期 望测度计算对象和点（比如，集群的代表点）的距离。在K-means中，是用一个 简化的距离测度（比如，欧几里得距离）计算来代替。在那个研究中，不确定性 对象是通过概率密度分布函数建模，而路程期望是通过这些概率密度分布函数计 算得来。
在研究中表明，聚类结果的质量可以通过在K-means算法中考虑不确定性来 提高。然而，研究的目标集中在提高聚类结果的质量。UK-means算法的效率是 个次要问题。它假设对象的概率密度分布函数的均匀分布。这种特殊的分布形式 允许了距离期望的有效计算。对于任意的概率密度分布函数，距离期望的计算