Transcript PPT - the Department of Computer Science

Practical Graph Mining with R
Graph-based Proximity Measures
Nagiza F. Samatova
William Hendrix
John Jenkins
Kanchana Padmanabhan
Arpan Chakraborty
Department of Computer Science
North Carolina State University
Outline
• Defining Proximity Measures
• Neumann Kernels
• Shared Nearest Neighbor
2
Similarity and Dissimilarity
• Similarity
–
–
–
–
Numerical measure of how alike two data objects are.
Is higher when objects are more alike.
Often falls in the range [0,1]:
Examples: Cosine, Jaccard, Tanimoto,
• Dissimilarity
–
–
–
–
Numerical measure of how different two data objects are
Lower when objects are more alike
Minimum dissimilarity is often 0
Upper limit varies
• Proximity refers to a similarity or dissimilarity
Src: “Introduction to Data Mining” by Vipin Kumar et al
3
Distance Metric
•
Distance d (p, q) between two points p and q is a
dissimilarity measure if it satisfies:
1. Positive definiteness:
d (p, q)  0 for all p and q and
d (p, q) = 0 only if p = q.
2. Symmetry: d (p, q) = d (q, p) for all p and q.
3. Triangle Inequality:
d (p, r)  d (p, q) + d (q, r) for all points p, q, and r.
•
Examples:
–
–
–
Euclidean distance
Minkowski distance
Mahalanobis distance
Src: “Introduction to Data Mining” by Vipin Kumar et al
4
Is this a distance metric?
p  ( p1, p2 ,...., pd ) 
d ( p, q)  max( p j , q j )
d
and q  (q1 , q2 ,...., qd ) 
d
Not: Positive definite
1 j  d
Not: Symmetric
d ( p, q)  max( p j  q j )
1 j  d
d ( p, q ) 
Not: Triangle Inequality
d
2
(
p

q
)
 j j
j 1
d ( p, q)  min | p j  q j |
1 j  d
Distance Metric
5
Distance: Euclidean, Minkowski, Mahalanobis
p  ( p1, p2 ,...., pd ) 
d ( p, q ) 
(p
j 1
j
and q  (q1 , q2 ,...., qd ) 
Minkowski
Euclidean
d
d
 qj )
2
 d
r 
dr ( p, q)    | p j  q j | 
 j 1

d
Mahalanobis
1
r
d ( p, q)  ( p  q)1 ( p  q)T
r  1:
City block distance
Manhattan distance
L1 -norm
r  2:
Euclidean, L2 -norm
6
Euclidean Distance
d ( p, q ) 
d
2
(
p

q
)
 j j
j 1
Standardization is necessary, if scales differ.
p  ( p1, p2 ,...., pd ) 
Mean of attributes
1 d
p   pk 
d k 1
d
Ex:
p  (age, salary)
Standard deviation of attributes
1 d
2
sp 
(
p

p
)


k
d  1 k 1
Standardized/Normalized Vector
pnew
pd  p
p1  p p2  p
p p

(
,
,...,
)
sp
sp
sp
sp
d
pnew  0
s pnew  1
7
Distance Matrix
d ( p, q ) 
d
2
(
p

q
)
 j j
j 1
• P = as.matrix (read.table(file=“points.dat”));
• D = dist (P[, 2;3], method = "euclidean");
• L1 = dist (P[, 2;3], method = “minkowski", p=1);
• help (dist)
3
Input Data Table: P
point
p1
p2
p3
p4
p1
2
p3
p4
1
p2
0
0
1
2
3
4
5
6
x
0
2
3
5
y
2
0
1
1
File name: points.dat
Output Distance Matrix: D
p1
p1
p2
p3
p4
0
2.828
3.162
5.099
Src: “Introduction to Data Mining” by Vipin Kumar et al
p2
2.828
0
1.414
3.162
p3
3.162
1.414
0
2
p4
5.099
3.162
2
0
8
Covariance of Two Vectors, cov(p,q)
p  ( p1, p2 ,...., pd ) 
d
and q  (q1 , q2 ,...., qd ) 
One definition:
1 d
cov( p, q)  s pq 
( pk  p )(qk  q ) 

d  1 k 1
d
Mean of attributes
1 d
p   pk 
d k 1
Or a better definition:
cov( p, q)  E[( p  E( p))(q  E(q))T ] 
E is the Expected values of a random variable.
9
Covariance, or Dispersion Matrix,
N points in d-dimensional space:
P1  ( p11 , p12 ,...., p1d ) 

d
.....
PN  ( pN 1 , pN 2 ,...., pNd ) 
d
The covariance, or dispersion matrix:
 cov( P1 , P1 ) cov( P1 , P2 )
 cov( P , P ) cov( P , P )
2
1
2
2
( P1 , P2 ,..., PN )  

...
...

cov( PN , P1 ) cov( PN , P2 )
cov( P1 , PN ) 
... cov( P2 , PN ) 

...
...

... cov( PN , PN ) 
...
The inverse, Σ-1, is concentration matrix or precision matrix
10
Common Properties of a Similarity
• Similarities, also have some well known
properties.
– s(p, q) = 1 (or maximum similarity) only if p = q.
– s(p, q) = s(q, p) for all p and q. (Symmetry)
where s(p, q) is the similarity between points
(data objects), p and q.
Src: “Introduction to Data Mining” by Vipin Kumar et al
11
Similarity Between Binary Vectors
• Suppose p and q have only binary attributes
• Compute similarities using the following quantities
– M01 = the number of attributes where p was 0 and q was 1
– M10 = the number of attributes where p was 1 and q was 0
– M00 = the number of attributes where p was 0 and q was 0
– M11 = the number of attributes where p was 1 and q was 1
• Simple Matching and Jaccard Coefficients:
SMC = number of matches / number of attributes
= (M11 + M00) / (M01 + M10 + M11 + M00)
J = number of 11 matches / number of not-both-zero
attributes values
= (M11) / (M01 + M10 + M11)
Src: “Introduction to Data Mining” by Vipin Kumar et al
12
SMC versus Jaccard: Example
p= 1000000000
q= 0000001001
M01 = 2 (the number of attributes where p was 0 and q was 1)
M10 = 1 (the number of attributes where p was 1 and q was 0)
M00 = 7 (the number of attributes where p was 0 and q was 0)
M11 = 0 (the number of attributes where p was 1 and q was 1)
SMC = (M11 + M00)/(M01 + M10 + M11 + M00)
= (0+7) / (2+1+0+7) = 0.7
J = (M11) / (M01 + M10 + M11) = 0 / (2 + 1 + 0) = 0
13
Cosine Similarity
• If d1 and d2 are two document vectors, then
cos( d1, d2 ) = (d1  d2) / ||d1|| ||d2|| , where:
 indicates vector dot product and
|| d || is the length of vector d.
• Example:
d1 = 3 2 0 5 0 0 0 2 0 0
d2 = 1 0 0 0 0 0 0 1 0 2
cos( d1, d2 ) = .3150
d1  d2= 3*1 + 2*0 + 0*0 + 5*0 + 0*0 + 0*0 + 0*0 + 2*1 + 0*0 + 0*2 = 5
||d1|| = (3*3+2*2+0*0+5*5+0*0+0*0+0*0+2*2+0*0+0*0)0.5 = (42) 0.5 = 6.481
||d2|| = (1*1+0*0+0*0+0*0+0*0+0*0+0*0+1*1+0*0+2*2) 0.5 = (6) 0.5 = 2.245
Src: “Introduction to Data Mining” by Vipin Kumar et al
14
Extended Jaccard Coefficient (Tanimoto)
• Variation of Jaccard for continuous or count
attributes
– Reduces to Jaccard for binary attributes
Src: “Introduction to Data Mining” by Vipin Kumar et al
15
Correlation (Pearson Correlation)
• Correlation measures the linear relationship
between objects
• To compute correlation, we standardize data
objects, p and q, and then take their dot product
pk  ( pk  mean( p)) / std ( p)
qk  (qk  mean(q)) / std (q)
correlation( p, q)  p  q
Src: “Introduction to Data Mining” by Vipin Kumar et al
16
Visually Evaluating Correlation
Scatter plots showing the
similarity from –1 to 1.
Src: “Introduction to Data Mining” by Vipin Kumar et al
17
General Approach for Combining Similarities
•
Sometimes attributes are of many different
types, but an overall similarity is needed.
Src: “Introduction to Data Mining” by Vipin Kumar et al
18
Using Weights to Combine Similarities
• May not want to treat all attributes the same.
– Use weights wk which are between 0 and 1 and sum to 1.
Src: “Introduction to Data Mining” by Vipin Kumar et al
19
Graph-Based Proximity Measures
In order to apply graphbased data mining
techniques, such as
classification and clustering,
it is necessary to define
proximity measures between
data represented in graph
form.
Within-graph
proximity measures:
Hyperlink-Induced
Topic Search (HITS)
The Neumann
Kernel
Shared Nearest
Neighbor (SNN)
√
Outline
• Defining Proximity Measures
• Neumann Kernels
• Shared Nearest Neighbor
21
Neumann Kernels: Agenda
Neumann
Kernel
Introduction
Co-citation and
Bibliographic
Coupling
Document and
Term
Correlation
Diffusion/Decay
factors
Relationship to
HITS
Strengths and
Weaknesses
Neumann Kernels (NK)
 Generalization of HITS
 Input: Undirected or Directed
Graph
 Output: Within Graph
Proximity Measure

Importance

Relatedness
von Neumann
NK: Citation graph
n1
n2
n3
n4
n5
n6
n7
n8
• Input: Graph
– n1…n8 vertices (articles)
– Graph is directed
– Edges indicate a citation
• Citation Matrix C can be formed
– If an edge between two vertices exists then the
matrix cell = 1 else = 0
NK: Co-citation graph
n1
n5
n2
n6
n3
n4
n7
n8
• Co-citation graph: A graph which has two nodes
connected if they appear simultaneously in the reference
list of a third node in citation graph.
• In above graph n1 and n2 are connected because
both are referenced by same node n5 in citation
graph
• CC=CTC
NK: Bibliographic Coupling Graph
n1
n5
n2
n6
n3
n4
n7
n8
 Bibliographic coupling graph: A graph which has two nodes
connected if they share one or more bibliographic references.
 In above graph n5 and n6 are connected because both are
referencing same node n2 in citation graph
 CC=C CT
NK: Document and Term Correlation
Term-document matrix: A matrix in which the rows represent
terms, columns represent documents, and entries represent a function
of their relationship
(e.g. frequency of the given term in the document).
Example:
D1: “I like this book”
D2: “We wrote this book”
Term-Document Matrix X
NK: Document and Term Correlation (2)
Document correlation matrix: A matrix in which the rows and
the columns represent documents, and entries represent the semantic
similarity between two documents.
Example:
D1: “I like this book”
D2: “We wrote this book”
Document Correlation matrix K = (XTX)
NK: Document and Term Correlation (3)
Term Correlation Matrix:- A matrix in which the rows and the columns represent
terms, and entries represent the semantic similarity between two terms.
Example:
D1: “I like this book”
D2: “We wrote this book”
Term Correlation Matrix T = (XXT)
Neumann Kernel Block Diagram
.
Input:
Graph
Output: Two matrices of dimensions n x n called K γ and Tγ
Diffusion/Decay Factor: A tunable parameter that controls the
balance between relatedness and importance
NK: Diffusion Factor - Equation & Effect
Neumann Kernel defines two matrices incorporating a
diffusion factor:
Simplifies with our
definitions of K and T
When
When
NK: Diffusion Factor - Terminology
Indegree = The indegree, δ-(v), of vertex v
is the number of edges leading to vertex v.
δ- (B)=1
Outdegree = The outdegree, δ+(v), of
vertex v is the number of edges leading
away from vertex v.
δ+(A)=3
Maximal indegree= The maximal
indegree, Δ-, of the graph is the maximum
of all indegree counts of all vertices of
graph.
Δ-(G)= 2
Maximal outdegree= The maximal
outdegree, Δ+, of the graph is the maximum
of all outdegree counts of all vertices of
graph.
Δ+(G)= 3
A
B
C
D
NK: Diffusion Factor - Algorithm
NK: Choice of Diffusion Factor and its effects
on the Neumann Algorithm
• Neumann Kernel outputs relatedness between
documents and between terms when g = γ
• Similarly when γ is larger, then the Kernel
output matches with HITS
Comparing NK, HITS, and
Co-citation Bibliographic Coupling
n1
n2
n3
n4
n5
n6
n7
n8
HITS. authority ranking for above graph
n3 > n 4 > n 2 > n 1 > n 5 = n 6 = n 7 = n 8
Calculation of Neumann Kenel for gamma=0.207 which is
maximum possible value of gamma for this case gives following
ranking
n3 > n 4 > n 2 > n 1 > n 5 = n 6 = n 7 = n 8
For higher values of gamma Neumann Kernel converges to HITS
Strengths and Weaknesses
Strengths
Weaknesses
Generalization
of HITS
Topic Drift
Merges
relatedness
and
importance
No penalty for
loops in
adjacency
matrix
Useful in many
graph
applications
Outline
• Defining Proximity Measures
• Neumann Kernels
• Shared Nearest Neighbor
37
Shared Nearest Neighbor (SNN)
• An indirect approach
to similarity
• Uses a dynamic
method of a kNearest Neighbor
graph to determine
the similarity
between the nodes
• If two vertices have
more than k
neighbors in common
then they can be
considered similar to
one another even if a
direct link does not
exist
SNN - Agenda
Understanding Proximity
Proximity Graphs
Shared Nearest Neighbor Graph
SNN Algorithm
Time Complexity
R Code Example
Outlier/Anomally Detection
Strengths
Weaknesses
SNN – Understanding Proximity
What makes a node a
neighbor to another
node is based off of the
definition of proximity
Definition: the
closeness between
a set of objects
Proximity can
measure the extent
to which the two
nodes belong to
the same cluster.
Proximity is a
subtle notion
whose definition
can depend on a
specific application
SNN - Proximity Graphs
• A graph obtained by connecting two points,
in a set of points, by an edge if the two
points, in some sense, are close to each
other
SNN – Proximity Graphs
(continued)
1
2
3
4
5
1
6
5
LINEAR
Various Types of
Proximity Graphs
2
4
7
6
RADIAL
2
1
5
3
CYCLIC
3
4
SNN – Proximity Graphs
(continued)
GABRIEL GRAPH
Other types of
proximity
graphs.
NEAREST NEIGHBOR
GRAPH
(Voronoi diagram)
MINIMUM SPANNING
TREE
RELATIVE NEIGHBOR
GRAPH
SNN – Proximity Graphs (continued)
Represents neighbor relationships
between objects
Can estimate the likelihood that a
link will exist in the future, or is
missing in the data for some reason
Using a proximity graph increases
the scale range over which good
segmentations are possible
Can be formulated with respect to
many metrics
SNN – Kth Nearest Neighbor (k-NN)
Graph
Forms the basis for the
Shared Nearest
Neighbor (SNN)
within-graph proximity
measure
Has applications in
cluster analysis and
outlier detection
SNN – Shared Nearest Neighbor Graph
• An SNN graph is a
special type of KNN
graph.
• If an edge exists between
two vertices, then they
both belong to each
other’s k-neighborhood
In the figure to the left, each of the two
black vertices, i and j, have eight nearest
neighbors, including each other. Four of
those nearest neighbors are shared which
are shown in red. Thus, the two black
vertices are similar when parameter k=4
for SNN graph.
SNN – The Algorithm
Input: G: an undirected graph
Input: k: a natural number (number of shared neighbors)
for i = 1 to N(G) do
for j = i+1 to N(G) do
if j < = N(G) then
counter = 0
end if
for m = 1 to N(G) do
if vertex i and vertex j both have an edge with vertex m
then
counter ++
end if
end for
if counter k then
Connect an edge between vertex i and vertex j in SNN
graph.
end if
end for
end for
return SNN graph
SNN – Time Complexity
 The number of vertices of graph G can be
defined as n
for i = 1
to n
for j = 1
to n
for k = 1
to n
 “for loops” i and
k iterate once for
each vertex in
graph G (n
times)
 “for loop” j
iterates at
most n -1
times (O(n))
 Cumulatively
this results in
a total
running time
of:
O(n3)
SNN – R Code Example
•
•
•
•
•
•
•
•
library(“igraph”)
library(“ProximityMeasure”)
data =
c(
0, 1, 0, 0, 1, 0,
1, 0, 1, 1, 1, 0,
0, 1, 0, 1, 0, 0,
0, 1, 1, 0, 1, 1,
1, 1, 0, 1, 0, 0,
0, 0, 0, 1, 0, 0)
mat = matrix(data,6,6)
G = graph.adjacency(mat,mode=c("directed"),
weighted=NULL)
V(G)$label<-c(‘A’,’B’,’C’,’D’,’E’,’F’)
tkplot(G)
SNN(mat, 2)
[0] A -- D
[1] B -- D
[2] B -- E
[3] C -- E
A
E
B
D
C
F
SNN – Outlier/Anomaly Detection
Outlier/Anomaly
Outlier/Anomaly
• something that
deviates from what is
standard, normal, or
expected
Outlier/Anomaly
Detection
• detecting patterns in
a given data set that
do not conform to an
established normal
behavior
3.5
3
2.5
2
1.5
1
0.5
0
0
1
2
3
SNN - Strengths
Ability to handle noise
and outliers
Ability to handle clusters
of different sizes and
shapes
Very good at handling
clusters of varying
densities
SNN - Weaknesses
Does not take into account
the weight of the link
between the nodes in a
nearest neighbor graph
A low similarity amongst
nodes of the same cluster in
a graph can cause it to find
nearest neighbors that are
not in the same cluster
Time Complexity Comparison
Run Time
HITS
Nuemann Kernel
Shared Nearest
Neighbor
O(k*n2.376)
O(n2.376)
O(n3)
Conclusion:
Nuemann Kernel <= HITS < SNN