Link spam detection using smooth classification function
View Patent ↗A spam detection system is disclosed. The system includes a classifier training component that receives a first set of training pages labeled as normal pages and a second set of training pages labeled as spam pages. The training component trains a web page classifier based on both the first set of training pages and the second set of training pages. A spam detector then receives unlabeled web pages uses the web page classifier to classify the unlabeled web pages as spam pages or normal pages.
1. A spam detection system, comprising:
a classifier training component that receives a first set of training pages labeled as normal pages and a second set of training pages labeled as spam pages, wherein the classifier training component trains a web page classifier based on both the first set of training pages and the second set of training pages; and
a spam detector that receives unlabeled web pages and, utilizing a computer processor, applies the web page classifier so as to classify the unlabeled web pages as either spam pages or normal pages.
2. The system of claim 1 , wherein the first set of training pages are marked by a trusted entity as content.
3. The system of claim 1 , wherein the second set of training pages are marked by a trusted entity as spam.
4. The system of claim 1 and further comprising:
a random walk component performing a random walk over a directed graph, having nodes representing web pages in a collection of web pages and edges representing links among the web pages in the collection, to obtain stationary probabilities for the web pages.
5. The system of claim 4 , wherein nodes representing the first set of training pages are labeled with a first training value indicative of a normal page, and wherein nodes representing the second set of training pages are labeled with a second training value indicative of a spam page.
6. The system of claim 5 , wherein the classifier training component optimizes a cost function that penalizes a difference between the classifier function value for the nodes representing the first set of training pages and the first training value and a difference between nodes representing the second set of training pages and the second training value.
7. The system of claim 6 , wherein the classifier training component optimizes the cost function that penalizes differences in function value from node-to-node in the directed graph.
8. The system of claim 4 , wherein the random walk component divides the directed graph into strongly connected directed graph components.
9. The system of claim 4 , wherein the random walk component selects a starting point in the directed graph and repeatedly moves to a new node in the directed graph by selecting uniformly, at random, whether to follow a link from a current node to another node in the directed graph or to randomly jump to another node in the directed graph.
10. The system of claim 9 , wherein the random walk component selects whether to follow a link according to a predefined random walk definition.
11. The system of claim 10 , wherein the predefined random walk definition comprises:
one of following outlinks from the current node, inlinks to the current node, and inlinks or outlinks regardless of direction relative to the current node.
12. A computer-implemented method of detecting spam in a collection of web pages, the method comprising:
receiving a first set of training pages labeled as content pages and a second set of training pages labeled as spam pages;
training a web page classifier based on both the first set of training pages and the second set of training pages; and
receiving unlabeled web pages and, utilizing a computer processor, classifying the unlabeled web pages as either spam pages or normal pages based on the web page classifier.
13. The method of claim 12 , wherein the first set of training pages are marked by a trusted entity as non-spam.
14. The method of claim 12 , wherein the first set of training pages are marked by a trusted entity as spam.
15. The method of claim 12 , and further comprising:
performing a random walk over a directed graph, having nodes representing web pages in a collection of web pages and edges representing links among the web pages in the collection, to obtain stationary probabilities for the web pages.
16. The method of claim 15 , wherein nodes representing the first set of training pages are labeled with a first training value indicative of a normal page, and wherein nodes representing the second set of training pages are labeled with a second training value indicative of a spam page.
17. The method of claim 16 , comprising optimizing a cost function that penalizes a difference between a classifier function value for the nodes representing the first set of training pages and the first training value and a difference between nodes representing the second set of training pages and the second training value.
18. The method of claim 17 , comprising optimizing the cost function that penalizes differences in function value from node-to-node in the directed graph.
19. The method of claim 18 , wherein performing the random walk comprising selecting a starting point in the directed graph and repeatedly moving to a new node in the directed graph by selecting uniformly, at random, whether to follow a link from a current node to another node in the directed graph or to randomly jump to another node in the directed graph.
20. The method of claim 19 , wherein performing the random walk comprising selecting whether to follow a link according to a predefined random walk definition.