多粒度大数据分析方法：以引领树和云模型为例 pdf下载

　　第1章绪论
信息技术渗透到人类生产和生活的各个领域，催生了相对*立于自然界和人类社会之外的第三元空间——数据空间。数据空间由来自不同渠道的多种类型数据构建而成。数据按照其产生的来源，大致可以分成三种：**种是社会活动数据，它是关于人类社会各种活动的记录，如社交网络、电子商务、网上办公、个人移动通信等；第二种是自然测量数据，指的是对自然界（包括宏观世界和微观世界）各种实体和现象进行测量及记录而产生的数据，如天文学、气象学、生物学、高能物理等科学研究获得的数据；第三种是计算机程序生成的数据，这是一种较为*特的数据，它指为了某个特定的目的，由计算机根据算法和程序直接产生的数据。这类数据的特点是生成速度非常快，但由于其包含的信息可由原始程序加以解释，所以一般不需长期存放。典型的例子有通过计算机图形处理器生成的三维动画，或者运用随机算法生成的人工数据集等。根据国际数据公司（International Data Corporation，IDC）的预测，全球数字信息总量将在2016～2025年增长10倍，达到大约163ZB（1ZB=270B）[1]。
面对如此浩瀚的数据海洋，全世界各个国家、各个领域研究人员都认识到大数据挖掘中蕴含的模式或规律具有巨大价值。与此同时，由于大数据具有体量巨大、增长迅速、结构多样、价值稀疏等特点，也给挖掘任务的主要承担者——信息技术领域的研究人员和工程技术人员，带来了前所未有的挑战。当现存的信息技术基础设施（计算机硬件、通信网络和系统软件等）都难以满足大数据存储、传输和分析等需求的时候，就需要结合自身的研究领域，分别从下一代网络、存储技术、中央处理器、图形处理器（graphics processing unit，GPU）并行计算、编程语言和计算模型等方面研发新的解决方案。
粒计算是一种关于问题描述和求解的方法论，它*先针对问题所处的客观世界建立起以用户为中心的概念，以便我们对待解决的问题形成抽象或概括的认识。以此为基础，在求解问题的过程中用粒度合适的“粒”作为计算对象，从而在保证获得所需精度的解的条件下，尽可能提高求解的时空效率。
自1997年Zadeh发表**篇关于信息粒度的文章[2]以来，国内外研究人员对粒计算理论和模型进行了深入的研究，并与其他计算智能和机器学习的技术相结合，取得了丰硕的研究成果。
粒计算应用于大数据分析的**步，就是构建多层次的信息粒结构[3]，经过这一过程得到的信息粒的粒度称为计算粒度。将信息粒结构作为输入，经过进一步的挖掘或学习，可以高效地得到一个问题的近似解。这个解也相应的有一个粒度，称为解的粒度。一般情况下，计算粒度和解的粒度并不一定相同，而是根据具体的学习算法存在一定的映射关系。发现这个映射关系具有重要意义，因为我们可以借助它来实现从解的粒度到计算粒度的反推，从而避免为了获取一个较粗粒度的解，在没有必要的细粒度上进行计算，造成计算资源浪费和求解时间延迟。
合适的粒度常常由问题本身及问题背景决定，这对设计基于粒计算的数据处理框架很重要。举一个关于时间的例子，X先生问他的朋友Y：“你什么时候回国的？”回答这个问题所选择的时间粒度其实跟Y回国的时间到现在有多久密切相关。如果没超过一天，那么Y可能会说：“昨天中午”；如果有十来天了，Y可以说：“上周”；再如果是Y回国好几年了，X才得知消息，那么“2019年”就可以是一个满意的答案了。注意到上面几个答案具有不同的粒度，分别是天、周和年。如果不采用合适的粒度，而是统一用计算机上常见的时间戳格式来回答，如“2020年9月27日下午7时18分”，就显得不合乎常理。
人工智能学科的诞生，是因为人们试图从人类思维和生物界的一些规律中得到启发，创建相应的计算模型，人工神经网络、基因计算、群体智能等都是成功的范例。粒计算作为问题求解的一种方法论，则在更高层次上模拟了人类的思维规律，将其运用到当前世界面临的大数据挑战中，并取得了一些不错的成果。
1.1大数据
1.1.1大数据的定义
为了应对数据规模快速增长带来的机遇和挑战，Nature杂志在2008年9月4日率先提出“大数据”的概念[4]。Gartner公司将大数据定义为：“大数据是巨量、高速和多样性的信息资源，它需要合算地、创新地进行信息处理以增强洞察力和决策力”。维基百科对大数据的定义是：“大数据是这样大而复杂的数据集的汇集，以致使用当前的数据库管理工具和数据处理应用程序很难有效地处理它”。另外，国际商业机器公司（International Business Machines Corporation，IBM）也从数据量大、增长快速和来源多样的角度对大数据进行了描述性定义。
根据上述定义，可以总结出大数据*基本的三个特征:
（1）数据量大。虽然有人认为数据量大并非大数据本质，但提到大数据时，数据的大小通常都应该在PB到EB级，至少要在GB以上a。
（2）高速增长。每天都有大约2.5EB（2.5×1018B）的数据产生出来，目前世界上90％的数据都是在过去两年中产生的。除了数据量急剧增大，很多情况下还要求数据处理要“及时”甚至“实时”。
（3）结构多样。大数据中的数据结构多样，如有文本、声音、视频、传感器信号以及点击流数据等。通常一个综合的数据处理和分析任务中，会存在多种类型的数据，这使得任务难度大大增加。
以上三点就是公认的大数据3V[volume（体量），velocity（速度），variety（多样性）]特性。如果说大数据的特性还有第四个V，那么对其含义就有不同的解释了。微软公司认为是“价值”（value），IBM认为是“真实性”（veracity），还有学者认为是“灵活性”（vitality）。吴信东教授提出了大数据的HACE法则[5]，认为大数据的特征是异构（heterogeneous）、自治（autonomous）、复杂（complex）和演化（evolving）。怀进鹏院士认为大数据计算具有近似性（inexact）、增量性（incremental）和归纳性（inductive）的3I特征[6]。
1.1.2大数据处理研究现状
当前，有关大数据处理的研究可以归结为以下四个方面:大数据处理范式、大数据处理算法、大数据处理平台以及大数据分析应用。其中，大数据处理范式是指研究者针对大数据与传统“小数据”的区别而从宏观上提出的数据处理基本原则，如李国杰教授的“计算围绕数据转”、陈俊龙教授等总结的大数据技术和大数据处理方法学[7]、李天瑞教授等提出大数据分析的PICKT解决方案[8]，均属于大数据处理范式。大数据算法包括数据的共享、检索、学习挖掘等方面，其中学习和挖掘是本书的主题，我们稍后会重点介绍近年来*具代表性的大数据挖掘算法与模型。大数据处理平台包括Apache软件基金会资助的众多开源文件管理系统和数据管理与数据挖掘项目（如Hadoop、MapReduce、Spark、Storm等），以及近年来各个高校和互联网技术（internet technology，IT）厂商推出的深度学习框架（如Tensorflow、Torch/Pytorch、Caffe、PaddlePaddle等）。大数据分析应用是指结合实际生产生活场景，在数据基础设施和问题建模、算法实现的基础上，开发出基于大数据的智能应用。
大数据算法包括数据的共享、检索、学习挖掘等方面。例如，Zhang等[9]针对多模态数据（文本和图像）进行判别性结构化子空间学习，并以此为基础完成多模态信息检索；大数据共享中的广播问题是指将大块的数据从一个源节点广播到一组目标节点，优化目标是传输时间*短。Wu等[10]将此问题建模为构造一棵*优锁步广播树（lock step broadcast tree，LSBT），该方法具有较低的时间复杂性，获得了更短的*长完成时间。由于本书关注大数据的挖掘和分析，因此我们重点调研一些这方面的相关算法，而对共享、检索和隐私保护等方面的工作不予展开。
Song等[11]从理论分析和实验运行的角度综合比较了基于MapReduce框架的多种精确和近似K*近邻（K-nearestneighbor，KNN）算法实现，归纳总结了各种方法的优点、缺点和应用场合。Zhang等[12]针对密度峰值聚类（density peak clustering，DPC）算法[13]需要先计算距离矩阵而妨碍其应用于大数据环境下的问题，使用局部性敏感哈希（locality sensitivity Hashing，LSH）方法[14]结合MapReduce编程模型，同时运用“非精确性”和“并行性”两种大数据处理方法论，使得DPC算法可以成功应用到大数据场景下。
近期，为了将大数据和算力的作用发挥到极致，国内外研究机构纷纷研发出参数达到千亿、万亿级的大模型，如OpenAI的GPT-3和北京智源人工智能研究院的“悟道”。大模型在文本、图片、音视频生成与识别等感知任务上达到了几乎与人类相当的水平。但是大模型相对于**深度学习并没有颠覆性的进化，只是由于数据量和算力上的优势，获得了更强大的表征能力，从而在有限任务上达到了*佳性能。当使用GPT-3这样的语言大模型尝试完成编程这种注重逻辑思维的任务时，只能正确解决测试集中28.8％的问题，由此可见，大模型距真正的人工智能还有很长的路要走。
1.2基于粒计算的大数据分析
1.2.1粒计算概述
从哲学高度来看，粒度贯穿于人类对任何对象的认知、度量、概念形成和推理中。因此，在智能系统的设计中，粒度起着至关重要的作用[15]。Zadeh教授1997年就提出粒计算是模糊信息粒化、粗糙集理论和区间计算的超集，同时是粒数学的子集。姚一豫教授概括地认为，粒计算是在解决问题的过程中使用“粒度”的所有理论、方法、技术和工具的“标签”[15]。粒计算并不是一个具体的模型或方法，而是一种方法论[16]。它包含了很多具体的模型，如模糊集、粗糙集、区间集、邻域系统、云模型、商空间等。
1.粒的定义
粒是粒计算的基本要素，它是依照不可区分性或相似性聚集到一起的对象集合。集合中的子集、论域中的等价类、文章中的章节和系统的模块等，都是粒的例子[17]。此前的粒一般定义在论域上，对应于结构化数据中的行。我们认为，在列（属性）上也可以形成粒，具体的实现方法有属性选择和特征抽取等。
粒计算的**步是确定具体粒化模型，然后相应地构建粒表示。可以从两个方向粒化：构建和分解。构建指的是将更细（低层）的粒合并成为较粗（高层）的粒；分解则相反，是将较粗（高层）的粒分解成更细（低层）的粒[17]。
粒化的目的是从原始数据中得到合适于问题解决的粒。
钱宇华[18]系统地研究了复杂数据的粒化机理。文献[19]中粒具有更广泛的含义，它包含了简单类型的信息粒，如不可区分或相似的类，以及复杂类型的功能粒，如决策规则集、分类器、聚类、agents或agents组等。宏观上看，数据粒化算法包含以下两步[20]：合并*相容的两个粒为一个；重复直到满足一个抽象标准。粒化过程中有一点很关键，即两个对象可以划分到同一个粒内需要满足什么条件。这也是粒的相容程度的定义，这个相容程度可以基于相似性，也可以是密度驱动的。
2.粒化方法
构建信息粒的主要方法有模糊信息粒化[2]、粗糙集近似[21]、商空间法[22，23]、基于聚类的粒化[18]和云模型法[24，25]等。下面分别简要介绍前四种模型，云模型在第2章介绍。
（1）模糊信息粒化[2]。尽管清晰粒在很多方法和技术中非常重要，但粒度的模糊性更能体现人类处理信息的特征。粒的主要类型包含可能性的、真实性的和概率性的。广义约束是模糊信息粒化理论（theory of fuzzy information granulation，TFIG）的出发点，粒的特征是由定义它的广义约束来刻画的。