基于Kendall tau距离的在线服务信誉度量方法
|
摘要
用户偏好及评价准则不一致导致不同用户对同一服务的评分不可比较,基于评价准则一致性假定的信誉机制不能保证不同服务信誉间具有可比较性,从而用户利用这种信誉进行服务选择时会产生不客观的结果.为此提出一种基于Kendall tau距离的在线服务信誉度量方法.该方法首先定义距离指标以衡量2个评分向量之间的一致性,然后将在线服务信誉度量建模为寻找一个与用户-服务评分矩阵距离最小的信誉向量的最优化问题,最后采用模拟退火算法来求解该优化问题,将得到的信誉向量作为服务信誉.通过实验验证了该方法的合理性和有效性.实验结果表明:该方法能够满足大多数用户的偏好,从而使得用户可以参考该信誉结果做出正确的服务选择决策,并且方法在保证信誉度量效率的同时提高了信誉度量方法的抗操纵性.
Due to the inconsistent user preferences and the inconsistent rating criteria, the ratings given by different users to one service are actually incomparable, and the reputation mechanism based on assumption of the consistent rating criteria cannot guarantee the comparability among different service reputations, which will result in unobjective outcome when the reputations are used to choose services. To improve the objectivity of online services reputation measurement under the circumstance referred above, this paper presents a method of online service reputation measurement based on Kendall tau distance. Firstly, a distance metric is defined to measure the consistency between the two rating vectors. Secondly, the measurement of online service reputation is modeled as an optimization problem to find a reputation vector that minimizes the Kendall tau distance between the reputation vector and the user-service rating matrix. Finally, simulated annealing algorithm is used to solve the optimization problem and the reputation vector is served as a service reputation. The rationality and effectiveness of the method have been verified by experimental study. The experiments show that the method can meet the preferences of most users, so that users can make right services choice decision, and ensure the efficiency while improving the manipulation resistance ability of the reputation measurement method.
Due to the inconsistent user preferences and the inconsistent rating criteria, the ratings given by different users to one service are actually incomparable, and the reputation mechanism based on assumption of the consistent rating criteria cannot guarantee the comparability among different service reputations, which will result in unobjective outcome when the reputations are used to choose services. To improve the objectivity of online services reputation measurement under the circumstance referred above, this paper presents a method of online service reputation measurement based on Kendall tau distance. Firstly, a distance metric is defined to measure the consistency between the two rating vectors. Secondly, the measurement of online service reputation is modeled as an optimization problem to find a reputation vector that minimizes the Kendall tau distance between the reputation vector and the user-service rating matrix. Finally, simulated annealing algorithm is used to solve the optimization problem and the reputation vector is served as a service reputation. The rationality and effectiveness of the method have been verified by experimental study. The experiments show that the method can meet the preferences of most users, so that users can make right services choice decision, and ensure the efficiency while improving the manipulation resistance ability of the reputation measurement method.
引文
[1]Jsang A,Ismail R,Boyd C.A survey of trust and reputation systems for online service provision[J].Decision Support Systems,2007,43(2):618-644
[2]Song Guangxing,Yang Deli,On some problems in the design of online reputation management system in electronic commerce[J].Systems Engineering,2004,22(9):5-9(in Chinese)(宋光兴,杨德礼.电子商务中在线信誉管理系统设计的若干问题研究[J].系统工程,2004,22(9):5-9)
[3]Mao Chen,Singh J P.Computing and using reputations for Internet ratings[C]//Proc of the 3rd ACM Conf on Electronic Commerce.New York:ACM,2001:154-162
[4]Dellarocas C.Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior[C]//Proc of the 2nd ACM Conf on Electronic Commerce.New York:ACM,2000:150-157
[5]He Lijian,Huang Houkuan,Zhang Wei.A survey of trust and reputation systems in multi-agent systems[J].Journal of Computer Research and Development,2008,45(7):1151-1160(in Chinese)(贺利坚,黄厚宽,张伟.多Agent系统中信任和信誉系统研究综述[J].计算机研究与发展,2008,45(7):1151-1160)
[6]Jsang A,Guo Guibing,Pini M S,et al.Combining recommender and reputation systems to produce better online advice[C]//Proc of the 10th Int Conf on Modeling Decisions for Artificial Intelligence.Berlin:Springer,2013:126-138
[7]Allahbakhsh M,Ignjatovic A,Motahari-Nezhad H R,et al.Robust evaluation of products and reviewers in social rating systems[J].World Wide Web,2015,18(1):73-109
[8]Li Jie,Wang Xingwei,Liu Rui.User reputation-based participatory incentive mechanism in social and community intelligence systems[J].Journal of Frontiers of Computer Science and Technology,2015,9(12):1471-1482(in Chinese)(李婕,王兴伟,刘睿.社群智能系统中基于用户信誉度的激励机制[J].计算机科学与探索,2015,9(12):1471-1482)
[9]Betzler N,Fellows M R,Guo Jiong,et al.Fixed-parameter algorithms for Kemeny rankings[J].Theoretical Computer Science,2009,410(45):4554-4570
[10]Yuan Yao,Ruohomaas S,Feng Xu.Addressing common vulnerabilities of reputation systems for electronic commerce[J].Journal of Theoretical and Applied Electronic Commerce Research,2012,7(1):1-20
[11]Wu Yan,Yan Chungang,Ding Zhijun,et al.A novel method for calculating service reputation[J].IEEETransactions on Automation Science&Engineering,2013,10(3):634-642
[12]Guang Ling,King I,Lyu M R.A unified framework for reputation estimation in online rating systems[C]//Proc of the 22nd Int Joint Conf on Artificial Intelligence.Palo Alto,CA:AAAI Press,2013:2670-2676
[13]Li Wei,Sun Qibo,Wang Shangguang.Context-based Web service reputation measurement[C]//Proc of the 17th IEEEInt Conf on Computational Science and Engineering.New York:IEEE Computer Society,2014:1489-1496
[14]Fu Xiaodong,Zou Ping,Jiang Ying.Web service reputation measurement based on quality of service similarity[J].Computer Integrated Manufacturing System,2008,14(3):619-624(in Chinese)(付晓东,邹平,姜瑛.基于质量相似度的Web服务信誉度量[J].计算机集成制造系统,2008,14(3):619-624)
[15]Zhang Haiteng,Shao Zhiqing,Zheng Hong,et al.Web service reputation evaluation based on QoS measurement[J].The Scientific World Journal,2014,2014(1):145-156
[16]Wang Shangguang,Sun Qibo,Yang Fangchun.Reputation evaluation approach in Web service selection[J].Journal of Software,2012,23(6):1350-1367(in Chinese)(王尚广,孙其博,杨放春.Web服务选择中信誉度评估方法[J].软件学报,2012,23(6):1350-1367)
[17]Chen Tingwei,Lei Jing.Research on service reputation evaluation method based on cloud model[J].International Journal of Intelligent Information Systems,2015,4(1):8-15
[18]Manaman H S,Jamali S,AleAhmad A.Online reputation measurement of companies based on user-generated content in online social networks[J].Computers in Human Behavior,2016,54(1):94-100
[19]Malik Z,Akbar I,Bouguettaya A.Web services reputation assessment using a hidden Markov model[C]//Proc of the7th Int Joint Conf on Service-Oriented Computing.Berlin:Springer,2009:576-591
[20]Blin G,Crochemore M,Hamel S,et al.Finding the median of three permutations under the Kendall-tau distance[C]//Proc of the 7th Int Conf on Permutation Patterns.Cambridge,UK:Cambridge University Press,2009:1-6
[21]Fu Xiaodong,Yue Kun,Liu Li,et al.Aggregating ordinal user preferences for effective reputation computation of online services[C]//Proc of the 23rd IEEE Int Conf on Web Services.New York:IEEE Computer Society,2016:554-561
[22]Ali A,MeilM.Experiments with Kemeny ranking:What works when?[J].Mathematical Social Sciences,2012,64(1):28-40
[23]Du Zhihui,Li Sanli,Wu Mengyue,et al.Hybrid SPMDsimulated annealing algorithm and its applications[J].Chinese Journal of Computers,2001,24(1):91-98(in Chinese)(都志辉,李三立,吴梦月,等.混合SPMD模拟退火算法及其应用[J].计算机学报,2001,24(1):91-98)
[24]He Yizhao,Wang Xizhao,Li Wenbin,et al.Research on genetic algorithms for the discounted{0-1}knapsack problem[J].Chinese Journal of Computers,2016,39(12):2614-2630(in Chinese)(贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630)
[25]Mansour N,El-Fakih K.Simulated annealing and genetic algorithms for optimal regression testing[J].Journal of Software Maintenance Research&Practice,2015,11(1):19-34
[26]Aarts E H L,Korst J.Simulated annealing and Boltzmann machines:A stochastic approach to combinatorial optimization[J].Siam Review,1988,12(2):323-323
[27]Fishburn P C.The Theory of Social Choice[M].Princeton,NJ:Princeton University Press,2015:80-109
① http://www.grouplens.org/node/73
[2]Song Guangxing,Yang Deli,On some problems in the design of online reputation management system in electronic commerce[J].Systems Engineering,2004,22(9):5-9(in Chinese)(宋光兴,杨德礼.电子商务中在线信誉管理系统设计的若干问题研究[J].系统工程,2004,22(9):5-9)
[3]Mao Chen,Singh J P.Computing and using reputations for Internet ratings[C]//Proc of the 3rd ACM Conf on Electronic Commerce.New York:ACM,2001:154-162
[4]Dellarocas C.Immunizing online reputation reporting systems against unfair ratings and discriminatory behavior[C]//Proc of the 2nd ACM Conf on Electronic Commerce.New York:ACM,2000:150-157
[5]He Lijian,Huang Houkuan,Zhang Wei.A survey of trust and reputation systems in multi-agent systems[J].Journal of Computer Research and Development,2008,45(7):1151-1160(in Chinese)(贺利坚,黄厚宽,张伟.多Agent系统中信任和信誉系统研究综述[J].计算机研究与发展,2008,45(7):1151-1160)
[6]Jsang A,Guo Guibing,Pini M S,et al.Combining recommender and reputation systems to produce better online advice[C]//Proc of the 10th Int Conf on Modeling Decisions for Artificial Intelligence.Berlin:Springer,2013:126-138
[7]Allahbakhsh M,Ignjatovic A,Motahari-Nezhad H R,et al.Robust evaluation of products and reviewers in social rating systems[J].World Wide Web,2015,18(1):73-109
[8]Li Jie,Wang Xingwei,Liu Rui.User reputation-based participatory incentive mechanism in social and community intelligence systems[J].Journal of Frontiers of Computer Science and Technology,2015,9(12):1471-1482(in Chinese)(李婕,王兴伟,刘睿.社群智能系统中基于用户信誉度的激励机制[J].计算机科学与探索,2015,9(12):1471-1482)
[9]Betzler N,Fellows M R,Guo Jiong,et al.Fixed-parameter algorithms for Kemeny rankings[J].Theoretical Computer Science,2009,410(45):4554-4570
[10]Yuan Yao,Ruohomaas S,Feng Xu.Addressing common vulnerabilities of reputation systems for electronic commerce[J].Journal of Theoretical and Applied Electronic Commerce Research,2012,7(1):1-20
[11]Wu Yan,Yan Chungang,Ding Zhijun,et al.A novel method for calculating service reputation[J].IEEETransactions on Automation Science&Engineering,2013,10(3):634-642
[12]Guang Ling,King I,Lyu M R.A unified framework for reputation estimation in online rating systems[C]//Proc of the 22nd Int Joint Conf on Artificial Intelligence.Palo Alto,CA:AAAI Press,2013:2670-2676
[13]Li Wei,Sun Qibo,Wang Shangguang.Context-based Web service reputation measurement[C]//Proc of the 17th IEEEInt Conf on Computational Science and Engineering.New York:IEEE Computer Society,2014:1489-1496
[14]Fu Xiaodong,Zou Ping,Jiang Ying.Web service reputation measurement based on quality of service similarity[J].Computer Integrated Manufacturing System,2008,14(3):619-624(in Chinese)(付晓东,邹平,姜瑛.基于质量相似度的Web服务信誉度量[J].计算机集成制造系统,2008,14(3):619-624)
[15]Zhang Haiteng,Shao Zhiqing,Zheng Hong,et al.Web service reputation evaluation based on QoS measurement[J].The Scientific World Journal,2014,2014(1):145-156
[16]Wang Shangguang,Sun Qibo,Yang Fangchun.Reputation evaluation approach in Web service selection[J].Journal of Software,2012,23(6):1350-1367(in Chinese)(王尚广,孙其博,杨放春.Web服务选择中信誉度评估方法[J].软件学报,2012,23(6):1350-1367)
[17]Chen Tingwei,Lei Jing.Research on service reputation evaluation method based on cloud model[J].International Journal of Intelligent Information Systems,2015,4(1):8-15
[18]Manaman H S,Jamali S,AleAhmad A.Online reputation measurement of companies based on user-generated content in online social networks[J].Computers in Human Behavior,2016,54(1):94-100
[19]Malik Z,Akbar I,Bouguettaya A.Web services reputation assessment using a hidden Markov model[C]//Proc of the7th Int Joint Conf on Service-Oriented Computing.Berlin:Springer,2009:576-591
[20]Blin G,Crochemore M,Hamel S,et al.Finding the median of three permutations under the Kendall-tau distance[C]//Proc of the 7th Int Conf on Permutation Patterns.Cambridge,UK:Cambridge University Press,2009:1-6
[21]Fu Xiaodong,Yue Kun,Liu Li,et al.Aggregating ordinal user preferences for effective reputation computation of online services[C]//Proc of the 23rd IEEE Int Conf on Web Services.New York:IEEE Computer Society,2016:554-561
[22]Ali A,MeilM.Experiments with Kemeny ranking:What works when?[J].Mathematical Social Sciences,2012,64(1):28-40
[23]Du Zhihui,Li Sanli,Wu Mengyue,et al.Hybrid SPMDsimulated annealing algorithm and its applications[J].Chinese Journal of Computers,2001,24(1):91-98(in Chinese)(都志辉,李三立,吴梦月,等.混合SPMD模拟退火算法及其应用[J].计算机学报,2001,24(1):91-98)
[24]He Yizhao,Wang Xizhao,Li Wenbin,et al.Research on genetic algorithms for the discounted{0-1}knapsack problem[J].Chinese Journal of Computers,2016,39(12):2614-2630(in Chinese)(贺毅朝,王熙照,李文斌,等.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630)
[25]Mansour N,El-Fakih K.Simulated annealing and genetic algorithms for optimal regression testing[J].Journal of Software Maintenance Research&Practice,2015,11(1):19-34
[26]Aarts E H L,Korst J.Simulated annealing and Boltzmann machines:A stochastic approach to combinatorial optimization[J].Siam Review,1988,12(2):323-323
[27]Fishburn P C.The Theory of Social Choice[M].Princeton,NJ:Princeton University Press,2015:80-109
① http://www.grouplens.org/node/73