 |
Claims  |
|
|
What is claimed is:
1. Client-server based apparatus for recommending an item to one of a plurality of users situated at a client computer, the client computer connected to a server computer,
wherein the item has not yet been rated by the one user, the apparatus comprising:
(A) the server computer having a first memory associated therewith, wherein the server:
(A1) stores a user profile, in the first memory, for each of a plurality of users, wherein the user profile comprises a separate rating value, supplied by a particular one of the users, for each corresponding one of a plurality of items, said
items including the item non-rated by the user;
(A2) stores an item profile, in the first memory, for each of the rated items, comprises a separate rating value, for a particular one of the items, provided by each one of the plurality of the users, wherein the user profile and the item profile
are distinct from each other; and
(A3) in response to a request issued by the client computer, accesses rating information from the user and item profiles stored in the first memory and provides the rating information to the client computer; and
(B) the client computer comprising:
(B1) a processor; and
(B2) a second memory, connected to the processor, for storing computer executable instructions therein; and
(B3) wherein the processor, in response to the executable instructions:
(B3a) issues, in response to interaction with the one user, the request to the server computer for the rating information;
(B3b) calculates, for each one of the plurality of users and in response to the rating information received from the server computer, a plurality of similarity factors, between said each one user and at least one other one of the users, for each
of said items, including said non-rated item;
(B3c) selects, in response to the plurality of similarity factors and for each one of the plurality of users, a plurality of neighboring ones of the users, such that each of the neighboring ones of the users has an associated similarity factor
which is greater than a first predefined threshold value or, if a confidence factor is associated with the associated similarity factor, both the associated similarity factor is less the first predefined threshold and the confidence factor exceeds a
second predefined threshold value;
(B3d) assigns a corresponding weight to each of the neighboring users so as to define a plurality of weights; and
(B3e) recommends at least one of a plurality of the items to said one user in response to the plurality of weights and ratings given to the non-rated item by the neighboring ones of the users.
2. The apparatus in claim 1 wherein the processor, in response to the executable instructions:
obtains additional rating information for at least one item from a given one of the users; and
supplies the additional rating information to the server computer; and
the server computer updates, in response to the additional rating information, the user and item profiles stored in the first memory.
3. The apparatus in claim 2 wherein profile data, forming the user and item profiles stored in the first memory, is organized into a plurality of profile sections and the request specifies a particular one of the profile sections for which
rating information is to be provided by the server computer, the one section being associated with a class of said items through which a recommendation could be obtained through the client computer to the one user.
4. The apparatus in claim 3 wherein the client computer is situated at a kiosk.
5. The apparatus in claim 3 wherein the server computer further comprises means for permitting a plurality of users, each stationed at a different one of a plurality of client computers, to share information amongst themselves related to the
items.
6. The apparatus in claim 3 wherein the user profile comprises either a set of user n-tuples or a first set of pointers to storage locations in the memory at which user entries are stored, wherein each of the user n-tuples comprises a separate
rating value, supplied by a particular one of the users, for each corresponding one of a plurality of items, said items including the item non-rated by the user and each of the user entries stores a separate rating for an associated one of the users for
a corresponding one of the items.
7. The apparatus in claim 6 wherein the item profile comprises either a set of item n-tuples or a second set of pointers to storage locations in the memory at which item entries are stored, wherein each of the item n-tuples comprises a separate
rating value, for a particular one of the items, provided by each one of the plurality of the users and each of the item entries stores a rating for an associated one of the items by a corresponding one of the users.
8. The apparatus in claim 7 wherein the calculating step further comprises the steps of:
receiving a rating from the given one of the users for a given one of the plurality of items so as to define a received rating;
updating the user profile associated with the given one user by either writing the received rating into an appropriate one of the user n-tuples or writing the received rating into an appropriate one of the user entries;
updating the item profile associated with the given one item by writing the received rating into an appropriate one of the item n-tuples or writing the received rating into an appropriate one of the item entries; and
calculating, for the given one user, a plurality of said similarity factors, wherein each of the similarity factors for said given one user represents similarity between said given one user and another one of the users with respect to the items.
9. The apparatus in claim 3 wherein the item profile comprises either a set of item n-tuples or a second set of pointers to storage locations in the memory at which item entries are stored, wherein each of the item n-tuples comprises a separate
rating value, for a particular one of the items, provided by each one of the plurality of the users and each of the item entries stores a rating for an associated one of the items by a corresponding one of the users.
10. The apparatus in claim 9 wherein the user profile comprises either a set of user n-tuples or a first set of pointers to storage locations in the memory at which user entries are stored, wherein each of the user n-tuples comprises a separate
rating value, supplied by a particular one of the users, for each corresponding one of a plurality of items, said items including the item non-rated by the user and each of the user entries stores a separate rating for an associated one of the users for
a corresponding one of the items.
11. The apparatus in claim 10 wherein the calculating step further comprises the steps of:
receiving a rating from the given one of the users for a given one of the plurality of items so as to define a received rating;
updating the user profile associated with the given one user by either writing the received rating into an appropriate one of the user n-tuples or writing the received rating into an appropriate one of the user entries;
updating the item profile associated with the given one item by writing the received rating into an appropriate one of the item n-tuples or writing the received rating into an appropriate one of the item entries; and
calculating, for the given one user, a plurality of said similarity factors, wherein each of the similarity factors for said given one user represents similarity between said given one user and another one of the users with respect to the
items. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF THE INVENTION
The present invention relates to a system for facilitating exchange of user information and opinion and, in particular, to a distributed method for facilitating exchange of user information and opinion using automated collaborative filtering.
BACKGROUND OF THE INVENTION
The amount of information, as well as the number of goods and services, available to individuals is increasing exponentially. This increase in items and information is occurring across all domains, e.g. sound recordings, restaurants, movies,
World Wide Web pages, clothing stores, etc. An individual attempting to find useful information, or to decide between competing goods and services, is often faced with a bewildering selection of sources and choices.
Individual sampling of all items, even in a particular domain, may be impossible. For example, sampling every restaurant of a particular type in New York City would tax even the most avid diner. Such a sampling would most likely be
prohibitively expensive to carry out, and the diner would have to suffer through many unenjoyable restaurants.
In many domains, individuals have simply learned to manage information overload by relying on a form of generic referral system. For example, in the domain of movie and sound recordings, many individuals rely on reviews written by paid
reviewers. These reviews, however, are simply the viewpoint of one or two individuals and may not have a likelihood of correlating with how the individual will actually perceive the movie or sound recording. Many individuals may rely on a review only
to be disappointed when they actually sample the item.
One method of attempting to provide an efficient filtering mechanism is to use content-based filtering. The content-based filter selects items from a domain for the user to sample based upon correlations between the content of the item and the
user's preferences. Content-based filtering schemes suffer from the drawback that the items to be selected must be in some machine-readable form, or attributes describing the content of the item must be entered by hand. This makes content-based
filtering problematic for existing items such as sound recordings, photographs, art, video, and any other physical item that is not inherently machine-readable. While item attributes can be assigned by hand in order to allow a content-based search, for
many domains of items such assignment is not practical. For example, it could take decades to enter even the most rudimentary attributes for all available network television video clips by hand.
Perhaps more importantly, even the best content-based filtering schemes cannot provide an analysis of the quality of a particular item as it would be perceived by a particular user, since quality is inherently subjective. So, while a
content-based filtering scheme may select a number of items based on the content of those items, a content-based filtering scheme generally cannot further refine the list of selected items to recommend items that the individual will enjoy.
SUMMARY OF THE INVENTION
The present invention relates to a system which collects a number of subjective ratings given to items by users. The described system allows users to provide ratings wherever and whenever such provision is convenient for the user. For example,
a user may provide ratings for objects in the comfort and privacy of their own home via the internet, or a user may provide ratings at a retail establishment specializing in particular items. The system also allows the rating information provided by the
users to be used to recommend items to the user, and to allow the user to locate individuals having similar tastes. The system may also be used to allow users having similar tastes to communicate with each other.
In one aspect, the present invention relates to a system for facilitating exchange of user information and opinion about items which includes memory elements for storing user profiles and item profiles. The system also includes a calculator for
calculating similarity factors between users and a selector for selecting neighboring users for each user based on the similarity factors. The system assigns a weight to each one of the neighboring users and uses the ratings given to items by those
neighboring users to recommend an item to the user. In some embodiments, the system includes a communication means that allows users to engage in dialog with each other and share information about items. In other embodiments, the system includes a user
recommender which refers users to other users based on the similarity factors calculated by the system.
In another aspect, the invention relates to a distributed system for managing user profile data used to facilitate the exchange of user information and opinion. The distributed system includes a central server which is connected to a network and
the server includes a memory element for storing user profile data. At least one node is connected to the network and the node includes a memory element for caching user profile registration information, a receiver for receiving user profile
registration information and a transmitter for transmitting the received user profile registration information to the central server. In some embodiments, the node periodically tries to transmit user profile registration information to the central
server. The node may also include memory elements for storing user profiles and item profiles, a calculator for calculating similarity factors between users of the distributed system, a selector for selecting a plurality of neighboring users based on
the calculated similarity factors, a means for assigning a weight to each of those neighboring users, and an item recommender for recommending items to users based on ratings given to items by the neighboring users and the weights assigned to those
neighboring users.
BRIEF DESCRIPTION OF THE DRAWINGS
This invention is pointed out with particularity in the appended claims. The above and further advantages of this invention may be better understood by referring to the following description taken in conjunction with the accompanying drawings,
in which:
FIG. 1 is a flowchart of one embodiment of the method;
FIG. 2 is a diagrammatic view of a user profile-item profile matrix;
FIG. 3 is a flowchart of another embodiment of the method;
FIG. 4 is a block diagram of an embodiment of the apparatus;
FIG. 5 is a block diagram of an Internet system on which the method and apparatus may be used;
FIG. 6 is a block diagram of a distributed system for facilitating exchange of user information and opinion;
FIG. 7 is a flow chart of the steps taken to register a user; and
FIG. 8 is a flow chart of the steps taken to verify whether an alias is in use.
DETAILED DESCRIPTION OF THE INVENTION
As referred to in this description, items to be recommended can be items of any type that a user may sample in a domain. When reference is made to a "domain," it is intended to refer to any category or subcategory of ratable items, such as sound
recordings, movies, restaurants, vacation destinations, novels, or World Wide Web pages. Referring now to FIG. 1, a method for recommending items begins by storing user and item information in profiles.
A plurality of user profiles is stored in a memory element (step 102). One profile may be created for each user or multiple profiles may be created for a user to represent that user over multiple domains. Alternatively, a user may be
represented in one domain by multiple profiles where each profile represents the proclivities of a user in a given set of circumstances. For example, a user that avoids seafood restaurants on Fridays, but not on other days of the week, could have one
profile representing the user's restaurant preferences from Saturday through Thursday, and a second profile representing the user's restaurant preferences on Fridays. In some embodiments, a user profile represents more than one user. For example, a
profile may be created which represents a woman and her husband for the purpose of selecting movies. Using this profile allows a movie recommendation to be given which takes into account the movie tastes of both individuals. For convenience, the
remainder of this specification will use the term "user" to refer to single users of the system, as well as "composite users." The memory element can be any memory element known in the art that is capable of storing user profile data and allowing the
user profiles to be updated, such as disc drive or random access memory.
Each user profile associates items with the ratings given to those items by the user. Each user profile may also store information in addition to the user's rating. In one embodiment, the user profile stores information about the user, e.g.
name, address, or age. In another embodiment, the user profile stores information about the rating, such as the time and date the user entered the rating for the item. User profiles can be any data construct that facilitates these associations, such as
an array, although it is preferred to provide user profiles as sparse vectors of n-tuples. Each n-tuple contains at least an identifier representing the rated item and an identifier representing the rating that the user gave to the item, and may include
any number of additional pieces of information regarding the item, the rating, or both. Some of the additional pieces of information stored in a user profile may be calculated based on other information in the profile, for example, an average rating for
a particular selection of items (e.g., heavy metal albums) may be calculated and stored in the user's profile. In some embodiments, the profiles are provided as ordered n-tuples. Alternatively, a user profile may be provided as an array of pointers;
each pointer is associated with an item rated by the user and points to the rating and information associated with the rating.
A profile for a user can be created and stored in a memory element when that user first begins rating items, although in multi-domain applications user profiles may be created for particular domains only when the user begins to explore, and rate
items within, those domains. Alternatively, a user profile may be created for a user before the user rates any items in a domain. For example, a default user profile may be created for a domain which the user has not yet begun to explore based on the
ratings the user has given to items in a domain that the user has already explored.
Whenever a user profile is created, a number of initial ratings for items may be solicited from the user. This can be done by providing the user with a particular set of items to rate corresponding to a particular group of items. Groups are
genres of items and are discussed below in more detail. Other methods of soliciting ratings from the user may include: manual entry of item-rating pairs, in which the user simply submits a list of items and ratings assigned to those items; soliciting
ratings by date of entry into the system, i.e., asking the user to rate the newest items added to the system; soliciting ratings for the items having the most ratings; or by allowing a user to rate items similar to an initial item selected by the user.
In still other embodiments, the system may acquire a number of ratings by monitoring the user's environment. For example, the system may assume that Web sites for which the user has created "bookmarks" are liked by that user and may use those sites as
initial entries in the user's profile. One embodiment uses all of the methods described above and allows the user to select the particular method they wish to employ.
Ratings for items which are received from users can be of any form that allows users to record subjective impressions of items based on their experience of the item. For example, items may be rated on an alphabetic scale ("A" to "F") or a
numerical scale (1 to 10). In one embodiment, ratings are integers between 1 (lowest) and 7 (highest). Ratings can be received as input to a stand-alone machine, for example, a user may type rating information on a keyboard or a user may enter such
information via a touch screen. Ratings may also be received as input to a system via electronic mail, by telephone, or as input to a system via a local area or wide area network. In one embodiment, ratings are received as input to a World Wide Web
page. In this embodiment, the user positions a cursor on a World Wide Web page with an input device such as a mouse or trackball. Once the cursor is properly positioned, the user indicates a rating by using a button on the input device to select a
rating to enter. Ratings can be received from users singularly or in batches, and may be received from any number of users simultaneously.
Ratings can be inferred by the system from the user's usage pattern. For example, the system may monitor how long the user views a particular Web page and store in that user's profile an indication that the user likes the page, assuming that the
longer the user views the page, the more the user likes the page. Alternatively, a system may monitor the user's actions to determine a rating of a particular item for the user. For example, the system may infer that a user likes an item which the user
mails to many people and enter in the user's profile an indication that the user likes that item. More than one aspect of user behavior may be monitored in order to infer ratings for that user, and in some embodiments, the system may have a higher
confidence factor for a rating which it inferred by monitoring multiple aspects of user behavior. Confidence factors are discussed in more detail below.
Profiles for each item that has been rated by at least one user may also be stored in memory. Each item profile records how particular users have rated this particular item. Any data construct that associates ratings
given to the item with the user assigning the rating can be used. It is preferred is to provide item profiles as a sparse vector of n-tuples. Each n-tuple contains at least an identifier representing a particular user and an identifier
representing the rating that user gave to the item, and it may contain other information, as described above in connection wit h user profiles. As with user profiles, item profiles may also be stored as an array of pointers. Item profiles may be
created when the first rating is given to an item or when the item is first entered into the system. Alternatively, item profiles may be generated from the user profiles stored in memory, by determining, for each user, if that user has rated the item
and, if so, storing the rating and user information in the item's profile. Item profiles may be stored before user profiles are stored, after user profiles are stored, or at the same time as user profiles. For example, referring to FIG. 2, item
profiled at a and user profile data may be stored as a matrix of values which provides user profile data when read "across," i.e. when rows of the matrix are accessed, and provides item profile data when read "down," i.e. when columns of the matrix are
accessed. A data construct of this sort could be provided by storing a set of user n-tuples and a set of item niuples. In order to read a row of the matrix a specific user n-tuple is accessed and in order to read a column of the matrix a specific item
n-tuple is selected.
The additional information associated with each item-rating pair can be used by the system for a variety of purposes, such as assessing the validity of the rating data. For example, if the system records the time and date the rating was entered,
or inferred from the user's environment, it can determine the age of a rating for an item. A rating which is very old may indicate that the rating is less valid than a rating entered recently, for example, users' tastes may change or "drift" over time.
One of the fields of the n-tuple may represent whether the rating was entered by the user or inferred by the system. Ratings that are inferred by the system may be assumed to be less valid than ratings that are actually entered by the user. Other items
of information may be stored, and any combination or subset of additional information may be used to assess rating validity. In some embodiments, this validity metric may be represented as a confidence factor, that is, the combined effect of the
selected pieces of information recorded in the n-tuple may be quantified as a number. In some embodiments, that number may be expressed as a percentage representing the probability that the associated rating is incorrect or as an expected deviation of
the predicted rating from the "correct" value.
Since the system may be hosted by any one of a number of different types of machines, or by a machine that is reconfigured frequently, it is desirable to provide data storage for profiles in a hierarchical, isolated manner. The term "isolated,"
for the purposes of this specification, means that the interface to the physical memory elements storing item and user profiles is abstracted, i.e. the system interacts with the physical memory elements through a defined data object. Although the
description of such a data object is couched in terms of profile data and the associated system for recommending items to users, the data object can be used in any system requiring that access to data be provided in an isolated, hierarchical manner, such
as databases or distributed file systems.
A data object of the sort described provides an abstraction of a physical memory in which profiles are stored. The data object includes an interface for storing data to the physical memory, an interface for retrieving data from the physical
memory, an interface for searching the physical memory, and a link to another data object. In some embodiments the data object is provided with "batch" capability, which will described in detail below.
The interfaces for storing and retrieving profiles from a physical memory implement those functions in a physical memory-specific manner. For example, a data object providing an abstraction of a disk drive memory would accept a "store profile"
or "retrieve profile" command from the system and issue the appropriate device driver commands to the disk drive with which it is associated. These commands may include a simple translation of the "store profile" command received into a "write" command
issued to the disk drive, or the data object may translate "store profile" command into a series of "write" commands issued to the disk drive. Profile data retrieved from the physical memory is provided to the system via the interface for retrieving
data.
The interfaces for storing and retrieving data may be provided as independent functions, dynamically loaded libraries, or subroutines within the object. It is only necessary for the data object to access the underlying physical memory element to
retrieve and store the data element, i.e. profile, requested; the data object need not implement functions provided by the memory element unless it is desirable to do so. For example, a data object representing a cache memory need not implement
functionality for retrieving cache misses from main memory, although it may be desirable to implement a "cache flush" command in the data object that could be used to reset the underlying physical memory.
The data object includes an interface for searching the physical memory. The interface accepts one or more criterion for screening data retrieved from the underlying physical memory. For example, the system may instruct the data object to
retrieve all profiles having ratings for a particular item in excess of "5." Alternatively, the system could instruct the data object to return the profiles of all users younger than 21. The data object receives the criterion and can accomplish the
screen by accessing all the profile information stored in the associated physical memory, applying the requested criterion, and providing the system with any profile that passes. Alternatively, the data object could use some other algorithm for
screening the data, such as running an SQL search on a stored table, or storing the profile data in a tree structure or hash table which allows the physical memory to be efficiently searched.
The "criterion" feature just described is an explication of one of the advantages of the data object described. The system does not need to specify physical memory addresses to access profile data. The system specifies a profile, or set of
profiles, it desires to transfer by reference to profile information. For example, the data object accepts desired profile information from the system (which includes name data, some item of demographic information, rating information, or some set of
this information) and implements the physical memory transfer.
The link identifies another data object to be accessed if the data request cannot be satisfied by the underlying physical memory. For example, a data object representing random access memory may be accessed to retrieve user profiles having a
state address equal to "Massachusetts." If no user profiles stored in the underlying physical memory match the provided criterion, the link, which identifies another data object, is followed. If the link identifies another data object, i.e. if the link
is not a null pointer, the system attempts to fulfill its request from the data object identified by the link. If, in turn, the request cannot be satisfied by the second-identified data object, and the second-identified data object is linked to a third
data object, the system attempts to fulfill its request from the third-identified data object. This process continues until a "null" link is encountered.
The link can be used to arrange the data objects into a hierarchy which corresponds to the order in which the system accesses memory. For example, the system may be provided with a "cache" data object that is linked to a "main memory" data
object, which is in turn linked to a "disk" memory object that is itself linked to a "network." Thus, a system would issue a "retrieve profile" request to the "cache" data object with a criterion of "name=john.sub.-- smith". If the cache memory is
unable to satisfy this request, it is presented to the next data object in the hierarchy, i.e. the "main memory" data object. If the request is satisfied from main memory, the user profile is returned to the cache, which can then satisfy the data
request. The hierarchy of data objects provided by the links can be set up once for a given system or the links may be dynamically rearranged. If the links are set up in a static fashion, they may be specified by a configuration file or, in some
applications, the links may be hardcoded. Dynamic reconfiguration of the links provides a system with the ability to reconfigure its memory hierarchy in response to run-time failures, e.g. a hard drive crash.
When a lower-level data object in the hierarchy satisfies a request that was not able to be fulfilled by a higher-level data object in the hierarchy, the lower-level object returns the result to the next higher-level data object. The
higher-level data object writes the result into its underlying physical memory, and returns the result to another higher-level data object, if necessary. In this manner, memory may be accessed in a hierarchical, isolated manner and data can be
transparently distributed to the most efficient level of memory.
In some embodiments it may be desirable to provide a data object with "batch" capability, i.e. the data object will retrieve more data than requested in an attempt to increase performance. This capability may be provided as a flag that, when
set, indicates that the data object should retrieve more data than requested. Alternatively, the data object may be provided with a function or subroutine which indicates to the data object when and how much should be retrieved in various situations, or
the data object may accept input (e.g. in the form of a passed parameter) from the system instructing it to initiate a batch transfer. For example, a data object may be provided with logic that examines requests and, if the request is one for a user
profile, initiates an access of four user profiles. The amount and frequency of such "look-ahead" memory accessing may be varied in order to advantageously take advantage of physical memory characteristics, such as latency and size.
Whether a hierarchical, isolated data store such as the one described above is provided or not, the user profiles are accessed in order to calculate a similarity factor for each user with respect to all other users (step 104). A similarity
factor represents the degree of correlation between any two users with respect to a set of items. The calculation to be performed may be selected such that the more two users correlate, the closer the similarity factor is to zero. Specialized hardware
may be provided for calculating the similarity factors between users, although it is preferred to provide a general-purpose computer with appropriate programming to calculate the similarity factors.
Whenever a rating is received from a user or is inferred by the system from that user's behavior, the profile of that user may be updated as well as the profile of the item rated. Profile updates may be stored in a temporary memory location and
entered at a convenient time or profiles may be updated whenever a new rating is entered by or inferred for that user. Profiles can be updated by appending a new n-tuple of values to the set of already existing n-tuples in the profile or, if the new
rating is a change to an existing rating, overwriting the appropriate entry in the user profile. Updating a profile also requires re-computation of any profile entries that are based on other information in the profile.
Whenever a user's profile is updated with new rating-item n-tuple, new similarity factors between the user and other users of this system may be calculated. In other embodiments, similarity factors are periodically recalculated, or recalculated
in response to so me other stimulus, such as a change in a neighboring user's profile. The similarity factor for a user may be calculated by comparing that user's profile with the profile of every other user of the system. This is computationally
intensive, since the order of computation for calculating similarity factors in this manner is n.sup.2, where n is the number of users of the system. It is possible to reduce the computational load associated with re-calculating similarity factors in
embodiments that store item profiles by first retrieving the profiles of the newly-rated item and determining which other users have already rated that item. The similarity factors between the newly-rating user and the users that have already rated the
item are the only similarity factors updated.
Any number of methods can be used to calculate the similarity factors. In general, a method for calculating similarity factors between users should minimize the deviation between a predicted rating for an item and the rating a user would
actually have given the item.
It is also desirable to reduce error in cases involving "extreme" ratings. That is, a method which predicts fairly well for item ratings representing ambivalence towards an item but which does poorly for item ratings representing extreme
enjoyment or extreme disappointment with an item is not useful for recommending items to users.
Similarity factors between users refers to any q | | |
