在投票系统中，每个投票人按照自己对候选人的认可程度，对候选人按照从高到低的顺序进行排名，从而得到大量的有序列表.为了生成一个综合投票结果，需要找到一种合理有效的列表合并算法，综合分析这些列表数据，将其合并为一个综合列表.本文提出一种基于可信度的列表合并算法.在现实中，不同投票人的可信度一般不相同，因此不同投票人所提供的排名信息的可信度也不同；同时，同一个投票人对不同候选人的了解程度也是不相同的，导致由同一个投票人提供的关于不同候选人的排名信息的可信度也不相同.基于这些启发式规则，本文提出一种基于可信度的列表合并算法.该算法首先通过综合分析众多投票列表，度量出投票人的可信度以及对候选人的了知度；然后综合以上二者信息，进一步计算出每个列表中每条排名信息的可信度；最后基于已经得到的排名信息的可信度值，综合多个投票列表中关于相同候选人的排名信息，让那些高可信度的排名信息在综合排名中发挥更大的作用，从而得到候选人的综合排名结果.

现有的投票算法大致可以归为两类：一类是单议席投票算法^{[1, 2, 3]}，如波达投票法BC(Borda count)^{[2, 3]}等；与之对应的是多议席投票算法^{[4, 5, 6]}，如单一可转移票制STV(single transferable voting)^{[4, 5]}等；第二类是随机投票算法^{[7, 8]}.这些算法均没有考虑信息的可信度因素，使得最终得到的投票结果不是很理想.基于可信度的算法在其他领域(如实体识别^[9]、元搜索^[10]等)也有涉及，但迄今为止，投票分析系统中关于投票人可信度方面的研究尚未见报道.本文提出一种新的适用于投票系统的计算可信度的方法，用以计算每个投票人以及投票信息的可信度，并将之应用到投票结果的综合分析中.

本文算法的基本标记符号如下：m代表候选人数量；n代表投票人数量；e_i指代第i个候选人；v_k指代第k个投票人；由投票人v_k给出的排名列表用L^k表示；投票人v_k的可信度为c^k；第i个候选人e_i在列表L^k中的排名用符号r_i^k表示；符号f_i^k用来表示投票人v_k对候选人e_i的排名r_i^k的“了知度”；而符号c_i^k则代表排名信息r_i^k的可信度；d_ij^k代表e_i到e_j在列表L^k中的排名距离，其值为d_ij^k=r_j^k－r_i^k(1≤i<j≤m)；与符号f_i^k类似，本文中用f_ij^k代表投票人v_k对差距信息d_ij^k的“了知度”；同时符号c_ij^k代表排名信息d_ij^k的可信度；最后符号s_i^k=m－r_i^k代表候选人e_i在列表中的得分.

一个投票系统一般包含候选人、投票人、投票列表以及采用的统计算法.其目的是根据该统计算法和相关投票列表数据，得到一个综合投票结果列表.表 1中给出一个全文通用的例子.假设有3个候选人，5个投票人，一共得到5个有序投票列表，投票结果如表 1所示.

表 1

Table 1

表 1(Table 1)

表 1 投票列表 Table 1 Voting lists ei L1 L2 L3 L4 L5 e1 2 3 1 1 2 e2 3 2 3 2 3 e3 1 1 2 3 1

表 1 投票列表 Table 1 Voting lists

由表 1可知，候选人数m=3，投票人数n=5.此时需要将表 1中给出的多个投票列表，合并为一个综合的排名结果.现有的投票列表合并算法很多，典型的有波达投票法BC和单一可转移票制STV.

在BC算法中，先算出每个候选人的综合得分.候选人e_i的综合得分是该候选人在所有列表中的得分s_i^k=m-r_i^k的总和，即s_i=s¹_i+s²_i+…+s_iⁿ，然后按照s_i的大小顺序得到最终的综合排名.BC算法本质上是根据多数规则提出的，即获得投票人支持最多的候选人获胜.

STV算法按照以下规则得到综合列表：首先统计所有列表中排在第一位的候选人的得票数，并将得票最多的候选人排在第一位.如表 1中，排在第一的候选人e₁得票数是2，e₃得票数是3，则将e₃排在综合列表中的第一位(如果排在第一位的有多个候选人，则通过一定的机制处理).其次将第一轮中落选的候选人的一票转移到排在第二位的候选人身上.如在列表L³中，将落选的e₁的那一票加到e₃上，e₃为2票，L⁴中e₂为2票.然后统计所有列表中排在第二位的候选人的得票数，可知这一轮e₁得2票，e₂得3票，e₃得2票(但不参与竞争)，e₂胜出.如此迭代直至第m轮，得到最终的综合列表.STA算法本质上遵从的是最大满意度原则，即尽量使最终结果让大多数投票人感到满意.

现有的投票列表合并算法均没有考虑排名信息的可信度问题.

本文提出两个基于可信度的算法：基于距离的算法和基于排名的算法.

由表 1可以得到任意两个候选人之间的排名距离d_ij^k (d_ij^k=r_j^k－r_i^k)，如表 2所示.由d_ij^k的定义可知，d_ij^k和d_ji^k是反对称的，因此只需考察其中的一种情况，这里只考虑i<j的情况，m个候选人一共有m(m-1)/2对组合.

表 2

Table 2

表 2(Table 2)

表 2 候选人之间的排名距离 Table 2 Rank distance between candidates dijk dij1 dij2 dij3 dij4 dij5 d12k 1 -1 2 1 1 d13k -1 -2 1 2 -1 d23k -2 -1 -1 1 -2

表 2 候选人之间的排名距离 Table 2 Rank distance between candidates

基于距离可信度的投票列表合并算法主要分为两部分：首先对表 2中的数据进行有效分析，挖掘并度量出投票人v_k对任意一对候选人之间的差距的了知度f_ij^k (1≤i<j≤m)；然后基于已知的了知度的值，从一个全新的角度计算出距离信息d_ij^k可被采信的程度(即可信度c_ij^k)，并用于最终的综合排名计算中.

对任意给定的一对候选人e_i和e_j(i<j)，首先假定每个投票人v_k(1≤k≤n)对他们之间差距的初始了知度是均等的，即f_ij^k=1/n(1≤k≤n).然后依据式(1)计算每对候选人的平均距离d_ij(1≤i<j≤m)，即以f_ij^k的概率来采信每个投票人v_k给出的距离信息d_ij^k，得到期望值d_ij：

这个期望距离d_ij近似反映了e_i到e_j的真实差距.因此通过|d_ij^k－d_ij|的大小，可以看出投票人v_k对每对候选人之间的差距的了知度.下面通过式(2)计算出新的了知度值：

显然新的了知度值更加准确，因此再次利用式(1)就可以计算出更加合理的均值d_ij，然后再次用式(2)计算出更加准确的了知度值f_ij^k.如此迭代t次，用第t次迭代结果f_ij^k作为最终的了知度值.

首先计算每条距离信息d_ij^k的可信度c_ij^k，然后基于此进行综合排名.通过3.1.1节，已经挖掘出了知度的值f_ij^k，显然了知度的值越大，距离信息d_ij^k的可信度c_ij^k越高;但在本文中并不简单地设定c_ij^k=f_ij^k，因为距离信息d_ij^k的可信度c_ij^k的大小，除了与投票人v_k对其的了知度f_ij^k有关外，还与该投票人自身的可信度c^k有关.

在现实生活中，对于一个低可信度的人，即使他对某些人很了解，人们也很难采信他所给出的信息；因此在本文的计算模型中，除了考虑了知度f_ij^k因素外，也考虑投票人v_k的可信度c^k因素，据此度量一条距离信息的最终可信度.

首先通过式(3)评估投票人v_k的可信度c^k，用该投票人对所有距离信息的了知度的平均值，即平均了知度，来度量该投票人的可信度；因为一个投票人对候选人之间的差距信息d_ij^k的了知度f_ij^k越高，则他的可信度就越高.

然后通过式(4)计算距离d_ij^k的可信度c_ij^k.即一个投票人v_k的可信度c^k越高，且对候选人e_i到e_j的相对差距的了知度f_ij^k越高，则v_k给出的距离信息d_ij^k的可信度c_ij^k也越大.

显然可信度c_ij^k反映了距离信息d_ij^k可被采信的程度.在e_i到e_j的最终距离d_ij的计算中，按照c_ij^k的大小采信距离信息d_ij^k，使可信度高的距离信息发挥更大的作用.距离d_ij的计算如式(5)所示：

最后根据d_ij的值及以下规则生成最终的综合列表：如果d_ij>0，则将元素e_i排列到元素e_j之前，否则相反.由定理1可知，基于距离d_ij的排名不会发生冲突情况.

定理1 如果d_ij>0并且d_jz>0，那么d_iz>0.

证明 d_iz^k=r_z^k－r_i^k=(r_z^k－r_j^k)+(r_j^k－r_i^k)=d_ij^k+d_jz^k，代入式(5)可得d_iz=d_ij+d_jz>0. 证毕.

基于排名可信度的算法，其大体的思想和方法和基于距离的基本一致.在该算法中，首先通过相似的迭代方法计算出每条排名信息r_i^k的了知度f_i^k，进而通过相似的方法，综合了知度f_i^k的值和投票人v_k的可信度c^k值求出r_i^k的可信度c_i^k，然后通过式(6)得到每个候选人e_i的综合得分s_i.最后按照s_i的大小对所有候选人进行综合排名.

本文的实验数据集分为两类.一类是自动生成的：首先假定一个标准排名，然后模拟现实中人的不同判断力和了知度而自动生成投票列表数据，然后运用本文提出的算法，得到合并结果，最后通过计算结果向量和标准排名的cosine相似度来度量算法的准确度，比较不同算法的优劣.模拟生成的实验数据集的规模为1000，即1000种模拟投票数据.另一类是一组真实的投票结果：给定10位明星，由实验室同学根据其知名度的高低各自给出一个排名，一共得到16个排名结果，然后根据本文提出的算法，得到一个综合排名，最后将综合结果和中国福布斯名人排行榜中的这10个人的相对排名进行对比，用以度量算法的优劣.

本文分别提出了基于距离可信度的合并算法DA和基于排名可信度的合并算法RA.为了全面考察算法RA和DA的性能，从以下4个方面对算法进行分析：①在模拟数据集上对比算法RA，DA，BC和STV；②在真实数据集上对比算法RA，DA，BC和STV；③考察式(2)中参数σ对RA，DA算法的影响；④考察式(4)中参数δ对RA，DA算法的影响.

图 1比较了不同算法在模拟数据集和真实数据集(即由16位同学对10位明星按照知名度进行排序的投票结果集)上的准确度，其中纵坐标准确度的取值是在1000组实验数据上所得结果的平均值.可以看出，本文提出的算法RA和DA总体上优于现有算法BC和STV，这主要是因为RA和DA算法不是简单地统计票数，而是通过数据分析和迭代计算挖掘出排名信息的可信度；另外DA算法总体上要优于RA算法，这主要是因为DA算法通过分析更加复杂的两两关系信息，通过相互制约，使得最终的投票结果的准确度可得到更高的保证.从总体上看，真实数据集上的效果不如模拟数据集，一方面是由于各位同学总体上对明星不是很熟悉，另一方面是由于数据量少(投票人数少)，使得算法的分析优势不能得到有效发挥，这也反映了RA和DA算法适合于数据量相对较大的投票场景中.

图 1(Figure 1)

Fig. 1

图 1 各算法在模拟数据集和真实数据集上的准确度 Fig. 1 Algorithm precision on simulated and real data sets

图 2反映了算法中参数σ，δ对算法准确度的影响.可以看出，当σ的取值在1.1左右时，算法的准确度最高，同时可以看出基于距离的合并算法DA的总体效果好于基于排名的合并算法RA.即在计算排名信息可信度时，那些偏离平均值远的排名信息，其可信度的取值不能太大也不能太小.

图 2(Figure 2)

Fig. 2

图 2 参数对算法准确度的影响 Fig. 2 Effect of parameters on algorithm precision

由图 2可以看出，当δ=0.8~0.9时，算法会取得比较好的计算效果.也就是说，一条排名信息的可信度主要取决于其投票人的可信度，同时投票人对它的了知度虽然在可信度计算中的权重(1-δ)较低，但它有效区分了同一个列表中的不同排名信息的可信度(如，某个投票人的可信度虽然很低，但由于该投票人对某几个候选人很熟悉，那么该列表中这几个候选人的相对排名顺序的可信度很有可能比其他人高).由图 2也可以看出，当完全依赖于投票人可信度(δ=1)时，算法效果急剧下降.

本文首次提出了基于可信度的投票算法.首先算法通过对投票列表数据进行综合分析，挖掘出每条排名信息的可信度.可信度的计算过程中不仅考虑了投票人的可信度因素，而且考虑了投票人对候选人的了知度，从而使得最终算得的排名信息的可信度值更加全面准确.在最终的综合排名中，利用得到的可信度的值，加权计算出候选人的排名值，从而使得最终的排名结果更加合理有效.

今后的工作，希望将多人的兴趣列表融合为一个群体兴趣列表.这就需要结合兴趣的具体特点提出一种新的算法，综合得到群体兴趣爱好，从而为更好的群体决策和服务提供依据和支撑.