<jupyter_start><jupyter_text>K-means clustering demo  1. Different distance metrics<jupyter_code>from math import sqrt

def manhattan(v1,v2):
    res=0
    dimensions=min(len(v1),len(v2))

    for i in range(dimensions):
        res+=abs(v1[i]-v2[i])

    return res


def euclidean(v1,v2):
    res=0
    dimensions=min(len(v1),len(v2))
    for i in range(dimensions):
        res+=pow(abs(v1[i]-v2[i]),2)

    return sqrt(float(res))


def cosine(v1,v2):
    dotproduct=0
    dimensions=min(len(v1),len(v2))

    for i in range(dimensions):
        dotproduct+=v1[i]*v2[i]

    v1len=0
    v2len=0
    for i in range (dimensions):
        v1len+=v1[i]*v1[i]
        v2len+=v2[i]*v2[i]

    v1len=sqrt(v1len)
    v2len=sqrt(v2len)
    
    # we need distance here - 
    # we convert cosine similarity into distance
    return 1.0-(float(dotproduct)/(v1len*v2len))
  

def pearson(v1,v2):
    # Simple sums
    sum1=sum(v1)
    sum2=sum(v2)
  
    # Sums of the squares
    sum1Sq=sum([pow(v,2) for v in v1])
    sum2Sq=sum([pow(v,2) for v in v2])
  
    # Sum of the products
    pSum=sum([v1[i]*v2[i] for i in range(min(len(v1),len(v2)))])
  
    # Calculate r (Pearson score)
    numerator=pSum-(sum1*sum2/len(v1))
    denominator=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))
    if denominator==0: return 1.0
    
    # we need distance here - 
    # we convert pearson correlation into distance
    return 1.0-numerator/denominator


def tanimoto(v1,v2):
    c1,c2,shared=0,0,0

    for i in range(len(v1)):
        if v1[i]!=0 or v2[i]!= 0:
            if v1[i]!=0: c1+=1 # in v1
            if v2[i]!=0: c2+=1 # in v2
            if v1[i]!=0 and v2[i]!=0: shared+=1 # in both
    
    # we need distance here - 
    # we convert tanimoto similarity into distance
    return 1.0-(float(shared)/(c1+c2-shared))<jupyter_output><empty_output><jupyter_text>2. K-means clustering algorithm<jupyter_code>import random

# k-means clustering
def kcluster(rows,distance=euclidean,k=4):
    # Determine the minimum and maximum values for each point
    ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows]))
    for i in range(len(rows[0]))]

    # Create k randomly placed centroids
    clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0]
                            for i in range(len(rows[0]))] for j in range(k)]
  
    lastmatches=None
    bestmatches = None

    for t in range(100):
        print ('Iteration %d' % t)
        bestmatches=[[] for i in range(k)]
    
        # Find which centroid is the closest for each row
        for j in range(len(rows)):
            row=rows[j]
            bestmatch=0
            for i in range(k):
                d=distance(clusters[i],row)
                if d<distance(clusters[bestmatch],row): bestmatch=i
            bestmatches[bestmatch].append(j)

        # If the results are the same as last time, this is complete
        if bestmatches==lastmatches: break
        lastmatches=bestmatches
    
        # Move the centroids to the average of the cluster members
        for i in range(k):
            avgs=[0.0]*len(rows[0])
            if len(bestmatches[i])>0:
                for rowid in bestmatches[i]:
                    for m in range(len(rows[rowid])):
                        avgs[m]+=rows[rowid][m]
                for j in range(len(avgs)):
                    avgs[j]/=len(bestmatches[i])
                clusters[i]=avgs
      
    return bestmatches<jupyter_output><empty_output><jupyter_text>3. Toy demo: clustering papers by title 3.1. Data preparationThe input is a list of Computer Science paper titles from file [titles.txt](titles.txt).<jupyter_code>file_name = "titles.txt"
f = open(file_name, "r", encoding="utf-8")
i = 0
for line in f:
    print("document", i, ": ", line.strip())
    i += 1<jupyter_output><empty_output><jupyter_text>To compare documents written in Natural Language, we need to decide how to decide which attributes of a document are important.  The simplest possible model is called a **bag of words**: that is we consider each word in a document as a separate and independent dimension. First, we collect all different words occuring across all the document collection (called corpora in NLP). These will become our dimensions.We create a vector as big as the entire vocabulary in a given corpora.Next we represent each document as a numeric vector: the number of occurrences of a given word becomes value in the corresponding vector dimension.Here are the functions for converting documents into bag of words:<jupyter_code>import re

# Returns dictionary of word counts for a text
def get_word_counts(text, all_words):
    wc={}
    words = get_words(text)
    # Loop over all the entries

    for word in words:
        if (word not in stopwords) and (word in all_words):
            wc[word] = wc.get(word,0)+1

    return wc

# splits text into words
def get_words(txt):
    # Split words by all non-alpha characters
    words=re.compile(r'[^A-Z^a-z]+').split(txt)

    # Convert to lowercase
    return [word.lower() for word in words if word!='']


# converts counts into a vector
def get_word_vector(word_list, wc):
    v = [0]*len(word_list)
    for i in range(len(word_list)):
        if word_list[i] in wc:
            v[i] = wc[word_list[i]]
    return v


# prints matrix
def print_word_matrix(docs):
    for d in docs:
        print (d[0], d[1])<jupyter_output><empty_output><jupyter_text>Some words of the document should be ignored. These are words that are very commonly used in all documents no matter the topic of the document: ''the'', ''it'', ''and'' etc. These words are called **stop words**. Which words to consider as stop words is application-dependent. One of possible stop words collection is given in file ''stop_words.txt''.<jupyter_code>stop_words_file = "stop_words.txt"
f = open(stop_words_file, "r", encoding="utf-8")

stopwords = []
for line in f:
    stopwords.append(line.strip())
    
f.close()

print(stopwords[:20])<jupyter_output><empty_output><jupyter_text>We collect all unique words and for each document we will count how many times each word is present.<jupyter_code>file_name = "titles.txt"
f = open(file_name, "r", encoding="utf-8")

documents = []
doc_id = 1
all_words = {}

# transfer content of a file into a list of lines
lines = [line for line in f]

# create a dictionary of all words and their total counts
for line in lines:
    doc_words = get_words(line)
    for w in doc_words :
        if w not in stopwords:
            all_words[w] = all_words.get(w,0)+1

unique_words = set()
for w, count in all_words.items():
    if all_words[w] > 1 :
        unique_words.add(w)

# create a matrix of word presence in each document
for line in lines:
    documents.append(["d"+str(doc_id), get_word_counts(line,unique_words)])
    doc_id += 1

unique_words=list(unique_words)
print("All unique words:",unique_words)
print(documents)<jupyter_output><empty_output><jupyter_text>Now we want to convert each document into a numeric vector:<jupyter_code>out = open(file_name.split('.')[0] + "_vectors.txt", "w")

# write a header which contains the words themselves
for w in unique_words:
    out.write('\t' + w)
out.write('\n')

# print_word_matrix to file
for i in range(len(documents)):
    vector = get_word_vector(unique_words, documents[i][1])
    out.write(documents[i][0])
    for x in vector:
        out.write('\t' + str(x))
    out.write('\n')
out.close()<jupyter_output><empty_output><jupyter_text>Our data now looks like this matrix:<jupyter_code>doc_vectors_file = "titles_vectors.txt"
f = open(doc_vectors_file, "r", encoding="utf-8")
s = f.read()
print(s)
# This function will read document vectors file and produce 2D data matrix, 
# plus the names of the rows and the names of the columns.
def read_vector_file(file_name):
    f = open(file_name)
    lines=[line for line in f]
  
    # First line is the column headers
    colnames=lines[0].strip().split('\t')[:]
    # print(colnames)
    rownames=[]
    data=[]
    for line in lines[1:]:
        p=line.strip().split('\t')
        # First column in each row is the rowname
        if len(p)>1:
            rownames.append(p[0])
            # The data for this row is the remainder of the row
            data.append([float(x) for x in p[1:]])
    return rownames,colnames,data


# This function will transpose the data matrix
def rotatematrix(data):
    newdata=[]
    for i in range(len(data[0])):
        newrow=[data[j][i] for j in range(len(data))]
        newdata.append(newrow)
    return newdata<jupyter_output><empty_output><jupyter_text>As the result of all this, we have the matrix where the rows are document vectors.Each vector dimension represents a unique word in the collection.The value in each dimension represents the count of this word in a particular document.  3.2. Clustering documents Performing k-means clustering.<jupyter_code>doc_vectors_file = "titles_vectors.txt"
docs,words,data=read_vector_file(doc_vectors_file)

num_clusters=2
print('Searching for {} clusters:'.format(num_clusters))
clust=kcluster(data,distance=pearson,k=num_clusters)
print()

print ('Document clusters')
print ('=================')
for i in range(num_clusters):
    print ('cluster {}:'.format(i+1))
    print ([docs[r] for r in clust[i]])
    print()<jupyter_output><empty_output><jupyter_text>Does this grouping make sense?<jupyter_code>for d in documents:
    print(d)<jupyter_output><empty_output><jupyter_text>3.3. Clustering words by their occurrence in documentsWe may consider that the words are similar if they occur in the same document. We say that the words are connected - they belong to the same topic, they occur in a similar context.If we want to cluster words by their occurrences in the documents, all we need to do is to transpose the document matrix.<jupyter_code>rdata=rotatematrix(data)
num_clusters = 3
print ('Grouping words into {} clusters:'.format(num_clusters))
clust=kcluster(rdata,distance=cosine,k=num_clusters)
print()
print ('word clusters:')
print("=============")
for i in range(num_clusters):
    print("cluster {}".format(i+1))
    print ([words[r] for r in clust[i]])
    print()<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup