Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
  • G06F16/90—Details of database functions independent of the retrieved data types
  • G06F16/95—Retrieval from the web
  • G06F16/953—Querying, e.g. by the use of web search engines
  • G06F16/9535—Search customisation based on user profiles and personalisation
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
  • G06F16/90—Details of database functions independent of the retrieved data types
  • G06F16/95—Retrieval from the web
  • G06F16/954—Navigation, e.g. using categorised browsing

Definitions

• the present invention generally relates, in a first aspect, to a method to generate personalized selection of items for a given user in an online computing system, and more particularly to a method that comprises mining out associations between items extracted from stored anonymous session logs for providing relevant items prediction and recommendation for said user.
• a second aspect of the invention relates to a system arranged to implement the method of the first aspect.
• the present invention is presenting in which a high percentage of the users interacting with the system are navigating anonymously into its contents, and similarity between items extracted from user sessions is the only way to create recommendations, given that users have, in general, no persistent profile data.
• Association Rules are rules of the kind "70% of the customers who buy wine and cheese also buy grapes" [5].
• the first step is to characterize the items assigning literals (usually a numerical id) to each item in a database.
• a transaction is a set of items from a database. The items somehow occur together because they appear closely related on an action that the user performed against the system.
• a transaction can be the set of items bought when shopping in a market, the set of actions executing a plan or the set of web pages seen during a browsing session. This is the transaction type the present invention is interested because it's assumed that when a user is browsing a site is because he has a coherent intention, being it be informed, evaluate alternatives before buying items or just enjoy a set of shared items.
• association rule a rule that is written as X -> Y, where X is a set of items called the antecedent and Y is another set of items called the consequent.
• the algorithms that learn association rules iterate over the set of all the available transactions, looking for deviation in the frequency of appearance of sets of items. For instance, if it is known that customers pick product A in the 10% of purchases and product B the 4% it should be expected that both products appeared on the 0.4% of the baskets if they were truly independent. But if instead, it is seen that they tend to appear together in the 1 % of the baskets it could be inferred that there is some correlation between those items and a meaningful rule can be extracted. In order to mine interesting rules, several concepts related to the Association Rules must be introduced:
• the confidence of a rule is called to the number of transactions in the database including both the antecedent and the consequent of the rule divided by the number of transactions including the antecedent. This measure represents how likely is that given the antecedent we find the consequent in the itemset.
• This algorithm works in two independent phases. In the first phase it enumerates all the item sets in the transaction database that exceed this threshold. In the second phase, the confidence threshold is used for generating all the rules that exceed this threshold. This two phase approach is common in most algorithms for mining association rules. The variations are tailored to better generation of the frequent itemsets based on prior knowledge of the transaction database.
• association rules provide a convenient framework for recommending items. They are somehow less vulnerable to data sparsity since association rule mining does not manipulate directly the (sparse) user- item matrix. Based on anonymous usage data the system is able to extract related items in a form very suitable for recommendations, if the user has seen/purchased/used some items (the antecedent) surely she would like these other items (the consequent). Once the rules have been extracted they form a knowledge base ready for exploitation by recommender systems so, contrary to standard collaborative filtering, they are less reliant on keeping a stable user profile.
• HAI Human Computer Interaction
• users can use the hierarchical directory of a web site or the search box to navigate to the piece of information they are looking for. Perhaps a user searched and the results were not relevant and she turned to the hierarchy because she remembered where the items where in the last visit.
• ordering of the items/events generated is of great relevance.
• the Association Rules paradigm does not take into account any kind of ordering (be it time ordering or importance ordering) when generating the rules but this information is very important for the online recommendations.
• An aim of the invention is to provide a user items recommendation method where anonymous usage is kept while tracking user actions.
• the present invention provides a method to generate personalized selection of items for a given user in an online system, wherein said user is connected to a services provider server by means of an application running in a terminal of said user.
• the method comprising as per common practice in the field: a) gathering data information from stored user session logs over a period of time, wherein said sessions refer to communications between said user terminal and said services provider server; and
• the method as per the present invention further comprises following steps: c) creating a specialised search structure for fast lookup of said frequent items of said step b);
• the stored user session logs are captured in said step a) anonymously therefore permitting that anonymous browsing can be successfully exploited for recommendations.
• the method further comprises a step f) for the use of a data mining algorithm for the association rule extraction of the frequent items in order to infer similarity between items.
• the method of the present invention also provides an specialised search structured based on a tree structure, the creation of said tree structure is done in two steps.
• the first step comprises the following steps: g) creating a composed list with an arbritary head-member and a sorted tail;
• the second step of the creation of the tree structure further comprises:
• the tree structure is designed to be used in combination with a running window that keep the session items in reverse temporal order, most recent first, and an accumulated list of items of potential interest for the user.
• the combination of the running window and the tree structure allows the present invention to cover the instantaneous interest of the user and at the same time keeping user past navigation times.
• a second aspect of the present invention concerns to a system to generate personalized selection of items for a given user, comprising an off-line processor implementing any of the method claims from 1 to 19.
• the system of the second aspect of the present invention further comprises an online processor implementing any of the method claims from 1 to 19.
• Figure 1 shows the architecture of the global system of the present invention.
• Figure 2 shows the flown diagram execution process that follows the off-line processor, according to an embodiment of the present invention.
• Figure 3 shows the procedure structure of the rule tree, according to an example embodiment of the present invention, wherein it can be observed that the tree creation is done in two passes.
• Figure 4 shows the process generation of the results in the on-line processor, according to an example embodiment of the present invention.
• Figure 5 shows the schematic diagram of the steps for generating recommendations, according to an example embodiment of the present invention.
• Figure 6 shows an example embodiment of the recommender system, wherein the server provides a service that delivers items of interest to the user.
• the present invention consists on a method and a system for mining out associations between items extracted from stored anonymous session logs, which are then used for online selection of candidate items matching user actions in the current session.
• An important issue is that no explicit user profile is built for users of the service, nor it is needed as in CF, so that anonymous browsing can be successfully exploited for recommendations.
• the present invention contains two main subsystems:
• the offline processor uses standard data mining tools, augmented with the building of a specialised search structure, on a dataset collected from past sessions.
• the online processor uses the above mentioned search structure to provide a prediction for items of potential interest for the user, given her current session activity (considered as a timed series of items). This can be used for item recommendation, among other purposes.
• the architecture of the global system of the global invention is showed in Figure 1.
• the Web service is the end-user service to which the invention provides added functionality. In the invention itself it can be distinguish the mentioned following elements:
• An off-line processor for mining out association rules and preparing the search structures
• An on-line processor producing relevant items according to real-time navigation.
• a data collection phase is carried out, in which a dataset is built by gathering information from the Web service about user actions as they navigate the site and interact with it. This is done across a period of time to build the initial dataset, and later on updated at regular intervals to keep the information current with recent user behaviour.
• User data is captured anonymously, and users are not tracked across sessions.
• the first step in the offline subsystem will execute a frequent itemset algorithm (an algorithm that finds out items that go frequently together) over a previously collected corpus of sets of items.
• Each set contains items that are linked together by some predefined criteria. Examples of these criteria are: a dataset of user sessions, in which each set contains the temporal succession of items visited by the user, or the set of items purchased together (market basket analysis), found out to belong to the user (inventory) or chained together by some user action (e.g. the set of songs listened together in a session of a music playing application).
• association rules in which a consequent item is said to be a probable addition to the set of itemsets in the antecedent, with a certain weight.
• rules with a single consequent that is, each association proposes a single additional item.
• the well-known Apriori algorithm is one example of a standard tool to create those association rules.
• Those thresholds are chosen after analysis of the whole itemset and rule production statistics: extraction (over the whole dataset or, if efficiency is important, over a significant subsample) is done over a grid of values of support and confidence, and the number of rules produced and the overall information gain of the rules for each combination is used to decide on the final values. In practice, this can be as a 2-pass effort: the 1 st pass determines the optimal support and confidence thresholds, and in the 2nd pass the final rules are extracted with those fixed support and confidence thresholds
• An additional measure of rule weight or significance is computed and stored as a weight of the rule.
• the type of measure used depends on the purpose of the system, and a number of them have been defined and evaluated [13]. For instance, to be used as a recommendation engine, the information gain of the consequent can be used (defined as the gain in entropy obtained by adding the consequent to the set, when compared with the entropy of the antecedent itemset). This can reflect the "interestingness" of the consequent.
• the invention creates a tree structure for fast lookup of frequent itemsets. For that it is assumed that it is possible to define a lexicographic ordering over the items. The ordering criteria is not important as long as it is consistent (i.e. it sorts two items always the same way); it could be e.g. alphabetical sorting of the canonicalized web URL of the item. For each rule the invention will sort items according to this lexicographic order.
• a single ordered tree will contain all possible frequent itemsets.
• the tree is divided into two parts: the first level is a flat list of each distinct item appearing in the antecedents of the extracted association rules; the second part (below each item in that first level) contains a set of subtrees. See Figure 3 for a representation.
• the procedure for tree creation is done in two passes, as follows: • In the first pass, this procedure is iterated for each rule: take one arbitrary item of the rule antecedent, and sort the rest of the items in the antecedent, creating a composed list with a head-member and a sorted tail. Then traverse the tree following that list (creating tree nodes at necessary). At the final leaf, add the rule data: rule consequent, rule weight (interestingness measure) and antecedent rule size.
• the process is repeated as many times as items in the antecedent, taking in turn as head-member each different item in the antecedent.
• a single rule whose antecedent is of size N is therefore encoded N times in the tree.
• the tree becomes a fast lookup table for association rules. Any rule candidate can be quickly found by taking out the head item, sorting the rest, and traversing the tree; the result (if a match is found) contains all the elements in the powerset of the candidate that are association rules.
• the online phase begins when a user enters the system. It is assumed that the user can be anonymously tracked throughout the session, i.e. its navigation actions can be followed (without any need to actually identify her). Those user actions get passed to the session handler, and each one activates a search in the itemset tree.
• the definition of an action is domain dependent and must be decided by the domain expert. The idea is to gather the pieces of information that are indicators of the true intentions or preferences from the user. For instance, getting the time spent watching a movie, getting the links a user is browsing in a web site or the tracks the user is listening in his iPod.
• the invention For each tracked user the invention keeps an accumulated list of items of potential interest for her, each one with an associated weight. It is updated with each new user action.
• the invention keeps also for each user a running window of K session items in reverse temporal order (most recent first), K being chosen as a compromise to balance comprehensiveness in session log and importance of recent activities.
• a K+1 candidate itemset is formed by sorting the existing K window in lexicographical order and adding the new item as the head item.
• the K+1 itemset are looked for in the tree.
• the head item selects the subtree to search, and then the tree is traversed by using the rest of the itemset. As this rest is sorted, lookup is fast.
• the corresponding item chosen by the user is added to the accumulated list of applicable items, using their final weight to position them in the list. If a consequent appears more than once, its weights are added.
• the accumulated item list such obtained is kept for the next action.
• the process is: i.
• the current list i.e. the one obtained with all the itemsets except the one coming in now
• the dampening factor could be a function of the time elapsed since the previous event, increasing monotonically with time, but with a very gentle slope and with a saturation point, to avoid too drastic forget procedures (since it is applied at each iteration, so its effects are multiplicative).
• New items obtained by the enlarged itemset that contains the new action are added to the list in an additive procedure, i.e. if an item does not exist it is inserted; if it already exists in the list, the new weight is added to the existing one (which in effect makes the addition reinforce the relevance of an item that was in the process of being forgotten).
• This accumulated item list is the used for its mission in the present invention: recommendations for the user, user action prediction for performance improvements, etc.
• an additional final step can be used to prune the list from items already visited by the user in this session (or at least recently visited), so that only new items are shown to her.
• This present invention can be instantiated in an embodiment supplying a method for recommenders systems.
• Recommender systems although they provide an improved user experience, need not be central to the service where they are deployed.
• this embodiment tries to be as unobtrusive as possible with a plug-and-play philosophy and a mechanism for not interfering with the main application (which avoids adding a point of failure to the main application flow).
• the server provides a service that delivers items of interest to the user.
• One representative instance is that of news services (e.g. an online newspaper), which provides users with the capability to navigate across a sizable set of news items (perhaps in the shape of web pages).
• the present invention communicates with the application where it is embedded by exposing a REST interface. Following the REST architecture patterns, the REST interface exposes the algorithm as a resource that is queried for recommendations. It also exposes the collection of user events as a resource where the host system sends any relevant event. In order to create such events and queries, the host must choose which method for notification it will employ. Common configurations are: embedding a Javascript snippet at the client side or modifying the server for routing new events to our system.
• the advantage is that the server code need not be modified in any way, but as a drawback we introduce additional requests on the client side that could introduce delays when rendering the Ul to the user.
• Another option is to embed those calls in the logic of the server so the user sees both the host service and the recommender engine as a unique endpoint.
• navigation events are received in the present invention REST interface they are routed to a messaging system.
• the messaging system broadcasts these messages to the agents that are listening to this channel, which in the system includes the on-line recommender agent and the off-line processor.
• the off-line processor is an independent process that receives events and serializes them in correct order and grouped by session to the hard disk. It uses also a Scheduler that fires from time to time the Apriori algorithm that generates the association rules.
• the Apriori algorithm can be implemented very efficiently to read the serialized sessions using a snapshot stored in the hard disk (therefore avoiding disruption from incoming events) and output the association rules..
• the off-line processing packs this information and the created specialized rule tree and routes it through the messaging system to the on-line recommender agent through a point-to-point messaging channel. It is responsibility of this algorithm to purge older sessions in order to maintain computations of the Apriori algorithm manageable.
• the on-line recommender agent is connected to the messaging system through two channels: one that is broadcasting the user navigation events and another one that listens for possible updates to the mined association rules. It embodies a session management component that is keeping track of the current users' sessions. This component is the one that returns the recommended items by combining the special tree generated during the offline process and the visited item list for a given user.
• a music recommender service might work by having specialized harversters in clients' application or devices, which collect information about users' listening sessions and periodically send them, as anonymized streams of listened music pieces, to a recollection point in the off-line process. This collects the sessions sent by the clients and from time to time runs the generation of the recommendation rules, starting with the Apriori algorithm, and sends the result to the on-line process.
• the procedure enables that all items selected by the user in the current session contribute to the list of candidates, and all possible combinations of items to be formed from session items are explored to find out (so that not only exact sessions are allowed, but also sessions with additional, non-relevant items).
• the system balances the whole user history in the session with the relevance of recent interests (items recently chosen) thanks to the use of the dampening function.
• navigation noise When talking about web usage mining, it can be defined navigation noise as the act of filling the user session history with events not connected to the main underlying objectives in the user's mindset as it traverses the website. Given the nature of web structure and its deep-linked graph, it is natural for people to have one aim (or a few aims) in mind but get distracted by side links; when trying to employ usage data for recommendation (and somehow less for link prediction) this navigation noise stands in the way of prediction algorithms, since is typically too random to be useful (unless the user is actually in 'random surfer mode'). It is therefore quite important to devise techniques robust against navigation noise, which can render users' surface behaviour similar to a random walk, and hide the underlying user intention.
• Sequential mining can be more precise to extract usage patterns, but given that typical navigation noise and the fact that the same web graph can usually be traversed in different but equivalent (from the point of view of user intentions) patterns, they tend to lead to insufficient (and noisy) output.
• basic plain frequent itemset mining (considering the session as an unordered set) is able to extract more results, but it loses the temporal meaning which is significant.
• the window size for rule matching is a parameter difficult to adjust (too small misses valid item relationships in the session, too big flattens the timeline and precludes efficient use of temporal information).
• the present invention approach can achieve the best of all worlds:
• the use of the present invention additive model implies that the present invention sequential matching is not of the same kind than the standard procedure for sequential mining.
• full event sequences from the timeline must be matched with the extracted sequential patterns.
• the even sequences need not be necessarily contiguous (except when defined otherwise), which helps to overcome navigation noise somehow, but it still requires full sequence matching.
• the present invention case could be better defined as a reinforcement model, in which unordered subsets of events are matched and produced results that add up as time progresses.
• the relative significance of session size is taken into account by appropriate weighting additional to the intrinsic of the rule.
• the combination of running window and accumulated tree is therefore a significant improvement over both regular association mining and sequential mining.
• the present invention uses the K+1 most recent events for item generation, so that covers the instantaneous interest of the user, (corresponding to short-term memory) but it accumulates rules found in past navigation times, so that user history is not forgotten (hence long-term memory contributes to the base pattern). In short-term memory all events could be considered to be active at the same time, and therefore it doesn't consider relative order explicitly when matching rules within the window.
• the present invention tree is specially designed to be used with a running window and an accumulated list: in a running window, only one element changes at a time, and therefore the present invention structure the tree to be able to find instantly all matches containing this new element (the head item), thanks to its first level indexed by head item instead of lexicographical order.
• the greater amount of memory required by having to encode each rule several times in the tree can be alleviated by using indirection in the tree nodes, so that the result list for each node is only stored once, and all equivalent tree paths point to that copy.
• the reinforcement model is also a natural way to deal with repeated events: it is not uncommon in web navigation events to find repeated items in a time series. This corresponds to the user going back in history, perhaps to end up a diversion or due to recovering interest in a previously seen item. These repetitions are readily used by the system to reinforce relationships that can be spun from them.
• the invention search in the (support, confidence) space for the best combination to prune the tree, and the possibility to use multiple minimum supports, allows a better selection of applicable rules.
• the use of an additional rule interestingness measure permits a better weight for the result items.
• the present invention choice of information gain is especially appropriate in this case, in which the additive model will combine all information gains received from all rule matchings' for the same item.
• This additive model applied to consequents enables an effective way of coping with short-sized frequent itemsets while taking into account also time order and the evolution of user interests along the session.

Landscapes

• Engineering & Computer Science (AREA)
• Databases & Information Systems (AREA)
• Theoretical Computer Science (AREA)
• Data Mining & Analysis (AREA)
• Physics & Mathematics (AREA)
• General Engineering & Computer Science (AREA)
• General Physics & Mathematics (AREA)
• Radar, Positioning & Navigation (AREA)
• Remote Sensing (AREA)
• Computer And Data Communications (AREA)
• Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Applications Claiming Priority (2)

Publications (2)

Family

ID=48013941

Family Applications (1)

Country Status (1)

Cited By (7)

Families Citing this family (1)

• 2013
  • 2013-03-15 WO PCT/EP2013/055345 patent/WO2013143878A2/fr not_active Ceased

Non-Patent Citations (2)

Also Published As

Similar Documents

Legal Events