Cluster-based identification of news stories

Abstract

Methods, systems, and techniques for cluster-based content recommendation are described. Some embodiments provide a content recommendation system (“CRS”) configured to recommend news stories about events or occurrences. In some embodiments, a news story about an event includes multiple related content items that each include an account of the event and that each reference one or more entities or categories that are represented by the CRS. In one embodiment, the CRS identifies news stories by generating clusters of related content items. Then, in response to a received query that indicates a keyterm, entity, or category, the CRS determines and provides indications of one or more news stories that are relevant to the received query. In some embodiments, at least some of these techniques are employed to implement a news story recommendation facility in an online news service.

1 . A method in a content recommendation computing system, the method comprising:
 using a processor of the computing system, automatically identifying a news story about an event, the news story including multiple related content items that each give an account of the event and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, comprising:
 processing content items to determine semantic information that includes identified entities and relations between the identified entities; 
 storing the identified entities and relations in a repository of the content recommendation system; 
 generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items, wherein generating the cluster comprises:
 finding a candidate cluster of a plurality of clusters that is nearest to one of the multiple related content items by computing a cosine distance between a term vector that represents the one content item and a term vector that represents a content item of the candidate cluster; and 
 determining whether the candidate cluster is a suitable cluster for the one content item, based at least on: cosine distances between the one content item and content items of the candidate cluster and a quantity of content items of the candidate cluster that have a cosine distance to the content item that is below a predetermined threshold; and 
 
 storing an indication of the identified news story and the generated cluster. 
   
     
     
         2 . The method of  claim 1  wherein generating the cluster includes:
 if the candidate cluster is determined to be a suitable cluster, adding the one content item to the candidate cluster; and 
 if the candidate cluster is not determined to be a suitable cluster, creating a new cluster that includes the one content item as a seed. 
 
     
     
         3 . (canceled) 
     
     
         4 . The method of  claim 3  wherein finding the candidate cluster that is nearest to one of the multiple related content items includes comparing the one content item to content items of the candidate cluster. 
     
     
         5 . The method of  claim 3  wherein finding the candidate cluster that is nearest to one of the multiple related content items includes comparing the one content item to a centroid of the candidate cluster. 
     
     
         6 . The method of  claim 3  wherein finding the candidate cluster includes computing a cosine distance between a term vector that represents the one content item and a term vector that represents a content item of the candidate cluster. 
     
     
         7 . The method of  claim 3  wherein finding the candidate cluster includes finding a cluster that includes a content item that has a cosine distance to the one content item that is lower than cosine distances between the one content item and other content items of other clusters. 
     
     
         8 . The method of  claim 1  wherein identifying the news story includes processing only content items published during a time interval that is about one day in length. 
     
     
         9 . The method of  claim 1  wherein identifying the news story includes reassigning content items from clusters that are smaller than a specified size to clusters that are larger than the specified size. 
     
     
         10 . The method of  claim 1  wherein identifying the news story includes merging two clusters into a single cluster when distances between centroids of the two clusters are lower than a specified threshold. 
     
     
         11 . The method of  claim 1  wherein identifying the news story includes generating two or more sub-clusters of the generated cluster, each sub-cluster including one or more of the multiple related content items. 
     
     
         12 . The method of  claim 11  wherein generating the two or more sub-clusters includes decomposing the multiple content items using a k-means process. 
     
     
         13 . The method of  claim 11  wherein generating the two or more sub-clusters includes discarding a candidate sub-cluster if a distance measured between a centroid of the generated cluster and a centroid of the candidate sub-cluster is lower than a specified threshold. 
     
     
         14 . The method of  claim 11  wherein generating the two or more sub-clusters includes retaining a candidate sub-cluster if a distance measured between a centroid of the generated cluster and a centroid of the candidate sub-cluster is greater than a specified threshold. 
     
     
         15 . The method of  claim 1  wherein identifying the news story includes determining a representative content item for the news story by selecting one of the multiple related content items that is nearest to a centroid of the generated cluster. 
     
     
         16 . The method of  claim 1  wherein storing the indication of the identified news story and the generated cluster includes storing an association between a keyterm, entity, or category and the generated cluster, along with an indicator of relevance of the keyterm, entity, or category to the generated cluster. 
     
     
         17 . The method of  claim 1  wherein storing the indication of the identified news story and the generated cluster includes storing one or more of: a representative content item for the identified news story; a representative image for the identified news story; a centroid of the generated cluster, the centroid including a vector of keyterms and/or entity identifiers; top categories for the identified news story; two or more sub-clusters for the identified news story; a growth rate of the generated cluster; and a date. 
     
     
         18 . The method of  claim 1 , further comprising:
 receiving a search query that includes an indication of a keyterm, entity or category;   selecting a news story from a plurality of news stories, the selecting based on how many keyterms, entities, or categories are in common between the received search query and the multiple content items of the selected news story; and   transmitting an indication of the selected news story.   
     
     
         19 . The method of  claim 18 , further comprising:
 selecting multiple news stories that are each relevant to the received search query; and   sorting the multiple selected news stories based on one or more of: the number of content items in each news story, a rate of growth of the number of content items in each news story, an importance of the indicated keyterm, entity, or category to content items in each news story, an age of each news story.   
     
     
         20 . A method in a content recommendation computing system for recommending a news story about an event, the news story including multiple content items that each give an account of the event, and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, comprising:
 receiving a search query that includes an indication of an entity or a category;   using a processor of the computing system, automatically selecting the news story from a plurality of news stories, the selecting based on how many entities or categories are in common between the received search query and the multiple content items of the selected news story, wherein each of the plurality of news stories has a corresponding cluster that includes multiple related content items, the cluster based at least on cosine distances between term vectors that each correspond to a different one of the multiple content items and that each reference keyterms, entities, and categories that are referenced by the corresponding content item and that are electronically represented by the content recommendation system; and   transmitting an indication of the selected news story.   
     
     
         21 . The method of  claim 20 , further comprising:
 for a plurality of content items in a plurality of news stories about an event,
 processing content items to determine semantic information that includes identified entities and relations between the identified entities; 
 storing the identified entities and relations in a repository of the content recommendation system; 
 generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items; and 
 storing an indication of the identified news story and the generated cluster. 
   
     
     
         22 . A non-transitory computer-readable medium including contents that enable a computing system to recommend content, by performing the method comprising:
 using a processor of the computing system, automatically identifying a news story about an event, the news story including multiple related content items that each give an account of the event and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, comprising:
 processing content items to determine semantic information that includes identified entities and relations between the identified entities; 
 storing the identified entities and relations in a repository of the content recommendation system; 
 generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items, the cluster based at least on cosine distances between term vectors that each correspond to a different one of the multiple content items and that each reference keyterms, entities, and categories that are referenced by the corresponding content item and that are electronically represented by the content recommendation system; and 
 storing an indication of the identified news story and the generated cluster. 
   
     
     
         23 . The computer-readable medium of  claim 22  wherein the computer-readable medium is at least one of a memory in a mobile computing device or a data transmission medium transmitting a generated signal containing the contents. 
     
     
         24 . The computer-readable medium of  claim 22  wherein the contents are instructions that when executed cause the computing system to perform the method. 
     
     
         25 . A computing system configured to recommend content, comprising:
 a memory;   a code module stored on the memory that is configured, when executed by a processing unit of the computing system, to automatically identify a news story about an event, the news story including multiple related content items that each give an account of the event and that each reference multiple entities or categories that are each electronically represented by the content recommendation system, by:
 processing content items to determine semantic information that includes identified entities and relations between the identified entities; 
 storing the identified entities and relations in a repository of the content recommendation system; 
 generating a cluster that includes the multiple related content items, based at least in part on how many entities each of the multiple related content items has in common with one or more other of the multiple related content items, wherein generating the cluster includes:
 finding a candidate cluster of a plurality of clusters that is nearest to one of the multiple related content items by computing a cosine distance between a term vector that represents the one item and a term vector that represents a content item of the candidate cluster; 
 determining whether the candidate cluster is a suitable cluster for the one content item, based at least on: cosine distances between the one content item and content items of the candidate cluster and a quantity of content items of the candidate cluster that have a cosine distance to the content item that is below a predetermined threshold; and 
 
 storing an indication of the identified news story and the generated cluster. 
   
     
     
         26 . The computing system of  claim 25  wherein the code module includes software instructions for execution in the memory of the computing system. 
     
     
         27 . The computing system of  claim 25  wherein the code module is a content recommendation system. 
     
     
         28 . The computing system of  claim 25  wherein the computing system is a mobile computing device and the module is a content recommendation module. 
     
     
         29 . The computing system of  claim 25  wherein the code module is configured to automatically recommend news stories to at least one of a personal digital assistant, a smart phone, a laptop computer, a tablet computer, and/or a third-party application.