毕业设计（论文）外文资料翻译系部：计算机科学与技术系专业：计算机科学与技术姓名：学号：外文出处：Proceeding of Workshop on the （用外文写）of Artificial,Hualien,TaiWan,2005不确定性数据挖掘：一种新的研究方向Michael Chau1, Reynold Cheng2, and Ben Kao31：商学院，香港大学，薄扶林，香港2：计算机系，香港理工大学九龙湖校区，香港3：计算机科学系，香港大学，薄扶林，香港摘要由于不精确测量、过时的来源或抽样误差等原因，数据不确定性常常出现在真实世界应用中。
目前，在数据库数据不确定性处理领域中，很多研究结果已经被发表。
我们认为，当不确定性数据被执行数据挖掘时，数据不确定性不得不被考虑在内，才能获得高质量的数据挖掘结果。
我们称之为“不确定性数据挖掘”问题。
在本文中，我们为这个领域可能的研究方向提出一个框架。
同时，我们以UK-means 聚类算法为例来阐明传统K-means算法怎么被改进来处理数据挖掘中的数据不确定性。
1.引言由于测量不精确、抽样误差、过时数据来源或其他等原因，数据往往带有不确定性性质。
特别在需要与物理环境交互的应用中，如：移动定位服务[15]和传感器监测[3]。
例如：在追踪移动目标（如车辆或人）的情境中，数据库是不可能完全追踪到所有目标在所有瞬间的准确位置。
因此，每个目标的位置的变化过程是伴有不确定性的。
为了提供准确地查询和挖掘结果，这些导致数据不确定性的多方面来源不得不被考虑。
在最近几年里，已有在数据库中不确定性数据管理方面的大量研究，如：数据库中不确定性的表现和不确定性数据查询。
然而，很少有研究成果能够解决不确定性数据挖掘的问题。
我们注意到，不确定性使数据值不再具有原子性。
对于使用传统数据挖掘技术，不确定性数据不得不被归纳为原子性数值。
再以追踪移动目标应用为例，一个目标的位置可以通过它最后的记录位置或通过一个预期位置（如果这个目标位置概率分布被考虑到）归纳得到。
不幸地是，归纳得到的记录与真实记录之间的误差可能会严重也影响挖掘结果。
图1阐明了当一种聚类算法被应用追踪带有不确定性位置的移动目标时所发生的问题。
图1（a）表示一组目标的真实数据，而图1（b）则表示记录的已过时的这些目标的位置。
如果这些实际位置是有效的话，那么它们与那些从过时数据值中得到的数据集群有明显差异。
如果我们仅仅依靠记录的数据值，那么将会很多的目标可能被置于错误的数据集群中。
更糟糕地是，一个群中的每一个成员都有可能改变群的质心，因此导致更多的错误。
图1 数据图图1.（a）表示真实数据划分成的三个集群（a、b、c）。
（b）表示的有些目标（隐藏的）的记录位置与它们真实的数据不一样，因此形成集群a’、b’、c’和c”。
注意到a’集群中比a集群少了一个目标，而b’集群中比b集群多一个目标。
同时，c也误拆分会为c’和c”。
(c)表示方向不确定性被考虑来推测出集群a’，b’和c。
这种聚类产生的结果比（b）结果更加接近（a）。
我们建议将不确定性数据的概率密度函数等不确定性信息与现有的数据挖掘方法结合，这样在实际数据可利用于数据挖掘的情况下会使得挖掘结果更接近从真实数据中获得的结果。
本文研究了不确定性怎么通过把数据聚类当成一种激励范例使用使得不确定性因素与数据挖掘相结合。
我们称之为不确定性数据挖掘问题。
在本文中，我们为这个领域可能的研究方向提出一个框架。
文章接下来的结构如下。
第二章是有关工作综述。
在第三章中，我们定义了不确定性数据聚类问题和介绍我们提议的算法。
第四章将呈现我们算法在移动目标数据库的应用。
详细地的实习结果将在第五章解释。
最后在第六章总结论文并提出可能的研究方向。
2.研究背景近年来，人们对数据不确定性管理有明显的研究兴趣。
数据不确定性被为两类，即已存在的不确定生和数值不确定性。
在第一种类型中，不管目标或数据元组存在是否，数据本身就已经存在不确定性了。
例如，关系数据库中的元组可能与能表现它存在信任度的一个概率值相关联[1,2]。
在数据不确定性类型中，一个数据项作为一个封闭的区域,与其值的概率密度函数（PDF）限定了其可能的值[3,4,12,15]。
这个模型可以被应用于量化在不断变化的环境下的位置或传感器数据的不精密度。
在这个领域里，大量的工作都致力于不精确查找。
例如，在[5]中，解决不确定性数据范围查询的索引方案已经被提出。
在[4]中，同一作者提出了解决邻近等查询的方案。
注意到，所有工作已经把不确定性数据管理的研究结果应用于简化数据库查询中，而不是应用于相对复杂的数据分析和挖掘问题中。
在数据挖掘研究中，聚类问题已经被很好的研究。
一个标准的聚类过程由5个主要步骤组成：模式表示，模式定义，模式相似度量的定义，聚类或分组，数据抽象和造工评核[10]。
只有小部分关于数据挖掘或不确定性数据聚类的研究被发表。
Hamdan与Govaert已经通过运用EM算法解决使混合密度适合不确定性数据聚类的问题 [8]。
然而，这个模型不能任意地应用于其他聚类算法因为它相当于为EM定制的。
在数据区间的聚类也同样被研究。
像城区距离或明考斯基距离等不同距离测量也已经被用来衡量两个区间的相似度。
在这些测量的大多数中，区间的概率密度函数并没有被考虑到。
另外一个相关领域的研究就是模糊聚类。
在模糊逻辑中的模糊聚类研究已经很久远了[13]。
在模糊聚类中,一个是数据簇由一组目标的模糊子集组成。
每个目标与每个簇都有一个“归属关系度”。
换言之，一个目标可以归属于多个簇，与每个簇均有一个度。
模糊C均值聚类算法是一种最广泛的使用模糊聚类方法[2,7]。
不同的模糊聚类方法已被应用在一般数据或模糊数据中来产生的模糊数据簇。
他们研究工作是基于一个模糊数据模型的，而我们工作的开展则基于移动目标的不确定性模型。
3.不确定数据的分类在图2中，我们提出一种分类法来阐述数据挖掘方法怎么根据是否考虑数据不准确性来分类。
有很多通用的数据挖掘技术，如: 关联规则挖掘、数据分类、数据聚类。
当然这些技术需要经过改进才能用于处理不确定性技术。
此外，我们区分出数据聚类的两种类型：硬聚类和模糊聚类。
硬聚类旨在通过考虑预期的数据来提高聚类的准确性。
另一方面，模糊聚类则表示聚类的结果为一个“模糊”表格。
模糊聚类的一个例子是每个数据项被赋予一个被分配给数据簇的任意成员的概率。
图2. 不确定性数据挖掘的一种分类例如，当不确定性被考虑时，会发生一个有意思的问题，即如何在数据集中表示每个元组和关联的不确定性。
而且，由于支持和其他指标的概念需要重新定义，不得不考虑改进那些著名的关联规则挖掘算法(如Apriori)。
同样地，在数据分类和数据聚集中，传统算法由于未将数据不确定性考虑在内而导致不能起作用。
不得不对聚类质心、两个目标的距离、或目标与质心的距离等重要度量作重新定义和进行更深的研究。
4．不确定性数据聚类实例在这个章节中，我们将以不确定性数据挖掘的例子为大家介绍我们在不确定性数据聚类中的研究工作。
这将阐明我们在改进传统数据挖掘算法以适合不确定性数据问题上的想法。
4.1 问题定义用S 表示V 维向量x i 的集合，其中i=1到n ，这些向量表示在聚类应用中被考虑的所有记录的属性值。
每个记录o i 与一个概率密度函数f i (x)相联系，这个函数就是o i 属性值x 在时间t 时刻的概率密度函数。
我们没有干涉这个不确定性函数的实时变化，或记录的概率密度函数是什么。
平均密度函数就是一个概率密度函数的例子，它描述“大量不确定性”情景中是最糟的情况[3]。
另一个常用的就是高斯分布函数，它能够用于描述测量误差[12,15]。
聚类问题就是在数据集簇C j （j 从1到K ）找到一个数据集C ，其中C j 由基于相似性的平均值c j 构成。
不同的聚类算法对应不对的目标函数，但是大意都是最小化同一数据集目标间的距离和最大化不同数据集目标间的距离。
数据集内部距离最小化也被视为每个数据点之间距离x i 以及x i 与对应的C j 中平均值c j 距离的最小化。
在论文中，我们只考虑硬聚类，即，每个目标只分配给一个一个集群的一个元素。
4.2 均值聚类在精确数据中的应用这个传统的均值聚类算法目的在于找到K(也就是由平均值c j 构成数据集簇C j )中找到一个数据集C 来最小化平方误差总和（SSE ）。
平方误差总和通常计算如下：∑∑=∈-K j x i j ji x c 1C 2 (1)|| . ||表示一个数据点x i 与数据集平均值c j 的距离试题。
例如，欧氏距离定义为：∑=-=-V i i i y x y x 12(2)一个数据集C i 的平均值（质心）由下面的向量公式来定义：∑∈=j C i i j i x C c 1 (3)均值聚类算法如下：1. Assign initial values for cluster means c 1 to c K2. repeat3. for i = 1 to n do4. Assign each data point x i to cluster C j where || c j - x i || is the minimum.5. end for6. for j = 1 to K do7. Recalculate cluster mean c j of cluster C j8. end for9. until convergence10. return C收敛可能基于不同的质心来确定。
一些收敛性判别规则例子包括：（1）当平方误差总和小于某一用户专用临界值，（2）当在一次迭代中没有一个目标再分配给不同的数据集和（3）当迭代次数还达到预期的定义的最大值。
4.3 K-means 聚类在不确定性数据中的应用为了在聚类过程中考虑数据不确定性，我们提出一种算法来实现最小化期望平方误差总和E(SSE)的目标。
注意到一个数据对象x i 由一个带有不确定性概率密度f(x i )的不确定性区域决定。
给定一组数据群集，期望平方误差总和可以计算如下：()ii K j C i ij Kj C i ij Kj C i i j dx x f x c x c E x c E j jj )(121212∑∑∑∑∑∑=∈=∈=∈-=-=⎪⎪⎭⎫ ⎝⎛- (4) 数据集平均值可以如下给出: ()∑⎰∑∑∈∈∈==⎪⎪⎭⎫ ⎝⎛=j jj C i ii i j C i i j C i i j j dx x f x C x E C x C E c )(111 (5) 我们到此将提出一种新K-means 算法，即UK-means ，来实现不确定性数据聚类。
1. Assign initial values for cluster means c 1 to c K2. repeat3. for i = 1 to n do4. Assign each data point x i to cluster C j where E(|| c j - x i ||) is the minimum.5. end for6. for j = 1 to K do7. Recalculate cluster mean c j of cluster C j8. end for9. until convergence10. return CUK-mean 聚类算法与K-means 聚类算法的最大不同点在于距离和群集的计算。