基于相似度的Apriori 混合算法研究

羅 潔， 王 力

（1 貴州大學大數據與信息工程學院， 貴陽 550025； 2 畢節工業職業技術學院， 貴州 畢節 551700；3 貴州工程應用技術學院信息工程學院， 貴州 畢節 551700）

0 引 言

大數據飛速發展的時代，各種商品琳瑯滿目，用戶的需求與日俱增。 數據挖掘就是幫助人們從大量數據中找出相關的有用信息，進而加以利用。 商家就可以通過關聯規則挖掘算法得到用戶需求的相關規則，從而制定營銷策略。 目前，已有大量的學者對此進行研究。 杜永興等學者［1］通過增加判斷集，減少候選項集的產生，提出了基于荒漠草原數據多樣性關聯規則改進的Apriori 算法，減少時間運算。 何慶等學者［2］通過改進Apriori 算法對貧困戶建檔立卡數據進行挖掘。 郭凱等學者［3］提出的基于Apriori 斷面越限調整策略的改進算法，大大減少了無效規則的產生。 林陳［4］提出的基于興趣度的關聯規則算法有效地降低了運行時間。 上述關聯分析旨在改進算法，減少運行時間，未能從商家角度去分析數據結果的有效性，利用率不大。

針對基于興趣度的Apriori 算法存在主觀因素，不利于計算關聯規則的準確度。 本文旨在添加相似度的屬性，利用客觀的相似度替代主觀的興趣度，通過用戶對商品的打分，分析用戶的喜好，從而得到相似度；改進Apriori 算法得到關聯規則。 同時，對電影數據進行分析研究，在此基礎上指導商家如何安排電影上架，驗證了混合算法的有效性。

1 相關知識

1.1 Apriori 算法

Apriori 算法可通過已知的頻繁項集來構成長度更大的項集，將其稱為候選頻繁項集。 如果k項集滿足支持度大于最小支持閾值min_sup，則稱為頻繁項集LK；而候選k項集CK是指由有可能成為頻繁k項集的項集組成的集合.具體的實現過程可以分解為2 部分：

（1）找出數據庫對象D中所有大于等于用戶指定的min_sup的頻繁項集。

（2）利用頻繁項集生成所需的關聯規則，根據用戶設定的最小可信度進行選擇，產生強關聯規則［5］。

1.2 興趣度度量

興趣度是一類新型的關聯規則度量方式的挖掘模型，是以支持度-置信度模型為基礎而提出的關聯規則度量方法。 一般的關聯規則挖掘方法常常會產生大量的關聯規則，但其中也包括許多用戶并不感興趣的規則。 興趣度恰好是通過用戶感興趣的專業知識和經驗來篩選關聯規則，挖掘最終產生的關聯規則的［6］。

興趣度可以分為以下2 類：主觀興趣度和客觀興趣度，其中客觀興趣度等同于數據驅動，主要根據數據庫中的數據以及規則或模式的形式進行定義；而主觀興趣度不僅要考慮數據，還要考慮一些人為因素的影響，屬于用戶驅動［6］。

1.3 相似度計算

在協同過濾算法當中，通過余弦相似度來計算用戶之間的相似度。 研究推得的數學公式如下：

其中，

Im，n表示用戶m，n的共同評分項目集；lm，j，ln，j表示用戶m，n分別對項目j的評分。 余弦相似度以向量夾角余弦值來度量用戶相似度，夾角越小，余弦值越大，相似度也就越高。

2 改進Apriori 算法

2.1 算法過程

如何有效地挖掘關聯規則是基于相似度的混合算法的重要任務。 過程主要包括：數據抽取、挖掘建模和分析結果。 基于相似度的混合算法過程如圖1所示。

圖1 基于相似度的混合算法過程Fig. 1 A hybrid algorithm process based on similarity

用戶的打分或喜好是主觀行為，但是集中相似用戶的打分行為或共同喜好，就較為客觀，能使目標群體更精確，得出的結論更為直接、準確，從經濟的角度考慮也能在更大程度上減少商家運營成本和時間，有利于商家對一類群體進行分析及做出決策。 再通過Apriori 關聯規則算法對相似用戶的行為進行數據挖掘，就能得出更加有效的數據規則結果。

2.2 算法步驟

基于相似度的Apriori 混合算法步驟具體如下。

輸入數據集、評分數據集

輸出關聯規則

步驟1初始化數據，并對評分數據進行歸一化處理。

步驟2找出所有數據集與用戶m有交集用戶，用式（1） 對這些用戶循環計算與用戶m的相似度。

步驟3根據相似度得到相似度大于等于0.6的列表數據。

步驟4對得到的列表數據進行數據預處理。

步驟5利用Apriori 算法對數據推導出關聯規則。

3 實驗結果與分析

3.1 算法結果分析

實驗環境為：Inter（R） Core（TM） i5-2410M CPU ＠ 2. 30 GHz； 8 GB 內存； 操作系統是Winsdow10 64 位，利用Jupyter Notebook 進行編程。實驗數據集為MovieLens（https：//grouplens. org/datasets/movielens/）提供的6 040 位用戶對3 925 部電影、共1 000 209 條評論信息。 從中抽取500 位用戶對50 部電影、共5 000 條相關評論信息進行測試。 電影的評分范圍為［1，5］區間所有整數值，用戶對電影的喜好程度由1 ～5 逐漸遞增，數值越大，就表明越喜歡。 抽取的每位用戶對10 部電影進行評分，實驗數據集包含了用戶信息、評分信息和電影信息。 可以根據基于相似度的Apriori 混合算法針對某一類人進行有效的關聯規則數據分析，得出的結論更準確。 實驗度量指標選用了平均支持度和平均置信度。 數學公式具體如下：

（1）實驗1。 為2 種算法在最小支持度為0.06，最小置信度為0.75，不同用戶數量條件下平均支持度、平均置信度、關聯規則個數、頻繁項集個數對比結果。

2 種算法在不同用戶數量下的比較結果見表1。從表1 中看出隨著用戶數量的增加，Apriori 算法的平均支持度、平均置信度和關聯規則個數在下降；但基于相似度的Apriori 混合算法的平均支持度卻在上升。

表1 2 種算法在不同用戶數量下的比較Tab. 1 Comparison of the two algorithms with different number of users

（2）實驗2。 為2 種算法在最小置信度為0.75，用戶數量為500，不同最小支持度條件下平均支持度、平均置信度、關聯規則個數、頻繁項集個數的對比結果。

2 種算法在不同支持度下的比較結果見表2。從表2 中看出隨著最小置信度的增加，原算法的平均支持度、平均置信度、關聯規則個數、頻繁項集個數都在下降，而改進算法的平均支持度卻在上升。

表2 2 種算法在不同支持度下的比較Tab. 2 Comparison of the two algorithms under different supports

3.2 改進算法實例解析

設置最小支持度0.6，最小置信度0.8。 關聯規則結果見表3。 實例分析如下：

表3 關聯規則結果Tab. 3 Association rule results

（1）userid為100 的用戶是位男性，年齡35 歲，職業是技術人員；從500 位用戶中查找與userid為100 相似的用戶，其中相似度為0.6 以上的有97 位用戶；這97 位用戶中25 位為女性，67 位為男性；年齡段為18～56 歲，均為成年人；職業為教育行業、技術人員、大學生等有文化人員。

（2）movieid為39 的電影類型為動作/犯罪/戲劇，movieid為32 的電影類型為神秘/科幻/驚悚片，movieid為11 的電影類型為喜劇/戲劇/浪漫，movieid為21 的電影類型為喜劇/犯罪/驚悚片，movieid為34 的電影類型犯罪劇。

（3）由表3 可推出結論：接受過高等文化教育的成年男性，喜歡看動作/犯罪/喜劇/浪漫/神秘/科幻/驚悚片/戲劇的大多都會看犯罪劇。

建議：電影院或是電影公司可以針對此類人群，有計劃地去拍攝或是播放電影。

4 結束語

本文提出了一種基于相似度的Apriori 混合算法，在Apriori 算法的基礎上，添加了相似度，有針對性地對某一類人群進行關聯規則挖掘。 通過協同過濾算法中的相似度度量找到相似用戶，再對相似用戶進行關聯規則挖掘，把相似度和Apriori 算法結合起來得到更準確的關聯規則，有助于商家更好地進行用戶分析及推薦。 實驗結果得出改進算法平均置信度、平均支持度分別比原算法提高13%、25%，表明改進算法關聯規則結果更準確。