又到了明天考试，今天突击的日子！！！！！
第1章数据挖掘基本概念
前言：邦弗朗尼原理实际上对数据挖掘的过度使用提出了警告。
1、数据挖掘的基本概念：数据挖掘是指从数据中提取有用模型的过程。提出的模型有时可以是数据的一个汇总结果，而有时可以是数据中极端的特征所组成的集合。
数据挖掘是数据“模型”的发现过程，统计学家认为数据挖掘是统计模型的构建过程，而统计模型指的是课间数据所遵从的总体分布。
2、数据挖掘和机器学习的区别：目标不同，算法相同。
机器学习是一门多学科交叉专业，涵盖概率论知识，统计学知识，近似理论知识和复杂算法知识，使用计算机作为工具并致力于真实实时的模拟人类学习方式，并将现有内容进行知识结构划分来有效提高学习效率。
机器学习三要素：模型，策略，算法
数据挖掘技术是机器学习算法和数据存取技术的结合，利用机器学习提供的统计分析、知识发现等手段分析海量数据，同时利用数据存取机制实现数据的高效读写。
相同的算法比如贝叶斯网络、支持向量机、决策树、隐马尔可夫模型、k-means算法等。
3、数据建模的两种方法：
4、邦弗朗尼原理基本概念：
在考察数据时，如果将某些对象视为数据的有趣特征，而这些对象中的许多实例都可能会在随机数据中出现，那么这些显著的特征就不可依赖。对于那些实际中并不充分罕见的特征来说，上述观察结果限制了从这些数据特征中进行挖掘的能力。
邦弗朗尼校正定理：该定理给出了一个统计上可行的方法来避免在搜索数据时出现的大部分“臆造”正响应。
数据挖掘所谓发现的模型可能是没有任何意义的，统计上称为邦弗朗尼原理。
在数据随机性假设的基础上，可以计算所寻找事件出现次数的期望值。如果该结果显著高于你所希望找到的真正实例的数目，那么可以预期，寻找到的几乎任何事物都是臆造的。
5、TF.IDF(TF指词项频率，IDF指逆文档频率)：度量给定词语在少数文档中反复出现程度的形式化指标。
假定有文档集中有N篇文档，fij为词项i在文档j中出现的频率，即次数。
于是词项i在文档j中的词项频率TFij定义为TFij=fij/maxkfkj
假定词项i在文档集的ni篇文档中出现，那么词项i的IDF定义如下：IDFi=log2N/ni
词项i在文档j中的得分被定义为TF.IDF=TFij*IDFi
具有最高TF.IDF得分的那些词项通常都是刻画文档主题的最佳词项。
如果某个词在少量文档当中频繁出现时，那么它在文档中的TF.IDF值较高。
6、哈希函数h的输入是一个哈希键值，输出是一个桶编号。假定桶的个数B，那么桶编号一般为0-B-1之间的整数。哈希键值可以是任何类型的数据。哈希函数的一个直观性质是它们将哈希键值“随机化”。
8、幂定律：两个变量在对数空间下呈现出线性关系。
马太效应：某个特性获得高价值，那么会导致该特性获得更大价值。（强者愈强）
比如：Web图当中节点的度、商品的销量、Web网站的大小、Zipf定律
9、本章小结：数据挖掘：从数据中提取出有用模型的过程。邦弗朗尼原理：显著特征不可依赖。TF.IDF指标：确定文档中哪些词语对文档主题有用。索引：给定字段值进行高效记录存取和检索。哈希是构建索引的一种方式。
第2章MapReduce
前言“计算集群”：大规模普通硬件的集合，计算节点通过以太网或价格低廉的交换机连接而成。软件栈下层是分布式文件系统，特征是存储单位大、提供数据冗余机制。
1、大数据的例子（并行化的处理方式）：
Web网页重要性排序：大规模迭代矩阵-向量乘法，大规模矩阵迭代相乘
在社交网站上的朋友关系网络中进行搜索
2、解决大数据计算问题：
3、MapReduce的计算过程（程序员只需编写Map函数和Redece函数）
（1）有多个Map任务，每个任务的输入是DFS中的一个或多个文件块。Map任务将文件块转化为一个键-值对序列。从输入数据产生键-值对的具体方式由用户编写的Map函数代码决定。
（2）主控制器从每个Map任务中收集一系列的键-值对，并将他们按照键大小排序。这些键又被分到所有的Reduce任务中，所以具有相同键的键-值对应该归到同一个Reduce任务中。
（3）Reduce任务每次作用于一个键，并将与此键关联的所有值以某种方式组合起来。具体的组合方式取决于用户所编写的Reduce函数代码。
4、节点失效后的处理：
（1）主控进程的计算节点崩溃，种植所有的MapReduce任务
（2）其他节点失效，通过主控进程来管理
（3）主控进程定期检查工作进程，发现节点的崩溃情况。重启相应的Map任务
（4）Reduce任务的计算节点失效，运行的Reduce任务的状态置为空闲，并安排给另外的工作节点按计划日程重新运行。
5、MapReduce能处理哪些计算？主要目的是什么？
大规模的矩阵--向量乘法；关系代数运算（选择，投影，并交及差，自然连接，分组和聚合）；字数统计；大规模的矩阵--矩阵乘法
MapReduce采用分而治之的策略，设计理念是“计算向数据靠拢”，将复杂的，运行于大规模集群上的并行计算过程高度的抽象到两个函数map和reduce上。编程容易，不需要掌握分布式并行编程细节，也可以很容易把自己的程序运行在分布式系统上，完成海量数据的计算。
6、本章小结分布式文件系统：文件块大小为64MB左右，每个文件块会有多个副本分别存放在不同的计算节点或机架上。
Map函数：输入对象的集合转换为0个或多个键值对，键值不一定要有唯一性。
分布式文件系统（DFS）使用（1）文件非常大。（2）文件极少更新。
第3章相似性发现
1、集合的Jaccard相似度：计算交集的相对大小来获得集合之间的相似度
集合S和T之间的Jaccrad相似度=|S∩T|/|S∪T|
2、文档相似性的应用：抄袭文档；镜像页面；同源新闻稿
3、协同过滤--集合相似度的应用：在线购物（基于用户和基于顾客），电影评级
4、文档的K-single：一篇文档就是一个字符串。文档的K-single定义为其中任意长度为k的字串。
将任意长度的空白穿替换为单个空格或许很合理。
5、两个集合经随机排列转换之后得到的两个最小哈希值相等的概率等于这两个集合Jaccard相似度
最小哈希：排列转换后的行排列次序下第一个列值为1的行的行号。
最小哈希签名：特征矩阵表示M。随机选择n个排列转换用于矩阵M的行处理。其中n一般为一百或几百。对于集合S对应的列，分别调用这些排列转换所决定的最小哈希函数h1，h2，h3，.......，hn，则可以构建S的最小哈希签名向量[h1(S),h2(S),.......,hn(S)],该向量通常写成列向量方式。因此，基于矩阵M可以构建一个签名矩阵，其中M的每一列替换成该列所对应的最小哈希签名向量即可。
6、局部敏感哈希算法的基本思路：
对目标项进行多次哈希处理，使得相似项会比不相似项更可能哈希到同一个桶中。将至少有一次哈希到同一桶中的文档对看作是候选对，只去检查这些候选对之间的相似度。我们希望大部分不相似的文档对不会哈希到相同的桶中，这样就永远不需要检查它们的相似度。
（1）把签名矩阵分成多个行条，对每个行条使用哈希函数
（2）具有相同部分的列将被哈希到同一个桶里。
（3）只考察那些哈希到同一个桶里面的列的相似性。
7、距离测度：是一个函数d（x，y），以空间中的两个点作为参数，输出是一个实数值
（1）d（x，y）大于等于0距离非负
（2）当且仅当x=y时，d（x，y）=0
（3）d（x，y）=d（y，x）对称性
（4）d（x，y）≤d（x，z）+d（z，y）三角不等式
8、LSH函数的应用：实体关联；指纹匹配；新闻报道匹配
实体关联：将代表同一真实世界实体的数据记录彼此关联。指纹匹配：将指纹表示为集合。新闻报道匹配
9、小结Jaccard相似度应用：文本相似度、购物习惯的相似度计算签名的LSH：给定集合的签名，我们可以将它们划分成行条，然后仅仅计算至少有一个行条相等的集合对之间的相似度。
第4章数据流挖掘
前言（1）数据流处理的每个算法都在某种程度上包含流的汇总过程。（2）汇总方法：a.抽取有用样本，滤除不想要的元素。b.只观察一个“定长”窗口。
1、数据流模型：该模型假定数据以某种速率到达处理引擎，该速率使得无法在当前可用内存中存放东西。流处理的一种策略是保留流的某个概要信息，使之足够回答关于数据的期望的查询。另一种方法是维持最后到达数据的一个滑动窗口。
流数据：数据以大量、快速、时变的流形式持续到达流可以在大容量归档存储器上进行处理，流汇总数据或者部分流数据可以存储在工作存储器上，该存储器可用于查询应答处理。
2、流数据例子：传感器数据；图像数据；互联网及Web流量
3、流查询的两种方式
4、流处理的若干问题的2个重点结论
流元素地分发速度通常很快，必须对元素进行实时处理。流处理算法通常在内存中执行，一般不会或极少访问二级存储器。
5、流中的抽样问题
6、布隆滤波器的组成和检测过程，性能分析（检测时可能遇到的问题，如假阳性问题）
布隆过滤器是一种概率空间高效的数据结构。用于检索一个元素是否在一个集合中。存在“在集合内（可能错误）”和“不在集合内（绝对不在集合内）”两种情况。
核心思想就是利用多个不同的Hash函数来解决冲突。
组成：
检测过程：位数组的所有位的初始值为0，对于S中每一个键值K，利用哈希函数进行处理。对于一些哈希函数及S中的键值K，将每个()对应的位置为1。当键值为K的流元素到达时，检查所有的()对应位是否为1，如果是，则允许该流元素通过，如果由一位或多位为0，则认为K不可能在S中，于是拒绝流元素通过。
性能分析：
（1）没有发生误判
（2）发生了误判---假阳性问题：把不属于这个集合的元素误认为属于这个集合。
7、独立元素统计的概念
假定流元素选自某个全集。我们想知道流当中从头或某个已知的过去时刻开始所出现的不同的元素数目。
8、矩估计概念和实际含义
概念：流的k阶矩是流中至少出现一次的元素的出现次数的k次方之和。用样本矩估计总体矩。
实际含义：假设i元素出现的次数位，则流的k阶矩是所有i上的（）k的和。
0阶矩：所有元素中不为0的数目。
1阶矩：的和
2阶矩：的平方和
9、本章小结
流数据模型：该模型假定数据以某种速率到达处理引擎，该速率使得无法在当前可用内存中存放所有数据。流抽样：为创建能为某类查询所用的流样本，我们确定流中的关键属性集合。
第5章链接分析
1、PageRank的两个创新
（1）使用了PageRank技术来模拟Web冲浪者的行为，这些冲浪者从随机页面出发，每次从当前页面随机选择出链前行，该过程可以迭代多次。最终，这些冲浪者会在页面上汇合。
（2）判断网页内容时，不仅只考虑网页上出现的词项，还考虑指向该网页的链接中或周围所使用的词项。
动机：Web用户会“用脚投票”；随机冲浪者的行为表明Web用户可能访问哪些网页。
2、PageRank，词项作弊的概念
PageRank：是一个函数，他对Web中的每个网页赋予一个实数值。
3、PageRank的计算公式
V=MV入V=MV（原谅我很懒，啊西巴）
4、避免终止点的办法
（1）将终止点及其入链从图中剔除，这样做可能会创建更多的终止点，继续迭代剔除终止点。
（2）可以修改随机冲浪者在Web上的冲浪过程。（抽税法）
5、抽税法计算公式，迭代计算
v’=βMv+（1-β）e/n
6、PageRank的计算和存储
两个问题：
转移矩阵的表示：如果分别用一个4字节整数来表示元素的行号和列号，使用一个8字节的双精度数字来表示元素的值，那么一个非零元素需要16个字节来表示。转移矩阵存储所需空间与非零元素的数目成线性关系，而不是与矩阵的行数或列数呈平方关系。
7、主题PageRank计算
概念：基于网页的主题来加大它们的权重。这种强加权重的机制改变了随机冲浪者的行为方式，它会使得随机冲浪者更倾向于停留在某个覆盖已知主题的网页。
v’=βMv+（1-β）es/|S|
8、垃圾农场结构
人工增加网页的PageRank的方法称为链接作弊，而得到的信息统称为垃圾。
为提高某个或者特定网页的PageRank的目的而构建的一个网页集合成为垃圾农场。
按照作弊者的观点，整个Web分为3个部分：不可达网页或不可达页；可达网页或可达页；自有网页或自有页
9、本章小结词项作弊：Web网页中故意引入的那些与内容无关的用于误导搜索引擎的词项。谷歌对付词项作弊：引入PageRank算法确定Web网页相对重要性、相信其他网页对当前网页的评价。PageRank值度量了网页的重要性。终止点：没有出链的Web网页。极大规模矩阵向量乘法：向量分成k段转移矩阵分成2个方块。垃圾农场：目标网页指向所有的支持网页，而支持网页只指向目标网页。
第6章频繁项集
前言
频繁项集发现常常被看成“关联规则”发现。
购物篮模型本质上是“项”和“购物篮”两类元素之间的多对多关系。
频繁项集和相似项的不同之处是：前者包含某个特定项集的购物篮绝对数目，后者是寻找购物篮之间具有较高重合度的项集，不管购物篮数目的绝对数量是否很低。
A-Priori算法基本思路：如果一个集合的子集不是频繁项集，那么该集合也不可能是频繁项集。
1、购物篮模型，频繁项集的基本定义
购物篮模型：用于描述两类对象之间一种常见形式的多对多关系。其中一类对象是项、另一类对象是购物篮（交易）。每个购物篮由多个项组成的集合构成。频繁项集：一个在多个购物篮中出现的项集称为“频繁”项集。如果I是一个项集，I的支持度是指包含I的购物篮数目。如果I的支持度不小于s，则称I是频繁项集。
2、频繁项集的应用
3、关联规则、可信度、兴趣度
关联规则：抽取结果往往采用if-then形式的规则集合来表示。
可信度：规则I→j的可信度等于集合I∪{}的支持度与I的支持度的比值。等于所有包含I的购物篮中同时包含j的购物篮的比例。
兴趣度：可行度及包含j的购物篮比率之间的差值。
4、频繁项集的两个假设
5、项集内存存储
6、A-Priori的前提，项集的单调性
如果项集I是频繁的，那么其所有子集都是频繁的。
7、A-Priori计算流程
（1）第一遍扫描：建立两张表。一张表转换项的名称为整数，另一张用于通过第一张表找到数组元素下标然后加1。（2）处理：给频繁项重新编号1到m，不频繁项置为0。（3）第二遍扫描：对两个频繁项组成的所有项对计数。扫描所需空间为22
8、本章小结购物篮数据：两种实体（项和购物篮），这两种存在多对多的关系。频繁项集：支持度是包含它们中所有项的购物篮数目。支持度不低于某个阈值的项集是频繁项集。
第7章聚类
前言：聚类是对点集进行考察并按照某种距离测度将它们聚成多个“簇”的过程。聚类的目标是使得同一簇内的点之间的距离较短，而不同簇中点之间的距离较大。
1、两种聚类策略
层次（凝聚式）算法：开始将所有点看成一个簇，簇与簇之间按照接近度来组合。点分配过程：按照某个顺序考虑每个点，并将它分配到最合适的簇中。
2、维数灾难
在高维空间下，几乎所有点对之间的距离都差不多相等。几乎所有向量都是正交的。
3、K-means聚类过程
（1）初始选择k个可能在不同簇的点。（2）让这些点作为簇的中心。（3）对于剩余的每个点找到最近的簇中心，将这个点加入簇中心，调整簇中心。
4、簇初始化（1）选择彼此距离尽可能远的点。（2）对某个样本数据先进行聚类，输出k个簇
5、本章小结
维数灾难：随机点之间几乎往往有相同的距离，随机向量往往近似相互正交。半径：质心到簇中任意点最大距离。直径：簇中两点最大距离。
2、在线算法和离线算法的定义
离线算法：将算法所需要的所有数据准备好，然后算法以任意次序访问数据，最后算法输出结果。
在线算法：流处理的极端形式是，我们必须在每个流元素到达之后就以输出方式对查询进行应答，于是我们必须在对未来一无所知时对当前每个元素进行决策。
3、贪心算法的性能
最大化当前输入元素和历史信息的某个函数，对每个输入元素都做出决策。
通过竞争率衡量性能。
性能不如离线算法。
4、本章小结
离线算法：得到所有数据之后才产生答案。
在线算法：必须对流中的每一个元素都立即做出应答，只对过去信息有所了解，对未来流元素一无所知。
贪心算法：每一步的选择基于某个目标函数的最小化进行。
竞争率：最小化在线算法与最优离线算法的收益比来衡量在线算法的质量。
第9章推荐系统
推荐系统样例：
1、推荐系统分类
2、效用矩阵，长尾现象效用矩阵：矩阵中每个用户-项对所对应的元素值代表的是当前用户对当前项的喜好程度。长尾现象：物理世界与在线世界的差别。
3、推荐系统应用
4、基于内容的推荐，推荐系统有两类基本的架构
协同过滤：先识别相似用户然后基于相似用户进行推荐的过程。
6、本章小结推荐系统处理的对象是用户和项。效用矩阵提供了已知的某个用户对某个项的喜好程度信息。基于内容的推荐系统：寻找项之间的共同特征来计算相似度。协同过滤方法：通过用户对项的偏好来计算用户的相似度，通过喜欢项的用户来计算项之间的相似度。