Transcript Inferring User-Context from Frequent Sequential Pattern for

Inferring User-Context from Frequent
Sequential Pattern for Personalized
Multidimensional Recommender System
Using Weighted Sequential Pattern and
Graph-Based Approach
By
OYEKUNLE Victoria
Keywords
• User-Context
• Multidimensional Recommender
system(MDR)
• Weighted sequential pattern
• Graph-based method
Keywords
Dey et al. (2001) define context as
“any information that can be used to
characterize the situation of entities”
and elaborate it as “typically the
location, identity, and state of people,
groups, and computational and
physical objects.”
The weighted sequential pattern
mining aims to find more interesting
sequential patterns, considering the
different significance of each data
element in a sequence database
MDR extends traditional twodimensional recommender
systems to handle multiple
dimensions
Graph–based model is a kind of
graph partitioning problem in a
weighted linkage graph, where
vertices correspond to the entities
in the domain (e.g user, item,
context), and edges correspond to
the relationship between entities.
INTRODUCTION
SEARCH ENGINES
lack user specific
needs and interests
Not all needs can be
easily presented by
keywords
RECOMMENDER
SYSTEM.
Provide personalized
recommendation
INTRODUCTION
• Personalised recommendation
service aims to provide
products tailored to
individuals, satisfying their
needs in a given context based
on knowledge of their
preferences and behaviour
(Adomavicius and Tuzhilin ,
2005).
Information interested to user
A might not interest user B
even though they belong to
the same group
Introduction……….
Recommender system is an important approach to help
users deal with information overload (Onifade et. al., 2008,
Choung et. al., 2011)
6
Introduction……….
Recommender system (RS) approaches
(Adomavicius and Tuzhilin , 2005)
Collaborative filtering
Content-based Recommendation
Hybrid Recommendation
Overspecialization Problem
Homogeneity of
Context and Cold
start problems
7
Multidimensional recommender
system(MDR)
• MDR aim to more accurately identify user
preferences by exploiting additional
dimensions(e.g location, time, season, etc) to
user and item dimensions. Additional
dimension is refered to as the context of the
user.
• MDR systems need an expressive and
unambiguous way for users and systems to
represent and process various queries.
8
MDR Approaches
• Reduction-based approach use user’s prior
item preferences that match the current
context.(Adomavicius et. al., 2005)
• Disjunction-based approach(Lee at. al., 2010)
• Learning to rank approach.(Khang at. al.,
2011)
All these fix the recommendation form and do
not allow users to express their intentions.
Motivated scenario
This man is diabetic.
Should Coke be recommended?
10
Problem Statement
• Existing MDR either recommends items
according to the given user’s context by only
using the prior item preferences that match
the current context(e.g Reduction-Based
Approach ) or fix the recommendation form
and do not allow users to express their
intentions.(e.g disjunction-based approach ).
Aim
• The aim of this paper is to develop a
framework to infer contextual knowledge for
personalised multidimensional
recommendation using weighted sequential
pattern mining and graph based approach.
Objectives
• User’s context is derived from user-item
sequence using sequential pattern approach
thereby extending two dimensional RS to
multidimensional RS.
• A tripartite graph based algorithm is
developed for hierarchical aggregation
recommendation.
13
Research Questions
• How can we derive user’s context from frequent
itemsets whose occurences exceed a predefined
weighted minimum support threshold ?
• How can we obtain relationship among the
derived user context in order to improve relevant
recommendation?
• How can we obtain the similarities between
obtained user-item-context relationship and new
user’s profile.?
14
Research Methodology
The framework comprises of the following
phases;
• Data Preprocessing
• Sequential Pattern Algorithm
• The Graph-based Algorithm
• The Multidimensional Recommender Engine
15
Conceptual Framework
Sequential
pattern
preprocessing
Graph based
algorithm
Seq. Db
Tripartite graph
Matching
User’s
profile
Recommendation / feedback
U× I× C =
R
Preprocessing
• The tasks include; data cleaning, user
identification and session identification.
• Data preprocessing reduce the size of the
dataset and increase the quality of the data
that will be suitable for mining.
17
Weighted Sequence Database
• This is constructed by identifying each user
transaction for a particular time period and
the quantity of the items purchased per item
by the user.
SeqID
Sequence
S1
<a(1,t1),b(4,t1),><b(4,t2),(c(2,t2))><b
(3,t3),d(2,t3)>
S2
<a(3,t1)><b(1,t3)d(2,t2)>
S3
<a(2,t1),c(5,t1)>
Weighted Sequential Pattern
Algorithm
Input : A weighted sequence database Wij, and wminsupvalue(wminsup) .
Output : The complete set of weighted-sequential patterns β .
Method : Call W-PrefixSpan ( <>,0, Wij).
Subroutine : W-PrefixSpan (α ,l, Wij/ α)
Parameters: α : SR-sequential pattern; l : the length of α ; Wij / α : the α -projected
database, if α ≠ <> ; otherwise, the weighted sequence database Wij.
Method:
1. Scan Wij/ α once, find the set of SR- pattern s such that
a) ' s ' can be assembled to the last element of α to form a SR-sequential pattern; or
b)< s> can be appended to α to form a SR sequential pattern.
2. For each SR- s equence, append it to α to form a SR-sequential pattern α ' .
3). For each α ' , construct α ' -projected database W ij/α, and call PrefixSpan (α ',l +1,
Wij/α ).
(Suneetha K. & Rani M. U. (2012). Modified)
Weightage Measures
• The weightage measures assume are the quantity of
the items purchased.(q)
• The time(t) of the last sequence
• Let Wij = (p11, q11, t11), (p12, q12, t12),-----,(p1n,q1n,t1n) be a data sequence of weighted
transaction database, where pij is the product
purchased, qij is the quantity of the product purchased
and tij is the time the product is purchased.
• Wminsup = 1/N 𝑁𝑡
𝑖=1 𝐼𝑠 𝑖 ∗ 𝑡(𝑖)
𝑁𝑡
𝑖=1 𝑡(𝑖)
𝑀𝑡
• Is = 𝑁𝑡
𝑞𝑖/
𝑖=1
𝑖=1 𝑞𝑖
Inferring Context from Sequential
Pattern
• Dey et al. (2001) define context as any information that can be used
to characterize the situation of entities.
• Each weighted sequential pattern is a representative of a different
context where the user has selected an item with specific
characteristics captured in the sequence.
• Given a weighted sequential pattern Wij = (W11, W12 -----------, W1n)
• A weighted sequential pattern Wij consists of m sets contexts C1,
C2,---------, Cm
• Where Ci is the context of each item in Wij
• Contexts are non-empty: Ci ≠ {}, 1≤ 𝑖 ≤ 𝑚
• Context cover all of S: 𝑚
𝑖=1 𝐶𝑖 = S
• Contexts overlap : Ci ∩ Cj ≠ {} i.e Cj is subsequence of Ci
if j≠ i
Graph-based algorithm
•
•
•
•
•
•
•
Algorithm: Compute Similarity of two hyperedges
Input: hyperedges 𝑒1 = (a, b, c) and 𝑒2 = (p,q,r)
Output: similarity between 𝑒1 and 𝑒2
If a ≠ 𝑝 𝑎𝑛𝑑 𝑏 ≠ 𝑞 𝑎𝑛𝑑 𝑐 ≠ 𝑟 𝑡ℎ𝑒𝑛
sim← 0 /∗ ℎ𝑦𝑝𝑒𝑟𝑒𝑑𝑔𝑒𝑠 are not adjacent ∗/
else
/∗ 𝑙𝑒𝑡 𝑎 =
𝑝; 𝑒𝑖𝑡ℎ𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑜𝑡ℎ𝑒𝑟 𝑡𝑤𝑜 𝑝𝑎𝑖𝑟𝑠 𝑚𝑎𝑦 𝑏𝑒 𝑐𝑜𝑚𝑚𝑜𝑛 𝑎𝑠 𝑤𝑒𝑙𝑙 ∗/
• 𝑆1 ← 𝑁𝑥(b) ∪ 𝑁𝑥 (c); 𝑆2 ← 𝑁𝑦 (c) ; 𝑆3 ← 𝑁𝑧 (b);
• 𝑆1 ← 𝑁𝑥(q) ∪ 𝑁𝑥 (r); 𝑆2 ’ ← 𝑁𝑦 (r) ; 𝑆′3 ← 𝑁𝑧 (q);
• sim←
• end if
𝑆1 ∩ 𝑆′1 + 𝑆2 ∩𝑆′2 + 𝑆3 ∩ 𝑆′3
𝑆1 ∪ 𝑆′1 + 𝑆2 ∪ 𝑆′2 + 𝑆3 ∪ 𝑆′3
Conclusion
• A framework for inferring context from the
frequent sequential pattern for
multidimensional recommendation has been
proposed.
• We intend to complete the work by evaluating
using an e-commerce dataset.
References
•
•
•
•
•
•
•
J.Han , J.Pei, B.Mortazavi-Asl, Q. Chen, U.Dayal, And M.-C. Hsu. Freespan: Frequent pattern
projected sequential pattern mining. In Proceedings of the 6th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining. ACM, New York, 355–359, 2000.
R.Agrawal and R.Srikant. Mining sequential patterns. Proceedings of the Eleventh International
Conference on Data Engineering, 1995.
G. Adomavicius, R. Sankaranarayanan, S. Sen, and A. Tuzhilin. Incorporating Contextual Information
in Recommender Systems Using a Multidimensional Approach. ACM Trans. Information Systems,
vol. 23, no. 1, Jan. 2005
D. Lee, S. E. Park, M. Kahng, S. Lee, and S.-g. Lee. Exploiting contextual information from event logs
for personalized recommendation. In Computer and Information Science, Studies in Computational
Intelligence, pp. 121-139. Springer. 2010.
M. Kahng, S. Lee, and S.-g. Lee. Ranking in context-aware recommender systems. In WWW '11:
Proceedings of the 20th International Conference Companion on World Wide Web. 2011.
http://doi.acm.org/10.1145/1963192.1963226
Dey A. K., Abowd G. D., and Salber D.(2001). A conceptual framework and a toolkit for supporting
the rapid prototyping of context-aware applications. Human-Computer Interaction, 16(2):97–166,
2001.
Suneetha K. & Rani M. U. (2012). Web Page Recommendation Approach Using Weighted Sequential
Patterns and Markov Model Global Journal of Computer Science and Technology Volume 12 Issue 9
Version 1.0 April 2012