① 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