Part 1 : Data Acquisition and Characteristics

Question 1

Analogue to Digital conversion involves

Answer 1

Sampling and Quantisation.

Question 2

Sampling

Answer 2

Ascertain the momentary value of (an analogue signal) many times a second so as to convert the signal to digital form.

Question 3

Quantisation

Answer 3

The process of mapping a large set of input values to a (countable) smaller set.

Question 4

Nyquist Shannon Sampling Theorem

Answer 4

If a function x(t) contains no frequencies higher than B hertz, it is completely determined by giving its ordinates at a series of points spaced 1/2B seconds apart.

Question 5

Nyquist Shannon Sampling Theorem (Laymans)

Answer 5

If the highest frequency in the signal is f(max) the sampling rate must be at least 2f(max).

Question 6

Valid distance measure D(a,b) has properties

Answer 6

• Non-negative
• Reflexive
• Symmetric
• Satisfies Triangular Inequality

Question 7

Minowski Distant or order p (p-norm distance) is defined as

Answer 7

D(x,y) = (Σ|x(i) - y(i)|^p)^(1/p)

Question 8

When p=1, 1-norm distance, Minowski

Answer 8

(aka Manhattan)

D(x,y) = Σ|x(i) - y(i)|

Question 9

When p=2, 2-norm distance, Minowksi

Answer 9

(aka Euclidean)

D(x,y) = ((x-y)^T(x-y))^(1/2)

Question 10

When p=∞, ∞-norm distance, Minowski

Answer 10

(aka Chebyshev)

D(x,y) = max(|x1-y1|, |x2-y2|,…,|xn-yn|)

Question 11

Time series

Answer 11

Successive measurements made over a time interval

Question 12

(Numerical Time Series), P-norm Distances can only

Answer 12

• Compare time series of the same length
• Very Sensitive respect to signal transformations
• Shifting
• Uniform Amplitude Scaling
• Non-Uniform Amplitude Scaling
• Uniform Time Scaling

Question 13

Dynamic Time Warping (Berndt and Clifford, 1994)

Answer 13

• Replaces Euclidean one-to-one with many-to-one
• Recognises similar shapes, even in the presence of shifting and/or scaling
• X = (x0,…,xn) and Y = (y0,…,yn) and Rest(X) = (x1,…,xn)
• DTW(X,Y) = D(x0,y0) + min{DTW(x, REST(Y)), DTW(REST(X),Y), DTW (REST(X), REST(Y)))}
• Solved Efficiently using dynamic programming by building an nxm distance matrix

Question 14

(Distance Symbolic) in text could be

Answer 14

• Syntactic

- Semantic

Question 15

Syntactic

Answer 15

• Defined over symbolic data of the same length

- Measures the number of substitutions required to change one string/number into another

Question 16

Syntactic e.g. Hamming Distance

Answer 16

Returns the number of mismatches, max = length

Question 17

Syntactic e.g. Edit Distance

Answer 17

Measures the minimum number of ‘operations’ required to transform one sequence to another

Question 18

Syntactic e.g. Edit Distance - Operations

Answer 18

• Insertion
• Substitutions
• Deletion

Question 19

Semantic

Answer 19

Built on top of a hierarchy of word semantics, e.g. WordNet (Princeton)

Question 20

Semantic tool WordNet

Answer 20

Contains 117,000 synsets (synset: set of one or more synonyms that are interchangeable in some context)

Question 21

Semantic e.g. WUP ( Wu and Palmer Distance, 1994)

Answer 21

WUP finds the path length to the root node from the LCS (Least Common Subsrciber), the value is scaled by the sim of the path lengths from the original concepts to the root.

Question 22

Semantic e.g. WUP Equation

Answer 22

WUP(C1,C2) = (2N3)/(N1+N2+(2N3))

Question 23

WordNet Relationships - Hyponomy

Answer 23

(is-a relationship) e.g. furniture -> bed

Question 24

WordNet Relationships - Meronymy

Answer 24

(part-of relationship) e.g. chair -> seat

Question 25

WordNet Relationships - Troponymy

Answer 25

[for verb hierarchies] (specific manner) e.g. communicate -> talk -> whisper

Question 26

WordNet Relationships - Antonymy

Answer 26

(strong contact) e.g. wet dry

Question 27

Mean - 1D

Answer 27

µ = 1/N(Σx(i))

Question 28

Variance(Spread) - 1D

Answer 28

σ^2 = 1/(N-1)(Σ(x(i)-µ)^2)

Question 29

Standard Deviation - 1D

Answer 29

σ = (1/(N-1)(Σ(x(i)-µ)^2))^(1/2)

Question 30

Mean - Multi-Dimensional

Answer 30

Calculated independently for each dimension

Question 31

Variance - Multi-Dimensional

Answer 31

Computed along each dimension using a Covariance Matrix

Question 32

Covariance Matrix

Answer 32

• Variances on the diagonal

- Also measures correlation

Question 33

Covariance Matrix (Correlation)

Answer 33

• Positive Covariance, means a proportional relationship between the variables
• Negative Covariance, indicates an inverse proportional relationship

Question 34

Eigenvectors and Eigenvalues

Answer 34

Av = λv

• v -> EigenVector
• λ -> EigenValue

Question 35

Characteristic Equation

Answer 35

|A − λI| = 0

• I -> Identity Matrix
• A -> Determinant of the Matrix

Question 36

Determinant of a Matrix

Answer 36

|A| = ad − bc

Question 37

Eigenvectors define principle axis

Answer 37

• Major Axis: eigenvector corresponding to larger Eigenvalue
• Minor Axis: eigenvector corresponding to smaller Eigenvalue
• Represented using major and minor axis of ellipses

Question 38

Data Normalisation Methods

Answer 38

• Rescaling
• Standardisation (aka z-score)
• Scaling to unit length

Question 39

(Data Normalisation) Rescaling

Answer 39

x’ = ( x- min(x) / max(x)-min(x) )

Question 40

(Data Normalisation) Standardisation

Answer 40

x’ = (x-µ) / σ

Question 41

(Data Normalisation) Scaling to Unit Length

Answer 41

x’ = x / ||x||

Question 42

Data Outliers

Answer 42

small number of points with values significantly different from that other points, not always easy to remove

Question 43

Median

Answer 43

• Difficult, median of two sets cannot be defined in terms of the individual medians

Question 44

Note - Sample Variance Vs. Variance

Answer 44

Only estimates, (N-1) gives unbiased estimate of the variance

Question 45

Normal Distribution

Answer 45

N(µ, σ^2)

Question 46

Normal Distribution - Standard Deviation

Answer 46

• 1sd - 68%
• 2sd - 95%
• 3sd - 99.9%

Question 47

Normal Distribution - Multi-Dimensional

Answer 47

Normal Distribution - Multi-Dimensional