2.1 Wavelet Transform

Question 1

step1: Calculate the average of input samples

step2: Calculate the difference of input samples

step3: Regard averages as input sequence. Repeat step1 and step2 until only one output average.

Quention 2

2.2 Principal Components Analysis

import numpy as np

dimension = 3
data_num = 7
data = [[-1, -2, -3, 1, 2, 3, 1], [-1, -1, -2, 1, 1, 2, 2],
        [1, 4, -2, 1, 2, 1, 4]]

data_mean = [np.mean(data[i]) for i in range(dimension)]

# normalize data by average
for i in range(0, dimension):
    for j in range(0, len(data[0])):
        data[i][j] -= data_mean[i]

# calculate covariance matrix according to definition
cov = []
for i in range(dimension):
    for j in range(dimension):
        sumOfRowMulti = 0
        for k in range(0, data_num):
            sumOfRowMulti += data[i][k] * data[j][k]
        cov.append(sumOfRowMulti / (data_num - 1))

cov_matrix = np.asarray(cov).reshape(dimension, dimension)
print 'covariance matrix is:'
print cov_matrix

# calculate eigen value and eigen vector using numpy function
eig_val, eig_vec = np.linalg.eig(cov_matrix)

for i in range(dimension):
    print 'eigen value', i, eig_val[
        i], ' corresponding eigen vector:', eig_vec[:, i]

# sort eigen value in descending order
eig_val_sorted = np.sort(eig_val)[::-1]

# calcuate propotion
# propotion=sum of eigen value of first k components/sum of all n eigen values
propotion = (eig_val_sorted[0] + eig_val_sorted[1]) / np.sum(eig_val_sorted)

print 'proportion of total population variance explained by the first two components: %.4f' % propotion

The result is:

image.png

3 Pattern Discovery

Question 1

Step 1: Discretization

Web page

1. Sorted data for web pages : 7,9,9,11,13,14,18,35,36,45
2. Partition into 4 equal-frequency (equal-depth) bins:

• web1: 7,9,9
• web2: 11,13
• web3: 14,18,35
• web4: 36,45

Session length

1. Find the max and min value of session length: 267,2017
2. Calculate the width of intervals: width = ( 2017 – 267 )/ 3≈583.4
3. Partition into 3 equal-frequency (equal-width) bins:

• len1 (267~850.4): 267,598,672
• len2 (850.3~1433.8): 898,998,1213,1345
• len3(1433.8~2017.2): 1543,1702,2017

Transactions table after discretization

Step 2: Apriori algorithm

1st scan

generate length 1 candidate itemsets

prune infrequent itemsets

2nd scan

generate length 2 candidate itemsets

prune infrequent itemsets

3rd scan

generate length 3 candidate itemsets
no length 3 candidate

Step 3: Get frequent itemsets

{web3} (support = 0.3)
{web1} (support = 0.3)
{len3} (support = 0.3)
{len1} (support = 0.3)
{NA} (support = 0.3)
{EU} (support = 0.3)
{len2} (support = 0.4)
{AS} (support = 0.4)
{yes} (support = 0.5)
{no} (support = 0.5)
{web3,yes} (support = 0.3)
{web1,no} (support = 0.3)
{NA,no} (support = 0.3)
{AS,yes} (support = 0.3)

Question 2

Step 1: Discretization

same as question question 1

Step 2: Deduce the ordered frequent items

Step 3: Construct FP tree

FP-tree

Step 4: construct conditional FP-tree for each item

Cond. FP-tree on "web3"

{web3} (support = 0.3)

web3

Cond. FP-tree on "web1"

{web1} (support = 0.3)

web1

Cond. FP-tree on "len3"

{len3} (support = 0.3)

len3

Cond. FP-tree on "len1"

{len1} (support = 0.3)

len1

Cond. FP-tree on "NA"

{NA} (support = 0.3)

NA

Cond. FP-tree on "EU"

{EU} (support = 0.3)

EU

Cond. FP-tree on "len2"

{len2} (support = 0.4)

len2

Cond. FP-tree on "AS"

{AS} (support = 0.4)

AS

Cond. FP-tree on "yes"

{yes} (support = 0.5)

yes

Cond. FP-tree on "no"

{no} (support = 0.5)

no

Step 5: Determine frequent patterns

{web3} (support = 0.3)
{web3,yes} (support = 0.3)
{web1} (support = 0.3)
{web1,no} (support = 0.3)
{len3} (support = 0.3)
{len1} (support = 0.3)
{NA} (support = 0.3)
{NA,no} (support = 0.3)
{EU} (support = 0.3)
{len2} (support = 0.4)
{AS} (support = 0.4)
{AS,yes} (support = 0.3)
{yes} (support = 0.5)
{no} (support = 0.5)

Question 3

closed frequent patterns

{web3,yes}
{web1,no}
{len3}
{len1}
{NA,no}
{EU}
{len2}
{AS}
{AS,yes}
{yes}
{no}

maximal frequent patterns

{web3,yes}
{web1,no}
{len3}
{len1}
{NA,no}
{EU}
{len2}
{AS,yes}