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