What is Data Mining?
in Databases I
Data mining is the discovery of models for data
• Statistical Modeling: Construction of a statistical model for the data
• Machine Learning (training and test datasets)
• Computational ( Summarizing or Extracting prominent features)
1
Big Data characteristics (five Vs)
• Volume
The quantity of generated and stored data. The size of the data determines the value and potential insight- and whether it can actually be considered big data or not.
• Variety
The type and nature of the data. This helps people who analyze it to effectively use the resulting insight.
• Velocity
In this context, the speed at which the data is generated and processed to meet the demands and challenges that lie in the path of growth and development.
• Variability
Inconsistency of the data set can hamper processes to handle and manage it.
• Veracity
The data quality of captured data can vary greatly, affecting the accurate analysis.
2
Linear Algebra
in Databases I
Review
Source: Linear Algebra and Matrices – UCL
3
Review Linear Algebra
• Definitions-Scalars
• Vectors and Matrices
• Vector and Matrix calculations
• Identity, inverse matrices & determinants
• Eigenvectors & inner products
4
Scaler
in Databases I
• A quantity (variable), described by a single real number
5
Vector
in Databases I
• Series of numbers (e.g. . A column of numbers) Not a physics vector (magnitude, direction)
OR=
i.e. A column of numbers
x1 x2
xn
6
Matrix
• •
•
Rectangular display of vectors in rows and columns Can inform about the same vector intensity at different times simultaneously .
Vector is just a n x 1 matrix
x11 x12 x13
x21 x22 x23
x31 x32 x33
7
Transposition
2
3
dT =4
9
b=1
1
column row row column
bT =1 1 2
d=3 4 9
1 2 3
A=5 4 1
6 7 4
1 5 6
AT =2 4 7
3 1 4
Linear Algebra & Matrices, MfD 2010
Matrix Calculations
Addition
– Commutative: A+B=B+A
– Associative: (A+B)+C=A+(B+C)
A+B=2 4+1 0=2+1 4+0=3 4 2 5 3 1 2 + 3 5 + 1 5 6
Subtraction
– By adding a negative matrix
Linear Algebra & Matrices, MfD 2010
Scalar multiplication Scalar * matrix = scalar multiplication
Linear Algebra & Matrices, MfD 2010
Matrix Multiplication
in Databases I
11
Matrix Multiplication
n m
l
in Databases I
A1 A2 A3
A4 A5 A6
A7 A8 A9 A10 A11 A12
B13 B14 B15 B16 B17 B18
k = m x l matrix
12
Matrix multiplication
➢ Matrix multiplication is NOT commutative i.e the order matters!
AB≠BA
➢ Matrix multiplication IS associative
A(BC)=(AB)C
➢ Matrix multiplication IS distributive
A(B+C)=AB+AC (A+B)C=AC+BC
13
Identify Matrix
For any nxn matrix A, we have A In = In A = A matrices)
in Databases I
14
Part II
More Advanced Matrix Techniques
Linear Algebra & Matrices, MfD 2010
Vector components & orthonormal base
• A given vector (a b) can be summarized by its components, but only in a particular base (set of axes; the vector itself can be independent from the choice of this particular base).
v
example a and b are the components of v
y axis b
v
a
in the given base (axes chosen for expression of the coordinates in vector space)
Orthonormal base: set of vectors chosen to express the components of the others, perpendicular to each other and all with norm (length) = 1
x axis
Linear Algebra & Matrices, MfD 2010
Linear combination & dimensionality
Vectorial space: space defined by different vectors (for example for dimensions…).
The vectorial space defined by some vectors is a space that contains them and all the vectors that can be obtained by multiplying these vectors by a real number then adding them (linear combination).
A matrix A (mn) can itself be decomposed in as many vectors as its number of columns (or lines). When decomposed, one can represent each column of the matrix by a vector. The ensemble of n vector-column defines a vectorial space proper to matrix A.
Similarly, A can be viewed as a matricial representation of this ensemble of vectors, expressing their components in a given base.
Linear Algebra & Matrices, MfD 2010
Linear dependency and rank
If one can find a linear relationship between the lines or columns of a matrix, then the rank of the matrix (number of dimensions of its vectorial space) will not be equal to its number of column/lines – the matrix will be said to be rank- deficient.
Example
X=( ) 24
12
y
4
x =()
1
12
When representing the vectors, we see that x1 and x2 are superimposed. If we look better, we see that we can express one by a linear combination of the other: x2 = 2 x1.
The rank of the matrix will be 1.
In parallel, the vectorial space defined will has only one dimension.
x =() 2 24
x2
2
12
x
Linear Algebra & Matrices, MfD 2010
x 1
Linear dependency and rank
• The rank of a matrix corresponds to the dimensionality of the vectorial space defined by this matrix. It corresponds to the number of vectors defined by the matrix that are linearly independents from each other.
• Linealy independent vectors are vectors defining each one one more dimension in space, compared to the space defined by the other vectors. They cannot be expressed by a linear combination of the others.
Note. Linearly independent vectors are not necessarily orthogonal (perpendicular). Example: take 3 linearly independent vectors x1, x2 et x3.
Vectors x1 and x2 define a plane (x,y) And vector x3 has an additional non-zero component in the z axis.
But x3 is not perpendicular to x1 or x2.
x 3
x 1
x 2
plan (x,y)
Linear Algebra & Matrices, MfD 2010
Eigenvalues et eigenvectors
One can represent the vectors from matrix X (eigenvectors of A) as a set of orthogonal vectors (perpendicular), and thus representing the different dimensions of the original matrix A.
The amplitude of the matrix A in these different dimensions will be given by the eigenvalues corresponding to the different eigenvectors of A (the vectors composing X).
Note: if a matrix is rank-deficient, at least one of its eigenvalues is zero.
For A’:
u1, u2 = eigenvectors k1, k2 = eigenvalues
In Principal Component Analysis (PCA), the matrix is decomposed into eigenvectors and eigenvalues AND the matrix is rotated to a new coordinate system such that the greatest variance by any projection of the data comes to lie on the first coordinate (called the first principal component), the second greatest variance on the second coordinate, and so on.
Linear Algebra & Matrices, MfD 2010
3 Outer product = matrix
Vector Products
x1 x1y1 x1y2 x1y3 xyT =xy y y=xy xy xy
T Outer product XY
(nx1) (1xn)
x1 y1
x = x2 y = y2
Two vectors:
Inner product = scalar
xTy=x1 x2 x3 y2=x1y1 +x2y2 +x3y3 = 3 xiyi
x y 3 3
y1 y
i=1
is a matrix
Inner product XTY is a scalar (1xn) (nx1)
2 1 2 3 2 1 2 2 2 3 x3 x3y1 x3y2 x3y3
Linear Algebra & Matrices, MfD 2010
Scalar product of vectors
Calculate the scalar product of two vectors is equivqlent to make the projection of one vector on the other one. One can indeed show that x1 •x2 = x1 . x2 . cos where is the angle that separates two vectors when they have both the same origin.
x 1
x cos 2
In parallel, if two vectors are orthogonal, their scalar product is zero: the projection of one onto the other will be zero.
x1 x2= x.x.cos •12
Linear Algebra & Matrices, MfD 2010
Determinants
For a matrix 11:
det(a )=a
For a matrix 22:
a a =a a −a a
11 12
11 11
aa
11 22 12 21
21 22
For a matrix 33: a11 a12 a13
a21 a22 a23 = a11a22a33+a12a23a31+a13a21a32–a11a23a32 –a12a21a33 –a13a22a31 a31 a32 a33
= a11(a22a33 –a23a32)–a12(a21a33 –a23a31)+a13(a21a32 –a22a31)
The determinant of a matrix can be calculate by multiplying each element of one of its lines by the determinant of a sub-matrix formed by the elements that stay when one suppress the line and column containing this element. One give to the obtained product the sign (-1)i+j.
Linear Algebra & Matrices, MfD 2010
Determinants •Determinants can only be found for square matrices.
•For a 2×2 matrix A, det(A) = ad-bc. Lets have at closer look at that:
[]
The determinant gives an idea of the ’volume’ occupied by the matrix in vector space
A matrix A has an inverse matrix A-1 if and only if det(A)≠0.
ab
det(A) =
= ad – bc cd
Linear Algebra & Matrices, MfD 2010
Determinants
The determinant of a matrix is zero if and only if there exist a linear relationship between the lines or the columns of the matrix – if the matrix is rank-deficient. In parallel, one can define the rank of a matrix A as the size of the largest square sub-matrix of A that has a non-zero determionant.
X=( ) 24
12
y
4
x =()
1
12
Here x1 and x2 are superimposed in space, because one can be expressed by a linear combination of the other: x2 = 2 x1.
The determinant of the matrix X will thus be zero.
The largest square sub-matrix with a non- zero determinant will be a matrix of 1×1 => the rank of the matrix is 1.
x2 2
x =() 2 24
12
x
Linear Algebra & Matrices, MfD 2010
x 1
Determinants
• In a vectorial space of n dimensions, there will be no more than n linearly independent vectors.
• If 3 vectors (21) x’1, x’2, x’3 are represented by a matrix X’: Graphically, we have:
123 X’=( )
Here x3 can be expressed by a linear combination of x1 and x2.
yy
221
The determinant of the matrix 3 X’ will thus be zero.
The largest square sub-matrix with a non-zero determinant will be a matrix of 2×2 => the rank of the matrix is 2.
3 2 1
x =ax +bx 2 1 3
(1,2) 2
(2,2)
x2 1
x 2
ax1 123x123x
(3,1)
x 3
bx3
Linear Algebra & Matrices, MfD 2010
x 1
Determinants
The notions of determinant, of the rank of a matrix and of linear dependency are closely linked.
Take a set of vectors x1, x2,…,xn, all with the same number of elements: these vectors are linearly dependent if one can find a set of scalars c1, c2,…,cn non equal to zero such as:
c1 x1+ c2 x2+…+ cn xn= 0
A set of vectors are linearly dependent if one of then can be expressed as a
linear combination of the others. They define in space a smaller number of dimensions than the total number of vectors in the set. The resulting matrix will be rank-deficient and the determinant will be zero.
Similarly, if all the elements of a line or column are zero, the determinant of the matrix will be zero.
If a matrix present two rows or columns that are equal, its determinant will also be zero
Linear Algebra & Matrices, MfD 2010
•
Matrix inverse
Definition. A matrix A is called nonsingular or invertible if there exists a matrix B such that:
11X2-
33 3333
1=2+
1-
1
+
1=10
–
Notation. A common notation for the inverse of a matrix A is A-1. So:
21+
1211-
33 3333
2
+
201
•
•
A-1 is also invertible and then (AT)-1 = (A-1)T
The inverse matrix is unique when it exists. So if A is invertible, then
• In Matlab: A-1 = inv(A)
•Matrix division: A/B= A*B-1
Linear Algebra & Matrices, MfD 2010
Matrix inverse
• For a XxX square matrix:
• The inverse matrix is:
• E.g.: 2×2 matrix
For a matrix to be invertible, its determinant has to be non-zero (it has to be square and of full rank).
A matrix that is not invertible is said to be singular.
Reciprocally, a matrix that is invertible is said to be non-singular.
Linear Algebra & Matrices, MfD 2010
Review
in Databases I
Review of Probability and Statistics
30
Probability in discrete space
Probability Axioms:
P(A) 0 P() =1
For Mutually Exclusive/Disjoint Events:
P(A1 A2 …An)=P(A1)+P(A2)+…+P(An)
A1
A2
A3
A4
A5
A6
A7
A8
A9
A10
A11
A12
A13
A14
A15
A16
A17
A18
A19
A20
31
Classical Probability
◼ Assumes all outcomes in the sample space are equally likely to occur
Classical probability of event A:
P(A) = NA = number of outcomes that satisfy the event A N total number of outcomes in the sample space
• Requires a count of the outcomes in the sample space
Probability in discrete space
Lemma:
P(A) =1− P(A)
P(A B) = P(A) + P(B) − P(A B)
33
Expectation of function variables
E[f(x)]=x f(x)p(x) 𝐸 𝑔(𝑋 )=න𝑔 𝑋 𝑓(𝑋)
34
Expectation of a random variables
= E[X] = x xp(x) 𝐸[𝑋] = න 𝑋𝑓(𝑋)
E[a]=a; E[aX]=aE[X]
35
Covariance between two random variables
Cov𝑥,𝑦 = ∑∑(x-μx)(y-μy)p(x,y)
Cov𝑥,𝑦 =
න න(𝑥−μ𝑥)(𝑦−μ𝑦)𝑓(𝑥,𝑦)
36
Variance of a random variables
Var(X) = E[(X − )2 ] Var(a)=0; Var(aX)=a2Var(X)
37