Information Technology Reference
In-Depth Information
vote(
x
j
)=
O
i
∈C
k
L
∗
−
r
ij
+1
.
X
∗
in descending order of
vote(
x
j
). Clearly, this method is equivalent to sorting the objects in ascending order of
the following mean ranks:
Then, a central order is derived by sorting objects
x
j
∈
1
r
j
=
r
ij
.
(15.9)
|
C
k
|
O
i
∈C
k
If all sample orders are complete and Spearman's distance is used, it is known that the
central order derived by the above Borda Count optimally minimizes Equation (15.5)
[4, theorem 2.2].
Because all sample orders are complete, Spearman's distance is proportional to the
distance
d
ρ
. Therefore, even in the case that
d
ρ
is used as dissimilarity, the optimal
central order can be derived by this Borda Count method. This optimal central order
can also be considered as a maximum likelihood estimator of the Mallows-
θ
model
[16]. The Mallows-
θ
model is a distribution model of the complete order
O
,andis
defined as
exp(
θd
S
(
O
0
,O
))
,
(15.10)
where the parameters
θ
and
O
0
are called a dispersion parameter and a modal order,
respectively.
Unfortunately, this original Borda Count method cannot be applied to incomplete
orders. To cope with incomplete orders, we must show the facts known in the order
statistics literature. First, we assume that there is hidden complete order
O
h
Pr[
O
;
O
0
,θ
]
∝
which is
randomly generated. A sample order
O
i
C
k
is generated by selecting objects from
this
O
h
uniformly at random. That is to say, from a universal object set
X
∗
,
L
i
objects
are sampled without replacement; then,
O
i
is generated by sorting these objects so as
to be concordant with
O
h
. Now we are given
O
i
generated through this process. In this
case, the complete order
O
h
∈
follows the distribution:
O
i
]=
L
i
!
if
O
h
and
O
i
are concordant,
Pr[
O
h
|
L
∗
!
(15.11)
0
otherwise.
Based on the theory of order statics from a without-replacement sample [17, sec-
tion 3.7], if an object
x
j
is contained in
X
i
, the conditional expectation of ranks of
the object
x
j
in the order
O
h
given
O
i
is
O
i
]=
r
ij
L
∗
+1
E[
r
j
|
L
i
+1
,
if
x
j
∈
X
i
,
(15.12)
where the expectation is calculated over all possible complete orders,
O
h
,and
r
j
≡
r
(
O
h
,x
j
). If an object
x
j
is not contained in
X
i
, the object is at any rank in the hidden
complete order uniformly at random; thus, an expectation of ranks is
O
i
]=
1
E[
r
j
|
2
(
L
∗
+1)
,
if
x
j
/
∈
X
i
.
(15.13)
