-
利用Graph-tool进行图的可视化处理
前言 最近恶心的项目中期检查，我被分配到做社交图的分析，然而事实上我并不知道弄啥。虽然不是我自己答辩，但是考虑到还是不要太坑dalao，我决定不管怎样至少得搞点图撑撑场面免得尴尬，这几天就赶鸭子上架倒腾了下graph_tool这个专门用于对图进行可视化的python库。虽然网上中文资料不足，但是他的英文文档还是非常全面的，很多设计的小细节也在文档里提及了，非常简单容易上手。下面就从一个初学者的记录下我的学习历程。 安装 虽然是个python库，但是毕竟是要做大量数据计算的，因此graph…
-
面向最小哈希签名的LSH
LSH 我们知道最小哈希签名能够把一篇较大的文档压缩成一个较短的签名并且不影响文档间的Jaccard相似度。很多情况下，我们用最小哈希签名的目的就是为了方便的对文档进行存储，并且对于给定的文档，能在大量的文档中快速的查找相似的文章。现在我们能做到快速的对两篇文章进行相似度比较，但是当总的文档数目比较大的时候，比较所有文档的最小哈希签名仍然是一个非常耗时耗力的事。而我们知道，对于给定的文档而言，文档库中的绝大多数文档其实都没有比较的意义，如果能有一个方法能过滤掉不需要比较的大量文档，那么显然就能…
-
最小哈希签名（MinHash）简述
最小哈希签名(minhashing signature)解决的问题是，如何用一个哈希方法来对一个集合（集合大小为n）中的子集进行保留相似度的映射（使他在内存中占用的字节数尽可能的少）。 其实哈希本身并不算难，难的是怎么保留两个子集的相似度的信息。所谓保留相似度，就是说我们能十分直观的从两个子集的哈希结果中看出他们的相似度。当然，朴素的办法就用是一个长度为n的二进制数的每个位来分别对应集合中的每个元素。不过当n比较大而待hash的集合的数目比较小的时候，这种方法的效率就太低了。这时候最常用的方法…
-
相似度度量标准之Jaccard相似度
定义 Jaccard相似度(杰卡德相似度)是一个用于衡量两个集合相似程度的度量标准，他的定义如下：给定两个集合$S,T$，那么我们记这两个集合的Jaccard相似度$SIM(S,T)$为: $$SIM(S,T)=|S\cap T|/|S\cup T|$$ 也就是两个集合交集的大小除以两个集合并集的大小。显然他的取值在[0,1]区间。 扩展 原始的Jaccard相似度定义的仅仅是两个集合(set)之间的相似度，而实际上更常见的情况是我们需要求两个包(bag,multiset)的相似度，即每…
-
文档分割的shingling算法
shingling算法是最常见的文档分割算法，说白了就是将一个文档分解成由短字符构成的字符串集合。分割后的文档就可以通过Jaccard相似度等简单的度量标准进行相似度检测了。 k-shingling 对于任意一篇文档，我们把他当成一个字符串，那么他的k-shingling集合就被定义为文档中所有长度为k的子字符串的集合。比如字符串“abcdabd”，他的2-shingling集合就是{ab,bc,cd,da,bd}。 当然，所有类型的子字符串只会在集合中出现一次。不过实际的文档中可能会有…
-
用于文档关键字提取的TFIDF指标
关键字提取问题 在大规模网络文章整合的过程中，我们经常需要对某一篇文章提取关键字。比如对于某一篇关于计算机的文章，我们应该提取出类似于“计算机”、“编程”、“CPU”之类的符合人类认知习惯的关键词，但是这个过程却不是那么容易。现在，我们把问题归结为，在不使用机器学习方法的情况下，给定一个文档集，仅从单词频率等角度对文档集当中的某一篇文档进行考虑，期望能够对于该篇文章，我们能从文章中依次提取出最有代表性的关键词。 我们很容易想到的方法就是统计每个词的词频了，但是对于任何文章而言，出现频率最多的…
-
PostGIS初探
PostGIS是PostgreSQL的空间扩展，他使得PostgreSQL支持空间数据类型，比如点、线段、折线段、多边形、椭圆等等，并且能够使用高效的空间索引进行存储和查找。 安装 ubuntu下在安装好PostgreSQL的基础下用apt install postgis即可。 确认安装版本可以用在postgreSQL的shell里查询: myths=# select * from pg_available_extensions where name like 'postgis…
-
GeoHash空间索引算法简述
背景 在空间索引类问题当中，一个最普遍而又最重要的问题是：”给定你某个点的坐标，你如何能够在海量的数据点中找到他所在的区域以及最靠近他的点”？ 最常见的应用就像是**POI(Point of Interest)**的查询了，比方说客户在路上突然想吃饭了，那么我就要根据他的位置查询最近的餐馆并根据这个做出推荐。 通常情况下，一提到查找类问题，我们就会想到二分查找或者是B树查找。但是问题在于我们不仅要找到这个点，而且要找到这个点附近的点。因此对于以经纬度来确定的坐标又不好直接进行二分查找。（如…
-
Garbled Bloom Filters算法简述
简述 Garbled Bloom Filters（GBF） 算法是Bloom Filters （BF）算法的变形，并且结合了Shamir的信息分享算法，更好的解决了hash冲突的问题其形式上是将Bloom Filters算法中的BitSet数组转换成了字符串数组，数组中的每一个字符串长度为安全参数$\lambda$，可以通过调节这个参数来获得想要的安全性。该算法同Bloom Filters 一样，是一种有一定容错率的hash算法，对于存在于集合中的元素查询返回的值总是true，而对于不在集合中…
-
Bloom Filters简介
简介 Bloom Filter(又叫布隆过滤器)是由B.H.Bloom在1970年提出的一种多哈希函数映射的快速查找算法。该算法的原名叫：“Space/time trade-offs in hash coding with allowable errors”，即一种允许一定容错率的哈希算法，因为在实际应用中经常有这样的情况：普通hash算法相对高额的空间消耗承受不住过大的数据，而实际上对询问的正确性要求又不大。在这种情况下Bloom Filter的时空优越性就体现出来了。 为了说明Bloom…