一種基于基因表達式編程的串行聚類算法并行化研究

蔡宏果,元昌安

( 1 廣西師范學(xué)院 科學(xué)計算與智能信息處理廣西高校重點實驗室，南寧 530023；2 廣西教育學(xué)院 培訓(xùn)學(xué)院，南寧 530023)

一種基于基因表達式編程的串行聚類算法并行化研究

蔡宏果1,2,元昌安1，*

( 1 廣西師范學(xué)院 科學(xué)計算與智能信息處理廣西高校重點實驗室，南寧 530023；2 廣西教育學(xué)院 培訓(xùn)學(xué)院，南寧 530023)

為進一步解決基于用戶的協(xié)作過濾技術(shù)的擴展性問題，利用基因表達式編程(GEP)的并行性優(yōu)勢，與已有的串行聚類DBSCAN算法進行融合，使得串行程序并行化，提出了一種GEP-DBSCAN協(xié)作過濾聚類算法來尋找最近鄰居，改進基于密度的協(xié)作過濾方法，實驗證明了算法的有效性以及提高了時間效率.

聚類算法；基因表達式編程；協(xié)作過濾

協(xié)作過濾技術(shù)分為基于用戶的協(xié)作過濾和基于資源的協(xié)作過濾.對于基于用戶的協(xié)作過濾推薦系統(tǒng)，當(dāng)有新用戶加入時，推薦的擴展性將成為非常嚴(yán)重的問題[1]，文獻[2]為了解決擴展性問題，在用戶評分?jǐn)?shù)據(jù)上再做一次用戶聚類分析是比較有效的辦法，由于在特定用戶分類中，最近鄰居群相對變化較小，研究表明，用戶分成多少個類別的群集，推薦系統(tǒng)的時間效率就能夠提高到幾倍.文獻[3]將基于鄰居聚類的協(xié)同過濾方法用于云計算環(huán)境，實驗表明，在數(shù)據(jù)量劇增環(huán)境下，基于協(xié)同過濾的個性化推薦技術(shù)比傳統(tǒng)的推薦技術(shù)具有更高的準(zhǔn)確率.文獻[4]用具有明確數(shù)學(xué)模型的基于隱語義概率模型的協(xié)同過濾方法來預(yù)測用戶偏好，具有更好的預(yù)測精度.文獻[5]使用基于密度的劃分方法在用戶評分?jǐn)?shù)據(jù)上做“最近鄰居”聚類分析，聚類計算往往可以離線，沒有實時要求的基礎(chǔ)，從而極大的緩解了推薦系統(tǒng)的實時計算壓力，增加了推薦系統(tǒng)的速度.但是，以上協(xié)同過濾方法中的聚類算法都需要精確的數(shù)學(xué)模型或大量的實驗來調(diào)整一些參數(shù)的設(shè)置，同時還存在推薦準(zhǔn)確率有待提高、沒有考慮空間拓展性能等問題，這給實際工作帶來應(yīng)用上的復(fù)雜性.為解決這些問題，近年來，利用進化計算來解決聚類技術(shù)存在的問題成為研究熱點之一.Murthy等在 1996年提出的基于遺傳算法的聚類技術(shù)，開創(chuàng)了進化計算用于聚類的研究，算法采用二進制編碼，只適合解決數(shù)據(jù)集較小的聚類問題.文獻[6]使用改進粒子群算法來實現(xiàn)聚類,該算法能夠處理較大的數(shù)據(jù)集.文獻[7]提出基因表達式編程(GEP)自動聚類算法，解決了進化計算自動聚類的問題.GEP是在遺傳算法和其它進化算法的基礎(chǔ)上發(fā)展的新技術(shù)，比遺傳算法編碼更靈活，具有更強的解決問題能力，GEP目前已經(jīng)應(yīng)用在多個領(lǐng)域[8-10].進化計算具有并行性和智能性的優(yōu)勢， 但是，進化計算具有求解問題只有近似解而難以得到最優(yōu)解的弊端，與經(jīng)典的基于密度的聚類算法相比，聚類的準(zhǔn)確率隨機性較大.

本文在以上研究的基礎(chǔ)上，依據(jù)傳統(tǒng)基于密度的聚類原理和GEP自動聚類的思想，提出了基于DBSCAN和GEP的聚類算法來解決協(xié)作過濾技術(shù)中的最近鄰居聚類問題，先通過密度原理形成幾個好的中心區(qū)域，再通過GEP并行性和智能性的處理能力，對用戶進行自動聚類，減少空間開銷，改善基于用戶的協(xié)作過濾方法的性能拓展，提高預(yù)測的準(zhǔn)確率.

1 相關(guān)工作

1.1 基于用戶的協(xié)作過濾和密度聚類概述

基于用戶的協(xié)作過濾的基本思想是根據(jù)用戶興趣的相似性來推薦資源，通過研究不同用戶的興趣,主動為當(dāng)前用戶推薦相似的其它用戶的已訪問資源，將N-top資源提供給當(dāng)前用戶[11].基于密度的聚類方法與其它方法的一個根本區(qū)別是，它不是基于各種各樣的距離的，而是基于密度的，文獻[12]和文獻[13]研究了基于密度原理的新的聚類方法.基于密度的方法指導(dǎo)思想是，對給定簇中的每個數(shù)據(jù)點，在給定半徑的鄰域內(nèi)至少必須包含規(guī)定的閾值個點.代表算法有：DBSCAN算法、DENCLUE算法、OPTICS算法等.DBSCAN算法有幾個重要的定義如半徑eps、Ε領(lǐng)域、核心對象、閾值minpts等[11].DBSCAN算法描述參見文獻[11].

1.2 基于GEP和DBSCAN協(xié)作過濾算法

基于GEP和DBSCAN的協(xié)作過濾聚類算法基本思路是：將日志文件以用戶作為個體，用戶訪問序列中的訪問頁(項目、屬性等)作為對象相似性度量，預(yù)處理成數(shù)據(jù)庫D，從數(shù)據(jù)庫D中選取用戶，通過半徑和密度閾值確定是否為核心對象或者噪聲，并創(chuàng)建核心對象的簇，結(jié)果標(biāo)記為數(shù)組arr[x]，利用基因表達式編程算法的深度遞歸搜索在arr[x]中尋找聚類族.

基于基因表達式編程的DBSCAN(GEP-DBSCAN)算法：

輸入： 數(shù)據(jù)庫D；GEP參數(shù)；Eps(鄰域或稱為半徑)；MinPts(密度閾值).

輸出：聚類簇結(jié)果.

步驟：

(1)掃描原始數(shù)據(jù)，數(shù)據(jù)清洗，預(yù)處理成數(shù)據(jù)庫D；

(2)讀取數(shù)據(jù)庫D中的任意一個還沒有分類的用戶U，檢索出與U的距離不大于Eps的所有對象Neps(U)；

(3) 如果(Neps(U)

(4)初始化種群，生成一定規(guī)模的染色體個體，計算Neps(U)的每個用戶與核心對象的相似性，公式2作為染色體個體的適應(yīng)性函數(shù)；

(5)依照輪盤規(guī)則實施GEP遺傳操作；

(6)按照GEP的交叉算子對個體進行遺傳交叉；

(7)按照GEP的變異算子對個體進行遺傳變異；

(8)若達到最大迭代次數(shù)則執(zhí)行步驟9，否則執(zhí)行步驟4 ；

(9)選擇出最優(yōu)個體；

(10) 輸出聚類簇結(jié)果.

1.3 GEP適應(yīng)度計算

用戶之間的相似計算主要是通過用戶對目標(biāo)項目(屬性)評分等決定，研究中，項目評分的次數(shù)、項目內(nèi)容的相近度都可以提高相似性計算，但是，一項協(xié)作過濾推薦算法比較研究表明：從所有用戶評分矩陣中抽離出維度更小的評分矩陣不僅提高了預(yù)測效率，而且在聚類的基礎(chǔ)上有時可以提高算法的預(yù)測精度，相似度計算方法可采用皮爾遜相關(guān)系數(shù)計算.

sim(i,j)=

(1)

(2)

2 實驗與性能分析

實驗數(shù)據(jù)來源于movielens數(shù)據(jù)集，本文實驗使用了數(shù)據(jù)集提供的用戶評分?jǐn)?shù)據(jù)ml數(shù)據(jù)集用于算法測試，實驗環(huán)境，Windows XP；Microsoft Visual studio(c#)及SPSS Clementine 10.0.

實驗一選取數(shù)據(jù)集中的1000條評價數(shù)據(jù).根據(jù)文獻[8]和文獻[9]對GEP遺傳算子參數(shù)的實驗結(jié)論和討論，選擇GEP參數(shù).設(shè)置不同的Eps、MinPts值，聚類結(jié)果如圖1和圖2所示.

圖1 聚類結(jié)果的比較(相同的鄰域，不同閾值條件下)Fig.1 Comparison results on clustering (same neighborhood, different threshold conditions)

圖2 聚類結(jié)果的比較(不同的閾值，相同鄰域條件下)Fig.2 Comparison results on clustering (different threshold, same neighborhood conditions)

根據(jù)圖1所示，eps不變，隨著minpts的值不斷增加，圓圈所示噪聲數(shù)據(jù)不出現(xiàn)在結(jié)果集合中，GEP-DBSCAN算法能過濾噪聲，類與類之間的間隔也比較明顯；根據(jù)圖2所示，minpts不變，隨著eps的值不斷增加，圓圈所示中的聚類個數(shù)減少.實驗表明，GEP-DBSCAN算法能夠發(fā)現(xiàn)數(shù)據(jù)集中的聚類模式，較好的解決最近鄰居的聚類，形成聚類中心.

實驗二對u1～u5這5個數(shù)據(jù)集進行實驗，將每個數(shù)據(jù)集其中80%作為訓(xùn)練集，20%作為測試集，通過GEP-DBSCAN算法進行一次聚類后，依據(jù)基于用戶的協(xié)作過濾方法，獲得項目推薦集，抽取測試集其中的5個用戶的訪問情況與推薦集比較.與傳統(tǒng)基于用戶的協(xié)作過濾方法和文獻[7]自動聚類后的協(xié)作過濾方法進行實驗比較和分析，通過推薦的準(zhǔn)確率來度量推薦質(zhì)量，得到實驗結(jié)果見表1，通過最常用的平均絕對偏差MAE值來度量三種算法推薦質(zhì)量如圖3所示，通過三種算法對數(shù)據(jù)集的運行時間和平均運行時間來度量時間效率，得到實驗結(jié)果見表2.

表1 不同數(shù)據(jù)集中三種推薦方法的準(zhǔn)確率

Tab.1 The accuracy rate of three recommended methods in different data sets

不同的數(shù)據(jù)集傳統(tǒng)基于用戶的協(xié)作過濾方法/%文獻[7]自動聚類GEP-Cluster方法/%GEP-DBSCAN算法的協(xié)作過濾方法/%U135.044.660.6C32.544.044.6U333.542.051.0U435.046.048.6U522.537.856.5平均準(zhǔn)確率31.742.852.2

圖3 三種方法的MAE值Fig.3 MAE value of three methods

Tab.2 The running time of three recommended methods in different data sets

不同的數(shù)據(jù)集傳統(tǒng)基于用戶的協(xié)作過濾方法/s文獻[7]自動聚類GEP-Cluster方法/s基于GEP-DB-SCAN算法的協(xié)作過濾方法/sU160.7340.6031.00U250.7040.0028.50U357.2238.0029.50U474.1642.0031.00U576.2433.8018.50平均運行時間63.8138.8827.70

根據(jù)表1實驗結(jié)果表明，基于GEP-DBSCAN算法的協(xié)作過濾方法平均推薦準(zhǔn)確度則為52.2 %，比基于用戶的協(xié)作過濾推薦算法的推薦準(zhǔn)確度提高了39.7%，比文獻[7]中改進的協(xié)作過濾方法的推薦準(zhǔn)確度提高了18%，能顯著提高協(xié)作過濾的推薦質(zhì)量.圖3表明，基于GEP-DBSCAN算法的協(xié)作過濾方法平均絕對誤差最小.表2表明，基于GEP-DBSCAN算法的協(xié)作過濾方法平均運行時間最少，時間效率最高.

4 結(jié)語

協(xié)作過濾推薦系統(tǒng)已經(jīng)被廣泛應(yīng)用于Web網(wǎng)站、電子商務(wù)、電子圖書館等眾多領(lǐng)域,隨著用戶和產(chǎn)品數(shù)量的不斷增加,傳統(tǒng)算法的許多缺點逐漸暴露了出來.本文通過對協(xié)作過濾存在的計算瓶頸問題，提出了一種GEP-DBSCAN的協(xié)作過濾聚類算法，來解決用戶的“最近鄰居”問題，通過算法的實驗，提供了可靠的支撐依據(jù).

[1] 雷建云,何 順，李白楊.基于標(biāo)簽和云模型的協(xié)同過濾算法[J].中南民族大學(xué)學(xué)報(自然科學(xué)版),2016,35(3):117-122.

[2 ] 陳天昊,帥建梅.一種基于協(xié)作過濾的電影推薦方法[J].計算機工程,2014,40(1):55-62.

[3] 朱 夏,宋愛波.云計算環(huán)境下基于協(xié)同過濾的個性化推薦機制[J].計算機研究與發(fā)展,2014,51(10):2255-2269.

[4] 胡 堰,潘啟民.一種基于隱語義概率模型的個性化Web服務(wù)推薦方法[J].計算機研究與發(fā)展,2014,51(8):1781-1793.

[5] SabeurAridhi,Laurentd’Orazio etc. Density-based data partitioning strategy to approximate large-scale subgraph mining [J].Information Systems,2013,48(2015):213-223.

[6] 陳小全,張繼紅.基于改進粒子群算法的聚類算法[J].計算機研究與發(fā)展,2012,48(S1):287-291.

[7] 陳 瑜,唐常杰.基于基因表達式編程的自動聚類方法[J].四川大學(xué)學(xué)報 (工程科學(xué)版), 2007, 39(6):108-112.

[8] 元昌安,彭昱忠,覃 曉,等編著.基因表達式編程算法原理與應(yīng)用[M].北京：科學(xué)出版社,2010：38-108.

[9] Ferreira.C. Gene Expression Programming: A New Adaptive Algorithm for Solving Problems[J]. Complex Systems, 2001, 13(2): 87-129.

[10] Qin Xiao,Yuan Chang-an.A GEP-Based Text Classification Algorithm[J].Journal of Information & Computational Science, 2009,6(3):1303-1309.

[11] Han Jiawei, Micheline Kamber, Jian Pei, etc. Data mining: concepts and techniques [M].Waltham: Morgan Kaufmann Press,2007:246-290.

[12] 黃創(chuàng)光,印 鑒.不確定近鄰的協(xié)同過濾推薦算法[J].計算機學(xué)報,2010,33( 8):1369-1377.

ResearchonGEP-basedClusterAlgorithmforSerialProgramtobeParallelized

CaiHongguo1,2,YuanChanan1

(1 Computer and information engineering college, Guangxi Teachers Education University, Nanning 530023， China；2 Training School, Guangxi College of Education, Nanning 530023， China)

To address the expansibility problem of collaborative filtering technology based on users, the GEP-DBSCAN algorithm for collaborative filtering clustering was proposed. It is key to fuse the parallelism of gene expression programming and the advantages of the DBSCAN algorithm. The new algorithm makes serial programs parallelized and can be used to find the nearest neighbors. It improves collaborative filtering method based on the density. The experimental results show that the GEP-DBSCAN algorithm is effective and can increase time efficiency.

cluster algorithm; gene expression programming; collaborative filtering

2017-06-27 *

元昌安，研究方向：智能計算和數(shù)據(jù)挖掘，E-Mail:yca@gxtc.edu.cn

蔡宏果(1978-)，男，高級工程師，研究方向：智能計算和文本挖掘，E-mail: webminning@163.com

國家自然科學(xué)基金資助項目(61262028)

TP181

A

1672-4321(2017)04-0112-04