基于聚類分析和Apriori算法的個(gè)性化推薦研究

劉玥波 劉田

（1.吉林建筑科技學(xué)院 吉林省長(zhǎng)春市 130114 2.啟明信息技術(shù)股份有限公司 吉林省長(zhǎng)春市 130122）

消費(fèi)購(gòu)物一直是人類生活中不可避免的一項(xiàng)活動(dòng)，隨著計(jì)算機(jī)技術(shù)與互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，越來越多的人習(xí)慣于網(wǎng)上購(gòu)物，尤其是面對(duì)特殊情況，無法實(shí)現(xiàn)線下購(gòu)物時(shí)，網(wǎng)上購(gòu)物為人們的生活帶來了更大的便利。面對(duì)網(wǎng)上海量的商品信息，用戶通常感覺無從選擇，同時(shí)虛擬的網(wǎng)絡(luò)無法讓用戶直觀地檢查產(chǎn)品的外觀和質(zhì)量。在這種情況下，用戶迫切地希望網(wǎng)上購(gòu)物系統(tǒng)能夠提供一種類似購(gòu)物助手的功能，可以根據(jù)用戶自身的興趣愛好推薦他們可能感興趣而且滿意的產(chǎn)品[1]。另一方面，海量數(shù)據(jù)、各類推薦算法與數(shù)據(jù)挖掘技術(shù)的發(fā)展，為個(gè)性化推薦提供了技術(shù)支持[2]。

1 聚類分析

聚類分析是數(shù)據(jù)挖掘的主要方法之一[3]，聚類算法分析主要是將對(duì)象的集合劃分為多個(gè)聚簇，以“物以類聚”為原理，對(duì)本身沒有類別的樣本集根據(jù)樣本之間的相似性程度分類，彼此相似的樣本被歸為一類。聚類是在事先不知道樣本類別的基礎(chǔ)上分類，屬于無監(jiān)督的學(xué)習(xí)，這一點(diǎn)與分類有本質(zhì)的區(qū)別，分類是用已知類別的樣本集來設(shè)計(jì)分類器，屬于有監(jiān)督的學(xué)習(xí)。聚類分析的目的是使同一個(gè)簇的樣本之間彼此相似，而不同簇的樣本之間足夠不相似。

1.1 K-means 聚類算法思想

1967年Mac Queen首次提出了K均值聚類算法（K-means算法），該算法已廣泛地應(yīng)用于科學(xué)研究和計(jì)算機(jī)網(wǎng)絡(luò)。聚類分析作為一種非監(jiān)督學(xué)習(xí)方法，是機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)非常重要的研究方向[4]。

該算法首先隨機(jī)選取K 個(gè)點(diǎn)，作為初始聚類中心，這也是該算法一個(gè)關(guān)鍵輸入，通過確定K 值的典型方法是依據(jù)某些先驗(yàn)知識(shí)可通過測(cè)試不同的K 值進(jìn)行探查聚簇的類型信息，從而最終選定適合的K 值。然后計(jì)算各個(gè)對(duì)象到所有聚類中心的距離，以歐式距離作為鑒定相似程度的標(biāo)準(zhǔn)，將對(duì)象歸入到離它最近的那個(gè)聚類中心所在的類，目標(biāo)函數(shù)如下所示：

其中，E 是數(shù)據(jù)庫(kù)中所有對(duì)象的平方誤差總和，x 是空間中的點(diǎn)，表示給定的數(shù)據(jù)對(duì)象，是簇ci的平均值[5]。

1.2 k-means算法描述

輸入：數(shù)據(jù)集D，聚族數(shù)k

輸出：聚簇代表集合C，聚簇成員向量m

（1）從數(shù)據(jù)集D 中隨機(jī)挑選k 個(gè)數(shù)據(jù)點(diǎn)。

（2）使用k 個(gè)數(shù)據(jù)點(diǎn)構(gòu)成初始聚簇代表集合C。

（3）將D 中的每個(gè)數(shù)據(jù)點(diǎn)重新分配至與之最近的聚簇均值。

（4）更新聚簇均值，即計(jì)算每個(gè)對(duì)象簇中的對(duì)象均值。

（5）計(jì)算目標(biāo)函數(shù)。

圖1：層次聚類結(jié)果

（6）重復(fù)（3）（4）（5），直到目標(biāo)函數(shù)收斂。

1.3 K-means 算法存在的問題

K-means 十分容易理解，也很容易實(shí)現(xiàn)，但同時(shí)也存在以下不足之處。對(duì)于離群點(diǎn)和孤立點(diǎn)敏感； k 值選擇無法確定，必須首先給出k（要生成的簇的數(shù)目），而事先并不知道給定的數(shù)據(jù)應(yīng)該被分成什么類別才是最優(yōu)的; 初始聚類中心的選擇，一旦初始值選擇的不好，可能無法得到有效的聚類結(jié)果；只能發(fā)現(xiàn)球狀簇。

2 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中一個(gè)比較重要的挖掘方法，關(guān)聯(lián)規(guī)則挖掘用于尋找給定數(shù)據(jù)集中數(shù)據(jù)項(xiàng)之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系。關(guān)聯(lián)規(guī)則揭示了數(shù)據(jù)項(xiàng)間未知、隱含的依賴關(guān)系。根據(jù)挖掘出的關(guān)聯(lián)關(guān)系，可以從一個(gè)數(shù)據(jù)對(duì)象的信息，來推斷另一個(gè)數(shù)據(jù)對(duì)象的信息。

2.1 關(guān)聯(lián)規(guī)則概念

若X、Y 均為項(xiàng)集，且X?I，Y?I，并且X ∩Y=?，則形如X →Y 的蘊(yùn)涵式即為關(guān)聯(lián)規(guī)則。其中，X 和Y 分別被稱為關(guān)聯(lián)規(guī)則的先導(dǎo)（前件）和后繼（后件）。

對(duì)于項(xiàng)集X，設(shè)定count(X)為交易集D 中包含X 的交易的數(shù)量，count(D)為事務(wù)總數(shù)，則項(xiàng)集X 的支持度為：

關(guān)聯(lián) 規(guī)則X →Y 的支 持度 為項(xiàng) 集X?Y 的 支持 度：

最小支持度是項(xiàng)集的最小支持閾值，記為minsup。支持度不小于minsup 的項(xiàng)集稱為頻繁項(xiàng)集，否則稱為非頻繁項(xiàng)集，長(zhǎng)度為k的頻繁集稱為k-頻繁集。

規(guī)則X →Y 的置信度表示D 中包含X 的事務(wù)中有多少可能性也包含Y，即表示規(guī)則確定性的強(qiáng)度，記作confidence(X →Y)

最小置信度是由用戶定義衡量置信度的一個(gè)閾值，記為minconf。

2.2 Apriori 算法

由 Rakesh Agrawal 和 Ramakrishnan Skrikant 提出的Apriori 算法是關(guān)聯(lián)規(guī)則算法中最經(jīng)典、最基礎(chǔ)、研究最廣泛的算法之一[6]。算法在挖掘的過程中，通過不斷迭代地掃描事務(wù)數(shù)據(jù)庫(kù)，掃描整個(gè)數(shù)據(jù)集，得到所有出現(xiàn)過的數(shù)據(jù)，作為候選1 項(xiàng)集C1，然后通過連接和剪枝步驟計(jì)算支持度Support（Ck）,當(dāng)Support(Ck)≥minsup 時(shí)，得到所有頻繁k 項(xiàng)集Lk。最后通過用戶給定的minconf，在每個(gè)最大頻繁項(xiàng)集中，尋找Confidence(X →Y)≥minconf 的關(guān)系規(guī)則，即找出強(qiáng)關(guān)聯(lián)規(guī)則。

2.3 Apriori算法存在的問題

Apriori 算法中，事務(wù)數(shù)據(jù)存放在數(shù)據(jù)庫(kù)中，為了獲取候選集，需要多次掃描事務(wù)數(shù)據(jù)庫(kù)，導(dǎo)致I/O 負(fù)載過大，另外由LK-1得到Ck的過程，會(huì)導(dǎo)致產(chǎn)生大量的沒有實(shí)際操作意義的候選集[7]。因此該算法的改進(jìn)可以從兩個(gè)方面考慮，一方面是如何對(duì)事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行有效的聚類，減少數(shù)據(jù)庫(kù)中的無用數(shù)據(jù)，從而提高掃描效率；另一方面是針對(duì)數(shù)據(jù)庫(kù)的描述得到的大量候選集，如何提高驗(yàn)證候選集支持度計(jì)數(shù)時(shí)的I/O 效率。

3 算法改進(jìn)

3.1 事務(wù)數(shù)據(jù)庫(kù)聚類方法

針K-means 算法的不足，對(duì)數(shù)據(jù)庫(kù)中數(shù)據(jù)進(jìn)行凝聚層次聚類(AHC)[8]，該算法屬于無監(jiān)督學(xué)習(xí)的一種聚類算法，使用自底向上的策略，將對(duì)象組織到層次結(jié)構(gòu)中。凝聚層次聚類的思想是：最初將每個(gè)對(duì)象作為一個(gè)簇，然后按照相似性度量標(biāo)準(zhǔn)，按照數(shù)據(jù)相似度的高低，由高到低的依次合并數(shù)據(jù)形成簇，隨著簇的合并，簇間的相似度逐漸降低，當(dāng)達(dá)到給定的相似度閾值時(shí)，聚類終止。

首先將樣本（p1,p2,p3,p4,p5,p6）中每個(gè)數(shù)據(jù)視為一個(gè)簇，然后根據(jù)相似性度量標(biāo)準(zhǔn)找到距離最短的兩個(gè)簇p2,p3 進(jìn)行合并形成P23，此時(shí)的簇集合為{p1,P23,p4,p5,p6},接著從當(dāng)前簇集合中尋找距離最短的兩個(gè)簇p4,p5 進(jìn)行合并形成P45，從而得到新簇{p1,P23,P45,p6},如果此時(shí)達(dá)到給定的閾值4，則聚類停止。

此處采用的相似性度量標(biāo)準(zhǔn)為歐式距離法：

簇間距離度量采用最短距離法（最大相似度）：Distmin(Ci,Cj)= min{|p-q|}(p∈Ci,q∈Cj)

該算法的整個(gè)過程是建立一個(gè)樹結(jié)構(gòu)，如圖1 所示。

3.2 采用矩陣方式存儲(chǔ)項(xiàng)集關(guān)聯(lián)事務(wù)[1]

通過掃描事務(wù)數(shù)據(jù)庫(kù)，獲取事務(wù)數(shù)據(jù)庫(kù)中的所有1 項(xiàng)集，利用m×n 階矩陣，記錄每個(gè)項(xiàng)集對(duì)應(yīng)的事務(wù)信息，每一行表示一個(gè)項(xiàng)，每一列表示一個(gè)事務(wù)，在矩陣中分別用“1”和“0”表示項(xiàng)Ii是否出現(xiàn)在Ti中。獲取候選1-項(xiàng)集C1的支持度記數(shù)，計(jì)算矩陣中每一行的取值為“1”的元素的個(gè)數(shù)。根據(jù)關(guān)聯(lián)規(guī)則性質(zhì)構(gòu)造頻繁K 項(xiàng)集LK。

4 聚類分析與Aprior在線購(gòu)物系統(tǒng)中的應(yīng)用

為數(shù)據(jù)庫(kù)中的每個(gè)購(gòu)物記錄構(gòu)造用戶相關(guān)的屬性，根據(jù)用戶注冊(cè)時(shí)輸入的信息，包括用戶的性別、年齡、愛好等信息，使用K-means凝聚層次聚類算法，先將數(shù)據(jù)庫(kù)中的每個(gè)對(duì)象作為一個(gè)簇，然后針對(duì)每個(gè)簇根據(jù)某個(gè)鄰近度量而進(jìn)行合并，反復(fù)進(jìn)行聚類合并過程，直到所有對(duì)象最終滿足要求，達(dá)到給定的相似度閾值，對(duì)合并后的簇找出其具有代表性的數(shù)據(jù)，從而實(shí)現(xiàn)事務(wù)數(shù)據(jù)庫(kù)的壓縮。算法的執(zhí)行過程如下：

（1）根據(jù)用戶的注冊(cè)信息，確定有用的用戶的屬性特征描述：用戶性別、年齡、職業(yè)、愛好、學(xué)歷等。

（2）對(duì)用戶屬性值進(jìn)行正規(guī)化操作，將所有屬性值映射到[0，1]區(qū)間。

（3）使用K-means 凝聚層次聚類算法，根據(jù)用戶的年齡或愛好等屬性，利用歐氏距離計(jì)算公式，計(jì)算距離最短的兩個(gè)用戶簇進(jìn)行合并，然后再次從簇集合中尋找距離最短的兩個(gè)簇合并，循環(huán)直到有所用戶都聚類完成，形成聚類樹。根據(jù)聚類樹劃分想要的N 個(gè)聚類，改變 cluster 數(shù)目不需要再次計(jì)算數(shù)據(jù)點(diǎn)的歸屬。

（4）從每個(gè)聚類中，根據(jù)商品出現(xiàn)的頻次構(gòu)造該聚類中的代表數(shù)據(jù)，完成事務(wù)數(shù)據(jù)庫(kù)的壓縮。

針對(duì)壓縮后的事務(wù)數(shù)據(jù)庫(kù)D，生成m×n 矩陣[1]，計(jì)算矩陣中每一行中“1”的個(gè)數(shù)，即得到Ii 的支持度，將結(jié)果記錄于數(shù)據(jù)字典中；然后將矩陣中小于最小支持度記數(shù)2 的項(xiàng)刪除，得到矩陣M1以及頻繁1-項(xiàng)集L1；將矩陣M1中的各行進(jìn)行“邏輯與”運(yùn)算，并計(jì)算“與”運(yùn)算的項(xiàng)的支持度，得到候選2 項(xiàng)集C2，將結(jié)果記錄于數(shù)據(jù)字典中；將小于最小支持度記數(shù)2 的項(xiàng)刪除，得到頻繁2-項(xiàng)集L2；根據(jù)頻繁項(xiàng)集的所有非空子集都必須是頻繁的，將頻繁2 項(xiàng)集進(jìn)行連接操作，同時(shí)掃描矩陣M1，當(dāng)連接后的項(xiàng)對(duì)應(yīng)的各行進(jìn)行“邏輯與”運(yùn)算，得到候選3 項(xiàng)集C3，將小于最小支持度記數(shù)2 的項(xiàng)刪除，得到頻繁3-項(xiàng)集L3；依此類推，最終得到所有需頻繁項(xiàng)集，生成關(guān)聯(lián)規(guī)則。

4 結(jié)論

本文利用關(guān)聯(lián)規(guī)則挖掘算法Apriori 發(fā)現(xiàn)在線購(gòu)物系統(tǒng)中用戶購(gòu)買商品的內(nèi)在聯(lián)系，以實(shí)現(xiàn)個(gè)性推薦功能，并針對(duì)Apriori 算法存在的不足，首先利用聚類算法對(duì)在線購(gòu)物系統(tǒng)數(shù)據(jù)庫(kù)進(jìn)行了聚類，然后利用矩陣及字典存儲(chǔ)事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)，最終完成頻繁項(xiàng)集的挖掘與關(guān)聯(lián)規(guī)則的生成，該算法可有效降低Apriori 算法反復(fù)掃描數(shù)據(jù)庫(kù)導(dǎo)致的產(chǎn)生大量候選集的情況，提高了算法的執(zhí)行效率。