大数据简介.docx

大数据通常定义为,超出了常用硬件环境和软件工具在可接受的时间内为其用户收集,管理和处理能量流的数据.大数据的“大”不仅体现在容量上,还体现在多样性,速度及复杂度等方面.大数据的威力体现在你所做的分析和所采取的行动上,而不是体现在"大"或者"数据这两个方面.大数据通常由某类机器自动地生成,而且其格式通常并非用户友好的.默认的做法是先采集到所有能采集的数据,然后再考虑哪些是其中最重要的.大数据会改变分析专家所使用的分析策略和工具,但它不会从根本上改变分析的动机，以及从分析中可获取的价值.不少大数据源是半结构化的.半结构化的数据源有一定的逻辑,但是可能并不漂亮.大数据最大的风险是某些数据源可能涉及隐私纠纷.大数据最令人激动的部份是，当它和其他数据结合以后所带来的业务价值.大数据和传统数据都是整体数据和分析策略的一部份.不要制定严格区分于传统数据策略的大数据策略.下面是我看大数据一互联网大规模数据挖掘与分布式处理一书第二章的总结。1 分布式文件系统：distributedfilesystem文件多副本存储，计算任务分多个，容错。文件非常大（TB）,文件极少更新2 Map-reduce：a多个map任务，每一个任务输入是DFS的一个或者多个文件块。b主控制器从每一个map任务中采集一系列键值对creduce任务每次作用于一个键经典任务：统计多个文本中单词的频率。节点失效时要有相应的容错组织map-reduce应用：矩阵向量乘法，关系代数运算（选择，投影，并交差，自然连接，分组聚合）map-reduce扩展：Pregel系统（递归失效解决方案）Hadoop：HDFS与map-reduce结合实现工作流系统：map-reduce普通化为支持任意无环函数集系统，每一个函数都可实例化为任意数目的任务，每一个任务在一部份数据上执行对应函数递归工作流：递归关系函数集，系统不保证节点失效，可在计算工作过程中设立检查点通信开消模型：map-reduce小任务开消简单，主要开消在于数据从创建到使用的开消。多路链接，星形连接。下面是我看大数据一互联网大规模数据挖掘与分布式处理一书第三章的总结。1 Jaccard相似度：交集大小/并集大小，可应用于文档相似度，购物习惯相似度计算2 Shingling：K-shingling文档中连续浮现的任意K个字符。3最小哈希：集合上的最小哈希函数是基于全局的罗列转换来定义。给定任意一个罗列转换，集合的最小哈希值为罗列转换次序下浮现的第一个集合元素。4最小哈希值相等的概率等于两个集合的JaCCard相似度。5最小哈希签名：选择多个罗列转换，在每一个罗列转换下计算集合的最小哈希值，这些最小哈希值序列构成集合的最小哈希签名。6高效最小哈希：选择随机哈希函数，利用该函数对集合中所有元素进行哈希操作，得到的最小值看成集合的最小哈希值7签名的局部敏感哈希：给定集合签名，划分成条，仅仅计算至少有一个行条相等的集合对之间相似度，合理选择行条大小，消除不满足相似度阈值的大部份集合对之间的比较。8测度距离：大于等于0；对称；满足三角不等式9欧式距离JaCCard距离：LJaccard相似度余弦距离，编辑距离，海明距离10局部敏感哈希理论：对给定集合，集合中的函数可用于相似性检测时决定某个项是否要作为候选对进行后续比较。对这些函数给出约束参数：1距离小于限制值这些函数判定为候选对下界，2距离大于限制值判定为候选对上界。H字符串比较的高相似度检测：利用局部敏感哈希理论，限制字符串长度。大数据：数据流挖掘下面是我看大数据一互联网大规模数据挖掘与分布式处理一书第四章的总结。1流数据模型：数据以某种速率达到处理引擎，该速率使得无法在当前内存存储数据。流处理一种策略是保留流的概要信息，使之足够回答数据的期望的查询。另一种是维持最近到达数据的滑动窗口。2流抽样：为创建某类查询创建的流样本。确定流中关键属性集合。对任一到达流的键值进行哈希处理，使用哈希值确定包含键值的全部元素会使抽样样本的一部份。3布隆过漉器：允许特定集合的流元素通过，大部份其他元素丢弃。使用一个大的位数组或者者多个哈希函数。集合元素哈希到桶，这些桶置为1。哈希检查流的某值是否属于某个集合。哈希值到的位置为1,则属于集合。4独立元素计数：估计流中浮现不同元素的次数。将元素哈希成整数，换成二进制数，最长O序列的长度作为2的塞指数得到结果为估计值。也可多哈希值组合，取中位数。5流的矩：流的K阶矩是流中至少浮现一次的元素浮现次数的K次方之和6窗口内1数据估计：0/1二进制流窗口1分到多个桶，估计出1的数目。7有关1的数目的查询应答：最近k个元素1的个数，寻觅一个最早的桶B,至少包含一部分查询范围，估计值为B的一半和后来的桶的和。8指数衰减窗口：窗口想象成所有达到的元素，t个时间单位之前的元素赋予权重e(-ct),保留指数衰减窗口的概要。9指数衰减窗口下高频元素的获取：每一个项看成二进制位流构成，0表示非当前时间到达，1表示当前时间到达，找出二进制流的和不低于1/2的元素，新元素到达时，将当前记录得分乘以(1-c)+1,并删除所有和小于1/2的项。页会指向不少权威页，权威页被不少导航页指向”。不需引入抽税机制。下面是我看大数据一互联网大规模数据挖掘与分布式处理一书第五章的总结。1词项做弊：在Web网页中估计引入那些与网页页面无关的用于误导搜索引擎的词项。2对付词项做弊：Pagerank。相信其他网页对当前网页的评价。3 Pagerank：是递归方程“重要网页指向的网页也重要”的解。4 Web的转移矩阵：一个或者多个链接从j指向i,那末第i行第j列元素值为1/k5强连通图pagerank计算：对强连通图，pagerank是转移矩阵的主特征向量。pagerank可从任意非零向量开始，反复用转移矩阵乘以当前向量，迭代约50次，估计出pagerank值。6随机冲浪模型：冲浪者从任意界面开始，每下一步随机访问当前页面所连接的页面。冲浪者在给定网页上停留的页面的极限概率就是网页的Pagorank值。7终止点：没有出链的Mb网页。8采集器陷阱：一系列节点，可能相互连接，但是不会连接集合外的点。9抽税机制：抑制采集器陷阱效果。成份分解加之分量。10转移矩阵高效表示：稀疏矩阵中提取非零元素表示。H极大规模矩阵向量乘法：web网络图结构，矩阵分块K*k方块，向量分k段。12面向主题的pagerank：查询用户对某个主题感兴趣，而对其主题相关的网页赋予更高pageranko13链接垃圾垃圾农场包括目标网页，支持网页，目标网页指向所有支持网页，支持网页只指向目标网页。14TrustRank:抑制链接做弊算法，面向主题的pagerank其中的远程跳转集合由一些可信的网页组成。15垃圾质量：trustrank值较pagerank值小不少的网页是垃圾农场的一部份。16导航页和权威页：HITS权威页是包含价值信息的网页，导航页是包含指向价值信息的网页。HITS递归算法“导航下面是我看大数据一互联网大规模数据挖掘与分布式处理一书第七章的总结。1聚类：促某空间下点形式的实用的概要表示。为了对点进行聚类，需要在该空间下定义一个距离测度。2聚类算法：层次聚类算法将每一个点自己都看成一个簇，然后相近的簇进行合并。点分配聚类算法挨次考虑每一个点并将他们分配到最符合的簇。3维数灾难：高维欧式空间和非欧空间。随机点之间往往具有相同的距离，随机向量往往近似相互正交。4质心和中心点：欧式空间所有元素求平均，该平均值为簇的质心。非欧空间选择代表元素或者典型元素代表簇中心点。5中心点选择：非欧空间簇的典型点选择，点到该簇其他点距离之和最小，上述距离的平方和最短等等。6半径和直径：半径质心到中心点最大距离，直径为簇内任意两点间的最大距离。7层次聚类：选择下一步合并；住手合并；8选择簇进行合并：选择质心或者中心点最近的簇合并；选择具有最相近点的两个簇合并；9合并住手条件：达到固定数目的簇；簇的半径直径达到某个阈值；10 K-均值算法：点分配算法欧式空间。11 K-均值算法的初始化:选择K个质心的方法是随机选择一点，然后选择此外KT个点，每个点选择尽可能远离前面选出的点；此外一种选择小的样本点集，使用层次聚类算法将他们合并成K个簇。12 K-均值K的选择：使用二分技术在不同的K值上运行K-均值聚类算法。搜索K的最大值以至于当下降k的值时，簇的平均直径会急剧增大。13 BFR算法：假设簇在坐标轴方向都满足正态分布，以k-均值算法为基础处理内存无法存放的大数据。点从磁盘以组块的方式读出，簇用点的数目，所有点的向量，所有点每一维分量上的平方和的向量表示。簇中远离质心的点表示成所谓的迷你簇，不挨近任意其他点的点用自己表示，为留存点。簇中大部份点分配给相近的簇，簇的参数由新加入的点调整，迷你簇可相互合并，最后一次内存装载，迷你簇和留存点可以合并到最近的簇中或者保存为离群点。14 CURE算法：点分配算法一种，欧式空间下，簇可能是任意形状，处理内存无法存放的大数据。算法开始对小规模点集样本进行聚类，然后为每一个簇选择代表点，选择时近可能让这些代表点之间相距较大。最终目标是从簇的边缘上选择代表点。每一个簇建立代表点后，整个点集可从磁盘读出并分配给一簇。15 GRGPF算法：点分配，可在非欧空间下，簇表示为簇中心点数目，簇中心点，离中心点最近的点集和离中心点最远的点集。对每一个点，记录点到簇中所有其他点的距离平方和和算术平方根Rowsum,簇会组成一棵类似B-树，节点是磁盘块，叶节点表示尽可能多的簇，父节点保留簇中心点样本。点集样本初始化后，将每一个点插入到离他最近的那个簇。16流聚类：DRIM在滑动窗口中对1计数的方法，演变成缓慢流点聚类。桶大小形成序列，每一个桶大小是前一个桶大小的2倍。桶的大小是其所代表点的数目。桶表示簇，而非点本身。桶合并时选择簇最相近的。聚类结果作为查询应答。17基于MaP-RCdUCC的聚类：将数据划分成组块，Map对每一个组块聚类，map输出的簇由reduce进一步聚类。1定向广告：Web广告按照某个用户的兴趣来选择，使得Web服务通过广告收益来支持运行。2在线及离线算法：得到所有数据才产生答案的传统算法称之为离线算法。在线算法必须对流中的每一个元素都即将作答，此时仅对过去的信息有所了解，对未来的数据一无所知。3贪心算法：在线算法采用贪心策略，算法每一步的选择基于某个目标函数的最小化来进行。4竞争率：在所有可能的输入情况下，通过最小化在线算法与最优离线算法的收益比来度量在线算法的质量。5二部图匹配：两个节点集合，寻觅两个集合节点相连构成边的集合，最大化边数，每一个节点的浮现都不会超过一次。6匹配问题的在线解决方案：在二部图中寻觅匹配的一个贪心算法对边按照某种方式排序，挨次对每条边处理。可以证明该算法的竞争率是1/2。7搜索广告管理：搜索引擎收到广告商对某些查询搜索的投标。对某个搜索杳询，某个广告会被显示，一旦有人点击广告，广告商要向搜索引擎付费。8Adwords问题：Adwords问题的数据包含广告商对某些搜索查询的一系列投标集合，每一个广告商的总预算，及每一个查询提交后每条广告的历史点击率。还有搜索引擎收到的搜索查询流。目标是对每条查询选择在线的固定大小的广告集予以显示，最大化搜索引擎利益。9简化adwords问题：每一个投标非0即1,每条查询仅对应一条广告，所有广告商预算相等。贪心算法促使搜索引擎将广告分配给对查询投标并有剩余预算的广告商。竞争率1为1/2.10Balance算法：相较贪心算法，Balance算法会将查询对应