UNIT-V

Recommendation systems
• Recommender systems are used in machine
learning to predict the ratings or preferences of
items for a given user.
• They are commonly used in e-commerce
applications to suggest items that a user may be
interested in.
• One common example of a recommender system
is Netflix. Netflix uses a recommender system to
suggest movies and TV shows that a user may want
to watch.
• There are a number of different types of
recommender systems. Some of them are
listed below:
• Content-based recommendation
• Collaborative filtering based recommendation
• Hybrid recommender system
• Content based recommender system:
• The most common type of recommender system is
the content-based recommender system. A
content-based recommender system is a type of
recommender system that relies on the similarity
between items to make recommendations. For
example, if you’re looking for a new movie to
watch, a content-based recommender system
might recommend movies that are similar to ones
you’ve watched in the past.
• Collaborative filtering recommender system:
• Another type of recommender system is
the collaborative filtering recommender system. A
collaborative filtering recommender system is a
type of machine learning algorithm that makes
predictions about what a user might want to buy or
watch based on the past behavior of other users.
The algorithm looks at the items that other users
with similar taste have purchased or rated highly,
and recommends those items to the new user.
• Hybrid recommender system
• A hybrid recommender system is a type of recommender
system that combines both content-based and collaborative
filtering approaches. The hybrid approach takes advantage
of both content-based and collaborative filtering by using
them to supplement each other. For example, a hybrid
recommender system might first identify a set of items that
are similar to the item the user is interested in, and then
use collaborative filtering to identify which of those items
the user is most likely to enjoy. This approach can provide
more accurate recommendations than either method used
alone.
 Dimensionality reduction
• Dimensionality reduction can be defined as it
is a way of converting higher dimensions data
into lesser dimensions set ensuring that it
provides similar information
• It is commonly used in the fields that deal with
high dimensional data such as speech
recognition, signal processing, bio-informatics
etc. it can be also used for data visualization ,
noise reduction and cluster analysis
• Purpose:
• Avoid curse of dimensionality: as you need more and
more attributes in data you need more and more
training samples to train algorithms
• If you increase dimensionality you need more storage ,
more computational time. So dimensionality reduction is
required to reduce amount of time and memory required
by the data mining algorithms.
• Allow data to be more easily visualized
• May help to eliminate irrelevant features or reduce noise
 Singular value decomposition(SVD):

• Singular value decomposition(SVD):

• the SVD of a matrix is a factorization of that
matrix into 3 matrices
• The SVD of mxn matrix A is given by the formula
• A=U Σ VT
• Where U:mxm matrix of the ortho-normal eigen
vectors of A. AT
• VT: nxn columns are eigen vectors of AT .A
• Σ: diagonal matrix of mxn
• Example: find singular value decomposition of
matrix A= 1 1
0 1
-1 1
STEP 1: for v compute AT .A.
AT .A= 1 0 -1 1 1 1+0+1 1+0-1
1 1 1 * 0 1 = 1+0-1 1+1+1
-1 1
• AT .A=V= 2 0
0 3
• STEP 2: find eigen values for AT .A=V so that e
can calculate VT.
characteristic equation = A- ƛ I = 0
2 0 1 0
0 3 -ƛ 0 1 = 0
• 2- ƛ 0
0 3- ƛ = 0

(2- ƛ) (3- ƛ)=0

ƛ=3 ƛ=2 (EIGEN VALUES)
Once we got the eigen values singular values we have to
obtain
1st singular value is root of 1st eigen value:√3
2nd singular value is root of 2nd eigen value :√2
so sigular values are= √3 ,√2
• Now calculate eigen vectors:
• For eigen value ƛ=3 for ƛ=2
• (A- ƛi)x=0
• v1= 0 v2= 1
1 0
V= 0 1 VT = 0 1
1 0 1 0
• Σ = √3 0
0 √2
0 0

STEP 3: FIND MATRIX “U”

U= 1/ √3 1/ √2 1/ √6
1/ √3 0 -2/√6
1/√3 1/√2 1/√6
PRINCIPLE COMPONENT ANALYSIS
• Principle component analysis is a statistical
process that converts the observations of
correlated features into a set of linearly
uncorrelated features with the help of orthogonal
transformation, these new transformed features
are called the principal components
• Examples: image processing, movie
recommendations system, optimizing the power
allocation in various communication channels.
• Steps in PCA:
• Step 1: Normalize the data
• First step is to normalize the data that we have
so that PCA works properly. This is done by
subtracting the respective means from the
numbers in the respective column.
• Step 2: Calculate the covariance matrix
• Step 3: compute eigen vector and
corresponding eigen values
• Step 4: sort the eigen vectors by decreasing
eigen values and choose k eigen vectors with
the largest eigen values to form dxk
dimensional matrix w
• Step 5: transform the samples onto the new
subspace
 example
• Given the following dataset; use PCA to
reduce the dimension from 2 to 1.
Feature Example 1 Example 2 Example 3 Example 4

X 4 8 13 7

Y 11 4 5 14
• Step 1: take the given data set
Feature Ex.1 Ex.2 Ex.3 Ex.4

X 4 8 13 7
Y 11 4 5 14

• here no. of features (n) = 2 (X , Y are the features)

• no of samples (N)= 4
• Step 2: computation of mean of variables:
• mean of x (x )= 4+8+13+7 = 8
4
• mean of y ( y ) = 11+4+5+14 = 8.5
4
Step 3: computation of co-variance matrix
n
cov(x,y)= 1 Σ (xi – x). (yi – y)
N-1 K=1
• COV(x,x)=1 [ (4-8)²+(8-8)²+(13-8)²+(7-8)²]
4-1
• cov(x,x)= 16+25+1 = 42 = 14
3 3
• Cov(x,y)= 1 [(4-8).(11-8.5) + (8-8)(4-8.5)+
4-1 (13-8)(5-8.5)+ (7-8)(14-8.5) ]
-11

= - 10-17.5-5.5 =
3
• cov(y,y)= 1 (11-8.5)²+(4-8.5)²+(5-.5)²

4-1 +(14-8.5)² 23

=6.25+20.25+12.25+30.25 =
3
so the covariance matrix is
S= cov(x,x) cov(x,y) = 14 -11
cov(y,x) cov(y,y) -11 23
• Step 4: calculate eigen values and eigen vector for
co-variance matrix
i) 14 - ƛ -11 = 0
-11 23 - ƛ
(14 – ƛ)(23 – ƛ )- (-11)(-11) =0
ƛ² - 37ƛ + 201 =0 => 1 √b²-4ac
ƛ=30.3849, 6.615 2a
ƛ1 =30.3849(1st principal component)
ƛ2 =6.615
• ii) calculate eigen vector of ƛ1
( S - ƛ 1 I ) U1 = 0
COVARIANCE MATRIX

14- ƛ1 -11 U1 = 0
-11 23- ƛ1 U2

(14- ƛ1 ) U1 – 11 U2 = 0
-11 U1 + (23- ƛ1 ) U2
(14- ƛ1 ) U1 – 11 U2 = 0
-11 U1 + (23- ƛ1 ) U2 = 0
U1 = U2 = t
11 14- ƛ1
when t=1
U1 = 11
U2 = 14- ƛ1
eigen vector for ƛ1= 11 = 11 = 11
14- ƛ1 14-30.3841 16.3849
• iii) normalize the eigen vector:
e1 = 11
-16.3849
√11² + (-16.3849)²

e1 = 0.5574
-0.8303
• Step 5: Derive new data set:
First Ex.1 Ex.2 Ex.3 Ex.4
principal
component p p12 p13 p14
11

Now calculate p11, p12 ,p13, p14

p11 = e1T 4-8  e1T x-x
11-8.5 y-y
• So p11 = (0.5574 -0.8303 ) -4
-2.5
p11 = -4.3052
similarly
p12 = 3.7361
p13 = 5.6928
p14 = -5.1238
• Finally the new data set of dimension 1 is:
PC 1 -4.3052 3.7361 5.6928 -5.1238
GIRVAN-NEWMAN ALGORITHM for detecting
communities in graphs or clustering of graphs
• Girvan- Newman technique is for the
detection and analysis of community structure
depends upon the iterative elimination of
edges with the highest number of the shortest
paths that pass through them.
• Repeat until no edge is left:
• STEP1: calculate edge betweenness for every
edge in the graph.
• Step 2: remove the edge with highest edge
betweenness .
• Step 3:calculte the edge betweenness for
remainng edges
• Step 4: connected components are
communities
• Example:

A B C

D E F
 1
A
3.165
1.835
1
B D 1

1.33 0.835
1+0.67=1.67
1.67/2=0.835
1 C
E 2

0.33 2/3=0.67

F 3
• Considering B: B 1

1.5 2 1.5

1 A 1 C 1
E

0.5 0.5
0.5 0.5

D F
2 2
• Cosidering C as node:
1
C
3.165 1.835
1
B F 1

1.33 0.835 0.835

1 A E
2

0.33 0.667

D
3
• Considering D as node:
1
D

1.834 3.164
1 1
A E
0.834 1.33
0.834

2 B F 1

0.667 0.33

C
3
• Considering E as node:
E 1

1.5 1.5 1.5

1 D 1 F 1
B

0.5 0.5 0.5 0.5

A C

2 2
• Considering F as node: 1
F

1.835 3.165

1 C E 1

0.835 0.835 1.33

2 B
D 1

0.667 0.33

A
3
EDGES
AB 3.165+1.5+1.33+0.385+0.5+0.667=8
AD 1.835+0.5+0.33+1.835+0.5+0.33=5.33
BC 3.165+1.5+1.33+0.835+0.5+0.667=8
BE 0.835+2+0.835+0.835+2+0.835=7.34
CF 1.835+0.5+0.33+1.835+0.5+0.33=5.33
DE 3.165+1.5+1.33+0.835+0.5+0.667=8
EF 3.165+1.5+1.33+0.835+0.5+0.667=8
•
4 4 C
A B

2.67 3.67 2.67

D E F
4 4

COMMUNTY 1 COMMUNITY-2 COMMUNITY-3

Direct discovery of communities in graph

• Clique percolation method (cpm):

• clique is the group of nodes in graph
such that all nodes in a cliques are connected
to each other
• k -> no of nodes in a clique
• For k=2 For K=3 for k=4
N1 N1
N1 N2

N2 N3
N2 N3 N4
• COMMUNITIES:
• Community is the group of cliques such that
all the cliques must have ‘K-1’ nodes in
common.
N1
• Eg: for k=3
• clique 1:{N1,N2,N3}
N3 N4
• clique 2:{N1,N2,N4}
• COMMUNITY:{clique1,clique2} N2
 EXAMPLE
• Use clique percolation method [CPM] and find
the communities? [for K=3 ]
7

3 6

1
2 5

8 4
• A => {1,2,3} community 1= {A ,B}
• B => {1,2,8} A B

• C => {2,4,6}
• D => {2,5,6} community 2={C,D,E,F}
• E => {5,6,4}
C D
• F => {2,4,5}
E F