随着大数据时代到来,数据的获取、传输和存储融入了人类生产生活的各个领域,而大数据核心价值来自对它的分析和理解.然而面对如此海量、高速和异构的数据,人类的认知和理解能力不能满足价值发现的需要.粒计算作为一种模拟人类知识表示和问题求解的近似数据分析基本范式,其优点是在解决特定问题时能够选择合适粒度,而不总是基于最细粒度的原始数据进行计算.所以,粒计算通常能够以更高的效率获得有效解.近年来,基于密度峰值的聚类方法DPClust以其准确性和高效性受到广泛关注.我们发现了DPClust背后的哲学思想是:邻域数据之间的地位并不平等,而是处于偏序关系之中.基于DPClust中间结果构建的引领树结构正是这种偏序关系的具体实现.本文利用这种偏序关系和引领树结构,层层递进地研究了它们在大数据聚类和分类问题中的应用,主要贡献如下:(1)针对静态海量数据,提出一种基于密度峰值的高效多粒度聚类方方法DenPEHC.该方法不需要迭代寻优以进行类簇的“拆分”或者“合并”,而是通过分析曲线的形状和引领树结构,在每个可能的聚类层次上直接到聚类结果.并且提出一种网格粒化框架,使得DenPEHC可以对高维海量数据进行层次聚类.这项研究工作包含三个部分:(一)使用的分布和线性拟合方法来选择聚类层次中的中心,而每个聚类层次由曲线中的“台阶”确定;(二)分析作为DPClust聚类方法中间结果的引领树结构,高效构建聚类层次;以及(三)设计一个框架使得DenPEHC在大量属性可以按照其语义进行分组的情况下,对高维海量数据聚类.DenPEHC通过简单地将每个中心点从它的父节点断开就可以构建聚类层次,其时间复杂性仅为(8)),这里8)是类簇的个数.与研究前沿相比,本文提出的DenPEHC方法在实验中表现出了极具潜力的高效性、准确性和鲁棒性.(第3章)(2)将DenPEHC聚类的思想扩展到高速演化数据流,得得到一种能够检测非球形类簇和及时提供聚类结果的数据流聚类方方法.引领树结构以粒计算方式转换为胖节点引领树FNLT,FNLT是数据流聚类问题中,一种对当前数据新颖的概要表达方式,具有良好的可解释性.新到数据可以快速融入到动态演化的FNLT结构中,因此随时到来的新数据可以及时地获得聚类结果.在新数据到来和提交聚类结果的间隔时间段,混合了新到数据点的现存FNLT进一步粒化成一棵新的FNLT,以保持总的节点数目不变.当前数据流的FNLT通过“融入–粒化–淡出”机制得到实时维护.同时,利用任意中心点对之间存在的偏序关系和鞅理论,进行改变点检测,以发现数据流中主要模式的漂移.与几个数据流聚类的前沿方法相比,本文提出的流聚类方法DP-Stream表现出很有竞争力的准确性和效率.(第4章)(3)将DenPEHC和DP-Stream方法中构建信息粒(即类簇)的方法带入“合理粒化准则”的框架下,提出一种基于局部密度度的最优粒化模型(LoDOG).LoDOG具有以下明显的优点:(一)它可以检测到任意形状的信息粒,(二)在引领树已经构建完毕的情况下,它能够以时间复杂性得到最优粒化方案.然后,我们用一小部分位于潜在流形骨架上的地标点描述任意形状的信息粒,从而准备好根据信息粒近似重建原始数据集.提出一个差异性度量来评价重建数据的质量,并且讨论了LoDOG信息粒的可解释性.理论分析和实验评价展示了LoDOG粒化模型和信息粒流形描述子的有效性.(第5章)(4)基于LoDOG构建的最优引领森林,提出一种非迭代式标签传播算法LaPOLeaF,并将其扩展到大数据据决策性分析中去.首先提出一个合理的假设:处于同一个邻域的数据点之间不是点对点的平等关系,而是由局部密度和点对之间的距离确定的偏序关系;每个中心点的标签可以看着是其追随者的贡献.从这个假设出发,提出了一种基于最优粒化森林的高效非迭代式标签传播算法(LaPOLeaF).该算法克服了传统基于图的半监督学习方法的两个主要弱点,即,(一)迭代优化算法导致低效性,(二)新到数据的标签需要重新构建图并且重新运行迭代优化.进一步研究了分块距离矩阵计算方法,几个中间结果的并行计算方法,以及局部敏感哈希算法,扩展LaPOLeaF使之可用于大数据的半监督学习.理论分析和在大规模数据实验显示了LaPOLeaF方法极具竞争力的准确性和高效性.(第6章)本文所有研究工作强调了大数据分析的准确性和高效性.所提出的这些方法都具有一个共同的特征,那就是这些方法是非迭代的.所有方法中,除了计算距离矩阵这一步,其余所有的过程都以线性时间复杂性完成,使得这一系列的研究工作非常适用于大数据分析场景.另一个亮点是,在本文所有方法中,多粒度思想均有非常直观和简单的实现方式,使得所有方法都便于在时间约束和精确性之间作出权衡.