标签：采样 ADS Closeness 笔记算法距离哈希节点复习

许我人间一两风，吹散十万八千梦

"余幼时即嗜code，家贫，无computer以观，每假借于电脑之家，拆板以刻，计日以还。既加冠，益慕算法之道，又患无cpp，java以游，遂至北理工，观此ppt。
当余之读ppt也，负箧曳屣，行无暖气之中教中，穷冬烈风，银杏叶深数尺，面庞皲裂而不知。至舍，四支僵劲不能动，吾自持汤沃灌，以衾拥覆，久而乃和。寓逆旅，北理日再食，无鲜肥滋味之享。同学长皆被绮绣，戴朱缨宝饰之帽，腰白玉之环，左佩雅思，右备答案，烨然若神人；余则六级未过处其间，略无慕艳意。Sktech中有足乐者，不知英语之奉不若人也。盖余之勤且艰若此。"

——关太师

Lecture 1

你说人生艳丽我没有异议
你说人生忧郁我不言语
只有默默地承受这一切
承受数不尽的

1 Frequent keys: The Misra Gries structure

1.1 引入及概念

Lemma：对于单个的MG sketch，每个key的误差上界为(m'-m)/(k+1)。

1.2 合并

Claim：对于合并后得到的MG sketch，每个key的误差上界依旧为(m'-m)/(k+1)。

合并的减少值的证明以及构建sketch减少值的证明

2 Set membership: Bloom Filters

3 Counting: Morris counters

改进1

步进时V==1，合并时V>1

改进2

证明方差

一刻也没有为计数器们悲伤，立刻赶到战场的是

Lecture 2

0 随机变量的边界 Quality of Estimates

1 蓄水池均匀采样

有关蓄水池算法的解释https://www.cnblogs.com/doublexi/p/15665695.html

2 基于bottom-k均匀采样的不同值采样

3 K-mins Minhash Sketch

最小哈希在[0,1]为什么期望是1/（n+1）?
因为这里的哈希函数满足h(x)~U[0,1]。易知，k个独立同分布的随机变量当中的最小值的期望为：E(Y)=，
其中Y=min{X1,...,Xk}。故当X1,...,Xk~U[0,1]，则前式中F_X(x)=x，f_X(x)=1,代入得E(Y)=1/(k+1)。

4 克拉莫劳下界

5 充分统计量

逆概率估计方法

梦为努力浇了水
爱在背后往前推
当我抬起头才发觉
我是不是忘了谁

是的，逆概率估计一直是我的好兄弟，PPS是我一直想来到的团队……

Lecture 3

加权采样（估计部分满足条件的和）

目标：权值越高越容易采样

泊松采样

期望的样本大小为k=\(E\left[ |S| \right] =\sum_i{p_i}\)
逆概率估计：
对于每个样本，如果被采样，则赋予一个\(a_i=\frac{w_i}{p_i}\),否则为0。（为了最终是无偏估计）
\(a_i\)的方差为\(Var[a_i]=w_i^2(\frac{1}{p_i}-1)\)，对于最终采样的结果的方差，则为\(Var\left[ \hat{w}\left( X \right) \right] =\sum_i{Var\left[ a_i \right]}\)
因为pi为我们自己设计，我们肯定希望方差越小越好，但是采样量还要保证是k，则最终的优化问题就是：

在\(\sum_i{p_i}=k\)的情况下，最小化\(\sum_i{w_i^2(\frac{1}{p_i}-1)}\)

最终pi和wi成正比，可以保证最小化，即\(\alpha _ip_i\gets \min \left\{ 1,\alpha w_i \right\}\)
证明（PPS）：

得到方差上界：

CV值（误差）为：

我们期待一个可合并的固定大小的采样。

Bottom-k：

赋予每个样本一个标签，进行排序，取最后的k个样本即为最终采样结果。

过程：

输入一个样本权值对（x，w），随机出一个h(x)（属于0到1之间），赋予该样本对一个标签h(x)/w
有放回PPS：
无放回PPS：
伪代码如下：

简单解释：维护一个第k小的哈希值，如果新进来一个元素进行比较，若小于原来维护的哈希值，则进行替换，并重新排序。合并就是将两个合并之后重新选k个。

对有放回PPS进行证明：

依旧构建一个Inverse概率，当一个样本被采样它的ae=w/pe，否则为0

被采样就是哈希值h(x)<w\tau

和与之前的PPS一样：

对无放回PPS进行证明：

无放回采样过程：

证明上述过程和等价

\(\underline{\mathsf{Lemma}}:\text{ Equivalent to bottom-}k\mathrm{~with~}r(x,w)=\frac{-\ln h(x)}w\left(\sim Exp[w]\right)\)
证明如下：

有重复元素（进行聚合）

一个x可能出现好多次，我们要进行估计

相比之前就多了一步重复元素保留最小的rank

聚合类似

局部敏感哈希是一种最小哈希的应用

近似查询：

做一个嵌入之后，做相似性查询。一种方法就是做minhash（同一个hash函数），对minhash结果进行分析。
相似性度量：

加权杰卡德相似性：

简单解释：分子加两个中的最小值，分母加两个中的最大值

文档相似度：
1.定义特征：

2.杰卡德相似度：

3.利用最小哈希去估计杰卡德相似度：

简单解释：N1并N2直接聚合就可以（取同一个特征的最小值），N1交N2需要再做一次判断，是否同时存在于N1和N2

总体来说Bottom-k类似
alpha可以有三种情况

n是两个集合不同元素的个数
方差的证明：
http://www.cohenwang.com/edith/bigdataclass2013/lectures/lecture3.pdf

左思想，右思量
出路在何方
天茫茫，地茫茫
无亲无戚靠台郎
月光光，心慌慌
故乡在远方

那一天，人们回想起了被图支配的恐惧

Lecture4

想要在非常大的图计算上做到的：
1.保持总计算/通信/存储在这些数据的大小上实现线性（或者亚线性）
2.权衡计算和近似质量
3.并行化(最小化依赖链)
4.局部化依赖(共享边的节点彼此存储得更近)
描述一个图中节点的特征：
度中心性：与节点的出入度相关，最好计算
特征向量：我是否重要取决于我的相邻的结点
Betweenness：我是否在必经之路上
Closeness：我是否可以快速到达很多节点

节点的度（重要度特征，结构特征）

对邻接矩阵的每行进行一个加和。只看数量不看质量

节点的中心性（重要度特征）

特征向量重要度：
一个节点是否重要取决于它的邻居是否重要。计算方法为：

可以等价为求一个矩阵的特征向量问题：

Betweenness centrality：
计算一个节点处于多少个一对节点的最短路径之上，计算方法如下：

Closeness centrality：
该节点到其他节点的最短路径之和的倒数，计算方法如下：

对于Closeness中心性，有另一个名称，那就是可达中心性（近邻中心性），即为节点u关于所有u可达的结点的一个距离的函数和，分为三种类型，分别是Harmonic centrality；Gaussian（高斯）中心性与指数中心性：

这规避了之前的Closeness中心性距离为0的情况。

基于距离/可达性度量的节点sketch：

1.可达性集的Minhash摘要
可达集就是一个数数问题

由于对于大图来说单独计算每个节点的可达集消耗资源太多。因此我们利用Minhash来对某个点可达集进行一个摘要，我们记录节点v的摘要为s_v：
1).sv的模就是节点v的可达点数
2).获取可达节点的随机样本
3).计算两个节点可达集之间的关系
4).所查询的种子节点的联合到达(到达影响)

接下来，我们对k=1的最小哈希的情况，做一个说明：

k=1的最小哈希摘要很简单，选出自己这个节点的可达集中最小的哈希值，是一个迭代更新的过程。

k=2的情况也类似，维护可达集中第二小的哈希值：

接下来，我们需要思考如何高效的计算这个摘要，有两个方法：

a.图搜索（BFS）

k=1:

在O(m)复杂度内，每条边恰好遍历一次。每个图搜索都依赖于所有先前的：似乎我们需要按顺序执行 n 次搜索。

并行化基于BFS的MinHash计算：
（1）为哈希值是较低一半的n/2个节点创造一个超级节点
（2）从超级节点执行(反向)搜索，并标记访问的所有节点
emmm，下面的操作以我浅薄的知识，我觉得它是进行了一个迭代剪枝搜索，将时间复杂度降到了log2（n），但是具体的我说不明白

最终的抽象化过程为：

边遍历的总数可以增加log2n倍
我们再接下来考虑：k>1的情况：

这个图就可以被简单的抽象为三个超级节点相连

b.动态规划/分布式

对于动态规划/分布式方法，有一个点和bfs不同的是，这是一个信息收发的过程：

结论：每个边被经过的次数小于lnn次
证明：
简单解释：看不太懂，感觉是类似一个加权算法，但是它的第一句话太难懂了，最后的期望加和是1+……+1/n可以理解成积分，不过我认为应该是等于lnn，可能是考虑到整数问题吧

图图，这是我最后的Sketch了

Lecture 5

基于距离的图数据挖掘：

一.基础前置：
1.距离分布（单源、种子集、全对）
2.邻域的基数，Closeness中心性
3.邻域的相似度，Closeness相似度
4.基于距离的影响
5.距离查询（距离预言）
6.按距离抽样(与d邻域一致或概率随距离减小)，按相似性抽样
7.以特征为中心的Closeness中心性
8.基于距离的SSL(标签完成/预测)
二.具体方法：
1.生成最短距离矩阵：

与距离相关：重要性/相关性随距离衰减，可以理解是Closeness中心性：

接下来，我们说明基于衰减距离的查询：
r-近邻：

距离衰减Closeness中心性：

基于距离的影响（想说点什么，但是我有点说不出来）（这到底表达什么）
（看明白了，就是加两个节点中最大的）：

基于距离的相似性：

节点特征/属性：

一些节点（实体）具有相关的特征/标签：主题、兴趣、社区、类型...
中心性/影响集中在这一特征上
标签补全(半监督学习):基于图结构和少数标记节点预测未标记节点的标签
首先是有详细标签的情况：

接下来，我们测试只关注是否存在标签：

需要探究14%和26%的作用

相似度计算（局部相似度，仅取决于直接邻居（不过我觉得第三个算错了应该是2/log5））：

后面两个AA都算错了，应该是：

距离相似度（全局）：

下面的我觉得是（距离衰减+主题）？

上面的：

要么把beta去掉要么把c改成alpha

距离摘要：

老生常谈：对于距离的精确计算开销太大，所以我们要做距离摘要

All-Distance摘要（ADS）：

在集合中的点是要满足什么条件：
不在集合中的点的距离要比集合中哈希值第k小的点的距离大

1.每个节点的距离向量的摘要
2.允许我们近似基于衰减距离的查询

Bottom-k ADS（v)：

一个列表其中包含（节点id，与v节点最短距离）对
是MInhash摘要d>0的并集
证明如下：
如果节点i属于ADS（v），那么h(i)一定是其中一个第k小的哈希值在\(N_{d_{vi}}(v)\)
如果i属于
因为dvi<d，所以它一定是\(N_{d_{vi}}(v)\)中的一个第k小哈希。
如何计算ADS呢？详见下图：

计算K=1的情况，我们要算的是ADS（黑武士），那么先按距离排序从近及远考虑：
黑武士自己一定在ADS中，先考虑白机器人，它的h(x)=0.42，只有黑武士自己比它离得近，所以N(v,u)中只有黑武士，K=1，N(v,u)中最小的哈希值是0.63>0.42，所以白机器人在ADS中，后面的都是以此类推。

定理：ADS的期望大小小于klnn
证明：
距离节点v第i近的节点被包括在ADS中的概率是\(min(1,\frac{k}{i})\),那么期望大小小于等于n个节点之和，即为：
当k>n的时候就相等。

bottom-k ADS

使用修剪后的Dijkstra搜索算法。

具体步骤如下：

按照 ℎ(u) 递增的顺序遍历所有节点 u。
对于每个节点 u，使用 Dijkstra 算法在反向图上执行搜索。在访问节点 v 时，执行以下操作：
- 如果 u 不在节点 v 的ADS中（ADS(v)），并且满足条件 |{i∈ADS(v)∧d_vi<d_vu}|<k（即与节点 v 的距离小于与节点 u 的距离的节点数小于 k），则将 (u, d_vu) 添加到节点 v 的ADS中（ADS(v)←ADS(v)∪{(u,d_vu)}）。
- 继续遍历节点 v 的入度邻居（inNeighbors(v)）。
- 否则，如果条件不满足，可以在节点 v 处修剪搜索，即不再继续向后搜索。

这个方法通过遍历节点并在每个节点上运行Dijkstra搜索来构建bottom-k ADS。在搜索的过程中，根据条件判断是否将节点 u 添加到节点 v 的ADS中。这个过程会得到每个节点的bottom-k ADS，以便后续的数据分析和查询。这种方法可以高效地计算ADS，并应用于许多基于距离的查询和分析任务。

当通过递增哈希来构建时的正确性：
1.每个ADS(i)是通过按h(u)递增顺序考虑节点u来构造的
2.如果哈希值小于 h(u) 的 k 个更接近节点到 i，则将节点插入到 ADS(i) 中
3.尚未考虑的所有节点 j 的散列都高于 h(u)，因此条件
剪枝搜索的正确性：
1.搜索在节点 i 处修剪，没有更新（有 k 个更近的节点，哈希更小）。
2.从 j thru 到达的所有节点，反向 SP 搜索也将具有比 u 更接近的节点。

动态规划计算ADS：

简单解释：传递的信息从哈希值变成了（哈希值，距离）对，其他思想没有变化，和之前的距离摘要类似。
对ADS计算的分析与简评：
剪枝Dijkstra是基于递增的哈希值，和距离摘要的BFS类似；DP是基于递增的距离，我们只需要为每个节点保留内存 k 个条目（到目前为止 k 个最小哈希）。DP适用于节点与邻居通信的分布式消息传递计算。

从摘要回答查询：

1.通过提取MinHash草图，d邻域的基数/相似度
从ADS(v)中提取v的d邻域Nd(v)的MinHash草图：

从Minhash中可以知道：

2.Closeness中心性:HIP估计器
计算公式如下：

我们通过对每个项的无偏估计求和来估计总和：
依旧使用熟悉的逆概率估计和PPS：

如果我们有无偏存在估计量，我们可以无偏地估计中心性

关于对的估计：
1.如果i不属于ADS（v），那么其就等于0
2.如果i属于ADS(v)，那么我们计算它被包含的概率p，条件是所有节点的固定哈希值比i更接近v。然后我们使用逆概率估计：

简单解释：p就是节点当时进ADS时比较的那个哈希值，逆推一下就可以

定理：

3.Closeness相似性
前置知识：