Nantonac Collaborative Filtering:
Recommendation Based on Order Responses
Toshihiro Kamishima
National Institute of Advanced Industrial Science and Technology (AIST)
AIST Tsukuba Central 2, Umezono 1-1-1, Tsukuba, Ibaraki, 305-8568 Japan

mail@kamishima.net (http://www.kamishima.net/)
ABSTRACT

method [12] to measure the users’ preferences. In this method, the user’s preferences are measured by a scale, the extremes of which are symbolized by antonymous adjectives
and the divisions of which are cardinal numbers. An example of this type of scale is :A recommender system suggests the items expected to bepreferred by the users. Recommender systems use collaborative ﬁltering to recommend items by summarizing thepreferences of people who have tendencies simliar to the user
preference. Traditionally, the degree of preference is represented by a scale, for example, one that ranges from one toﬁve. This type of measuring technique is called the semantic
diﬀerential (SD) method. We adopted the ranking method,
however, rather than the SD method, since the SD method
is intrinsically not suited for representing individual preferences. In the ranking method, the preferences are represented by orders, which are sorted item sequences according
to the users’ preferences. We here propose some methods torecommend items based on these order responses, and carryout the comparison experiments of these methods.

prefer [ 5 4 3 2 1 ] not prefer
A user represents the degree of his/her preference by choosing a number from 1 to 5. As will be explained in the next
section, this measurement is intrinsically not ﬁt for use toevaluate individual preferences.
We therefore advocate a CF framework which adopts the
ranking method. In this method, users’ preferences are represented by orders. An order is an item sequence which
is sorted according to the user’s preference. The systempresents some items to a user, and receives its response oforders sorted according to the user’s preferences. We will
present several CF methods that can deal with these order
responses. We will experimentally show how our framework
is superior to the traditional one.
We would like to point out that the word nantonac isoriginates from a Japanese word, nantonaku, which means“unable to explain speciﬁcally, but I think such and suchis the case.” Since order responses allow a more vague andintuitive expression of users’ preferences, we decided to callthis type of ﬁltering method nantonac filtering.
We show the framework of the traditional CF method andour new framework in Section 2. In Section 3, we propose
some CF methods that can be used within this framework.
The experimental results are presented in Section 4, and thesummary in Section 5.

Categories and Subject Descriptors
H.3.3 [Information Storage and Retrieval]: Information
Search and Retrieval—Clustering, Information filtering

Keywords
Order, Recommender System, Collaborative Filtering

1.

INTRODUCTION

Recommender systems suggest the items expected to bepreferred by the users [14]. These systems are playing an
increasingly important role in business [16]. Collaborativeﬁltering (CF for short) is one of the methods used to implement recommender systems. CF works according to thisframework: First, the user inputs his/her preference patterns to the system. The system then searches its databasefor other people whose preferences are similar to those of theuser. Next, to the user, the system recommends the items
that those people prefer.
Though many methods of CF have been studied, almost
all of these methods adopt the semantic diﬀerential (SD)

1.1 Merits of Using Order Responses
There are several reasons why the SD method is not appropriate for CF. Before explaining why, it is necessary tolook at a notion in Stevens’ Scales of Measurement [17].
Stevens classiﬁed scales into four levels: nominal, ordinal,
interval, and ratio. Among these four levels, we discuss theordinal and interval scales. It is possible to more or less determinate the values of the ordinal scales. For example, twovalues of the ordinal scales, 2 and 3, are given. An interpretation that “2 is smaller than 3” is appropriate, but that “3is 1.5 times as much as 2” is inappropriate. On the other
hand, the values of interval scales are allowed to determine
the equality of the intervals. For example, three values ofinterval scales, 2, 3, and 4, are given. One proper determination is that “the diﬀerence between 2 and 4 is twice asmuch as that between 3 and 4.”
Let’s return to a discussion of the Semantic Diﬀerential

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
SIGKDD ’03, August 24-27, 2003, Washington, DC, USA.
Copyright 2003 ACM 1-58113-737-0/03/0008 ...$5.00.

583

The estimation method of the GroupLens works as follows: First, the similarity between the active user and thesample user i in DS is measured by the Pearson correlation:(SD) method [12]. By applying the SD method, we can get
observations represented by ordinal scales. For example, auser rates the items A and B at 4 and 2, respectively. The
proper interpretation is that the user prefers item A to B.
It should not be interpreted that the user prefers A twice
as much as B. However, due to the lack of an analysis
technique, these scores are of necessity treated as interval
scales, by introducing the following two unrealistic assumptions: the divisions of scales are equivalent and all users
share an understanding of scale extremes. Why has the SD
method been eﬀectively used? The SD method should be
intrinsically used for measuring the concepts of a group ofusers. For this purpose, even though intervals or extremesof scales are diverged, this divergence is lessened by averaging over users. However, in CF the system has to deal withindividual preferences, and because of this, the divergence
seriously inﬂuences the precision of preference prediction.
If the users’ responses deviate from the standard scale, thesimilarities to other people’s responses are incorrectly identiﬁed, and the wrong items are then recommended.
Another drawback of the SD method is the so-called Central Tendency eﬀects [12], which are well-known in experimental psychology literature. This phenomenon describes atendency to use only the near neutral portion of the rating
scale. Such rater eﬀects also confuse the identiﬁcation ofpreference similarity.

rai =s −s̄ s −s̄  
s −s̄  ,j∈I(Xai )

aj

a

ij

i

2

j∈I(Xai )

ij

i

2

where Xai =Xa ∩Xi and I(X)={j|xj ∈X}. s̄i is the meanscore of user i for the items in Xai .
The expected score of the item j for the active user isŝaj =s̃a +i∈X̃j rais − s̄ ij

i∈X̃j |rai |

i

,

(1)

where s̃a =|Sa|−1 saj ∈Sa saj and X̃j ={i|Si ∈DS s.t. sij ∈Si }.
The system recommends the items for which the expectedscore ŝaj is high.
This algorithm is simple, but very eﬀective. In survey [2],it performed the best for the data set in which the items wererated on a 6-level scale. A Bayesian network performs better
than this algorithm if the rating scale is binary (prefer ornot). Because a multi-level scale was used in our experiment,
we chose this algorithm for comparison.

2.2 Nantonac Collaborative Filtering
We will next describe our new framework: nantonac collaborative filtering. This framework is the same as the traditional one described above, except for the representationof the users’ preferences. Instead of using the set of scoresacquired by the SD method, we adopted the order acquiredby the ranking method. The system shows a set of items,
Xi , to the user i, and the user sorts these items according to his/her preferences. The sorted sequences are denoted by Oi =x1 x2  · · · x|Xi | . This indicates that, forexample, the user i prefers item x1 to item x2 . The rank,r(Oi , xj ), is the cardinal number that indicates the positionof the item xj in the order Oi . For example, for the order
Oi =x1 x3 x2 , r(Oi , x1 )=1 and r(Oi , x2 )=3. In our framework, the user database is a set of orders sorted by all theusers, DS ={O1 , . . . , O|DS | }. Let Xa be a set of items sortedby the active user, and Oa be the sorted order. Given the
Oa and DS , the task of nantonac CF is estimating the items
that the active user is expected to prefer.

1.2 Related Works
There have been many studies published on CF [1, 9, 10,
11, 13]. Breese et al.’s work [2] is an empirical comparison
survey in this research area. However, all of these methods
employed the SD method to measure users’ preferences.
Recently, there has been active research on the processingof orders. Cohen et al. [3] and Joachims [4] proposed amethod to sort attributed items associated with pairwise
precedence information. Kamishima and Akaho [5] and Kazawa et al. [7] studied the learning problem from ordereditem sets. Sai et al. [15] proposed association rules between
order variables.

2.

j∈I(Xai ) saj −s̄a

COLLABORATIVE FILTERING

We will now describe the traditional CF framework, andcompare it with our new one.

2.1 Traditional Collaborative Filtering
3. METHODS

We will ﬁrst describe the framework of CF developed
as part of the Riedl et al.’s GroupLens project [13]. CF
is a task to predict the preferences of a particular user
(an active user) based on the preference data collected onother users (a user database). Formally, the task is deﬁned as follows: Let sij be the score of item j by theuser i. The score represents the preference of the user,
and takes one of the values from, for example, {1, 2, 3, 4, 5}.
Xi = {x1 , . . . , x|Xi | } denotes a set of items the user i rated∗
and Si ={sij |xj ∈Xi }. X ∗ ={x1 , . . . , x|X | } denotes the setof all items. Note that |X| is the size of a set X. The user
database, DS = {S1 , . . . , S|DS | }, is a set of all Si . We callthe users in the database sample users. Let Sa be the set ofscores rated by the active user, and Xa be the set of items
the active user has already rated. Given the Sa and the DS ,the CF task is estimating the items that the active user is
expected to rate high. Such items are then recommended tothe active user.

We would like to propose some CF methods for the framework described in Section 2.2. In survey [2], the ﬁltering
methods are categorized: a memory-based method and amodel-based method. To estimate the users’ preferences,memory-based methods use an entire user database. Inmodel-based methods, a user database is used for the learning model for prediction. In addition to these methods, we
also propose a method which is a hybrid of these two methods. Below, we will show the modiﬁed version of the traditional methods, which has been adjusted to deal with orders.

3.1 Memory-Based Methods
In [2], Breese et al. described two basic methods for measuring similarities between two users by a correlation and avector similarity, and several extensions of these methods.
We will describe and present a modiﬁed version of thesemethods.

584

3.1.1 A Simple Correlation Method

Algorithm k-o’means(S, k, maxIter)
S = {O1 , . . . , O|S| }: a set of orders
k: the number of clusters
maxIter: the limit of iteration times
1) S is randomly partitioned into a set of clusters
π = {C1 , . . . , Ck }, π  := π, t := 0.
2) t := t + 1, if t > maxIter goto step 6.
3) for each cluster Cj ∈ π, derive the order means Ōjby the procedure in Section 3.2.
4) for each order Oi in S, assign it to the cluster:arg minCj d(Ōj , Oi ).
5) if π = π  then goto step 6
else π := π, goto step 2.
6) output π.

In order to carry out CF, it is necessary to measure thesimilarities of preferences between the active and the sample
users. In this method, we treat given ranks as scores of
the GroupLens’s method. That is to say, the similarities
between the users are



Rai =





j
xj ∈Xai r(Oa , x ) − r̄ar(O , x ) − r̄ 

2jxj∈Xai(r(Oa, x )−r̄a )

i

j

i

2
j
xj∈Xai(r(Oi, x )−r̄i ), (2)where Xai =Xa ∩Xi and r̄i =|Xai |−1 xj ∈Xai r(Oi , xj ). Notethat the items not contained in the other order are ignored,
but the ranks are not renumbered. For example, from theorder Oa = x1 x2 x3 , the item x2 is eliminated, but therank of x3 remains r(Oa , x3 )=3. The system estimates preferences for the item j by the active user by the function:r̃a +i∈X̃j Rair(O , x ) − r̄ iji∈X̃j |Rai |i,

Figure 1: The k-o’means algorithm
The k-o’means [6] is the algorithm for clustering orders.
We here simply describe this algorithm in Figure 1. The ko’means is the same as the well-known k-means algorithm,
except for the notions of a dissimilarity and a mean. We
deﬁne a dissimilarity based on the ρ between two ordersas d(Oi , Oa ) = 1 − ρ. The ρ denotes a widely used similarity of orders, the Spearman’s Rank Correlation [8]. For
the two orders Oi and Oa consisting of the same item set(i.e., Xi =Xa ), the ρ between the two orders is equal to theEquation (2). The ρ becomes 1 if the two orders are coincident, and −1 if one order is a reverse of the other order. If
Xi =Xa , the items not contained in the other order are again
eliminated, but the ranks are renumbered. For example, if
the item x3 is eliminated from the order x1 x3 x4 x6 , therank of the item x6 changes from 4 to 3. Note that if nocommon items exist between the two orders, the ρ = 0 (i.e.,
no correlation).
As a mean, we used the following notion of the order mean,that is a representative of given orders. For a set of orders,C, the order mean is deﬁned as(3)

where r̃a =|Xa|−1 xj ∈Xar(Oa, xj ), X̃j={i|Oi ∈DS s.t. xj ∈Xi}.
The items are sorted in ascending order of these estimatedpreferences, and the highly ranked items are recommended.

3.1.2 Default Voting
In [2], three extensions are proposed. Though their experimental results show that the inverse user frequency extension is eﬀective, we could not impose this idea onto ourframework. Case ampliﬁcation extension is not eﬀective somuch, and adopts the subjective parameter tuning; thus wedidn’t implement this. We imposed only the idea of default
voting to our framework.
The idea of default voting is designed for a situation inwhich relatively few items are evaluated. According to adecrease of |Xi | relatively to |X ∗ |, the frequency of the event,Xa ∩Xi =∅, increases. Since the Rai is always 0 in a case inwhich no commonly evaluated items exist, the similarities
between users can no longer be precisely measured. Whenderiving similarities between two orders Oa and Oi , if weassign default ranks to the items either of the user i or theactive user evaluated, then the similarities can be calculated
over Xa ∪ Xi . Similar to [2], we give neutral preferences tothese items. The items that are not in one order are inserted
into the middle of the order. For example, the responses of
the active user the user i are Oa = x1 x3 x6 and Oi =x5 x3 x2 x6 , respectively. The items evaluated only by
the other user is inserted: Oa = x1 x3 x2 ∼x5 x6 andOi = x5 x3 x1 x2 x6 (∼ denotes the tie in rank). To
all tied items, we give the same rank, which is the mean ofthese ranks. For example, the items x5 and x2 which areat the 3rd and 4th positions in the order Oa , are tied, thus
The rank of these items are 3.5. The similarities between
Oa and Oi are calculated by Equation (2). The expected
preference is derived by Equation (3), except that r(Oi , xj )is used instead of r(Oi , xj ). The other procedures are thesame as those described in Section 3.1.1.

ŌC = arg maxOj

Oi ∈C ρij .

(4)

Unfortunately, the method to derive the optimal solution of
Equation (4) could not be developed. Instead, the following method based on Thurstone’s paired comparison, which
gives a good performance empirically. First, the probability Pr[xa xb ] is estimated. From the order Oi ∈ C, all theitem pairs, (xa , xb ), are extracted such that xa precedes xb
in the order. For example, from the order Oi = x3 x1 x2 ,three item pairs, (x3 , x1 ), (x3 , x2 ), and (x1 , x2 ), are extracted. Such pairs are extracted from all |C| orders, andare collected into the set PC . As the probability Pr[xa xb ],we adopted the following Bayesian estimator with Dirichletprior distribution in order that the probability remains at
non-zero:Pr[xa xb ] =|xa , xb |+0.5|xa , xb |+|xb , xa |+1,

where |xa , xb | is the number of the item pairs (xa , xb ) in PC .
Then, for each item that appears in some order in the C,(i.e., XC = Oi ∈C Xi ), the following µa are calculated:

3.2 Model-Based Methods
In [2], the two model-based method is provided: a clustermodel and a Bayesian Network model. Since we do not know
the Bayesian Network designed for dealing with orders, only
the cluster model was examined.

µa =

585

1
|XC |

 Φ Pr[x x ],
−1

xb ∈X

C

a

b

XiB by the SD method using a ﬁve point scale. The responsescores were denoted by SiB .
3, 4) Next, two questions were irrelative to preferences.
These two questions lessened the inﬂuence of query 2 onquery 5.
5) We asked the user i to sort the items in the XiB set
according to his/her preference. The response order was
denoted by OiB .
The total number of responses collected was 1039. We
eliminated the data obtained within a response time which
was either too short or too long. Consequently, the data set
includes 1025 tuples: (OiA , OiB , SiB ). We performed a preliminary experiment to compare two types of responses. We
derived the ratio of responses in which there exists contradiction between SiB and OiB . Here, the contradiction means
that, though the item xa precedes the xb in OiB , the score of
xb in SiB is rated higher than that of xa . We found such contradictions in 70% of the tuples. This result at least showsthat diﬀerent aspects of preference can be captured by the
ranking and SD methods.

where Φ(·) is a normal distribution function of N (0, 1). By
sorting the items according to these µa , the order mean isapproximated.
The recommendation process is as follows: Before recommendation, the database DS is divided into the partition
πDS = {C1 , . . . , C|πDS | } by the k-o’means. Given the active
user’s order, Oa , the system calculates the above dissimilarities between the Oa and each order mean of clusters inthe πDS , and the most similar cluster is found. The systemthen recommends the highly ranked items in the most similar order mean. Note that since the output of the k-o’means
depends on the initial partitions, we chose the partition that
achieved the minimum sum of dissimilarities among 10 trials
in the experiment described in Section 4.

3.3 Hybrid Methods
We examined the hybrid methods of memory-based andmodel-based methods. The cluster models combined withthe simple rank correlation method.
The original memory-based algorithm calculates the similarities between the active user and each user in the entire
user database. In this hybrid method, ﬁrst the most similarcluster C ∗ is found by the procedure described in Section 3.2.
Then active user’s preference is predicted only from the user
data in the C ∗ , and the rest of the data is ignored.

4.

4.2 The Evaluation Procedure and Criterion
To evaluate each method, we applied the 10-fold crossvalidation test. The training and the test sets are denotedby D̄ and D , respectively. As described above, a data set
D was composed of tuples: (OiA , OiB , SiB ). The SiB and OiB
were used for a traditional CF and for ours, respectively.
The set, which consists of all the OiB (or SiB ) in the D̄ , wastreated as a user database DS . Each OiB (or SiB ) in the D
was picked up in turn, and the picked order (or score) was
considered as the active users response OaB (or SaB ). Given
the DS and the OaB (or SaB ), the system predicted the orderof items in the X A (the type A item set) sorted according to
the active user’s preference. Let ÔiA be the predicted order.
The ÔiA is compared with the true response order OiA in
the D . To measure the quality of the predicted order, ρbetween the ÔiA and the OiA as used in [10].
In order to investigate the changes in user database sizes,
we generated three sets, sizes (denoted by |D|) of which are
1025, 500, and 300, respectively. Similarly, by randomly
eliminating items from the XiB and renumbering the ranksof these items, we changed the sizes of item sets XiB to 10,
7, 5, 3, and 2.

EXPERIMENTS

To compare the above CF methods, we applied thesemethods to sushi preference data.

4.1 The Data Collection Procedure
Before describing the data collection procedure, we would
like to explain why we chose to use preferences in sushi (aJapanese food) as a testbed. First, there are many types ofsushi, and preferences are diﬀerent for each person. In addition, since users have fewer privacy concerns about expressing their preferences in sushi, the data was easily collected.
The preference data were collected using the following procedure. Before collecting the data, we surveyed menu datafrom 25 sushi restaurants found on the WWW. For eachtype of item (i.e., type of sushi sold at the restaurant), we
counted the number of restaurants that oﬀered the item.
From these counts, we derived the probabilities that each
item would be supplied. By eliminating unfamiliar or low
frequency items, we came up with a list of 100 items. This
item set corresponds to X ∗ in Section 2.1.
We generated two item sets, which were presented as Xi
to each user. The type A set (X A ) was common for allusers. We chose the following 10 popular items: Shrimp,
Sea eel, Tuna, Squid, Sea urchin, Salmon roe, Egg, Fatty
tuna, Tuna roll and Cucumber roll. This set was used fortesting. The other type B sets (XiB ) were diﬀerent for eachuser. Ten items were randomly selected from X∗ according
to the above probability distribution. The orders in thisitem set were treated as user responses. Note that the X A
and the XiB had overlap of 2.41 items per order on average.
We collected the responses via a commercial WWW survey service. The following queries were presented:
1) We asked each user i to sort items in the X A according
to his/her preference. The user selected ranks of presented
items through the WWW interface. The response order was
denoted by OiA .
2) We asked the users i to rate their preferences in items of

4.3 Experimental Results
We applied the evaluation procedure in the previous section to each of the methods described in Section 2.1 and 3.
These methods are denoted by the symbols: SCR (Sec. 2.1),
RCR (Sec. 3.1.1), CLS (Sec. 3.2), and HCR (Sec. 3.3).
As described in Section 4.1, the item sets X A and XiB canbe overlapped. We didn’t abandon these overlapped items
because the preference orders have to be predicted, even if
the ranks or scores of items in the XiB are given. These
overlapped items were treated as follows. In the case of the
SCR method, since the scores were rated with common scales,
the score given in the SiB was used as the expected score.
The scores of the other non-overlapped items were predicted
by Equation (1). However, in the cases of all the othermethods, all the preferences were estimated irrespective ofwhether or not the items were in the XiB , because ranks
depend on the item set to sort. The numbers of clusters khave to be ﬁxed to apply the methods, CLS and HCR, that
use the k-o’means algorithms. Since we had not developed586

Table 1: Means and s.d. of ρ (|X B |=10, |D|=1025)
SCR
RCR
CLS
HCR
mean
0.362
0.432
0.389
0.442
s.d.
0.30750.30340.34430.3095

0.4

rho

0.3

0.4

0.2

0.3
rho

SCR
RCR
CLS
HCR
0.1
300

500
sizes of data sets

1025

0.2

Figure 3: Changes of criteria according to the sizesof the data sets (|D|)

SCR
RCR
CLS
HCR
0.1
2

3

5
7
sizes of item sets

10

Table 2: t-values of ρ between the SCR and each of
the other methods

Figure 2: Changes of criteria according to the sizesof the response item sets (|X B |)(a) sizes of item sets (|XB |)a method to determine these numbers, the numbers werechanged from 2 to 10, and the best result was selected.
We applied all the methods to the data set in which thesize of the data set (|D|) is 1025 and the sizes of the response
item sets (|X B |) is 10. The means and standard deviationsof ρ are shown in Table 1. Surprisingly, in all criteria, thetraditional method was worse than any of our methods. We
think that this result is due to the undesirable propertiesof SD methods for CF. Below, we show the ratios of eachrating score selected by users:[1] 0.082[2] 0.095[3] 0.226[4] 0.224

|X B|
RCR ⊕
CLS
HCR ⊕

10
7
5
3
2
7.390
2.306 −1.275 −2.019−1.7722.031 ⊕ 4.803 ⊕ 5.675 ⊕ 3.572 ⊕ 8.358
7.865
2.017 ⊕ 3.024
0.724 ×−2.560

|D|
RCR
CLS
HCR

1025
⊕ 7.390
2.031⊕ 7.865(b) sizes of data sets (|D|)[5] 0.372

500⊕ 3.234
0.006
1.982

300
1.280
0.404
0.329

recommendation based on rather generalized preferences.
Figure 3 shows the changes of the means of criteria according to the sizes of the data sets (|D|), when the |XB | areﬁxed to 10. Again, the order-based method achieves superiority over the SCR method if more information is available.
To stringently examine the diﬀerence between the SCR
method and the other methods, we applied a paired t-test(Table 2). The positive t-values indicate that order-based
methods are superior. The ⊕ and(× and ) indicatethat the order-based methods are superior (inferior), andthat the diﬀerence is statistically signiﬁcant at the significance level of 1% and 5%, respectively. We ﬁrst discuss
results in Table 2(a). As described above, except for the
CLS method, the order-based methods are superior to the
SCR method, if the |X B | is large. However, the SCR is superior when the |X B | = 2 or 3. Overall, if the system isdesigned to request to sort 7 or more items, the order-based
method surpasses the traditional methods. In the case of
Table 2(b), the larger the |D| grows, the more superior theorder-based methods, except for the CLS, become.
To test the eﬃciency of hybridization in Section 3.3, a hybrid method and its source method were compared. Table 3
shows the t-values between the ρ of the hybrid method HCR
and of its source method, RCR and CLS. The positive t-values
indicate the superiority of the hybrid methods. When com-

This distribution is highly skewed, and users gave ratings
within a narrow range of the scale. Therefore, we believe
it is problematic to treat these ratings as values of interval
scales by introducing the assumptions in Section 1.1. Notethat it might appear to be eﬀective to normalize by using
the minimum and the maximum ratings of each user. By imposing this normalization on the SCR, the mean of ρ became
0.367. This normalized SCR appeared to have no signiﬁcantadvantage over the original SCR, and was found to be significantly inferior to the RCR.
Figure 2 shows the changes of the means of criteria according to the sizes of the response item sets (|XB |), when thesizes of the data sets (|D|) are ﬁxed to 1025. When comparing the SCR method and the other order-based methods, thelarger the |X B | becomes, the more the order-based methods overcome the SCR. Among the order-based methods, the
CLS method is rather characteristic. This method performed
even if the |X B | is small, but is inferior to the other methods when the |X B | is large. We think this is due to thefact that while the other methods are designed to purely
predict the personal preferences of an active user, the CLS
method is designed to predict the preferences of the groupto which the active user belongs. Therefore, if less personal
information is supplied, the CLS method can make a better587

7. REFERENCES

Table 3: Comparison with hybrid methods and theirsource methods
|X B|
10
7
5
3
2
RCR
1.464 −0.301 ⊕ 4.422 ⊕ 2.933 −1.767
CLS ⊕ 5.112 ×−3.627 ×−3.303 ×−3.295 ×−9.207
|D|
RCR
CLS

1025
1.464
⊕ 5.112500−1.446
1.896[1] C. Basu, H. Hirsh, W. W. Cohen, and
C. Nevill-Manning. Technical paper recommendation:
A study in combining multiple information sources.
Journal of Artificial Intelligence Research, 14:231–252,
2001.
[2] J. S. Breese, D. Heckerman, and C. Kadie. Empricalanalysis of predictive algorithms for collaborativeﬁltering. In Uncertainty in Artificial Intelligence 14,
pages 43–52, 1998.
[3] W. W. Cohen, R. E. Schapire, and Y. Singer.
Learning to order things. Journal of Artificial
Intelligence Research, 10:243–270, 1999.
[4] T. Joachims. Optimizing search engines using
clickthrough data. In Proc. of The 8th Int’l Conf. on
Knowledge Discovery and Data Mining, pages
133–142, 2002.
[5] T. Kamishima and S. Akaho. Learning from order
examples. In Proc. of The IEEE Int’l Conf. on Data
Mining, pages 645–648, 2002.
[6] T. Kamishima and J. Fujiki. Clustering orders. In
Proc of The 6th Int’l Conf. on Discovery Science,
2003. (submitted).
[7] H. Kazawa, T. Hirao, and E. Maeda. Ranking SVM
and its application to sentence selection. In Proc. of
2002 Workshop on Information-Based Induction
Sciences, 2002. (in Japanese).
[8] M. Kendall and J. D. Gibbons. Rank Correlation
Methods. Oxford University Press, ﬁfth edition, 1990.
[9] W. S. Lee. Collaborative learning for recommendersystems. In Proc. of The 18th Int’l Conf. on Machine
Learning, pages 314–321, 2001.
[10] R. J. Mooney and L. Roy. Content-based book
recommending using learning for text categorization.
In ACM SIGIR Workshop on Recommender Systems:
Algorithms and Evaluation, 1999.
[11] A. Nakamura and N. Abe. Collaborative ﬁltering
using weighted majority prediction algorithms. In
Proc. of The 15th Int’l Conf. on Machine Learning,
pages 395–403, 1998.
[12] C. E. Osgood, G. J. Suci, and P. H. Tannenbaum. The
Measurement of Meaning. University of Illinois Press,
1957.
[13] P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, andJ. Riedl. GroupLens: An open architecture forcollaborative ﬁltering of Netnews. In Proc. of The
Conf. on Computer Supported Cooperative Work,pages 175–186, 1994.
[14] P. Resnick and H. R. Varian. Recommender systems.
Communications of The ACM, 40(3):56–58, 1997.
[15] Y. Sai, Y. Y. Yao, and N. Zhong. Data analysis andmining in ordered information tables. In Proc. of The
IEEE Int’l Conf. on Data Mining, pages 497–504,
2001.
[16] J. B. Schafer, J. A. Konstan, and J. Riedl.
E-commerce recommendation applications. Journal of
Data Mining and Knowledge Discovery, 5:115–153,
2001.
[17] S. S. Stevens. Mathematics, measurement, andpsychophysics. In S. S. Stevens, editor, Handbook ofExperimental Psychology. John Wiley & Sons, Inc.,
1951.

300
−1.316−0.175

Table 4: t-values between the ρ with and without
default voting (|D| = 1025)
10|X B|
t-val ⊕ 2.681
1.768
#

7
5
3
2
−1.053 × −9.412 ×−31.520 × −8.891
0.868
0.445
0.161
0.072

paring with the RCR, there were no clear characteristics according to the changes of the |D| or the |X B |. However, noneof the methods are worse than the RCR if the |XB | is greaterthan 3. By clustering the user database in advance, it ispossible to save the number of the sample users to whichsimilarities had to be calculated. Since this result showsthat the performance was not depressed by using clustering, it is possible to save time required for recommendation
to be made by using hybridization. When comparing with
CLS, by hybridization, the characteristics of the CLS method
seem to have been lost. Therefore, similar to other memorybased methods, the hybrid methods are superior if the |X B |is large.
We compared the RCR methods with and without default
voting in Section 3.1.2. The results of the comparison are
shown in Table 4. The positive t-values indicate the superiority of the method with default voting. The row labeled“#” shows the mean numbers of items shared between two
preference orders, Oa and Oi . As the sizes of item sets decrease, the number of shared items also decrease. We had
expected default voting to be eﬀective when the numberof shared items was small, but default voting depressed theperformance in such cases, i.e., |XB | ≤ 5. This phenomenon
was also observed if |D| is 500 or 300. We currently are notable to explain these phenomena, but one possible hypothesis is that default ranking described in Section 3.1.2 does
not work as neutral evaluation.

5.

CONCLUSIONS

We advocate the new nantonac CF, by using which items
are recommended based on the order responses. We showedthat the prediction performance of nantonac CF was clearlysuperior to those of the traditional method.
The current framework cannot handle a large universal
item set X ∗ , since it is diﬃcult for users to sort items if|Xi | is larger than about 10. Thus, to collect a more user
preference data, we will develop a method that allows eachuser to bring multiple responses in terms of distinct item
sets.

6.

ACKNOWLEDGMENTS

A part of this work is supported by the grant-in-aid for
exploratory research (14658106) of the Japan society for thepromotion of science.

588