摘要：在拥挤的大卖场或是百货公司逛街时，常因环境或是外在因素而导致行动网络不稳定，无法顺利在有限时间内将特定广告信息传递至目标消费者，因此该文在机会网络下结合数据挖掘与社群网络技术，提出一个高效率算法，能在有限时间内将商家或是消费者想要推播的广告信息推播给特定目标消费者，并且在推播过程中选择较有兴趣的消费者进而有效提高广告效益以及商家销售量。
关键词： 数据挖掘； 社群网络技术； 高效率算法
中图分类号：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 简介
近年同时因为社群网络的蓬勃发展，许多机会网络均与社交网络上的信息结合，同时随着智能型行动装置的进步，目前更逐渐在发展只要透过行动装置就能直接在商家透过手持装置完成消费的功能，在大卖场或百货公司这种人潮拥挤的场所下，若想在消费者逛街的有效时间内发送有效地广告与消费信息往往会因为行动网络的不稳定而需要花费很长的绕送路径，又无法在有限时间将广告送达给消费者，抑或是要发送多次，提高发送成本才能送达消费者。因此提出了Interest-aware People Rank （IPeR） 算法，在People Rank的计算上加入使用者的兴趣，透过此算法可以选择较有兴趣的使用者进行广告推播，如此不仅可以提高推播广告时的广告效益，更可以提升找到目标使用者的机率。然而，提出的IPeR算法需要O（n4）的复杂度才能完成推播，若是有大量的使用者要进行广告的推播将会使得智能型行动装置上的负荷太重，且在选择推播路径食指使用消费者的社群来判断消费者的兴趣，若是能加入消费历史数据进行判断，将能更有效地找到潜在的消费者，进而提升广告的效益。
因此该文结合机会网络与社群和与消费数据，提出一个消费行为多层模型以及Interest-aware Opportunistic Advertising算法，简称ISC算法，在大卖场或是百货公司的环境下，透过分析社群与消费数据有效选择有兴趣且具有潜在消费机率的消费者进行广告的推播，如此可将广告推播给真正有需求且有兴趣的消费者，进而有效提高广告效益以及商家销售量，同时ISC算法可以在O（n2） 完成广告的播送运算，在智能型装置上将可更有效率。
2 背景
针对IPeR算法，我们认为有两个部分可以加以强化改进。首先，IPeR算法后发现他们的算法内包含了两层循环使得整个算法的时间复杂度会达到O（n4），鉴于整个算法是执行于手持行动装置上方，若大量地使用IPeR算法进行广告的推播，将造成行动装置上的负荷量过大且执行效率差；第二，在过往的研究中均是使用消费的历史数据进行消费商品的推荐，却只从消费者的社群数据中判断消费者的兴趣，并推测消费者对于广告的兴趣，如此可能无法有效增加广告在推播时的效益，因此在机会网络的推播算法里除了使用社群数据外，若加入了实际的历史消费信息来判断消费者的兴趣以及消费机率将可更有效地选择推播的消费者同时提升广告的效益。因此本文使用了社群以及消费数据来选择有兴趣且具有消费潜力的消费者进行广告的推播，且提出的算法能在O（n2）内完成广告的推播，在智能型装置执行，相当有效率。
3 方法
本节将探讨我们所提出的方法，包含了一个多层模型，如图1以及ISC算法。在多层模型方面，我们一开始会预先做数据搜集的动作，数据内容包含消费者的消费信息以及商家信息，再来我们提出了属性层，主要用来定义商家的型态，同时此数据将会提供给社交层，社交层会收集使用者的朋友信息同时利用曾经消费过的店家进行消费行为的比对，同时商店层也会进行店家间的关联性比对，此多阶层的算法实行在智能型手持装置上将可以为商家或消费者更有效率的播送广告给附近有共同喜好、共同兴趣抑或是有社群关系者，以提升整体广告效益。
图1为我们的ISC算法图形架构，在ISC算法中，我们将智能型手持装置中的每则广告依据算法中的三个步骤机制来判断如何广播至附近的智能型手持装置使用者，藉此达到降低花费以及提升广告效益的目的。
步骤1：附近使用者人数的多寡将影响整个广告广播的花费以及效益，但当附近人数不足时，若还针对广播加以限制，那整体广告效益以及将广告传达至目标使用者的机率将会很低。所以我们先行一步判断附近使用者的数量是否有高于定义值 ，若是，则再进一步透过步骤二判断；否则将广告进行广播给附近所有装置。
步骤2：对广告有兴趣者比例的多寡将是影响到整个广播机制是否能够提升广告效益的重要因素，因为有相同兴趣者容易聚集在一起。因此，我们将判别附近对广告有兴趣的使用者人数，若是人数比例高达定义值 时，则将广告传送给附近所有对广告有兴趣的使用者；否则将进入步骤3判断。
步骤3：透过上一节所记录的两个表来开发可能对该广告有兴趣的消费族群。透过Cosine Similarity（公式1）来计算目前使用者与其它使用者的社交与消费行为相似程度值，当两使用者所算出的相似度值越高即代表两者在社群以及消费相关性都极度相似，如此即有可能也会对该广告产生兴趣而产生消费行为，所以当相似度高于定义值时，只将广告传送给与使用者相似度高的使用者；否则将广告广播给附近所有人。
算法一开始需要在装置上存有附近使用者Neighbors的数量以及消费属性表、商家集合表以及使用者社群朋友清单。Ads In Buffer记录目前行动装置内所包含的所有广告数量；exchange Interest Data函式用来判断正在沟通的对象是否对于目前广告有兴趣；contact With代表目前正在沟通的使用者；is Similarity则会判断两者相似度程度高低。
4 模拟结果
4.1 模拟环境
该文的实验环境主要是以程序开发软件Eclipse支持的Android 仿真器以及实体智能型手机来仿真算法在一般生活中手机的实际执行情形，使用的仿真器版本以及智能型手机型号如表III所示。参数部分主要设定（附近消费者人数；广告数目；朋友个数），三种参数数目的多寡都会影响到算法实际执行的效率、决策方式、最后广告效益、以及装置所需的内存容量。
4.2 数据来源
数据方面使用了CRAWDAD网站所提供的“SIGCOMM 2009”会议数据以及英国政府网站释出的消费者信用卡消费数据”Wiltshire Council - Credit card spending”。在SIGCOMM数据当中，纪录了共76位拥有智能型手机的参与者数据并安装了会议提供的软件来记录下会议期间的消费者数据，其中包含了消费者兴趣以及朋友数据；我们使用了2014年5月至2014年8月共16个月的数据来找出消费者之间的相似程度，其中包含152个消费者数据以及1352间不同店家。
4.3 实验结果
针对于图2，此图是在Eclipse上的Android仿真器执行ISC算法以及IPeR算法，折线图代表的意义为两算法执行时间，其中横轴代表在上一节提到的参数设定（附近消费者人数；广告数目；朋友个数），总共四组；纵轴所代表的是时间，单位为秒。我们透过折线图可以清楚发现一般来说ISC算法的执行速度都是快于IPeR算法的，而执行的时间会依广告数量以及附近人数多寡有明显的增减，其中在（100；100；70）这组当中，ISC算法的效率比IPeR算法足足高出约4.48倍。
针对于图3，此图是在Desire手机上执行ISC算法以及IPeR算法的结果，从结果中可以明显发现实机的执行效率远比仿真器的高出很多，而在此结果中更可以明显观察出两算法的差距，其中各组的倍率差分别是20.2倍、1.42倍、5.01倍以及11.18倍。
最后，针对于图3，其中可以观察出在（15；100；11）这组数据当中ISC算法的处理时间反而比IPeR算法来的高，但在图4的实机上可以在看到ISC算法的处理时间比IPeR算法来的低，所以此状况应该是仿真器执行上的处理问题，在一般实际手机上我们的ISC算法执行的效率都是比IPeR算法来的好很多。
5 结论
在此篇文章中，我们提出了一个多层模型和ISC算法，ISC算法结合了社群、兴趣以及消费信息，能在没有通讯网路的环境之下透过智能型手持装置有效地将来源端的广告信息于有限的时间之内推送至目标使用者，并确保在推播的过程中，转送广告的中间消费者对转送的广告有一定程度的兴趣，能增加将广告送到目标消费者的机率更能提升广告效益。透过多层模型与ISC算法，机会网络成功与社群平台数据结合，广告的发送更有效率与效益。
参考文献：
[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.SAC’06，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.