① python如何图像识别
Python图片文本识别使用的工具是PIL和pytesser。因为他们使用到很多的python库文件，为了避免一个个工具的安装，建议使用pythonxy
pytesser是OCR开源项目的一个模块，在Python中导入这个模块即可将图片中的文字转换成文本。pytesser调用了tesseract。当在Python中调用pytesser模块时，pytesser又用tesseract识别图片中的文字。pytesser的使用步骤如下：
首先，安装Python2.7版本，这个版本比较稳定，建议使用这个版本。
其次，安装pythoncv。
然后，安装PIL工具，pytesser的使用需要PIL库的支持。
接着下载pytesser
最后，将pytesser解压，这个是免安装的，可以将解压后的文件cut到Python安装目录的Lib\site-packages下直接使用，比如我的安装目录是：C:\Python27\Lib\site-packages，同时把这个目录添加到环境变量之中。
完成以上步骤之后，就可以编写图片文本识别的Python脚本了。参考脚本如下：
from pytesser import *
import ImageEnhance
image = Image.open('D:\\workspace\\python\\5.png')
#使用ImageEnhance可以增强图片的识别率
enhancer = ImageEnhance.Contrast(image)
image_enhancer = enhancer.enhance(4)
print image_to_string(image_enhancer)
tesseract是谷歌的一个对图片进行识别的开源框架，免费使用，现在已经支持中文，而且识别率非常高，这里简要来个helloworld级别的认识
下载之后进行安装，不再演示。
在tesseract目录下，有个tesseract.exe文件，主要调用这个执行文件，用cmd运行到这个目录下，在这个目录下同时放置一张需要识别的图片，这里是123.jpg
然后运行:tesseract 123.jpg result
会把123.jpg自动识别并转换为txt文件到result.txt
但是此时中文识别不好
然后找到tessdata目录，把eng.traineddata替换为chi_sim.traineddata,并且把chi_sim.traineddata重命名为eng.traineddata
ok,现在中文识别基本达到90%以上了
② 如何使用局部敏感哈希函数
在检索中，需要解决的问题是给定一个查询样本query，返回与此query相似的样本，线性搜索耗时耗力，不能承担此等重任，要想快速找到结果，必须有一种方法可以将搜索空间控制到一个可以接受的范围，哈希在检索中就是承担这样的任务，因而，这些哈希方法一般都是局部敏感（Locality-sensitive）的，即样本越相似，经过哈希后的值越有可能一样。所以，本文中介绍的技术都是局部敏感哈希（Locality Sensitive Hashing，LSH），与hashmap、hashtable等数据结构中的哈希函数有所不同。
③ python之哈希算法
哈希(Hash)算法：`hash（object）`
哈希算法将一个不定长的输入，通过散列函数变换成一个定长的输出，即散列值。是一种信息摘要算法。对象的hash值比原对象拥有更低的内存复杂度。
它不同于加密。哈希（hash）是将目标文本转换成具有相同长度的，不可逆的杂凑字符串，而加密则是将文本转换为具有相同长度的，可逆的密文。
哈希（hash）算法是不可逆的，只能由输入产生输出，不能由输出产生输入。而加密则是可逆的。即可以从输入产生输出，也可以反过来从输出推出输入。
对于hash算法，不同的数据应该生成不同的哈希值。如果两个不同的数据经过Hash函数计算得到的Hash值一样。就称为哈希碰撞（collision）。哈希碰撞无法被完全避免。只能降低发生概率。
好的hash函数会导致最少的hash碰撞。
*
可哈希性（hashable）：
可哈希的数据类型为不可变的数据结构（如字符串srt，元组tuple，对象集objects等）。这种数据被称为可哈希性。
不可哈希性：
不可哈希的数据类型，为可变的数据结构（如字典dict，列表list和集合set等）。
如果对可变的对象进行哈希处理，则每次对象更新时，都需要更新哈希表。这样我们则需要将对象移至不同的数据集，这种操作会使花费过大。
因此设定不能对可变的对象进行hash处理。
**
**
Python3.x添加了hash算法的随机性，以提高安全性，因此对于每个新的python调用，同样的数据源生成的结果都将不同。
哈希方法有（MD5, SHA1, SHA256与SHA512等）。常用的有SH256与SHA512。MD5与SHA1不再常用。
- MDH5 (不常用)
- SHA1 (不常用)
- SHA256 (常用)
- SHA512 (常用)
一种局部敏感的hash算法，它产生的签名在一定程度上可以表征原内容的相似度。
> 可以被用来比较文本的相似度。
安装simhash：
Pip3 install simhash
感知哈希算法（perceptual Hash Algorithm）。用于检测图像和视频的差异。
安装Imagehash:
pip3 install Imagehash
比较下面两张图片的Imagehash值
可以看到两张图片的hash值非常相似。相似的图片可以生成相似的哈希值是Imagehash的特点。
④ 如何理解哈希算法（局部敏感哈希）中的投影向量以及哈希函数中的截距
不一定，这要视变量的变化速度而定，例如x趋于0时，x、x^2都是趋于0的数，而1/x、1/x^2都是趋于无限大的数，但limx*(1/x)=1，lim(x^2)*(1/x)=limx=0，limx*(1/x^2)=lim1/x=∞。因此一个趋于0的数和一个趋于无穷大的数的乘积可能趋于0，可能趋于无穷大，也可能趋于非零常数。其实这就是极限理论这所谓的0*∞型未定式，它可以转化为0*(1/0)=0/0型未定式，从而通过比较0/0型未定式中分子分母无穷小的阶，来确定结果是以上三种中的哪一种。
⑤ 文本相似度之Sim_hash算法
本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。
最近项目有用到Sim_hash，做个简单记录。
Sim_hash是Google用来处理大量文本去重的算法，属于 局部敏感哈希（Locality Sensitive Hashing，LSH） ，LSH哈希能够使两篇只有小部分改动的文章编码后哈希值具有相似性，既可用于去重，也可用于计算相似度。对于只有小部分改动的两篇文章，在计算他们之间的相似度时，如果采用md5，两篇文章的md5编码值差异会非常大。但使用局部敏感哈希可以使相似的文章哈希编码后聚集在一起，删除符合阈值条件的文章，达到去重的效果。
一、算法流程
1）分词：对文本进行去停用词、分词，提取n个关键词和关键词的tf-idf权重来表征文章。如下图分词及权重。
2）关键词哈希编码：每个关键词通过hash函数生成固定位数二进制哈希。
3）权重编码：二进制编码中0调整为-1变为权重向量，与权重相乘。
4）权重编码叠加：将所有权重编码纵向求和，得到最终的文章权重。
5）二值化：按正数为1负数为0的规则将文章权重二值化。
6）汉明距离相似度：排除汉明距离小于阈值的文章，一般设置为3。汉明距离计算速度快，思路简单，原理是计算两个二值化编码相同位置处的不同值的个数。
二、Sim_hash整体流程
需求： 来了一个相似文章推荐需求，需要推荐出与文章内容相似的数据，但又不能完全相似。利用目前库中已有的POI标签和POI权重数据，结合simhash算法，计算出每个文章poi_sim_hash，计算距离
数据： 线上拉取10W文章数据
测试结果： 下图为随机抽样的测试结果（第一条为查询数据），基本 符合预期效果 。前期还可以使用 类目和发布时间 进行前置过滤，减少数据量。
⑥ LSH（局部敏感哈希）算法
参考/摘自：
minHash(最小哈希)和LSH(局部敏感哈希)
大规模数据的相似度计算：LSH算法
LSH（locality sensitivity Hashing，局部敏感性哈希）算法是一种海量数据中进行相似性搜索的算法。
在传统的基于用户或基于物品的协同推荐算法中，一个常见的步骤是计算user-user之间的相似度或者item之间的相似度，计算量为O(n**2)在用户或者物品较少的时候，这些计算量是可以接受的，但是随着用户或者物品的增大，计算量会变得异常大，即便是有大规模计算集群也变得难以维持。因此我们需要提升计算效率。
Min Hashing能够对高维稀疏数据进行压缩，从而提升计算效率。继续以上面推荐中的例子，来进行说明，假设下面的表格表示4个用户分别对5个商品的购买情况：
利用jaccard相似度可以计算各个用户之间的相似度，如:
jaccard(u1, u4) = (i4+i5)/(i3+i4+i5) = 2/3
虽然上面的计算非常简单，但是随着物品以及用户达到了千万或以上的量级，计算量依然是非常庞大的。现在，我们将使用Min Hashing 来对数据进行降维。
为了得到“最小哈希值”，我们需要先对行进行一个扰动（或者称为permutation，打乱），随机交换行数。如下图：
在交换完行数之后，变可以得到每一列（这里就是每一个user）的最小哈希值了，以上图为例：
每一次交换行数后都能得到一个最小哈希值，交换次数一般远小于原始矩阵行数，因此可以对数据维度进行压缩。
在经过打乱后的两个集合（这里即两个用户）计算得到的最小哈希值相等的概率等于这两个集合的jaccard相似度。简单推导如下。
假设只考虑两个用户，那么这两个用户的行有下面三种类型：
假设属于X类的行有x个，属于Y类的行有y个，所以u1和u2交集的元素个数为x，并集的元素个数为x+y，所以SIM(u1, u2) = x / (x+y)。注：SIM(u1, u2)就是集合S1和S2的Jaccard相似度。
接下来计算最小哈希值h(u1) = h(u2)的概率。经过打乱后，对特征矩阵从上往下进行扫描，在碰到Y类行之前碰到X类行的概率是x/(x+y)；又因为X类中h(u1)=h(u2)，所以h(u1)=h(u2)的概率为x/(x+y)，也就是这两个集合的jaccard相似度。
在上面中每一次打乱生成一个最小哈希值，假设原来有n个物品，打乱m次，便可以得到m个最小哈希值，一般来说m《 n，以对原始矩阵进行维度压缩。这时候的最小哈希值组成的矩阵便称为最小哈希签名（signature）矩阵。
但是，在实践中我们一般不会这么做，因为对于一个巨大的矩阵，多次打乱行数也是一个计算量巨大的操作。通常我们可以使用一个针对row index的哈希函数来达到permutation的效果，虽然可能会产生哈希碰撞的情况，但是只要碰撞的概率不大，对结果的影响就会很小。具体做法如下：
（1）取m个这针对row index的哈希函数，h1到h m ；
（2）记Sig(i, v)为v列原向量在第i个哈希函数下的min hash值，初始值可设置为inf；
（3）对于原矩阵的每一行r：
如下图：
具体的每一步是如何填充的可以参考 https://blog.csdn.net/liujan511536/article/details/47729721 中的说明。
如上，我们使用了两个哈希函数，因此压缩后的哈希签名矩阵为两行。此时可以利用新的矩阵来计算Jaccard相似度：
Sim(u1, u4) = 2/2 = 1。
通过上面的Min Hashing可以将一个大矩阵通过哈希映射压缩成一个小矩阵，同时保持各列之间的相似性，从而降低了复杂度。但是，虽然我们降低了特征复杂度，如果用户非常多的话，我们的计算量依然是非常大的（O(n**2)），如果我们能先粗略地将用户分桶，将可能相似的用户以较大概率分到同一个桶内，这样每一个用户的“备选相似用户集”就会相对较小，降低寻找其相似用户的计算复杂度，LSH就是这样一个近似算法。
LSH的具体做法是在Min Hashing所得的signature向量的基础上，将每一个向量分为几段，称之为band（即每个band包含多行），如下图所示：
每个signature向量被分成了4段，图上仅展示了各向量第一段的数值。其基本想法是：如果两个向量的其中一个或多个band相同，那么这两个向量就可能相似度较高；相同的band数越多，其相似度高的可能性越大。所以LSH的做法就是对各个用户的signature向量在每一个band上分别进行哈希分桶来计算相似度，在任意一个band上被分到同一个桶内的用户就互为candidate相似用户，这样只需要计算所有candidate用户的相似度就可以找到每个用户的相似用户群了。
这样一种基于概率的用户分桶方法当然会有漏网之鱼，我们希望下面两种情况的用户越少越好：
实际操作中我们可以对每一个band使用同一个哈希函数，但是哈希分桶id需要每个band不一样，具体说来，假设向量 A, B均被分为3个band：[A1, A2, A3]和[B1, B2, B3]。则向量A、B的每个band都被hash到一个桶类，相同行band如果被分到一个桶内便说明A、B是相似的，互为candidate相似用户。
下面我们对signature向量的分桶概率作一些数值上的分析，以便针对具体应用确定相应的向量分段参数。假设我们将signature向量分为b个band，每个band的大小（也就是band内包含的行数）为r。假设两个用户向量之间的Jaccard相似度为s，前面我们知道signature向量的任意一行相同的概率等于Jaccard相似度s，我们可以按照以下步骤计算两个用户成为candidate用户的概率：
这个概率在r和b取不同值时总是一个S形的曲线，例如当b=100，r=4时，1-(1-s 4 ) 100 的曲线如下图所示：
这个曲线的特点在于，当s超过一个阈值之后，两个用户成为candidate用户的概率会迅速增加并接近于1。这个阈值，也就是概率变化最陡的地方，近似为t=(1/b) 1/r 。实际应用当中，我们需要首先决定 s>s min 为多少才可以视为相似用户，以及signature向量的长度来确定这里的b和r，并考虑：
（1）如果想要尽可能少的出现false negative，就需要选择b和r使得概率变化最陡的地方小于 s min 。例如假设我们认为s在0.5以上才属于相似用户，那么我们就要选择b和r使得S曲线的最陡处小于0.5（上图所示的b=100，r=4就是一个较好的选择），这样的话，s在0.5以上的“真正”的相似用户就会以很大的概率成为candidate用户。
（2）如果想要保证计算速度较快，并且尽可能少出现false positive，那么最好选择b和r使得概率变化最陡的地方较大，例如下图所示的b=20，r=6。这样的话，s较小的两个用户就很难成为candidate用户，但同时也会有一些“潜在”的相似用户不会被划分到同一个桶内。（candidate用户是一部分质量较高的相似用户）。
这样针对具体应用，经过前期的数据探索之后，我们便可以为LSH算法设置具体的参数，使得在保证精度的情况下，提升计算效率。当然这里只是说明了Jaccard相似度下的LSH算法，对于其他的相似度度量比如余弦相似度等，可参考《mining of massive datasets》中chapter 3：finding similar items.
参考：
http://www.360doc.com/content/18/0927/15/39821762_790129444.shtml
⑦ 字符串距离
又称Levenshtein距离，是编辑距离（edit distance）的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
一种局部敏感hash，它也是Google公司进行海量网页去重使用的主要算法。
传统的Hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上仅相当于伪随机数产生算法。传统的hash算法产生的两个签名，如果原始内容在一定概率下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别很大。所以传统的Hash是无法在签名的维度上来衡量原内容的相似度，而SimHash本身属于一种局部敏感哈希算法，它产生的hash签名在一定程度上可以表征原内容的相似度。
我们主要解决的是文本相似度计算，要比较的是两个文章是否相似，当然我们降维生成了hash签名也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hash却不行。
流程
在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。
例如：
1011101与1001001之间的汉明距离是2
xlturing/simhashJava