Categorizing documents
View Patent ↗Categorizing documents is disclosed. A hierarchy of topics is received. A seed for each topic is determined. One or more documents is received. The seed is used to evaluate the relevance of each document to one or more of the received topics. One or more topics is associated with each document.
1. A method comprising:
receiving, by a computer system, a selection of a seed set from a linked document corpus, the seed set relating to a topic;
calculating, by the computer system, for each document of the linked document corpus, a destination score according to a biased random walk of the linked document corpus, where the random walk is biased toward the seed set;
calculating, by the computer system, for each document of the linked document corpus, a source score according to an effect of the each document on the destination scores of other documents in the linked document corpus according to a link structure of the linked document corpus;
receiving a query identifying the topic;
selecting one or more documents from the linked document corpus according to topic scores based on a combination of the source and destination scores of the documents of the linked document corpus; and
returning the selected one or more document as a result for the query
wherein calculating, by the computer system, for each document of the linked document corpus, the destination score according to a biased random walk of the linked document corpus further comprises:
initializing source scores for the documents of the linked document corpus, such that documents of the seed set have a non-zero source score and other documents have a source score of zero;
calculating the destination score for the each document according to a random walk of a link structure of the linked document corpus with random teleportation to documents of the linked document corpus where a probability of teleportation to a document is proportional to a source score thereof.
2. The method of claim 1 , wherein the topic scores are based on a weighted combination of the source and destination scores.
3. The method of claim 1 , wherein calculating, by the computer system, for each document of the linked document corpus, the destination score according to a biased random walk of the linked document corpus further comprises:
initializing source scores for the documents of the linked document corpus, such that documents of the seed set have a non-zero source score and other documents have a source score of zero;
initializing destination scores for the documents of the linked document corpus to zero;
calculating an updated destination score b(p) for the each document p of the linked document corpus, where b(p) is an element of a vector b calculated according to βAb+(1−β)s/|s|, where β is an arbitrary probability, A is matrix encoding a link structure of the linked document corpus, b is a vector of current destination scores for the document corpus, and s is a vector of current source scores of the linked document corpus.
4. The method of claim 3 , further comprising:
calculating an updated source score s(p) for each document p of the linked document corpus, where s(P is an element of a vector s calculated according to
s ( p )=Σ q∈N r p ( q ) d ( q )
where r p (q) is a stationary probability for document p and d(q) is the destination score of a document q in the linked document corpus.
5. The method of claim 4 , wherein the stationary probability r p (q) is an element of vector r p that is a solution to the equation r p =βAr p +(1−β)v p , where v p is a teleport vector centered on document p, where the vector v p is equal to s/|s|.
6. The method of claim 3 , further comprising:
calculating an updated source score s(p) for each document p of the linked document corpus, where s(P is an element of a vector s calculated according to
s
(
p
)
=
∑
q
∈
N
r
p
(
q
)
r
(
q
)
d
(
q
)
where r p (q) is a stationary probability for document q with respect to document p, r(q) is an unbiased probability of page q, and d(q) is the destination score of a document q in the linked document corpus.
7. The method of claim 3 , further comprising:
calculating an updated source score s(p) for each document p of the linked document corpus, where s(P is an element of a vector s calculated according to
s
(
p
)
=
{
N
ϕ
S
+
∑
q
∈
N
r
p
(
q
)
r
(
q
)
d
(
q
)
if
p
∈
s
(
1
-
ϕ
)
∑
q
∈
N
r
p
(
q
)
r
(
q
)
d
(
q
)
if
p
∉
s
where r p (q) is a stationary probability for document q with respect to document p, r(q) is an unbiased probability of page q, d(q) is the destination score of a document q in the linked document corpus, S is the seed set, and φ is a factor effective to reduce at least one of topic drift and topic generalization.
8. The method of claim 1 , further comprising, adding documents of the linked document corpus according to the source scores.
9. The method of claim 8 , wherein calculating, by the computer system, for each document of the linked document corpus, the source score according to an effect of the each document on the destination scores of other documents in the linked document corpus according to a link structure of the linked document corpus further comprises:
calculating the source score according to both an initial value of the source score for the each document and according to an effect of the each document on the destination scores of other documents in the linked document corpus.
10. A system comprising one or more processors and one or more memory devices operably coupled to the one or more processors, the one or more memory devices storing executable and operational code effective to cause the one or more processors to:
receive a selection of a seed set from a linked document corpus, the seed set relating to a topic;
calculate for each document of the linked document corpus, a destination score according to a biased random walk of the linked document corpus, where the random walk is biased toward the seed set;
calculate for each document of the linked document corpus, a source score according to an effect of the each document on the destination scores of other documents in the linked document corpus according to a link structure of the linked document corpus;
receive a query identifying the topic;
select one or more documents from the linked document corpus according to topic scores based on a combination of the source and destination scores of the documents of the linked document corpus; and
return the selected one or more document as a result for the query
wherein the executable and operational data are further effective to cause the one or more processors to calculate for each document of the linked document corpus, the destination score according to a biased random walk of the linked document corpus by:
initializing source scores for the documents of the linked document corpus, such that documents of the seed set have a non-zero source score and other documents have a source score of zero;
calculating the destination score for the each document according to a random walk of a link structure of the linked document corpus with random teleportation to documents of the linked document corpus where a probability of teleportation to a document is proportional to a source score thereof.
11. The system of claim 10 , wherein the topic scores are based on a weighted combination of the source and destination scores.
12. The system of claim 10 , wherein the executable and operational data are further effective to cause the one or more processors to calculate for each document of the linked document corpus, the destination score according to a biased random walk of the linked document corpus by:
initializing source scores for the documents of the linked document corpus, such that documents of the seed set have a non-zero source score and other documents have a source score of zero;
initializing destination scores for the documents of the linked document corpus to zero;
calculating an updated destination score b(p) for the each document p of the linked document corpus, where b(p) is an element of a vector b calculated according to βAb+(1−β)s/|s|, where β is an arbitrary probability, A is matrix encoding a link structure of the linked document corpus, b is a vector of current destination scores for the document corpus, and s is a vector of current source scores of the linked document corpus.
13. The system of claim 12 , wherein the executable and operational data are further effective to cause the one or more processors to:
calculate an updated source score s(p) for each document p of the linked document corpus, where s(P is an element of a vector s calculated according to
s ( p )=Σ q∈N r p ( q ) d ( q )
where r p (q) is a stationary probability for document p and d(q) is the destination score of a document q in the linked document corpus.
14. The system of claim 13 , wherein the stationary probability r p (q) is an element of vector x that is a solution to the equation r p =βAr p +(1−β)v p , where v p is a teleport vector centered on document p, where the vector v p is equal to s/|s|.
15. The system of claim 12 , wherein the executable and operational data are further effective to cause the one or more processors to:
calculate an updated source score s(p) for each document p of the linked document corpus, where s(P is an element of a vector s calculated according to
s
(
p
)
=
∑
q
∈
N
r
p
(
q
)
r
(
q
)
d
(
q
)
where r p (q) is a stationary probability for document q with respect to document p, r(q) is an unbiased probability of page q, and d(q) is the destination score of a document q in the linked document corpus.
16. The system of claim 12 , wherein the executable and operational data are further effective to cause the one or more processors to:
calculate an updated source score s(p) for each document p of the linked document corpus, where s(P is an element of a vector s calculated according to
s
(
p
)
=
{
N
ϕ
S
+
∑
q
∈
N
r
p
(
q
)
r
(
q
)
d
(
q
)
if
p
∈
s
(
1
-
ϕ
)
∑
q
∈
N
r
p
(
q
)
r
(
q
)
d
(
q
)
if
p
∉
s
where r p (q) is a stationary probability for document q with respect to document p, r(q) is an unbiased probability of page q, d(q) is the destination score of a document q in the linked document corpus, S is the seed set, and φ is a factor effective to reduce at least one of topic drift and topic generalization.
17. The system of claim 10 , wherein the executable and operational data are further effective to cause the one or more processors to add documents of the linked document corpus according to the source scores.
18. The system of claim 17 , wherein the executable and operational data are further effective to cause the one or more processors to calculate for each document of the linked document corpus, the source score according to an effect of the each document on the destination scores of other documents in the linked document corpus according to a link structure of the linked document corpus by:
calculating the source score according to both an initial value of the source score for the each document and according to an effect of the each document on the destination scores of other documents in the linked document corpus.