[推薦算法]基于JACCARD推薦（0,1推薦）

基于JACCARD推薦（0,1推薦） 1、什麼是jaccard？

    傑卡德相似系數(Jaccard similarity coefficient)，也稱傑卡德指數(Jaccard Index)，是用來衡量 兩個集合相似度的一種名額。 Jaccard相似指數用來度量兩個集合之間的相似性，它被定義為兩個集合交集的元素個數除以并集的元素個數。

    在我們項目中對于新聞的推薦，每個使用者對新聞的浏覽可以看做是一個集合。這樣就可以使用jaccard算法實作使用者之間的相似度計算；     公式如下：  

給定兩個n維二進制向量A、B，A、B的每一維都隻能是0或者1，利用Jaccard相似系數來計算二者的相似性：

1）  

代表向量A與向量B都是0的次元個數；

2）  

代表向量A是0而向量B是1的次元個數；

3）  

代表向量A是1而向量B是0的次元個數；

4 )    

  代表向量A和向量B都是1的次元個數。

n維向量的每一維都會落入這4類中的某一類，是以：

（目前我們的推薦隻涉及到二維）

則Jaccard相似系數為：

    在二維裡面其實就是 AB的一個交集數量/整體元素數量 ；

2、jaccard舉例？

    比如我們的使用者對新聞的一個浏覽資料如下：    

ABCD 代表的四個使用者 ；1,2,3,4 代表的是四個新聞；1代表看過該新聞，0代表沒有看過該新聞；下面簡單計算一下相似度：

使用者A 和 使用者B 的相似度計算：  M11 就是1   M01+M10+M11 = 4  是以J（A,B） = 1/4 = 25% 使用者A 和 使用者C 的相似度計算：  M11 就是3   M01+M10+M11 = 4  是以J（A,B） = 3/4 = 75% 使用者A 和 使用者D 的相似度計算：  M11 就是2   M01+M10+M11 = 4  是以J（A,B） = 2/4 = 50%

由此可見A跟使用者的相似度排名從高到低就是   C D B ；

時間複雜度分析 1.  假設資料已經存在  A[n][m]  二維數組 n代表使用者 m代表商品    nm的值就是某個使用者是否看過某個商品  值用0,1 标示。0沒看過，1看過。 2.使用jaccard算法比較每個使用者 循環 A[n][m] ，依次比較從0到n的使用者 ； 形成數組B[n1][n2]  存放的資料代表每個使用者n1和使用者n2的相似度；   for (int i = 0; i < USERCOUNT; i++) {       for (int j = 0; j < USERCOUNT; j++) {            if (i == j) {//自己跟自己的相似度 1                 similarityMatrix[i][j] = 1;        } else  {                 similarityMatrix[i][j] = computeSimilarity(preference[i], preference[j]);        }             }               時間複雜度為O2

3.進行評分預測

A 周遊使用者   for                          B1相似度排序（array）                for  ( int  j = 0; j < temp.length; j++) {                 temp[j] = similarity[j];             }                             B2擷取近鄰            for (int m = temp.length - 1; m >= temp.length - KNEIGHBOUR; m--) {                 for(int j = 0; j < similarity.length; j++) {                     if (similarity[j] == temp[m] && similarity[j] != 0.0 && j!=i)                         neighborSerial.add(new Integer(j));                 }                 }  

              B3周遊商品                      C1周遊近鄰  擷取評分 時間複雜度為  O2+  O3+O3  = O2 + 2O3   最終近似為O3