K-means算法，即UK-means，来实现不确定性数据聚类。.AssigninitialvaluesforclustermeansctocK.repeat.fori=tondo.AssigneachdatapointxitoclusterCjwhereE(||cj-xi||)istheminimum..endfor.forj=toKdo.RecalculateclustermeancjofclusterCj.endfor.untilconvergence.returnCUK-mean聚类算法与K-means聚类算法最大不同点在于距离和群集计算。特别地，UK-means基于数据不确定性模型来计算预期距离和数据集质心。同时，收敛可按照不同标准来定义。注意到如果收敛依赖于下平方误差，那么在方程式（）中E(SSE)应该替代SSE使用。在第步中，常常很困难用代数方法来确定E(||cj-xi||)据簇由一组目标模糊子集组成。每个目标与每个簇都有一个“归属关系度”。换言之，一个目标可以归属于多个簇，与每个簇均有一个度。模糊C均值聚类算法是一种最广泛使用模糊聚类方法[,]。不同模糊聚类方法已被应用在一般数据或模糊数据中来产生模糊数据簇。他们研究工作是基于一个模糊数据模型，而我们工作开展则基于移动目标不确定性模型。.不确定数据分类在图中，我们提出一种分类法来阐述数据挖掘方法怎么根据是否考虑数据不准确性来分类。有很多通用数据挖掘技术，如:关联规则挖掘、数据分类、数据聚类。当然这些技术需要经过改进才能用于处理不确定性技术。此外，我们区分出数据聚类两种类型：硬聚类和模糊聚类。硬聚类旨在通过考虑预期数据来提高聚类准确性。另一方面，模糊聚类则表示聚类结果为一个“模糊”表格。模糊聚类一个例子是每个数据项被赋予一个被分配给数据簇任意成员概率。不确定性数据挖掘：一种新研究方向图.不确定性数据挖掘一种分类例如，当不确定性被考虑时，会发生一个有意思问题，即如何在数据集中表示每个元组和关联不确定性。而且，由于支持和其他指标概念需要重新定义，不得不考虑改进那些著名关联规则挖掘算法(如Apriori)。同样地，在数据分类和数据聚集中，传统算法由于未将数据不确定性考虑在内而导致不能起作用。不得不对聚类质心、两个目标距离、或目标与质心距离等重要度量作重新定义和进行更深研究。．不确定性数据聚类实例在这个章节中，我们将以不确定性数据挖掘例子为大家介绍我们在不确定性数据聚类中研究工作。这将阐明我们在改进传统数据挖掘算法以适合不确定性数据问题上想法。.问题定义用S表示V维向量xi集合，其中i=到n，这些向量表示在聚类应用中被考虑所有记录属性值。每个记录oi与一个概率密度函数fi(x)相联系，这个函数就是oi属性值x在时间t时刻概率密度函数。我们没有干涉这个不确定性函数实时变化，或记录概率密度函数是什么。平均密度函数就是一个概率密度函数例子，它描述“大量不确定性”情景中是最糟情况[]。另一个常用就是高斯分布函数，它能够用于描述测量误差[,]。聚类问题就是在数据集簇Cj（j从到K）找到一个数据集C，其中Cj由基于相似性平均值cj构成。不同聚类算法对应不对目标函数，但是大意都是最小化同一数据集目标间距离和最大化不同数据集目标间距离。数据集内部距离最小不确定性数据挖掘：一种新研究方向化也被视为每个数据点之间距离xi以及xi与对应Cj中平均值cj距离最小化。在论文中，我们只考虑硬聚类，即，每个目标只分配给一个一个集群一个元素。.均值聚类在精确数据中应用这个传统均值聚类算法目在于找到K(也就是由平均值cj构成数据集簇Cj)中找到一个数据集C来最小化平方误差总和（SSE）。平方误差总和通常计算如下：KjxijjixcC()||.||表示一个数据点xi与数据集平均值cj距离试题。例如，欧氏距离定义为：Viiiyxyx()一个数据集Ci平均值（质心）由下面向量公式来定义：jCiijixCc()均值聚类算法如下：.AssigninitialvaluesforclustermeansctocK.repeat.fori=tondo.AssigneachdatapointxitoclusterCjwhere||cj-xi||istheminimum..endfor.forj=toKdo.RecalculateclustermeancjofclusterCj.endfor.untilconvergence.returnC收敛可能基于不同质心来确定。一些收敛性判别规则例子包括：（）当平方误差总和小于某一用户专用临界值，（）当在一次迭代中没有一个目标再分配给不同数据集和（）当迭代次数还达到预期定义最大值。.K-means聚类在不确定性数据中应用为了在聚类过程中考虑数据不确定性，我们提出一种算法来实现最小化期望平方误差总和E(SSE)目标。注意到一个数据对象xi由一个带有不确定性概率密度f(xi)不确定性区域决定。给定一组数据群集，期望平方误差总和可以计算如下：不确定性数据挖掘：一种新研究方向iiKjCiijKjCiijKjCiijdxxfxcxcExcEjjj)(()数据集平均值可以如下给出:jjjCiiiijCiijCiijjdxxfxCxECxCEc)(()我们到此将提出一种新K-means算法，即UK-means，来实现不确定性数据聚类。.AssigninitialvaluesforclustermeansctocK.repeat.fori=tondo.AssigneachdatapointxitoclusterCjwhereE(||cj-xi||)istheminimum..endfor.forj=toKdo.RecalculateclustermeancjofclusterCj.endfor.untilconvergence.returnCUK-mean聚类算法与K-means聚类算法最大不同点在于距离和群集计算。特别地，UK-means基于数据不确定性模型来计算预期距离和数据集质心。同时，收敛可按照不同标准来定义。注意到如果收敛依赖于下平方误差，那么在方程式（）中E(SSE)应该替代SSE使用。在第步中，常常很困难用代数方法来确定E(||cj-xi||).Barbara,D.,Garcia-Molina,H.andPorter,D.“TheManagementofProbabilisticData,”IEEETransactionsonKnowledgeandDataEngineering,(),.[].Bezdek,J.C.PatternRecognitionwithFuzzyObjectiveFunctionAlgorithms.PlenumPress,NewYork().[].Cheng,R.,Kalashnikov,D.,andPrabhakar,S.“EvaluatingProbabilisticQueriesoverImpreciseData,”ProceedingsoftheACMSIGMODInternationalConferenceonManagementofData,June.[].Cheng,R.,Kalashnikov,D.,andPrabhakar,S.“QueryingImpreciseDatainMovingObjectEnvironments,”IEEETransactionsonKnowledgeandDataEngineering,()()-.[].Cheng,R.,Xia,X.,Prabhakar,S.,Shah,R.andVitter,J.“EfficientIndexingMethodsforProbabilisticThresholdQueriesoverUncertainData,”ProceedingsofVLDB,.[].deSouza,R.M.C.R.anddeCarvalho,F.deA.T.“ClusteringofIntervalDataBasedonCity–BlockDistances,”PatternRecognitionLetters,()–.[].Dunn,J.C.“AFuzzyRelativeoftheISODATAProcessandItsUseinDetectingCompactWell-SeparatedClusters,”JournalofCybernetics,()-.[].Hamdan,H.andGovaert,G.“MixtureModelClusteringofUncertainData,”IEEEInternationalConferenceonFuzzySystems()-.[].Ichino,M.,Yaguchi,H.“GeneralizedMinkowskiMetricsforMixedFeatureTypeDataAnalysis,”IEEETransactionsonSystems,ManandCybernetics,()()–.[].Jain,A.andDubes,R.AlgorithmsforClusteringData.PrenticeHall,NewJersey().[].NileshN.D.andSuciu,D.“EfficientQueryEvaluationonProbabilisticDatabases,”VLDB()-.[].PfoserD.andJensen,C.“CapturingtheUncertaintyofMoving-objectsRepresentations,”ProceedingsoftheSSDBMConference,–,.[].Ruspini,E.H.“ANewApproachtoClustering,”InformationControl,()()-.[].Sato,M.,Sato,Y.,andJain,L.FuzzyClusteringModelsandApplications.Physica-Verlag,Heidelberg().[].Wolfson,O.,Sistla,P.,Chamberlain,S.andYesha,Y.“UpdatingandQueryingDatabasesthatTrackMobileUnits,”DistributedandParallelDatabases,(),.[].Yeung,K.andRuzzo,W.“AnEmpiricalStudyonPrincipalComponentAnalysisforClusteringGeneExpressionData,”Bioinformatics,()()-.据簇由一组目标模糊子集组成。每个目标与每个簇都有一个“归属关系度”。换言之，一个目标可以归属于多个簇，与每个簇均有一个度。模糊C均值聚类算法是一种最广泛使用模糊聚类方法[,]。不同模糊聚类方法已被应用在一般数据或模糊数据中来产生模糊数据簇。他们研究工作是基于一个模糊数据模型，而我们工作开展则基于移动目标不确定性模型。.不确定数据分类在图中，我们提出一种分类法来阐述数据挖掘方法怎么根据是否考虑数据不准确性来分类。有很多通用数据挖掘技术，如:关联规则挖掘、数据分类、数据聚类。当然这些技术需要经过改进才能用于处理不确定性技术。此外，我们区分出数据聚类两种类型：硬聚类和模糊聚类。硬聚类旨在通过考虑预期数据来提高聚类准确性。另一方面，模糊聚类则表示聚类结果为一个“模糊”表格。模糊聚类一个例子是每个数据项被赋予一个被分配给数据簇任意成员概率。不确定性数据挖掘：一种新研究方向图.不确定性数据挖掘一种分类毕业设计（论文）外文资料翻译系部：计算机科学与技术系专业：计算机科学与技术姓名：学号：外文出处：ProceedingofWorkshoponthe（用外文写）ofArtificial,Hualien,TaiWan,指导老师评语：签名：年月日不确定性数据挖掘：一种新研究方向不确定性数据挖掘：一种新研究方向MichaelChau,ReynoldCheng,andBenKao：商学院，香港大学，薄扶林，香港：计算机系，香港理工大学九龙湖校区，香港：计算机科学系，香港大学，薄扶林，香港摘要由于不精确测量、过时来源或抽样误差等原因，数据不确定性常常出现在真实世界应用中。目前，在数据库数据不确定性处理领域中，很多研究结果已经被发表。我们认为，当不确定性数据被执行数据挖掘时，数据不确定性不得不被考虑在内，才能获得高质量数据挖掘结果。我们称之为“不确定性数据挖掘”问题。在本文中，我们为这个领域可能研究方向提出一个框架。同时，我们以UK-means聚类算法为例来阐明传统K-means算法怎么被改进来处理数据挖掘中数据不确定性。.引言由于测量不精确、抽样误差、过时数据来源或其他等原因，数据往往带有不确定性性质。特别在需要与物理环境交互应用中，如：移动定位服务[]和传感器监测[]。例如：在追踪移动目标（如车辆或人）情境中，数据库是不可能完全追踪到所有目标在所有瞬间准确位置。因此，每个目标位置变化过程是伴有不确定性。为了提供准确地查询和挖掘结果，这些导致数据不确定性多方面来源不得不被考虑。在最近几年里，已有在数据库中不确定性数据管理方面大量研究，如：数据库中不确定性表现和不确定性数据查询。然而，很少有研究成果能够解决不确定性数据挖掘问题。我们注意到，不确定性使数据值不再具有原子性。对于使用传统数据挖掘技术，不确定性数据不得不被归纳为原子性数值。再以追踪移动目标应用为例，一个目标位置可以通过它最后记录位置或通过一个预期位置（如果这个目标位置概率分布被考虑到）归纳得到。不幸地是，归纳得到记录与真实记录之间误差可能会严重也影响挖掘结果。图阐明了当一种聚类算法被应用追踪带有不确定性位置移动目标时所发生问题。不确定性数据挖掘：一种新研究方向图（a）表示一组目标真实数据，而图（b）则表示记录已过时这些目标位置。如果这些实际位置是有效话，那么它们与那些从过时数据值中得到数据集群有明显差异。如果我们仅仅依靠记录数据值，那么将会很多目标可能被置于错误数据集群中。更糟糕地是，一个群中每一个成员都有可能改变群质心，因此导致更多错误。图数据图图.（a）表示真实数据划分成三个集群（a、b、c）。（b）表示有些目标（隐藏）记录位置与它们真实数据不一样，因此形成集群a’、b’、c’和c”。注意到a’集群中比a集群少了一个目标，而b’集群中比b集群多一个目标。同时，c也误拆分会为c’和c”。(c)表示方向不确定性被考虑来推测出集群a’，b’和c。这种聚类产生结果比（b）结果更加接近（a）。我们建议将不确定性数据概率密度函数等不确定性信息与现有数据挖掘方法结合，这样在实际数据可利用于数据挖掘情况下会使得挖掘结果更接近从真实数据中获得结果。本文研究了不确定性怎么通过把数据聚类当成一种激励范例使用使得不确定性因素与数据挖掘相结合。我们称之为不确定性数据挖掘问题。在本文中，我们为这个领域可能研究方向提出一个框架。文章接下来结构如下。第二章是有关工作综述。在第三章中，我们定义了不确定性数据聚类问题和介绍我们提议算法。第四章将呈现我们算法在移动目标数据库应用。详细地实习结果将在第五章解释。最后在第六章总结论文并提出可能研究方向。.研究背景近年来，人们对数据不确定性管理有明显研究兴趣。数据不确定性被为两类，即已存在不确定生和数值不确定性。在第一种类型中，不管目标或数据元组存在是否，数据本身就已经存在不确定性了。例如，关系数据库中元组可能与能表现不确定性数据挖掘：一种新研究方向它存在信任度一个概率值相关联[,]。在数据不确定性类型中，一个数据项作为一个封闭区域,与其值概率密度函数（PDF）限定了其可能值[,,,]。这个模型可以被应用于量化在不断变化环境下位置或传感器数据不精密度。在这个领域里，大量工作都致力于不精确查找。例如，在[]中，解决不确定性数据范围查询索引方案已经被提出。在[]中，同一作者提出了解决邻近等查询方案。注意到，所有工作已经把不确定性数据管理研究结果应用于简化数据库查询中，而不是应用于相对复杂数据分析和挖掘问题中。在数据挖掘研究中，聚类问题已经被很好研究。一个标准聚类过程由个主要步骤组成：模式表示，模式定义，模式相似度量定义，聚类或分组，数据抽象和造工评核[]。只有小部分关于数据挖掘或不确定性数据聚类研究被发表。Hamdan与Govaert已经通过运用EM算法解决使混合密度适合不确定性数据聚类问题[]。然而，这个模型不能任意地应用于其他聚类算法因为它相当于为EM定制。在数据区间聚类也同样被研究。像城区距离或明考斯基距离等不同距离测量也已经被用来衡量两个区间相似度。在这些测量大多数中，区间概率密度函数并没有被考虑到。另外一个相关领域研究就是模糊聚类。在模糊逻辑中模糊聚类研究已经很久远了[]。在模糊聚类中,一个是数据簇由一组目标模糊子集组成。每个目标与每个簇都有一个“归属关系度”。换言之，一个目标可以归属于多个簇，与每个簇均有一个度。模糊C均值聚类算法是一种最广泛使用模糊聚类方法[,]。不同模糊聚类方法已被应用在一般数据或模糊数据中来产生模糊数据簇。他们研究工作是基于一个模糊数据模型，而我们工作开展则基于移动目标不确定性模型。.不确定数据分类在图中，我们提出一种分类法来阐述数据挖掘方法怎么根据是否考虑数据不准确性来分类。有很多通用数据挖掘技术，如:关联规则挖掘、数据分类、数据聚类。当然这些技术需要经过改进才能用于处理不确定性技术。此外，我们区分出数据聚类两种类型：硬聚类和模糊聚类。硬聚类旨在通过考虑预期数据来提高聚类准确性。另一方面，模糊聚类则表示聚类结果为一个“模糊”表格。模糊聚类一个例子是每个数据项被赋予一个被分配给数据簇任意成员概率。不确定性数据挖掘：一种新研究方向图.不确定性数据挖掘一种分类例如，当不确定性被考虑时，会发生一个有意思问题，即如何在数据集中表示每个元组和关联不确定性。而且，由于支持和其他指标概念需要重新定义，不得不考虑改进那些著名关联规则挖掘算法(如Apriori)。同样地，在数据分类和数据聚集中，传统算法由于未将数据不确定性考虑在内而导致不能起作用。不得不对聚类质心、两个目标距离、或目标与质心距离等重要度量作重新定义和进行更深研究。．不确定性数据聚类实例在这个章节中，我们将以不确定性数据挖掘例子为大家介绍我们在不确定性数据聚类中研究工作。这将阐明我们在改进传统数据挖掘算法以适合不确定性数据问题上想法。.问题定义用S表示V维向量xi集合，其中i=到n，这些向量表示在聚类应用中被考虑所有记录属性值。每个记录oi与一个概率密度函数fi(x)相联系，这个函数就是oi属性值x在时间t时刻概率密度函数。我们没有干涉这个不确定性函数实时变化，或记录概率密度函数是什么。平均密度函数就是一个概率密度函数例子，它描述“大量不确定性”情景中是最糟情况[]。另一个常用就是高斯分布函数，它能够用于描述测量误差[,]。聚类问题就是在数据集簇Cj（j从到K）找到一个数据集C，其中Cj由基于相似性平均值cj构成。不同聚类算法对应不对目标函数，但是大意都是最小化同一数据集目标间距离和最大化不同数据集目标间距离。数据集内部距离最小不确定性数据挖掘：一种新研究方向化也被视为每个数据点之间距离xi以及xi与对应Cj中平均值cj距离最小化。在论文中，我们只考虑硬聚类，即，每个目标只分配给一个一个集群一个元素。.均值聚类在精确数据中应用这个传统均值聚类算法目在于找到K(也就是由平均值cj构成数据集簇Cj)中找到一个数据集C来最小化平方误差总和（SSE）。平方误差总和通常计算如下：KjxijjixcC()||.||表示一个数据点xi与数据集平均值cj距离试题。例如，欧氏距离定义为：Viiiyxyx()一个数据集Ci平均值（质心）由下面向量公式来定义：jCiijixCc()均值聚类算法如下：.AssigninitialvaluesforclustermeansctocK.repeat.fori=tondo.AssigneachdatapointxitoclusterCjwhere||cj-xi||istheminimum..endfor.forj=toKdo.RecalculateclustermeancjofclusterCj.endfor.untilconvergence.returnC收敛可能基于不同质心来确定。一些收敛性判别规则例子包括：（）当平方误差总和小于某一用户专用临界值，（）当在一次迭代中没有一个目标再分配给不同数据集和（）当迭代次数还达到预期定义最大值。.K-means聚类在不确定性数据中应用为        毕业设计（论文）外文资料翻译系部：计算机科学与技术系专业：计算机科学与技术姓名：学号：外文出处：ProceedingofWorkshoponthe（用外文写）ofArtificial,Hualien,TaiWan,2005指导老师评语：签名：年月日不确定性数据挖掘：一种新的研究方向1不确定性数据挖掘：一种新的研究方向MichaelChau1,ReynoldCheng2,andBenKao31：商学院，香港大学，薄扶林，香港2：计算机系，香港理工大学九龙湖校区，香港3：计算机科学系，香港大学，薄扶林，香港摘要由于不精确测量、过时的来源或抽样误差等原因，数据不确定性常常出现在真实世界应用中。
        目

文档预览结束

找同类相似 下载到手机