CSE3024 – Web Mining
WINTER SEMESTER – 2019-2020
G2 SLOT
E-RECORD
Assessment No.: 03
Submitted By
Deep Agrawal
Reg. No.: 18BCE0518
B.Tech. (Branch) – II Year
SCOPE
VELLORE INSTITUTE OF TECHNOLOGY
VELLORE – 632 014
TAMIL NADU
INDIA
18BCE0518 DEEP AGRAWAL
TF-IDF, SNA, Page Rank and HITS
1. Write a program to extract the contents (excluding any tags) from the following
five websites
https://en.wikipedia.org/wiki/Web_mining
https://en.wikipedia.org/wiki/Data_mining
https://en.wikipedia.org/wiki/Artificial_intelligence
https://en.wikipedia.org/wiki/Machine_learning
https://en.wikipedia.org/wiki/Mining
save the content in five separates .doc file. Considering a vector space model and
do the following operations according to the query “Mining of large data”
import urllib.request
import urllib.parse
from bs4 import BeautifulSoup as soup
import nltk
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize
from nltk.stem import WordNetLemmatizer
import numpy as np
sw = set(stopwords.words('english'))
lemmatizer = WordNetLemmatizer()
urls = ['https://en.wikipedia.org/wiki/Web_mining',
'https://en.wikipedia.org/wiki/Data_mining',
'https://en.wikipedia.org/wiki/Artificial_intelligence',
'https://en.wikipedia.org/wiki/Machine_learning',
'https://en.wikipedia.org/wiki/Mining']
d = []
for _ in range(5):
urlOpen = urllib.request.urlopen(urls[_])
urlHTML = urlOpen.read()
urlSoup = soup(urlHTML, 'html.parser')
pageText = ''
for i in urlSoup.findAll('p'):
pageText = pageText + i.text
pageText = pageText.lower()
words = word_tokenize(pageText)
terms = [w for w in words if not w in sw]
lemTerms = ''
# Lemmatization
for w in terms:
lemTerms += lemmatizer.lemmatize(w) + ' '
with open('doc{}.doc'.format(_), 'r+', encoding='utf-8') as doc:
doc.write(lemTerms)
doc.seek(0)
d.append(doc.read())
q = 'mining of large data'
d.append(q)
pg. 2
18BCE0518 DEEP AGRAWAL
all_t = [] # Set of all terms in 5 docs
t = [] # array arrays of terms in each doc
t1 = [] # set of arrays of t
cd = [] # count of each terms in each doc
dtc = [] # array of number of terms in each doc len() = 5
for _ in range(len(d)):
words = word_tokenize(d[_])
# StopWords Removal
t.append([w for w in words if not w in sw])
for i in t[_]:
all_t.append(i)
all_t = list(set(all_t))
for _ in range(len(d)):
cd.append([0]*len(all_t))
for i in range(len(all_t)):
for j in range(len(t[_])):
if all_t[i] == t[_][j]:
cd[_][i] = cd[_][i] + 1
for _ in range(len(d)):
t1.append(list(set(t[_])))
dtc.append(len(t1[_]))
table = [['aaa', 0, 0, 0, 0, 0]]*len(all_t)
for _ in range(len(all_t)):
table[_] = [all_t[_], cd[0][_], cd[1][_], cd[2][_], cd[3][_], cd[4]
[_], cd[5][_]]
Bag-of-Words (Document set)
from tabulate import tabulate
print("Bag of words representation representation :\n")
print(tabulate(table, headers=['Term', 'Doc1', 'Doc2', 'Doc3', 'Doc4',
'Doc5', 'Query']))
pg. 3
18BCE0518 DEEP AGRAWAL
TF (Document set)
tf = []
for _ in range(len(d)):
tf.append([0]*len(all_t))
for i in range(len(all_t)):
for j in range(len(t[_])):
if all_t[i] == t[_][j]:
tf[_][i] = tf[_][i] + 1
for i in range(len(tf)):
for j in range(len(tf[i])):
tf[i][j] = round(tf[i][j] / dtc[i], 5)
for _ in range(len(all_t)):
table[_] = [all_t[_], tf[0][_], tf[1][_], tf[2][_], tf[3][_], tf[4]
[_], tf[5][_]]
print("Term Frequency :\n")
print(tabulate(table, headers=['Term', 'Doc1', 'Doc2', 'Doc3', 'Doc4',
'Doc5', 'Query']))
IDF (Document set)
idf = [0]*len(all_t)
for i in range(len(all_t)):
for j in range(len(tf)):
if tf[j][i] != 0:
idf[i] += 1
import math
pg. 4
18BCE0518 DEEP AGRAWAL
for i in range(len(idf)):
idf[i] = round(math.log(len(d) / idf[i], 10), 3)
for _ in range(len(all_t)):
table[_] = [all_t[_], idf[_]]
print("Inverse Doc Freq :\n")
print(tabulate(table, headers=['Terms', 'IDF']))
TF-IDF (Document set)
tfidf = []
for _ in range(len(d)):
tfidf.append([0]*len(all_t))
for i in range(len(all_t)):
for j in range(len(t[_])):
if all_t[i] == t[_][j]:
tfidf[_][i] = tfidf[_][i] + 1
for i in range(len(tfidf)):
for j in range(len(tfidf[i])):
tfidf[i][j] = round(tfidf[i][j] / dtc[i], 5)
for i in range(len(tfidf)):
for j in range(len(tfidf[i])):
tfidf[i][j] = round(tfidf[i][j] * idf[j], 5)
for _ in range(len(all_t)):
table[_] = [all_t[_], tfidf[0][_], tfidf[1][_], tfidf[2][_], tfidf[3]
[_], tfidf[4][_]]
In [16]:
print("TF - IDF (Document set and Query):\n")
print(tabulate(table, headers=['Term', 'Doc1', 'Doc2', 'Doc3', 'Doc4',
'Doc5']))
pg. 5
18BCE0518 DEEP AGRAWAL
TF-IDF (Query)
for _ in range(len(all_t)):
table[_] = [all_t[_], tfidf[0][_], tfidf[1][_], tfidf[2][_],
tfidf[3][_], tfidf[4][_], tfidf[5][_]]
print("TF - IDF (Document set and Query):\n")
print(tabulate(table, headers=['Term', 'Doc1', 'Doc2', 'Doc3', 'Doc4',
'Doc5', 'Query']))
Normalized (Query)
Normalized - TF-IDF (Document set)
for i in range(len(tfidf)):
temp = 0
for j in range(len(tfidf[i])):
temp += tfidf[i][j] ** 2
temp = temp ** (1/2)
for k in range(len(tfidf[i])):
tfidf[i][k] = tfidf[i][k] / temp
for _ in range(len(all_t)):
pg. 6
18BCE0518 DEEP AGRAWAL
table[_] = [all_t[_], tfidf[0][_], tfidf[1][_], tfidf[2][_], tfidf[3]
[_], tfidf[4][_], tfidf[5][_]]
In [21]:
print("TF - IDF (Normalized Document set and Query):\n")
print(tabulate(table, headers=['Term', 'Doc1', 'Doc2', 'Doc3', 'Doc4',
'Doc5', 'Query']))
Cosine Similarity
cosine = [0]*6
for i in range(len(tfidf)):
for j in range(len(tfidf[i])):
cosine[i] += tfidf[i][j] * tfidf[5][j]
cosine[i] = round(cosine[i], 5)
for i in range(len(tfidf)):
print("Cosine similarity of Doc{}: ".format(i) + str(cosine[i]))
Euclidean Distance
eu = [0]*6
for i in range(len(tfidf)):
for j in range(len(tfidf[i])):
eu[i] += (tfidf[i][j] - tfidf[5][j]) ** 2
eu[i] = round(eu[i] ** (1/2), 5)
In [25]:
for i in range(len(tfidf)):
print("Euclidean Distance of Doc{}: ".format(i) + str(eu[i]))
pg. 7
18BCE0518 DEEP AGRAWAL
Document Ranking (Display Order)
cosineSort = cosine[:]
cosineSort.sort()
cosineSort = cosineSort[::-1]
cosineSort = cosineSort[1:]
for i in range(len(cosineSort)):
index = cosine.index(cosineSort[i])
print("{}. Doc{} - Link: {}".format(i, index, urls[index]))
Document Similarity (Among Documents)
docsim1 = [0]*5
for i in range(len(tfidf) - 1):
for j in range(len(tfidf[i])):
docsim1[i] += tfidf[i][j] * tfidf[0][j]
docsim1[i] = round(docsim1[i], 5)
print(docsim1)
docsim2 = [0]*5
for i in range(len(tfidf) - 1):
for j in range(len(tfidf[i])):
docsim2[i] += tfidf[i][j] * tfidf[1][j]
docsim2[i] = round(docsim2[i], 5)
print(docsim2)
docsim3 = [0]*5
for i in range(len(tfidf) - 1):
for j in range(len(tfidf[i])):
docsim3[i] += tfidf[i][j] * tfidf[2][j]
docsim3[i] = round(docsim3[i], 5)
print(docsim3)
docsim4 = [0]*5
for i in range(len(tfidf) - 1):
for j in range(len(tfidf[i])):
docsim4[i] += tfidf[i][j] * tfidf[3][j]
docsim4[i] = round(docsim4[i], 5)
print(docsim4)
docsim5 = [0]*5
for i in range(len(tfidf) - 1):
for j in range(len(tfidf[i])):
docsim5[i] += tfidf[i][j] * tfidf[4][j]
docsim5[i] = round(docsim5[i], 5)
pg. 8
18BCE0518 DEEP AGRAWAL
print(docsim5)
2. Find out different types of centrality (degree, Betweenness, closeness) and
prestige (Degree, Proximity) using a graph dataset given in the following link.
http://snap.stanford.edu/data/wiki-Vote.txt.gz
nodes = 7115 # Number of nodes with outgoing links (no. of voters)
edges = 103689 # Number of edges (no. of votes)
with open('Wiki-Vote.txt', 'r') as dataset:
d = dataset.read()
dataset.seek(0)
d = d.split()
f = d[0::2]
fset = []
for _ in f:
if _ not in fset:
fset.append(_)
ffreq = []
for i in range(len(fset)):
ffreq.append(f.count(fset[i]))
t = d[1::2]
deg = []
for _ in range(len(fset)):
deg.append(round(ffreq[_]/nodes, 5))
In [31]:
for _ in range(len(fset)):
print('Degree Centrality of node {} is: {}'.format(fset[_], deg[_]))
print("Degree Centrality of all other nodes is 0")
pg. 9
18BCE0518 DEEP AGRAWAL
tset = []
for _ in t:
if _ not in tset:
tset.append(_)
tfreq = []
for i in range(len(tset)):
tfreq.append(t.count(tset[i]))
pdeg = []
for _ in range(len(tset)):
pdeg.append(round(tfreq[_]/nodes, 5))
for _ in range(len(fset)):
print('Degree Centrality of node {} is: {}'.format(fset[_], deg[_]))
print("Degree Centrality of all other nodes is 0")
3. Write a program to display the page rank of the given directed graph
representing web of six pages and damping factor is 0.9. Input to the program must
be adjacency matrix or adjacency list of the given web graph along with damping
factor and threshold value (stopping criteria: - ε = 0.05). The program must print
the result after each of the following scenario:
import numpy as np
l = [[0,1,1,1,0,0,0], [0,0,0,1,1,0,0], [0,0,0,0,0,1,0], [0,0,1,0,0,1,1],
[0,0,0,1,0,0,1], [0,0,0,0,0,0,0], [0,0,0,0,0,1,0]]
a. Handling the nodes with no outgoing links
for i in range(len(l)):
temp = 0
for j in range(len(l[i])):
temp += l[i][j]
if temp == 0:
l[i] = [round(1/len(l[i]), 5)]*len(l[i])
In [39]:
l
pg. 10
18BCE0518 DEEP AGRAWAL
b. Stochastic matrix formation
for i in range(len(l)):
temp = 0
for j in range(len(l[i])):
temp += l[i][j]
for k in range(len(l[i])):
l[i][k] = round(l[i][k] / temp, 5)
In [41]:
l
c. Page rank of all the seven nodes after each iteration
import numpy as np
d = 0.9
ep = 0.05
e = np.matrix([[1/7], [1/7], [1/7], [1/7], [1/7], [1/7], [1/7]])
p = [e]
k = 1
lt = np.matrix(l).transpose()
for i in range(100):
res1 = np.matrix(e) * (1 - d)
res2 = lt * p[i]
res2 = res2 * d
p.append(np.add(res1, res2))
temp = 0
res3 = np.subtract(p[k], p[k-1])
temp = np.linalg.norm(res3)
if temp < ep:
break
else:
k += 1
print(p[k])
pg. 11
18BCE0518 DEEP AGRAWAL
d. Total number iteration count until stopping criteria.
print("Number of iteration : " + str(k))
4. Write a program to implement HITS algorithm for the graph shown in Question No.
3 and display the final authority score and hub score of all the nodes after
stopping criteria are attained. (Note.: Consider the same criteria as mentioned for
Question No. 3)
l = np.matrix([[0,1,1,1,0,0,0], [0,0,0,1,1,0,0], [0,0,0,0,0,1,0],
[0,0,1,0,0,1,1], [0,0,0,1,0,0,1],
[0,0,0,0,0,0,0], [0,0,0,0,0,1,0]])
lt = l.transpose()
n = 7
ep = 0.05
a = np.matrix([1] * n).transpose()
h = np.matrix([1] * n).transpose()
k = 1
ltl = lt * l
llt = l * lt
ak = [a]
hk = [h]
for _ in range(5):
ak.append(ltl * ak[k-1])
hk.append(llt * hk[k-1])
anorm = np.linalg.norm(ak[k])
ak[k] = np.matrix(ak[k]) / (anorm)
hnorm = np.linalg.norm(hk[k])
hk[k] = np.matrix(hk[k]) / (hnorm)
if np.linalg.norm(np.subtract(ak[k], ak[k-1]))<ep and
np.linalg.norm(np.subtract(hk[k], hk[k-1]))<ep:
break
else:
k += 1
print(ak[k])
print(hk[k])
pg. 12
18BCE0518 DEEP AGRAWAL
print("Number of iterations: " + str(k))
pg. 13
