System and method for mining tags using social endorsement networks
Descriptive data relating to at least a subset of a plurality of entities on a website is retrieved over a network. Endorsement data relating to the plurality of entities is retrieved from the website. A first set of probabilities is determined reflecting a probability that endorsements can be attributed to specific aspects. A second set of probabilities is determined reflecting a probability that terms can be attributed to aspects. Using the first set of probabilities and the second set of probabilities, a subset of the terms that are most probably associated with each entity are selected. Tags are then generated for each entity using the selected terms.
1. A method comprising:
retrieving, over a network at a computing device, descriptive data relating to at least a subset of a plurality of entities on a website, the descriptive data comprising a plurality of descriptive data entries, each descriptive data entry relating to a respective one of the subset of the plurality of entities;
retrieving, over the network at the computing device, from the website, endorsement data relating to the plurality of entities, the endorsement data comprising a plurality of endorsements, each endorsement relating to a respective one of the plurality of entities and a respective one of a plurality of users;
determining, via the computing device, based on the descriptive data and the endorsement data, a first set of probabilities, each of the first set of probabilities reflecting a probability that a respective one of the plurality of endorsements is attributable to a respective one of a plurality of aspects, each of the plurality of aspects representing a cluster of entities, wherein said determination of the first set of probabilities comprises:
determining, using the computing device, using the descriptive data and the endorsement data, a third set of probabilities, each of the third set of probabilities reflecting a probability that a respective one of the plurality of users associated with a respective one of the plurality of endorsements made the respective endorsement due to a respective one of the plurality of aspects;
determining, using the computing device, using the descriptive data and the endorsement data, a fourth set of probabilities, each of the fourth set of probabilities reflecting a probability that a respective one of the plurality of entities was endorsed in a respective one of the plurality of endorsements due to a respective one of the plurality of aspects; and
determining, using the computing device, the first set of probabilities using the third set of probabilities and the fourth set of probabilities;
determining, via the computing device, based on the descriptive data and the endorsement data, a second set of probabilities, each of the second set of probabilities reflecting a probability that a respective one of a plurality of terms is attributable to a respective one of the plurality of aspects;
selecting, via the computing device, based on the first set of probabilities and the second set of probabilities, for each entity, a respective subset of the plurality of terms that are most probably associated with the respective entity; and
generating, via the computing device, for each entity, based on the respective subset of the plurality of terms that are most probably associated with the respective entity, a respective set of tags, each tag reflecting one of the subset of the plurality of terms.
2. The method of claim 1 where the third set of probabilities is p(k|u) and the fourth set of probabilites is p(e|k) which are determined as follows, let:
U denote a set of users who endorse entities picked from a set ε,
K be a set of aspects,
α′ and β′ be Dirichlet smoothing parameters,
Ψ: {φ uk =p(k|u), ∀uεU, kεK} represents a set of aspect-user distributions,
ξ: {ξ ke =p(e|k), ∀kεK, eεε} represents the set of entity-aspect distributions,
Dir is an LDA function
e i and y i indicate an entity in the endorsed set ε(u) of the user u
and the aspect it is sampled from, respectively;
the endorsement generation process is:
for all aspects k; sample ξ k ˜Dir(β′);
for all users u; sample ψ u ˜Dir(α′)
for each endorsement slot ε(u)
(a) Sample an aspect y i ˜Mult(ψ u )
(b) Sample an entity e i ˜Mult(ψ u ).
3. The method of claim 2 where the distribution-sets ψ and ξ are learned by finding an assignment of each endorsement to an aspect using a collapsed Gibbs sampling method.
4. The method of claim 3 where collapsed Gibbs sampling method uses the equation
P
(
y
i
=
k
❘
e
i
=
l
,
e
-
i
,
y
-
1
)
∝
n
k
❘
u
,
-
1
+
α
′
ɛ
(
u
)
+
α
′
K
×
n
e
❘
k
,
-
i
+
β
′
n
.
❘
k
,
i
+
β
′
ɛ
where n k|u,−i is the number of times aspect k is observed for user u,
n e|k,−i is the number of times entity e is sampled from aspect k,
|ε(u)| is number of entities endorsed by user u, and
n. |k,−i is the total number of entities generated from aspect k,
such that the above quantities are computed over all endorsement-slots except the i th one.
5. The method of claim 2 where each of the first set of probabilities is θ ek =p(k|e), calculated as follows for each of the plurality of aspects k and each of the plurality of entities e:
θ
ek
=
p
(
k
❘
e
)
=
p
(
e
,
k
)
p
(
e
)
∝
∑
u
ɛ
U
p
(
u
)
p
(
k
❘
u
)
p
(
e
❘
k
)
where p(u) is the probability that a user u makes an endorsement.
6. The method of claim 1 where each of the second set of probabilities is p(t|k), determined using a term-aspect distribution as follows:
Φ:{Φ kt =p ( t|k )∀ k εK,tεK,tεν}
where Φ is a term-aspect distribution for all terms and aspects,
φ kt is a term-aspect distribution for a particular term t and aspect k,
K is the plurality of aspects;
ν is a vocabulary of terms.
7. The method of claim 5 where the term-aspect distribution is determined by sampling a value for an aspect z i that generated the term w at a term-slot t i using aspect assignments of all other term-slots z−i as follows:
P
(
z
i
=
k
❘
t
i
=
w
,
t
-
i
,
z
-
i
)
∝
n
k
❘
e
,
-
i
+
α
d
e
,
-
i
+
α
K
×
n
t
❘
k
,
=
i
+
β
n
.
❘
k
,
-
i
+
β
υ
where n k|e,−i is the number of times one of the plurality of aspects k is observed for one of the plurality of entities e,
n t|k,−i is the number of times one of the plurality of terms t is sampled from k,
|d e,−1 is the number of term occurrences associated with e, and
n. |k,−i is the total number of entities generated from aspect k,
α and β are Dirichlet smoothing parameters.
8. The method of claim 1 where the term-aspect distribution is determined by sampling a value for an aspect z i that generated the term w at a term-slot t i using aspect assignments of all other term-slots z−i as follows:
P
(
z
i
=
k
❘
t
i
=
w
,
t
-
1
,
z
-
i
)
∝
p
(
k
❘
e
)
×
n
t
❘
k
,
-
i
+
β
n
.
❘
k
,
=
i
+
β
υ
where n t|k,−i is the number of times one of the plurality of terms t is sampled from k,
n. |k,−i s the total number of entities generated from aspect k,
β is a Dirichlet smoothing parameter
ν is a vocabulary of terms.
9. The method of claim 5 where the probability that a given entity e can be associated with a given term t, p(e|t), is calculated as follows:
p
(
e
❘
t
)
=
p
(
e
,
t
)
/
p
(
t
)
=
∑
k
p
(
e
)
p
(
k
❘
e
)
p
(
t
❘
k
)
/
p
(
t
)
where p(t) is a reduction in entropy associated with the presence of term t.
10. The method of claim 9 where p(t) is calculated as follows.
p
(
t
)
=
∑
k
∑
e
p
(
e
)
p
(
k
❘
e
)
p
(
t
❘
k
)
where p(e)=1/|ε| is assumed to be the same for all entities.
11. The method of claim 1 wherein the at least a subset of a plurality of entities comprises less than all of the plurality of entities.
12. The method of claim 1 wherein the descriptive data is retrieved from the website.
13. The method of claim 1 wherein the descriptive data is retrieved from a data source separate from the website.
14. The method of claim 1 further comprising:
determining, using the computing device, for each of the at least a subset of the plurality of entities, a frequency of each of the respective subset of terms in the respective descriptive data entries for the respective entity, wherein the terms having the highest frequency are selected.
15. The method of claim 1 further comprising:
transmitting, over the network, for each of the plurality of entities, the respective set of tags to the website; and
causing, using the computing device, the website to update each of the plurality of entities with the respective set of tags relating to the entity.
16. A computing device comprising:
a processor;
a storage medium for tangibly storing thereon program logic for execution by the processor, the program logic comprising:
descriptive data retrieving logic executed by the processor for retrieving descriptive data relating to at least a subset of a plurality of entities on a website, the descriptive data comprising a plurality of descriptive data entries, each descriptive data entry relating to a respective one of the subset of the plurality of entities;
endorsement data retrieving logic executed by the processor for retrieving from the website, endorsement data relating to the plurality of entities, the endorsement data comprising a plurality of endorsements, each endorsement relating to a respective one of the plurality of entities and a respective one of a plurality of users;
entity-aspect determination logic executed by the processor for determining based on the descriptive data and the endorsement data, a first set of probabilities, each of the first set of probabilities reflecting a probability that a respective one of the plurality of endorsements is attributable to a respective one of a plurality of aspects, each of the plurality of aspects representing a cluster of entities, wherein the entity-aspect determination logic comprises logic executed by the processor for:
determining based on the descriptive data and the endorsement data, a third set of probabilities, each of the third set of probabilities reflecting a probability that a respective one of the plurality of users associated with a respective one of the plurality of endorsements made the respective endorsement due to a respective one of the plurality of aspects;
determining based on the descriptive data and the endorsement data, a fourth set of probabilities, each of the fourth set of probabilities reflecting a probability that a respective one of the plurality of entities was endorsed in a respective one of the plurality of endorsements due to a respective one of the plurality of aspects; and
determining the first set of probabilities based on the third set of probabilities and the fourth set of probabilities;
term-aspect determination logic executed by the processor for determining, based on the descriptive data and the endorsement data, a second set of probabilities, each of the second set of probabilities reflecting a probability that a respective one of a plurality of terms is attributable to a respective one of the plurality of aspects;
tag selection logic executed by the processor for selecting based on the first set of probabilities and the second set of probabilities, for each entity, a respective subset of the plurality of terms that are most probably associated with the respective entity; and
tag generation logic executed by the processor for generating, for each entity, based on the respective subset of the plurality of terms that are most probably associated with the respective entity, a respective set of tags, each tag reflecting one of the subset of the plurality of terms.
17. A non-transitory computer-readable storage media for tangibly storing thereon computer readable instructions, that when executed by a processor, perform a method comprising:
retrieving descriptive data relating to at least a subset of a plurality of entities on a website, the descriptive data comprising a plurality of descriptive data entries, each descriptive data entry relating to a respective one of the subset of the plurality of entities;
retrieving from the website, endorsement data relating to the plurality of entities, the endorsement data comprising a plurality of endorsements, each endorsement relating to a respective one of the plurality of entities and a respective one of a plurality of users;
determining based on the descriptive data and the endorsement data, a first set of probabilities, each of the first set of probabilities reflecting a probability that a respective one of the plurality of endorsements is attributable to a respective one of a plurality of aspects, each of the plurality of aspects representing a cluster of entities, wherein said determination of the first set of probabilities comprises:
determining based on the descriptive data and the endorsement data, a third set of probabilities, each of the third set of probabilities reflecting a probability that a respective one of the plurality of users associated with a respective one of the plurality of endorsements made the respective endorsement due to a respective one of the plurality of aspects;
determining based on the descriptive data and the endorsement data, a fourth set of probabilities, each of the fourth set of probabilities reflecting a probability that a respective one of the plurality of entities was endorsed in a respective one of the plurality of endorsements due to a respective one of the plurality of aspects; and
determining the first set of probabilities based on the third set of probabilities and the fourth set of probabilities;
determining, based on the descriptive data and the endorsement data, a second set of probabilities, each of the second set of probabilities reflecting a probability that a respective one of a plurality of terms is attributable to a respective one of the plurality of aspects;
selecting based on the first set of probabilities and the second set of probabilities, for each entity, a respective subset of the plurality of terms that are most probably associated with the respective entity; and
generating, for each entity, based on the respective subset of the plurality of terms that are most probably associated with the respective entity, a respective set of tags, each tag reflecting one of the subset of the plurality of terms.