本文學習如何用親和性分析方法找出在什么情況下兩個對象經常一起出現。通俗來講，這也 叫“購物籃分析”，因為曾有人用它找出哪些商品經常一起出售。 前一篇文章關注的對象為球隊，并用特征描述球隊。本文所用到的電影評分數據有所不同，我們 所關注的對象（電影）埋在數據中。本章數據挖掘任務的目標是找出對象同時出現的情況，也就 是尋找用戶同時喜歡幾部電影的情況。 本文主要涉及以下幾個概念。 ? 親和性分析 ? 用 Apriori 算法挖掘關聯特征 ? 電影推薦 ? 數據稀疏問題

---

一 親和性分析

親和性分析用來找出兩個對象共同出現的情況。而前文，我們關注的是同種對象之間的相似度。親和性分析所用的數據通常為類似于交易信息的數據。從直觀上來看，這些數據就像是商店的交易數據—— 從中能看出哪些商品是顧客一起購買的。 然而，親和性分析方法的應用場景有很多，比如： ? 欺詐檢測 ? 顧客區分 ? 軟件優化 ? 產品推薦 親和性分析比分類更具探索性，因為通常我們無法拿到像在很多分類任務中所用的那樣完整 的數據集。例如，在電影推薦任務中，我們拿到的是不同用戶對不同電影的評價。但是，每個用 戶不可能評價過所有電影，這就給親和性分析帶來一個不容忽視的大難題。如果用戶沒有評價過 一部電影，是因為他們不喜歡這部電影（據此就不推薦給他們），還是因為他們出于別的原因還 沒有評價？ 本文不對上述問題做出解答，但是我們要思考數據集中類似這樣的潛在問題該怎么解決。這 些思考有助于提升推薦算法的準確性。

---

二 親和性分析算法

基礎的親和性分析算法，嘗試了所有可能的規則組合，計算了每條規則的置信度和支持度，并根據這兩個標準進行排序，選取最佳規則。 然而，這個方法效率不高。即使是再不起眼的小賣鋪出售的商品也達上百種之多，網店更是有成千上萬種 商品（甚至幾百萬種！）。如果規則生成方法 過于簡單，計算這些規則所需要的時間復雜度將呈指數級增長。隨著商品數量的增加，計算所有規則所需的時間增長得很快。 。數據集有 5 個特征，可能的規則就有 31 條；有 10 個特征，可能的規則就有1023 條；僅僅有 100 個特征，規則數就能達到 30 位數字。即使計算能力大幅提升也未必能趕上在線商品的增長速度。因此，與其跟計算機過不去，不如尋找更加聰明的算法。 Apriori 算法可以說是經典的親和性分析算法。它只從數據集中頻繁出現的商品中選取共同出現的商品組成頻繁項集 （ frequent itemset ），避免了上述復雜度呈指數級增長的問題。一旦找到頻繁項集，生成關聯規則就很容易了。 Apriori 算法背后的原理簡潔卻不失巧妙。首先，確保了規則在數據集中有足夠的 支持度 。 Apriori算法的一個重要參數就是最小支持度。比如，要生成包含商品 A 、 B 的頻繁項集（ A, B ），要求支持度至少為30 ，那么 A 和 B 都必須至少在數據集中出現 30 次。更大的頻繁項集也要遵守該項約定，比如要生成頻繁項集（A, B, C, D ），那么子集 (A, B, C) 必須是頻繁項集（當然 D 自己也 要滿足最小支持度標準）。 生成 頻繁項集 后，將不再考慮其他可能的卻不夠頻繁的項集（這樣的集合有很多），從而大 大減少測試新規則所需的時間。 其他親和性分析算法有 Eclat 和 頻繁項集挖掘算法 （ FP-growth ）。從數據挖掘角度看，這些 算法比起基礎的 Apriori 算法有很多改進，性能也有進一步提升。接下來，先來看一下最基礎的 Apriori 算法。

---

三 選擇參數

挖掘親和性分析所用的關聯規則之前，我們先用Apriori算法生成頻繁項集。接著，通過檢測頻繁項集中前提和結論的組合，生成關聯規則（例如，如果用戶喜歡電影X，那么他很可能喜歡電影Y）。

第一個階段，需要為 Apriori 算法指定一個項集要成為頻繁項集所需的最小支持度。任何小于最小支持度的項集將不再考慮。如果最小支持度值過小，Apriori 算法要檢測大量的項集，會拖慢的運行速度；最小支持度值過大的話，則只有很少的頻繁項集。 找出頻繁項集后，在第二個階段，根據置信度選取關聯規則?？梢栽O定最小置信度，返回一 部分規則，或者返回所有規則，讓用戶自己選。 本文，我們設定最小置信度，只返回高于它的規則。置信度過低將會導致規則支持度高，正確率低；置信度過高，導致正確率高，但是返回的規則少。

---

四 電影推薦問題

產品推薦技術是門大生意。網店經常用它向潛在用戶推薦他們可能購買的產品。好的推薦算法能帶來更高的銷售業績。每年有幾百萬乃至幾千萬用戶進行網購，向他們推薦更多的商品，潛在收益著實可觀。 產品推薦問題被人們研究了多年，但它一直不溫不火，直到 2007 年到 2009 年間， Netflix 公司推出數據建模大賽，并設立Netflix Prize 獎項之后，才得到迅猛發展。該競賽意在尋找比 Netflix公司所使用的預測用戶為電影打分的系統更準確的解決方案。最后獲獎隊伍以比現有系統高10個百分點的優勢勝出。雖然這個改進看起來不是很大，但是Netflix 公司卻能借助它實現更精準的電影推薦服務，從而多賺上百萬美元。

---

六 獲取數據集

自打 Netflix Prize 獎項設立以來，美國明尼蘇達大學的 Grouplens 研究團隊公開了一系列用于 測試推薦算法的數據集。其中，就包括幾個大小不同的電影評分數據集，分別有 10 萬、 100 萬和 1000 萬條電影評分數據。 數據集下載地址為 http://grouplens.org/datasets/movielens/ 。本文將使用包含 100 萬條數據的 MovieLens 數據集。下載數據集，解壓到你的 Data 文件夾。啟動 IPython Notebook 筆記本，輸入以 下代碼。 import os import pandas as pd data_folder = os.path.join(os.path.expanduser("~"), "Data", "ml-100k") ratings_filename = os.path.join(data_folder, "u.data") 確保 ratings_filename 指向解壓后得到的文件夾中的 u.data 文件。

---

七 用?pandas 加載數據

MovieLens數據集非常規整，但是有幾點跟pandas.read_csv方法的默認設置有出入，所以要調整參數設置。第一個問題是數據集每行的幾個數據之間用制表符而不是逗號分隔。其次，沒有表頭，這表示數據集的第一行就是數據部分，我們需要手動為各列添加名稱。

加載數據集時，把分隔符設置為制表符，告訴 pandas 不要把第一行作為表頭（ header=None ）， 設置好各列的名稱。代碼如下： all_ratings = pd.read_csv(ratings_filename, delimiter="\t", header=None, names = ["UserID", "MovieID", "Rating", "Datetime"]) 雖然本文用不到，還是稍微提一下，你可以用下面的代碼解析時間戳數據。 all_ratings["Datetime"] = pd.to_datetime(all_ratings['Datetime'], unit='s') 運行下面的代碼，看一下前五條記錄。 all_ratings[:5] 輸出結果如下

---

?八?稀疏數據格式

這是一個稀疏數據集，我們可以將每一行想象成巨大特征矩陣的一個格子，在這個矩陣中，每一行表示一個用戶，每一列為一部電影。第一列為每一個用戶給第一部電影打的分數，第二列為每一個用戶給第二部電影打的分數，以此類推。

數據集中有 1000 名用戶和 1700 部電影，這就意味著整個矩陣很大。將矩陣讀到內存中及在它 基礎上進行計算可能存在難度。然而，這個矩陣的很多格子都是空的，也就是對大部分用戶來說， 他們只給少數幾部電影打過分。比如用戶 #213 沒有為電影 #675 打過分，大部分用戶沒有為大部分 電影打過分。 用上述圖表中的格式也能表示矩陣，且更為緊湊。序號為 0 的那一行表示，用戶 #196 在 1997 年 12 月 4 日為電影 #242 打了 3 分（滿分是 5 分）。 任何沒有出現在數據集中的用戶和電影組合表示它們實際上是不存在的。這比起在內存中保 存大量的 0 ，節省了很多空間。這種格式叫作 稀疏矩陣 （ sparse matrix ）。根據經驗來說，如果數 據集中 60% 或以上的數據為 0 ，就應該考慮使用稀疏矩陣，從而節省不少空間。 在對稀疏矩陣進行計算時，我們關注的通常不是那些不存在的數據，不會去比較眾多的 0 值， 相反我們關注的是現有數據，并對它們進行比較。

---

九 Apriori 算法的實現

本章數據挖掘的目標是生成如下形式的規則： 如果用戶喜歡某些電影，那么他們也會喜歡這 部電影 。作為對上述規則的擴展，我們還將討論喜歡某幾部電影的用戶，是否喜歡另一部電影。 要解決以上問題，首先要確定用戶是不是喜歡某一部電影。為此創建新特征 Favorable ，若 用戶喜歡該電影，值為 True 。 all_ratings["Favorable"] = all_ratings["Rating"] > 3 我們在數據集中看一下這個新特征。 all_ratings[10:15]

?從數據集中選取一部分數據用作訓練集，這能有效減少搜索空間，提升Apriori算法的速度。 我們取前200名用戶的打分數據。

ratings = all_ratings[all_ratings['UserID'].isin(range(200))] 接下來，新建一個數據集，只包括用戶喜歡某部電影的數據行。 favorable_ratings = ratings[ratings["Favorable"]] 在生成項集時，需要搜索用戶喜歡的電影。因此，接下來，我們需要知道每個用戶各喜歡哪 些電影，按照 User ID 進行分組，并遍歷每個用戶看過的每一部電影。 favorable_reviews_by_users = dict((k, frozenset(v.values)) for k, v in favorable_ratings groupby("UserID")["MovieID"]) 上面的代碼把 v.values 存儲為 frozenset，便于快速判斷用戶是否為某部電影打過分。對于這種操作，集合比列表速度快。 最后，創建一個數據框，以便了解每部電影的影迷數量。 num_favorable_by_movie = ratings[["MovieID", "Favorable"]]. groupby("MovieID").sum() 用以下代碼查看最受歡迎的五部電影。 num_favorable_by_movie.sort("Favorable", ascending=False)[:5] 輸出結果如下：

---

十 Apriori 算法

Apriori 算法是親和性分析的一部分，專門用于查找數據集中的頻繁項集?；玖鞒淌菑那耙徊秸业降念l繁項集中找到新的備選集合，接著檢測備選集合的頻繁程度是否夠高，然后算法像下面這樣進行迭代。 (1) 把各項目放到只包含自己的項集中，生成最初的頻繁項集。只使用達到最小支持度的項目。 (2) 查找現有頻繁項集的超集，發現新的頻繁項集，并用其生成新的備選項集。 (3) 測試新生成的備選項集的頻繁程度，如果不夠頻繁，則舍棄。如果沒有新的頻繁項集， 就跳到最后一步。 (4) 存儲新發現的頻繁項集，跳到步驟 (2) 。 (5) 返回發現的所有頻繁項集。 整個過程表示如下。

---

十一 實現

Apriori算法第一次迭代時，新發現的項集長度為2，它們是步驟(1)中創建的項集的超集。第二次迭代（經過步驟(4)）中，新發現的項集長度為3。這有助于我們快速識別步驟(2)所需的項集。

我們把發現的頻繁項集保存到以項集長度為鍵的字典中，便于根據長度查找，這樣就可以找到最新發現的頻繁項集。下面的代碼初始化一個字典。

frequent_itemsets = {} 我們還需要確定項集要成為頻繁項集所需的最小支持度。這個值需要根據數據集的具體情況 來設定，可自行嘗試其他值，建議每次只改動 10 個百分點，即使這樣你可能也會發現算法運行時 間變動很大！下面，設置最小支持度。 min_support = 50 我們先來實現 Apriori 算法的第一步，為每一部電影生成只包含它自己的項集，檢測它是否夠 頻繁。電影編號使用 frozenset ，后面要用到集合操作。此外，它們也可以用作字典的鍵（普通 集合不可以）。代碼如下： frequent_itemsets[1] = dict((frozenset((movie_id,)), row["Favorable"]) for movie_id, row in num_favorable_ by_movie.iterrows() if row["Favorable"] > min_support) 接著，用一個函數來實現步驟 (2) 和 (3) ，它接收新發現的頻繁項集，創建超集，檢測頻繁程 度。下面為函數聲明及字典初始化代碼。 from collections import defaultdict def find_frequent_itemsets(favorable_reviews_by_users, k_1_itemsets, min_support): counts = defaultdict(int)

經驗告訴我們，要盡量減少遍歷數據的次數，所以每次調用函數時，再遍歷數據。這樣做效果不是很明顯（因為數據集相對較小），但是數據集更大的情況下，就很有必要。我們來遍歷所有用戶和他們的打分數據。

for user, reviews in favorable_reviews_by_users.items(): 接著，遍歷前面找出的項集，判斷它們是否是當前評分項集的子集。如果是，表明用戶已經 為子集中的電影打過分。代碼如下： for itemset in k_1_itemsets: if itemset.issubset(reviews): 接下來，遍歷用戶打過分卻沒有出現在項集里的電影，用它生成超集，更新該項集的計數。 代碼如下： for other_reviewed_movie in reviews - itemset: current_superset = itemset | frozenset((other_ reviewed_movie,)) counts[current_superset] += 1 函數最后檢測達到支持度要求的項集，看它的頻繁程度夠不夠，并返回其中的頻繁項集。 return dict([(itemset, frequency) for itemset, frequency in counts.items() if frequency >= min_support]) 創建循環，運行 Apriori 算法，存儲算法運行過程中發現的新項集。循環體中， k 表示即將發 現的頻繁項集的長度，用鍵 k ? 1 可以從 frequent_itemsets 字典中獲取剛發現的頻繁項集。新 發現的頻繁項集以長度為鍵，將其保存到字典中。代碼如下： for k in range(2, 20): cur_frequent_itemsets = find_frequent_itemsets(favorable_reviews_by_users, frequent_itemsets[k-1], min_support) frequent_itemsets[k] = cur_frequent_itemsets 如果在上述循環中沒能找到任何新的頻繁項集，就跳出循環（輸出信息，告知我們沒能找到 長度為 k 的頻繁項集） if len(cur_frequent_itemsets) == 0: print("Did not find any frequent itemsets of length {}". format(k)) sys.stdout.flush() break 如果確實找到了頻繁項集，我們也讓程序輸出信息，告知我們它會再次運行。因為算法運行 時間很長，所以每隔一段時間輸出一下狀態是很有必要的！代碼如下： else: print("I found {} frequent itemsets of length {}".format(len(cur_frequent_itemsets), k)) sys.stdout.flush() 最后，循環結束，我們對只有一個元素的項集不再感興趣 —— 它們對生成關聯規則沒有用 處 —— 生成關聯規則至少需要兩個項目。刪除長度為 1 的項集。代碼如下： del frequent_itemsets[1] 上面這些代碼要好幾分鐘才能運行完，老機器需要的時間更長。如果你在本地運行代碼有問 題，可以考慮使用云主機提升速度。 上述代碼返回了不同長度的 1718 個頻繁項集。你也許會發現隨著項集長度的增加，項集數隨 著可用規則的增加而增長一段時間后才開始變少，減少是因為項集達不到最低支持度要求。項集 的減少是 Apriori 算法的優點之一。如果我們搜索所有可能的項集（不只是頻繁項集的超集），判 斷多余項集的頻繁程度需要成千上萬次查詢。

---

十二 抽取關聯規則

Apriori算法結束后，我們得到了一系列頻繁項集，這還不算是真正意義上的關聯規則，但是很接近了。頻繁項集是一組達到最小支持度的項目，而關聯規則由前提和結論組成。 我們可以從頻繁項集中抽取出關聯規則，把其中幾部電影作為前提，另一部電影作為結論組成如下形式的規則：

如果用戶喜歡前提中的所有電影，那么他們也會喜歡結論中的電影。

每一個項集都可用這種方式生成一條規則。 下面的代碼通過遍歷不同長度的頻繁項集，為每個項集生成規則。 candidate_rules = [] for itemset_length, itemset_counts in frequent_itemsets.items(): for itemset in itemset_counts.keys(): 然后，遍歷項集中的每一部電影，把它作為結論。項集中的其他電影作為前提，用前提和結 論組成備選規則。 for conclusion in itemset: premise = itemset - set((conclusion,)) candidate_rules.append((premise, conclusion)) 這樣就能得到大量備選規則。通過以下代碼查看前五條規則。 print(candidate_rules[:5]) 輸出結果如下： [(frozenset({79}), 258), (frozenset({258}), 79), (frozenset({50}), 64), (frozenset({64}), 50), (frozenset({127}), 181)] 在上述這些 規則 中，第一部分（ frozenset ）是作為規則前提的電影編號，后面的數字表示 作為結論的電影編號。第一組數據表示如果用戶喜歡電影 79 ，他很可能喜歡電影 258 。 接下來，計算每條規則的置信度，計算方法跟第 1 章類似，只不過要根據這里新的數據格式 做些改動。 我們需要先創建兩個字典，用來存儲規則應驗（ 正例 ）和規則不適用（ 反例 ）的次數。代碼 如下： correct_counts = defaultdict(int) incorrect_counts = defaultdict(int) 遍歷所有用戶及其喜歡的電影數據，在這個過程中遍歷每條關聯規則。 for user, reviews in favorable_reviews_by_users.items(): for candidate_rule in candidate_rules: premise, conclusion = candidate_rule

測試每條規則的前提對用戶是否適用。換句話說，用戶是否喜歡前提中的所有電影。代碼如下：

if premise.issubset(reviews): 如果前提符合，看一下用戶是否喜歡結論中的電影。如果是的話，規則適用，反之，規則不 適用。 if premise.issubset(reviews): if conclusion in reviews: correct_counts[candidate_rule] += 1 else: incorrect_counts[candidate_rule] += 1 用規則應驗的次數除以前提條件出現的總次數，計算每條規則的置信度。 rule_confidence = {candidate_rule: correct_counts[candidate_rule] / float(correct_counts[candidate_rule] + incorrect_counts[candidate_rule]) for candidate_rule in candidate_rules} 對置信度字典進行排序后，輸出置信度最高的前五條規則。 結果如下： Rule #1 Rule: If a person recommends frozenset({64, 56, 98, 50, 7}) they will also recommend 174 - Confidence: 1.000 Rule #2 Rule: If a person recommends frozenset({98, 100, 172, 79, 50, 56}) they will also recommend 7 - Confidence: 1.000 Rule #3 Rule: If a person recommends frozenset({98, 172, 181, 174, 7}) they will also recommend 50 - Confidence: 1.000 Rule #4 Rule: If a person recommends frozenset({64, 98, 100, 7, 172, 50}) they will also recommend 174 - Confidence: 1.000 Rule #5 Rule: If a person recommends frozenset({64, 1, 7, 172, 79, 50}) they will also recommend 181 - Confidence: 1.000

輸出結果中只顯示電影編號，而沒有顯示電影名字，很不友好。我們下載的數據集中的u.items文件里存儲了電影名稱和編號（還有體裁等信息）。

用pandas從u.items文件加載電影名稱信息。關于該文件和類別的更多信息請見數據集中的 README文件。u.items文件為CSV格式，但是用豎線分隔數據。讀取時需要指定分隔符，設置表 頭和編碼格式。每一列的名稱是從README文件中找到的。

movie_name_filename = os.path.join(data_folder, "u.item") movie_name_data = pd.read_csv(movie_name_filename, delimiter="|", header=None, encoding = "mac-roman") movie_name_data.columns = ["MovieID", "Title", "Release Date", "Video Release", "IMDB", "<UNK>", "Action", "Adventure", "Animation", "Children's", "Comedy", "Crime", "Documentary", "Drama", "Fantasy", "Film-Noir", "Horror", "Musical", "Mystery", "Romance", "Sci-Fi", "Thriller", "War", "Western"] 既然電影名稱對于理解數據很重要，我們就來創建一個用電影編號獲取名稱的函數，以免去 每次都要人工查找的煩惱。函數聲明如下： def get_movie_name(movie_id): 在數據框 movie_name_data 中查找電影編號，找到后，只返回電影名稱列的數據。 title_object = movie_name_data[movie_name_data["MovieID"] == movie_id]["Title"] 我們用 title_object 的 values 屬性獲取電影名稱（不是存儲在 title_object 中的 Series 對象）。我們只對第一個值感興趣 —— 當然每個電影編號只對應一個名稱！ title = title_object.values[0] 函數最后返回電影名稱。 return title 調整之前的代碼，這樣就能在輸出的規則中顯示電影名稱。請在 IPython Notebook 筆記本文 件的新格子里輸入以下代碼。 for index in range(5): print("Rule #{0}".format(index + 1)) (premise, conclusion) = sorted_confidence[index][0] premise_names = ", ".join(get_movie_name(idx) for idx in premise) conclusion_name = get_movie_name(conclusion) print("Rule: If a person recommends {0} they will also recommend {1}".format(premise_names, conclusion_name)) print(" - Confidence: {0:.3f}".format(confidence[(premise, conclusion)])) print("") 結果清楚多了（還有些小問題，暫時先忽略）。 Rule #1 Rule: If a person recommends Shawshank Redemption, The (1994), Pulp Fiction (1994), Silence of the Lambs, The (1991), Star Wars (1977), Twelve Monkeys (1995) they will also recommend Raiders of the Lost Ark (1981) - Confidence: 1.000 Rule #2 Rule: If a person recommends Silence of the Lambs, The (1991), Fargo (1996), Empire Strikes Back, The (1980), Fugitive, The (1993), Star Wars (1977), Pulp Fiction (1994) they will also recommend Twelve Monkeys (1995) - Confidence: 1.000 Rule #3 Rule: If a person recommends Silence of the Lambs, The (1991), Empire Strikes Back, The (1980), Return of the Jedi (1983), Raiders of the Lost Ark (1981), Twelve Monkeys (1995) they will also recommend Star Wars (1977) - Confidence: 1.000 Rule #4 Rule: If a person recommends Shawshank Redemption, The (1994), Silence of the Lambs, The (1991), Fargo (1996), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Star Wars (1977) they will also recommend Raiders of the Lost Ark (1981) - Confidence: 1.000 Rule #5 Rule: If a person recommends Shawshank Redemption, The (1994), Toy Story (1995), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Fugitive, The (1993), Star Wars (1977) they will also recommend Return of the Jedi (1983) - Confidence: 1.000

---

十三 小結

本文把親和性分析用到電影推薦上，從大量電影打分數據中找到可用于電影推薦的關聯規則。整個過程分為兩大階段。首先，借助Apriori 算法尋找數據中的頻繁項集。然后，根據找到的頻繁項集，生成關聯規則。 由于數據集較大， Apriori 算法就很有必要。我們用一部分數據作為訓練集以發現關聯規則，在剩余數據——測試集上進行測試。

---

我們是Greaterwms軟件開發團隊。

項目介紹：
我們的產品是開源倉儲管理軟件，榮獲gitee最有價值開源項目獎，評選為GVP項目

產品支持多倉，波次發貨，合并揀貨，Milk-Run等業務模型。前后端分離為完全開源項目。

軟件著作權編號：2018SR517685
GitHub地址：github
Gitee地址： ? gitee
視頻教程： ? ?bilibili
Demo地址：DEMO
商務聯系：mail@56yhz.com
技術交流：GreaterWMS-01（加微信進群）

總結

以上是生活随笔為你收集整理的【实用算法教学】——Apriori算法，教你使用亲和性分析方法推荐电影的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。