In [24]:
## Solution 1.
import numpy as np
A = np.array([[0, 0, 1, 0, 0, 1, 0, 0], #A
[0, 0, 0, 0, 1, 0, 0, 1], #B
[1, 0, 0, 1, 0, 1, 0, 0], #C
[0, 0, 1, 0, 1, 0, 1, 0], #D
[0, 1, 0, 1, 0, 0, 0, 1], #E
[1, 0, 1, 0, 0, 0, 1, 0], #F
[0, 0, 0, 1, 0, 1, 0, 1], #G
[0, 1, 0, 0, 1, 0, 1, 0] #H
])
print "Adjacent Matrix A:"
print A
print "Zero elements in A:"
print A.shape[1]* A.shape[0] - A.sum()
print "Sum as well as Non zero elements in A:"
print A.sum()
print "=========================================="
D = np.diag([2,2,3,3,3,3,3,3])
print "Degree Matrix D:"
print D
print "=========================================="
L = D - A
print "Laplacian Matrix L:"
print L
2 -----6
/ \ |
1 4 |
\ / \ |
3 5
The goal is to find two clusters in this graph using Spectral Clustering on the Laplacian matrix. Compute the Laplacian of this graph. Then compute the second eigen vector of the Laplacian (the one corresponding to the second smallest eigenvalue).
To cluster the points, we decide to split at the mean value. We say that a node is a tie if its value in the eigen-vector is exactly equal to the mean value. Let's assume that if a point is a tie, we choose its cluster at random. Identify the true statement from the list below.
In [62]:
import numpy as np
A = np.array([[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 0, 0],
[1, 0, 0, 1, 0, 0],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[0, 1, 0, 0, 1, 0]
])
D = np.diag([2, 2, 2, 3, 2, 2])
L = (D - A)
print "=========================================="
print "Graph Laplacian Matrix: "
print L
values, vectors = np.linalg.eig(L)
print "Eigen values: "
values = np.around(values, decimals=4)
print values
print "=========================================="
print "Eigen vectors: "
vectors = np.around(vectors, decimals=4)
print vectors
print "=========================================="
print "Second Smallest Eigen vectors: "
print vectors[:, 2]
print "=========================================="
print "Mean of each row in vectors: "
print np.mean(vectors[:, 2])
We wish to estimate the surprise number (2nd moment) of a data stream, using the method of AMS. It happens that our stream consists of ten different values, which we'll call 1, 2,..., 10, that cycle repeatedly. That is, at timestamps 1 through 10, the element of the stream equals the timestamp, at timestamps 11 through 20, the element is the timestamp minus 10, and so on. It is now timestamp 75, and a 5 has just been read from the stream. As a start, you should calculate the surprise number for this time.
For our estimate of the surprise number, we shall choose three timestamps at random, and estimate the surprise number from each, using the AMS approach (length of the stream times 2m-1, where m is the number of occurrences of the element of the stream at that timestamp, considering all times from that timestamp on, to the current time). Then, our estimate will be the median of the three resulting values.
You should discover the simple rules that determine the estimate derived from any given timestamp and from any set of three timestamps. Then, identify from the list below the set of three "random" timestamps that give the closest estimate.
In [78]:
def cal_supprise(current_t = 75):
common = ( current_t / 10 ) % 10
more_set = ( current_t ) % 10
less_set = 10 - more_set
return more_set * (common+1)**2 + less_set * (common**2)
def AMS(time_list, current_t = 75):
estimates = []
for t in time_list:
delta = current_t - t
elem = t % 10
threshold = current_t % 10
common = (delta / 10) % 10
if elem > threshold:
estimates.append( ( 2*common - 1)*current_t )
else:
estimates.append( ( 2*common + 1)*current_t )
return estimates
print cal_supprise()
print np.mean(AMS([31,32,44]))
print np.mean(AMS([14,35,42]))
print np.mean(AMS([32,48,50]))
print np.mean(AMS([22,42,62]))
In [ ]:
#buffer
We wish to use the Flagolet-Martin lgorithm of Section 4.4 to count the number of distinct elements in a stream. Suppose that there are ten possible elements, 1, 2,..., 10, that could appear in the stream, but only four of them have actually appeared. To make our estimate of the count of distinct elements, we hash each element to a 4-bit binary number. The element x is hashed to 3x + 7 (modulo 11). For example, element 8 hashes to 3*8+7 = 31, which is 9 modulo 11 (i.e., the remainder of 31/11 is 9). Thus, the 4-bit string for element 8 is 1001.
A set of four of the elements 1 through 10 could give an estimate that is exact (if the estimate is 4), or too high, or too low. You should figure out under what circumstances a set of four elements falls into each of those categories. Then, identify in the list below the set of four elements that gives the exactly correct estimate.
In [63]:
def hash1(x):
return (3*x + 7) % 11
def printBinary(x):
print "- The binary result of {0} is:".format(str(x)) + str(bin(x))
def countTrailingZerosInBinary(num):
bnum = str(bin(num))
return len(bnum) - len(bnum.rstrip('0'))
def FlagoletMatrtin(hash_list):
maxnum = 0
for val in hash_list:
num = countTrailingZerosInBinary(val)
if num > maxnum:
maxnum = num
return 2**maxnum
print FlagoletMatrtin(([hash1(x) for x in [1,3,6,8]]))
print FlagoletMatrtin(([hash1(x) for x in [2,4,6,10]]))
print FlagoletMatrtin(([hash1(x) for x in [2,6,8,10]]))
print FlagoletMatrtin(([hash1(x) for x in [3,4,8,10]]))
print "================="
print FlagoletMatrtin(([hash1(x) for x in [2,6,8,9]]))
print FlagoletMatrtin(([hash1(x) for x in [4,6,9,10]]))
print FlagoletMatrtin(([hash1(x) for x in [1,5,8,9]]))
print FlagoletMatrtin(([hash1(x) for x in [1,6,7,10]]))
print "================="
print FlagoletMatrtin(([hash1(x) for x in [1,2,3,9]]))
print FlagoletMatrtin(([hash1(x) for x in [1,3,9,10]]))
print FlagoletMatrtin(([hash1(x) for x in [3,4,8,10]]))
print FlagoletMatrtin(([hash1(x) for x in [4,6,9,10]]))
print "================="
print FlagoletMatrtin(([hash1(x) for x in [1,4,7,9]]))
print FlagoletMatrtin(([hash1(x) for x in [4,6,9,10]]))
print FlagoletMatrtin(([hash1(x) for x in [1,6,7,10]]))
print FlagoletMatrtin(([hash1(x) for x in [4,5,6,10]]))
End Time 100 98 95 92 87 80 65
Size 1 1 2 2 4 8 8
In [ ]: