User Modeling in Folksonomies: Relational Clustering and
Tag Weighting∗

Takuya Kitazawa
k.takuti@gmail.com

Masahide Sugiyama
sugiyama@u-aizu.ac.jp

School of Computer Science and Engineering
The University of Aizu, Fukushima, Japan

ABSTRACT

1.

This paper proposes a user-modeling method for folksonomic data.
Since data mining of folksonomic data is diﬃcult due to their complexity, significant amounts of preprocessing are usually required.
To catch sketchy characteristics of such complex data, our method
employs two steps: (1) using the infinite relational model (IRM)
to perform relational clustering of a folksonomic data set, and (2)using tag-weighting to extract the characteristics of each user cluster. As an experimental evaluation, we applied our method to realworld data from one of the most popular social bookmarking services in Japan. Our user-modeling method successfully extracted
semantically clustered user models, thus demonstrating that relational data analysis has promise for mining folksonomic data. In
addition, we developed the user-model-based filtering algorithm(UMF), which evaluates the user models by their resource recommendations. The F-measure was higher than that of random recommendation, and the running time was much shorter than that ofcollaborative-filtering-based top-n recommendation.

Folksonomy, also known as social tagging, is the result of a social networking, and it can be used to share a wide variety of content through the use of user-defined tags. Fig. 1 shows an example
of a social network creating a folksonomy. In this figure, each user
(1, 2, 3, and 4) demonstrates diﬀerent relationships with diﬀerent
resources (a, b, c, d, and e), each adds their own choices of tags (V,W, X, Y, and Z) to the resource items.

a
X
Y

▲
user

H.2.8 [Database Management]: Database Applications—Data mining; H.3.3 [Information Storage and Retrieval]: Information Searchand Retrieval—Clustering, Information filtering

Algorithms, Experimentation

Keywords
Folksonomy, User Modeling, Recommendation∗Current aﬃliation is Graduate School of Information Science andTechnology, The University of Tokyo, Japan.

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.
WIMS ’15, July 13 - 14, 2015, Larnaca, Cyprus
Copyright 2015 ACM 978-1-4503-3293-4/15/07 ...$15.00.

DOI: http://dx.org/10.1145/2797115.2797129

Y

tag

b

1

▲

c

V
W
Y
Z

d

4

▲

2

Categories and Subject Descriptors

General Terms

INTRODUCTION

3▲econtent

Figure 1: Social network creating a folksonomy
For instance, Flickr1 and Delicious2 are well-known services thatmake use of folksonomy; the former supports photo sharing, andthe latter provides social bookmarking. While these services areindeed flexible for users, the analysis of real-world folksonomic
data sets poses diﬃculties. This is due the data being very sparseand tags fluctuating. Tag fluctuations occur because people sharethe same content with similar, but diﬀerent, tags; for example, tothe same content, one user may add the tag “MUSIC,” while another adds the tag “music.” Thus, it has been necessary to develop
algorithms to normalize the data sets prior to further processing.
The primary reasons for mining folksonomy systems are to findclusters and to develop recommendations. Thus, the principal purpose and expected applications of this study is the same as thoseof previous studies [2, 9, 11, 12]. However, for the reasons that we
mentioned above, the methods presented in previous studies usually require that the data sets undergo careful normalizations andcomputations. Even though careful data mining improves accuracy
in some ways, if folksonomic data can be mined more roughly,
there is hope that running time can be reduced, and unpredictable
quality of extracted information can be preserved.
More importantly, since these data sets are continuously chang1
2

Flickr. http://www.flickr.com/
Delicious. http://delicious.com/

ing, time-consuming algorithms are not realistic. For example, therecommender system proposed by Niwa et al. [9] may be impracticable because the system requires many tiny steps. Unfortunately,
as long as researchers use the vector space model for folksonomy
data sets, it will be necessary to include these extra steps. Even
though Hothho et al. [3] established a formal model for retrieving
information from folksonomies and contributed greatly to the understanding of folksonomy, their algorithm also uses vectors. Currently, there are many diﬀerent data mining techniques, and it isstraightforward to extract knowledge, such as user preferences andsimilarities, from folksonomic data, without the need to use a vector space model.
This paper proposes an unsubtle approach to the mining of folksonomic data. In particular, we focus on clustering to determine
the relationship between users and resources. Our method is basedon the infinite relational model (IRM) [5], which is a nonparametric Bayesian model, and the use of tag weighting to extract usermodels. User models for services that use folksonomy have a highpotential for providing practical personalized applications, such asrecommender systems. By demonstrating semantically clustereduser models and considering their applications, we show in thispaper how relational analysis of folksonomic data can eﬀectively
catch the momentary characteristics of users.

Table 2: Example of output from user modeling, using the datafrom Fig. 1
k User cluster Tag weights
1{1, 2}
w1 (V), w1 (W), w1 (X), w1 (Y), w1 (Z)2{3}
w2 (V), w2 (W), w2 (X), w2 (Y), w2 (Z)3{4}
w3 (V), w3 (W), w3 (X), w3 (Y), w3 (Z)preferences of users, since this information leads to practical personalized applications. In this context, the term “user modeling”
refers only to their tagging of content, and not to personal attributes,
such as gender or age.

2.2

Infinite Relational ModelFirst, we will introduce the IRM because it plays a central rolein our approach. The IRM is a stochastic model that is used todetermine clusters in relational matrices; IRM-based clustering has
been used to discover useful structures in real-world relational data,
as discussed in previous studies [4, 5]. As a simple example, Fig. 2
demonstrates clustering for a relational matrix in which the entries
are 0 (white) or 1 (black) to show the connections between data sets
S 1 and S 2 . The figure shows three clusters.

2. PROBLEM FORMULATION
2.1 Input and Output
Let U be a set of users, let C be a set of resource items, and let
T be a set of tags in a folksonomy. Thus, for example, based on
Fig. 1, U = {1, 2, 3, 4}, C = {a, b, c, d, e}, and T = {V, W, X, Y, Z}.
Under this setting, we define a binary relational matrix R on U × C;
the i, j-th entry has the value of 1 if the i-th user has a connection to
the j-th item, and it is 0 otherwise. Hence, Fig. 1 can be represented
as:
1
2
3
4

a

 1
 1

 0

0

b
0
0
0
1

c
0
0
1
0

d
0
1
1
0

e

1 

0 
,
0 
0(1)

in which the i-th user corresponds to the i-th row, and the j-th item
corresponds to the j-th column. Note that when we say a user isconnected to a resource item, we mean that the user has bookmarked the item (such as a web page) or has marked it as a “favorites” (such as a shared photo). Each resource item is also associated with added tags and the frequency of each tag, as shown in
Table 1.
Table 1: Tag information for each item in Fig. 1
Content Added tags and frequencya{(V, 0), (W, 0), (X, 1), (Y, 2), (Z, 0)}b{(V, 1), (W, 1), (X, 0), (Y, 0), (Z, 0)}c{(V, 0), (W, 0), (X, 0), (Y, 0), (Z, 1)}d{(V, 0), (W, 0), (X, 0), (Y, 0), (Z, 0)}e{(V, 0), (W, 0), (X, 0), (Y, 1), (Z, 0)}
The above information comprises the input for user modeling,
and an example of the output is shown in Table 2. According to thistable, several user clusters are found, and we can infer the characteristics of the each of these clusters from the weighted tags. In thetable, wk (t) indicates the weight of tag t for the k-th user cluster.
In this paper, we will primarily focus on the characteristics and

S1

IRM

−−−→

η̄(3, 1) ≒ 3/4 = 0.75

S2

Figure 2: Example of IRM-based clustering
The IRM assumes that the relational matrices, such as the lefthand matrix in Fig. 2, create dense or sparse sub-blocks in it. Fora better understanding, cluster assignments for all elements z1 , z2 ,and inter-cluster density η(k, ℓ) are shown in Fig. 3. Importantly,
this is just how the IRM assumed the data have been generated. In
practice, the relational data R is observed, and the estimation of the
optimal cluster allocation z1 and z2 is the main task3 .
25

134
679
256
7 8

8
39

z2

1

z

14

0.1

0.9

0.9 η(k, ℓ)

0.1

0.1

0.9

0.9

0.1

0.1

2
5
6
7
8
1
4
3
9

2 5 1 3 4 6 7 9 8R(i, j)Figure 3: Relational data generative model of the IRM
3
C code developed by Kemp et al. [5] is available at:
http://www.psy.cmu.edu/ ckemp/code/irm.html.

Let N1 be the number of S 1 clusters, and let N2 be the number ofS 2 clusters. As can be seen in Fig. 2, relational clustering enables
the computation of the maximum a posteriori value of η(k, ℓ):m(k, ℓ) + βη̄(k, ℓ) =,m̄(k, ℓ) + m(k, ℓ) + 2β

C6U6

Figure 5: Part of the result of clustering U × C
As can be seen in Fig. 5, the density of 1 in the intersection of U9and C8 is high, as indicated by black dots. From Eq. (2), we findthat η̄(9, 8) ≒ 0.14 is large, and thus U9 and C8 have a relatively
strong relationship. We can see that the density in the intersectionof U9 and C7 is lower, and, as expected, η̄(9, 7) ≒ 0.02 is smaller.
The user-modeling method uses η̄(k, ℓ) to find the characteristics ofuser clusters.
Fig. 6 shows the log-likelihood of a given relation and the number of clusters obtained in each iteration. The cluster assignmentsof all elements are individually reallocated in each step. Processing of the 1,017-by-7,000 matrix (97.6% sparse) took 54 minutes
for 20 iterations. We note that the likelihood and the number ofclusters converged at diﬀerent rates.

content
clusters

Figure 4: Relationships between components of the usermodeling algorithm

These data were collected from Jun. 4, 2014 to Jun. 5, 2014.
5
Hatena Bookmark. http://b.hatena.ne.jp/

160

-6.75

140
-7.00

AKA

120

User cluster (N1 )

-7.25

100
80

-7.50

60

-7.75
-8.00
-8.25

0

5

Web page cluster (N2 )

40



20
10

15

20

Figure 6: Convergence of the IRM-based clustering

4.

USER MODELING BASED ON THE CLUSTERING RESULTAs mentioned in Section 3, η̄(k, ℓ) indicates the strength of therelationship between the user clusters and the content clusters. In
this section, we discuss the assignment of weights to each tag; thisis done to determine the characteristics of each of the user clusters.
We apply tag weighting and user modeling to the social bookmarking data sets used in the previous section.

4.1
4

180

log-likelihood

Number of iterations

3. RELATIONAL CLUSTERING IN SOCIAL
BOOKMARKING
As the first step in user modeling, we collected data sets4 from
Hatena Bookmark5 , one of the most popular social bookmarking
services in Japan, and we then performed relational clustering forthe data matrix, which consisted of 1,017 users U and 7,000 web
pages C [6]. IRM-based clustering generated 163 user clusters(N1 = 163) and 8 content (web page) clusters (N2 = 8). Partial
results are shown in Fig. 5, where T ℓ is the set of tags given to Cℓitems, with the frequency of each tag.

-6.50

Number of clusters

-5

C N2

strongweak

U9

Log-likelihood of relation (x 10 )highweighted
tags

...

...

...
U N1

user
clusters

C1
C2

U2

T8

..
.

To create user models for a given data set, the following steps
are followed: (1) preform relational clustering for the matrix R (abinary relational matrix of U × C), and (2) use tag weighting to
extract the characteristics of each user cluster. After the first step,
user clusters and content clusters are generated simultaneously.
Next, the characteristics of each content cluster are determinedby gathering the tag frequencies, as shown in Table 1. We will
introduce a tag weighting technique in Section 4.1, and we will beinterested in the tags with the highest weights.
Finally, we integrate the results from the above two steps, andthe characteristics of all of the individual users are output as a setof weighted tags. Fig. 4 shows an example of the relationships
between components in the user-modeling algorithm. In step (1),the relationship between Uk and Cℓ is determined by η̄(k, ℓ), andthen in step (2), each content cluster Cℓ is characterized by the setof tags with the highest weights.
η̄(k, ℓ)C8..
.

2.3 User-Modeling Algorithm

U1

T7

C7

U1

(2)

where m(k, ℓ) and m̄(k, ℓ) are, respectively, the number of 1s and 0s
in the intersection of the k-th cluster (k = 1, 2, ..., N1 ) with the ℓ-th
cluster (ℓ = 1, 2, ..., N2 ), and β is a parameter of the IRM.

T6

Using Tag Weighting to Extract the Characteristics of User Clusters

The tag-weighting technique is similar to term frequency–inverse

document frequency tf-idf weighting, and our goal is to determine
which tags have special significance for each user cluster. Thus, thecharacteristics of the user clusters correspond to the tags with thehighest weights.
Let T ℓ and tag t ∈ T correspond, respectively, to a document anda term in tf-idf weighting. Hence, tft,ℓ indicates the frequency oft in T ℓ , and{dft denotes the number} of T ℓ such that tft,ℓ , 0. Let
idft = max 0, log ((N2 − df t )/df t ) , where N2 denotes the numberof content clusters [8]. Thus, the weight of t in T ℓ is

U9 users are likely to be primarily interested in general topics, butalso interested to some degree in programming. This knowledge
was obtained as an output of the user modeling. On the other hand,since it is diﬃcult to obtain more-specific user preferences, it isnecessary to further refine our proposed method.
0.3
0.2

(3)

0.1

In order to compare this with T ℓ (ℓ√= 1, 2, ..., N2 ), we then normal∑
2
ize Eq. (3) by dividing it by w0 =t∈T ℓ wt,ℓ :0

wt,ℓ = tft,ℓ · idf t .

wt,ℓ
w∗t,ℓ =.
w0

C1
 η̄(1, 1) η̄(2, 1)

..


.
η̄(N1 , 1)

C2
η̄(1, 2)η̄(2, 2)..
.
η̄(N1 , 2)

...
...
...
..
.
...

C N2

η̄(1, N2 ) η̄(2, N2 ) 
.
..


.
η̄(N1 , N2 )(5)

Since this paper focuses on the users, the sum ofrow in Eq. (5)∑Neach2
should be 1, as compared with Cℓ ; however, ℓ=1
η̄(k, ℓ) , 1. So,
we normalize η̄(k, ℓ):η̄∗ (k, ℓ) =where η̄0 =cluster Uk is∑N2η̄(k, ℓ)
,
η̄0

N2
∑

5

10

15

20

Figure 8: Top-20 w9 (t) tags for U9 usersη̄∗ (k, ℓ) · w∗t,ℓ .

5.

(7)

ℓ=1

The solutions to Eq. (7) provide the Uk user characteristics for large
values of wk (t).

4.2 User Modeling in Social Bookmarking
We applied user modeling to the clustering result discussed in
Section 3. First, we used Eq. (4) to compute the tag weights; Fig. 7
shows the 20 tags with the largest weights (top-20) for each T ℓ(N2 = 8). In this figure, the x-axis and the y-axis indicate therank of the tags and their weights, respectively, with the top-3 tags
written in boxes. For example, note that all of the top-3 tags in
T 1 are associated with topical news, and the tags of T 3 are terms
related to engineering in the IT field.
As seen above, tag weighting allows us to infer the characteristics of each cluster. However, at the same time, the characteristics
of some tag sets, such as T 8 , are{ uncertain. Note that }use of themodified idf formula idft = max 0, log ((N2 − df t )/df t ) is important in this experiment, since applying the conventional formulaidft = log (N2 /df t ) leads to undesirable weighting, in which severalof the tags end up in the top-3 of diﬀerent T ℓ sets.
As mentioned above, in Fig. 7, the height of the gray area in the
background represents η̄(9, ℓ). In this figure, we can see that the
tags in T 1 , T 6 , and T 8 are characteristic of the users in U9 ; this isconfirmed by the top-20 w9 (t), which are shown in Fig. 8. Most
top-20 tags are rather general terms, but there are some heavily
weighted technical tags, such as w9 (“swift”) and w9 (“VBA”). Thus,

EVALUATION AND DISCUSSION

In the previous sections, we discussed how to extract from folksonomic data the structure of groups and the characteristics of users.
In this section, we will evaluate the correctness of the extracteduser models, by using this information to make recommendations.
We will use the results of user modeling to learn the data, create
recommendations based on the user models, and then evaluate theaccuracy of recommendations using test data. Importantly, in practical terms, the number of iterations for IRM-based clustering (IRM
iterations) is a crucial factor for running time.
In this section, we will use relational tuples, instead of the relational matrix used above. For example, the relational matrix in
Eq. (1) can also be represented as a set of relational tuples:{(1, a), (1, e), (2, a), (2, d), (3, c), (3, d), (4, b)},(6)ℓ=1 η̄(k, ℓ). The weight of the tag t for each userwk (t) =)(4)

Next, our approach integrates Eq. (4) and η̄(k, ℓ) to compute theweight of the tag for each user cluster. As shown in Eq. (2), η̄(k, ℓ)
is determined for each intersection:
U1
U2
..
.
U N1

swift (T 6 ) cinema graph (T8 )  rental space (T6 )   VBA (T8 )+(8)where the tuple (X,Y) means that user X has a connection to item
Y. Note that the size of the set in Eq. (8) is equal to the number of
1s in Eq. (1).
As mentioned in Section 3, the social bookmarking data set has
1,017 users and 7,000 web pages. We represented this data as relational tuples and evaluated them by 5-fold cross validation. Table 3
shows the numbers of tuples, 80% for learning and 20% for testing,in each cross validation step.
Table 3: Number of tuples in the social bookmarking data set
All
100% 172,365
Learning
80% 137,892
Test
20%
34,473After dividing the data, we reconverted the learning tuples intoa relational matrix and then performed user modeling, as shown in
the previous sections.
IRM-based clustering is implemented in C, and we ran the program on Vine Linux 6.3 (32bit) with an Intel(R) Core(TM) i7-2600
CPU @ 3.40GHz and 4GB RAM. After relational clustering, theresults were handled by codes written in Python 2.7.8.

5.1

User-Model-Based Recommendation

We chose recommended web pages for every user cluster. As
shown in Table 2, user cluster k has overall tag weights wk (t), so
our recommendation algorithm can compute the prediction degree
Pk (p) of web page p for the k-th user cluster:∑Pk (p) =wk (t).
(9)t added top

To give an example, as a result of user modeling in the first crossvalidation step, the sorted Pk (p) for the largest user cluster k in

0.6
0.4

0.6

T1

election (tf=84, df=1)
South Sudan (tf=73, df=1)

0

docker (tf=1129, df=3)

buﬀalo (tf=38, df=1)

0.4

GIMP (tf=195, df=1)

0.4

0.2

Tactics Ogre
(tf=38, df=1)

0.2

Responsive web design(tf=713, df=3)

0.2

0
5

10

15

0.6
0.4

PATLABOR(tf=55, df=1)
sea accident (tf=39, df=1)

0.2

Kumamon (tf=38, df=1)

0

20

5
0.6

T5

0.4
0.2

0

10

15

swift
(tf=576, df=3)
cash flow(tf=134, df=2)
rental space(tf=119, df=1)

20

0.4

10

15

10

15

20

5
0.6

T

7
awk (tf=281, df=1)
dummy data
(tf=256, df=1).htaccess (tf=185, df=1)

0.2

5

10

15

20

10

15

20

cinema graphT8(tf=86, df=1)
VBA (tf=134, df=2)
So Takei, Japanese Athlete(tf=104, df=2)

0.4
0.2

0

20

T4
nasal congestion(tf=382, df=1)
podcast (tf=489, df=2)
nose (tf=266, df=1)

0
5

0.6

T6

0
5

0.6

T3

0.4

UNICEF (tf=65, df=1)

0.2

0.6

T2

torne (tf=49, df=1)

0
5

10

15

20

5

10

15

20

Figure 7: Top-20 w∗t,ℓ in T ℓ and top-3 tags; the height of the gray areas in the background indicates η̄∗ (9, ℓ). Words in italics are
Japanese tags that were translated into English.

IRM iteration
Iter 1
Iter 2Iter 3Iter 4Iter 5Prediction degree

0.3
0.25
0.2
0.15
0.1
0.05
0
0

200

400

600

800

1000

1200

Rank of web pages

Figure 9: Sorted Pk (p) in diﬀerent IRM iterations
Fig. 9 also depicts that prediction degrees may not be aﬀectedby the number of IRM iterations. Hence, we can use earlier cluster
assignments for fast, practical recommendations.
After computing the Pk (p), web pages were recommended when
the prediction degree exceeded the threshold θ, that is, Pk (p) > θ
for web page p; then p was recommended to each user u ∈ Uk , excluding any p for which (u, p) was in the learning data. We call thisrecommendation the user-model-based filtering algorithm (UMF).
The precise procedure of UMF is described as Algorithm 1.
Algorithm 1 Find all recommended pages, using a threshold θ
1: L ← ∅▷ list of recommended relational tuples
2: for k = 1, 2, ..., N1 do
3:for all {p | p ∈ C} do▷ all web pages
4:
Pk (p) ← 0
5:
for all tag t added to p do
6:
Pk (p) ← Pk (p) + wk (t)7:if Pk (p) > θ then▷ filtering web page8:
for all {u | u ∈ Uk and (u, p) < Learning} do
9:L ← L ∪ {(u, p)}
10: return L

Evaluation Based on the F-measure andRunning TimeIn this section, we will use the F-measure to evaluate the accuracy of the recommendations, and then we will discuss the eﬀectiveness of the proposed user-modeling method. As a result of the
UMF procedure, both the precision and the recall can be computed,
as follows:|L ∩ Test|
Precision =
,
(10)
|L|
|L ∩ Test|
Recall =.
(11)|Test|
We applied UMF with various values of θ in order to determine the optimal threshold value. As can be seen in Fig. 10, theF-measure peaked when θ = 0.025 for every IRM iteration; wealso note that for this value, the overall running time except for
IRM-based clustering was acceptable. When θ < 0.025, too many
web pages were recommended, the running time was much longer,
and the F-measure was lower. Thus, 0.025 is the optimal thresholdvalue. Note that this is the result of 5-fold cross validation.
0.02

120
IRM iteration (running time)
Iter 1 ( 4.914 sec.)
Iter 2 (+13.926 sec.)
Iter 3 (+25.256 sec.)
Iter 4 (+34.304 sec.)
Iter 5 (+45.464 sec.)

0.015

0.01

100
80

F-measure

60
40

0.005

Time [sec.]

0.35

5.2

F-measurediﬀerent IRM iterations are shown in Fig. 9. This figure clearly
illustrates that only about 400 web pages (out of 7,000 total) aresignificant.

20
0running time (not include IRM-based clustering)

0

0.05

0.1

0.15

0.2

0.25

0

0.3

Threshold
Figure 10: F-measure and running time (except for IRM-based
clustering), for diﬀerent thresholds and iterations
Actually, in Fig. 10, the F-measure increased from the first IRM
iteration to the second IRM iteration, but it is clear that the numberof iterations did not aﬀect the accuracy after the second iteration.
This fact can be also confirmed by Fig. 6 because, at the second iter-

ation, the IRM-based clustering already reached the nearly-optimal
likelihood. That is, more iterations do not lead to better F-measuresin our method. Hence, from here, we will only focus on the cluster
assignments after the second IRM iteration (green line in Fig. 10)
for eﬃcient recommendation. To obtain the assignments, relational
clustering takes 18.84 [s] before tag weighting (4.914 [s] in the first
iteration and 13.926 [s] in the second iteration).
UMF for the second IRM iteration with θ = 0.025 generated
333,951 recommended relations (tuples) on average of 5-fold crossvalidation. For comparison, we also considered 5-fold cross validation with 333,951 random recommendations as the worst cases. Fora single user, we also examined the results of user-based collaborativefiltering (CF) and top-n recommendation, a straightforward andcommonly used recommendation algorithm. With CF, we chose theJaccard similarity coeﬃcient to compute the similarities between
the selected user and the other users. Table 4 shows the F-measuresand running times for these three diﬀerent methods.
Table 4: F-measure and running time obtained by the 5-foldcross validation with the three diﬀerent methods
MethodF-measure Time [s]Random (average of five)0.00891—
CF and top-328 for a single user
0.10273 367.278
UMF (θ = 0.025)
0.0182029.933 ††This time is sum of 18.84 [s] for the IRM-based clustering
and 11.093 [s] for UMF shown in Algorithm 1.
Since CF compares the similarities separately, the F-measure is
not very low. However, despite the calculation of recommendations
for only a single user, the running time was more than ten times
longer than that of our proposed method. To make recommendations for 1,017 users like UMF, CF will compute scores for over one
hour. The main reason for this is that we roughly accomplished usermodeling, and the user characteristics were approximated. Naturally, these running times strongly depend on the particular implementation, but such a wide gap will persist. Note that N = 328
in the top-n recommendation comes from 333951/1017 ≒ 328, because we considered a single user, and there are 1,017 users in total.

5.3 Discussion
As can be seen in Table 4, UMF was more accurate than theworst cases, and the running time was acceptable. Therefore, ourmethod successfully extracted practical user models. The collaborative filtering-based top-n recommendation was even more accurate, but that approach is time consuming. CF encountered many
diﬀerent problems, such as a cold start and sparsity [1].
It should be noted that Algorithm 1 requires users to choose athreshold value, but an optimal θ may depend on data sets. Evenif θ = 0.025 yields poor results in diﬀerent data sets, searching an
optimal threshold like Fig. 10 every time is certainly time consuming. In this case, top-n approach will be more promising because
the prediction degree shows characteristic distribution as shown in
Fig. 9. Folksonomic data generally suﬀers from a lot of garbage
tags, one-time only tags. So, such specific distribution of Pk (p) is
probably general, and it makes easier to implement top-n recommender systems.
Currently, numerous recommendation algorithms have been proposed, but none is suﬃciently versatile. For instance, even thoughmatrix factorization [7] is considered a promising solution for the
problem of dimensionality in CF, this technique does not work as
expected on a very large, sparse, and binary matrix, such as the
U × C used in this study; however, a new branched method has
been proposed [13]. As this branching process is repeated, the outcomes will be increasingly unrealistic.

Hence, it is important to gain more sketchy knowledge. From
this perspective, the motivation behind many recent studies on largesocial networks makes sense. Similarly, this study also satisfies thisdemand by providing relational-cluster-based user modeling. We
note that user models can be used not only to provide recommendations, but also for other purposes, such as marketing.

6.

CONCLUSION

In this paper, we have proposed a user-modeling method for folksonomy data sets. The method uses the results of IRM-based relational clustering. The experimental results showed that our method
discovered semantically clustered tag groups, and thus user modeling was possible. Therefore, this paper has revealed that relational
clustering works successfully for folksonomy data sets. Moreover,
we made recommendations based on user models, and these performed well in terms of running time. In the future, further experimental supports are required because the Jaccard similarities in CF
can be approximated by more eﬃcient techniques like MinHash.
Our method does not use a vector space model and does not require preprocessing, and it is a relatively rough method for mining folksonomic data; however, the results have also revealed some
limitations. As a next step, we intend to consider larger data sets
and time series of U × C. Furthermore, we intend to incorporate
related work on relational data analysis, such as the work by Rendle and Schmidt [10], and to apply an advanced IRM [4] in order toobtain cleaner user models and more accurate recommendations.

7.

REFERENCES[1] J. Bobadilla et al. Recommender systems survey.
Knowledge-Based Systems, 46:109–132, July 2013.
[2] J. Gemmell et al. Personalization in folksonomies based on
tag clustering. In Proc. of the 6th Workshop on Intelligent
Techniques for Web Personalization and Recommender
Systems, pages 37–48, Apr. 2008.
[3] A. Hotho et al. Information Retrieval in Folksonomies:
Search and Ranking, pages 411–426. Springer Berlin
Heidelberg, 2006.
[4] K. Ishiguro et al. Subset infinite relational models. In Proc.
of AISTATS2012, pages 547–555, Apr. 2012.
[5] C. Kemp et al. Learning systems of concepts with an infinite
relational model. In Proc. of AAAI2006, pages 381–388, July
2006.
[6] T. Kitazawa and M. Sugiyama. Relational clustering in social
bookmark. In Proc. of ECEI2014, 2A05, Aug. 2014.
[7] Y. Koren et al. Matrix factorization techniques forrecommender systems. Computer, 42(8):30–37, Aug. 2009.
[8] C. D. Manning et al. Introduction to Information Retrieval.
Cambridge Univ. Press, 2008.
[9] S. Niwa et al. Web page recommender system based onfolksonomy mining. In Proc. of ITNG2006, pages 388–393,
Apr. 2006.
[10] S. Rendle and L. Schmidt-Thieme. Pairwise interaction
tensor factorization for personalized tag recommendation. In
Proc. of WSDM2010, pages 81–90, Feb. 2010.
[11] A. Shepitsen et al. Personalized recommendation in social
tagging systems using hierarchical clustering. In Proc. of
RecSys2008, pages 259–266, Oct. 2008.
[12] Z. Xu et al. Towards the semantic web: Collaborative tag
suggestions. In Proc. of the Collaborative Web Tagging
Workshop at WWW2006, May 2006.
[13] Z. Zhang et al. Binary matrix factorization with applications.
In Proc. of ICDM2007, pages 391–400, Oct. 2007.