https://www.youtube.com/playlist?list=PLLssT5z_DsK9JDLcT8T62VtzwyW9LNepV
Coda是一个开放源代码的分布式文件系统,它采用了新的设计思路:
为了解决NFS一致性问题,Coda采用了支持离线工作的设计。它允许客户端在网络断开时继续访问文件,工作完成后再同步到服务器。
Coda将元数据与数据分离存储。元数据存储在服务器上保证一致性,数据可以本地缓存或者直接存储在客户端,大大提高访问效率。
Coda使用版本控制管理文件内容变更,客户端工作离线后生成本地版本,后和服务器同步时自动合并版本。
客户端可以选择性地将部分或者全部工作移除本地缓存,实现 Anu-Hoard算法来管理客户端缓存空间。
Coda采用服务器集群与数据冗余设计,单点失败后可以切换服务器保持运行。
Coda支持强一致性和ugins-style的最终一致性访问模式,给用户选择。
总之,Coda最大的亮点在于支持脱机工作,尤其适合 laptop 主机,提高了移动用户的工作效率。
Google文件系统(GFS)是Google公司内部使用的大规模分布式文件系统。
GFS的主要设计思路和技术点:
采用主-从设计,将文件切片后分布在集群各机器,一个块服务器是一个主,多个从复制该块。
所有文件的元数据存储在单独的Master节点,对文件进行统一管理与调度。
数据以块为单位存储,默认每个块为64MB,可以动态调整。
块的读取写操作都是从主服务器执行,从服务器以lazily方式更新状态。
块的复制数量可以配置,默认是3个复本。提高数据可靠性。
最长序列读写策略,减少头部文件的随机读问题。
块级锁机制,读写锁定粒度小,提高效率。
GFS面向海量数据和高吞吐量,以容量和 throughput 为主,对一致性要求不高。
MapReduce是Google提出的一种编程模式,用于进行分布式计算。其基本思想是:
输入数据被切分成一个一个的键值对。
这些数据被分配到各个计算节点上进行处理。每个节点独立地运行Map和Reduce任务。
Map任务将输入数据转换为一个中间结果列表。
Reduce任务将Map输出进行汇总计算,产生最终结果。
MapReduce的特征:
易于编程,只需实现Map和Reduce函数即可。
具有很强的可扩展性,随数据量的增加可以任意增加计算节点。
隐藏了并行计算的细节,使开发者可以独立思考业务逻辑。
具备容错机制,任务失败时可以自动重新运行。
MapReduce广泛应用于搜索、数据挖掘、信息检索等过滤和聚合计算中的问题。
MapReduce工作流程如下:
Master节点负责任务的分配、调度和失败处理。
输入数据被切分为Split,并进行复制。在Map阶段每个Split只运行在一台机器上。
Map任务将每个split内的键值对转换为多对<Key,Value>输出。
通过Shuffle流程,将相同Key的数据发送到同一个Reduce任务。
Reduce任务对Shuffle输出进行汇总,产生最终结果输出。
Master节点负责跟踪任务状态,失败任务进行重跑。
整个过程对开发者透明,隐藏了计算和通信的细节实现。
MapReduce通过核心组件Master和Worker节点来实现分布式运算。
Master节点负责任务的调度、监控和失败处理。它跟踪每个任务的状态,并将任务分配给Worker节点执行。
输入数据被切分成多个Split,存储在分布式文件系统中。MapReduce会安排Map任务运行在离数据Split最近的Worker节点上,以减少数据传输量。
每个Map任务负责处理一个Split。它通过Map函数将输入记录转换为多个小块<Key,Value>对。
这些<Key,Value>对通过网络传输并根据Key分组,分发给各个Reduce任务。Reduce任务通过Reduce函数进行汇总计算,生成最终结果输出。
Master节点负责接收客户请求,并根据情况创建Map和Reduce任务。它将任务状态标记为“就绪”或“进行中”等。
当Worker节点有可用资源时,Master会从就绪任务中选择一个分配给它执行。完成后Worker返回结果,Master再调度下一个任务。
如果Worker出现故障,Master会将它上运行的未完成任务再分配给其他Worker。Reduce任务的已完成输出不受影响,因为数据已经写入分布式文件系统。
如果Master失败,整个MapReduce任务将被终止。客户端需要重头重新提交任务。但Master节点单一,故障概率较低。
MapReduce程序的输入和最终输出保存在分布式文件系统中。为减少数据传输,Map任务尽量运行在离输入数据较近的机器上。
Map任务产生的中间结果存储在Worker本地,不写入分布式文件系统,以避免复制 overhead。这些数据通过网络传输给Reduce任务。
Reduce任务执行完后,结果写入分布式文件系统。本阶段的数据写入更频繁,Map阶段读操作多,Reduce阶段写操作多。
通常设置Map任务数量M要大于集群规模,可以让一个失败的Map任务迅速重新调度。
Reduce任务数量R较小,但大于机器数量,以均匀地将输出结果分散到多个机器上存储。
正确设置M和R对MapReduce任务效率和性能有很大影响。
Combiner是可以减少网络传输的数据量的优化方式。
Map任务产生大量具有相同Key的中间结果。Combiner可以在Map端进行简单的聚合,比如计算频数 Sum等,从而减少相同Key数据传输量。
Combiner的输入是Key和多个Value,输出是单个Value。Combiner函数通常与Reduce函数一致,如把多个次数Sum为一个值。
但Combiner只适用于满足交换律和结合律的操作,如Sum。不满足这两律的如Avg计算时,需要传输Sum和Count再在Reduce端计算Avg。
MapReduce默认通过Key的Hash值决定Reduce任务,可能导致不均匀划分。
可以自定义分区函数,比如根据URL主机名Hash值将相同站点URL分给同一Reduce,实现分布式聚合。
Hadoop是一个开源的MapReduce框架实现。它使用HDFS作为分布式文件系统,使用Java开发。
Hive和Pig是支持SQL和Pig Latin语言的框架,它们内部使用MapReduce实现各种查询和转换功能。
公有云如AWS的EC2允许按需伸缩计算和存储资源,实现弹性伸缩计算能力。AWS也提供Elastic MapReduce服务,让用户在EC2上运行Hadoop集群。
链接分析是一类用来计算图中的节点重要性得分的算法。它通过分析网络结构来学习节点的特征。
其中的PageRank算法是Google搜索引擎中的关键技术。它假设重要页面更容易被其他重要页面链接,从而可以通过链接关系来评估页面重要性。
PageRank算法基于以下假设:
如果一个页面被更多其他重要页面链接,它本身也更重要。
用户在浏览网页时,会不定期点击随机链接。这就形成了链接的随机性。
PageRank通过 web 图模拟这个随机浏览过程来计算页面得分。它定义每个页面的 PageRank 值 PR(A) 作为被其他页面均匀地访问的概率。
PageRank值的计算采用迭代求解。每次迭代都会将当前 PageRank 值按照下方公式重新分配:
PR(A) = (1-d) + d * (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))
其中,T1 ~ Tn 是链接到 A 的页面,C(Ti) 是 Ti 的出链数量,d 是跳转概率。
通过反复迭代,PageRank值会趋于稳定,找到一个公平合理的分布。
链接分析算法不仅可以用来评估网页重要性,还可应用于其他网络中的节点排名问题,例如:
学术文章和会议重要性评估
微信公众号和微博账号影响力评定
用户兴趣聚类和个性化推荐等。
此外,还可将链接分析技术扩展到检测网络中的垃圾节点,例如实现网页垃圾内容筛选。
PageRank算法是计算网页重要性的一种方法。它假设重要页面更容易被其他重要页面链接。
PageRank将链接视为投票,认为节点重要性与指向它的节点重要性成正比。但不是所有链接都一样,来自重要页面的链接影响更大。
PageRank使用流量模型计算节点重要性。假设每个节点有一定流量,流量会通过连接传输给相邻节点。
具体来说,如果节点j流量为Rj,出度为dj,则每条出链上的流量为Rj/dj。节点i流量Ri等于指向它的所有节点流量之和。
以一个三节点网页图作为例子,给出节点RANK可以表示重要性得分的计算公式。
得出每个节点的RANK分数方程,但方程组没有唯一解。增加一个约束:所有节点RANK和为1,此时就有唯一解了。
对大规模网络,无法直接解线性方程组获得RANK分数。需要一种迭代算法进行近似计算。
PageRank使用流量模型描述链接关系,给出节点RANK概念表示重要性。但对大型网络直接解方程组不可行,需要使用迭代算法计算近似RANK值。
PageRank算法是一种用于计算网页重要性的算法。它基于网页之间的链接关系,假设被更多重要网页链接的网页自己也更重要。
功能迭代法是求解PageRank值的一种方法。它通过重复计算R=M×R这个矩阵等式来迭代求解PageRank向量R。
具体操作是:
初始化R向量,令各成分均为1/n。
计算R×M,得到新的R向量。
重复执行上一步,直到R向量在两次迭代之间的变化很小,即收敛到一个稳定值为止。
PageRank值也可以通过随机游走模型进行解释。
假设有一个随机上网用户在网页网络中随机游走。它从当前页面中随机选择一个链接跳转到下一个页面。
那么PageRank值就对应于这个随机用户在稳态时停留在每个网页上的概率分布。
如果网络结构满足一定条件,例如每个节点出链总数有下限,则PageRank值的收敛具有如下属性:
稳态分布唯一汇聚,不依赖初始化R向量。
通过功能迭代法一定能收敛到这个唯一的PageRank向量。
这就保证了PageRank值的计算结果是确定和唯一的。
PageRank算法在计算网页重要性时会出现两个问题:
陷阱网页问题。有些网页形成闭环,随机点击者进入后会永远停留,计算结果不正确。
死胡同网页问题。有些网页没有出链, pageRank得分无法传播给其他网页,所有网页得分都将趋近于0。
Google通过增加随机点击的概率来解决这个问题:
随机点击者在每个网页有概率β选择跟随链接跳转;
也有概率1-β随机跳转到任意其他网页。
这使得随机点击者能够在几次步伐内跳出闭环状的陷阱网页。
对于出链为0的死胡同网页,Google认为在访问它时,随机点击者将以概率1随机跳转到其他任意网页。
这改变了标量M的结构,死胡同网页对应的列将全部元素取值为1/N。使得它传播的PageRank得分能够保留在系统中。
如果网络图结构满足:
每个节点出链数量都至少有一个下限。
元素值都大于0。
那么PageRank值的计算一定能通过 power 迭代法收敛到唯一的稳定分布。
在解决了陷阱和死胡同网页问题后,PageRank算法的计算结果就会更合理和符合我们的实际预期。
它可以很好地反映网页的真实重要性,成为搜索引擎排名的关键指标之一。
PageRank算法在计算网页重要性时,会出现两个问题:
陷阱网页问题。有些网页形成闭环,随机点击者进入后会永远停留,计算结果不准确。
死胡同网页问题。有些网页没有出链,PageRank分数无法传播给其他网页,所有网页的分数都将趋近于0。
Google通过增加随机点击的概率来解决这个问题:
随机点击者在每个网页有概率β选择跟随链接跳转;
也有概率1-β随机跳转到任意其他网页。
这使得随机点击者能够在几次步伐内跳出闭环状的陷阱网页。
对于出链为0的死胡同网页,Google认为在访问它时,随机点击者将以概率1随机跳转到其他任意网页。
这改变了标量M的结构,死胡同网页对应的列将全部元素取值为1/N。使得它传播的PageRank分数能够保留在系统中。
如果网络图结构满足:
每个节点出链数量都至少有一个下限。
元素值都大于0。
那么PageRank值的计算一定能通过 power 迭代法收敛到唯一的稳定分布。
Google提出了随机点击的新算法:
在每个步伐中,随机点击者有β的概率选择跟随链接,1-β的概率随机跳转。
对于出链为0的节点,随机点击者跳转概率定义为1。
这使得过渡矩阵满足随机性、可达性和周期性条件,PageRank算法可收敛。
以一个简单网络为例,计算不同节点的PageRank分数。
结果显示,引入随机跳转后,原先分数为0的节点 agora都有了非零分数,算法得以正常运行。这Valid本解决问题的方法。
PageRank算法的递推公式为:
Rj = βΣ(Ri * Pij/Di) + (1-β)/N
其中:
Rj表示节点j的PageRank值
Ri表示指向节点j的节点i的PageRank值
Pij表示从节点i跳转到节点j的概率
Di表示节点i的出度
β表示随机点击者选择按链接跳转的概率
1-β表示随机点击者选择随机跳转的概率
N是网络中的节点总数
可以把上述公式表示为矩阵形式:
R = A * R
其中A定义为Google矩阵:
A = βM + (1-β)E/N
M是原网络的转移矩阵
E是全1矩阵
可以把Google矩阵A分解为:
A = βM + (1-β)U
其中U表示随机跳转部分。
这样问题就转化为求A的特征向量,与原始PageRank问题等价。
因此,PageRank算法仍然可以通过Power Iteration方法收敛到唯一正定的特征向量,实现 PageRank scores的计算。
以一个简单网络为例,计算不同迭代下PageRank向量R的取值变化过程。
最后结果显示,算法收敛到一个稳定的PageRank分数分布,证明该方法能正确实现PageRank algorithem的计算。
在大量数据集合(数以百万或十亿计)中找出相似的集合。相似性的概念是双重匹配率,就是两个集合中元素数量的比例。
如果数据集合有百万个,那么集合对数就是5亿万,没办法一个一个比对。所以需要“魔法”来直接关注可能很相似的集合对,跳过大多数不相似对。
将文档切分成固定长度的词窗口(shingle),得到文档对应的集合。
对集合使用散列(minhashing)算法,计算一个短向量作为该集合的签名。
两个集合签名中相同元素越多,说明原始集合越相似。
签名空间小,可以提高内存效率。
查找镜像网页
检测剽窃文档
聚合新闻网站的重复新闻
推荐机制:用户喜好相似推荐商品
实体链接:将不同网站上个人资料链接起来
对文档切分shingle构成集合
对集合计算minhash签名
使用LSH算法,找到签名相似性高的文档对
可能存在误报和漏报,但可以通过调整参数控制错误率
最小哈希算法是一种用于近似判断两个集合元素是否相同的算法。
它针对集合计算一个
对于大量数据点,找到距离最近的k个点需要 reiteratively 次计算,开销很大。
本地性敏感哈希(LSH)提供近似方法,提高效率。
设计一系列概率哈希函数family,能保留数据点距离信息。
对每个数据点使用这些函数映射,不同点可能映射到同一个桶。
桶内数据点可能近似,跨桶数据点一定较远。
以桶为单位筛选,提速 kNN 查找。
以欧式空间作为例子:
构建随机直线将空间切分成片区。
数据点位置决定它被映射到哪个片区。
同一片区数据点可能近,不同片区一定离散。
Jaccard相似度:选择随机特征集划分
汉明距离:选择随机位掩码掩码数据点
Near-duplicate document detection
Content-based recommendation
Nearest-neighbor search in vector spaces
Similarity search in databases
Natural language processing tasks
Information retrieval, computer vision等
对象匹配问题需判断记录是否对应同一实体,难点在于记录属性可能以不同形式表示。
A、B公司各有100万用户记录,但未标记是否同一用户。
设计匹配度函数,同名地址号得分高,不同得0分。
LSH仅比对同桶记录,提速。记录以名、址、号各独立哈希。
得分筛选180,000对可能匹配对,手工检查仅意外遗漏2500对。
根据创建日期差分,推断匹配概率。
如果无法使用LSH字段,可以用其它属性验证匹配,如身高差异来判断。
LSH将近似匹配文档置入相同桶,降低比对成本。各种距离都有LSH方法,如名相似度、汉明距离等。
近似ня邻查询、文档重复检测、推荐系统、信息检索、自然语言处理等。
给定一大量指纹库,找到哪些指纹来自同一人。通常不考虑所有对匹配,而是匹配新指纹与库中指纹。
从指纹图像提取特征点位置(结合点、分叉点等),用坐标集表示指纹。在指纹上覆盖网格,将特征点包含在网格中。每个指纹用包含特征点的网格集合表示。
将指纹表示转换为特征点在各网格中的良率信息。采用多个网格组成的LSH桶将指纹分布。同一指纹特征点集重合程度高,有更高概率分布同一桶。
假设网格有20%概率含特征点。同一指纹特征点集重合程度超过80%。设置1000组由3个网格构成的LSH桶。
同一指纹分布同一桶概率约0.4%,不同指纹为0.00000064。采用LSH可找到98.5%的匹配对,錯失率1.5%。错误匹配率6.3%。可通过增大LSH组数量降低错误匹配率。
LSH方法有效地将指纹匹配问题转化为集合相似性判断,提高计算效率。参数设置直接影响算法性能。
许多新闻来源可能报道同一新闻,但由于来源不同,文章在不同网站上的表现形式可能不同。需要将含有相同或类似新闻内容的网页进行分组。
定义“词组”为以停用词开头后续两个词。此方式使页面上的词组主要来源于新闻文章而非广告等信息。
将页面分解为词组集合进行表示。相似页面词组集合重合程度高,其新闻内容相同。
普通切词会忽略停用词,但新闻切词利用停用词区分新闻与广告内容,使词组主要来源于新闻文本。
使用Jaccard相似度计算页面词组集合的相似性。相似度高则新闻内容高度相似。
以停用词区分新闻与广告内容
词组更注重新闻文本而非页面其他元素
有效识别同一新闻在不同来源页面上的表现形式
用于衡量数据点间的相似程度,是重要数据挖掘技术如聚类、最近邻查询的基础。
用于实值向量空间,计算两个点之间的标准平方差和。
用于概率分布,计算两个分布之间的距离。
用于固定长度的二进制向量,计算差异位的数量。
用于词袋模型下文本文档,计算两个文档共同词语与独有词语的比例。
用于衡量标准化后变量的线性相关性。
聚类算法用来衡量样本点到簇中心的距离。
根据数据类型和问题需求选择合适的距离测量,如文本用雅阑度量,图像用欧式距离。正确选择有助于得到更好结果。
监督学习的目标是学习一个函数f,该函数可以根据输入特征X预测输出类别或数值Y。
如果Y是一个类别变量,则称为分类问题;如果Y是一个实数,则称为回归问题。
实例学习直接使用训练数据来预测未知数据。一种实例学习方法是k临近点学习。
给每一个新数据点Q找其训练点中最近的一个点,并使用该点的标签作为Q的预测标签。
给新数据点找k个最近的训练点,然后用这k个点的标签平均值作为预测标签,可以得到更平滑的预测函数。
常用欧几里得距离来衡量点与点之间的距离。另外还需要考虑算法的效率,可以使用局部感知哈希来实现常数时间内查找临近点。
协同过滤推荐算法就是一个k临近点分类器的应用,它根据用户行为找到与目标用户最相近的其他用户,再根据这些用户的历史行为给目标用户做个性化推荐。
超市数据里记录某用户一次购物记录了购买的所有物品。问题是找出一组物品集合,这组物品集合在用户购物篮里同时出现的频率大于某个阈值。
如果某组物品在用户购物篮里同时出现的频率超过给定支持度阈值,则这个物品集合被称为频繁项集。
Apriori算法采用层次搜索的方法来挖掘频繁项集。它的搜索策略遵循:如果一个k-项集不是频繁的,则其所有超集都不可能是频繁的。
通过消除不必要的候选项集生成和支持度计数,实现更高效率的频繁项集挖掘。
Apriori算法在候选列和支持计数方面效率低下。
将数据分块存储在磁盘,一次只加载一块数据到内存进行频繁项集挖掘,降低I/O开销。
利用频繁项集的大小排序顺序避免加载不必要的候选集,例如使用FP-growth树结构进行挖掘。
使用基数编码对属性值进行定长编码,降低数据库大小,加快扫描速度。
为频繁项集建立索引,快速定位数据内容,避免全表扫描。
将任务分布到多个节点并行处理,每个节点分别挖掘一部分数据,最后集中计算结果。
利用集合操作原理,避免重复计数支持度,比如用交集和并集计算支持度。
Apriori算法经过上述多种优化后,在大规模场景下使用效率得以明显提升。
给出一个蛋白质互作网络,网络中节点为蛋白质,边表示蛋白质间互作。我们要检测功能模块,即一组一起工作的蛋白质集合。
给出一个Facebook好友网络,我们要分析结构并检测社交社区。
找出网络中可能重叠的社区,其中部分节点可能属于多个社区。
社区看作是网络中的样式,样式越多重叠,该区域内边越密集。
两个重叠社区内节点间更可能连接。可以用邻接矩阵表示网络,矩阵中样式重叠区域对应值更大。
根据样式理念,从网络中依次提取样式。探究网络结构,找到可能重叠的社区集合。
实际检测出4个社交社区,且重叠程度高,与初始假设不同。验证社区概念更符合实际。
以样式理念重新定义社区,可以更好描述可能重叠的真实社区结构,实现更准确的社区检测。
给定一个实际的社交网络,如Facebook网络,我们要找到网络中的潜在社区结构。
隶属图模型可以生成带有社区结构的网络。模型由四个要素定义:节点集合、社区集合、节点与社区之间的隶属关系、每个社区对应的链接参数。
每个节点可能属于一个或多个社区。两个节点之间以每个共同社区的链接参数作为概率生成边。如果它们有多个共同社区,连接概率就更高。
如果社区之间不重叠,可以用一个社区节点表示每个社区,节点只属于一个社区。
如果社区重叠,重叠部分的节点同时隶属这些社区。
可以用母社区包含子社区的方式表示层次结构。
给定实际网络,我们可以估计模型参数,找到最有可能生成该网络的隐秘社区结构。这就实现了社区检测。
该模型可以表达各种社区结构,同时具备生成网络和检测社区的双向功能。它是社区检测的一个通用框架。
BIGCLAM模型是为了简化原来的隶属图模型,可以更简单有效地检测大规模网络中的社区结构。
BIGCLAM模型用成员强度矩阵F描述每个节点隶属各个社区的程度,而不是零一变量。F矩阵是网络节点数×社区数的矩阵。
两个节点之间由单个社区产生链接的概率为:1-exp(- strength积)。由多个共同社区产生链接的概率为:1-∏(1-单个社区概率)
Strength矩阵F完全描述了网络结构,每行向量描述一个节点隶属各社区的强度。
P(U-V链接)=1-exp(-F行U与F行V点积)
这个公式将隶属网络抽象成强度向量,简化了模型解释和计算。
模型能表达节点不同程度隶属社区,节点多社区混合隶属,可以准确描述社区重叠结构。并且模型本身同时包含生成网络和检测社区的功能。
给出一个Strength矩阵实例,计算不同节点对之间的链接概率,验证了模型是如何根据共同社区强度来生成网络结构的。
图拉普拉斯矩阵定义为度矩阵D减去邻接矩阵A。D矩阵的对角线元素为节点度,其他元素为0;A矩阵表示节点之间的连接关系。
D矩阵中的对角线元素d_{ii}表示节点i的度,即与它相连的边数。其他位置元素都为0。
A矩阵的aij元素表示节点i和j是否连接,连接则为1,否则为0。对于无向图,A矩阵是对称矩阵。
L = D - A,它充分描述了图结构的局部信息。
计算L矩阵的奇异值分解,可以得到矩阵的奇异值向量,它表示图结构的簇分布信息。
小于1的奇异值对应的特征向量,其元素绝对值接近的节点更易属于同一簇。最大奇异值为0,对应的特征向量为常数向量。
图拉普拉斯矩阵通过定义将图结构问题转换为线性代数问题,从而可以通过矩阵分解获得图结构特征,有助于社区检测等任务。
规则图中每个节点度数相同,可以求解该图的特征值和特征向量。
如果图分成两个不相交组件A和B,可以把A组件节点赋值为1,B组件节点赋值为0,构成特征向量。此时特征值还是1。
如果两组件之间添加一些交叉边,图结构差异不大,特征值和特征向量也基本不变。
特征值代表了各个特征向量在图拉普拉斯矩阵中的“重要程度”,较大特征值对应的特征向量更能代表图的结构特征。
特征向量不同元素值代表了对应节点在该特征向量下的“重要程度”。元素值相近的节点更易归类到一个簇中。
规律图中,所有一维特征向量的特征值都等于图的阶,这些特征向量描述了图的主要结构。
图的特征值分解可以揭示图结构的基本特征,有助于社区检测和嵌入学习等应用。添加少量边对分解结果影响不大。
邻接矩阵A是一个二元矩阵,其元素表示节点之间是否直接相连,相连为1,否则为0。
度矩阵D是对角矩阵,其对角元素表示对应的节点度,即与其相连的边数。
绿色矩阵G也是一个对角矩阵,其对角元素表示对应的节点度。
图拉普拉斯矩阵L定义为度矩阵D减去邻接矩阵A,等价于绿色矩阵G减去邻接矩阵A。
图拉普拉斯矩阵的特征值都是非负实数,特征向量互正交。矩阵元素和为0。
图拉普拉斯矩阵充分描述了图结构,其特征值分解可以揭示图结构特征,有助于社区检测等应用。
通过定义各种基础矩阵,系统说明了图拉普拉斯矩阵的定义及其相关属性,为后续分析图结构特征奠定基础。 本文没有有效内容,无法生成知识笔记。
对图进行矩阵化表示,构造图拉普拉斯矩阵L。
计算L矩阵的特征值分解,找出第二最小特征值λ2和对应的特征向量x2。
按x2特征向量中的正负值将节点分为两个集合,实现二分类聚类。
给出一个例子,演示了三步操作实现二分类聚类。
更高阶特征向量可能暗示更多簇结构,例如x3对应4个簇。
递归二分法,反复二分实例空间直到K个簇为止。
统整法,采用多个特征向量描述每个节点,然后用K-Means分类。
概述了基于图谱理论的图谱聚类三步流程,并给出处理多簇情况的方法,为实际应用提供指导。
Trawling方法用于在大规模网络中检测小社区结构。它利用市场篮分析中的频繁项目集枚举算法。
将网络表示为图结构,节点为网络实体,边为连接关系。目标是检测完全连通的双层子图结构。
将每个节点的邻居看作一个“篮子”,包含该节点指向的其他节点ID。这样将图问题转换为频繁项目集问题。
完全连通的双层子图Ks,T对应频繁项目集的支持度为s,项目数为T。找到支持度≥s的大小为T的项目集,即检测出该子图。
通过例子说明算法的原理和结果,如何从频繁项目集推断出隐含的子图结构。
Trawling方法利用频繁项目集算法,以较高效率检测网络中不同类型的重叠社区结构。
与数据库管理系统类似,数据流管理系统处理连续不断的流数据,支持即时查询和持续查询。
数据流元素高速不断到来,无法存储所有历史数据。只能使用有限存储空间处理流中的一部分窗口数据。
通过最近n个元素或最近时间内元素,定义流中当前需要处理的窗口数据范围。窗口会随新数据到来滑动更新。
一次性查询,对当前时刻窗口数据求解;持续查询,对窗口内数据变化进行持续输出。
搜索查询流、点击流、网络包流等。这些流数据规模大,但对窗口内小范围历史数据进行分析就能得到有价值信息。
检测搜索热点变化、分析流量变化规律、识别网络异常等。任务往往需要对高速流数据做近似处理。
以整数流和计算窗口平均值为例,说明如何利用差分更新思想高效处理持续查询任务。
给定一个高速不断流入的二进制位流,求解一个持续查询任务:计算窗口内1的个数。
直接计数窗口内每个元素,时间复杂度O(n)不可行。
利用bing的性质:新元素进来时,窗口内1的个数等于原来的1个数加上新元素减去去掉的元素。
使用两个计数器分别累加窗口内0和1。新元素进来时,更新两个计数器即可获得窗口内1的个数。
只使用两个计数器,空间复杂度为O(1)。
每次元素到来只需常数时间更新计数器,时间复杂度为O(1)。
通过利用差分方法和bing特点,设计了一个时间和空间效率都很高的算法,可用于高速位流中的持续统计任务。
数据流中的数据元素高速不断到来,无法存储所有历史数据,只能使用有限存储空间处理流中的一部分窗口数据。
通过最近n个元素或最近时间内元素,定义流中当前需要处理的窗口数据范围。窗口会随新数据到来滑动更新。
如果按随机采样元素,无法正确处理重复元素和计算唯一元素比例等查询。
采用哈希函数,以查询词或元素作为关键字,结果保证重复元素对应相同的哈希值,实现一致性采样。
可以采样固定百分比的流元素,也可以采样固定数量的元素。通过调整哈希桶数量实现。
采样大小超限时,可以删除对应哈希值桶中的所有元素,从而减小采样。
包含主键-值对,关键字可以是主键或其它字段,保证相同关键字对应相同处理。
以员工薪资数据为例,以部门作为关键字哈希,实现对不同部门范围内数据的一致采样。
通过分析关键字-值对模式,设计哈希采样方法可以有效处理数据流中复杂查询与采样问题。
如何在数据流中统计滑动窗口内唯一元素的个数?
直接保存所有元素,计数唯一元素个数。空间复杂度高,不适用于大数据流。
利用哈希函数将元素映射到定长比特串,作为元素的“签名”。
在滑动窗口保存所有元素的签名。统计签名种类就为唯一元素个数。
使用多个哈希函数,每个元素映射到不同bit位置。过滤器初始化为0。
新元素到来,对应bit位置设为1。窗口溢出元素,对应bit位置不变0。
以bit位置1的个数作为唯一元素的估计值。
布隆过滤器会产生一定占位误报,导致唯一元素个数上估。但随着bit位数增加,误差下降快。
每个bit位置同时记录1的个数。元素到来时对应bit位置累加1,离开时减1。
直接统计所有bit位置大于0的个数,即为唯一元素的计数结果。
通过签名、布隆过滤器等技术估算唯一元素,在保证时间和空间效率的前提下解决数据流问题。
根据用户的历史行为和与其他用户的相似度,为用户推荐可能感兴趣的信息或产品。
内容推荐:根据用户查看或喜欢过的内容主题推荐相似内容。
协同过滤推荐:根据用户与其他用户的兴趣相似矩阵,利用其他用户的行为推荐。
知识推荐:结合用户个人资料和行为习惯进行个性化推荐。
收集用户行为数据,如浏览,购买,评分等
计算用户与用户,项目与项目的相似度矩阵
对新项目或新用户进行预测评价和推荐
实时学习,不断更新相似度模型提升推荐效果
覆盖率:推荐最大限度覆盖 possível喜好项目
新颖度:包含一定比例用户未曾接触的项目
准确性:推荐列表与用户实际喜好匹配的程度
可解释性:可解释每一推荐理由
可信赖性:避免推荐出问题项目
基于大数据的个性化推荐,能有效提升用户体验和企业营收水平。
根据用户查看或喜好的内容属性,找到内容属性相似的项目推荐给用户。
收集用户行为数据,如浏览历史记录
对每种内容提取特征摘要作为内容描述符
计算用户查看项目与其他项目内容特征的相似性
根据相似度从未查看项目中选取Top-N项目推荐
包含标题、作者、主题词等内容本身信息作用描述。
常用余弦相似度、欧式距离等方法计算两个内容描述符之间的相似程度。
随着新内容不断增加,需要定期更新内容描述符数据库,并根据最新用户行为实时学习模型。
以新闻网站为例,根据用户浏览新闻主题和关键词,推荐其他相关新闻内容。
根据内容本身属性进行匹配,可解释和控制推荐质量。
需要大量人工标注训练数据,新内容需及时更新描述符。
基于内容属性的个性化推荐是内容推荐的经典方法。
根据用户历史行为和与其他用户口味相似度,为活跃用户找到其他潜在感兴趣项目。
构建用户对项目的评分矩阵,空值表示用户未曾评价该项目。
计算两个用户对同一组项目的评分差异,如 PersonCorr距离,得出用户之间的相似度矩阵。
计算两个项目在同一组用户上的评分差异,得出项目之间的相似度矩阵。
根据用户相似矩阵,预测活跃用户对新项目的潜在评分,并推荐评分高的项目。
以电影推荐为例,说明构建相似度矩阵和预测评分的具体过程。
新用户新项目数据稀疏问题,以及推荐效果随时间下降问题等。
协同过滤是利用用户历史行为偏好信息进行个性化推荐的重要技术。
实现协作过滤最費時的步驟是找出對一個項目或用戶最相似的商品或用戶。要找出最相似的商品,需要將目標商品與其他所有商品計算相似度,比如使用餘弦相似度或中心化餘弦相似度。如果為每個步驟都進行這樣的計算,時間複雜度將是用戶-商品評分矩陣的大小。然而實際上,用戶和商品數量極大,直接計算不現實。所以需要預先計算每個商品與相似商品,或每個用戶與相似用戶的相似度。但預計算的時間也會很長。
使用局部性敏感哈希等方法,快速找到目標項目或用戶的近鄰集合。
通過對用戶和商品進行聚類,將搜尋範圍限定在集群內,提升效率。
使用降維技術,將高維用戶-商品空間降低維度。
定期(每天或每幾小時)預先計算近鄰相似度,而非實時計算。
優:適用任何類型商品,無需手動選取特徵。
劣:新客戶問題、疏密問題(大部分用戶未評分大部分商品)、新商品問題、流行偏差(傾向推薦熱門商品)。
結合內容推薦成分,來解決新商品問題。
結合全域基準推薦法,多使用整體信息而非具體用戶行為。
結合多個推薦系統(如全域基準與協作過濾),通過線性模型組合預測。
針對新用戶利用人口統計資料構建假設個人偏好來解決新客戶問題。
使用全域基準考慮整體平均評分、用戶與商品的偏差,估計初值;然後結合協作過濾修正,通過加權求和得出最終推薦。這種方法既可解決新客戶問題,又融合了個性化推薦。
以用户-电影评分矩阵为例,部分评分作为测试集,算法预测这部分并与真实评分对比。
计算预测值与真实值差的平方和平均值,称为根均方误差(RMSE)。它是最常用的评估指标。
仅关注预测精度,忽略推荐目的,可能推荐集中重复,忽略用户上下文。
推荐项目一致性差,无法引入新项目。用户上下文变化时推荐失效。项目顺序影响体验较大。
考虑预测多样性、新颖度。
根据用户上下文Personalized推荐。
排序项目推荐顺序。
仅评估高分项目推荐情况,如Top-K Precision。
统计用户高分项目TopK在推荐前K项中的匹配度,更符合推荐目的。
正确评估指标能促进算法优化,提高个性化推荐质量与用户体验。
将稀疏矩阵表示为两个低秩矩阵的乘积,可以有效提取矩阵内在信息。
任何矩阵M都可以写为UΣV^T的形式:
奇异值分解是有效解决推荐系统稀疏数据问题的数学工具,提取数据内在特征。
使用奇异值分解(SVD)可以有效提取矩阵内在信息,将高维数据投影到低维空间中,以最小化重构误差。
奇异值分解找到数据点在某个轴上的投影误差和最小,这就是最优投影轴。
用奇异向量矩阵U乘以奇异值Σ,可以得到数据点在各主成分轴上的坐标。
保留前k个最大奇异值及其对应的奇异向量,其余设置为0,将高维空间投影到k维子空间中。
用弗罗贝尼乌斯范数来衡量两矩阵之间的误差大小,它是各元素差的平方和的平方根。
用一个2D例子展示如何通过SVD找到最优投影轴和数据点在此轴上的坐标。
能最大限度提取矩阵内在信息,实现无监督降维。降维后数据与原数据误差最小。
使用奇异值分解(SVD)可以将矩阵A分解为三个矩阵的乘积:U∑V^T,其中U和V都是正交矩阵,∑为对角矩阵,记录奇异值。
通过将∑矩阵中的一些小奇异值设为0,可以得到低秩矩阵B=U∑’V^T近似A,这里∑’只保留部分奇异值。
用弗罗贝尼乌斯范数‖A-B‖衡量A和B之间的误差。SVD产生的B使得这个范数达到最小。
常见做法是选择使通量(奇异值平方和)达到80%~90%的奇异值维数K。
对矩阵A进行SVD需要O(n^2m)或O(nm^2)时间,其中n和m分别为A的行和列数。
SVD能够提取矩阵内在信息,实现无监督降维。它给出秩K近似矩阵B时,B与A之间的误差最小。
假设有用户和电影间的评分矩阵,利用SVD将用户和电影投影到概念空间中,找到喜欢某电影的用户,并基于此找出可能也喜欢的其他用户。
将特定用户构建为查询点Q,将Q与主成分向量V进行内积,得到Q在各个概念轴上的坐标,实现到概念空间的映射。
在原始空间中,Q与未观看电影但喜欢其他电影的用户D没有相似性。但将两者投影到概念空间后,两者在科幻概念上坐标接近,表明用户特征相似。
对对称矩阵A进行SVD等同于对其进行特征分解。奇异值的平方即为矩阵对应的特征值。
优点是可以找到误差最小的低秩近似。缺点是奇异向量难以解释,并且分解后的矩阵通常不是稀疏的。
SVD可以提取矩阵内在信息进行降维,在推荐系统等领域有广泛应用。它给出的低秩近似矩阵会使重构误差最小。
与SVD目标相同,将矩阵A表示为三个矩阵C、U、R的乘积,但在计算成本和结果解释性上优于SVD。
C矩阵选择A矩阵某些列组成,R矩阵选择A矩阵某些行组成。
利用C和R交集处的伪逆矩阵计算出U矩阵。
理论证明COR重构误差小于SVD误差加上一个Epsilon项。
允许COR选择Klog(1/Δ)/ε^2列,K^6log(1/Δ)行,能与SVD选择K列效果近似,但计算成本更低。
通常选择4K行列即可与SVD相当,CUR更易于结构化数据提取隐含信息,效果更好。
CUR分解在降低计算成本和结果解释性上优于SVD,是一种有效的矩阵低秩近似技术。
CUR算法为选择矩阵A的某些列形成C矩阵,选择某些行形成R矩阵。
当C选KlogK/ε2列,R选KlogK/ε2行时,CUR误差小于SVD误差的2ε倍,概率大于89%。
CUR算法可以近似实现矩阵低秩分解,效率高于SVD,且重构误差控制在SVD的2ε倍范围内。它是一种实用的矩阵降维方法。
CUR分解易于解释,C矩阵和R矩阵为实际数据,特征向量是稀疏的。
重复采样的行/列仅保留一份,但乘以重复次数平方根进行缩放,保证结果一致。
SVD中Σ矩阵稀疏但小,U矩阵稠密;CUR中U矩阵稀疏但小,C和R矩阵稀疏。
DBLP论文作者-会议矩阵,4万作者×3.5k会议,具有明显稀疏结构。
重建误差、存储空间大小、计算时间。
CUR重建误差与SVD一致需要更少存储空间和计算时间,因为特征向量稀疏。
CUR分解能有效提取稀疏矩阵隐含信息,在解释性、存储和计算效率上优于SVD,适用于推荐系统降维。
建立用户与项目的关联,得出用户喜好,为其推荐个性化项目。
将稀疏用户-项目评分矩阵分解为两个低秩矩阵的乘积,提取潜在因素。
假设用户偏好和项目特征可以表示为一组潜在因素,用户喜好一个项目的程度由这些因素决定。
用奇异值分解提取用户和项目在各潜在因素上的坐标,预测未知评分。
基于SVD提取潜在语义结构的无监督学习方式。
基于非负矩阵分解,提取非负潜在因素,结果更易解释。
矩阵分解找到潜在因素空间下用户和项目的关系,实现个性化推荐,是推荐系统重要理论基础。
采用小批量随机梯度下降法最大限度减少成本函数,即预测误差平方和。
将预测评分标准化到1-5星级,避免负数或过大预测值。
准确率、召回率、覆盖率、新颖度等指标衡量个性化和质量。
潜在因素模型在推荐系统中广泛应用,通过矩阵分解提取隐含关系有效提升推荐效果。
本课主要探讨了如何找到隐含因子来构建推荐模型。
首先,使用矩阵分解将用户-物品评分矩阵R分解为QMP式,其中Q和P表示用户和物品的隐含因子矩阵。
然后介绍了梯度下降算法来解决这个最优化问题,找到P和Q矩阵。具体来说,首先使用SVD初始化P和Q,然后重复以下步骤求解:
给定Q,计算P关于损失函数的梯度,并使用学习率η沿梯度下降的方向更新P。
给定更新后的P,同样计算Q关于损失函数的梯度,并使用学习率η更新Q。
如此反复直到梯度接近0,即收敛到最优解。
但是直接最小化训练误差可能会导致过拟合。为此,利用正则化来平衡模型复杂度和预测性能。具体来说,在原始目标函数基础上添加一个正则项,其中λ参数控制两者之间的权重。
正则项的作用是:对样本少的用户推荐简单模型,但对样本多的用户允许更复杂的模型,从而避免过拟合。
最后,通过Netflix挑战数据实验发现,使用两个隐含因子可以很好地捕获电影类型等规律,实现内容层面的推荐。
模型用户评分考虑用户偏好和项目偏差,用三部分表示预测分数:平均分+用户偏好+项目偏差。
将用户偏好和项目偏差作为参数加入优化问题,使用梯度下降同时学习隐含向量和偏好参数。
仅使用隐含向量RMSE为0.9,加入偏好后RMSE下降到0.898,性能有提升。
电影受欢迎度和评分随时间变化,可按月训练分隔模型捕获时效影响。
加入时间因素后,RMSE下降到0.75,接近奖金线0.85,但参数过多容易过拟合。
集成130个推荐模型,每个模型给一个评分,最后合并预测,将RMSE降到0.75并获得奖金。
实践中常用隐含模型,深入研究可以细分时间段或多模型集成,进一步提升推荐precision。
给定一组数据点和点间距离定义,将数据点分组成簇,使同一簇内点距离近,不同簇点距离远。
高维空间中几乎所有点距离相近,难分组;簇重叠等。
天体光谱分类、音乐分类、文本主题提取等。
根据数据表示选择距离度量,如测试集表示选择雅各布距离;文本空间表示选择余弦距离。
层次聚类方法:合并式(自下向上)或分割式(自上向下)。
点归属聚类方法:不断将点分配至最近簇,直至点全分配完毕。
聚类在很多应用中能提取数据隐含关系,但是高维聚类存在困难,不同方法针对不同场景而有不同表现。
层次聚类方法可以分为两种:
底向聚类法:每个数据点起初单独作为一个集群,然后不断选择两个最近的集群进行合并,形成新的大集群,直到所有数据点合并成一个集群为止。
顶向聚类法:所有数据点起初作为一个大集群,然后不断将集群进行划分,提取出内部相似性高的子集群,直到每个数据点单独成为一个子集群为止。
欧几里得空间:可以使用聚类质心来表示一个聚类。聚类质心通过计算所有数据点在各个维度上的平均值得到。
非欧几里得空间:由于无法计算质心,必须使用另一种表示方法“簇代表点”。簇代表点是该聚类内其他点距离最近的那个点。
欧几里得空间:直接计算两个聚类质心之间的距离。
非欧几里得空间:把簇代表点视为质心,计算两个簇代表点之间的距离。
设置预先的簇个数K,当聚类结果达到K类时停止。
设置聚类的合适程度标准,如簇直径、半径、密度等,当下一次合并结果无法满足标准时停止。
初始化:每个数据点一个簇。
计算所有簇对距离,找到最近的两个簇。
合并这两个簇。
更新簇间距离矩阵。
重复2-4步,直到终止条件满足。
算法时间复杂度为O(n2logn),适用于内存中小规模数据集。对于大数据集通常使用其他更高效的聚类算法。
k-means算法是一种典型的点归属聚类方法。
随机指定k个质心点。
将每个数据点分配至与之最近的质心形成的簇。
再根据每个簇内的数据点,重新计算质心点的位置。
重复第2-3步,直到质心点位置不再变化。
利用 Within Cluster Sum of Squares(WCSS)参数来评价分cluster的好坏,即各个数据点到其所属质心的平方误差和。WCSS越小,则表明cluster效果越好。
易实现,计算效率高。但可能得到局部最优解。
需要预先指定聚类数k,对这个参数很敏感。
适用于质心分布紧凑的球形簇,无法很好处理非球形、重叠簇的情况。
在高维空间效果不佳,因为距离失去意义。
对异常值和噪声点很敏感。
需要多次运行以获得更优解,每次结果可能不同。
k-means在许多情况下效果很好,但有其固有缺点,在实际问题中需要综合多个因素选择或设计聚类算法。
BFR(Ball Forest Reorganization)是一种基于联合概率模型的自适应聚类算法。
初始化所有数据点为单个球形簇。
计算每个数据点的稠密度,取最大密度点为球心。
逐个数据点计算它被哪个球心吸引,分配到距离最近的簇。
合并过于相近的簇。
移除体积过小或数据点过少的簇。
重复3-5步,直到联合概率增益不再显著。
可以探测任意形状的复杂簇结构。
算法自适应,无需预设簇数。
考虑噪声点及异常值的影响。
处理大数据效率高,能实时增量聚类。
但是也存在局部极大值问题,需要多次运行取优解。
BFR算法通过动态形态自我组织,能更好地从数据中发现隐含的簇结构信息。
CURE算法对k-means算法进行改进,能发现任意形状的非球形簇。
从每个簇中随机采样若干数据点。
对每个采样点邻域内的数据点执行局部链接,形成子簇。
采用递减函数代表子簇变化趋势,得到最终的簇代表点。
按代表点分配数据点,更新代表点位置。
5.重复步骤4,直到收敛。
可以找到天然分块、水平或链式分布的非球形簇。
不需要预先指定簇数,可以自动识别簇数。
采样操作可以有效缩小问题规模,适用于大数据集。
存在参数设置敏感性问题,需要多次试运行选优参数。
与BFR算法相比收敛速度较慢。
CURE算法通过局部链接实现对非球形任意形状簇的识别,在一定条件下效果优于k-means。
谷歌AdWords平台面临的一个重要问题是如何为每条搜索query匹配相关广告。
每个广告都关联一些关键词。
每次搜索都对应一个query词。
需要设计匹配算法,根据query匹配相关广告。
数据量巨大,每天成百万次搜索查询。
关键词之间关系复杂,手工匹配难以完成。
需要实时响应,匹配延迟影响用户体验。
广告商竞争激烈,匹配结果影响广告收入。
词性匹配:查询词与关键词精确匹配。
扩展匹配:使用词典实现关键词间相关性。
人工规则匹配:运用专家知识编写入手规则。
利用大量历史采集数据,采用统计学习方法自动学习广告与查询之间的关系,实现更优质的匹配服务。
平衡算法可以通过历史数据自动学习广告与查询的匹配模式,用于解决AdWords问题。
建立广告-查询关系二分图。
每个边加入权重,表示他们的相关程度。
使用PageRank算法计算顶点权重,高权重表示相关程度强。
对新查询,返回权重最大的前N个广告进行匹配。
从日志中提取广告、查询及他们的关系。
初始化二分图及每条边的权重。
不断迭代更新顶点PageRank权重分数。
当权重收敛后结束,保存最终模型。
在线实时为新查询返回匹配广告。
可以自动学习广告与查询的匹配模式。
根据大量历史数据进行调优,匹配效果好。
在线实时响应能力强,应对高频查询。
准确匹配率和新查询匹配率都能提升。
本节讲授广义平衡算法,用于解决广告拍卖问题。
假设有n个广告主,每个广告主的预算B相同。每次查询只有1个广告位。
最优算法是:将第1轮查询分配给第1个广告主,将第2轮查询分配给第2个广告主,以此类推,将第K轮查询分配给第K个广告主。如此每次查询都能分配,算法收入为n×B。
平衡算法每轮将查询分配给各广告主,以保持其预算消耗的平衡性。
具体做法是:第1轮将查询平均分给所有广告主,每份B/n;第2轮只考虑第2-n个广告主,平均分B/n-1给每个广告主,第3轮只考虑3-n广告主,平均分B/n-2…
通过欧拉列将求和公式求出,平衡算法能分配查询的轮数为n×(1-1/e)轮。收入为n×B×(1-1/e)。
实际情况下,每个广告主预算和出价可能不同。
广义平衡算法考虑每个广告主i不同的出价Xi和预算Bi,计算每个广告主对当前查询Q的”积分”:
Si(Q)=Xi×(1-e)^-fi
其中fi为广告主i当前剩余预算比例(1-已花费/总预算)
将查询Q分配给积分最大的广告主。
证明当出价和预算都相同时,等效于简化模型下的平衡算法。广义平衡算法的竞争比也达到1-1/e。
假设我们是一个电子邮件服务商,需要为每封邮件判断是否是垃圾邮件。
每封邮件用特征向量表示,每个词对应一个维度,值为0/1。
分类问题为二分类:垃圾/正常。
假设存在权重向量W,能使得不同类别样本点分布在W的两侧。
预测函数为:W·X ≥ θ则预测为1类,否则为0类。
目标是学习权重向量W和阈值θ,使得类间间隔最大。
类间间隔为距离最近样本点到分离超平面W·X=θ的最小距离。
学习过程求解最大化间隔问题,所得权重向量与 support vectors(支持向量)一致。
新样本 prediction 根据预测函数分类。
支持向量机因此被称为maximum margin classifier。
概括能力强,防止过拟合。
学习过程独立于特征尺寸,对异常值和噪声不敏感。
学习效果好,广泛应用于文本分类、预测分析等领域。
我们需要区分垃圾邮件和正常邮件。
每个邮件用词频特征向量表示,特征包括各词是否出现。
假设存在权重向量W可使样本点分类,预测函数为:W·X ≥ θ为1类,否则为0类。
目标是学习W和θ,使分类间隔最大。间隔定义为离最近样本点到划分超平面的最小距离。
我们想找到能最大限度地将样本点分开的决策边界,即最大化分类间隔。
间隔γ定义为离决策边界最近样本点的距离。我们可计算每个样本点a到决策线L的距离来得到γ。
我们要找到W,使得所有训练样本的γ大于某个值。这对应求解最大化γ的优化问题。
confidence=W·X+b, γ=confidence×类标签。我们要找使所有γ大于某值的W,也就是最大化最小γ。
SVM通过最大间隔原理来学习W,目的是找到能最大限度分离样本点的决策边界。我们将问题建模为一个凸优化问题来求解W。
SVM的目标是找到能最大限度分开样本点的决策边界,即最大化分类间隔。
间隔γ定义为离决策边界最近样本点的距离。
需要找到W,使所有训练样本的γ大于某值。等同于求解最大化γ的优化问题。
将问题修改为求解归一化W的最小范数,从而找到最大间隔γ=1/‖W‖。
若最近样本点为X1,则X1=X2+2γW。
左右支持向量距离边界γ时,等式为W∙X+B=±1。
求解‖W‖2/2最小,使所有样本的分类confidence>1。这是支持向量机的标准形式。
SVM通过最大间隔原理,寻找能最大限度隔开样本的决策边界。它将问题修改为求解W的最小范数,从而找到最大间隔。
实际数据集通常无法利用线性分离,存在噪声点。
硬边缘SVM假设存在线性分隔超平面,但对大多数数据集无法适用。
通过引入松弛变量ξ,允许部分数据集点位于错误一侧。这样可以寻找最大间隔与最小误差的平衡。
目标函数考虑最大间隔和最小ξ之和,通过参数C控制二者权重。当C趋于无限,相当于硬边缘条件。
ξ衡量数据集点到正确边界的距离。ξ越大,误分类程度越严重。
找寻W、B以及ξ,使‖W‖2/2 + CΣξ最小,同时满足分类限制。通过此方法同时兼顾最大间隔和最小误差。
C控制最大间隔和最小误差的权衡。C越大,误差成本越高,结果偏重数据拟合;C越小,结果偏重间隔最大化。
解决实际数据噪声问题,通过C参数调节分类限制,取得Classification-error和间隔的平衡。
SVM目标是找到最大化间隔的分类超平面。
间隔γ定义为离决策边界最近的样本点到该超平面的距离。
要计算每个样本点Xi到决策超平面W·X+B=0的距离,使用公式:
| γi = | W·Xi + B | / ‖W‖ |
若Xi属正类,则W·Xi + B ≥ 1;若Xi属负类,则W·Xi + B ≤ -1。
| 若样本点正确分类,则γi = | W·Xi + B | /‖W‖ ≥ 1。 |
| 若样本点错误分类,则0 < γi = | W·Xi + B | /‖W‖ < 1,需要引入松弛变量ξ。 |
引入松弛变量后,所有样本点间隔公式统一为:
γi = 1 - ξi * yi(W·Xi + B)
其中ξi≥0。最大间隔为mini{γi}。
通过计算每个样本点到决策边界的距离γi,并考虑分类情况,求解最大间隔问题。
本节通过一个实际运输服务例子,说明SVM在线上学习中的应用。
根据客户交换信息给出运费价格,预测客户是否接受。
利用特征X(客户信息)和标记Y(接受与否),训练SVM分离线。
网站运行持续接受客户,但客户偏好随时间变化。模型应动态调整。
客户上站,represented为(X,Y)对。
根据Y更新权重向量W,小步幅改变W逐步学习变化。
每个客户都作为单独训练实例,实时更新模型。
适应客户动态变化偏好。
只考虑单个数据点,效率高。
模型动态,随系统变化一起学习。
采用SGD迭代优化,实现持续学习而不停止。
决策树是一种树形结构模型,用于分类或回归问题。它通过测试属性值,将样本点划分到不同叶节点上,进行预测。
决策树包含决策节点和叶节点。决策节点根据属性值进行二值划分,将样例分流到左右子节点。叶节点给出预测结果。
每个样本用多维特征向量表示。每个特征称为属性,有其特定值域,如颜色属性 domain为红、绿等;年龄 attribute 为实数域。
给定样本集合,学习输入属性到目标属性的映射函数。函数采用决策树结构,通过递归二值划分得到复杂的决定边界。
将新样本从根节点开始,按节点条件判断向左或右子树分流,最后定在叶节点给出预测结果。
用二维数据集 illustrate 决策树建造过程:递归二值划分样本空间,直到每个区域内样本标签一致,形成树状结构。
决策树可学习非线性复杂决定边界。每个节点只考虑一个属性,计算简单高效。可解释性强,易理解决策过程。
如何从根节点开始递归构建树结构,找到每层节点的最优二值划分条件。
选取能最大限度将数据集划分成纯粹的子集的属性和值进行划分。
利用信息论的概念测量属性可能带来的信息增益。选择信息增益最大的属性进行划分。
描述数据集混乱程度的度量。计算公式为:-Σp(x)loge(p(x)),p(x)为类x在数据集中的概率。
以信息熵来衡量划分前后信息混乱程度的变化。信息增益=原信息熵-经过划分后的信息熵之和。
如对特征A有两个值{0,1},原数据集熵H=1,经A划分后子节点熵为H1=0.5,H2=0.8。则信息增益=1-0.5-0.8=0.3
过拟合问题。按信息增益筛选属性后,再判断子节点合并是否能提高准确率,从而控制树的大小。
ID3/C4.5算法利用信息增益方法递归构建决策树。CART算法用基尼指数替代信息增益。
信息增益衡量属性X对目标Y的预测能力。度量Y的熵与Y给定X的条件熵间的差异。
衡量不确定程度。对概率分布求和的 logs。
Y给定X的条件下的平均熵。各X值对应的Y的熵,按X概率加权求和。
信息增益=Y的熵-Y给定X的条件熵。越大表示X对Y预测能力越强。
分析年龄、性别、吸烟等属性对预測生存80年的预测能力。吸烟效果显著,年龄较强,性别次之,最后四位社会信用码毫无影响。
计算每属性的信息增益,从大到小排序。选择信息增益最大的属性作为决策节点进行划分。
信息增益可评价特征重要性,选择决策树构建时最优属性,实现分类任务。利用历史数据挖掘属性间依赖关系。
数据量大,无法加载至内存。需要分布式计算来找到最佳划分属性和值。
将问题分解为映射和归约任务。映射处理小批数据并输出中间结果,归约汇合计算最终结果。
利用MapReduce构建决策树的算法。通过一系列MapReduce工作,递归构建每层次的决策树。
包含初始化、寻找最佳划分和内存构建三个MapReduce工作阶段。初始化获取所有属性值域,后两者迭代构建各层次。
加载部分模型,处理分配数据块,统计各叶节点左右子树数据,输出局部统计结果。
汇总映射的局部统计结果,计算所有候选划分质量,选择最优划分,输出给主节点决策。
跟踪全局模型信息和中间结果,响应MapReduce工作,负责保存决策树。
层层迭代,每个层次MapReduce配合计算最佳属性值,递归构建完整决策树结构。
决策树是数据挖掘和机器学习最流行的工具。其结构简单易懂,易于解释结果。训练和使用过程均简单高效。
过拟合serious,需要前置处理如剪枝来防止。只能处理有限特征数和数据规模。
单棵决策树精度较低。bagging通过生成多个模型并集成预测来提高准确率。
利用Hash划分大数据集成小样本,并行构建各个子决策树模型达到分布式学习效果。
决策树适用于小规模、分类和回归问题。支持向量机在大规模线性分类如文本分类等任务上效果更好。
用户分类、页面点击预测等小规模问题。支持向量机用于大规模线性任务如文本分类。
MapReduce算法设计的两个关键参数:Reduce任务规模和数据复制率。它们之间存在利弊权衡,需要找到最佳平衡点。
定义问题和算法,给出Reduce任务规模与复制率函数的下界。可以描述问题和算法本质。
MapReduce作业计算代价分为Map任务计算代价、Reduce任务计算代价和系统计算代价。
key-value对在Map和Reduce节点之间传输的代价。通常Map任务与输入 proximity,Reduce任务需将key-value对从产生地点传输到下一级节点。
最小化总成本,包括计算代价和通信代价。但工期时间也是一个重要指标,通常通信成本增加可缩短工期。需权衡两者。
利用MapReduce设计算法,不仅可以得到最优的Reduce算法,也可以扩展到使用两次MapReduce任务的方法,效率高于单次MapReduce方法。
通信代价通常占主导地位,是决定作业结束时间的关键。通常计算资源增多并不一定可以缩短工期。
取1000万患者20年病历,研究不同药品配合可能产生的不良反应。
将3000药品两两组合,每组1M字节记录,产生4.5亿组合。mapa输出2999份复件,带来9T传输规模。
将3000药品分组,每组100药,得到30组。map输出每个组内外29份记录,降低传输87G,加快处理。
输入每个记录及药ID,输出<组对,记录+ID>键值对,组对表示两组编号。
输入<组对,记录列表>,按记录内嵌ID区分,统计两组内外药品配对不良反应。
降低map复制纪录次数,大幅减少网络传输规模,保持计算复杂度不变。
同一组内药品比较由多Reduce完成,需要规则划分任务。
细致划分大问题,合理设计MapReduce流程,可有效减少计算和通信成本,解决大规模实际问题。
提出MapReduce计算模型,分析算法在该模型下的性能。
MapReduce程序包含Map和Reduce阶段,输入及中间结果保存在分布式文件系统。
计算成本、通信成本和执行时间。
描述问题数据在Map输出中的分布规律。
最小化计算成本和通信成本的总和。
考虑数据和任务划分、任务调度以及通信网络带宽限制等实际因素。
分析Map和Reduce任务规模,以及Shuffle阶段的通信量,并给出理论下界。
WordCount、排序等基础算法,给出其在MapReduce模型下的时间复杂度分析。
提出系统框架研究MapReduce算法,分析通信成本对算法性能影响,为实际应用提供评估指导。
np完全问题求近似算法,系统heterogeneous环境下的分析研究。
计算两个矩阵A和B的乘积C=A×B。
每个元素分别计算所有相乘项的和,时间复杂度O(n^3)。
采用块分割策略,将矩阵分为小块并行计算。
输入A和B的块,以块坐标为key输出该块元素。
按块坐标映射,相应元素相乘并求和,输出结果块。
Map输出大约n^2个分块,Reduce任务数也是n^2。
每个Map输出一个块,传输量为O(n^2)。
Map和Reduce时间均为O(n^2),通信时间为O(n^2)/B,B为网络带宽。
调整块大小,减少数据移动次数,利用数据本地性等。
MapReduce框架可以高效并行解决矩阵乘法问题。
定位敏感哈希,用于近似nearest neighbor搜索。
通过哈希函数,将近似的对象映射到同一个桶里的概率高于其他对象。
共有四个LSH家族:模赘 similarity search、Hamming距离、杰卡德相似度和角度相似度。
通过模赘函数对向量内积进行二值化,计算Hamming距离近似欧式距离。
选取随机向量,计算投影,取值大于零作为哈希值。
信息检索、推荐系统、物理实体追踪等领域进行近似KNN查询。
定位敏感,空间效率高,支持动态数据集。
映射精度影响查询质量,空间摄受LSH函数数影响查询效率。
LSH家族提供通用框架实现大规模近似nearest neighbor问题。
本节将介绍更多关于LSH家族的知识,其中包括:随机超平面LSH家族、欧式距离LSH家族等。
该家族适用于角度相似度,每一个哈希函数以随机向量V定义,将向量X映射到正负号标号的桶里。
任意两个向量X和Y的概率P(H(X)=H(Y))等于1-θ/180,θ为X和Y之间的角度。
每一个哈希函数以随机线段定义,将向量投影到线段上,根据投影点分桶。
如果两个点的距离D小于某值a,它们有很大概率落入同一桶;如果D大于a,它们很可能不在同一桶。
实际上,任何LSH家族都可以用于实现近似最近邻搜索,只要它满足一定的定位敏感性质性。
LSH家族提供统一的解决方法,可以用于处理各种距离度量问题,是大规模近似最近邻搜索中的重要工具。
不考虑所有集合对,适用于高雅可德相似度或低雅可德距离的情况。
通过字符串方式来表示集合,字符表示元素。排序元素后形成字符串。
分析字符串编辑距离与集合雅可德距离的关系。
利用B树快速查找长度在某范围内的字符串对。
利用前缀、后缀筛选候选字符串对,减少实际相似度计算对数。
词按文档频率排序,低频词作为字符串首字符,提高索引效果。
长度相近不确定相似度,需要真实计算集合雅可德相似度。
从简单长度索引开始,加入更多元信息优化查找效率。
查找效率高,结果精确,适用于大数据近似集合查询。
设字符串s的长度为L,上限Jaccard距离为J。字符串s的前缀为其前floor(JL)+1个位置的子字符串。
如果两个字符串Jaccard距离≤J,它们必然在前缀部分有交集符号。利用此建立索引查询高相似字符串。
将每个字符串按前缀符号建立键值对,放入根据符号命名的迷宫类别中。以B树实现更高查询效率。
给出具体字符串,计算其前缀长度。对不同长度字符串,其前缀长度可能不同。
输入查询字符串,查看其每个前缀符号对应的迷宫,检索相应键值对字符串。计算Jaccard距离,报告符合距离阈值的候选字符串。
利用前缀信息筛选相似字符串,大幅减少实际距离计算量。建立多级索引提高查询效率。
存储方式影响IO开销,需要权衡存储完整字符串 vs 指针。关键在于寻找平衡点。
字符串前缀索引提供有效方法解决大数据近似字符串匹配问题。
给出字符串s和T,分析其首个匹配符号在s和T中的位置I和J,以及这两个位置提供的编辑距离下界。
LCSS最长时,I后s中每个符号都在T中匹配。最长LCSS长度为s长度减I加1。
把编辑距离下界和LCSS长度上限代入Jaccard公式,获得J的上限表达式。
索引包含符号及位置键值对(a,I),索引字符串s所有前缀位置。效率高于单层索引。
据I算出Jaccard上限公式,不同I下J上限值不一。以此判断需要搜索的索引键值范围。
给出查询字符串及相关参数,演示如何根据I计算不同J范围,以确定需要检查的索引键值对。
在I的前缀位置循环中,根据I计算J上限,在相应范围内的键值对中检索候选字符串。
利用I及相关定理精确定位需要检查的索引区域,大幅提高近似匹配效率。
给字符串s和T,假设s的第一个匹配T的字符位于第i位置,T的位置为j,则编辑距离下界为i+j-2。
假设s和T首个匹配字符分别在i和j位置,取字符长为LCSS的一部分,LCSS长度上限为1加上二者中较短后缀长度。
将编辑距离下界和LCSS长度上限带入Jaccard公式,可以得到J的下界。
索引键包括字符、位置和后缀长度,每个键对应一个桶,用于存储具有对应特征的字符串。
给出查询字符串,根据其每个位置的特征,计算可能满足不等式范围的键,得到需要搜索的桶。
若两个字符串的后缀长度差异太大,则其编辑距离一定超过下界,无法成为候选匹配strings。
给出具体字符串,分析其在不同位置建立的键和对应的桶,以及根据查询进行桶搜索的过程。
高维索引可以利用位置和长度信息更精确定位需要搜索的范围,有效减少假正匹配。
计算网页在特定主题上的重要性分数,而不仅仅根据整体流量计算PageRank。
PageRank最初目标是找出网络上重要网页,但不一定想要泛电流量高的页面。
给出一个页面集S,称为传输集,只允许随机游走者跳到S中的页面。
将随机跳转概率分布限定在传输集S内,构建带主题偏向的矩阵A。
每个传输集S对应一个主题特定PageRank向量。利用OpenDirectory构建传输集。
用户选择主题后,搜索结果根据该主题的PageRank排序。也可以分类检索词与主题匹配。
通过调整传输集S和随机跳转概率β,观察PageRank分数的变化情况。
主题特定PageRank定量探究网页在特定主题上的重要性,有助于主题驱动的网页检索。
介绍如何使用PageRank来测量图中节点间的亲缘关系。
使用最短路径可能计算结果相同,但亲缘关系实际不同。
网络流无法惩罚长链,无法准确反映亲缘关系。
从单个节点出发,随机游走但能fois重新返回出发节点,计算其他节点的访问概率。
构建论文-会议图,从特定会议节点出发随机游走,计算其他会议的访问概率。
与出发会议相关性越高的会议,访问概率越高,反映两会议亲缘关系强弱。
方法通用,不限于特定图或领域,可以衡量任意节点间亲缘关系。
每节点都需单独计算,不具备很好的可扩展性。
考虑集合作为重新定位点,回到个性化PageRank概念,可处理大规模问题。
spammer创建大量虚假页面,所有页面都链接至目标页面,集中传输PageRank得分。
Google成为主导搜索引擎后,骗子试图操纵搜索结果。他们创建链接农场集中PageRank。
网页可分为无法访问、可访问和spammer自有三类。spammer可以添加评论等操纵可访问页面。
spammer从可访问页面添加链接至目标页面T,形成链接农场。所有页面得分都传给T。
利用PageRank方程计算 spammer自有页面和目标页面T的得分。T得分受链接农场大小M影响,会越来越大。
例如采用汇聚模式,可访问页面通过评论链接至T,spammer页面全链接T。
分析页面链接关系,检查可疑页面是否满足上述特征,以检测并阻止链接农场操纵搜索结果。
从少量人工标注的可靠网页开始,通过链接传播信任得分,识别整个网页图中spam页面。
链接农场战争中,检测结构后spammer隐藏,需更通用解决方案。
选择可信赖网页集,从中传播信任得分,近似隔离理论下好页面难指向spam。
采用主题特定PageRank,设定可信赖网页集为瞬移概率,沿链接传播信任分数。
平衡语料量和覆盖度,采用高PageRank网页或受信任域名下网页。
低信任传播得分视为spam,但新页面得分也可能低,需改进。
比较综合PageRank与信任传播PageRank差异,高差异页面视为spam。
考虑相对信任传播能力而非绝对分值,识别spam更准确。