UESTC大数据分析课程

大三大数据课程上课笔记以及课下补充

数据分析（机器学习算法基础）：

数据关系算法：

• 获取心的知识或者技能嗷！！！
• 知识体系：
  • 统计学
  • 人工智能
  • 信息论
  • 认知科学
  • 计算复杂性
  • 控制等

TF-IDF算法：

• Term Frequency-Inverse Document Frequency

• 典型的应用是一堆文档中选择属于每个文本最具有代表性的词汇。

• 常用于检索系统的加权技术。

• What is key-word ? A word can describe the whole passage.

词袋模型：

• 第一步：将文本转换为向量，转换为能够作为计算的数量，即把文本转换到数量空间。（向量空间模型）
  • what is 词袋模型：
    • 一种广泛用于自然语言处理和信息检索的词语模型
    • 若干词语直接放在一个“袋子”中，而不考虑词语间的语法和相互顺序
  • A,B取所有词的并集构成词袋，然后词袋分别在A,B文档中遍历一次，获得每个文档对应的向量（长度是相同的，因为词袋的大小是固定的嗷！！）
  • 词袋模型仅仅与词频有关系，但是对于逻辑，语义和顺序是没有关系的嗷！！！
• 基本思想：文档中的每个词的重要性与它在当前文档中出现的次数成正比，但是与它在其他文件中出现的次数成反比。（想法：找出每个文档中特有的词汇嗷！！！）
• 推论：如果某个词在A中出现频率高，在其他中出现很低，那么这个文档就可以由这个词语进行区分嗷！！！

过程：

缺点：

1. 对于过长文本和短文本的处理不是很好
2. 忽略了语法和语义的表达
3. 词语之间必须完全匹配，对于相似的词语或者词语的子词语之间不能够进行有效的匹配。

余弦相似性算法：

• 平行的衡量相似度的系数：Jaccard系数，通过符号度量或者布尔值标识，适合集合的计算。
• 直观想法：两篇文章越相似，他们词语的交集就越多。余弦向量的计算公式：

$$
cos{\theta} = \frac{a \times b}{||a|| \times ||b||}
$$

然后通过向量的定义，能够再拆开成数量的计算嗷！！！

优缺点：

1. 余弦相似度考虑了每个词的频次和顺序，Jaccarb则考虑的就少了嗷！！！
2. 长文本计算复杂度高嗷！

Apriori算法：

• 数据的关联规则挖掘就是用这个算法来操作的嗷！！！看似无关的海量历史数据中，挖掘出可能具有的价值信息，再商业活动中会利用数据之间的关系产生较大的商业价值。

• 关联规则反映的是两个或者多个事务相互之间的依存性和关联性。

• 频繁项集算法

• 应用广泛，超市商品关联分析，消费习惯分析等。。。

• 概念：

  • 项集：项的结合。
  • 关联规则：蕴含表达式，其中X和Y是不相交的项集。
  • 支持度：关联规则的支持度，说白了就是联合概率密度。
  • 置信度：项集X发生的情况下，项集Y发生的概率。
  • 最小支持度：统计意义上的最低重要性。
  • 最小置信度：人为按照实际意义的阈值，表示关联规则的最低可靠性。
  • 频繁项集：满足最小支持度的所有项集，称为频繁项集。

• 如果一个集合是频繁项集，那么它的所有集合都是频繁项集合。如果一个集合它不是频繁项集，那么它的所有超集都不是频繁项集。

算法流程：

1. 扫描历史数据，对于每项数据进行频率次数统计。
2. 构建候选项集C1，并计算其支持度。
3. 对于候选项集进行筛选，形成频繁项集L1。
4. 对于频繁项集L1进行连接生成候选项集C2。
5. 重复上述步骤，最终形成频繁K项集或者最大频繁项集。

缺点：

1. 没有考虑排除一些无关元素。
2. 候选项集产生较多的组合。
3. 每次计算项集的过程都会扫描原始的数据表。
4. 对于数据量较大的系统而言，重复扫描开销大。

解决途径：

1. 压缩数据表
2. 利用哈希表的快速查找特性对于项集进行计数统计。
3. 合理选样
4. FP-Growth算法

PageRank算法：

• 数据关系还可以应用到搜索引擎和推荐系统。
• PageRank的思想：看一个人怎样，看他有什么朋友就知道了。被越多优质的网页所指向的网页，它是优质的网页的概率就越大。
• 假设：
  • 数量假设：一个页面节点接收到的其他页面指向的入链数量越多，那么这个页面越重要。
  • 质量假设：越是质量高的页面指向页面A，则页面A越重要嗷！！！

算法步骤：

1. 每个网页初始化PR值为1/N，其中N为网页总数。
2. 投票算法不断迭代，知道达到平稳分布为止。

常见问题：

• 排名上升
• 排名下沉
• 排名

优缺点：

1. 离线计算获得，减少在线查询的计算量
2. 过分相信链接关系
3. 忽视了主题相关性，旧的页面等级会比新的页面高

分类和聚类：

• 分类与聚类：

  • 监督学习：分类

  需要人类先验的知识，打上flag，例如猫狗大战的训练数据。我们把分类好的数据给计算机，去引导计算机进行学习分类

  • 非监督学习：聚类

  不需要人类先验的知识，也不需要打flag。计算机自己根据传递的数据，将数据分为几类。比如我们给了一坨数据给机器，告诉它咱给他分两类。这个就是聚类嗷！！！

• 分类过程：

  1. 训练
  2. 识别

Naive Bayes（重点）：

• 根据Bayes定理为理论基础，进行了推论嗷！！！
• 贝叶斯的前提：假设所有因素都是无关的嗷！！！
• 贝叶斯公式：

$$
P(H | X) = \frac{P(X|H)P(H)}{P(X)}
$$

• 给定特征W = (w1 , w2 , ... , wn)，给定类别C = (c1 , ... , cm)，然后我们就回去算这个概率嗷！！！
• 我们对于给定的所有特征进行计算，然后比较不同的条件概率，最大的，就是我们判定的标签嗷！！！

AdaBoost（重点）：

• 想法：组合分类器，是一种强分类器。先训练出一批弱分类器，将弱分类器组合为强分类器。
• 具有基于测试过程中的错误反馈调节分类器的分类效果嗷！！！
• 某个样本被错判，下一次迭代过程中，错的样本的权值就会增加嗷！！！同时，判断正确的样本的权值下一轮就会被降低嗷！！！
• 优点：
  • 准确率大幅提高
  • 分类速度快，基本不用调参
  • 过拟合的情况几乎不会出现嗷！！！
  • 构建子分类器时有多种情况可以使用！
  • 方法简单，容易理解和掌握，不用做特征分类。

SVM：

• 适用于小样本，高维模式的识别。
• 基于结构风险最小化：经验风险和置信区间的折中（考虑了容错的哦！！！）。
• 原理：超平面去切这些点的空间，会把点分到两侧。超平面以上是正样本，以下是负样本。（超平面在两边的边界之间嗷！！！）
• 还有个什么核，可以将叠加让平面不规则帮助我们完成分类嗷！！！

KNN：

• 计算并且获得待测样本附近的K个样本
• 根据分类决策规则，投票康康这个点是哪个类的嗷！！！
• 缺点：
  1. 不平衡样本
  2. 计算量相对较大
  3. K值的设定对于算法的结果有很大影响
• 解决途径：在实际应用过程中将类别典型的样本纳入样本库中嗷！！！

K-Means：

• 聚类的方法，非监督学习的方法。核心思想：人以类聚，物以群分嗷！！！
• 聚类的个数往往是人为选取的嗷！！！（但是有章可循）
• 句子之间的相似性可以采用余弦相似性来进行计算嗷！！！
• 缺点：
  • 对于异常值和摇摆值比较敏感，收敛比较慢嗷！！！
  • 非常不适合分布均匀，数据界限不明晰的聚类。
  • 初始中心点的选择对于迭代次数影响大，K-Means++算法，改进了初始点的选择
  • 需要提前确定聚类簇的值嗷！！！

数据决策：

ID3：

• 决策树，是一个预测模型，代表 对象属性和对象值的一种映射关系 。

• 决策树经常用于数据挖掘中的 数据分析和预测 。

• 决策树是一种特殊的树结构，用来创建达到目标的规划。

• 理论基础：

  • 信息熵和信息增益

• 决策树的关键问题：树分支裂变的依据，选择准则。

• ID3算法默认的变量是离散型变量嗷！！！

• 根据什么裂变？

  • 算出每个属性的信息增益
  • 选择信息增益最大的属性来进行裂变
  • 如果结果有确定性，那递归，不然就结束算法嗷！！！

C4.5：

• ID3偏向于选择属性多的属性，因为其信息增益较大，这样某种概念上是不公平的嗷！！！
• 决策树在构造过程中支持剪枝。
• C4.5还需要计算分裂信息度量，计算信息增益率，选择信息增益率最高的属性作为决策树结点进行分裂。
• 递归！！！

CART：

• 分类与回归树，根据变量是离散的还是回归的，CART都可以进行处理嗷！！！
• GINI指数
  • 用于表示信息不确定性的（集合不确定性）
  • 指数越大，样本不确定性也越大嗷！！！

汤老师：

Lession1：

• 每一层都是分布式架构（MR , HDFS …）
• HDFS底层就是主从架构模式，对应的软件和硬件是配套的，都是主从架构（HDFS , HBase , Zookeeper…）。
• Hadoop几层架构要搞清楚。
• HDFS为什么要分成64KB？Load Balance
• Fault Tolerance? Three duplicates , one on one sack ,another two on the same sack (different machines)

Lession2:

• Hadoop上面建立已成HBase分布式数据库，why？底层以及提供Fault Tolerance和Load Balance两层了orz

• 系统架构含义：

  • Hardware : Hadoop cluster
  • Software : HDFS system

• Hbase集群部署：四大组件

  • Master
  • Region Server（HBase的Worker程序）
  • Zookeeper（HBase的Master程序）
  • Client（HBase的Client程序）

• 数据的逻辑存储结构：

  • Stack , Queue , Tree , Hash…

• 数据的物理存储结构：

  • Volume -> Section -> Track（机械磁盘）
  • 持久化存储
  • 驱动器和文件系统都完成了实际上的物理存储的功能。

• 从逻辑到物理架构的转换 -> 有程序负责从物理存储结构到逻辑转换（类似于HBase），Restore -> Hbase + HDFS

• HDFS只负责数据相关的存储和容错等，HBase负责存储架构的转换，读取出来的数据的复原等等！！！

• HBase如何存储？

  • Region（HBase的分区）：
    • 数据库表单被拆分为不同的子表存储到不同的Machine上
    • 算法负责将子表分发到不同的服务器上存储
    • 一个结点部署一个Region Server，子表实际上被划分到的服务器就是Region Server（本质是一个程序）
    • 一个服务器上就运行着一个Region Server
    • 每一个HBase都是独立的，那负载均衡咋办？？？ —> Zookeeper就是负责统一协调部署的嗷！！！
  • Region到底是怎么存的呢？
    • Region内部是一个子表
    • 子表按照列（不一定是一列）又分区了，分成了Store
    • 把Store在内部水平分区分成了StoreFile
    • StoreFile和HDFS的大小刚好匹配上了嗷！！！StoreFile直接就给HDFS了，整活！
    • HDFS再生成Copy啊，分发到部分结点上嗷（完成灾备等功能）！！（本质上交给HDFS之后，HDFS只负责另外两个备份存到哪个Server上嗷！！！）

• HLog缓冲区：

  • HLog缓存的常用的Store
  • 对于每个Store，在内存中开辟缓冲区来缓存信息（MemStore），存储常用的StoreFile。
  • 观测程序在不断统计哪些Store和StoreFile被访问的最多，拿出来放到HLog，MemStore（缓冲区中）
  • HBase底层自动帮助我们进行缓冲和缓冲区的分配，采用LRU进行缓冲的替换嗷！！！

• Hbase存储的什么数据结构？？？

  • HBase数据模型：
    • 非常简单，非常灵活
    • 三元组，key-value pair（行键，列族：列限制符，时间戳）
    • 小的数据类型非常灵活，不受限制

• 对于一个数据的Instance，只有一个RegionServer，对于不同的Instance，每个Instance对应的一个RegionServer。

• 寻址：

  • 三层机构：
    • Zookeeper
    • Root
    • .META.
  • 客户端从Zookeeper获得Region存储位置后，直接在RegionServer写数据嗷！！！

• HBase索引与检索：

  • HBase查询方式：
    1. 单个RowKey
    2. RowKey区间访问查询
    3. 全表扫描
  • 二次检索表技术：
    • 建立列和行键的关系，方便我们通过列找到对应的行键
    • 再通过行键就能查找找到对应的列了嗷！！！
    • 表的维护，表的存储，表的分区等等（表在内存嗷！！！）。。。好多问题，但是！！！以空间换时间嗷！！！
    • 关键：避免全表搜索！最痛恨的就是全表搜索。。。

• 工程经验：

  1. 遇到大数据第一想数据拆分
  2. 第二想多线程
  3. 第三大数据平台嗷！！！

• 分布式协同管理组件Zookeeper：

  • 提供服务：
    • 主从架构
    • 一个主节点
    • 多个从节点
  • 每台机器上也有Zookeeper，Worker也会有Zookeeper的从节点嗷！！！

• 分布式消息队列： 同步队列和FIFO队列

• 分布式锁：独占锁和控制时序锁 -> Zookeeper调用接口使用过

• 作业调度与工作引擎流Oozie：

  • 工作流：定义作业任务的拓扑和执行逻辑
  • 协调层：

• Oozie工作原理

• 集群资源管理框架YARN：主从架构

Lession3：

• 计算模型：算法+特定的数据结构（逻辑解决方案）

• 计算架构：在分布式机器上用软件实现计算模型（物理解决方案）

• Flynn并行计算模型：

  • 两个维度：1.指令流（Instruction） 2.数据流（Data）
  • 可以按照指令流和数据流划分为：
    • SISD（Single Instruction Single Data）
    • SIMD（Single Instruction Multiple Data）
    • MISD（Multiple Instruction Single Data）
    • MIMD（Multiple Instruction Multiple Data）(最常用的架构模式，我们Hadoop的Cluster就在其中)

• MR会慢？？？为什么？？？三个原因？？？

  • 生成大量中间文件
  • 将文件存储到磁盘中
  • 中间文件的远程读取

• 存在内存？是否合理，是否所有的Map结果中间文件都要使用呢？

Lession4：

• 应用场景：大数据分析解决的有关于图（网络）的问题。
• 图分割模型难题：
  • 图的切割
• BSP模型：
  • 三个部分：
    • 组件：处理器
    • 路由器：实现组件通讯
    • 全局时钟：用于同步全部或部分的组件
  • 超步（Superstep）:
    • 将一个大任务分解为一定数量的超步
    • 压缩数据通信的时间！
    • 付出代价：Barrier要求要等其他的哇！！！跑得快的要等！！！
• 计算过程：
  • 本地计算
  • 全局通信
  • 栅栏同步
• BSP的实现：逻辑架构 -> 物理架构（开发工具包或API函数库）
• 谷歌做出来的框架就是Pregel开发包。
• BSP也是主从架构嗷！！！
  • BSPMaster
  • GroomServer
• 图分割，使用$Hash(Node)$ % N这种模式来进行图分割。
• 两种状态：
  • active
  • inactive
• 所有都inactive流程就结束了嗷！
• 最大值/最小值/平均值/中位数/众数。。。都可以用这个状态机搞定嗷！！！

• 开源图并行计算框架Hama：
  - 大规模数据处理计算：
  - 大规模矩阵运算
  - 机器学习（K-means Clustering , Decision Tree）
  - 图计算（BFS , PageRank , SSSP , MF-MC）
  - 网络算法（神经网络，社交网络分析，网络实时流量检测等）