《聚类分析 翻译》由会员分享，可在线阅读，更多相关《聚类分析 翻译（8页珍藏版）》请在金锄头文库上搜索。
1、1西安科技大学毕业设计毕业设计( (论文论文) )文献翻译文献翻译题 目 聚类分析 院、系(部) 计算机科学与技术学院 专业及班级 计算机科学与技术 1002 姓 名 李倩 指 导 教 师 杨君锐 日 期 2介绍介绍如今，很多行业都对数据进行收集，而且，聚类分析也被应用到很多数据上用来发现数据的某些知识或者特性。聚类分析是一门普通的统计学数据分析技术，被应用到很多领域，包括数据挖掘技术，图形识别和图像分析。一种聚类是将一个对象的数据集分割成为子集，所以在每个子集内的对象被认为是相似的，在不同子集的对象被认为是不相似的。这种相似或不相似的定义以及如何被衡量，取决于特定的应用程序。聚类分析可以根据
2、它的应用目标分类为：（1）减少一定价值的函数（比如：数据对象到它们各自群集代表点距离的总和。 ） （2）确定模型参数最优可能的取值（比如：高斯混合的方式） （3）识别高密度链接区域（比如：对象的高密度人口区域） （4）将类似的数据对象连接在一起（比如：连接一个图像上有相似颜色的像素分布）我们的研究分为第一个和最后一个类别。无论类别，数据在很多聚类应用中包含着内在的值的不确定性。这些数据被称作不确定数据。很多的因素造就了这些不确定性，比如无规律的数据生成和收集进程，测量误差，和数据老化。目前有大量的数据分析研究，只有以少部分从事数据不确定性研究。在这篇论文中，我们将研究如何在聚类分析中利用这些不
3、确定性数据。我们也将在研究中提出方法来解决聚类效率和准确性问题。1.11.1 不确定数据和模型不确定数据和模型在需要和现实世界交互的应用程序中，比如定位服务技术，传感器监测，和图像服务，数据不确定性是一个固有属性。特别地，从测量工具或者远距离来源收集的数据常常是不精确的，由于测量工具的误差，取样的差异，过时的数据来源，或者其他的错误。比如，在移动对象的环境中，让数据库在所有的瞬间追踪所有对象的准确位置是不可能的，每个对象的位置与不确定性之间的更新有关。近期的作品也提出通过削弱用户位置的精确度来保护位置隐私。所有这类在值上有不确定性的数据被称作不确定性数据。不确定性的不同来源必须被认为是为了产生
4、准确的数据查询和分析结果。近期，很多不确定性数据的研究集中在数据库中不确定性数据的管理，比如，不确定性数据在数据库中的表示和带不确定性的数据查询，然而，很少有研究从事关于不确定性数据挖掘问题。甚至更少有研究在聚类分析领域。这篇论文的目的是研究聚类不确定性数据的各种问题。3一些不确定性数据具有多维的不确定性，比如上文中提到的在移动对象环境中陈旧的位置数据，特别地，一个数据对象在空间中并不是一个简单的点，而是由概率密度函数定义的不确定区域建模。概率密度函数说明了对象在空间中的每个可能位置的概率密度。概率密度函数一般有能力建立任何不确定性模型，包括均匀分布或者高斯分布。因此，带有不确定性过时位置数据
5、的移动对象可以用这种方法来建模。这种对象的概率密度函数可以由它的最新报告位置、地理信息和它的特性构造。对于带有测量误差的数据，可以通过概率密度函数建模。错误可以通过采取相同数据的多元测量解决，也可以在数据分析中利用这些错误。利用多元测量的一种方法是重新定义度量标准，这种测量标准过去习惯用一种测量尺度，到所有的测量结果。比如说，为了计算两个不确定性对象之间的相似度，我们可能会计算这两个对象之间所有可能的测量结果的平均相似度值。这个平均值给出了预期相似度作为这两个不确定性对象之间的相似度。一些应用程序可能会需要数据值的比较值来检验一些条件（比如，高出了某一阈值。 ）在这些应用程序中，每一个测量结果
6、在比较中都可能作为数据值被单独的来使用。这些比较的大多数校验结果（比如，满足不满足条件）将会被作为整体结果。这一作业常常通过定义给定概率值的概率量度来完成。在这篇论文中，在不确定性数据的聚类问题上，我们既考虑到数据模型，还有概率密度函数和多重测量结果。我们还要指出，一些不确定性数据可以通过值的间隔来建模。不同距离的测量，比如曼哈顿距离测量和闵可夫斯基距离测量，经常被扩展到处理时间间隔局。由于数据具有测量误差，它们可能会通过内核函数来建模。1.21.2 最小价值函数的聚类分析最小价值函数的聚类分析聚类分析的一个目标是将数据对象分割成集群，以便减小价值函数（比如：数据对象到它们各自群集代表点距离的
7、总和。 ） 。K-means 算法是聚类应用的一种常见算法。简单来说，传统的聚类算法并没有解决数据值的不确定性这样的问题。然而数据的不确定性在一些现实的应用程序中是本身固有的，由于这样一些因素，比如，比如无规律的数据生成和收集进程，测量误差，和数据老化。在这片论文中，我们将研究带有位置不确定性的空间对象的聚类问题。在我们的模型中，一个对象的位置通过空间概率密度函数表示。我们的目标是研究在改编传统的不确定性数据聚类的 K-means 算法中的计算问题，并且设计出高4效的算法来解决这一问题。作为一个积极的例子，让我们一起来讨论移动设备的聚类问题。在很多无线网络应用程序中，移动设备定期的向远程设备报
8、告它们的位置。每一个设备可以和周边的设备进行低耗能近距离的通信，或者直接地和远程设备进行高耗能远距离的通信。为了减少耗能，出现了批处理协议。在这些协议中，某些设备被选来做指导设备，它们的工作是通过近距离通讯收集来自周围设备的消息。这些指导设备然后通过远距离通信（图 1.1）将收集到的消息采用批处理的方式发送到服务器。通过批处理消息，很多远距离消息被近距离消息所代替。本地指导者的选举可以被描述为一个聚类问题。目的是为了减小每个设备和与之对应的作为聚集代表的本地指导者之间的距离。这个聚类问题有别于传统环境下存在的数据不确定性。图 1.1物理设备用来确定设备的位置，到达一定的精度才会准确。设备的当前
9、位置只有基于最近的报告值才能估计。换句话说，数据常常老化。其他的实际性问题，比如，数据包的丢失，也会增加数据的不确定性程度。数据的不确定性也可以由用户引进去保护他们的位置隐私。特别地，数据隐身这一想法在发送到服务器提供者之前就被研究，数据隐身就是用户的serverleaderMember5位置被转换成更大的范围。由于不确定性，一个移动设备的踪迹只能通过在它的最新报告位置强加不确定模型来粗略估计。一个典型的不确定模型需要关于设备的移动速度和它的运动是否受限制（一个在公路网上运动的小车）或不受限制（比如一个追踪装置安装在在平原上运动的动物身上）的知识。 通常，一个定义在有界区域的二维概率密度分布函
10、数模拟数据的不确定性。在聚类中，从移动设备的最新报告位置得到的集群很明显的区别于那些好像可以得到的实际位置得到的集群。如果我们仅仅依赖报告位置，很多移动设备会被放入错误的集群。通过合并不确定信息，比如，不确定性数据的概率密度分布函数放入现存的聚类算法，聚类结果可能更加接近已知的信息，就可以认为聚类适用于并且使用实际（精确）数据。不确定性数据聚类问题首次在 UK-means 算法提出的时候得到解决。UK-means 算法在聚类过程中考虑了数据的不确定性。该算法提出遵循传统的 K-means 算法，除了只有一个变化。这个变化是，在 UK-means 算法中用路程期望测度计算对象和点（比如，集群的代
11、表点）的距离。在 K-means 中，是用一个简化的距离测度（比如，欧几里得距离）计算来代替。在那个研究中，不确定性对象是通过概率密度分布函数建模，而路程期望是通过这些概率密度分布函数计算得来。在研究中表明，聚类结果的质量可以通过在 K-means 算法中考虑不确定性来提高。然而，研究的目标集中在提高聚类结果的质量。UK-means 算法的效率是个次要问题。它假设对象的概率密度分布函数的均匀分布。这种特殊的分布形式允许了距离期望的有效计算。对于任意的概率密度分布函数，距离期望的计算需要数字化的集成，而数字化集成非常昂贵。UK-means 算法也需要大量的距离期望计算和更多数据集大小的增加。这使
12、得具有任意概率密度分布函数对象的聚类算法不切实际。在第三章中我们研究两种剪枝算法，即就是 PC 和 CS，可以显著的减少距离期望的计算。这两种算法依靠良好的边界技术。我们在指标属性和三角学的基础上提出和估计这两种算法。而 Met 边界是由三角不等式推导出来的。Tri边界是通过三角等式得来的。我们的实验结果表明，Tri 提供了非常高的修剪权。在某些情况下，超高99.9%的距离期望计算被剪去。这些结果在非常有效的聚类算法里。1.31.3 连接类似数据的聚类算法连接类似数据的聚类算法有些聚类应用程序有一个连接相似数据对象的目标。图像分割是这个目标6的特殊应用。一个图像的像素点被连接到集群。比如，医学
13、成像技术如 X-ray，电子计算机 X 射线断层成像（CT） ，核磁共振（MRI） ，正电子发射计算机断层扫描（PET） ，超声波（USG） ，是各种医学疾病分析的必要条件。如果在一个图像中的了两个像素有相同的颜色而且它们之间的相似度不低于一定的阈值，这两个像素就被认为是相似的。因此，相似的像素在图像中被连接成为任意的图形。图像中的边界，曲面，和一些元件的分割值可以被看到或者通过集群提取。这些分割元件和它们的边界对内科医生个外科医生在医学分析中起至关重要的作用。我们指出这聚类容许我们发现任意形状的集群相似于通过基于密度聚类得到的集群。其他类的聚类如 K-means 聚类只能发现规则图形的集群。
14、图像分割也应用到地理卫星图像如城市的分段和道路的提取。在道路提取中，颜色类似度的测量被应用到一个地区图像像素的聚类。集群们是这样形成的，每一个集群由所有的在同一个集群中与另一个像素颜色相似的所有像素组成。有相似颜色的像素但是被分散在一个图像中，因此由一个集群连接在一起。在像素被聚类后，一些后期处理（基于像素颜色识别代表道路的集群和提取道路边界集群）被应用到集群中为了得到图像中的道路网。再如，考虑到卫星图片分割问题。相同的图像花费不同的时间可能会得到不同的像素颜色分布。这可能是由于光照的变化，大气的变化，等等。这引起了颜色数据的值的不确定性。另一个不确定性例子是在数字图像上类似像素颜色的量子化进
15、入到离散的色阶。此外，由于相机分辨率有限，一个像素实际上代表了一种地理（任意的）颜色。这种不确定性可能被认为是测量误差。在这篇论文中，我们通过运用相同数据的多元测量解决错误这种方法来研究具有不确定性数据的聚类。如 1.1 中讨论的，测量误差也可以通过概率密度分布函数建模来解决。而在一些应用程序中比如图像分割，我们常常没有能力去确定概率密度分布函数，等等，由于上文中提到的可能的错误来源。与此同时，相同不确定数据的多个采样可能会很昂贵，比如，相同对象的很多卫星图像，超过很长的时间是为了近似数据的概率密度分布函数。因此，我们的研究重点在这些应用程序，我们不得不采用除了概率密度分布函数外的多元（可能很
16、少）数据测量去解决测量误差。目前，在相似数据连接方面的传统数据聚类有两种方法：（1）基于阈值的模糊关系聚类，这种聚类是基于模糊等价关系。 （2）基于阈值的单链接聚类算法，这种聚类是基于分层聚类。我们研究不确定性数据的聚类算法是在二种算法的基础上。这是因为第二种算法允许我们开发更高效的算法。在第四章，我们提出基于阈值的单链接聚类算法，采用不确定性数据聚类7的多元数据测量方法是为了提高聚类结果的质量。像那章中解释的，不确定性数据聚类的效率是一个主要问题。因此，基于我们的聚类方法的不同算法的提出是为了解决这个问题。我们的实验结果表明，我们采用多元测量来提高聚类结果质量的算法明显的超过了对于不确定性数据只采用一种测量方法的传统单链接算法。当数据
