Database Reference
In-Depth Information
U-Net
ID
Usefulness
}
Retained
RandomView
v
1
0.95
i=1
i=2
i=3
}
Already in
U-Net
Users
v
1
v
2
0.92
ID
Usefulness
}
Need to be
2b
2
Most useful
user (
best
)
v
6
v
7
v
8
v
9
v
7
v
3
0.89
v
7
0.89
0.78
1a
v
6
0.21
v
4
v
5
0.65
0.45
i=4
i=5
Initialization of
the candidate list
3b
recomputed
2a
v
8
compute
scores
0.65
v
9
0.22
}
v
3
v
4
v
5
0.12
1b & 3a
Move from
U-Net
to candidates list
0.42
0.41
Candidates List
Fig. 1.
An example of the execution of Useful-Unet
added to the
U-Net
and is initialized each time the clustering algorithm is trig-
gered.
In the following we present in more details the
Useful U-Net
algorithm based
on the example of Figure 1. The random view entries correspond to the profiles
of users
v
1
,v
6
,v
7
,v
8
,v
9
. The previous useful user profiles are
v
1
,v
2
,v
3
,v
4
,v
5
and
are stored in
U-Net
. Assuming that the algorithm is executed in
u
's node, the
algorithm input is
u
's profile, its random view denoted
RandomView
u
and its
U-Net
denoted
U-Net
u
. The data structure used for
U-Net
is an array of size
N
of user profiles, associated to their usefulness score and sorted in decreasing
order of usefulness. The output of the algorithm is the updated
U-Net
.
Useful
U-Net
algorithm has three main parts:
1. The first part (lines 1 to 6) finds the
best
useful user profile from the random
view, and the position
i
where it should be inserted in the
U-Net
(recall that
the usefulness score of a user depends on its position in the
U-Net
). As a
consequence, the update of the
U-Net
will only concern the user profiles
from position
i
to
N
. To find the
best
useful user from the random view,
the algorithm first initializes the
candidates
list with all users in the random
view except those already in the
U-Net
(line 2). In Figure 1,
v
1
is already
in the
U-Net
, so the candidates list is initialized with the users
v
6
,v
7
,v
8
,v
9
(1
a
). For each position
i
in
U-Net
, all the usefulness scores of the candidates
are computed using Formula 7 taking into account the set of users in the
U-Net
at positions 1
, ..., i −
1, and compared with the usefulness score of
the user profile in
U-Net
u
[
i
]. If the best user profile in
candidates
is more
useful than
U-Net
u
[
i
], then, the algorithm stops iterating (line 6). If there is
more than one best user profile, the best user profile is chosen randomly with
respect to the set of best user profiles. In Figure 1,
v
7
is more useful than
v
3
at the third position in
u
's
U-Net
because
v
3
's usefulness is 0
.
78 while
v
7
's usefulness is 0
.
89 (1
b
). If there is no user profile in the candidate list
whose profile score is superior to any user profile in the
U-Net
, position
N
is
reached and the algorithm stops. Only the scores of the user profiles up to
position
i
are definitive. Thus, in our example, the scores of
v
4
,v
5
,v
6
,v
8
,v
9
are not definitive because they are either not in the
U-Net
or after
i
.
Search WWH ::
Custom Search