计算机导论

计算机起源

• 计算机是一种能够对各种信息进行存储和处理的工具。
• 广义上说，计算机是一种不需人的直接干预，自动完成各种算术和逻辑运算的工具。
• 早期的计算工具：手指（十进制）、结绳、算筹（祖冲之算圆周率）、算盘（唐朝开始）
• 机械计算机：1642，法国，布莱斯·帕斯卡（Blaise Pascal），加法器（Pascaline）
• 1673，德国数学家，戈特弗里德·莱布尼兹（Gottfried Wilhelm von Leibniz），步进计算器（乘法器）（Stepped Reckoner）（虽然叫乘法器，但是能够加减乘除），包含阶梯轴（莱布尼茨轮）
• 1804，法国，约瑟夫·雅卡尔（Joseph Jacquard），基于穿孔卡片的提花织布机（Jacquard Loom），可程式化机器的里程碑
• 1822，英国数学家，查尔斯·巴贝奇（Charles Babbage），差分机（Difference Engine）
• 1833，英国数学家，查尔斯·巴贝奇，计算机之父，分析机（Analytical Engine）模型，该模型包括了现代计算机所具有的5个基本组成部分，没造完
• 英国，拜伦之女，爱达·拉芙拉斯（Ada A. Lovelace Byron）为分析机贡献一生（翻译巴贝奇的《分析机概论》，建议分析机用二进制，指出分析机可以编程，发现编程的基本要素，如循环、子程序），被誉为世界上第一位程序员。为纪念她，1979年美国国防部的一种编程语言命名为Ada语言。
• 机电计算机：1866，美国统计学家，赫尔曼·霍勒瑞斯（Herman Hollerith），制表机（Tabulating Machine）；1896创建制表机公司（Tabulating Machine Company, TMC），1911年与另外两家公司合并为CTR，后改名IBM
• 1934_{1941，德国，康拉德·祖斯，全部采用继电器的通用计算机Z-3，世界上第一台完全由程序控制的机电计算机（Z-1：1934}1938，纯机械；Z-2：因战争搁浅）
• 1939~1942，约翰·阿塔诺索夫（John V. Atanasoff），ABC计算机（Atanasoff-Berry Computer），被遗忘的计算机之父，最早的电子管计算机（核心部件：控制器）
• 1940~1942，阿兰图灵，巨人（Colossus），破译德国恩尼格码机（Enigma）密码
• 1944，美国，霍华德·艾肯（Howard H. Aiken），受分析机启发造机电计算机Mark-I (ASCC)；1945~1947造Mark-II，均由IBM赞助（Mark-I部分使用继电器，Mark-II全部使用继电器），1945年bug这个词在Mark-II研制过程中诞生了
• 格瑞斯·霍普海军少将，编译语言之母，美国海军计算机化之母，IT界十大最有远见的人才中唯一的女性，发现了计算机程序中的第一个bug，创造了计算机世界最大的Bug——千年虫（Y2K），实现了第一个编译语言和编译器，创造了世界上第一种商业编程语言COBOL
• 电子计算机：1946年2月15日，ENIAC (Electronic Numerical Integrator and Computer)，世界上第一台电子数字计算机，美国宾夕法尼亚大学。莫奇利提出总体设计，埃克特负责工程技术，戈尔斯坦负责组织协调。程序是外插型的而不是存储程序型
• 1951年6月14日，埃克特-莫奇利计算机公司生产UNIVAC，交付美国人口统计局使用

计算机发展

• 第一代计算机（电子管时代1946-1958）：物理器件使用电子管，内存储器使用汞延迟线，使用穿孔卡片机作为数据和指令的输入设备，用磁鼓纸带或卡片作为外存储器；运算速度为每秒几千到几万次，使用机器语言和汇编语言编写程序；主要用于科学计算
• 第二代计算机（晶体管时代1958-1964）：晶体管代替了电子管；磁芯存储器作主存，磁盘与磁带作辅存；运算速度提高到每秒几十万次基本运算，在软件方面配置了子程序库和批处理管理程序，出现了FORTRAN、COBOL、ALGOL等高级语言及其相应的编译程序；应用于科学计算、数据处理、实时控制
• 第三代计算机（中小规模集成电路1964-1971）：物理器件使用中、小规模的集成电路；内存储器用半导体代替了磁芯体；使用微程序设计技术简化I/O处理机；外存使用磁带、磁盘；结构化程序设计语言，多道程序、并行处理、虚拟存储系统以及功能完备的操作系统，大量面向用户的应用程序 > 摩尔定律：1965，牙膏厂名誉董事长戈登·摩尔，单位面积晶体管数目每18-24个月（1969年修正为18个月）增加一倍，成本下降一半；1995，牙膏厂董事会主席罗伯特·诺伊斯预见摩尔定律受到经济因素——摩尔第二定律
• 第四代计算机（大规模、超大规模集成电路1971-）：微处理器或超大规模集成电路取代了普通集成电路，光学字符识别和条形码等技术输入，互联网广泛应用，形成所谓的地球村······
• 第五代计算机：使计算机能够具有像人一样的思维、推理和判断能力，向智能化发展，实现接近人的思维方式；在智能计算机领域完成了大量的基础性研究工作，促进了人工智能和机器人技术的发展；包括神经网络计算机、生物计算机、光子计算机、量子计算机等非电子计算机

计算机应用

• 超算：1976，美国克雷公司，Cray-1，每秒2.5亿次；西摩·克雷主导开发Cray-1至Cray-3，由于技术瓶颈没有Cray-4

• 2009，天河一号；2016，神威·太湖之光；2018，Summit；2021，Fugaku（富岳）

• 发展趋势：巨型化、微型化、网络化、智能化

• 分类：按用途分为通用计算机和专用计算机；按所处理对象的表现形式分为模拟计算机、数字计算机和混合型计算机；按综合性能指标分为巨型机、大型机、小型机、微型机（个人计算机）、工作站和服务器 ## 计算机学科

• 计算机理论和结构：奠基人为阿兰图灵（1936年发表论文论可计算数及其在判定问题中的应用奠定了计算机理论基础，1950年10月发表了论文计算机和智能，并提出了图灵测试）和冯诺依曼（1944年夏天，戈尔斯坦偶遇冯·诺依曼，后者了解了正在研制中的ENIAC，并提出过建议；冯诺依曼于1945年总结了EDVAC方案）

• EDVAC奠定了现代计算机基本结构：明确了计算机的5个组成部分（存储器、运算器、控制器、输入设备、输出设备），采用二进制计数和计算，采用存储程序方式

• 中央处理器包括运算器和控制器

• 中国国家最高科学技术奖获得者：吴文俊、王选、金怡濂

• 1956年，中科院计算技术研究所，国营738厂，103机

• 1958年8月1日，103机完成了四条指令的运行，标志着由中国人制造的第一架通用数字电子计算机正式诞生

• 计算机相关协会：美国计算机学会(ACM)，电气和电子工程师协会(IEEE)（目前全球最大的非营利性专业技术学会），计算机系统协会(USENIX)，管理科学与运筹学协会(INFORMS)，美国科学促进会(AAAS)，工业工程和应用数学协会(SIAM)

• 数学物理相关协会：美国数学学会(MAA)，美国统计学会(ASA)，美国物理学会(APS)，美国物理联合会(AIP)

• 船建、材料相关协会：拖拽水池联合会(ITTC)，船舶与海洋结构联合会(ISSC)，美国材料研究学会(MRS)

• 计算机学科中国学会：中国计算机学会(CCF)，中国电子学会(CIE)，中国通信学会(CIC)，中国运筹学会(ORSC)，中国中文信息学会(CIPS)

• 计算机学科扩充后也称计算学科

• 计算机专业教学：1962年美国普渡大学首开计算机学位课程，1991年IEEE-CS/ACM发布Computing Curricula (CC1991)，目前到CC2020；1956年哈尔滨工业大学首开计算装置与仪器专业，1998年统一为计算机科学与技术专业，2001年增设软件工程专业，2015年增设网络空间安全专业，2019年增设人工智能专业

程序设计语言

概述

计算机指令、符号指令、高级编程语言——本质：不同抽象程度的程序表达

组成

语言要素：字符集、词汇、语法、语义 四大基本成分：数据成分（描述程序所涉及的 对象——数据）、运算成分（用以描述程序中所包含的运算，算术运算、逻辑运算、字符串运算等）、控制成分（用以控制程序中所含语句的执行顺序）、传输成分（用以描述程序中的数据传输操作） - 数据成分：数据是客观事物在计算机内的（格式化）表示，是程序所操作和处理的对象，程序中的数据通常应该先说明、后使用 - 运算成分：运算符、表达式 - 控制成分：提供一种基本框架，三种基本控制结构——顺序结构、条件选择结构、重复结构 - 翻译程序：源程序到目标程序，常见的有——汇编语言通过汇编器到机器语言、高级语言通过编译器到机器语言或汇编语言、高级语言通过解释器边解释边执行不产生目标程序 - 编译程序：把源程序编译为机器语言目标程序后，再由计算机运行，如C/C++、Java。解释程序：解释器直接解释并且执行源语言程序，不产生目标程序，如BASIC、VB、Python、JavaScript - 编译器与解释器 - 国产编译器：华为方舟编译器（一个统一编程平台，包含编译器、工具链、运行时）

发展

• 1946 机器语言（ENIAC）计算机的指令系统，使用二进制编码。现已不直接用机器语言编制程序
• 1951 汇编语言 （Grace Hopper, 助记符来表示操作码/符和操作数地址）
• 1957 高级语言（IBM, John Backus, FORTRAN），目前主流
• 1970 结构化语言（Niklaus Wirth, Pascal）
• 1995 面向对象语言（Sun, James Gosling, Java）类、对象
• 2006 图形化编程

高级语言范式（分类法）

• 过程式语言：基于动作的语言，顺序执行的操作命令序列（FORTRAN、ALGOL、BASIC、Pascal、C）
• 面向对象语言：数据封装到对象，问题对象之间的交互（Smalltalk、Ada、C++、Java、C#）
• 函数式语言：关注函数计算，而不是计算机状态改变（LISP、ML、Haskell）
• 逻辑语言：数理逻辑约束的列举，描述事实与规则，而非具体解决过程（Prolog）

数据结构与算法

概述

• 数据结构——数据的特性以及数据之间存在的关系
• 1968，美国，唐·欧·克努特教授，《计算机程序设计技巧》第一卷《基本算法》，第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。
• 图书馆的书目检索自动化问题——线性的数据结构
• 人机对弈问题——一棵倒置的树
• 多岔路口交通灯的管理问题——图
• 基本概念：数据——所有能输入到计算机中并被计算机程序处理的符号的总称，数据元素——组成数据的基本单位（又称为结点或记录），数据项——一个数据元素可由多个数据项组成，是数据不可分割的最小单位（又称为字段或域），数据结构——一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的一门学科（三要素：对象、关系、操作），数据对象——性质相同的数据元素的集合，是数据的一个子集（如一个班的成绩表），数据结构——数据元素集合（也可称数据对象）中各元素的关系/相互之间存在特定关系的数据元素集合
• 数据结构的三方面内容：逻辑结构、存储结构（物理结构）、数据的运算
• 算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构
• 顺序存储结构：逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。即只存储结点的值，不存储结点之间的关系。通常顺序存储结构是借助于语言的数组来描述的
• 线性表：由n个性质相同的数据元素构成的有限序列。线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间的关系是线性的，存在着序偶关系。
• 线性表的基本运算：表的初始化、求表长、存取表中的结点、查找结点、插入结点、删除结点等
• 顺序表是线性表的顺序存储表示的简称，它指的是，“用一组地址连续的存储单元依次存放线性表中的数据元素”，即以“存储位置相邻”表示 位序相继的两个数据元素之间的前驱和后继的关系（有序对 \(<a_{i-1},a_i>\)）””，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址
• 顺序表特点：以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系；是随机存取的存储结构，只要确定了存储线性表的起始位置，线性表中的任一数据元素可随机存取；数据中的元素间的地址是连续的；数组中所有元素的数据类型是相同的
• 顺序表优劣：可以随机定位任意元素，直接实现定位操作；可用数组直接定义顺序存储结构的线性表，便于程序设计/需预先确定数据元素最大个数，即预先分配相应的存储空间，不便于扩充表；插入与删除运算的效率很低
• 顺序存储适用于不常进行插入和删除操作、表中元素相对稳定的线性表

典型数据结构

栈和队列：两种特殊的线性表 - 栈（stack）：在表中，允许插入和删除的一端称作栈顶（Top），不允许插入和删除的另一端称作栈底（Bottom），当栈中无数据元素时，称为空栈。 - 入栈/进栈（push），出栈/退栈（pop），后进先出（LIFO） - bottom为null表示栈不存在，top=bottom表示空栈，非空栈中的栈顶指针始终在栈顶元素的下一个位置上 - 算术表达式求值（操作数、运算符、界限符） - 递归（直接、间接）——汉诺塔 - 队列（queue）：在表中，允许插入的一端称作队尾（Rear），允许删除的另一端称作队头（Front） - 进队/入队，出队，FIFO - 顺序队列、循环队列 - 使用一维数组来作为队列的顺序存储空间，另外再设立两个指示器：一个为指向队头元素位置的指示器front，另一个为指向队尾的元素位置的指示器rear - 作业排队问题 - 树：节点（node），根节点（root），边（edge），父节点，度，叶节点，兄弟节点，子树（除根节点外的其余结点被分为多个不相交的集合，每个集合本身也是树），路径，祖先 - 深度（depth）/层次（level），规定根节点深度为0 - 高度（height）：由该节点到叶节点的最长路径的长度，所有叶节点高度为0 - 树的高度/深度：其根节点的高度 - 树的层次数：树的高度加一 - 二叉树，空树，真二叉树（所有节点的子节点数为0或2），满二叉树（最后一层节点的度都为0，其他节点的度都为2），完全二叉树（从根节点至倒数第二层是一颗满二叉树，最后一层叶节点靠左对齐） - 优先队列：键值/优先级，最大/小优先队列——银行服务、网络带宽管理 - 优先队列的实现-二叉堆（一颗完全二叉树）：任意节点的键值小于等于其子节点的键值；对于任意子树，其根结点为键值最小的结点； - enqueqe（将新加入的元素插入为最右侧的叶结点，向上调整，将新加入的元素的键值与其父结点的键值比较，调整至合适的位置使二叉树满足二叉堆的性质），deqeueuMin（删除根结点，用最右侧的叶结点替代根结点，将根结点键值与左、右子树的根结点键值相比较，与其中较小者交换；重复上述操作，直到其为叶结点，或键值小于等于左、右子树的根结点键值），getMin

算法基本概念

• 波斯，数学家，数学家花拉子密（al-Khwārizmī）
• 算法的特征：输入（零个或以上）、输出（一个或以上）、明确性、有限性、有效性
• 时间复杂度、空间复杂度
• O-Notation, \(\Omega-\) Notation, \(\Theta-\) Notation, o-Notation, \(\omega-\) Notation

算法·图探索

• 1736，欧拉，戈尼斯堡七桥问题，图论元年 妖怪图：每个点关联三条边；边染色需用四种颜色，使公共顶点的边异色；任意切断三条边不会断裂成两个有边的子图（除单点）

图论基本概念

• 无向图，顶点，边，顶点集，边集，度，悬点（度为1），悬边，奇点，偶点，正则图（每点度都相同），完全图
• 有向图，起点/尾，出边，终点/头，入边，有向完全图，出度，入度
• 子图，真子图，生成子图/支撑子图（子图中包含了原图所有的顶点），导出子图（子图中顶点包含了原图中所有的边），平凡子图
• 无向树，高（树中最长路的长），树叶，分支点，树枝，有根树
• 生成树，连通图生成树不唯一

广度优先搜索

1. 从顶点𝑆开始标记，将𝑆标记为0。
2. 找出与𝑆相邻的顶点，给它们做标记1(𝑆)（广度优先搜索算法给出的顶点标记指明了该顶点与𝑆之间的距离，以及该顶点的从𝑆到它的一条最短路上的前驱）。
3. 考虑每个与标记为1的顶点𝑉𝑉相邻的未标记的顶点，把这些顶点加1，标记为2(𝑉)。
4. 按(3)的方式继续进行，直到𝐺中没有与已标记顶点相邻的未标记顶点为止，算法结束。 使用队列

深度优先搜索

1. 标记源点𝑠；从𝑠出发搜索𝑠的邻接点𝑢。
2. 以𝑢作为新的出发点，标记𝑢并记录𝑢的父亲。
3. 搜索𝑢的邻接点。若𝑢有未标记过的邻接点𝑣，则将𝑣作为新的出发点重复(2), (3)步骤；若𝑢没有未标记过的邻接点，则退回𝑢的父亲结点并重复(3)。
4. 重复上述步骤直至图中所有顶点均已被访问为止。 使用栈

算法·贪心算法

简介

• 工厂生产问题：按照商品生产结束时间对商品进行排序，优先选择结束时间早的商品，贪心算法正确性与贪心策略有关
• 背包问题：贪心算法不一定对，但在工程中是快速算法（可以优化为1/2-近似算法），可以利用动态规划求最优解
• 硬币找零问题，美国邮票问题，贪心算法正确性与问题设定有关

最短路算法

Dijkstra算法：将顶点集合𝑉分为两个集合，𝑆表示已经求得最短路径的顶点集合，构建优先级队列𝑄=𝑉−𝑆。每一步将𝑄中与源点距离最小的顶点𝑢加入集合𝑆，更新𝑢相邻顶点与𝑠的距离。直至𝑆中包含所有顶点。

应用

Dijkstra算法：单源最短路径，带权图，地图寻址、最优路线 Prim和Krustal算法：最小生成树，带权图，管道铺设、最小开销 哈夫曼树和哈夫曼编码：将字母转化为不等长二进制字符串，降低存储量，信道传输、文件存储

图灵机

定义

重要性：描述了可计算的极限，计算机从原则上讲是有限制的，用程序我们可以解决什么问题，奠定了现代数字计算机的基础

基本概念：五个组成部分 - 一组有限的符号，\(\{s_1,\cdots ,s_n\}\) - 一条无限长的纸带，纸带被划分为一个接一个的小格子 - 一个读写头，可以在纸带上左右移动，可以读写当前所指的格子上的符号 - 一组状态寄存器， \(\{q_s,q_1,\cdots ,q_m,q_h\}\) ，保存图灵机当前所处的状态 - 一套控制规则（指令集），根据当前机器所处的状态和当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态

三个主要性质：抽象性（表示计算机的假想装置而非实用的计算技术），简洁性（根据规则表操作磁带上的符号），自动性（自动计算程序）

基础图灵机

多带图灵机：输入纸带，工作纸带，输出纸带 用 \((\Gamma, Q, \delta)\) 元组表示，其中：\(\Gamma\) 为一组有限的符号集，\(Q\) 为一组有限的状态集，\(\delta\) 为一个状态转移函数

图灵机变体

• \(\{0,1, , \Box \}\) 和复杂的语言系统：如果函数 \(f\) 可由复杂符号集计算，那么可用简单符号集计算（ASCII编码）
• 多带图灵机可用单带图灵机计算
• 双向纸带在 \(T(n)\) 时间内计算，可用单向纸带在 \(4T(n)\) 时间内计算
• 非确定型图灵机：对于任意一个非确定型图灵机𝑀，存在一个确定型图灵机 \(\tilde{M}\)，使得它们的语言相等

邱奇-图灵论题（Church Turing Thesis）：逻辑和数学中的各类计算模型均可由图灵机来表示。

计算机组成

“中国计算机之母”——夏培肃

计算机组成主要研究计算机系统结构的逻辑实现和工作原理，包括机器内部的数据流和控制流的组成及逻辑设计等。

基础知识

冯·诺伊曼计算机的特点 - 指令和数据都用二进制代码表示 - 指令和数据都以同等地位存放于存储器内，并可按地址寻访 - 指令在存储器内顺序存放，且由操作码和地址码组成：操作码用来表示操作的性质；地址码用来表示操作数在存储器中的位置 - 存储程序：将事先设计好、用以描述计算机解题过程的程序如数据一样，采用二进制形式存储在机器中；计算机在工作时自动高速地从机器中逐条取出指令加以执行

指令集

• 计算机语言中的基本单词称为指令，一台计算机的全部指令称为该计算机的指令集

• 机器语言：二进制代码，一般由操作码和操作数两部分组成；不同型号的计算机其机器语言是不相通的，按着一种计算机的机器指令编制的程序，不能在另一种计算机上执行

• 汇编语言：用人类容易理解和记忆的字母、单词来代替一个特定的指令；用助记符代替机器指令的操作码，用地址符号或标号代替指令或操作数的地址；在不同设备中，对应着不同的机器语言指令集，通过汇编过程转换成机器指令；特定的汇编语言和特定的机器语言指令集一一对应，不同平台之间不可直接移植

• 复杂指令集（Complex Instruction Set Computer, CISC）：使用大量的指令，包括复杂指令。如x86。

• 精简指令集（Reduced Instruction Set Computer, RISC）：使用少量的指令完成最少的简单操作。如ARM，MIPS，RISC-V。

CPU

指令的执行过程：通常，执行一条MIPS指令，包含如下5个处理步骤：取指（IF）（从指令存储器中读取指令）；译码（ID）（指令译码的同时读取寄存器）；执行（EXE）（执行操作或计算地址）；访存（MEM）（从数据存储器中读取操作数）；写回（WB）（将结果写回寄存器）

• 时钟周期与始终频率：时钟周期（时钟间隔的时间），时钟频率（时钟周期的倒数）
• 一个程序需要的CPU执行时间（简称“CPU时间”）：CPU时间=指令数×CPI×时钟周期=指令数×CPI/时钟频率
• 指令数：执行该程序所需的总指令数量
• CPI（Clock Cycle per Instruction）：每条指令的时钟周期数
• 单周期：在一个时钟周期内完成一条指令的所有的工作。简单容易理解。单周期设计中每条指令的时钟周期必须相同，时钟周期要由执行时间最长的那条指令决定；对于更复杂的指令，比如浮点乘法，问题就更大了；等待一条指令完全执行完成了以后再执行下一条指令，会导致硬件资源的浪费（指令的执行过程将是5个步骤依次执行。当指令执行到某个步骤时，剩下4个步骤的硬件资源将被闲置）
• 多周期：一条指令的执行需要经过多个时钟周期，执行不同指令所需要的时钟周期数可能不同。更有效地使用时钟周期——时钟周期由最慢的指令步骤决定，允许更快的时钟频率、不同的指令采取不同数量的时钟周期数、指令可以在不同的时钟周期内多次使用同一个功能单元。CPU的实现更为复杂，需要额外的内部状态寄存器，和更复杂的控制单元
• 流水线：在多周期CPU设计的基础上，利用各阶段电路间可并行执行的特点，让各个阶段的执行在时间上重叠起来
• 多核：在一枚处理器中集成两个或多个完整的计算引擎；处理器能支持系统总线上的多个处理器，由总线控制器提供所有总线控制信号和命令信号

存储设备

• 局部性原理：在任何时间内，程序访问的只是地址空间相对较小的一部分内容
• 时间局部性：如果某个数据项被访问，那么在不久的将来它可能再次被访问（如循环结构中的指令、变量）
• 空间局部性：如果某个数据项被访问，那么与它地址相邻的数据项可能很快也将被访问（如访问顺序的指令、遍历数组）
• 存储系统：计算机中由存放程序和数据的各种存储设备、控制部件及管理信息调度的设备（硬件）和算法（软件）所组成的系统
• 存储层次：在计算机体系结构下存储系统层次结构的排列顺序

• 寄存器（Register）：CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果，包括通用寄存器、专用寄存器和控制寄存器
• 随机存取存储器（Random Access Memory，RAM）：RAM工作时可以随时从任何一个指定的地址写入（存入）或读出（取出）信息，一旦断电所存储的数据将随之丢失
• 静态随机存取存储器（Static Random Access Memory，SRAM）：所谓的“静态”，是指这种存储器只要保持通电，里面储存的数据就可以恒常保持
• 动态随机存取存储器（Dynamic Random Access Memory，DRAM）：所储存的数据需要周期性地刷新
• 闪存（Flash Memory）：一种非易失性存储器，即断电数据也不会丢失；一种电子式可清除程序化只读存储器的形式，允许在操作中被多次擦或写的存储器；支持随机存取，比磁盘快100~1000倍
• 磁盘（Magnetic Disk）：非易失性存储器，早期计算机使用的磁盘是软磁盘（Floppy Disk，简称软盘），如今常用的磁盘是硬磁盘（Hard disk，简称硬盘）

操作系统

概述

有效管理计算机软硬件资源，合理组织计算机工作流程，控制程序执行，提供多种服务功能及界面，方便用户使用计算机的系统软件，是计算机中最靠近硬件的软件

发展

• 1945~1955：真空管和穿孔卡片
• 1955~1965：晶体管和批处理系统
• 1965~1980：集成电路和多道程序设计
• 1980年至今：个人计算机

多道程序设计：是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插的运行。多道程序设计技术的根本目的是为了提高 CPU 的利用率，充分发挥计算机系统部件的并行性。

Windows：高度兼容： 所有程序拥有相同的或相似的基本外观，其高度兼容性保证了它拥有一个丰富的软件资源库；完全封闭：它的源代码均封闭，用户和开发者，被限制在封闭的开发环境中

MacOS：安全稳定，绘图，Unix风格的内存管理，先占式多任务处理

Linux：源码公开，稳定安全

功能

处理器管理（进程调度），存储管理，设备管理，文件管理，用户接口

• 处理器管理：在一段时间内，只能有一个进程在CPU中执行。处理器管理的基本功能：作业和进程调度，进程控制，进程通信：同步方式和互斥方式；通信机制 > 进程（Process）：一个计算机程序关于某数据集的一次执行过程，系统进行资源分配和调度的一个可并发执行的独立单位，在进程看来，自己独占计算机系统，并可以调用 OS 提供的服务。 > 同步关系：多个进程为完成同一个任务相互协作 > 互斥关系：多个进程为争夺有限的系统资源进入竞争状态

• 进程的特性：动态性（进程具有生命周期，经历创建、运行、消亡等过程），并发性（多个进程可以并发地执行），独立性（进程既是系统中资源分配和保护的基本单位，也是系统调度的独立单位）
• 进程与程序关系：进程是程序的一次动态执行活动，而程序是进程运行的静态描述文本；程序是一个软件，可以长期存在，而进程是一次执行过程；一个程序可以对应多个进程
• 进程与线程：线程是程序执行中一个单一的顺序控制流程，是程序执行流的最小单元，是处理器调度和分派的基本单位
• 进程的三种典型状态：运行态（running），占有处理器正在运行；就绪态（ready）具备运行条件，等待系统分配处理器以便运行；等待/阻塞态（blocked）不具备运行条件，正在等待某个事件的发生。

• 运行态->阻塞态：等待资源/事件等；如等待外设传输，或人工干预。

• 阻塞态->就绪态：资源得到满足；如外设传输结束；人工干预完成。

• 运行态->就绪态：运行时间片到；出现有更高优先权进程。

• 就绪态->运行态：选择一个就绪进程运行。

• 调度准则：面向用户/面向系统

• 调度方式：不可剥夺式/可剥夺式

• 调度策略：FCFS RR（轮转）SPN（最短进程优先）SRT（最短剩余时间优先 ）HRRN（最高响应比优先）等。

Round-Rubin调度策略

各就绪进程轮流运行一小段时间，这一小段时间称为时间片。当一个进程耗费完一个时间片而尚未执行完毕，调度程序就强迫它放弃处理机，使其重新排到就绪队列末尾。

进程的同步与互斥

• 两个或两个以上的进程要协作完成一个任务，它们之间就要互相配合，需要在某些动作之间进行同步
• 进程间另一种关系是互斥，这种关系一般发生在两个或两个以上的进程竞争某些同时只能被一个进程使用的资源的情况下
• 在一段时间内只能允许一个进程访问的资源称为 临界资源 ，如打印机、磁带机、光盘刻写机、绘图仪等
• 进程执行的访问临界资源的程序段称为临界段或互斥段

进程间互斥控制方法

锁可以用于控制临界段的互斥执行。锁有两个状态，一个是打开状态，另一个是关闭状态，故锁可以用布尔变量表示。在C中，锁变量可以定义为char或int类型变量

问题：锁的关闭操作包含测试和关闭两个操作，是否会被中断？解决方案：原子操作：专用锁操作指令，交换指令

死锁：两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去

产生死锁的四大必要条件： - 资源互斥 (Mutual exclusion)：每个资源同时只能被一个进程使用 - 占有并请求 (Hold and wait)：已经得到资源的进程还能继续请求新的资源 - 资源不可剥夺 (No preemption): 已被分配的资源只能由当前占有者主动地释放该资源 - 环路等待 (Circular wait): 死锁发生时，系统中存在一条环路，环路上的每个进程都在等待下一个进程所占有的资源

存储器管理

基本功能：内存分配，地址映射（逻辑地址、物理地址），内存保护（上界地址值、下界地址值），内存扩充（虚拟存储技术）

设备管理

计算机外设种类众多，而且各种设备的传输速度差异很大 ，很难开发一种通用的、一致的解决方案

基本功能：缓冲区管理，设备分配，设备驱动，设备无关性

文件管理

在大多数应用中，文件是一个核心成分，除了实时应用和一些特殊 应用外 应用程序的输入都是通过文件来实现的。

基本功能：文件存储空间的管理，文件操作的一般管理，目录管理，文件的读写管理和存取控制

用户接口

操作系统为用户操作提供良好的硬件接口。

基本接口类型：命令界面（DOS, Unix, windows命令行），程序界面（系统调用界面），图形界面（windows窗口，Linux的X-window）

附加功能和服务

• 网络：TCP/IP
• 系统工具：shell: command line interface, ls, find/search,man；系统管理:ps,shutdown,mount,mkdir；软件开发:compilers, debuggers
• OS 库：I/O: data buffering and formatting；Math: common utilities, APIs: (cos,sin,abs,sqrt)
• 信息保护与安全：访问控制，只有经过授权的用户才能访问系统，用户只能访问属于自己的信息；信息流：限制系统中的信息流动方向

软件工程

软件（Software）是一系列按照特定顺序组织的计算机数据和指令，是计算机中的非有形部分 软件特征：软件是逻辑的而不是有形的系统元件；软件具有与硬件完全不同的特征；软件是被开发或设计的，而不是被制造的；虽然软件产品正在向基于构件的组装前进；大多数软件仍然是定制的；软件不会“磨损”

发展： - 1946：计算机问世 - 1957：高级程序语言 - 1958：软件，约翰·图基 - 1966：软件危机 - 1967：软件工程，北约 - 1992：面向对象，伊万·雅各布森，Objectory - 1997：统一建模语言，克里斯·科布林 - 2001：敏捷软件开发，杰夫·萨瑟兰

软件工程是（1）将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中；（2）在（1）中所述方法的研究

软件工程的关注焦点是软件质量和软件成本

软件成本占比最高的是维护

软件生存周期是指软件产品从考虑其概念开始到产品交付使用，直到最终退役 软件开发模型是软件开发的全部过程、活动和任务的结构框架。 瀑布模型：自上而下，相互衔接

软件需求分析

软件需求 ① 用户解决问题或达到目标所需的条件或能力。 ② 系统或系统部件要满足合同、标准、规范或其它正式规定文档所需具有的 条件或能力。 ③ 一种反映上面① 或 ② 所描述的条件或能力的文档说明。

软件项目失败的最重要的五个原因：需求不完整，缺少客户的参与，缺少资源，期望值过高，缺少高层的支持

确定系统必须具有的功能和性能，系统要求的运行环境，并且预测系统发展的前景。即以一种清晰、简洁、一致且无二义性的方式，对一个待开发系统中各个有意义的方面的陈述的一个集合。

客户需求说明 \(\neq\) 软件需求

软件需求分析中的七个任务：起始（与利益相关者的初步交流，沟通存在的问题，期望解决方案等），获取（向客户明确软件的目标，明确软件如何满足业务的要求），细化（开发精确的需求模型，由用户场景建模，解析每个用户场景提取最终用户可见的业务实体），协商（协商资源和客户要求之间的矛盾，和客户协商需求的优先级），规格说明（在基于计算机系统的环境下使用术语进行规格说明），确认（检查规格说明保证无歧义的说明了所有的系统需求），需求管理（在整个生存周期中，控制和跟踪需求以及需求变更）

实例：

软件系统设计

在 [IEEE610.12 90] 中，软件设计定义为软件 系统或组件的架构、构件、接口和其他特性的定义过程及该过程的结果。 软件设计是 软件质量形成的地方。好的设计应该具有如下三个特点 - 设计必须实现在分析模型中包含的所有明确要求，必须满足客户所期望的所有隐含要求； - 设计必须对编码人员、测试人员及后续的维护人员是可读可理解的； - 设计应提供该软件的完整视图，从实现的角度解决数据、功能及行为等各领域方面的问题

• 软件设计主要为分解设计D-design（Decomposition）。即将软件映射 为各构件 体系结构设计描述软件系统如何构成以及其构件如何一起工作 构件级设计细化描述每个模块定义模块控制对象形成程序代码

体系结构设计

数据流体系结构--管道和过滤器模式 - 特点：输入数据经过一系列计算构件和操作构件的变换形成输出数据 - 应用：媒体播放器，编译器

调用和返回体系结构--主程序/子程序模式 - 特点：目标功能被分解为一个控制层次，主程序调用一组程序构件，这些构件又去调用其他构件 - 应用：Safe Home Access 软件

构建级设计 - 构件是系统中模块化的、可部署的和可替换的部件，该部件封装了实现并对外提供一组接口 - 类是现实世界或思维世界中的实体在计算机中的反映，它将数据以及这些数据上的操作封装在一起定义为一种类型 - 对象是具有类类型的变量。类是对象的抽象，而对象是类的具体实例。类是抽象的，不占用内存，而对象是具体的，占用存储空间。类是用于创建对象的蓝图，它是一个定义函数和变量的软件模板。在构件级设计中，每个类都会得到详细阐述，包括所有属性和与其实现相关的操作 - 领域模型（Domain Model）是对领域内的概念类或现实世界中对象的可视化表示

构建级设计

分析类类型 - 实体类：用于对必须存储的信息和相关行为进行建模 - 边界类：位于系统与外界的交界处 - 控制类：负责协调边界类和实体类的工作

对象时序图如下：

软件程序编码

什么是软件编码： 软件编码是一个复杂而迭代的过程，包括程序设计和程序实现 软件编码要求 - 正确地理解用户需求和软件设计思想 - 正确地根据设计模型进行程序设计 - 正确地而高效率地编写和测试源代码 软件编码是设计的继续，会影响软件质量和可维护性。

出错率：每百行源程序的错误数 对于少于100个语句的小段程序，源代码行数与出错率是线性相关的。 随着程序的增大，出错率以非线性方式增长

程序设计风格：程序首先是正确，其次是考虑优美和效率；对所有的用户输入，必须进行合法性和有效性检查；不要单独进行浮点数的比较；所有变量在调用前必须被初始化；改一个错误时可能产生新的错误，因此修改前首先考虑其影响；最好使用括号以避免二义性；应保持注释与代码完全一致，处理过程的每个阶段和典型算法前都有相关注释说明，但是不要对每条语句注释

编码的总体原则：代码可读性优先级高于执行效率（除非有特定质量要求），简化复杂度

软件测试策略

软件测试是为了发现程序中的错误而执行程序的过程 软件开发过程是一个自顶向下，逐步细化的过程；测试过程是依相反的顺序安排的自底向上，逐步集成的过程 测试的过程按照四个步骤进行即单元测试集成测试，确认测试和系统测试

软件测试技术

白盒测试（结构测试）： - 测试应用程序的内部结构或运作，而不是测试应用程序的功能 - 以编程语言的角度来设计测试案例。通过输入数据验证数据流在程序中的流动路径，并确定适当的输出

基于状态图的测试定义了软件单元可以采用的一组抽象状态，并通过将其实际状态与预期状态进行比较来测试该单元的行为

黑盒测试（功能测试）： - 通过测试来检测每个功能是否都能正常使用。在测试中，程序被看作不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的情况下，在程序接口进行测试 - 黑盒测试只检查程序功能是否按照需求规格说明书的规定正常使用，程序是否能适当地接收输入数据而产生正确的输出信息

等价类划分方法 - 将所有可能的输入空间划分为等价类，以便期望程序在同一等价类的每个输入上有相同表现 - 步骤：(1) 将输入参数的值划分为等价类 (2) 从每个类中选择测试输入值

边界值划分方法：关注输入参数的边界值。从每个等价类的“边缘”或“异常值”中选择元素例如0，最小最大值，空集，空字符串和null

软件文档

文档-确保软件的正确使用和有效维护 用户文档：告诉用户如何一步步地使用软件包 通常包含教程指导用户熟悉软件包的各项特性 系统文档：定义软件本身，目的是为了让原始开发人员之外的人能够维护和修改软件包；系统文档需要记录软件开发的四个阶段——分析（记录收集到的相关信息并记录信息的来源 需求和选用的方法必须用基于它们的推论来清楚表述），设计（记录软件用到的工具，如最终版本结构图），实现（记录代码的每个模块，代码应该使用注释和描述头尽可能详细地形成自文档化），测试（记录每种测试的方法和结果） 技术文档：技术文档描述软件系统的安装和服务，其中安装文档描述软件如安装在每台计算机上，如服务器和客户端，服务文档描述了如果需要系统应该如何维护和更新

密码学

概述

密码学：研究编制密码和破译密码的技术科学。数学和计算机科学的分支，包括信息论、计算复杂性理论、统计学、组合学、抽象代数以及数论。

密码学保证消息的保密性、完整性、真实性

发展（古典密码学与近代密码学） - 公元前5世纪：加密机械（斯巴达，密码棒） - 公元前1世纪：替换加密（凯撒） - 公元9世纪：频度分析（阿拉伯） - 1553：多表替换（替换表，意大利密码学家吉奥万·贝拉索） - 1919：电子加密系统（恩格玛，德国发明家亚瑟·谢尔比乌斯）

古典加密：对称加密的雏形，对称（双方共享密钥）。现实：古典密码都已经被破解

发展（现代密码学） - 1975：数据加密标准（DES），美国国家标准局将Data Encryption Standard颁布为国家标准 - 1976：Diffie-Hellman 密钥交换（图灵奖2015），第一个密钥交换算法 - 1977：RSA算法（图灵奖2002），麻省理工学院的罗纳德·李维斯特（Ron Rivest）阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）提出了第一个比较完善的公钥密码体制 - 1986：多方安全计算（图灵奖2000），普林斯顿大学的姚期智提出的在无可信第三方情况下，能够安全地进行多方协同计算的理论框架 - 2005：基于属性的加密（ABE），最先由Waters 提出，是一种公钥加密方案。实现了加密数据的细粒度访问控制，即数据拥有者可以指定谁可以访问加密的数据，数据拥有者对数据具有完全的控制权 - 2005：容错学习问题（哥德尔奖2018）由Oded Regev 在 2005 年提出 。求解LWE问题的时间开销是指数级的，即使是对量子计算机也没有任何帮助，故 LWE 困难性被用作创建公钥密码系统 - 2009：全同态加密（FHE），IBM的 Craig Gentry 提出的同态加密算法。可以在没有密钥的情况下，把密文任意组合形成新的密文，并且新的密文可以完美的被还原成明文 - 2013：不可区分混淆（iO）-密码学皇冠上的明珠，是最有可能实现的安全混淆器。混淆后的程与混淆前功能一样，并且无法从混淆代码中提取出任何有效信息（密钥、模型等）。iO可以用来保护机器学习的模型和算法。

分类：

古典密码学

最早的密码——密码棒

送信人先绕棍子卷一张纸条，然后把要写的信息打纵写在上面，接着打开纸送给收信人。如果不知道棍子的粗细是不能解密里面的内容的

凯撒密码

平移

单表替换密码

相比于凯撒密码使用了随机排列

单表替换密码的破解

频率分析

多表替换密码（维吉尼亚密码）

根据密钥来决定用哪一行的替换表

中国古代密码学 - 商朝末年：“阴书”、“阴符”（姜子牙设计，竖向书写，把一段信息分为三段，从不同路线、时间发出；通过纸条长度判别军方信息） - 春秋战国：《左传》“暗语”（春秋战国，楚国进攻萧国时候，楚国大夫申叔展与萧国大夫还无社有旧交，通过暗语战争结束还无社获救） - 三国时期：“拆字法”（三国时期民谣“千里草，何青青，十日卜，不得生”。其中“千里草”为“董”，“十日卜” 为“卓”，暗指董卓作恶多端） - 唐朝：“拆字法”（唐朝徐敬业起兵反抗武则天，密信写道“青鹅”，其中“青”为“十二月”，“鹅为“我自与”，意思为“起义在12月发起”） - 明朝：戚继光“反切码”（取上字的声母和下字的韵母，“切”出另外一个字的读音，其原理与现代密电码的设计原理完全一样）

现代密码学

基础：ASCII 编码，异或运算

数字加密与分组密码

数据加密标准 (DES) - 1977年成为美国联邦信息处理标准 - 64 位的分组长度和 56 位的秘钥长度 - 初始和末尾有一个置换 - 中间进行 16 轮 Feistel 函数

分组密码 - 以 64bit 的明文为一个单位进行加密 - 秘钥通过固定的移位和置换函数产生16个子秘钥

密码强度： - DES：56位密钥有 \(2^{56}=7 \times 10^{16}\) - AES：明文长度128位，密钥长度128位，192位，256位 有 \(2^{128}=3 \times 10^{38}\)

密码设计的变革

对称密码体制的缺陷 - 加密密钥与相应的解密密钥相同 - 消息的发送方和接收方必须在密文传输之前通过安全信道进行密钥传输

公钥加密体制 - 将传统密码的密钥一分为二，分为加密密钥（公钥）和解密密钥（秘钥） - 公钥是公开的，任何人都可获得 - 私钥保密，需要妥善保存 - 消息的发送方和接收方不再需要通过安全信道进行密钥传输

公开密钥密码体制

• 公开密钥密码体制使用 不同的加密密钥与解密密钥 ，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。
• 两个主要用途：一是解决常规密钥密码体制的密钥分配问题，另一是用于数字签名。
• 最著名的体制：RSA 体制，它基于数论中大数分解问题的体制，由美国三位科学家Rivest, Shamir和Adleman于1976年提出并在1978年正式发表的。

加密密钥 即公开密钥 ) PK、加密算法E和解密算法D都是公开的，只有解密密钥（即秘密密钥）SK是需要保密的 虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。

RSA 算法

公钥密码：RSA算法、 - 公钥：e和n - 私钥：d和n - Bob将公钥发给Alice - Alice用公钥加密 - Alice发送密文 - Bob用私钥解密

每个用户有两个密钥：加密密钥PK={e,n}和解密密钥SK={d,n}

RSA流程： - 取两个素数p和q（保密），计算n=pq（公开），\(\varphi(n)=(p-1)(q-1)\)（保密） - 随机选取整数e，满足 \(\operatorname{gcd}(e,\varphi(n))\)（公开），即e与 \(\varphi(n)\) 互素且小于 \(\varphi(n)\) - 计算d，满足 \(de\equiv 1 (\operatorname{mod}\varphi(n))\)（保密） - 利用 RSA 加密第一步需将明文数字化，并取长度小于 \(\log _{2} n\) 位的数字作明文块。加密算法：\(c=E(m)\equiv m^{e} (\operatorname{mod} n)\) 解密算法：\(D(c)\equiv c^{d} (\operatorname{mod} n)\)

Eve计算秘钥等于求解质因数分解问题，目前算法复杂度为指数级。

中国现代密码学

王小云（清华大学教授、中科院院士） - 提出了密码哈希函数的碰撞攻击理论，即模差分比特分析法，破解了包括 MD5 、SHA-1 在内的5个国际通用哈希函数算法的强碰撞性，导致工业界几乎所有软件系统中MD5和SHA-1哈希函数逐步淘汰

碰撞攻击：找到两个信息块，两者的哈希值相同

信息安全

概述

信息 香农：信息是用来消除不确定性的东西。钟义信：信息是事物运动的 状态及其变化方式。

信息安全 ISO（国际标准化组织，此处转指信息安全管理要求）：在技术上和管理上为数据处理系统建立的安全保护，保护计算机硬件、软件和数据不因偶然和恶意的原因而遭到破坏、更改和泄露。

维基百科：意为保护信息及信息系统免受未经授权的进入、使用、披露、破坏、 修改、检视、记录及销毁。

信息的生命周期

创建、使用、存储、传递、更改、销毁

信息安全理解的两种观点

信息安全分层结构，面向应用的信息安全框架（工程角度）（从上到下）：内容安全，数据安全，运行安全，实体安全

信息安全金三角结构，面向属性的信息安全框架：完整性（确保信息没有遭到篡改和破坏），保密性（确保信息没有非授权的泄漏，不被非授权的个人、组织和计算机程序使用），可用性（确保拥有授权的用户或程序可以及时、正常使用信息）

传统计算机安全

定义：信息本身的保密性（Confidentiality）、完整性（Integrity）和可用性（Availability）的保持，即防止未经授权使用信息、防止对信息的非法修改和破坏、确保及时可靠地使用信息。

其他扩展：可鉴别性（真实性，不可抵赖，可计量性…），可靠性，可控性，隐私…

信息安全和网络安全发展阶段历程

COMSEC通信安全，COMPUSEC计算机安全，INFOSEC信息系统安全，IA信息安全保障，CS/IA网络空间安全/信息保障安全

威胁

特洛伊木马，黑客攻击，后门、隐蔽通道，计算机病毒，拒绝服务攻击，内部、外部泄密，蠕虫，逻辑炸弹，信息丢失、篡改、销毁

安全攻击

主动攻击：更改数据流，或伪造假的数据流。 - 伪装（Masquerade） 即冒名顶替。一般而言，伪装攻击的同时往往还伴随着其他形式的主动攻击 - 重放（Replay）先被动地窃取通信数据，然后再有目的地重新发送 - 篡改（Modification）即修改报文内容。或者对截获的报文延迟、重新排序 - 拒绝服务（Denial of Service）阻止或占据对通信设施的正常使用或管理。针对特定目标或是某个网络

被动攻击：对传输进行偷听与监视，获得传输信息。 - 报文分析：窃听和分析所传输的报文内容 - 流量分析：分析通信主机的位置、通信的频繁程度、报文长度等信息

四种常见攻击：中断，窃听，修改，伪造

ISO/OSI安全体系结构内容

安全服务：在对威胁进行分析的基础上，规定5种标准安全服务：对象认证服务、访问控制安全服务、数据保密性安全服务、数据完整性安全服务、防抵赖性安全服务非否认性安全服务。

安全机制： - 基本机制：加密机制、数字签名机制、访问控制机智、数据完整性机制、认证交换机制、防业务流量分析机制、路由控制机制、公证机制等； - 其它普遍采用的机制：可信功能机制、安全标记机制、事件检测机制、安全审计追踪机制、安全恢复机制等； - OSI 安全体系结构说明了：实现哪些安全服务？应该采用哪些机制？

安全服务与安全机制的关系

安全服务与安全机制有着密切的关系。安全服务体现了安全系统的功能；而安全机制则是安全服务的实现。

一个安全服务可以由多个安全机制实现；而一个安全机制也可以用于实现多个安全服务中。

安全目标统领安全服务

信息安全保障机制

信息安全风险评估 - 低级：对于组织（处理能力、功能）、资产、个人造成有限的轻微的影响 - 中级：对于组织（处理能力、功能）、资产、个人造成严重的影响 - 高级：对于组织（处理能力、功能）、资产、个人造成巨大或灾难性的影响

信息安全保障标准介绍

• 可信计算机系统评估准则（TCSEC）（美国国防部评估标准-美国桔皮书）
• 可信网络解释（TNI, Trusted Network Interpretation）（红皮书）
• 通用准则CC
• 信息技术安全测评标准（欧洲评估标准-欧洲白皮书）
• 信息安全管理标准 BS 7799
• 《计算机信息系统安全保护等级划分准则》
• 信息系统安全评估方法探讨

TCSEC

TCSEC标准是计算机系统安全评估的第一个正式标准，具有划时代的意义。该准则于1970年由美国国防科学委员会提出，并于1985年12月由美国国防部公布。TCSEC最初只是军用标准，后来延至民用领域。

在TCSEC中，美国国防部按处理信息的等级和应采用的响应措施，将计算机安全从高到低分为：A、B、C、D四类八个级别，共27条评估准则。

随着安全等级的提高，系统的可信度随之增加，风险逐渐减少。

我国网络安全和信息安全发展史

• 1986：计算机安全专业委员会
• 1987：国家信息中心信息安全处
• 1994：《中华人民共和国计算机信息系统安全保护条例》（这是我国第一个计算机安全方面的法律，较全面地从法规角度阐述了关于计算机信息系统安全相关的概念、内涵、管理、监督、责任。）
• 1999：国家计算机网络与信息安全管理协调小组
• 2001：国务院信息化工作办公室成立网络与信息安全小组（国家在信息安全的法律、规章、原则、方针上都有对应措施，国家信息安全走向正轨）
• 2015：《中华人民共和国网络安全法》（2014年是中国接入国际互联网 20 周年。20 年来，中国互联网抓住机遇，快速推进，成果斐然。国家对网络安全的重视日益加强。2015年7月6日《中华人民共和国网络安全法》公布，并向社会公开征求意见。）

国家互联网应急中心：https://www.cert.org.cn/

软件系统安全

恶意软件分类

恶意软件（或恶意代码）被定义为经过存储介质和网络进行传播，从一台计 算机系统到另外一台计算机系统，未经授权认证破坏计算机系统完整性的程序或代码。恶意软件（或恶意代码） 两个显著的特点是：非授权性和破坏性

恶意软件（或恶意代码）包括：计算机病毒、蠕虫、特洛伊木马、逻辑炸弹、后门、用户级RootKit、核心级RootKit、脚本恶意代码、僵尸、间谍软件、网络钓鱼软件和恶意ActiveX控件等

恶意软件行为

恶意行为：删除敏感信息；作为网络传播的起点；监视键盘；收集你的相关信息；获取屏幕；在系统上执行指令 程序；窃取文件，如文档 财务 技术 商业机密；开启后门，作为攻击其他计算机的起点 /（肉鸡）；隐藏在你主机上的所有活动；诱骗访问恶意网站

攻击方式：通过共享目录攻击，通过软盘读写攻击，通过光盘读写攻击，通过邮件攻击，通过FTP方式攻击，通过WEB方式攻击，通过漏洞攻击

计算机病毒

• 概念：编制或者在计算机程序中插入的破坏计算机功能或者毁坏数据，影响计算机使用，并能自我复制的一组计算机指令或者程序代码
• 特征：复制、感染、隐蔽、破坏
• 危害：病毒运行后能够损坏文件、使系统瘫痪，从而造成各种难以预料的后果。网络环境下，计算机病毒种类越来越多、传染速度也越来越快、危害更是越来越大
• 防治：以防为主，病原体（病毒库）是病毒防治技术的关键
• 结构：病毒起作用的关键是被感染的程序调用时先执行病毒代码，之后再执行原本的程序代码，病毒通用结构如下：

计算机病毒/恶意软件防治

计算机病毒传播方式：通过不可移动的计算机硬件设备进行传播；通过移动存储设备来传播这些设备包括软盘、磁带等；第三种途径：通过计算机网络邮件、网页、局域网、远程攻击、网络下载）进行传播。计算机病毒可以附着在正常文件中通过网络进入一个又一个系统；通过点对点通信系统和无线通道传播

防治技术的6个层次：检测，清除，预防（被动防治），免疫（主动防治），防范策略，数据备份及恢复

三分技术、七分管理、十二分数据

黑客（Hacker）与骇客（Cracker）

• 入侵 ( Intrusion)：指任何企图危及资源的完整性、机密性和可用性的活动。不仅包括发起攻击的人 如恶意的黑客 取得超出合法范围的系统控制权，也包括收集漏洞信息，造成拒绝服务等对计算机系统产生危害的行为。
• 真正黑客具备四种基本素质：“ Free” 精神、探索与创新精神、反传统精神和合作精神。
• 假冒用户、违法用户、隐秘用户

网络安全大赛--CTF

CTF：Capture The Flag 在信息安全领域的CTF是说，通过各种攻击手法，获取服务器后寻找指定的字段，或者文件中某一个固定格式的字段，这个字段叫做 flag ，其形式一般为 flag{xxxxxxxx}，提交到裁判机就可以得分。最早起源于96年的DEFCON全球黑客大会

• 解题模式（Jeopardy）：以解决网络安全技术挑战题目的分值和时间来排名，通常用于在线选拔赛。题目主要包含逆向、漏洞挖掘与利用、 Web 渗透、密码、取证、隐写、安全编程等类别。
• 攻防模式（Attack-Defense）
• 混合模式（Mix）：结合了解题模式与攻防模式的 CTF 赛制，iCTF国际CTF竞赛

相关法律法规

《刑法》第二百八十五条【非法侵入计算机信息系统罪】：违反国家规定，侵入国家事务、国防建设、尖端科学技术领域的计算机信息系统的，处三年以下有期徒刑或者拘役。

《刑法》第二百八十六条【破坏计算机信息系统罪】：违反国家规定，对计算机信息系统功能进行删除、修改、增加、干扰，造成计算机信息系统不能正常运行，后果严重的，处五年以下有期徒刑或者拘役后果特别严重的，处五年以上有期徒刑。

网络信息安全

网络空间已经成为继陆、海、空、天之外的第五维国家安全领域，网络空间与现实世界相互渗透，推进人机物三元融合

网络安全成为国家战略 - 2013 年 11 月 12 日，中央国家安全委员会正式成立 - 2014 年 02 月 27 日 ，中央网络安全和信息化领导小组成立 - 2017 年 6 月，我国网络安全领域的基本法《中华人民共和国网络安全法》正式实施

提升到国家战略 - 高度重视网络空间安全保障工作 - 加快构建关键信息基础设施安全保障体系 - 全天候全方位感知网络安全态势 - 增强网络安全防御能力和威慑能力 - 要有高素质的网络安全和信息化人才队伍

没有信息化就没有现代化——2018年2月27日，习近平在中央网络安全和信息化领导小组第一次会议上的的讲话 没有网络安全就没有国家安全——2018年4月21日，习近平在全国网络安全和信息化工作会议上的讲话

社会工程学

学会识别社会工程攻击，提高信息安全意识！

常见黑客社会工程学手段 - 恐吓：社会工程学师常常利用人们对安全，漏洞，病毒，木马的敏感性，以权威机构的身份出现，使用危言耸听的伎俩恐吓欺骗计算机用户，以使用户言听计从。（如欺诈短信） - 伪装：用来网络钓鱼的银行页面，例如URL里把真实网址的o换成0，让人真假难辨。 - 恭维：高明的黑客精通心理学，人际关系学等社会工程学方面的知识与技能善于利用人类的本能反应，好奇心、盲目信任等人性弱点，掌握说话的艺术迎合目标对象，投其所好，往往目标人物会友善的对待。 - 说服：以利益引诱，说服内部员工配合攻击者收集信息，如果内部员工本来就心存不满甚至有了报复的念头，攻击就更容易达成，千防万防，家贼难防。

社会工程学防范

• 及时更新操作系统和应用程序软件
• 定期更新系统密码
• 学习社工工程案例
• 检测发现社交网站的泄露信息

计算机网络概述

网络分类与网络示例

互联网（Internet）	互连网（internet）
网络的网络	网络的网络
特指遵循TCP/IP 标准、利用路由器将各种计算机网络互连起来而形成的、覆盖全球的、特定的互连网	泛指由多个不同类型计算机网络互连而成的网络
使用TCP/IP	除TCP/IP外，还可以使用其他协议
是一个专用名词	是一个通用名词

互连网的构成

网络边缘 - 端系统：位于互联网边缘与互联网相连的计算机和其他设备 - 端系统由各类主机（host）构成：桌面计算机、移动计算机、服务器、其他智能终端设备

网络核心 - 由互联端系统的分组交换设备和通信链路构成的网状网络（分组交换：路由器、链路层交换机。通信链路：光纤、铜缆、无线电、激光链路）

网络边缘设备

智能音箱、IP相框、AR眼镜、起搏器和监护仪、安全摄像头、自行车、智能手环、烤面包机、感应床垫、智能汽车、能源监测器、互联网冰箱

接入网概述

接入网目标 - 接入网的目标是将主机连接到边缘路由器上 - 边缘路由器是端系统Host去往任何其他远程端系统的路径上的第一台路由器

如何将终端系统连接到边缘路由器？ - 有线网络接入技术：光纤到户FTTH，以太网同轴电缆，双绞线的DSL，古老的拨号上网 - 无线网络接入技术：WiFi、4G/5G，卫星广域覆盖 - 接入场景：住宅（家庭）接入网，机构（学校、公司）接入网，移动接入网络（WiFi、4G/5G） 各种异构网络通过边缘路由器接入

接入网-光纤到户FTTH

光纤到户FTTH - FTTH: Fiber To The Home - 我国及全球先进地区普遍采用的光纤通信的传输方法 - 分为两类：有源光纤网络AON和无源光纤网络PON - 带宽大、线路稳定

无源光纤网络PON - PON: Passive Optical Network - OLT ：局端的光线路终端 - ONU 光网络单元（如光猫ONT） - 光猫 ONT 通过一个或多个无源分光器，连接到局端的光线路终端 OLT

接入网-数字用户线DSL

数字用户线DSL：Digital Subscriber Line 使用电话线连接到数字用户线接入复用器(DSLAM) - DSL电话线上，语音和数据可以同时传输 - 数据进入互联网，语音连接到电话网

上下行速率不对称 - 24-52 Mbps下行速率，3.5-16 Mbps上行速率

我国已广泛升级为FTTH，国外依然大量使用DSL

接入网-同轴电缆

同轴电缆：Cable - 家庭利用传统有线电视信号线（同轴电缆）接入头端上网 - 多个家庭共享有线电视的头端 - 不对称：高达 40 Mbps 1.2 Gbps 下行传输速率，30 100 Mbps 上行传输速率

混合光纤同轴电缆HFC - 先用同轴电缆接入光纤节点，再用光纤连接到头端

我国已广泛升级为FTTH，美国住宅依然有80% 多使用DSL和同轴电缆接入

接入网-无线接入

无线接入网 通过基站（“接入点”）将终端系统连接到路由器上

无线局域网（WLAN） - 通常在建筑物内或周围（10米） - 802.11b/g/n（WiFi）：11、54、450 Mbps

广域蜂窝接入网 - 由移动蜂窝网络运营商提供（10公里） - 2G/3G/4G/5G等蜂窝网络 - 0.1-1000Mbps速率

接入网-企业和家庭网络

实际的接入网 - 往往采用有线、无线等多种技术的混合 - 甚至 WiFi 和 4G 等多种无线技术的混合接入

有线以太网接入 - 100Mbps、1Gbps、10Gbps等接入速率

无线WiFi接入 - 11、54、450Mbps等

无线WiFi接入点、有线以太网（1Gbps）、路由器防火墙NAT、电缆或DSL调制解调器经常合并在一个盒子里

网络实例-物理介质

传输单元：位（bit） - 在发射机 接收机之间的物理介质上传播的数据的最小单元 - 用比特表示（bit）

物理媒体 - 是指发射机和接收机之间的具体链路介质 - 引导型介质 ：信号在固体介质中传播，例如铜、光纤、同轴电缆 - 非引导型介质 ：信号自由传播，例如无线电（陆地无线电、卫星无线电信道

存储常用字节Byte，K/M/G层级为 \(2^{10}\)进制，传输常用比特Bit，K/M/G层级为 \(10^{3}\) 进制

物理介质-光纤

光纤：玻璃纤维携带光脉冲，每个脉冲一位 高速运行：高速点对点传输（10-100 Gbps） 低错误率：中继器相距很远，对电磁噪声免疫

物理介质-双绞线和同轴电缆

双绞线（Twisted Pair） - 两根绝缘铜线互相缠绕为一对 - 电话线 为 1 对双绞线 - 网线 为 4 对双绞线，广泛用于计算机网络（以太网）双向传输 - 第5类： 100 Mbps-1 Gbps - 第6类： 10Gbps

同轴电缆 - 两根同心铜导线，双向传输 - 电缆上的多个频率通道 - 带宽可达 100Mbps

物理介质-非引导型介质

无线电 - 电磁频谱中各种“波段”携带的信号 - 没有物理“电线” - 不依赖介质的广播 - 半双工（发送方到接收方）

传播环境影响 - 反射 - 物体阻挡 - 干扰/噪声

无线链路类型 - 无线局域网（WiFi）（10-100 Mbps；10米） - 广域（如3/4/5G蜂窝）（在-10公里范围内） - 蓝牙：短距离，有限速率 - 地面微波：点对点；45Mbps - 卫星：同步卫星（36000km高空，280ms的往返时延），低轨卫星（近地）

网络核心

网络核心 - 目标：将海量的端系统互联起来 - 由各类交换机（路由器）和链路，构成的网状网络

分组交换（也称包交换） - 主机将数据分成分组，发送到网络 - 网络将数据分组从一个路由器转发到下一个路由器，通过从源到目标的路径上的链路，逐跳传输抵达目的地

网络核心的两大功能

功能 1 路由 - 全局操作 ：确定数据分组从源到目标所使用的路径 - 需要路由协议和路由算法，产生路由表

功能 2 转发 - 本地操作 ：路由器或交换机将接收到的数据分组转发出去（即移动到该设备的某个输出接口） - 确定转发出去的接口 链路：根据从“入接口”收到分组头中的目的地址查找本地路由表，确定“出接口”

路由器转发模型

网络协议与参考模型

协议设计目的

网络协议 - 为进行网络中的数据交换而建立的规则、标准或约定，即网络协议（network protocol） - 通信双方需要共同遵守，互相理解

三要素 - 语法：规定传输数据的格式（如何讲） - 语义：规定所要完成的功能（讲什么） - 时序：规定各种操作的顺序（双方讲话的顺序）

网络协议设计目的：可靠性、资源分配、拥塞问题、自适应性、安全问题

协议层次结构

层次栈 - 为了降低网络设计的复杂性，大部分网络都组成一个层次栈，每一层都建立在其下一层的基础上

对等实体 - 不同机器上构成相应层次的实体成为对等实体

接口 - 在每一对相邻层次之间的是接口；接口定义了下层向上层提供哪些原语操作与服务

网络体系结构 - 层和协议的集合为网络体系结构，一个特定的系统所使用的一组协议，即每层的协议，称为协议栈

OSI参考模型

OSI 7 层模型由ISO提出，Day,Zimmermann，1983

物理层 - 定义如何在信道上传输 0、1：Bits on the wire - 机械接口（ Mechanical ）：网线接口大小形状、线缆排列等 - 电子信号（ E lectronic ）：电压、电流等 - 时序接口（ Timing ）：采样频率、波特率、比特率等 - 介质（ M edium ）：各种线缆、无线频谱等

数据链路层 （Data Link Layer） - 实现相邻（ Neighboring ）网络实体间的数据传输 - 成帧（Framing）：从物理层的比特流中提取出完整的帧 - 错误检测与纠正：为提供可靠数据通信提供可能 - 物理地址（ MAC address 48 位，理论上唯一网络标识，烧录在网卡，不便更改 - 流量控制，避免 淹没（overwhelming）当快速的发送端遇上慢速的接收端，接收端缓存溢出 - 共享信道上的访问控制（MAC）：同一个信道，同时传输信号。如同：同一间教室内，多人同时发言，需要纪律来控制。

网络层（Network Layer） - 将数据包跨越网络 从源设备发送到目的设备（host to host） - 路由（Routing）：在网络中选取从源端到目的端转发路径，常常会根据网络可达性动态选取最佳路径，也可以使用静态路由 - 路由协议：路由器之间交互路由信息所遵循的协议规范，使得单个路由器能够获取网络的可达性等信息 - 服务质量（QoS）控制：处理网络拥塞、负载均衡、准入控制、保障延迟 - 异构网络互联：在异构编址和异构网络中路由寻址和转发

为何在唯一的MAC地址之外，还需要唯一的IP地址？ 由于全世界存在着各式各样的网络，他们使用不同的硬件地址。要使这些异构网络能够互相通信就必须进行非常复杂的硬件地址转化工作，因此由用户或用户主机来完成这项工作几乎是不可能的的事。但IP编址就把这个复杂的问题解决了。连接到互联网的主机只需要各自拥有一个唯一的IP地址，他们之间的通信就像连接在同一个网络那么简单方便。因为ARP是由计算机软件自动进行的，对用户来说是看不见这种调用过程的。 互联网是由很多异构的物理网络通过路由器联接起来的，不同的物理网络，寻址方式很可能是不同的，可能根本不使用MAC地址。这样，不同的物理网络想要进行通讯就变得十分困难，因为彼此的数据帧相互不兼容。所以，我们想要一个公用的标准去遵循，这个标准就是IP。IP地址的分配是根据网络的拓朴结构，而不是根据谁制造了网络设置。

传输层（Transport Layer） - 将数据从源端口发送到目的端口（进程到进程） - 网络层定位到一台主机（ host ），传输层的作用域具体到主机上的某一个进程 - 网络层的控制主要面向运营商，传输层为 终端用户 提供端到端的数据传输控制 - 两类模式：可靠的传输模式，或不可靠传输模式 - 可靠传输：可靠的端到端数据传输，适合于对通信质量有要求的应用场景，如文件传输等 - 不可靠传输：更快捷、更轻量的端到端数据传输，适合于对通信质量要求不高，对通信响应速度要求高的应用场景，如语音对话、视频会议等

会话层（Session） - 利用传输层提供的服务，在应用程序之间建立和维持会话，并能使会话获得同步

表示层（Presentation Layer） - 关注所传递信息的语法和语义，管理数据的表示方法，传输的数据结构

应用层（Application Layer） - 通过应用层协议，提供应用程序便捷的网络服务调用

TCP/IP参考模型

TCP/IP 参考模型：ARPANET 所采用 - 以其中最主要的两个协议 TCP/IP 命名 - Vint Cerf 和 Bob Kahn 于 1974 年提出

链路层（Link Layer） - 描述了为满足无连接的互联网络层需求，链路必须具备的功能

互联网层（Internet Layer） - 允许主机将数据包注入网络，让这些数据包独立的传输至目的地，并定义了数据包格式和协议（ IPv4 协议和 IPv6 协议）

传输层（Transport Layer） - 允许源主机与目标主机上的对等实体，进行端到端的数据传输：TCP UDP

应用层（Application Layer） - 传输层之上的所有高层协议：DNS、HTTP、FTP、SMTP...

先有 TCP/IP 协议栈，然后有 TCP/IP 参考模型 参考模型只是用来描述协议栈的

TCP/IP 参考模型 - 摒弃电话系统中“笨终端 聪明网络”的设计思路 - 采用 聪明终端 简单网络 ，由端系统TCP负责丢失恢复等，简单的网络大大提升了可扩展性 - 实现了建立在简单的、不可靠部件上的可靠系统

IP 分组交换的特点 - 可在各种底层物理网络上运行 IP over everything - 可支持各类上层应用 Everything over IP) - 每个 IP 分组携带各自的目的地址，网络核心功能简单（通过路由表转发分组），适应爆炸性增长

OSI模型与TCP/IP模型比较

7 层模型与 4 层模型 - TCP/IP 模型的网络接口层定义主机与传输线路之间的接口，描述了链路为无连接的互联网层必须提供的基本功能 - TCP/IP 模型的互联网层、传输层与 OSI 模型的 网络层、传输层 大致对应 - TCP/IP 模型的应用层包含了 OSI 模型的表示层与会话层

基本设计思想：通用性与实用性 - OSI ：先有模型后设计协议，不局限于特定协议明确了服务、协议、接口等概念，更具通用性 - TCP/IP 模型：仅仅是对已有协议的描述

无连接与面向连接 - OSI 模型网络层能够支持无连接和面向连接通信 - TCP/IP 模型的网络层仅支持无连接通信（IP）

分层模型与网络实例

互联网发展史与启示

• 1957年10月：苏联发射成功第一颗人造卫星斯普特尼克1号
• 1958年2月：美国成立国防高级研究计划局（ARPA）
• 1969年8月：ARPANET诞生，创新地采用了分组交换技术（四个节点UCLA/SRI/UCSB/Utah）
• 1972年底：24个站点，美国国防部DARPA、基金委NSF以及UCLA、UCSB等高校
• 1983年：ARPANET采用TCP/IP，标志着互联网诞生
• 80年代中期：Internet横跨北美、欧洲和澳大利亚，成为全球性网络
• 1990年：APRANET退役移交基金委NSF

商业需求是核心驱动力，技术创新提供重要基础 - 有远见的 企业 参与并不断投入： MCI 、 IBM 、 Qwest CISCO…… - 有线->无线->广覆盖：便捷程度决定了用户使用方式和在线时间 - 网络性能决定了应用体验，成了互联网应用发展的必要条件 - 网络带宽决定了应用能传什么：文本 图片（静图 动图） 音频 视频（低清 高清，短视频 直播） - 网络性能提升、延迟降低 ：快速响应？可靠性？计算、存储、传输的互换

我国的互联网发展情况

起步阶段 - 1987 年，建成第一个电子邮件节点，从北京向德国发送第一封邮件 成功（越过长城，走向世界） - 1994 年，我国通过 64K 专线接入互联网，全功能连接

我国网络发展规模 - 五大网络： CHINANET 电信， UNINET 联通， CMNET 移动，CERNET 教育网， CSTNET 科技网 - 2019 年底，我国国际出口带宽超过 8.8T - 4G 基站 551 万个（ 全球 4G 基站总数不超过 900 万） - 2020 年底， 5G 基站达 70 万个，占全球比重近 7 成 - IPv4 地址 3.8 亿个； IPv6 地址 50903 块 /32 ，居世界第二 - .CN 域名数 2304 万个，全球第一 - 应用 APP 在架数量达到 359 万款

网络设备商华为

华为现状 - 1987 年成立，全球 20 万人，多个产品线全球第一：宽带接入、光传输、移动接入网、移动核心网

居安思危 - 2000 年全国电子百强首位，任正非：华为的冬天（2000 年互联网泡沫来临，设备商巨头朗讯倒下） - 长期坚持超大研发投入，从幕后走到前台 - 长期受美国打压，难进全球最大市场美国 - 美国科技封锁，自研芯片等备胎转正，焉知非福？

技术领先、标准引领，秉持开放共赢 - 学术：活跃于 Sigcomm 等顶级学术会议 - 专利：专利申请全球第一，从数量到质量 - 标准： 3GPP 、 ITU T 、 IETF 等标准主要贡献者

总结

网络度量单位：带宽、时延和丢失率

物联网技术及其应用

基础知识

背景与定义

物联网， The Internet Of Things (IOT) IOT)，是把所有物品通过网络连接起来，实现任何物体、任何人、任何时间、任何地点（ 4A ）的智能化识别、信息交换与管理。

Internet 将世界上所有的人联结起来， Internet of People for P2P

物联网将世界上所有的东西联结起来， Internet of Things for P2T or T2T

物联网是具有标识、感知和智能处理能力的物体基于通信技术相互连接形成的网络，这些物体可以在无需人工干预的条件下实现协同和互动，目的在于为人们提供智慧和集约的服务。——孙利民

历史进程

• 1999（MIT概念）：麻省理工学院（MIT ）的Kevin Ashton 首次提出：把RFID 技术与传感器技术应用于日常物品形成“物联网”。
• 2005（智能计算）：国际电信联盟（ITU ）报告：物联网是通过 RFID 和智能计算等技术实现全世界设备互联的网络。
• 2008（智慧地球）：IBM指出：把物联网设备安装到各种物体中，并普遍连接形成网络，即”物联网“，进而在此基础上形成”智慧地球“。
• 2009（物联网行动计划）：欧洲物联网研究所（CERP IoT项目工作组制定 《 物联网战略研究路线图 》 ，介绍传感器 /RFID 等前端技术和 20 年发展趋势。
• 2015（物联网标准联盟）：工业物联网标准联盟的成立证明了物联网有可能改变任何链流程的运行方式。

物联网的纪元史

• 1999 年 MIT 的 Auto ID Center：EPC(Electronic Product Code 电子产品码，在计算机互联网基础上 利用射频识别 、 无线数据通讯等技术 构造的一个覆盖世界上万事万物的实物互联网 (Internet of Things) 。
• 2005 年 11 月 17 日 国际电信联盟 ITU：发布了《 ITU Internet Reports 2005 The Internet of Things 》无所不在的 物联网 通信时代即将来临 世界上所有的物体从轮胎到牙刷、从房屋到纸巾都可以通过因特网主动进行交换。
• 2008 年 11 月 IBM CEO 彭明盛：《 智慧的地球：下一代领导人议程 》
• 2009 年 1 月 28 日 美国总统奥巴马：美国工商业领袖 圆桌会议；积极回应 智慧地球
• 2009 年 2 月 24 日 IBM 大中华 CEO 钱大群：智慧地球 、 赢在中国
• 2009 年 8 月 7 日 中国总理温家宝：访问无锡 、 感知中国
• 2012 年 2 月 工信部 《 物联网 十二五 发展规划 》
• 2013 年 2 月 17 日 国务院 《 关于推进物联网有序健康发展的指导意见 》

物联网的本质

物联网不仅仅是一个网络 更是一个平台 一个应用 或者说是一个带有节点和内容的网络 。

也有将物联网理解为 Intelligent Interconnection Of Things ( 体现出了 智慧 和 泛在网络 的含义 。

物联网不仅仅是网络，更是面向业务的智能应用和服务

物联网VS互联网

网络覆盖范围不同 - 物联网是为物而生，主要是为了管理物，间接为人服务。 - 互联网的产生是为了让人通过网络交换信息 其服务的对象是人 。

终端接入方式不同 - 物联网中的传感器结点需要通过无线传感器网络的汇聚结点接入互联网 。 - 互联网用户通过端系统的服务器 、 台式机 、 笔记本和移动终端访问互联网资源 。

数据采集方式不同 - 物联网感知的数据是传感器主动感知或者是 RFID 读写器自动读出的 。 - 互联网提供的各类服务 主要是进行人与人之间的信息交互 。

网络技术范围不同 - 物联网运用的技术包括互联网等等几乎涵盖了信息通信技术的所有领域 。 - 互联网只是物联网的一个技术方向 。

核心技术

物联网模型——物联网层次模型

• 综合应用层：物联网应用以“物”或者物理世界为中心，涵盖物品追踪、环境感知、智能物流、智能交通、智能电网等 。
• 管理服务层：解决数据如何存储 数据库与海量存储技术 、 如何检索 搜索引擎 、 如何使用 数据挖掘与机器学习 、 如何不被滥用数据安全与隐私保护 等问题 。
• 网络构建层：主要负责传递和处理感知层获取的信息分为有线传输和无线传输两大类 其中无线传输是物联网的主要应用 。 无线传输又可分为短距离传输和广域网通信等几种 。
• 感知识别层：（数据采集子层，短距通信技术，协同处理子层），位于物联网四层模型的最底端 是所有上层结构的基础 。

核心技术：无线传感器网络（WSN）

• 传感器（Sensor）是能感受规定的被测量并按照一定的规律转换成可用信号的器件或装置 通常由敏感元件和转换元件组成。
• 无线传感器网络 WSN Wireless Sensor Networks 是由部署在监测区域内的大量传感器节点通过无线通信方式形成的一个多跳的自组织网络系统，其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息 能够实现数据的采集量化、处理融合和传输应用。
• 传感器、感知对象和观察者构成了无线传感器网络的三个要素 。
• 无线传感器网络的特点包括大规模、自组织、动态性、可靠性应用相关和以数据为中心 。

无线传感器网络——网络结构

传感器网络结构：传感器网络系统通常包括传感器节点、汇聚节点和管理节点。

WSN体系结构：平面拓扑结构

WSN体系结构：逻辑分层结构

无线传感器网络——传感器节点

传感器节点是由四个主要部件组成的小微型计算机系统：Sensing，Processing，Communication，Power

伯克莱Mica Mote节点

什么是无线传感网络？

无线传感网络是由部署在监测区域内的大量微型、低成本、低功耗的传感器节点组成的多跳无线网络。

大规模、自组织、随机部署、环境复杂、传感器节点资源有限、网络拓扑经常变化

连接物理世界和数字世界

无线传感器网络——关键技术

拓扑控制 - 拓扑控制是无线传感器网络研究的核心技术之一，通过拓扑控制自动生成的良好的网络拓扑结构能够提高路由协议和 MAC 协议的效率。

时间同步 - 时间同步是需要协同工作的传感器网络系统的一个关键机制。如测量移动车辆速度需要计算不同传感器检测事件的时间差，通过波束阵列确定声源位置节点间时间同步。

定位技术 - 位置信息是传感器节点采集数据中不可缺少的一部分，确定事件发生的位置或采集数据的节点位置是传感器网络最基本的功能之一。

数据融合 - 传感器网络存在能量约束，减少传输的数据量能够有效地节省能量，可利用节点的本地计算和存储能力处理数据的融合去除冗余信息，从而达到节省能量的目的。数据融合技术可以与传感器网络的多个协议层次相结合。

核心技术：射频识别技术（RFID）

• 射频识别技术 RFID (Radio Frequency Identification) 俗称电子标签 通过射频信号自动识别目标对象 并对其信息进行标志 、 登记 、 储存和管理 。
• 射频识别技术具有适用性 、 高效性 、 独一性和简易性 。
• 射频识别技术依标签供电方式可分为无源 RFID 、 有源 RFID 和半有源 RFID 。
• 射频识别技术的发展具有高频化 、 网络化和多能化的趋势 。

射频识别技术——工作流程

• 读写器将要发送的信息，经编码后加载到高频载波信号上再经天线向外发送。
• 电子标签接收此信号，卡内芯片对此信号进行处理，然后对命令请求、密码、权限等进行判断。
• 若为读命令，则从存储器中读取有关信息，发送给阅读器，收到信号后送至信息系统进行处理。
• 若为写命令，电子标签内部电荷泵提升工作电压，擦写 E2PROM 。若经判断其对应密码和权限不符，则返回出错信息。

核心技术：WSN和RFID的融合

传感器网络架构下RFID 与 WSN 的融合：智能节点

传感器网络架构下RFID 与 WSN 的融合：智能传感标签

核心技术：5G

5 G(The 5 th Generation Mobile Networks) 即第五代移动通信技术 是继2 G 4 G 通信技术后的新一代数字移动通信技术 相比于前代技术实现了提高数据传输速率 、 降低延迟 、 提高系统容量 为大规模设备接入提供了可能 这也为物联网的普及提供了万物互联的网络基础 。

核心技术：移动通信技术发展历史

• 1G 是模拟式通信系统，代表在无线传输采用模拟式的 FM调制，将 300Hz 3400Hz 的语音转换到高频载波频率上。
• 2G 是数字通信系统，具有高保密、抗干扰、成本低、多种通信业务等优势， 2G 的到来开启了移动上网时代。
• 3G 有 4 种标准制式，其中 CDMA （码分多址）是第三代移动通信系统的技术基础。
• 4G 包括 TD LTE 和 FDD LTE 两种制式，能够快速传输数据、高质量、音频、视频和图像等。
• 5G 采用统一标准，高速率、低延迟、大容量是主要特征，推动了移动互联网进阶到物联网。

核心技术：5G和4G对比

总的来说 5 G 相比 4 G 有着很大的优势： - 在容量方面 5 G 通信技术将比 4 G 实现单位面积移动数据流量增长 1000 倍； - 在传输速率方面 典型用户数据速率提升 10 到 100 倍 峰值传输速率可达10 Gbps 4 G 为 100 Mbps 端到端时延缩短 5 倍； - 在可接入性方面 可联网设备的数量增加 10 到 100 倍； - 在可靠性方面 低功率 MMC 机器型设备 的电池续航时间增加 10 倍 。

由此可见 5 G 将在方方面面全面超越 4 G 实现真正意义上的融合性网络 。

技术应用

智能交通，智能城市，智能物流，智能环保，智能家居，M2M应用，精准农业，智能医疗

智能交通——车载自组网

车载自组网， Vehicle Ad Hoc Networks (VANET)，是物联网应用的典型场景，能够为针对减少交通事故而设计的车辆主动式安全应用提供基础性支持，目标是在道路上构建一个自组织、结构开放的车辆间通信网络，从而实现事故预警、减免交通拥堵、辅助行车驾驶员安全驾驶等应用，最终提高行车效率与安全。

整个车载自组网分为两部分：车与车V2V Vehicle to Vehicle ）和车与设施（ V2I Vehicle to Infrastructure ）。

车载自组网关系图

技术应用：智能安防

上海浦东国际机场防入侵系统铺设了 3 万多个传感节点，覆盖了地面、栅栏和低空探测，多种传感手段组成一个协同系统后，可以防止人员的翻越、偷渡、恐怖袭击等攻击性入侵。

系统架构

工程概况

技术应用——智能电网

• 与现有电网相比，智能电网体现出电力流、信息流和业务流高度融合的显著特点。
• 江西电网对分布在全省范围内的 2 万台配电变压器安装传感装置，对运行状态进行实时监测，实现用电检查、电能质量监测、负荷管理、线损管理、需求侧管理等高效一体化管理，一年降低电损 1.2 亿千瓦时。
• 日本计划在 2030 年全部普及智能电网，同时官民一体全力推动在海外建设智能电网。

智能电网架构

智能航天——航天传感网

航天传感网借助于航天器布撒的传感器节点实现对星球表面大范围、长时期、近距离的监测和探索， NASA 的 JPL 实验室研制的 Sensor Webs 是为将来的火星探测、选定着陆场地等需求进行技术准备的。

“吉林一号”卫星星座是我国对地观测的重要卫星遥感网络。卫星遥感影像已广泛应用于国土资源监测、土地测绘、矿产资源开发、智慧城市建设等领域。

深入思考

物联网面临的问题 - 更安全的防护措施； - 更普及的智能设备； - 更加关注人工智能； - 更快速的数据转化； - 应用先行、技术突破、产业同步 。

物联网的发展趋势 - 统筹规划和顶层设计缺乏； - 标准规范和核心技术缺失； - 系统管理 、 维护和扩展性差； - 规模化应用和成熟商业模式缺乏； - 终端设备多而零散； - 产业链不完善 。

人工智能

决策——从搜索到学习

决策：从模拟器到物理现实

机器人学

经典案例——鸡尾酒会问题

计算机视觉：从2D到3D；从IID（独立同分布）到OOD（Out of Distribution）

计算机视觉：从判别模型到生成模型

经典案例：对经典流体物理的模仿和超越，精准预报极端天气，预测蛋白质折叠的三维结构

我国新一代人工智能发展规划（2030）

定义

人工智能就是根据对环境的感知，做出合理的行动，并获得最大收益的计算机程序（《人工智能：一种现代的方法》一书中的定义，既强调人工智能可以根据环境感知做出主动反应，又强调人工智能所做出的反应必须达致目标，同时，不再强调人工智能对人类思维方式或人类总结的思维法则的模仿。）

作为学科，人工智能是一门集成脑科学、认知科学、心理学、语言学、逻辑学、哲学与计算机科学的交叉学科。它是研究、开发用于模拟、延伸和扩展人的智道能的理论、方法、技术及应用系统的一门新的技术科学

人工：人为的、人造的

智能：具有 - 感知能力：感知外部世界 - 记忆能力：对感知到的外界信息或由思维产生的内部知识进行存储 - 思维能力：对所存储的信息或知识的本质属性、内部规律的认识 - 学习与自适应能力：具有特定目的的知识获取 - 决策与行为能力：对感知到的外部信息做出动作反应

强人工智能

强人工智能是像人类一样能够对世界进行感知和交互，通过自我学习的方式对所有领域进行记忆、推理和解决问题的人工智能。

弱人工智能

弱人工智能指的是专注于且只能解决特定领域问题的人工智能，其自身模型只能够解决相关领域的问题。其不具备自我意识，不具备理解、思考、计划解决问题的能力（如人脸识别，淘宝推荐广告）

历史

问世：图灵测试

• 1950年，计算机科学之父阿兰图灵发表论文Computing Machinery and Intelligence（计算机与智能）。
• I propose to consider the question, “Can machines think?”（我建议思考这样一个问题：机器能思考吗？）
• 第一次提出了智能的概念，并定义了图灵测试（图灵测试至今仍被当做人工智能水平的重要测试标准之一）
• 图灵测试是指，人们通过设备和另外一个人进行聊天，可以是文字形式也可以是语音，聊天之后，如果30%的人认为是在和一个真人聊天，而实际对方却是个机器，那么我们就认为这个机器通过了图灵测试，它是具有“智能”的。

问世：达特茅斯会议

• 1956年，一群科学家聚会在美国汉诺思小镇宁静的达特茅斯学院开会，这次会议的主题就是“达特茅斯夏季人工智能研究计划”。
• 他们从不同领域（数学，心理学，工程学，经济学和政治学）正式确立了人工智能为研究学科。
• 麦卡锡将人工智能定义为：研制智能机器的一门科学与技术

历史

• 1957：贝尔曼方程
• 1958：感知机
• 1965：专家系统
• 1973：莱特希尔辩论
• 1982：神经网络受到关注
• 1986：多层感知机
• 1989：卷积神经网络（CNN）
• 1991：DART投入军用
• 1995：支持向量机（SVM）
• 1997：长短期记忆网络（LSTM）
• 2006：深度学习
• 2009：图神经网络（GNN）
• 2012：AlexNet夺冠
• 2014：生成对抗网络（GAN）
• 2017:人工智能通过Tensorflow Lite，Caffe2实现从云到端

形成期（1956-1970）

理查德·贝尔曼：动态规划创始人，最短路径Bellman-Ford算法

1957年，Richard Bellman提出贝尔曼方程（也被称作动态规划方程），奠定了强化学习基础

名词	解释
Agent（智能体）	学习器与决策者的角色
Environment（环境）	智能体之外一切组成的、与之交互的事物
Action（动作）	智能体的行为表征
State（状态）	智能体从环境获取的信息
Reward（奖励）	环境对于动作的反馈

Frank Rosenblatt 弗兰奇·罗森布拉特（1928-1971） 1958年，心理学家Rosenblatt提出感知机模型，是最简单的神经网络，是第一个从算法上描述的神经网络。

专家系统是一个具有大量的专门知识与经验的程序系统，它应用人工智能技术和计算机技术，根据某领域一个或多个专家提供的知识和经验，进行推理和判断，模拟人类专家的决策过程，以便解决那些需要人类专家处理的复杂问题 - 1965年在美国国家航空航天局要求下，斯坦福大学成功研制了DENRAL专家系统，该系统具有非常丰富的化学知识，可根据质谱数据帮助化学家推断分子结构。这个系统的完成标志着专家系统的诞生。 - 在此之后, 麻省理工学院开始研制MACSYMA系统，现经过不断扩充, 它能求解600多种数学问题。、

专家系统结构示意图

• Shakey是斯坦福研究院（SRI）的人工智能中心于1966年到1972年研制的世界上第一台真正意义上的移动机器人。
• 虽然Shakey只能解决简单的感知、运动规划和控制问题，但它却是当时将AI应用于机器人的最为成功的研究平台，它证实了许多通常属于人工智能领域的严肃的科学结论。

黯淡期（1966-1974）

1965年，西蒙提出：20年内，机器将能做人所能做的一切。

感知机无法解决异或（XOR）问题

机器翻译遭遇困境 The spirit is willing but the flesh is weak. 机器翻译：酒是好的，肉变质了 实际意思：心有余而力不足

计算机内存有限，运算能力不足，无法解决指数型爆炸的复杂计算问题

此前对人工智能过于乐观使人们期待过高，当AI研究人员的承诺无法兑现时，公众开始激烈批评AI研究人员，许多机构不断减少对人工智能研究的资助，直至停止拨款。人工智能遭遇发展史上第一次寒冬。

1973年6月，科学界各方对人工智能看法不一。在英国著名媒体BBC的安排下，对人工智能技术前景持否定态度的詹姆斯·莱特希尔，和对人工智能未来前景强烈认同的美国斯坦福大学教授约翰·麦卡锡，出现在专业的人工智能研讨会上，也出现在BBC的直播镜头之前。

两位怒气冲冲、针锋相对的科学家，给人工智能历史留下了极其精彩的莱特希尔辩论（LighthillDebate）的故事。

詹姆斯·莱特希尔爵士在调查研究了美国的AI热之后，在议会发表了著名的批评报告。他在报告中罗列了详尽的证据，认为当时流行的基于逻辑学的符号编程，根本无法解决复杂的现实问题。

这份报告给了AI领域当头一棒，直接导致欧美国家大幅度削减AI领域的研发资金，直接导致了历史上著名的“AI之冬”的到来。

应用期（1970-1988）

专家系统和知识工程在全世界得到了迅速发展。专家系统为企业等用户赢得了巨大的经济利益。

DEC公司与卡内基梅隆大学合作开发的XCON-R1专家系统，它每年为DEC公司节省数百万美元。

专家系统开发过程中，研究者达成共识，即人工智能系统是一个知识处理系统，而知识获取、知识表示和知识利用成为人工智能系统三大基本问题。

发展期（1986-）

人工智能研究进入稳步发展阶段，技术与方法论发展均保持高速状态，实用化进程也逐渐成熟 - 大数据：人工智能发展的助推剂，为人工智能模型提供训练数据 - 互联网：使联网计算机都能获得海量数据 - 云计算：提供计算资源；可以通过其众包服务来获取手工标记的数据

支持向量机（supportvectorMachine）是由Cortes和Vapnik于1995年首先提出的。由于它有非常完美的数学理论推导做支撑（统计学与凸优化等），并且非常符合人的直观感受（最大间隔），更重要的是它在线性分类的问题上取得了当时最好的成绩，在深度学习（2012）出现之前，SVM 被认为是近十几年来最成功，表现最好的机器学习算法

SVM要解决的问题可以用一个经典的二分类问题加以描述。如图所示，红色和蓝色的二维数据点显然是可以被一条直线分开的，在模式识别领域称为线性可分问题。然而将两类数据点分开的直线显然不止一条。图中(b)和(c)分别给出了A、B两种不同的分类方案，其中黑色实线为分界线，术语称为“决策面”。每个决策面对应了一个线性分类器。 虽然在目前的数据上看，这两个分类器的分类结果是一样的，但如果考虑潜在的其他数据，则两者的分类性能是有差别的。SVM算法认为图中的分类器A在性能上优于分类器B，其依据是A的分类间隔比B要大。具有“最大间隔”的决策面就是SVM要寻找的最优解。而这个真正的最优解对应的两侧虚线所穿过的样本点，就是SVM中的支持样本点，称为“支持向量”

• 1986年，Hinton发明了适用于多层感知器（MLP）的BP算法，并采用Sigmoid进行非线性映射，有效解决了非线性分类和学习的问题。该方法引起了神经网络的第二次热潮。
• 1989年，LeCun发明了卷积神经网络（CNN）-LeNet，并将其用于数字识别，且取得了较好的成绩
• 1997年，LSTM模型被发明，该模型在序列建模上的特性非常突出，缓解循环神经网络（RNN）梯度消失问题
• 2006年，深度学习元年，Hinton提出了深层网络训练中梯度消失问题的解决方案：无监督预训练对权值进行初始化+有监督训练微调。第一次提出深度学习的概念
• 2011年，ReLU激活函数被提出，该激活函数能够有效的抑制梯度消失问题。
• 2012年，Hinton课题组为了证明深度学习的潜力，首次参加ImageNet图像识别比赛，其通过构建的CNN网络AlexNet一举夺得冠军，且碾压第二名（SVM方法）的分类性能。

分类

• 从广义上讲，人工智能描述一种机器与周围世界交互的各种方式。

• 通过先进的、像人类一样的智能——软件和硬件结合的结果——一台人工智能机器或设备就可以模仿人类的行为或像人一样执行任务。

• 机器学习是人工智能的一种途径或子集，它强调“学习”而不是计算机程序。

• 一台机器使用复杂的算法来分析大量的数据，识别数据中的模式，并做出一个预测——不需要人在机器的软件中编写特定的指令。

• 深度学习是机器学习的一个子集，推动计算机智能取得长足进步。它用大量的数据和计算能力来模拟深度神经网络。

• 从本质上说，这些网络模仿人类大脑的连通性，对数据集进行分类，并发现它们之间的相关性。

应用

计算机视觉：对单张图像或一系列图像的有用信息进行自动提取、分析和理解 自然语言处理是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言，特别是如何编程计算机以成功处理大量的自然语言数据。 智慧城市 - 智慧交通：融合城市多元时空数据，为市民打造智能化出行服务，为政府和交管机构提供管控优化指导 - 智慧公安：通过大数据和人工智能技术，预测城市各区域犯罪率，设计合理巡检路线 - 智慧环保：结合大数据和人工智能技术，从数据感知、实时监测、预测未来、历史溯源和调度优化等方向构建智能环保体系 - 城市画像：应用大数据和人工智能技术，对城市的居民消费、人口流动、环境监测等情况进行分析呈现

机器人

机器学习

基本概念与发展史

机器学习（Machine Learning）是一门从数据中研究算法的多领域交叉学科。 研究计算机如何模拟或实现人类的学习行为。 从以往的经验中得到数据，通过学习构建模型，预测新数据，或对特定问题做出决策。

基础范式

给定包含预期结果的示例，机器学习将会发现执行一项数据处理任务的规则。 因此，需要以下要素进行机器学习： - 数据：输入数据点与预期输出的示例； - 模型：对输入输出关系的假设空间； - 目标：衡量模型效果好坏的方法； - 算法：优化模型参数以使模型输出逼近目标。

机器学习的类型及对应场景

• 监督学习：数值预测（价格预测等）、类别预测（人脸识别等模式识别任务）
• 无监督学习：用户聚类、生物信息对比等等
• 半监督学习：图像分类、语音识别等具有海量无标记数据的“监督学习”任务
• 强化学习：机器人、游戏等领域中与环境交互但无数据标签的问题
• 迁移学习：自动驾驶、自然语言处理等

监督学习（Supervised Learning）Slide16第7页

• 目的：在监督学习中，已知一些数据集（输入），并且知道它们的答案（输出），学习输入输出的关系
• 主要分为分类（Classification）和回归（Regression）
• 有监督的分类问题就是用已知类别的样本来学习模型参数
• 例子：线性回归问题

	分类	回归
输入	离散数据	连续数据
目的	寻找决策边界	寻找最优拟合

假设空间越复杂（模型参数越多），就越能拟合训练数据，训练数据误差就会越低；但过于复杂的模型对导致未知数据的泛化误差可能增大 - 解决方法1：取一部分验证数据，确定合适的参数规模（超参数调节） - 解决方法2：增加训练数据量（Data augmentation），提升大模型的泛化能力

回归案例：芝麻信用分是怎么来的？

机器学习的基本流程： - 步骤1：构建问题，选择模型 - 步骤2：收集已知数据，把数据分成几个部分：训练集（Trainingset）、验证集（Validationset）（确保模型没有过拟合）、测试集（Testset） - 步骤3：训练模型得到理想参数 - 步骤4：对新用户进行预测

无监督学习

无监督学习根据类别未知的训练样本来学习 数据降维表示与恢复是常见的一类无监督学习算法 - 传统模型：主成分分析（PCA，Principal components analysis）等 - 深度模型：自动编码器（AutoEncoder）等 聚类：K-means等 典型应用场景：异常检测、推荐系统、用户细分、无监督预训练

其他类型的学习

半监督学习（Semi-supervised Learning） - 综合使用大量的未标记数据，以及小部分标记数据，来进行学习工作

迁移学习（Transfer Learning） - 把为任务A 开发的模型重新应用在为任务B 开发模型的过程中

强化学习（Reinforcement Learning） - 通过智能体与环境的交互学习策略以实现回报最大化或实现特定目标 - 在决定合适的行动时，需要考虑后续步骤 - 三要素：状态、动作、回报（如棋局胜负）

状态转移图：其中每个节点是一个状态，每个边是一个可能的转移（通常为概率式的）。边都有奖励，我们的目标是计算出在任何状态下的最佳行为方式，从而最大化奖励。

机器学习和人工智能、计算机视觉的关系

和人工智能的关系

和计算机视觉的关系

发展历史

• 二十世纪五六十年代：推理期，机器学习的起源“逻辑推理家”
• 二十世纪七八十年代：知识期，把人总结的知识体系交给计算机专家系统
• 二十世纪八九十年代：归纳学习与统计学习，从样例中学习，符号主义、联结主义、统计学习
• 二十一世纪：深度学习，深度神经网络，人工智能

发展历史：推理期

人们认为只要给机器赋予逻辑推理能力，机器就能具有智能。 这一阶段的代表性工作：“逻辑理论家”，西蒙和钮威尔因此获1975年图灵奖。

逻辑理论家程序：这是第一个刻意模仿人类解决问题技能的程序，被称为“第一个人工智能程序”。模拟人证明符号逻辑定理的思维活动成功地证明了怀特海德和罗素的《数学原理》中前52个定理中的38个。

发展历史：知识期

专家系统（Expert System） - 大家开始思考如何把人类的知识总结形成“专家系统”，交给计算机。 - 知识工程之父费根鲍姆因为该贡献获得了1994 年图灵奖

代表工作 - 专家系统，费根鲍姆等人的“DENDRAL”系统 - 模式识别，包括语音识别、光学字符识别等。让一个计算机程序去做一些看起来很“智能”的事情，例如识别“4”这个手写数字。

难题 - 把知识成体系总结出来很难，一些领域还有许多特例存在 - 不是所有领域的专家都乐意“分享”

发展历史：归纳学习

由于知识获取难题，八十年代的机器学习主流是从样例中学习（归纳学习），其中的两大主要流派便是符号主义与联结主义。

符号主义（Symbolism）学习：包括决策树（Decision Tree）和基于逻辑的学习。 - 早期人工智能的研究方向，基础是纽威尔和西蒙的物理符号系统假设 - “逻辑理论家”，专家系统，知识工程都是符号主义发展过程中的产物 - 八十年代符号主义的经典模型是决策树模型，包括ID3，CART，C4.5三种经典实现（当下广泛应用的GBDT/XGBoost模型也都属于决策树模型）

联结主义（Connectionism）学习：基于神经网络“黑箱”模型。 - 在二十世纪五十年代取得发展，但许多早期人工智能学者更偏爱符号主义 - 六七十年代，以感知机为代表的脑模型的研究出现过热潮 - “人工智能之父”明斯基获1969年图灵奖 - 八十年代联结主义的代表工作有多层网络中的反向传播(BP)算法，卷积神经网络等至今仍广泛使用的经典模型

发展历史：统计学习（Statistical Learning）

二十世纪九十年代中期统计学习登上历史舞台并迅速取代归纳学习成为主流 - 以统计学习理论为直接支撑，主要研究学习的统计性能、算法的收敛性、学习过程的复杂性 - 代表性技术是支持向量机(Support Vector Machine，简称SVM) 以及更一般的核方法(Kernel Methods) - 九十年代中，连接主义学习技术的局限性凸显，而SVM的优越性得到验证

发展历史：深度学习

深度学习的发展历程 - 早期联结主义曾多次流行，但在九十年代中期被统计学习压制而进入瓶颈期 - 2006年辛顿正式提出了深度学习的概念，随后在学术圈引起巨大反响 - 2012年ImageNet大赛中辛顿用AlexNet一举夺魁，掀起深度学习的浪潮

深度学习领域的经典算法及其应用 - 反向传播（BP，Back Propagation）算法：深度学习基本训练算法，奠定了神经网络的基础 - 卷积神经网络（CNN，Convolutional Neural Network）：主要用于处理图像数据，例如图像识别问题 - 循环神经网络（RNN，Recurrent Neural Network）：主要用于处理序列数据，例如自然语言处理 - 生成对抗网络（GAN，Generative Adversarial Network）：无监督学习的生成模型，可用于图像生成 - 图卷积网络（GCN，Graph Convolutional Network）：主要用于图表示学习任务，例如社交网络任务 - 深度Q学习模型（DQN，Deep Q Network）：主要用于强化学习任务，如机器人、导航等领域

神经网络

神经网络：脑启发

神经网络：感知器

用于布尔函数的感知器

罗森布拉特（Rosenblatt）感知器模型（1958） - 输入和权重都是布尔值 - 阈值的逻辑：若输入的加权和超过阈值T，则触发神经元（输出为1）

神经网络：多层感知机

多层感知机（MLP，1969），由包含多层感知器的网络组成

用于布尔函数的MLP，第一层是“隐藏”层

用于普遍布尔函数的MLP，可以建模任意复杂的布尔函数！

用于实数函数的MLP - 输入和权重都是实数 - 实数感知器是一个线性分类器

用于复杂决策边界的MLP - 可以计算任意复杂的分类边界 - 将这些线性边界组合起来，第二层感知器用于“AND”

前向传播

向量化表示

激活函数 激活函数不一定是阈值函数（thresholdfunctions），可以是非线性的 激活函数的用途是向网络中引入非线性成分，在识别实际问题中的复杂数据模式时非常重要

用于分类问题的MLP - 在高维空间内寻找决策边界 - 可以利用一个MLP来表示（也可以选用其他机器学习模型）

实际问题中的多层感知机

• 单层非线性感知器的权重可视化
• 如果权重和输入之间的相关性超过阈值，则输出神经元被触发
• 感知器是一个相关性滤波器
• 用作级联特征检测器的MLP，较深的网络需要更少的神经元

底层神经元：对某个局部特征模式（边、角）进行特征检测 高层神经元：底层特征模式的复杂组合模版

神经网络：总结

1.基于阈值激活函数的感知器可以被视为布尔函数或线性分类器 2.激活函数向网络中引入了非线性成分 3.多层感知机可以表示任意决策边界 4.与较浅的网络相比，较深的网络需要更少的神经元

高级MLP应用：三维场景可微渲染-神经辐射场

深度学习

卷积神经网络：如何识别物体？

单个感觉神经元的感受野是感觉空间的特定区域。在该区域内，刺激将改变该神经元的激活状态

如果是让MLP来做，很难适应视角变化、比例变化、光照条件变化等情况。

卷积神经网络：改进1-局部连接

将每个神经元只与输入量的局部区域相连 其局部区域的空间范围由名为感受野的超参控制

卷积神经网络：改进2-参数共享

卷积神经网络举例：LeNet

卷积神经网络：卷积层

神经元的结果：在卷积核和图像的一小块553 之间进行点积 (即：553 = 75 维点积+ 偏差)

卷积神经网络：步长（Stride）

卷积神经网络：参数共享

卷积神经网络：卷积层

在输出中，第d个大小为28*28的切片是第d个卷积核与输入进行卷积的结果

将这些堆叠在一起得到隐藏层特征图，尺寸为28286

卷积神经网络：池化层（Pooling）

池化操作在各个28*28的特征切面上是独立的： - 池化减少了宽度和高度的尺寸 - 特征图深度在池化前后保持不变

卷积神经网络：典型的多层卷积连结方式

CNN是一组堆叠在一起的卷积层，其中穿插着激活函数和池化层

循环神经网络：序列建模

自然语言，医疗频谱，语音波形 机器翻译：编码压缩-解码输出

循环神经网络（RecurrentNeuralNetwork）

循环神经网络：RNN沿时间展开

使用相同的参数，W和U ht当中包含了所有来自历史时刻的信息

循环神经网络：RNN按输入输出类型分类

2. 图像命名，图像-> 自然语言
3. 感情分类，自然语言-> 感情
4. 机器翻译，自然语言->自然语言
5. 帧级别的视频分类

循环神经网络：多到多的RNN

循环神经网络：Seq2Seq：多到一+一到多

多到一：将输入序列编码为一个单独的向量 一到多：通过一个单独的输入向量生成输出序列

循环神经网络：深度RNN

计算机视觉

概念初探

计算机视觉的最初目标是建造能够像人类一样看见东西并为机器人执行感知的机器*，随后发展成一门跨学科的科学领域。 主要解决如何使计算机对图像或视频产生高阶的认识。从工程学的角度来看，它试图使人类视觉系统可以完成的任务自动化。

• 1965：三维机器视觉，Roberts 通过计算机程序从数字图像中提取出诸如立方体等多面体的三维结构。
• 1973：抽象表示，对于如何识别和表示对象，斯坦福科学家提出“广义圆柱体”和“圆形结构”，即每个对象都是由简单的几何图形单位组成。
• 1997：目标分割，Shi & Malik 提出若识别太难了，就先做目标分割，就是把一张图片的像素点归类到有意义的区域。
• 2004：尺度不变特征变换（SIFT），对关键点提取其局部尺度不变特征的描绘子， 采用这个描绘子进行用于对两幅相关的图像进行匹配

基础知识

多种类型的数据

图像：图像由一个个像素点组成，每个像素点为RGB像素 视频：视频本质上是图像在时间序列上的叠加，组成视频的每一张图像叫做视频帧 点云：点云包含了丰富的信息，包括三维坐标X，Y，Z、颜色、分类值、强度值、时间等等 深度图像：深度图像也叫距离影像，指将从图像采集器到场景中各点的距离（深度）值作为像素值的图像

图像滤波

图像滤波：计算每个位置处局部邻域的函数值 滤波很重要! - 图像增强：去噪、调整大小、对比度增强，等等 - 从图像中提取信息：纹理、边缘、特征点，等等 - 检测模式：模板匹配

空间域图像滤波 - 直接对像素进行操作 - 平滑化、锐化

频率域图像滤波 - 修改图像的频率 - 去噪、采样、图像压缩

模板和图像金字塔 - 将模板匹配到图像 - 检测、粗糙到精细

每个像素的值用其邻域像素的平均值替换 实现平滑效果（去除尖锐特征）

其他滤波器 垂直边缘（绝对值）

水平边缘（绝对值）

基础知识：传统图像处理到深度学习

基础知识：卷积神经网络（ConvolutionalNeuralNetwork）

卷积神经网络是神经网络家族的一员，最简单的卷积神经网络由一个或多个卷积层和顶端的全连通层组成。复杂的卷积神经网络还包括池化层，激活层等。 上图中，每一个彩色小方格便是一个卷积核，通过不同的卷积核可以提取不同特征。

基础知识：卷积神经网络的学习过程

卷积核是一成不变的吗？我怎么可能一开始就给出有效的卷积核呢？ 实际上，卷积核不是固定不变的，而是在训练过程中动态更新的。

基本任务

图像分类

将一只猫的照片输入深度卷积神经网络，并设定输出为“猫”。经过训练，得到网络神经网络的参数，神经网络便能从照片中学习猫的特征。

为了应对图片的复杂性，可以用大量的猫的图片训练模型，提升神经网络识别猫的准确率。

选取各个类别的大量样本图片训练深度卷积神经网络，可以使得神经网络识别出更多类别的物体。

ImageNet图像识别大赛 2012年首次使用深度学习模型，2015年起错误率低于人类

目标检测

目标检测的任务是找出图像中所有感兴趣的目标，确定它们的类别和位置。

通过一定的策略选择性搜索候选区域，并将其输入目标分类模块进行图像分类，最终获得目标检测结果。

语义分割（Semantic Segmentation）

语义分割需要进一步判断图像的轮廓。

语义分割是对图像中的每个像素都划分出对应的类别，即实现像素级别的分类。如图所示，每一个数字代表一类标签，对图像中的每一个像素进行分类，便可以框出各类物体的边界。

实例分割（Instance Segmentation）

实例分割不但要进行像素级别的分类，还需在具体的类别基础上区别开不同的实例。 目标检测+语义分割。 - 先用目标检测方法将图像中的不同实例框出，再用语义分割方法在不同包围盒内进行逐像素标记。

目标跟踪（Object Tracking）

目标跟踪是计算机视觉领域基本问题之一。给出指定物体在视频第一帧中的位置坐标，目标跟踪算法需要在接下来的视频帧中找到该指定物体的位置。 - 区别于目标检测需要给出图像中所有的物体的类别和位置，目标跟踪只需要给出指定物体的位置。因此，目标跟踪算法可以被看作为对指定物体的目标检测算法。 - 目标检测在自动驾驶中有着非常广阔的应用。

目标检测：姿态估计（Pose Estimation）

对人体姿态的估计常常转化为对人体关键点的预测问题，即首先预测出人体各个关键点的位置坐标，然后根据先验知识确定关键点之间的空间位置关系，从而得到预测的人体骨架。 - 自顶向下的思路是首先对图片进行目标检测，找出所有的人；然后将人从原图中提取出来，输入到网络中进行姿态估计。 - 自底向上的思路是首先找出图片中所有关键点，然后对关键点进行分组，从而得到一个个人。

技术应用

数据库系统

发展历程

简述：数据处理和管理是计算机应用最重要的领域之一，涉及社会生活的方方面面

数据库：存放数据的仓库，用户可以进行新增、截取、更新、删除等操作。

• 1960s：集成数据存储（美国Honeywell公司的IDS（Integrated Data Store）系统投入运行，揭开了数据库技术的序幕。）
• 1970s：关系模型（数据库蓬勃发展的年代，层次模型、网状模型占据了整个数据库商用市场，首次提出关系模型。）
• 1980s：关系数据库（关系系统由于使用简便以及硬件性能的改善，逐步代替网状系统和层次系统占领了市场。）
• 2000s：数据仓库（大数据时代到来数据仓库，No逐渐涌现。）

图灵奖得主： - 1973，查理士·巴赫曼，首创网状模型理论 - 1981，埃德加·科德，首创关系模型理论 - 1998，詹姆斯·格雷，革新事务处理技术 - 2014，迈克尔·斯通布雷克，现代数据库系统底层开发

数据库系统市场

关系数据库管理系统的公司： - 甲骨文（Oracle）、SAP（Sybase）：最大的数据库软件公司之一 - IBM（DB2）：世界上最大的DBMS供应商之一 - 微软的SQL-Server以及Access：精简、相对便宜

关系数据库公司的挑战：随着互联网web2.0网站的兴起，为了解决大规模数据集合多重数据种类带来的挑战，NoSQL数据库应运而生

其他数据库产品：Ingres, Paradox, Foxbase, FoxPro, dBase,…

中国数据库 - Ocean，蚂蚁金服，自研 - Polar DB，阿里云，基于MySQL开发 - GaussDB，华为，基于PostgreSQL开发 - TDSQL，腾讯，基于MySQL开发 - TiDB，PingCAP，基于Spanner论文自研 - SequoialDB，巨杉，自研

设计理论

关系模型

1970年首次提出 - 利用简单的数据结构存储数据 - 通过更高级的语言访问数据 - 忽略物理层存储的实现细节

关系是由一个无序的集合组成，属性之间的关系构成实体

关系中的一行（元组）是一系列属性值（域）的集合 - 值可以是整数，字符串，日期等类型 - “NULL”是所有属性里面都存在的特殊值

一个N维关系=一个N列的表格

关系模型——主键

一个关系中的主键唯一标识了一个元组

一些数据库管理系统会自动帮助用户创建一个内部的主键 - SEQUENCE(SQL:2003) - AUTO_INCREMENT(MySQL)

结构化查询语言（SQL）：Structured Query Language

关系模型——外键

外键用于与另一张表的关联 - 确定另一张表记录的字段 - 用于保持数据的一致性

关系代数

关系代数定义了在数据表中查询与操控元组的基本操作 每一个操作符输入一个或多个关系，输出一个新的关系 - 把多个操作符链接起来可以构成一个更加复杂的操作

• \(\sigma\) 选择（Select）
• \(\pi\) 投影（Projection）
• $$ 并（Union）
• $$ 交（Intersection）
• \(-\) 差（Difference）
• $$ 笛卡尔积（Product）
• \(\bowtie\) 连接（Join）

关系代数-选择

选择又称为限制（Restriction） - SELECT 语句用于从表中选取数据。 - 结果被存储在一个结果表中（称为结果集）

语法：\(\sigma_{predicate}(R)\)

关系代数-投影

从R中选择出若干属性列组成新的关系 - 可以对属性值进行重新排序 - 可以修改属性值

语法：\(\pi_{(A_1,A_2,\cdots ,A_n)}(R)\)

关系代数-并/交

并：由所有关系中包含的所有元组集合组成一个新的关系 语法：\((R \cup S)\)

交：由在所有关系中均出现的元组集合组成一个新的关系 语法：\((R \cap S)\)

关系代数-差/连接

差：由在第一个关系中出现不在第二个关系中出现的的元组集合组成一个新的关系 语法：\((R-S)\)

连接：从两个关系中选取属性间满足一定条件的元组 语法：\((R \bowtie S)\)

关系代数-笛卡尔积

由输入的关系中所有可能的元组组合组成一个新的关系 语法：\((R \times S)\)

查询实例

架构体系

数据(Data)是数据库中存储的基本对象 定义：描述事物的符号记录 种类：文本、图形、图像、音频、视频、学生的档案记录、货物的运输情况等 特点：数据与其语义是不可分的

数据库 定义：数据库(Database,简称DB)是长期储存在计算机内、有组织的、可共享的大量数据的集合。 组织：数据按一定的数据模型组织，数据相互关联。 基本特征：数据按一定的数据模型组织、描述和储存，可为各种用户共享，冗余度较小，数据独立性较高，易扩展

数据库包含两层意思 - 数据库是一个实体，它是能够合理保管数据的“仓库”，数据和库组成了数据库。 - 数据库是数据管理的新方法和技术，能更合适的组织数据、更方便的维护数据、更严密的控制数据和更有效的利用数据。

数据库管理系统（DBMS）

概念：用于建立、使用和维护数据库的系统软件。位于用户与操作系统之间的数据管理软件。 特点：专用于实现对数据进行管理和维护的系统软件；利用DBMS能科学地组织和存储数据、高效地获取和维护数据；如：SQL Server，Oracle，Sybase，Mysql

数据库应用程序与用户使用

数据库应用程序：运用数据库管理系统所支持的程序设计语言编写，如Visual Basic，Delphi，Java, Python

功能：创建并处理表单等 - 处理用户查询 - 创建并处理报表 - 执行应用逻辑 - 控制应用

数据库分类

关系型数据库 - 关系型数据库，存储的格式可以直观地反映实体间的关系。 - 关系型数据库和常见的表格比较相似，关系型数据库中表与表之间是有很多复杂的关联关系的。常见的关系型数据库有Mysql，SqlServer等。

非关系型数据库（NoSQL） - 随着近些年技术方向的不断拓展，大量的NoSql数据库如MongoDB、Redis、Memcache出于简化数据库结构、避免冗余、影响性能的表连接、摒弃复杂分布式的目的被设计。 - NoSQL数据库适合追求速度和可扩展性、业务多变的应用场景。存储方式包括键值对、图结构或者文档等。

区别

数据库领域的学术会议

• SIGMOD：ACM Conference on Management of Data
• SIGKDD：ACM Knowledge Discovery and Data Mining
• VLDB：International Conference on Very Large Data Bases
• ICDE：IEEE International Conference on Data Engineering
• TKDE：IEEE Transactions on Knowledge and Data Engineering

数据挖掘

什么是数据挖掘？对数据进行 收集、清洗、加工和分析并从中获取有用知识的过程。

为什么需要数据挖掘？ - 进入大数据时代，各类自动化系统生成的数据已达到 PB 或 EB 的数量级，如：万维网、财务交往、用户交互、传感器技术和物联网。 - 数据挖掘旨在使用一系列处理流程，从不同格式的异构数据源中为特定应用目标提取 简明扼要的、可操作性强的 洞察及理解。

经典案例： - 沃尔玛：啤酒与尿布 - 奥巴马：美国总统大选连任 - 微软：预测奥斯卡 - 招聘网站：职位信息

数据挖掘的过程

数据收集： 硬件、软件、人工 数据预处理 - 特征提取： 将大量的原始文件、系统日志、商业交易转换为有意义的数据库特征 - 清洗与集成：1.数据清洗： 处理错误或缺失的条目，维护一致性 2.特征选择： 将高维特征空间转换为更适合分析的新数据空间 3.数据转换： 将一些属性转换为另一种相同或类似数据类型的属性 分析过程与算法： 通过数据挖掘过程的“超级问题”或基本模块解决个性化应用

数据准备阶段

数据收集的途径 - 传感器网络等专门的硬件 - 手工录入的用户调查 - Web 爬虫等软件工具 - 从其他系统批量导入

基本数据类型-非依赖型数据

非依赖型数据 Nondependency Oriented Data) - 如多维数据或文本数据，数据项或属性之间没有任何依赖关系。 - 多维数据通常包含一组记录（又称数据点、实例、样例、交易记录、实体、元组、对象或特征向量） - 每条记录都包含一组字段（又称属性、维度或特征） - 例：人口统计数据集

非依赖型数据的分类 - 定量型的多维数据（Quantitative Multidimensional）：连续的、数值的或定量的属性：如年龄；便于分析处理：均值、方差等运算 - 类别型和混合型数据（Categorical and Mixed Attribute）：类别型数据：离散且无次序的值，如性别、种族和邮政编码；混合型数据：数据项既有定量型的又有类别型的 - 二元和集合数据（Binary and Set）：多维类别型数据的特例：表示离散的类别；多维定量型数据的特例：可以给予两个值先后次序；集合归属数据：表示元素是否隶属于某个集合 - 文本数据（Text）：直接表示为字符串时，单词之间有次序关系，是一种依赖型数据；表示为文档术语矩阵时，是一种多维定量型数据，存在数据稀疏性问题

基本数据类型-依赖型数据

依赖型数据 (Dependency Oriented Data) - 数据项之间可能有某种隐式的相互依赖关系（时间、空间）或者显示的依赖关系（比如数据项之间有某种网络的链接关系）。 - 隐式依赖关系：相关领域有“通常”存在的、数据项之间的依赖关系，如传感器连续收集的时序数据 - 显式依赖关系：用图或网络数据显式地给出数据项之间的关系

时间序列数据 ：随着时间的推移通过连续测量所生成的数值 - 多元时间序列的定义：一个长度为 𝑛，维度为 𝑑的矩阵在 𝑡1,⋯,𝑡𝑛这 𝑛个时间戳的每个时间点上有 𝑑个定量型特征（上下文属性：对应于时间维度，如传感器数据中表示测量时间的时间戳；行为属性：对应于测量的数值，如传感器数据的读数） - 典型问题：时序预测（根据单变量 𝑖的历史时间序列 𝑧𝑖,𝑡，预测未来时序的行为）

离散序列和字符串 - 多元离散序列的定义：一个长度为 𝑛，维度为 𝑑的矩阵在 𝑡1,⋯,𝑡𝑛这 𝑛个时间戳的每个时间点上有 𝑑个离散值 - 事件日志：计算机系统依据用户的活动创建日志（例如，一个金融网站上的用户操作日志如下，可能代表用户试图闯入一个有密码保护的系统）

• 生物数据：如核苷酸、氨基酸字符串，提供了有关蛋白功能的特性信息

空间数据 ：上下文属性用于表示空间位置 - 如气象学数据中的经度、纬度为上下文属性

时空数据 ：包含时间和空间两种属性 - 测量时间和空间的动态行为属性：如随着时间的推移测量海面温度变化 - 轨迹数据：在时空环境下，对一个或多个移动对象运动过程的采样所获得的数据信息

时空数据举例 - 出租车 订单数据（订单的起终点经纬度、订单类型、出行品类、乘车人数等） - 百度迁徙数据（迁入和迁出人口地和规模） - 微信宜出行数据（ 人流量、经纬度等 - 地铁刷卡数据（进出站流量、乘车时间等）

网络和图数据 - 一个网络 𝐺=(𝑁,𝐴)包含一组节点 𝑁和一组边 𝐴，数据值对应于网络中的节点而数据值之间的关系对应于网络中的边。边 (𝑖.𝑗)可以是有向或无向的，取决于当前的应用。 - Web 图：节点对应于网页，有向边表示超链接及方向，网页中的文本是相应网页节点的属性。 - 社交网络：节点对应于社交网络用户，边对应于朋友关系，社交页面的内容是节点上的属性数据，邮件及聊天的通信记录是边上的属性数据。 - 化合物数据库：节点对应于元素，边对应于元素之间的化学键。

数据预处理概述

为什么要对数据预处理？ - 低质量的数据导致低质量的挖掘结果 - 影响数据质量的因素有：准确性、完整性、一致性、时效性、可信性、可解释性

数据预处理的主要步骤 - 数据清洗 - 数据集成 - 数据归约 - 数据变换

数据清洗

缺失值 填充方法 - 直接删除法：如分类问题中缺少类标号时 - 人工填写缺失值 - 使用一个全局常量填充：如 𝑁𝐴𝑁或 −∞等 - 使用属性的均值、众数、中位数填充 - 使用最可能的值：如通过回归、贝叶斯推理、决策树等来推断

填充工具 - Python Pandas 中的 fillna 函数、 interpolate() 插值函数， sklearn 库函数等 - R Hmisc 包、 missMDA 包等，包含多种函数，支持简单插补、多重插补和典型变量插补

噪声（错误或不一致）：被测量的变量的随机误差或方差 光滑法 - 分箱（Binning）：通过考察数据的近邻来光滑有序数据值（例：一组数据 4,8,15,21,21,24,25,28,34 ，划分到 3 个箱中） - 回归 (Regression)：用一个函数拟合来光滑数据 领域知识约束法：限制了属性值的范围和不同属性之间的约束 - 如：生日与身份证号之间的关系，国家 城市 区之间的限制 检测法 ：利用数据的统计行为特征检测异常点

数据归约

数据归约的作用 ：更简洁地表示数据，但仍接近于保持数据的完整性 数据归约的策略 - 维归约：减少考虑的随机变量或属性的个数（小波变换、主成分分析等；特征选择工具： sklearn.feature_extraction 模块、 FeatureSelector 库等） - 数量归约：用较小的数据表示形式替换原数据（参数方法：使用模型估计数据，仅存储模型参数；非参数方法：直方图、聚类、抽样、数据立方等） - 数据压缩：使用变换压缩数据，如果原数据能从压缩后的数据重构，称为“无损的”

数据变换

数据规范化 ：把属性数据按比例缩放使之落入一个特定的小区间，如 [1,1] 或 [0,1]

为什么要规范化？ 属性值的度量单位可能影响数据分析，具有较大值域的属性倾向于有较大的影响或较高的权重。

规范化的方法 - min-max 规范化：设 𝑚𝑖𝑛𝐴，𝑚𝑎𝑥𝐴分别为属性 A 的最小值和最大值，min-max 规范化把 A 的值映射到新区间 𝑛𝑒𝑤_𝑚𝑖𝑛𝐴，𝑛𝑒𝑤_𝑚𝑎𝑥𝐴中 - z score 规范化（标准化）（使用均值和标准差进行规范化；其中 \(\bar{A}\) 表示均值，\(s_{A}\)表示标准差）

数据挖掘使用的技术

主要任务

考虑一个具有 n 个记录和 d 个属性的多维数据库 D ，每行对应于一条记录，每列对应于一个维度。数据条目之间的关系有两种：

列之间的关系 - 关联模式挖掘： 确定在一行中各值之间频繁或罕见的关系 - 数据分类： 通过其他列与特殊列的关系预测特殊列的缺失值

行之间的关系 - 聚类 ：把行分成多个子集，使得属于一个子集中的行在相应列的值上具有相关性 - 异常检测： 一行的列值与其他行中相应的列值很不一样 （需要用到大量概率统计知识

这四个问题构成了数据挖掘的主要任务。

异常检测简介

什么是异常点？与其他观察值偏离很多的值，也称作孤立点、不和谐点、离群点或不规则点

异常点的类型 - 全局异常点：显著地偏离数据集中的其他对象 - 情境（条件）异常点：关于对象的特殊情境，显著地偏离数据集中的其他对象 - 集体异常点：数据对象的一个子集显著地偏离数据集中的其他对象

异常检测模型的输出 ：数据点的异常程度被量化为一个数值，称为异常分 （outlier score） - 实数值的异常分（定量地表达一个数据点是异常点的倾向；越大（越小）的分数说明数据点越可能是异常点；可以为概率值，量化是异常点的可能性） - 二元标签：输出一个点是否为异常点的二元结果

异常检测的应用： - 数据清洗：去除噪声 - 信用卡欺诈：检测罕见的信用卡活动模式 - 网络入侵检测：检测网络流量中罕见的记录或罕见的趋势改变

关联模式挖掘

“购物篮分析”——一个经典问题

关联模式挖掘的应用： - 超市数据：提供关于目标营销和货架摆放的有用信息 - 文本挖掘：发现同时出现的术语和关键词 - 推广到时序数据、序列数据、空间数据和图数据：用于互联网日志分析、软件程序 - 错误检测、时空事件探测等 - 作为子程序，为聚类、分类、异常分析等问题提供解决方案

基本概念

以如下超市数据为例

• 支持度(Support)：某个商品组合出现的次数与总次数之间的比例
• 频繁项集 ：支持度大于等于最小支持度的集合
• 如果定义 最小支持度 minsup =0.3 ，则频繁项集为{Bread, Milk}
• 支持度的一些性质：支持度越小，频繁项集数越多；支持度单调性 ：项集的任意子集的支持度 该项集的支持度；向下闭包性 ：频繁项集的每个子集也是频繁的
• 最大频繁项集 ：在一个给定的最小支持度下，如果项集 L 是频繁的，且它的任何超集都不是频繁的，那么称 L 为最大频繁项集
• 通过最大频繁项集可以推导出所有的频繁项集（为最大频繁项集的子集，共 11 个）
• 置信度 ( Confidence)：指当你购买了商品 A，会有多大的概率购买商品 B \[ conf(X \Rightarrow Y)=\frac{sup(X \cup Y)}{sup(X)} \]
• 关联规则 ：令 X 和 Y 为两个项集，若满足以下两个条件，则规则 X Y 是最小支持度为 minsup 和最小置信度为 minconf 的强关联规则（项集 X∪Y 的支持度>=minsup ，即 X∪Y 是一个频繁项集；规则 X Y 的置信度>=minconf）

关联规则生成框架

生成关联规则的总体框架 - 第一阶段：以最小支持度 minsup ，生成所有频繁项集 计算密集 - 第二阶段：以最小置信度 minconf ，从频繁项集中生成关联规则 相对简单（给定一个频繁项 集的集合 𝐹，对于集合中的每个项集 𝐼 把 𝐼分解 成所有可能的集合 𝑋和集合 𝑌=𝐼−𝑋的 组合，满足 𝐼=𝑋∪𝑌；计算每条规则 X Y 的置信度，保留满足最小置信度要求的规则）

置信度单调性： 如果项集 𝑋1、𝑋2和 𝐼满足 𝑋1⊂𝑋2⊂𝐼，那么 c𝑜𝑛𝑓(𝑋2⇒𝐼−𝑋2)≥𝑐𝑜𝑛𝑓(𝑋1⇒𝐼−𝑋1)

不同商品的展开可构成 项集格 Lattice，如项空间包含 5 项时，总共有 \(2^{5}=32\) 个项集节点

它是频繁模式的搜索空间

频繁项集挖掘算法

暴力算法 主要思想： 生成所有的可能的频繁项集，在事务数据库上计算其支持率，检查给定的项集是否是每个事务的子集

穷举的问题：一个项空间 𝑈除去空集共有 \(2^{\lvert U \rvert }-1\)个不同的子集，当 |𝑈|很大时，计算是不现实的

提高算法效率的方法 - 利用向下闭包性，通过剪除候选项集来缩小搜索空间 - 对候选项集计数时，通过剪除已知的与此候选集不相关的事务，使计数更加高效 - 使用紧凑的数据结构表示候选项集或事务数据库，实现快速的计数

Apriori算法 主要思想 ：由向下闭包性可知，频繁项集的任意子集也是频繁的，如果一个项集是非频繁的，那么对它的超集进行支持率计数就没有意义

算法流程： - k=1 开始，对比数据库计算 k 项集的支持度 - 筛选掉小于最小支持度的项集 - 当 k 项集不满足条件时， k+1 项也不满足条件，即可剪枝，停止该方向的搜索 - 否则k=k+1，重复 1-3步

聚类

基本概念

聚类的定义：将数据集中的样本划分成若干个通常不相交的子集，使得类内相似度高，类间相似度低。

聚类的应用 - 数据汇总：从数据中提取摘要信息（或简明的见解） - 客户分类：分析相似用户组的共同行为特性如，协同过滤 - 社交网络分析：通过连接关系而紧密聚集的节点通常属于相似的组 - 与其他数据挖掘问题的关系：聚类常用在分类或异常检测模型的预处理步骤

什么是聚类中心？ - 关于簇中的数据点的函数（例如均值） - 从簇中现有的数据点中选择

算法思想 - 构造 K 个聚类中心 - 考察数据点之间的相似度 距离 - 将数据点分配给距离最近的中心 - 调整聚类中心，使其类内的数据点到中心的距离总和最小 - 反复迭代直至收敛 - 关键在于：如何衡量数据点的相似度 距离，采用不同的距离函数和中心生成策略衍生出不同的算法版本

欧氏距离：最简单常用的距离，但也正由于将所有维度等同看待，不能满足一些特定需求

K-Means算法

距离函数：欧式距离（L2范数） 中心点：平均值 步骤 - 初始化：为给定样本集合𝑋 = (𝑥𝑖𝑗 )𝑚×𝑛，随机初始化K个随机聚类中心 - 分配样本点：计算每个点到聚类中心的距离，并将之分配到距离它最近的聚类中心 - 更新聚类中心：利用每一类点的均值作为新的聚类中心 - 重复第2步和第3步，当算法在新的一轮迭代中聚类中心没有更新，或者到达迭代的最大代数，算法终止，输出聚类中心

局限性 - K 值需预先给定 - 对初始选取的聚类中心点敏感，不同的随机种子点得到的聚类结果不同 - 使用贪心思想迭代，算法常常收敛至局部最优解，无法获得全局最优解 - 不适合所有数据类型：如不适合处理非球形簇、不同尺寸和不同密度的簇 - 找到最优划分是 NP 难问题（Aloise 2009）

基于代表点的算法 K Medians 算法 - 距离函数：曼哈顿距离（ L1 范数） - 中心点：中位数 - 优点：比起 K Means 算法鲁棒性更好，使用中位数相较于均值更不容易受到噪声和异常点的干扰

K Medoids 算法 - 距离函数：曼哈顿距离（ L1 范数） - 中心点：数据集中的一个点 - 优点：不容易受到噪声和异常点的干扰；一些数据类型的中心点难以计算，如变长时间序列，该方法可以应用于任何一种数据类型，只要有合适的相似度度量函数

层次聚类算法

优点：不同层次的聚类粒度给应用提供了不同的视角 例：开放式目录网站的分类，这种组织结构使得用户可以方便地手动阅览

自底向上（凝聚）法 - 开始每个数据点看作一个簇 - 衡量簇之间的相似度，将相似度高的小簇合并成为更大的簇 - 终止条件：到达合并簇距离阈值或簇数阈值

自顶向下（分裂）法 - 从数据点集合向下递归地划分成树状结构 - 终止条件：树的高度达到特定要求或每个节点包含的数据数目少于预定值 - 优点：可以更好地控制树的整体结构，如树的度和分支之间的平衡性 - 二分 K Means 算法（每个结点分裂成两个孩子节点；增长策略——优先分裂所含数据点最多的节点，优先分裂与根节点最近的节点）

基于网格和密度的算法

出发点： 可以对任意形状的簇进行聚类 核心思想 - 识别数据中细粒度的密集区域，它们是构建任意形状的簇的“构建块” - 将这些区域合并为簇

代表算法 基于网格的算法（需要确定的参数：网格数量、密度阈值）

DBSCAN 算法（基于密度的算法） 记半径为 Eps ，密度为 τ ，将数据点分类为 - 核心点 ：至少包含 τ 个数据点 - 边界点 ：包含小于 τ 个数据点且半径内至少包含 1 个核心点 - 噪点 ：既不是核心点也不是 边界点 - 步骤：从某个核心点出发，不断向密度可达的区域扩张，从而得到一个包含核心点和边界点的最大化区域，区域中任意两点密度相连

分类

分类的定义 ：给定一个训练数据集，其中每个数据点带有一个类标签，确定一个或多个之前未见过的测试实例的类标签。

分类的应用 | 应用 | 特征 | 标签 | | -------------- | ---------------------- | ---------------------- | | 消费者目标营销 | 客户历史购买行为 | 客户是否对某商品感兴趣 | | 医疗疾病管理 | 病人医疗检测和治疗方案 | 治疗效果 | | 文档分类与过滤 | 文档中的单词 | 文档的主题 | | 多媒体数据分析 | 照片、视频、音频特征 | 用户的特定行为 |

基本概念

分类算法的两个阶段 - 训练阶段：通过训练 样例构建 一个训练模型 - 测试阶段：通过训练模型确定之前没有见过的测试实例的类标签

输入： 数据集 𝐷，其中含有 𝑛个数据点和 𝑑个特征 输出 - 标签预测（手写数字识别） - 数值分数（适合某一个类别稀少的情况）（给每一个实例 标签组合打一个分数，衡量该实例属于某个特定类别的倾向大小） - 数值分数取最大值 取在不同类别上加权最大值  标签预测

决策树

决策树学习的本质 ：从训练集中归纳出一组划分准则，使得树的每个分支的类变量的“混杂”程度逐层减小且尽可能小

步骤： ①将所有的数据看成是一个节点； ②从所有的特征（属性）中 挑选一个属性 a 对划分该节点 ③生成若干孩子节点，依次判断每个孩子节点 是否满足停止分裂条件： (1)若是，跳转 ④ (2)否则，跳转 ② ④设置该节点是叶子节点， 对应的类别定义为该节点在训练数据上数量占比最大的类别。

核心问题：如何选择分裂特征？何时停止节点分裂？

什么是好的划分准则？ 使决策树的分支节点所包含的样本尽可能属于同一类别。

量化划分准则质量的指标 - 错误率（Error）：令 𝑝为数据集 𝑆中属于主导类别的实例比例，则错误率为 1−𝑝；选择错误率最低的划分 - 基尼系数（Gini Index）：反映了从数据集中随机抽取两个样本，其类别标记不一致的概率；具体计算方法见Slide 19第54-55页

停止准则 - 过拟合：在训练集上表现很好，在测试集上表现不佳（当决策树生长到最末端，直到每一个叶节点只包含某个特定的类时，得到的决策树能 100% 正确分类训练数据中的实例，但此时决策树已经过拟合于训练样例中的随机特性） - 剪枝：修建决策树过拟合的部分，把内节点转换为叶节点（保留一小部分（如 20%20%）的训练数据，在剩下的数据上构建决策树；在保留数据集上测试剪除掉一个节点对分类准确率的影响，若提高，则剪掉这个节点；反复对叶节点进行剪枝，直到通过剪枝不能再提高准确率为止）

推荐系统

简介

推荐系统是一种 信息过滤系统 ，用于预测用户对物品的评分或偏好。

把那些最终会在节点之间产生的连接找出来。（人与人之间、人与商品之间、人与咨询之间）

设计要诀：已经存在的连接->未来的连接

发展史

• 1994：明尼苏达大学，第一个自动化推荐系统
• 1997：Resnick等人首次提出“推荐系统”（Recommender System）一词
• 2003：亚马逊Linden 等人，公布基于物品的协同过滤算法
• 2006：Netflix举办电影推荐算法竞赛，引起了学术界和工业界的极大关注
• 2007：第一届ACM 推荐系统大会在美国举行
• 2016：YouTube发表论文，将深度神经网络应用推荐系统中
• 2019：强化学习用于推荐系统，蚂蚁金服提出生成对抗用户模型

算法

算法分类

推荐系统可以利用的信息：物品特征（关键词、类别、品牌等），用户特征（性别、年龄、地域、画像等），用户物品交互（评分、购买数、喜欢、转发等）

推荐系统算法的分类： - 基于内容：主要使用用户和特征的特征信息； - 协同过滤：主要基于用户 物品交互； - 结合新技术的新兴算法： 图嵌入、神经网络、深度学习

基于内容的推荐系统

基本思想：给用户推荐与其曾经喜爱的物品的相似物品 例如：电影：相同的演员，导演，电影风格 新闻：相似的主题，事件，人物，地点 书籍：同一作者，出版社，类型

基于内容的推荐步骤

• 物品表示：为每个物品抽取出一些特征来表示此物品。并将这些特征通过向量的形式组合在一起。
• 用户偏好学习：利用一个用户过去喜欢（及不喜欢）的物品的特征数据，来学习出此用户的喜好特征（Profile）。
• 生成推荐：通过比较上一步得到的用户偏好与候选物品的特征，为此用户推荐一组相关性最大的物品。

物品表示

物品(Item)有一些可以描述的属性，包括结构化属性和非结构化属性， 表示物品即需要对其不同的属性进行编码。

例如在电影网站上，物品(Item)即不同的电影 - 结构化属性：类别、国家、主角等 - 非结构化属性：电影简介，用户评论等 - 例如编码：成龙主演的某动作片在中国大陆上映

相似度计算

将用户画像和物品画像表示成向量，计算相似度，来度量用户偏好

余弦相似度：计算两个向量夹角的余弦值，从方向上区分差异，而对 绝对数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，

欧式距离：从维度的 数值大小 中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异

常用相似度

余弦、杰卡德、欧几里得、曼哈顿、切比雪夫、闵可夫斯基、皮尔逊相关系数、斯皮尔曼相关系数

用户偏好学习

用户历史上包含很多类型的物品交互记录 - 显示记录： 评分，评论，投票等，直接表达用户偏好信息 - 隐式记录： 点击，购买，关注，点赞等，相比显示记录有时更能反映用户偏好

如何对隐式记录进行建模以学习用户偏好特征是推荐系统的重点及难点，常用方法：时间序列模型（长短期记忆网络（LSTM）、循环门控单元（GRU）），注意力机制（Self-Attention模型、Transformer模型）

生成推荐

用户偏好学习(Profile Learning)模型：

基于内容的推荐系统

优点 - 为某一用户做推荐时不需要其他用户的数据 - 可以为具有特殊口味用户做预测 - 可解释性好，物品的特征决定了推荐值

缺点 - 某些物品的特征提取比较难，例：图像，音乐，电影，如果对应的人没有元数据（例如风格，演员，导演，作者等），自动提取特征较难 - 推荐物品过于单一，永远不会推荐和用户曾经喜欢的物品不相关的物品，完全没有利用其他用户的喜好提高对此用户的推荐质量 - 对于新用户有冷启动（ Cold Start ）问题，新用户的用户画像为空，无法做出推荐

协同过滤

利用用户的交互来过滤感兴趣物品。可以将交互的集合可视化为一个矩阵，其中每一项 (𝑖,𝑗)代表用户 𝑖和物品 𝑗的交互。

利用矩阵分解，补全评分矩阵R 中的未知用户 物品交互，可得到两个新的矩阵 U和 I ，满足 U × I 和 R 的所有已知项相等。那么， U × I 也提供了 R 中未知项的值，这些值可以用来生成推荐。

基于用户的协同过滤算法（UserCF） - 推荐系统中最古老的算法，基于用户的协同过滤方法的诞生标志了推荐系统的诞生 - 主要包括两个步骤：1.找到和目标用户兴趣相似的用户集合2.找到这个集合中的用户喜欢的，且目标用户没有听说过的物品推荐给用户

基于物品的协同过滤算法（ItemCF） - 目前业界应用最多的算法，亚马逊、 Netflix 、 Hulu 、 Youtube 等的基础推荐算法 - 主要包括两个步骤：1.计算物品之间的相似度2.根据物品的相似度和用户的历史行为给用户生成推荐列表

UserCF和ItemCF优缺点对比

	UserCF	ItemCF
性能	适用于用户较少的场景，如果用户数量很多，计算用户相似度矩阵代价很大	适用于物品数目明显小于用户数的场合，如果物品很多（网页），计算物品相似度 矩阵代价很大
领域	实时性较强，用户个性化兴趣不太明显的领域	长尾物品丰富，用户个性化需求强烈的领域
实时性	用户有新行为，不一定造成推荐结果立刻变化	用户有新行为，一定会导致推荐结果的实时变化
推荐理由	很难提供令用户信服的推荐解释	利用用户的历史行为给用户做推荐解释，可以令用户比较信服

知识图谱

• 知识图谱是一个有向异构图，包含节点和节点间的关系
• 一个知识图谱由很多三元组组成（ head relation tail
• 推荐系统中的项目也是知识图谱中的节点

图嵌入

淘宝（阿里公司）基于图嵌入的推荐算法：获得用户行为序列->构建有向图->获得随机游走序列->神经网络训练

应用

应用流程

推荐系统应用的一般流程：建立用户与产品数据库->提取用户与产品特征->应用推荐算法获得推荐结果->向用户展示推荐结果

国内现状

推荐系统已经被应用于诸多与生活息息相关的领域中，国内涌现了一 大批互联网企业，引领了推荐系统的研究。

数据可视化

概述

疫情下的数据表达 - 患病年龄分布——直方图 - 病患总数排名——柱状图 - 治愈率-死亡率分布——气泡图 - 每日新增情况——折线图 - 患病类型比例——饼图 - COVID-19疫情地图——地图

定义

维基百科定义：数据可视化旨在借助于图形化手段，清晰有效地传达与沟通信息

为什么需要可视化？ - 直观：重要的见解往往隐藏在数据之中，而单纯查看数据往往无法获知 - 生动：数据可视化让数据生动起来，快速有效得到问题的关键性见解 - 有效：可视化是分享和交流信息的有效工具（展示模型结果，传达疫情趋势，了解政策影响，显示数据关系）

分类

数据对比图：折线图、柱状图、杆图、堆叠图 数据统计图：饼图、环图、雷达图、南丁尔格玫瑰图、旭日图 数据分布图：箱型图、直方图、小提琴图、蜜蜂图 离散数据图：散点图、气泡图、热力图、矩阵视图 文本可视化：词云、文档卡片、新闻地图 地理可视化：散点地图、区域地图、热力地图、气泡地图、统计地图 信息关联图：桑葚图、主题河流、弦图、弧图、圆装箱图 层次网络图：树图、网络图、金字塔图 函数解析图：一元/多元函数、极坐标图形、三维曲线/平面 示意图：流程图、思维导图

类型

描绘数据的变化–折线图（Plot Line）

• 显示随时间（根据常用比例设置）而变化的连续数据，非常适用于显示在相等时间间隔下数据的趋势、
• 类别数据沿水平轴均匀分布，所有值数据沿垂直轴均匀分布

突出数据的排序–条形图（Bar Chart）

• 用宽度相同的条形的高度或长短来表示数据多少的图形，可以横置、竖置
• 条形图是统计图资料分析中最常用的图形（能够一眼看出各个数据的大小，易于比较数据之间的差别）

突出数据的排序–柱状图（Bar Chart）

突出数据的排序–堆叠图（Stack Diagram）

• 堆叠有两种形式，普通的堆叠和按百分比堆叠；普通堆叠是按照数值大小依次堆叠，百分比堆叠是按照数值所占百分比进行堆叠
• 默认情况下图形是根据数据列的属性依次从上到下堆叠的，可以设置堆叠反转（ReversedStacks）属性可以将这个顺序调换，即从下到上堆叠

突出数据的排序–正反对比图

描述数据的分布–直方图（Histogram）

• 用来显示在连续间隔或特定时间段内的数据分布。
• 当中每个条形表示每个间隔/时间段中的频率。直方图的总面积也相等于数据总量。直方图有助于估计数值集中位置、上下限值以及确定是否存在差距或异常值；也可粗略显示概率分布

描述数据的分布–饼图(Pie Chart)

• 显示一个数据系列：在图表中绘制的相关数据点，这些数据源自数据表的行或列
• 使用要求：1.仅有一个要绘制的数据系列；2.要绘制的数值没有负值；3.要绘制的数值几乎没有零值；4.类别数目无限制；5.各类别分别代表整个饼图的一部分；6.各个部分需要标注百分比

描述数据的分布–雷达图(Radar Chart)

• 从同一点开始的轴上表示的三个或更多个定量变量的二维图表的形式显示多变量数据的图形方法
• 主要用于查看哪些变量具有相似的值、变量之间是否有异常值；也可用于查看哪些变量在数据集内得分较高或较低

描述数据的分布–南丁格尔玫瑰图(Rose Chart)

• 最早由弗罗伦斯·南丁格尔发明，又名为极区图。
• 是一种圆形的直方图

描述数据的分布–玫瑰图变种

描述数据的分布–灵活变种

描述数据之间的相关性–散点图（Scatter Plot）

• 表示因变量随自变量而变化的大致趋势，据此可以选择合适的函数对数据点进行拟合
• 通常用于显示和比较数值，例如科学数据、统计数据和工程数据

描述数据的概率分布–箱式图(Box Plot)

• 箱式图又称盒须图、盒式图或箱线图，是一种用作显示一组数据分散情况资料的统计图。
• 能显示出一组数据的最大值、最小值、中位数、及上下四分位数。

描绘数据的概率分布–小提琴图(Violin Chart)

• 小提琴图(ViolinChart)用于显示数据分布及其概率密度
• 结合箱形图和密度图的特征，主要用来显示数据的分布形状。上下两条线段代表95%置信区间；中间的线段为中位数；左右的浅蓝色区域描绘了数据的概率分布

描述数据之间的相关性–气泡图（Bubble Chart）

• 一种包含多个变量的图表，结合了散布图和比例面积图。使用笛卡尔双轴座标来绘制数值点
• 每一点都会获分配一个标签或类别（在旁边或图例中显示）。每个数值点再以其圆形面积表示第三个变量

描述数据之间的相关性–相关图/热力图（Heat Map）

• 将一个表结构一样的数据，可以是一个矩阵，以表的结构呈现出来。每一个位置的颜色代表了该元素的数值大小
• 如果每一行（每一列）代表数据中的一个维度或一个属性，则此时的图表称为相关图

表格透视–数据透视表（Pivot Table）

• 数据透视表（PivotTable）是一种交互式的表，可以进行某些计算，如求和与计数等。所进行的计算与数据跟数据透视表中的排列有关
• 创建数据透视表后，可对其进行自定义以集中在所需信息上。自定义的方面包括更改布局、更改格式或深化以显示更详细的数据
• 表格透视（TableLens）：不直接列出数据在每个维度上的值，而是将这些数据用水平横条或者点表示，占用的空间较少，可以在有限的屏幕空间中表示大量的数据和属性

矩阵视图（Matrix View）

• 矩阵的行代表承载用户观念的载体，列代表用于的评价属性，颜色用于传达用户的观念倾向程度，而矩阵中的小格子则表示参与评价的用户人数
• 例如：新闻数据中蕴藏的情感信息可视化效果。其中不同性质的图元代表不同的评价对象，水平轴指示时间属性，纵轴代表用户观念分数

文本可视化–词云（Word Cloud）

• “词云”就是通过形成“关键词云层”或“关键词渲染”，对网络文本中出现频率较高的“关键词”的视觉上的突出
• 词云图过滤掉大量的文本信息，使浏览网页者只要一眼扫过文本就可以领略文本的主旨

文本可视化–主题河流（Theme River）

• 主题河流图是一种特殊的流图,它主要用来表示事件或主题等在一段时间内的变化
• 主题河流中不同颜色的条带状河流分支编码了不同的事件或主题，河流分支的宽度编码了原数据集中的value值

地理信息可视化–地图（Map）

• 按照一定的法则，有选择地以二维或多维形式与手段在平面或球面上表示地球（或其它星球）若干现象的图形或图像
• 它具有严格的数学基础、符号系统、文字注记，并能用地图概括原则，科学地反映出自然和社会经济现象的分布特征及其相互关系
• 由使用地图语言表示事物所产生的直观性。地图上表示各种复杂的自然和人文信息都是通过地图语言来实现的

地理信息可视化–点示地图（Dot Map）

• 点示地图(DotMap)在地理区域上放置圆点，旨在检测该地域上的空间布局或数据分布

地理信息可视化–线数据

• 流向地图(FlowMap)在地图上显示信息或物体从一个位置到另一个位置的移动及其数量，通常用来显示人物、动物和产品的迁移数据。
• 单一流向线所代表的移动规模或数量由其粗幼度表示，有助显示迁移活动的地理分布

地理信息可视化–区域数据

地理信息可视化–POI网格视图

流数据可视化–桑基图（Sankey Diagram）

• 用来显示流向和数量（彼此之间的比例）。箭头或线的宽度用于显示大小，因此箭头越大，流量也越大
• 桑基图非常适合描述数据流（Flow），我们可用不同颜色来区分图表中的不同类别

描述数据随时间的演变–弧图(Arc Diagram)

• 弧图(ArcDiagram)是二维双轴图表以外另一种数据表达方式
• 在弧线图中，节点(Nodes)将沿着X轴（一维轴）放置，再利用弧线表示节点与节点之间的连接关系
• 每条弧线的粗幼度表示源节点和目标节点之间的频率。弧线图适合用来查找数据共同出现的情况

基于时间线发展势态图

态势可视化(Generative Graph) - 该看板以团队发明的通用可视化图表‘跌落态势图’为核心，主要用于可视化呈现部分省市COVID-19 患者每个个体从发病到治愈，以及从接触到发病等不同维度的历程与时间分布。 - 试图通过这种可视化方法观察患者病程与病毒传代，毒力，及潜伏期之间可能存在的关系。

网络可视化–树形结构图（Tree Map）

• 树状结构图(TreeMap)是一种利用嵌套式矩形显示层次结构的方法，同时通过面积大小显示每个类别的数量

网络可视化–基本网络图（Network）

• 网络图(Networkplanning)是一种图解模型，形状如同网络，故称为网络图。网络图是由作业（箭线）、事件（又称节点）和路线三个因素组成的
• 选择基本网络图后，可以快捷修改数据。网络图中不能出现循环路线

描述一个工作过程的具体步骤–流程图（Flow Diagram）

• 流程图用图形化的符号记录整个系统和系统各模块的结构，描述了系统各子系统、相关文件和数据之间的关系。
• 形象直观，各种操作一目了然，不会产生“歧义性”，便于理解
• 缺点是所占篇幅较大，由于允许使用流程线，过于灵活，不受约束，使用者可使流程任意转向，从而造成阅读和修改上的困难

可视化技术

可视化与工具–Web 工具

基于前端套件：HTML、CSS、JavaScript 工具繁多：HighCharts、Echarts、D3.js… 特点：效果美观，套用模版，简单易学，便于实现可视化交互

可视化与工具–编程语言

Python：Matplotlib，功能全面，风格简洁、朴素而正式；不提供交互式界面（对比Matlab），只能自己查阅文档，修改参数。入门易，进阶难；适用于快速可视化实验结果 Seaborn：基于Matplotlib，提供更为高层的API Plotly：提供了更加现代化、更美观的图形输出，提供交互式绘图，可以制作3D图像 Matlab/Mathematica：优势是与进行计算的程序可无缝对接，缺点是作图不如专门的作图工具美观，Matlab提供交互式作图，大大提升了作图效率，降低了对文档的依赖和上手难度 R+ggplot2：核心理念是将绘图与数据分离，可以快速地将可视化结果转化成好看的、现代化主题 TikZ：基于LaTeX，方便与正文字体保持高度一致性，易于在图中插入公式，学习曲线略微陡峭

可视化与工具–可视化软件

Gnuplot：基于命令行的交互式图工具，优点是速度快、画风清爽，软件开源且免费，图片质量相当专业 Gephi：开源作图软件，专长于制作网络图；内置了许多先进的网络图可视化算法供用户选择；作为桌面软件，可以交互式操作，上手快；作为桌面软件失去一定的灵活性，不具备作复杂网络图的能力，数据量大时会有卡顿

可视化与美学

聚焦 - 将用户注意力吸引到重要的区域上 - 通过形状、大小、朝向、权重、位置、颜色等形成对比 平衡 - 有效利用空间 - 使重要元素位于中间 - 使各元素在空间中平衡分布 简单 - 避免包含过多造成混乱的图形元素 - 平衡美学特征与信息量 生动 - 使用形象的图像、符号以及视觉隐喻 - 通过交互拉近传者与受者的距离

可视化，为有精度地观察疫情而设计 疫情可视化包含95%以上的图表类型 - 常规条形图、折线图、气泡图等基本图形 - 网络关系图、日历图、南丁格尔玫瑰图 涵盖病例数据、人口流动、知识科普、应对措施、疫情影响等

可视化的作用 - 通过数据可视化，辨别出更广阔的疫情背景和更详尽的情景 - 借助具体疫情数据和呈现，可以辅助检测政策是否合理 - 跟踪进度，发现趋势，给出明智的战略性决定