聚类作为数据挖掘/知识发现的基础方法,其应用涉及工程领域(如机器学习、模式识别、信号处理、信息压缩)、计算机科学(包括Web挖掘、信息检索、图像分割等)、生命医学领域的基因功能识别与疾病诊断、天文与地球学(星体分类、地理地貌分析等)、社会科学领域(人的行为模式分析、社会网络分析、犯罪心理学、考古发现等)以及经济领域中的客户特征与购买模式分析、企业分类和股票趋势分析等。在聚类的广泛应用中,由于测量不精确、采样误差、过时数据源以及人们的认知不足等造成数据本身存在模糊、随机等各种不确定性。数据的不确定性给数据的聚类分析带来巨大挑战。一方面,在传统数据预处理中采用消除数据的不确定成分,往往会影响聚类结果的质量,另一方面,已有的面向确定性数据聚类算法中引入数据的不确定性特征会带来算法复杂性问题。聚类作为数据挖掘的重要领域,在不确定数据聚类技术方面也得到了广泛研究。学者们通过采用概率密度函数对不确定对象进行建模并扩展已有聚类算法,提出了包括K-Means算法的改进版本UK-Means、改进的EM算法、基于密度的FDBSCAN算法以及面向层次聚类的FOPTICS算法;Benjamin等结合蒙特卡洛数据库系统中的可能世界方法对不确定数据进行聚类;而Aggarwal和Yu针对数据流中不确定数据设计了相应算法UMicro,Chau等应用UK-Means算法解决移动对象的不确定聚类,并产生较好结果。上述算法的共同基础在于将不确定性成分(概率密度函数表示)引入距离度量中,势必引起在期望距离计算时,增加算法的时间复杂度,同时距离的近似计算也制约了算法的扩展性。在相关文献中通过计算公式进行变换(类似力学中的平行轴定理)、最小——最大剪枝法以及切面函数法来简化上述期望距离的计算复杂度,但由于采用松弛约束条件的方法以求得计算量的减少,往往导致算法的扩展能力较弱。不确定数据聚类研究作为未来发展趋势,其所面对的最直接的挑战,就是数据规模(聚类计算要处理的)呈指数倍的增长。目前在针对可能世界实例的聚合查询(相当于聚类)研究,主要涉及Top-k聚合算法,分别采用分枝定界、计算松弛降低计算复杂性。由于数据采集技术、数据库技术以及Internet等技术的发展,在巨量数据上进行聚类分析凸显其重要性。已有的聚类算法扩展到大规模数据上,常常采用随机采样、数据压缩、基于格的方法、分而治之等方法解决计算时间或存储空间上复杂度。另外聚类的研究对多属性、多特征的高维、动态变化(如随时间变化)数据是学术界关注的另一种计算的复杂性,如对基因数据、金融数据、卫星图像数据以及Web文档数据聚类分析。维度诅咒(curse of dimensionality)使得聚类中许多距离函数计算在高维空间不再有效。本文针对不确定数据环境下,研究了如何对不确定数据进行表达、不确定数据间相似性度量,在此基础上,提出了面向不确定数据集的聚类算法,并对算法有效性进行验证。具体内容包括:(1)提出了不确定域的概念和基于不确定域的几种聚类算法。在建立不确定域的概念基础上,提出了两类聚类算法和基于不确定域的聚类有效性度量。第一类是基于不确定域的硬C均值聚类算法,包括U-aHCM和U-sqHCM,U-aHCM算法是离线更新聚类中心(即批更新聚类中心),而U-sqHCM是在线更新聚类中心(即当有一个数据对象从一个分配到另一聚类中,则更新数据对象变动的两个聚类);第二类是基于不确定域的模糊C均值聚类算法,也包括两种:U-sFCM和U-eFCM。这些算法基于提出的数据的不确定域概念较好地处理数据的不确定性。(2)提出了基于超矩形的数据不确定域概念和基于超矩形不确定域的聚类算法。基于超矩形不确定域聚类算法能够更灵活处理数据的不确定性和发现不同形状与大小的聚类(簇),本论文主要提出了三类基于超矩形不确定域的聚类算法:SU-aHCM与SU-sHCM、SU-sFCM与SU-eFCM以及SU-sPCM与SU-ePCM。(3)为了解决基于超矩形不确定域聚类算法中不适定问题(ill-posed problem),提出了基于正则化的超矩形不确定域概念,构建了两类基于Lx正则化的超矩形不确定域聚类算法。一类是基于L2正则化的超矩形不确定域模糊C均值聚类算法(L2 -SU-sFCM与L2 -SU-eFCM),另一类基于L1正则化的超矩形不确定域模糊C均值聚类算法(L1—SU—sFCM与L1—SU—eFCM),该算法体现对数据对象稀疏化,从而更能发现数据结构关系。(4)为了表达模糊C均值聚类算法中隶属函数的不确定性,本论文结合直觉模糊集理论与方法提出了基于直觉模糊集的聚类算法,包括基于基于直觉模糊集的模糊C均值聚类算法(IFS-sFCM)和基于直觉模糊和信息熵的模糊C均值聚类算法(IFS-eFCM)。