基于數(shù)據(jù)挖掘的ISC算法研究

陳婕

摘要：在擁擠的大賣場或是百貨公司逛街時，常因環(huán)境或是外在因素而導致行動網(wǎng)絡不穩(wěn)定，無法順利在有限時間內將特定廣告信息傳遞至目標消費者，因此該文在機會網(wǎng)絡下結合數(shù)據(jù)挖掘與社群網(wǎng)絡技術，提出一個高效率算法，能在有限時間內將商家或是消費者想要推播的廣告信息推播給特定目標消費者，并且在推播過程中選擇較有興趣的消費者進而有效提高廣告效益以及商家銷售量。

關鍵詞： 數(shù)據(jù)挖掘； 社群網(wǎng)絡技術； 高效率算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）35-8588-03

Research on the ISC Algorithm Based on Data Mining

CHEN Jie

（Hunan Vocational College of Railway Technology，Zhuzhou 412006，China）

Abstract： In a crowded mall or department store shopping， the environment or external factors often lead to action network is not stable， won't go down well in the limited time to specific advertising information transmission to the target consumers， so this thesis under the opportunity to network combined the technology of data mining and social network， an efficient algorithm， can in the limited time to push businesses or consumers want to broadcast advertising information push to specific target consumers， and choose more interested in the process of pushing seeding of consumers and effectively improve the efficiency of the advertising and sales dealer.

Key words： data mining； community network technology； efficient algorithms

1 簡介

近年同時因為社群網(wǎng)絡的蓬勃發(fā)展，許多機會網(wǎng)絡均與社交網(wǎng)絡上的信息結合，同時隨著智能型行動裝置的進步，目前更逐漸在發(fā)展只要透過行動裝置就能直接在商家透過手持裝置完成消費的功能，在大賣場或百貨公司這種人潮擁擠的場所下，若想在消費者逛街的有效時間內發(fā)送有效地廣告與消費信息往往會因為行動網(wǎng)絡的不穩(wěn)定而需要花費很長的繞送路徑，又無法在有限時間將廣告送達給消費者，抑或是要發(fā)送多次，提高發(fā)送成本才能送達消費者。因此提出了Interest-aware People Rank （IPeR） 算法，在People Rank的計算上加入使用者的興趣，透過此算法可以選擇較有興趣的使用者進行廣告推播，如此不僅可以提高推播廣告時的廣告效益，更可以提升找到目標使用者的機率。然而，提出的IPeR算法需要O（n4）的復雜度才能完成推播，若是有大量的使用者要進行廣告的推播將會使得智能型行動裝置上的負荷太重，且在選擇推播路徑食指使用消費者的社群來判斷消費者的興趣，若是能加入消費歷史數(shù)據(jù)進行判斷，將能更有效地找到潛在的消費者，進而提升廣告的效益。

因此該文結合機會網(wǎng)絡與社群和與消費數(shù)據(jù)，提出一個消費行為多層模型以及Interest-aware Opportunistic Advertising算法，簡稱ISC算法，在大賣場或是百貨公司的環(huán)境下，透過分析社群與消費數(shù)據(jù)有效選擇有興趣且具有潛在消費機率的消費者進行廣告的推播，如此可將廣告推播給真正有需求且有興趣的消費者，進而有效提高廣告效益以及商家銷售量，同時ISC算法可以在O（n2） 完成廣告的播送運算，在智能型裝置上將可更有效率。

2 背景

針對IPeR算法，我們認為有兩個部分可以加以強化改進。首先，IPeR算法后發(fā)現(xiàn)他們的算法內包含了兩層循環(huán)使得整個算法的時間復雜度會達到O（n4），鑒于整個算法是執(zhí)行于手持行動裝置上方，若大量地使用IPeR算法進行廣告的推播，將造成行動裝置上的負荷量過大且執(zhí)行效率差；第二，在過往的研究中均是使用消費的歷史數(shù)據(jù)進行消費商品的推薦，卻只從消費者的社群數(shù)據(jù)中判斷消費者的興趣，并推測消費者對于廣告的興趣，如此可能無法有效增加廣告在推播時的效益，因此在機會網(wǎng)絡的推播算法里除了使用社群數(shù)據(jù)外，若加入了實際的歷史消費信息來判斷消費者的興趣以及消費機率將可更有效地選擇推播的消費者同時提升廣告的效益。因此本文使用了社群以及消費數(shù)據(jù)來選擇有興趣且具有消費潛力的消費者進行廣告的推播，且提出的算法能在O（n2）內完成廣告的推播，在智能型裝置執(zhí)行，相當有效率。

3 方法

本節(jié)將探討我們所提出的方法，包含了一個多層模型，如圖1以及ISC算法。在多層模型方面，我們一開始會預先做數(shù)據(jù)搜集的動作，數(shù)據(jù)內容包含消費者的消費信息以及商家信息，再來我們提出了屬性層，主要用來定義商家的型態(tài)，同時此數(shù)據(jù)將會提供給社交層，社交層會收集使用者的朋友信息同時利用曾經(jīng)消費過的店家進行消費行為的比對，同時商店層也會進行店家間的關聯(lián)性比對，此多階層的算法實行在智能型手持裝置上將可以為商家或消費者更有效率的播送廣告給附近有共同喜好、共同興趣抑或是有社群關系者，以提升整體廣告效益。

圖1為我們的ISC算法圖形架構，在ISC算法中，我們將智能型手持裝置中的每則廣告依據(jù)算法中的三個步驟機制來判斷如何廣播至附近的智能型手持裝置使用者，藉此達到降低花費以及提升廣告效益的目的。

步驟1：附近使用者人數(shù)的多寡將影響整個廣告廣播的花費以及效益，但當附近人數(shù)不足時，若還針對廣播加以限制，那整體廣告效益以及將廣告?zhèn)鬟_至目標使用者的機率將會很低。所以我們先行一步判斷附近使用者的數(shù)量是否有高于定義值 ，若是，則再進一步透過步驟二判斷；否則將廣告進行廣播給附近所有裝置。

步驟2：對廣告有興趣者比例的多寡將是影響到整個廣播機制是否能夠提升廣告效益的重要因素，因為有相同興趣者容易聚集在一起。因此，我們將判別附近對廣告有興趣的使用者人數(shù)，若是人數(shù)比例高達定義值 時，則將廣告?zhèn)魉徒o附近所有對廣告有興趣的使用者；否則將進入步驟3判斷。

步驟3：透過上一節(jié)所記錄的兩個表來開發(fā)可能對該廣告有興趣的消費族群。透過Cosine Similarity（公式1）來計算目前使用者與其它使用者的社交與消費行為相似程度值，當兩使用者所算出的相似度值越高即代表兩者在社群以及消費相關性都極度相似，如此即有可能也會對該廣告產生興趣而產生消費行為，所以當相似度高于定義值時，只將廣告?zhèn)魉徒o與使用者相似度高的使用者；否則將廣告廣播給附近所有人。

算法一開始需要在裝置上存有附近使用者Neighbors的數(shù)量以及消費屬性表、商家集合表以及使用者社群朋友清單。Ads In Buffer記錄目前行動裝置內所包含的所有廣告數(shù)量；exchange Interest Data函式用來判斷正在溝通的對象是否對于目前廣告有興趣；contact With代表目前正在溝通的使用者；is Similarity則會判斷兩者相似度程度高低。

4 模擬結果

4.1 模擬環(huán)境

該文的實驗環(huán)境主要是以程序開發(fā)軟件Eclipse支持的Android 仿真器以及實體智能型手機來仿真算法在一般生活中手機的實際執(zhí)行情形，使用的仿真器版本以及智能型手機型號如表III所示。參數(shù)部分主要設定（附近消費者人數(shù)；廣告數(shù)目；朋友個數(shù)），三種參數(shù)數(shù)目的多寡都會影響到算法實際執(zhí)行的效率、決策方式、最后廣告效益、以及裝置所需的內存容量。

4.2 數(shù)據(jù)來源

數(shù)據(jù)方面使用了CRAWDAD網(wǎng)站所提供的“SIGCOMM 2009”會議數(shù)據(jù)以及英國政府網(wǎng)站釋出的消費者信用卡消費數(shù)據(jù)”Wiltshire Council - Credit card spending”。在SIGCOMM數(shù)據(jù)當中，紀錄了共76位擁有智能型手機的參與者數(shù)據(jù)并安裝了會議提供的軟件來記錄下會議期間的消費者數(shù)據(jù)，其中包含了消費者興趣以及朋友數(shù)據(jù)；我們使用了2014年5月至2014年8月共16個月的數(shù)據(jù)來找出消費者之間的相似程度，其中包含152個消費者數(shù)據(jù)以及1352間不同店家。

4.3 實驗結果

針對于圖2，此圖是在Eclipse上的Android仿真器執(zhí)行ISC算法以及IPeR算法，折線圖代表的意義為兩算法執(zhí)行時間，其中橫軸代表在上一節(jié)提到的參數(shù)設定（附近消費者人數(shù)；廣告數(shù)目；朋友個數(shù)），總共四組；縱軸所代表的是時間，單位為秒。我們透過折線圖可以清楚發(fā)現(xiàn)一般來說ISC算法的執(zhí)行速度都是快于IPeR算法的，而執(zhí)行的時間會依廣告數(shù)量以及附近人數(shù)多寡有明顯的增減，其中在（100；100；70）這組當中，ISC算法的效率比IPeR算法足足高出約4.48倍。

針對于圖3，此圖是在Desire手機上執(zhí)行ISC算法以及IPeR算法的結果，從結果中可以明顯發(fā)現(xiàn)實機的執(zhí)行效率遠比仿真器的高出很多，而在此結果中更可以明顯觀察出兩算法的差距，其中各組的倍率差分別是20.2倍、1.42倍、5.01倍以及11.18倍。

最后，針對于圖3，其中可以觀察出在（15；100；11）這組數(shù)據(jù)當中ISC算法的處理時間反而比IPeR算法來的高，但在圖4的實機上可以在看到ISC算法的處理時間比IPeR算法來的低，所以此狀況應該是仿真器執(zhí)行上的處理問題，在一般實際手機上我們的ISC算法執(zhí)行的效率都是比IPeR算法來的好很多。

5 結論

在此篇文章中，我們提出了一個多層模型和ISC算法，ISC算法結合了社群、興趣以及消費信息，能在沒有通訊網(wǎng)路的環(huán)境之下透過智能型手持裝置有效地將來源端的廣告信息于有限的時間之內推送至目標使用者，并確保在推播的過程中，轉送廣告的中間消費者對轉送的廣告有一定程度的興趣，能增加將廣告送到目標消費者的機率更能提升廣告效益。透過多層模型與ISC算法，機會網(wǎng)絡成功與社群平臺數(shù)據(jù)結合，廣告的發(fā)送更有效率與效益。

參考文獻：

[1] Hui P，et al.Bubble Rap： Social-based forwarding in Delay Tolerant Networks[C]//9th ACM Mobi Hoc Proceedings，2008：241-250.

[2] Mtibaa A，May M，Ammar M.Social Forwarding in Mobile Opportunistic Networks： A Case of PeopleRank[J].Communication and Social Networks，Springer， 2012，58：387-425.

[3] Nan Li，Guanling Chen.Multi-layered Friendship Modeling for Location-Based Mobile Social Networks.Mobi Quitous '09.

[4] Vincent S Tseng，Jeng-Chuan Chang，Kawuu W Lin.Mining and Prediction of Temporal Navigation Patterns For Personalized Services in E-Commerce.SAC06，Dijon， France，2006：23-27.

[5] Noraswaliza Abdullah，Yue Xu，Shlomo Geva.Infrequent Purchased Product Recommendation Making Based on User Behaviour and Opinions in E-commerce Sites[C]Data Mining Workshops （ICDMW），2010 IEEE International Conference on.

[6] Yan Zheng Wei，Luc Moreau，Nicholas R Jennings.Learning Users' Interests by Quality Classification in Market-based Recommender Systems[J].IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING， DECEMBER 2005，17（12）.

[7] Xiaoyuan Su，Taghi M Khoshgoftaar.A Survey of Collaborative Filtering Techniques[J].Journal Advances in Artificial Intelligence Volume 2009，2009 （4）.

[8] Soumaia Al Ayyat，Sherif G Aly，Khaled A Harras.Interest Aware People Rank-Towards Effective Social-Based Opportunistic Advertising[C].2013 IEEE Wireless Communications and Networking Conference （WCNC）： SERVICES & APPLICATIONS，2013.

[9] Xiong YP，Sun LM，Niu JW.Opportunistic networks[J].Journal of Software，2009，20（1）：124-137.