国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

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

2020-02-03 01:24劉玥波劉田
電子技術與軟件工程 2020年14期
關鍵詞:項集事務關聯(lián)

劉玥波 劉田

(1.吉林建筑科技學院 吉林省長春市 130114 2.啟明信息技術股份有限公司 吉林省長春市 130122)

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

1 聚類分析

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

1.1 K-means 聚類算法思想

1967年Mac Queen首次提出了K均值聚類算法(K-means算法),該算法已廣泛地應用于科學研究和計算機網(wǎng)絡。聚類分析作為一種非監(jiān)督學習方法,是機器學習領域中的一個非常重要的研究方向[4]。

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

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

1.2 k-means算法描述

輸入:數(shù)據(jù)集D,聚族數(shù)k

輸出:聚簇代表集合C,聚簇成員向量m

(1)從數(shù)據(jù)集D 中隨機挑選k 個數(shù)據(jù)點。

(2)使用k 個數(shù)據(jù)點構成初始聚簇代表集合C。

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

(4)更新聚簇均值,即計算每個對象簇中的對象均值。

(5)計算目標函數(shù)。

圖1:層次聚類結果

(6)重復(3)(4)(5),直到目標函數(shù)收斂。

1.3 K-means 算法存在的問題

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

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

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

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

若X、Y 均為項集,且X?I,Y?I,并且X ∩Y=?,則形如X →Y 的蘊涵式即為關聯(lián)規(guī)則。其中,X 和Y 分別被稱為關聯(lián)規(guī)則的先導(前件)和后繼(后件)。

對于項集X,設定count(X)為交易集D 中包含X 的交易的數(shù)量,count(D)為事務總數(shù),則項集X 的支持度為:

關聯(lián) 規(guī)則X →Y 的支 持度 為項 集X?Y 的 支持 度:

最小支持度是項集的最小支持閾值,記為minsup。支持度不小于minsup 的項集稱為頻繁項集,否則稱為非頻繁項集,長度為k的頻繁集稱為k-頻繁集。

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

最小置信度是由用戶定義衡量置信度的一個閾值,記為minconf。

2.2 Apriori 算法

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

2.3 Apriori算法存在的問題

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

3 算法改進

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

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

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

此處采用的相似性度量標準為歐式距離法:

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

該算法的整個過程是建立一個樹結構,如圖1 所示。

3.2 采用矩陣方式存儲項集關聯(lián)事務[1]

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

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

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

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

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

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

(4)從每個聚類中,根據(jù)商品出現(xiàn)的頻次構造該聚類中的代表數(shù)據(jù),完成事務數(shù)據(jù)庫的壓縮。

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

4 結論

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

猜你喜歡
項集事務關聯(lián)
基于分布式事務的門架數(shù)據(jù)處理系統(tǒng)設計與實現(xiàn)
不懼于新,不困于形——一道函數(shù)“關聯(lián)”題的剖析與拓展
河湖事務
“一帶一路”遞進,關聯(lián)民生更緊
奇趣搭配
智趣
關聯(lián)規(guī)則中經(jīng)典的Apriori算法研究
一種頻繁核心項集的快速挖掘算法
SQLServer自治事務實現(xiàn)方案探析
移動實時環(huán)境下的數(shù)據(jù)一致性研究