
	Randomly generate k centroids associated with k clusters
	Assign each vector to one of the k clusters
	Repeat until termination condition met:
	Re-determine cluster centroids
	Reassign each vector to a cluster

In the K-means algorithm, an arbitrary number k is predefined. In some embodiments k is a value between 2 and 16, while in some other embodiments k is a value between 2 and 50. K random vectors in the vector space of the word value vectors are generated. The k random vectors are the initial centroids for the vector space. Each initial centroid represents the “center” of a cluster. In other words, k initial clusters and their centers are arbitrarily defined. Each word value vector is assigned to one of the k clusters based on the similarity (distance) between the respective word value vector and each centroid. A word value vector is assigned to the centroid with which it is most similar (shortest distance).

In some embodiments, the similarity (distance) between a word value vector and a centroid is the cosine similarity (also known as “cosine distance”):

\cos θ = \frac{X \cdot Y}{ X  \times  Y }

where X·Y is the dot product of vectors X and Y, ∥X∥×∥Y∥ is the length of vector X times the length of vector Y, and cos θ is the cosine similarity. If vectors X and Y are exactly the same, the cosine similarity value is 1. The range of values for cosine similarity in these embodiments is between 0 and 1, inclusive (the cosine similarity can never be negative because the word values can never be negative). Thus, reviews with cosine similarity closer to 1 are more similar (shorter distance), while reviews with cosine similarity closer to 0 are more dissimilar (longer distance). In some other embodiments, alternatives manners of determining the distance or similarity may be used.

In some embodiments, a number of predefined canonical reviews may be used as the initial centroids. The canonical reviews are a set of predefined reviews that serve as exemplars of reviews commenting on particular aspects of a subject. The set of canonical reviews may vary, depending on what the subject of the corpus of reviews is. For example, the set of canonical reviews for a subject that is a product, which may include canonical reviews for aspects such as ease of use and performance, may be different than the set of canonical reviews for a subject that is a product provider, which may include canonical reviews for aspects such as customer service and shipping timeliness.

After the word value vectors are assigned to the k clusters, centroids for the k clusters are determined anew. That is, the centroids are re-determined for each cluster. The centroid for a cluster may be determined by taking the “average” of the word value vectors in the cluster (not including the initial centroid; the initial centroid is relevant for only the initial cluster assignment). The formula for determining a centroid C is:

C = \frac{\sum_{i = 1}^{CS} V_{i}}{CS}

where CS is the size of the cluster (number of word value vectors in the cluster), and V_iare normalized (converted to vectors of unit length) vectors of the word value vectors in the cluster.

Upon determination of the new centroids, the word vector values are reassigned into clusters, this time based on the similarity to the new centroids. A word value vector is assigned to the centroid to which it is most similar. After each word value vector is reassigned to a cluster, the iteration of re-determining the centroids and re-assigning the word value vectors repeat. The iteration repeats until a termination condition is met. In some embodiments, the termination condition is when a convergence criterion is met. The convergence criterion may be that no word value vectors are reassigned to a different cluster after the completion of an iteration. In some other embodiments, the termination condition is that a predefined number of iterations have been performed.

It should be appreciated that alternative manners of clustering, such as hierarchal clustering, the fuzzy c-means algorithm, and others, may be used.

Upon grouping the reviews into clusters, the sizes of the review clusters are identified (508). This is simply the number of reviews (represented by the word value vectors, not including the centroid) in each cluster.

Reviews are selected from each cluster (510). In some embodiments, reviews are selected from each cluster in proportion to the cluster sizes. A predefined total number of reviews are selected from the corpus of reviews to serve as a sample of the corpus of reviews. The reviews in the sample are selected from the clusters in proportion to the sizes of the clusters. The sample would have more reviews selected from a larger cluster than a smaller cluster. In some embodiments, a cluster that is extremely small (for example, less than a predefined number of reviews or less than a predefined percentage of the number of total reviews in the corpus) may be excluded from the review selection; no review from that cluster will be selected for inclusion in the sample. If a cluster is excluded, then one or more reviews may be selected from other clusters so that the number of reviews in the sample reaches the predefined total number.

In some embodiments, reviews may be selected from a cluster based on additional predefined criteria. For example, reviews may be selected from a cluster based on the quality of the reviews, as described above, in relation toFIG. 4. Reviews of high quality are generally more informative and easier to read than reviews of low quality. Thus, for example, if 10 reviews are to be selected from a cluster, then with the additional quality criterion, the 10 highest quality reviews from that cluster may be selected. As another example, reviews may be selected from a cluster based on the ratings associated with the reviews, such as the selection process described above, in relation toFIG. 3. More generally, as long as a cluster contributes to the review sample a number of reviews that is proportional to the cluster size, reviews from that cluster may be selected based on zero or more predefined criteria.

A response that includes the selected reviews is generated (512). The generated response is a document that is transmitted to aclient102 for rendering and presentation to a user. The response document includes the review summary for the subject. The reviews summary may include information such as the overall rating for the subject and optionally the collective ratings for the subject given by the review sources. The reviews summary also includes the reviews sample, which includes content from the selected reviews, as described above, in relation toFIG. 2.

By clustering reviews and selecting reviews from the clusters, a review sample that is representative of the topical focus of the reviews is selected. Clustering helps the reviews engine identify reviews that focus on particular aspects of a subject. By separating the reviews by the aspect upon which the review focuses (into the clusters) and selecting reviews from the clusters for inclusion in a reviews sample, a user, upon being shown the reviews sample, can get a better understanding of which aspects of the subject are particularly noteworthy or were of particular concern to other users who have had experience with the subject.

FIG. 6 is a flow diagram of a process for generating a snippet from high quality content within a review, according to some embodiments of the invention. To save time, a user may prefer to read only parts of reviews rather than the full content of reviews. The reviews engine may select particular content within reviews for inclusion in the reviews sample as review snippets.

A review is identified (602). The identified review is divided into partitions (604). In some embodiments, the partitions are the sentences of the review. That is, each sentence of the review is a partition of the review. Sentences in the review may be identified based on sentence delimiters such as periods. It may be the case that a review may only have one partition, such as when the review has only one sentence. For convenience of explanation, the process ofFIG. 5 will be described below as if the partitions of reviews are the sentences of the reviews. It should be appreciated, however, that alternative manners of partitioning a review (such as partitions of Z words, where Z is a predefined whole number) may be used.

A quality score is determined for each sentence of the review (606). The quality score for a review sentence is similar to the quality score for a review, as described above in relation toFIG. 4. The sentence quality score provides a basis for a relative ordering of the sentences of a review with regard to their quality. The quality score may be based on one or more factors. A sub-score may be determined based on each of the factors. The sub-scores may be combined into the quality score for a sentence, using the weighted sum equation similar to that described in relation toFIG. 3 above. In some embodiments, the predefined factors include the length of the sentence, values associated with words in the sentence, and the position of the sentence within the review.

With regard to the length of a review sentence, sentences that are not too long and not too short (i.e., sentence of “reasonable length”) are favored. Extremely short sentences may not include much information and extremely long sentences may be difficult to read. In some embodiments, a sub-score based on sentence length may be based on the deviation of the sentences in the review from a predefined “optimal” sentence length. The sentence length may be based on a word count or a character count.

With regard to values associated with words in the sentence, sentences with high value words are favored over sentences with low value words. In some embodiments, the word values are based on the inverse document frequency (IDF) values associated with the words, similar to the word value factor used in scoring reviews, described above in relation toFIG. 4. For a sentence, a frequency for each distinct word in the sentence is determined and multiplied by the IDF for that word. The word value sub-score for the review is:

{WV}_{P} = \sum_{w \in P}^{} f_{w, P} \log {IDF}_{w}

where WV_Pis the word value sub-score for sentence P, f_w,Pis the number of occurrences of word w in sentence P, and log IDF_wis the logarithm of the IDF value for word w.

In some other embodiments, word values are based on a predefined dictionary of words that are deemed valuable in a reviews context. Separate dictionaries may be defined for different subject types, as different words may be valuable for use in reviews regarding different subject types. For example, there may be a dictionary of valuable words for reviews where the subject is a product and another dictionary of valuable words for reviews where the subject is a provider. In these embodiments, the word value sub-score may be based on a count of how many of the words in the predefined dictionary are included in the respective sentence.

With regard to the position of the sentence within the review, in some embodiments the reviews engine may favor sentences that occur in the beginning of the review. Thus, a sub-score based on position may be based on the position of the sentence in the review, normalized for the number of sentences in the review. For example, for the 4th sentence of a review with 10 sentences, the position sub-score for that sentence may be 4/10=0.2.

Upon determination of the sub-scores for a sentence, the sub-scores may be mathematically combined into a quality score for the sentence, using the formula similar to that described above, in relation toFIG. 4.

Combinations of the review sentences are identified (608). Each combination includes one or more consecutive sentences of the review that satisfies predefined length criteria. In some embodiments, the length criteria are that the length of the combination is equal to a predefined maximum snippet length (which may be based on a word count or a character count) or exceeds the maximum snippet length by a portion of the last sentence in the combination. An exemplary algorithm for identifying the combinations is illustrated by the pseudocode below:


	For each sentence i in the review:
	integer j = i
	combination i = sentence j
	while (length(combination i) < max_snippet_length)
	combination i = combination i + sentence (++j)

As illustrated in the pseudocode above, the combination starts out as one sentence in the review, and subsequent sentences are appended to the combination, up to and including the first sentence that makes the length of the combination equal to or greater than the maximum snippet length. Thus, a combination is a concatenation of as many consecutive sentences of the review as possible without making the length of the combination exceed the maximum snippet length, plus possibly one additional sentence that, when added to the combination, makes the length of the combination equal to or greater than the maximum snippet length.

In some other embodiments, the algorithm may be refined to also consider how much of the sentence to be appended will be within the maximum snippet length, i.e., how much “space” remains in the combination to accommodate an additional sentence. For example, it may be more worthwhile to not append an additional sentence to a combination when the combination is only one or two words short of the maximum snippet length.

A combination with the highest combined quality score is selected (610). In some embodiments, the combined quality score for a combination is a simple sum of the quality scores of the sentences within the combination. In some other embodiments, the combined quality score may be a weighted sum, simple average, or weighted average of the quality scores of the sentences within the combination.

A snippet is generated using the selected combination (612). The snippet includes the selected combination, up to the maximum snippet length. If the combination exceeds the maximum snippet length, content is truncated from the end of the combination until the length of the combination is equal to the maximum snippet length. In some embodiments, the combination may be truncated to be shorter than the maximum snippet length if only a small part (e.g., one or two words) of the last sentence in the combination remains after the truncation to the maximum snippet length. In other words, it may be more worthwhile to truncate by removing the last sentence in the combination if only a few words of that sentence will remain after truncating the combination to the maximum snippet length.

A response including the snippet is generated (614). The generated response is a document that is transmitted to aclient102 for rendering and presentation to a user. The response document includes the review summary for the subject. The reviews summary may include information such as the overall rating for the subject and optionally the collective ratings for the subject given by the review sources. The reviews summary also includes the reviews sample, which includes content from the selected reviews, as described above, in relation toFIG. 2.

Reviews engine

106 selects reviews from its reviews repository and generates a response including content from the selected reviews (such as full reviews and/or snippets) for transmission to aclient102.FIGS. 3,4, and5 illustrate three processes for selecting reviews for the sample.FIG. 6 illustrates a process for generating a snippet of a review, which may be a review selected in the processes ofFIGS. 3,4, and/or5. It should be appreciated that the processes above may be combined. For example, thereviews engine106 may select a number of reviews that correspond to the rating range into which the overall score falls and have high quality scores. As another example, thereviews engine106 may cluster reviews for a subject and select from each cluster, in proportion to the cluster sizes, reviews that correspond to the rating range into which the overall score falls and have high quality scores. Snippets of these selected reviews are generated and a response including the snippets is generated. More generally, reviews may be selected based on one or more predefined criteria and snippets of these reviews may be generated and included in a response sent to theclient102.

FIG. 7 is a block diagram illustrating areviews processing system700, according to some embodiments of the invention. Thesystem700 typically includes one or more processing units (CPU's)702, one or more network orother communications interfaces710,memory712, and one ormore communication buses714 for interconnecting these components. Thesystem700 optionally may include auser interface704 comprising adisplay device706 and a keyboard/mouse708.Memory712 includes high-speed random access memory, such as DRAM, SRAM, DDR RAM or other random access solid state memory devices; and may include non-volatile memory, such as one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, or other non-volatile solid state storage devices.Memory712 may optionally include one or more storage devices remotely located from the CPU(s)702.Memory712, or one or more of the storage devices (e.g., one or more non-volatile storage devices) inmemory712, includes a non-transitory computer readable storage medium. In some embodiments,memory712 or the computer readable storage medium ormemory712 stores the following programs, modules and data structures, or a subset thereof:

- anoperating system716 that includes procedures for handling various basic system services and for performing hardware dependent tasks;
- anetwork communication module718 that is used for connecting thereviews processing system700 to other computers via the one or more communication network interfaces710 (wired or wireless), such as the Internet, other wide area networks, local area networks, metropolitan area networks, and so on;
- areview storage interface720 that interfaces with a review storage system;
- asource identification module722 that identifies sources of reviews;
- areview identification module724 that identifies reviews and associated ratings from review sources;
- anoverall rating module726 that determines an overall rating for a subject and determining which rating range the overall rating falls under;
- a reviewquality scoring module728 that determines quality scores for reviews;
- a review clustering module730 that organizes reviews into clusters;
- areview partition module732 that divides reviews into partitions, determines quality scores for the partitions, identifies combinations of partitions, and selects the combination with the highest combined quality score;
- a review selection module734 that selects reviews based on one or more predefined criteria;
- acontent filter736 that evaluates reviews and review partitions for content satisfying predefined content criteria, such as objectionable content; and
- aresponse generation module738 that generates responses that include reviews and/or snippets of reviews.

Thesystem700 also includes areview storage system740. Thereview storage system740 stores reviews and associated ratings. Thereview storage system740 includes asnippet generator742 that generates snippets of reviews. In some embodiments, thesnippet generator742 may be located inmemory712, rather than in thereview storage system740.

Each of the above identified elements may be stored in one or more of the previously mentioned memory devices, and corresponds to a set of instructions for performing a function described above. The above identified modules or programs (i.e., sets of instructions) need not be implemented as separate software programs, procedures or modules, and thus various subsets of these modules may be combined or otherwise re-arranged in various embodiments. In some embodiments,memory712 may store a subset of the modules and data structures identified above. Furthermore,memory712 may store additional modules and data structures not described above.

AlthoughFIG. 7 shows a “reviews processing system,”FIG. 7 is intended more as functional description of the various features which may be present in a set of servers than as a structural schematic of the embodiments described herein. In practice, and as recognized by those of ordinary skill in the art, items shown separately could be combined and some items could be separated. For example, some items shown separately inFIG. 7 could be implemented on single servers and single items could be implemented by one or more servers. The actual number of servers used to implement a reviews processing system and how features are allocated among them will vary from one implementation to another, and may depend in part on the amount of data traffic that the system must handle during peak usage periods as well as during average usage periods.

It should be appreciated that the description above are not limited in their application to reviews that are purely textual, i.e., consisting of strings of characters. The description is capable of adaptation to reviews that includes audio, video, or other forms of media. For example, for a review that includes audio (such as audio-only reviews or a video reviews with an audio track), the audio may be converted to text using speech to text conversion, which are well known in the art. The converted text may be used as the “review” for the selection and snippet generation processes described above. The snippet of an audio or video review would the portion of the audio or video that has the speech with the words that were selected for a snippet based on the converted text of the review. If review quality is a criterion for selecting audio/video reviews, the grammatical quality factor may be adapted for the medium. For example, capitalization is not very relevant when the content of the review is verbal rather than textual, and thus can be disregarded.

The foregoing description, for purpose of explanation, has been described with reference to specific embodiments. However, the illustrative discussions above are not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated.