基于反向引用的電子商務(wù)信用評價(jià)算法及其在云計(jì)算平臺中的實(shí)現(xiàn)

1、基于反向引用的電子商務(wù)信用評價(jià)算法及其在云計(jì)算平臺中的實(shí)現(xiàn)Credit Evaluation in E-business Based on Inverted Reference and a MapReduce Implementation代棟 Dai Dong 楊峰Yang Feng中國科學(xué)技術(shù)大學(xué)蘇州研究院，蘇州， 215123Suzhou Institute for Advance Study of USTC, Suzhou摘要隨著網(wǎng)上交易的興起，C2C平臺中買賣雙方的信用評價(jià)成為影響電子商務(wù)成敗的關(guān)鍵因素，傳統(tǒng)的信用評價(jià)體系無法全面真實(shí)的反應(yīng)一個(gè)網(wǎng)上店鋪的信用，在實(shí)際的運(yùn)營中反而帶來了很

2、多信用欺詐問題。淘寶網(wǎng)在發(fā)展的過程中，不斷提出新的信用評價(jià)方法，極大的改進(jìn)了信用評價(jià)體系，但是由于采取的措施受到系統(tǒng)平臺和評價(jià)體系模型的因素，不夠靈活和準(zhǔn)確。本文考慮了在C2C平臺中交易的商鋪、個(gè)人的關(guān)系，提出了采用搜索引擎中的頁面比重排序算法對交易歷史進(jìn)行分析，充分考慮了C2C交易中各種影響商鋪或個(gè)人信譽(yù)的因素及其權(quán)重。并且，在該算法的基礎(chǔ)上提出了在云計(jì)算平臺中，構(gòu)建和實(shí)現(xiàn)這一算法的方法，并且針對實(shí)現(xiàn)策略進(jìn)行了性能分析。該信用評價(jià)模型相比較傳統(tǒng)模型更能夠阻止惡意信用欺詐行為，并且由于采用云計(jì)算平臺，相比傳統(tǒng)方法更加高效、擴(kuò)放性更好。關(guān)鍵字電子商務(wù)；網(wǎng)上交易；信用評價(jià)；搜索引擎；PageRan

3、k；云計(jì)算；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 引言根據(jù)正望咨詢的調(diào)查顯示，2009年我國有1.3億消費(fèi)者共計(jì)在網(wǎng)上購買了2670億元的商品，比2008年實(shí)現(xiàn)了90.7%的增長。2009年，在經(jīng)濟(jì)危機(jī)的大形勢下，中國電子商務(wù)保持較快的增長速度，其中B2B市場保持了20%的增長率，C2C市場比2008年增長了一倍，而B2C市場交易額更是達(dá)到2008年的2倍【1】。在電子商務(wù)

7、大發(fā)展的形式之下，誠信問題逐漸成為影響電子商務(wù)進(jìn)一步發(fā)展的重大阻礙，因此誠信體系的構(gòu)建也就網(wǎng)規(guī)體系的根本和核心【2】。國內(nèi)C2C電子商務(wù)的發(fā)展主要以淘寶網(wǎng)、易趣網(wǎng)、拍拍網(wǎng)為主，其中淘寶規(guī)模最大，也最具有代表性【3】。淘寶網(wǎng)所面臨的誠信問題包括：宣傳與實(shí)際商品不符、商品售后服務(wù)缺失，信用炒作，套取誠信、惡意競拍等。其中信用炒作會導(dǎo)致失信行為無法體現(xiàn)在后續(xù)交易中，如果不能很好的對信用機(jī)制進(jìn)行改進(jìn)，長此以往將影響整個(gè)電子商務(wù)平臺的誠信氛圍。2 影響信用評價(jià)的因素一個(gè)典型的C2C平臺，主要包括對商鋪、商鋪中的商品、消費(fèi)者三種個(gè)體的信用評價(jià)45。其中商鋪是商品的集合地。對商鋪的信用評價(jià)往往代表了在C2C

8、平臺中商品出售者的信譽(yù)。商品出售者可能是一個(gè)獨(dú)立個(gè)體或者一個(gè)公司，但是其對外表現(xiàn)為統(tǒng)一的商鋪信用；商鋪中所有商品的信用評價(jià)和商鋪的信用評價(jià)是息息相關(guān)的，但是具體到商品的信用評價(jià)，則不僅僅可以反映C2C中賣家的信用，也可以反應(yīng)出非賣家因素導(dǎo)致的商品信用的波動。比如某項(xiàng)商品的生產(chǎn)商對產(chǎn)品質(zhì)量把握出現(xiàn)差錯(cuò)，當(dāng)然，也可能在普通賣家中出現(xiàn)明星商品。因此商鋪中商品的信用評價(jià)更加準(zhǔn)確、真實(shí)，在購買特定商品時(shí)可以提供更好的參考。最后，消費(fèi)者的信用評價(jià)來自于賣家，我們鼓勵(lì)消費(fèi)者保護(hù)自己的賬號，通過機(jī)制激勵(lì)消費(fèi)者賬號的長期使用，C2C平臺是一個(gè)向消費(fèi)者展示商家的平臺，因此對消費(fèi)者的信用評價(jià)主要用來生成商家及商品的

9、信用評價(jià)。影響商鋪中商品信用評價(jià)的因素主要包括如下幾個(gè)方面：l 商品被購買的次數(shù)l 商品被消費(fèi)者給予的評價(jià)l 給予評價(jià)的消費(fèi)者本身的信用度如果一定數(shù)目的信用度較高的用戶給予店鋪中某商品較高的評價(jià)，那么我們就認(rèn)為該商品具有較高的信用值，也意味著更值得購買。影響商鋪的信用評價(jià)的因素主要包括幾個(gè)方面：l 商鋪中所售商品的信用度l 所出售各種商品占業(yè)務(wù)量的比重l 對交易中消費(fèi)者的評價(jià)如果商鋪中業(yè)務(wù)量中占絕大多數(shù)的商品都有較高的信譽(yù)度，那么該商鋪也一定具有較高的信用度，更值得從該商鋪中選購商品。這里需要注重的是，商鋪中所賣商品組成商鋪信譽(yù)的時(shí)候，其權(quán)重是不同的，該權(quán)值由商品價(jià)格占店鋪總交易量的比重而定，

10、防止商鋪通過大量出售非常便宜的商品來進(jìn)行信用欺騙。影響消費(fèi)者信用評價(jià)的因素主要包括：l 消費(fèi)者所購買商品時(shí)得到店鋪的評價(jià)l 評價(jià)消費(fèi)者的店鋪本身的信用l 對交易中店鋪的評價(jià)如果一個(gè)消費(fèi)者在很多交易中都得到商家的好評，說明該消費(fèi)者能夠在交易中做到誠實(shí)守信，因此其信用度也會較高。為了防止惡意影響信用評價(jià)體系的可能性，我們在影響商鋪和消費(fèi)者的因素中加入對對方的評價(jià)，如果對一個(gè)信用度較高的個(gè)體給予很低的評價(jià)，或者對一個(gè)信用較低的個(gè)體給予較高的評價(jià)，其權(quán)重都會很低。3 基于反向引用的評價(jià)方法反向引用6是一種搜索引擎中用來評價(jià)網(wǎng)頁重要程度的方法，其原理非常直觀，即認(rèn)為大量引用別的頁面的網(wǎng)頁并不一定是好的，

11、但是被大量頁面引用的網(wǎng)頁，往往是大家認(rèn)為非常重要的。因此相對于引用來說，反向引用更為重要。在C2C平臺中進(jìn)行信用度計(jì)算的模型和搜索引擎的頁面排名類似。一次交易的一個(gè)評價(jià)相當(dāng)于一個(gè)指向所交易的商品的鏈接，與超鏈接不同的是，這個(gè)鏈接還有權(quán)重即交易時(shí)的評價(jià)值；最終C2C平臺中所有個(gè)體的信用評價(jià)都是由這個(gè)鏈接系統(tǒng)生成的?？紤]一次交易的情形：某商鋪的兩件商品Ia和Ib，用戶c1、c2作為兩個(gè)消費(fèi)者購買了這兩件商品，并給予了交易評價(jià)、同時(shí)商戶也根據(jù)這兩次交易的情況給予兩位消費(fèi)者評價(jià)，這樣便產(chǎn)生了多個(gè)反向鏈接，如圖1所示。圖1 一次交易產(chǎn)生的消費(fèi)者C和商品I之間的鏈接關(guān)系這里我們用CR(object)函數(shù)來

12、表示整個(gè)交易系統(tǒng)中一個(gè)實(shí)體的信用度量。計(jì)算一個(gè)實(shí)體的信用度量只需要考慮鏈接到該實(shí)體的別的實(shí)體的信用值。引入公式：該公式表明, CR(object)表示對象object的信用值。計(jì)算I的信用值，要通過所有購買I的消費(fèi)者的信用值來計(jì)算，每一個(gè)消費(fèi)者在長期的購買過程中必然會帶有大量的交易和評價(jià)信息，對當(dāng)前I評價(jià)為W，那么實(shí)際計(jì)入I的評價(jià)應(yīng)為W占用戶所有對外評價(jià)的比重。任何一個(gè)實(shí)體的信用度量可以表示為所有引用至該節(jié)點(diǎn)的所有節(jié)點(diǎn)的單位信用度量的加權(quán)和。公式中是個(gè)常量，可以隨應(yīng)用調(diào)整，我們這里把其設(shè)置為0.85。表示對的信用評價(jià)，按照：好、較好、一般、較差、差的標(biāo)準(zhǔn)對應(yīng)為5,4,3,2,1的權(quán)值。由于系統(tǒng)

13、初始時(shí)沒有權(quán)值，我們設(shè)定所有元素的初始權(quán)值都為1，通過多次迭代計(jì)算出最終每一個(gè)節(jié)點(diǎn)的信用度量。4 系統(tǒng)架構(gòu)和算法實(shí)現(xiàn)4.1 計(jì)算量分析C2C交易平臺的交易數(shù)據(jù)非常龐大。以淘寶網(wǎng)為例，2009上半年，在線商品數(shù)目遠(yuǎn)超了1.4億，交易量達(dá)到809億元，此時(shí)注冊用戶為1.45億。如果將商品和用戶之間的鏈接關(guān)系表示成有向圖的鄰接矩陣的形式，可以得到一個(gè)非常巨大的（N100,000,000)，卻非常稀疏的矩陣。因此一次計(jì)算CR的過程計(jì)算量是非常大的，而且由于我們采用迭代的方法來逼近最終的CR值，因此往往需要多次重復(fù)計(jì)算，計(jì)算模式復(fù)雜，性能也很難得到保證。不僅如此，通過對淘寶網(wǎng)的實(shí)際交易情景的了解可知，商

14、鋪、商鋪所出售的商品、消費(fèi)者都是隨著時(shí)間不斷變化的。因此對信用的計(jì)算架構(gòu)必須在一定周期下不斷進(jìn)行，才能保證整個(gè)數(shù)據(jù)的正確性。從另外一個(gè)角度來看，由于整個(gè)交易平臺中所有元素之間信用值都是相關(guān)的，所以任意一個(gè)元素的信用值改變都會帶來整個(gè)系統(tǒng)的信用值的改變，這也要求每次的計(jì)算必須是全局性的。4.2 MapReduce7模型MapReduce是Google公司于2004年提出的一種編程模型。MapReduce是一種專用于處理和產(chǎn)生海量數(shù)據(jù)的編程模型及其實(shí)現(xiàn)，該模型使用一個(gè)map函數(shù)來處理key/value對，并用它們來產(chǎn)生一系列中間的key/value值對；使用一個(gè)reduce函數(shù)，根據(jù)這些中將結(jié)果的

15、key值來合并到一起，模型如下所示： Map函數(shù)由用戶編寫，輸入為一個(gè)key/value對，并且產(chǎn)生一些列的中間key/value值對，MapReduce框架負(fù)責(zé)將這些中間值對按照Key的值相同聚合在一起，并且發(fā)送給同一個(gè)reduce函數(shù)；Reduce函數(shù)同樣由用戶編寫，接收一個(gè)中間值對的值Key以及對應(yīng)該Key的一個(gè)value的列表。reduce函數(shù)將這些值根據(jù)用戶的請求聚合在以期，并且生成一個(gè)較小規(guī)模的數(shù)據(jù)集輸出。MapReduce雖然是一個(gè)簡單的思想，但是卻被證明可以表達(dá)出非常復(fù)雜的算法。該計(jì)算模型已經(jīng)廣泛的應(yīng)用在包括數(shù)據(jù)挖掘、搜索引擎、日志分析等多個(gè)方面。4.3 反向引用信用計(jì)算的Ma

16、pReduce算法我們使用MapReduce的計(jì)算模型來計(jì)算C2C平臺中交易元素的信用評價(jià)。 一個(gè)比較典型的交易過程可以用下面一段記錄來描述：buys fromand gives credit ，givescredit 一個(gè)運(yùn)行中的C2C平臺系統(tǒng)中，每時(shí)每刻都會產(chǎn)生大量的這種記錄。而我們要作的計(jì)算正是基于這種記錄。采用MapReduce模型進(jìn)行編程，我們把整個(gè)計(jì)算過程分為3個(gè)階段，前一個(gè)階段用來計(jì)算商鋪中商品的信用度，第二個(gè)階段根據(jù)商鋪中所售商品的信用度量計(jì)算出商鋪的信用度量，第三個(gè)階段根據(jù)商鋪對消費(fèi)者的反饋評價(jià)計(jì)算消費(fèi)者的信用度。階段一：Map函數(shù)的描述如下：Reduce函數(shù)的描述如下：首先

17、我們將記錄通過map函數(shù)進(jìn)行處理，得到一個(gè)中間key/value值對，值對中Key為店鋪和所交易商品的組合，Value為進(jìn)行交易的消費(fèi)者的信用度以及該消費(fèi)者對這個(gè)商品的評價(jià)。這些中間值對中，Key相同的（也即是同一個(gè)商鋪，同一件商品）的所有購買者的信用度以及對這個(gè)商品的評價(jià)被發(fā)送給同一個(gè)reduce函數(shù)來處理。該reduce函數(shù)通過公式1計(jì)算后得到最終的結(jié)果商鋪A中商品A的信用度。階段二：得到商鋪所有商品的信用度之后，需要計(jì)算出商鋪的信用度，這也是利用MapReduce過程來計(jì)算的，Map、Reduce函數(shù)的描述如下： 階段三：我們利用階段二中計(jì)算出的商鋪的信用來計(jì)算費(fèi)者的信用，其Map、Re

18、duce函數(shù)的描述如下： 這三個(gè)MapReduce階段是交替進(jìn)行的，初始時(shí)所有的CR都是1，不斷迭代的過程中將會逼近這些交易數(shù)據(jù)所能反應(yīng)的真實(shí)的信用評價(jià)。需要注意的是，計(jì)算消費(fèi)者信用值的時(shí)候，我們需要對消費(fèi)者做出評價(jià)的商鋪的信用值，這一數(shù)據(jù)通過階段二的MapReduce任務(wù)來獲得。4.4 算法分析和策略根據(jù)4.3節(jié)所述算法可知，在整個(gè)迭代計(jì)算過程中對上一次迭代中所產(chǎn)生的信用值結(jié)果是非常依賴的。每次迭代會產(chǎn)生一個(gè)新的和，而所有下一輪計(jì)算都需要這兩個(gè)數(shù)據(jù)，與此同時(shí)每次迭代計(jì)算都需要以及。如何快速訪問這些數(shù)據(jù)是關(guān)系到算法應(yīng)用和穩(wěn)定非常重要的問題。MapReduce框架往往基于一個(gè)分布式文件系統(tǒng)實(shí)現(xiàn)，

19、一個(gè)MapReduce任務(wù)的輸入來自于分布式文件系統(tǒng)，框架自動根據(jù)所處理的數(shù)據(jù)所在的節(jié)點(diǎn)，將任務(wù)分配到對應(yīng)節(jié)點(diǎn)執(zhí)行。我們希望在map和reduce階段所需要的數(shù)據(jù)都能盡量在本地獲得，而不需要網(wǎng)絡(luò)訪問。我們將C2C平臺中所有交易數(shù)據(jù)抽象為如下格式，保存在分布式文件系統(tǒng)（HDFS）中：也就是說交易系統(tǒng)將一次交易表示成為一個(gè)由分隔符分隔開來的，有序的屬性列表。一個(gè)成功的交易記錄依次記錄了消費(fèi)者id、消費(fèi)者的CR、商鋪的id、商鋪的CR、物品的id以及在這次交易中消費(fèi)者給予商品的信用評價(jià)，還有店鋪給予消費(fèi)者的信用評價(jià)。本算法利用MapReduce實(shí)現(xiàn)的關(guān)鍵點(diǎn)在于交易信息不能隨著map或者reduce階

20、段的進(jìn)行而消失，我們要求在每一次MapReduce任務(wù)結(jié)束時(shí)，輸出的文件中都能重建這個(gè)交易信息。也即是，每一輪3個(gè)階段MapReduce任務(wù)完成之后，我們將獲得一個(gè)存儲在分布式文件系統(tǒng)中的新版本的C2C平臺交易數(shù)據(jù)：新的交易數(shù)據(jù)中存放了上一輪計(jì)算出的Person和Store的信用度量來進(jìn)行本輪迭代，而且由于輸入格式相同，處理可以循環(huán)不停止的進(jìn)行下去。同時(shí)利用MapReduce框架的本地化優(yōu)化策略，處理中需要網(wǎng)絡(luò)傳輸數(shù)據(jù)的幾率相當(dāng)小的，不會發(fā)生數(shù)據(jù)依賴。4.5 偽碼實(shí)現(xiàn)該算法的偽代碼實(shí)現(xiàn)如下所示，三個(gè)階段的輸出和輸入相連，迭代進(jìn)行。1，階段一：void map(TransactionRecord

21、): Person,CRp,Store,CRs,Item,CRpi,CRsp = TransactionRecord EmitIntermediate(Store,Item,CRp, CRpi,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 Emit( Store, It

22、em, (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 for each Item, CR, RebuiltList in Values: CRs += CR * weight for each Person, CRp, CRpi, CRsp,Item in Rebuil

23、tList: TransactionRecordNew = Person, CRp, Store, CRs, Item, CRpi, CRsp Emit(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,

24、Store, 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(TransactionRecordNew)5 實(shí)驗(yàn)和性能評測Hadoop8是一個(gè)基于Apache開放源碼協(xié)議的開源項(xiàng)目，最核心的組成部分為一個(gè)基于Java實(shí)現(xiàn)的分布式文件系統(tǒng)HDFS9以及在此文件系統(tǒng)基礎(chǔ)之上的MapReduce框架。

25、Hadoop自提出以來短短幾年的時(shí)間得到了長足的發(fā)展，現(xiàn)在已經(jīng)開始廣泛的使用與工業(yè)界，具有穩(wěn)定運(yùn)行在大型數(shù)據(jù)中心（超過2000+節(jié)點(diǎn)，1W+處理器）的能力，因此我們在這里也選用Hadoop作為實(shí)驗(yàn)平臺。我們構(gòu)造了一個(gè)基于Hadoop的小型機(jī)群，采用Hadoop-。機(jī)群共有3臺計(jì)算機(jī)，其中一個(gè)為NameNodeServer、一個(gè)為JobTrackerServer，3個(gè)節(jié)點(diǎn)同時(shí)都作為TaskTrackerServer來運(yùn)行。機(jī)群共有存儲能力360GB，數(shù)據(jù)復(fù)制系數(shù)為1。機(jī)群中計(jì)算機(jī)CPU為Core2 Duo E6550， 2G內(nèi)存。由于本實(shí)驗(yàn)牽扯到比較敏感的交易數(shù)據(jù)，無法獲得大量有效的交易數(shù)據(jù)。我

26、們通過編寫MapReduce程序來生成海量的C2C平臺中用戶交易數(shù)據(jù)進(jìn)行模擬。首先是在較大數(shù)據(jù)規(guī)模的情況下的執(zhí)行時(shí)間，圖2中x軸代表交易數(shù)據(jù)量的大小，縱軸代表得到最終結(jié)果的執(zhí)行時(shí)間。由圖中我們可以看出，在任務(wù)量很大的情況下，使用MapReduce方法來計(jì)算信用值的時(shí)間也是可以接受的。圖2 交易數(shù)據(jù)量對計(jì)算時(shí)間的影響?？v軸單位為分鐘，以迭代10次為例圖3表示同樣的交易數(shù)據(jù)量的情況下，購買者數(shù)目的變化對執(zhí)行時(shí)間的影響，可以看出，當(dāng)系統(tǒng)中消費(fèi)者的數(shù)目較少的情況下，計(jì)算性能有少許的提高。圖3 同樣的交易數(shù)據(jù)量下，消費(fèi)者數(shù)目的變化對執(zhí)行時(shí)間的影響圖4是較小數(shù)據(jù)規(guī)模的用戶產(chǎn)生的信用評價(jià)圖，用來對該模型進(jìn)行

27、驗(yàn)證。數(shù)據(jù)來源如表1所示，我們將用戶和商品以及商戶進(jìn)行了模擬，通過這些數(shù)據(jù)計(jì)算出最后的信用，跟我們的真實(shí)行為對比，可以看出該算法的準(zhǔn)確性。表1 交易數(shù)據(jù)來源定義消費(fèi)者商鋪商品給予評價(jià)收到評價(jià)張三電子商城U盤55張三小商品城文具34張三電子商城mp445張三小商品城辦公用品43李四電子商城mp354李四電子商城U盤54李四小商品城文具34李四小商品城辦公用品33圖4 根據(jù)上表算得的示例信譽(yù)6 結(jié)語本文根據(jù)搜索引擎評價(jià)頁面的思想，提出了一種基于反向應(yīng)用的方法計(jì)算C2C平臺中交易雙方信用值的算法，并且提出在基于MapReduce的云計(jì)算平臺中實(shí)現(xiàn)本算法具有較高的擴(kuò)放性和靈活性，為如何在實(shí)際生產(chǎn)環(huán)境中