基于反向引用的电子商务信用评价算法及其在云计算平台中的实现

1、基于反向引用的电子商务信用评价算法及其在云计算平台中的实现Credit Evaluation in E-business Based on Inverted Reference and a MapReduce Implementation代栋 Dai Dong 杨峰Yang Feng中国科学技术大学苏州研究院，苏州， 215123Suzhou Institute for Advance Study of USTC, Suzhou摘要随着网上交易的兴起，C2C平台中买卖双方的信用评价成为影响电子商务成败的关键因素，传统的信用评价体系无法全面真实的反应一个网上店铺的信用，在实际的运营中反而带来了很

2、多信用欺诈问题。淘宝网在发展的过程中，不断提出新的信用评价方法，极大的改进了信用评价体系，但是由于采取的措施受到系统平台和评价体系模型的因素，不够灵活和准确。本文考虑了在C2C平台中交易的商铺、个人的关系，提出了采用搜索引擎中的页面比重排序算法对交易历史进行分析，充分考虑了C2C交易中各种影响商铺或个人信誉的因素及其权重。并且，在该算法的基础上提出了在云计算平台中，构建和实现这一算法的方法，并且针对实现策略进行了性能分析。该信用评价模型相比较传统模型更能够阻止恶意信用欺诈行为，并且由于采用云计算平台，相比传统方法更加高效、扩放性更好。关键字电子商务；网上交易；信用评价；搜索引擎；PageRan

3、k；云计算；MapReduceAbstractWhile the rapid development of E-business, Credit evaluation in C2C platform became a critical factor that determine the success of E-business. Traditional credit evaluation system can not reflect the real credit of a store or a customer, and cause lots of credit-cheat problem

4、s. Taobao, as the biggest C2C platform provider in China, was continuously proposing new credit evaluation systems in recent years, and has improved the way to solve this problem a lot. In this paper, we use PageRank-like algorithm to analyse the links produced by a trade action, and give a full con

5、sideration to the relationship among items, consumers and sellers in a C2C platform. Based on this algorithm, we use MapReduce and distributed file system to implement a flexible, scalable framework. This new credit evaluation model and its implementation can reduce the credit-cheating actions more

6、effectively and be more efficient, more scalable.KeywordE-Business; C2C; Credit Evaluation; PageRank; Search；Cloud Computing; MapReduce1 引言根据正望咨询的调查显示，2009年我国有1.3亿消费者共计在网上购买了2670亿元的商品，比2008年实现了90.7%的增长。2009年，在经济危机的大形势下，中国电子商务保持较快的增长速度，其中B2B市场保持了20%的增长率，C2C市场比2008年增长了一倍，而B2C市场交易额更是达到2008年的2倍【1】。在电子商务

7、大发展的形式之下，诚信问题逐渐成为影响电子商务进一步发展的重大阻碍，因此诚信体系的构建也就网规体系的根本和核心【2】。国内C2C电子商务的发展主要以淘宝网、易趣网、拍拍网为主，其中淘宝规模最大，也最具有代表性【3】。淘宝网所面临的诚信问题包括：宣传与实际商品不符、商品售后服务缺失，信用炒作，套取诚信、恶意竞拍等。其中信用炒作会导致失信行为无法体现在后续交易中，如果不能很好的对信用机制进行改进，长此以往将影响整个电子商务平台的诚信氛围。2 影响信用评价的因素一个典型的C2C平台，主要包括对商铺、商铺中的商品、消费者三种个体的信用评价45。其中商铺是商品的集合地。对商铺的信用评价往往代表了在C2C

8、平台中商品出售者的信誉。商品出售者可能是一个独立个体或者一个公司，但是其对外表现为统一的商铺信用；商铺中所有商品的信用评价和商铺的信用评价是息息相关的，但是具体到商品的信用评价，则不仅仅可以反映C2C中卖家的信用，也可以反应出非卖家因素导致的商品信用的波动。比如某项商品的生产商对产品质量把握出现差错，当然，也可能在普通卖家中出现明星商品。因此商铺中商品的信用评价更加准确、真实，在购买特定商品时可以提供更好的参考。最后，消费者的信用评价来自于卖家，我们鼓励消费者保护自己的账号，通过机制激励消费者账号的长期使用，C2C平台是一个向消费者展示商家的平台，因此对消费者的信用评价主要用来生成商家及商品的

9、信用评价。影响商铺中商品信用评价的因素主要包括如下几个方面：l 商品被购买的次数l 商品被消费者给予的评价l 给予评价的消费者本身的信用度如果一定数目的信用度较高的用户给予店铺中某商品较高的评价，那么我们就认为该商品具有较高的信用值，也意味着更值得购买。影响商铺的信用评价的因素主要包括几个方面：l 商铺中所售商品的信用度l 所出售各种商品占业务量的比重l 对交易中消费者的评价如果商铺中业务量中占绝大多数的商品都有较高的信誉度，那么该商铺也一定具有较高的信用度，更值得从该商铺中选购商品。这里需要注重的是，商铺中所卖商品组成商铺信誉的时候，其权重是不同的，该权值由商品价格占店铺总交易量的比重而定，

10、防止商铺通过大量出售非常便宜的商品来进行信用欺骗。影响消费者信用评价的因素主要包括：l 消费者所购买商品时得到店铺的评价l 评价消费者的店铺本身的信用l 对交易中店铺的评价如果一个消费者在很多交易中都得到商家的好评，说明该消费者能够在交易中做到诚实守信，因此其信用度也会较高。为了防止恶意影响信用评价体系的可能性，我们在影响商铺和消费者的因素中加入对对方的评价，如果对一个信用度较高的个体给予很低的评价，或者对一个信用较低的个体给予较高的评价，其权重都会很低。3 基于反向引用的评价方法反向引用6是一种搜索引擎中用来评价网页重要程度的方法，其原理非常直观，即认为大量引用别的页面的网页并不一定是好的，

11、但是被大量页面引用的网页，往往是大家认为非常重要的。因此相对于引用来说，反向引用更为重要。在C2C平台中进行信用度计算的模型和搜索引擎的页面排名类似。一次交易的一个评价相当于一个指向所交易的商品的链接，与超链接不同的是，这个链接还有权重即交易时的评价值；最终C2C平台中所有个体的信用评价都是由这个链接系统生成的。考虑一次交易的情形：某商铺的两件商品Ia和Ib，用户c1、c2作为两个消费者购买了这两件商品，并给予了交易评价、同时商户也根据这两次交易的情况给予两位消费者评价，这样便产生了多个反向链接，如图1所示。图1 一次交易产生的消费者C和商品I之间的链接关系这里我们用CR(object)函数来

12、表示整个交易系统中一个实体的信用度量。计算一个实体的信用度量只需要考虑链接到该实体的别的实体的信用值。引入公式：该公式表明, CR(object)表示对象object的信用值。计算I的信用值，要通过所有购买I的消费者的信用值来计算，每一个消费者在长期的购买过程中必然会带有大量的交易和评价信息，对当前I评价为W，那么实际计入I的评价应为W占用户所有对外评价的比重。任何一个实体的信用度量可以表示为所有引用至该节点的所有节点的单位信用度量的加权和。公式中是个常量，可以随应用调整，我们这里把其设置为0.85。表示对的信用评价，按照：好、较好、一般、较差、差的标准对应为5,4,3,2,1的权值。由于系统

13、初始时没有权值，我们设定所有元素的初始权值都为1，通过多次迭代计算出最终每一个节点的信用度量。4 系统架构和算法实现4.1 计算量分析C2C交易平台的交易数据非常庞大。以淘宝网为例，2009上半年，在线商品数目远超了1.4亿，交易量达到809亿元，此时注册用户为1.45亿。如果将商品和用户之间的链接关系表示成有向图的邻接矩阵的形式，可以得到一个非常巨大的（N>100,000,000)，却非常稀疏的矩阵。因此一次计算CR的过程计算量是非常大的，而且由于我们采用迭代的方法来逼近最终的CR值，因此往往需要多次重复计算，计算模式复杂，性能也很难得到保证。不仅如此，通过对淘宝网的实际交易情景的了解

14、可知，商铺、商铺所出售的商品、消费者都是随着时间不断变化的。因此对信用的计算架构必须在一定周期下不断进行，才能保证整个数据的正确性。从另外一个角度来看，由于整个交易平台中所有元素之间信用值都是相关的，所以任意一个元素的信用值改变都会带来整个系统的信用值的改变，这也要求每次的计算必须是全局性的。4.2 MapReduce7模型MapReduce是Google公司于2004年提出的一种编程模型。MapReduce是一种专用于处理和产生海量数据的编程模型及其实现，该模型使用一个map函数来处理key/value对，并用它们来产生一系列中间的key/value值对；使用一个reduce函数，根据这些中

15、将结果的key值来合并到一起，模型如下所示：        Map函数由用户编写，输入为一个key/value对，并且产生一些列的中间key/value值对，MapReduce框架负责将这些中间值对按照Key的值相同聚合在一起，并且发送给同一个reduce函数；Reduce函数同样由用户编写，接收一个中间值对的值Key以及对应该Key的一个value的列表。reduce函数将这些值根据用户的请求聚合在以期，并且生成一个较小规模的数据集输出。MapReduce虽然是一个简单的思想，但是却被证明可以表达出非常复杂的算法。该计算模型已经广泛

16、的应用在包括数据挖掘、搜索引擎、日志分析等多个方面。4.3 反向引用信用计算的MapReduce算法我们使用MapReduce的计算模型来计算C2C平台中交易元素的信用评价。    一个比较典型的交易过程可以用下面一段记录来描述： buys from  and gives credit ，  gives credit     一个运行中的C2C平台系统中，每时每刻都会产生大量的这种记录。而我们要作的计算正是基于这种记录。采用MapReduce模型进行编程，我们把整个计算过程分

17、为3个阶段，前一个阶段用来计算商铺中商品的信用度，第二个阶段根据商铺中所售商品的信用度量计算出商铺的信用度量，第三个阶段根据商铺对消费者的反馈评价计算消费者的信用度。阶段一：Map函数的描述如下： Reduce函数的描述如下：首先我们将记录通过map函数进行处理，得到一个中间key/value值对，值对中Key为店铺和所交易商品的组合，Value为进行交易的消费者的信用度以及该消费者对这个商品的评价。这些中间值对中，Key相同的（也即是同一个商铺，同一件商品）的所有购买者的信用度以及对这个商品的评价被发送给同一个reduce函数来处理。该reduce函数通过公式1计算后得到最终的结果

18、商铺A中商品A的信用度。阶段二：得到商铺所有商品的信用度之后，需要计算出商铺的信用度，这也是利用MapReduce过程来计算的，Map、Reduce函数的描述如下：   阶段三：我们利用阶段二中计算出的商铺的信用来计算费者的信用，其Map、Reduce函数的描述如下：      这三个MapReduce阶段是交替进行的，初始时所有的CR都是1，不断迭代的过程中将会逼近这些交易数据所能反应的真实的信用评价。需要注意的是，计算消费者信用值的时候，我们需要对消费者做出评价的商铺的信用值，这一数据通过阶段二的MapReduce任务来

19、获得。4.4 算法分析和策略根据4.3节所述算法可知，在整个迭代计算过程中对上一次迭代中所产生的信用值结果是非常依赖的。每次迭代会产生一个新的和，而所有下一轮计算都需要这两个数据，与此同时每次迭代计算都需要以及。如何快速访问这些数据是关系到算法应用和稳定非常重要的问题。MapReduce框架往往基于一个分布式文件系统实现，一个MapReduce任务的输入来自于分布式文件系统，框架自动根据所处理的数据所在的节点，将任务分配到对应节点执行。我们希望在map和reduce阶段所需要的数据都能尽量在本地获得，而不需要网络访问。我们将C2C平台中所有交易数据抽象为如下格式，保存在分布式文件系统（HDFS

20、）中：也就是说交易系统将一次交易表示成为一个由分隔符分隔开来的，有序的属性列表。一个成功的交易记录依次记录了消费者id、消费者的CR、商铺的id、商铺的CR、物品的id以及在这次交易中消费者给予商品的信用评价，还有店铺给予消费者的信用评价。本算法利用MapReduce实现的关键点在于交易信息不能随着map或者reduce阶段的进行而消失，我们要求在每一次MapReduce任务结束时，输出的文件中都能重建这个交易信息。也即是，每一轮3个阶段MapReduce任务完成之后，我们将获得一个存储在分布式文件系统中的新版本的C2C平台交易数据： 新的交易数据中存放了上一轮计算出的Person和

21、Store的信用度量来进行本轮迭代，而且由于输入格式相同，处理可以循环不停止的进行下去。同时利用MapReduce框架的本地化优化策略，处理中需要网络传输数据的几率相当小的，不会发生数据依赖。4.5 伪码实现该算法的伪代码实现如下所示，三个阶段的输出和输入相连，迭代进行。1，阶段一：void map(TransactionRecord):    Person,CRp,Store,CRs,Item,CRpi,CRsp = TransactionRecord    EmitIntermediate(Store,Item,CRp, CRpi

22、,Person, CRs, CRsp)void reduce(Key, Values):    Store, Item = Key    for each CRp, CRpi, Person, CRs, CRsp in Values:        CR += CRp * CRpi / CrNumPersonp        RebuiltList += Person, CRp, CRpi, CRsp, Item  

23、  Emit( Store, Item, (CR*(1-p) + p), RebuiltList )2，阶段二：void map(Key, Value):    Store, Item, CRs = Key    CR, RebuiltList = Value    EmitIntermediate(Store, Item, CR, RebuiltList)void reduce(Key, Values):    Store = Key   &#

24、160;for each Item, CR, RebuiltList in Values:        CRs += CR * weight    for each Person, CRp, CRpi, CRsp,Item in RebuiltList:        TransactionRecordNew = Person, CRp, Store, CRs, Item, CRpi, CRsp        Em

25、it(TransactionRecordNew)3，阶段三:void map(TransactionRecord):    Person,CRp,Store,CRs,Item,CRpi,CRsp = TransactionRecord    EmitIntermediate(Person, CRs, CRsp,Store, Item, CRpi)void reduce(Key, Values):    Person = Key    for each CRs, CRsp,St

26、ore, Item, CRpi in values:        CRp += CRs * CRsp / CrNumStoreStore    for each CRs, CRsp,Store, Item, CRpi in values:        TransactionRecordNew = Person, CRp, Store, CRs, Item, CRpi, CRsp        Emit(Trans

27、actionRecordNew)5 实验和性能评测Hadoop8是一个基于Apache开放源码协议的开源项目，最核心的组成部分为一个基于Java实现的分布式文件系统HDFS9以及在此文件系统基础之上的MapReduce框架。Hadoop自提出以来短短几年的时间得到了长足的发展，现在已经开始广泛的使用与工业界，具有稳定运行在大型数据中心（超过2000+节点，1W+处理器）的能力，因此我们在这里也选用Hadoop作为实验平台。我们构造了一个基于Hadoop的小型机群，采用Hadoop-0.19.2。机群共有3台计算机，其中一个为NameNodeServer、一个为JobTrackerServer，

28、3个节点同时都作为TaskTrackerServer来运行。机群共有存储能力360GB，数据复制系数为1。机群中计算机CPU为Core2 Duo E6550， 2G内存。由于本实验牵扯到比较敏感的交易数据，无法获得大量有效的交易数据。我们通过编写MapReduce程序来生成海量的C2C平台中用户交易数据进行模拟。首先是在较大数据规模的情况下的执行时间，图2中x轴代表交易数据量的大小，纵轴代表得到最终结果的执行时间。由图中我们可以看出，在任务量很大的情况下，使用MapReduce方法来计算信用值的时间也是可以接受的。图2 交易数据量对计算时间的影响。纵轴单位为分钟，以迭代10次为例图3表示同样的

29、交易数据量的情况下，购买者数目的变化对执行时间的影响，可以看出，当系统中消费者的数目较少的情况下，计算性能有少许的提高。图3 同样的交易数据量下，消费者数目的变化对执行时间的影响图4是较小数据规模的用户产生的信用评价图，用来对该模型进行验证。数据来源如表1所示，我们将用户和商品以及商户进行了模拟，通过这些数据计算出最后的信用，跟我们的真实行为对比，可以看出该算法的准确性。表1 交易数据来源定义消费者商铺商品给予评价收到评价张三电子商城U盘55张三小商品城文具34张三电子商城mp445张三小商品城办公用品43李四电子商城mp354李四电子商城U盘54李四小商品城文具34李四小商品城办公用品33图4 根据上表算得的示例信誉6 结语本文根据搜索引擎评价页面的思想，提出了一种基于反向应用的方法计算C2C平台中交易双方信用值的算法，并且提出在基于MapReduce的云计算平台中实现本算法具有较高的扩放性和灵活性，为如何在实际生产环境中使用本算法提供了一些参考。本文提出的基于反向引用的信用计算方法尚未考虑更多的能够影响信用评价的因子，比如很久之前的交易行为和当前较近时期的交易行为对信用评级的作用应该不同，为了防止恶意刷信用的行为应当