kmeans_clustering_demo.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-means clustering demo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Different distance metrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import sqrt\n",
    "\n",
    "def manhattan(v1,v2):\n",
    "    res=0\n",
    "    dimensions=min(len(v1),len(v2))\n",
    "\n",
    "    for i in range(dimensions):\n",
    "        res+=abs(v1[i]-v2[i])\n",
    "\n",
    "    return res\n",
    "\n",
    "\n",
    "def euclidean(v1,v2):\n",
    "    res=0\n",
    "    dimensions=min(len(v1),len(v2))\n",
    "    for i in range(dimensions):\n",
    "        res+=pow(abs(v1[i]-v2[i]),2)\n",
    "\n",
    "    return sqrt(float(res))\n",
    "\n",
    "\n",
    "def cosine(v1,v2):\n",
    "    dotproduct=0\n",
    "    dimensions=min(len(v1),len(v2))\n",
    "\n",
    "    for i in range(dimensions):\n",
    "        dotproduct+=v1[i]*v2[i]\n",
    "\n",
    "    v1len=0\n",
    "    v2len=0\n",
    "    for i in range (dimensions):\n",
    "        v1len+=v1[i]*v1[i]\n",
    "        v2len+=v2[i]*v2[i]\n",
    "\n",
    "    v1len=sqrt(v1len)\n",
    "    v2len=sqrt(v2len)\n",
    "    \n",
    "    # we need distance here - \n",
    "    # we convert cosine similarity into distance\n",
    "    return 1.0-(float(dotproduct)/(v1len*v2len))\n",
    "  \n",
    "\n",
    "def pearson(v1,v2):\n",
    "    # Simple sums\n",
    "    sum1=sum(v1)\n",
    "    sum2=sum(v2)\n",
    "  \n",
    "    # Sums of the squares\n",
    "    sum1Sq=sum([pow(v,2) for v in v1])\n",
    "    sum2Sq=sum([pow(v,2) for v in v2])\n",
    "  \n",
    "    # Sum of the products\n",
    "    pSum=sum([v1[i]*v2[i] for i in range(min(len(v1),len(v2)))])\n",
    "  \n",
    "    # Calculate r (Pearson score)\n",
    "    numerator=pSum-(sum1*sum2/len(v1))\n",
    "    denominator=sqrt((sum1Sq-pow(sum1,2)/len(v1))*(sum2Sq-pow(sum2,2)/len(v1)))\n",
    "    if denominator==0: return 1.0\n",
    "    \n",
    "    # we need distance here - \n",
    "    # we convert pearson correlation into distance\n",
    "    return 1.0-numerator/denominator\n",
    "\n",
    "\n",
    "def tanimoto(v1,v2):\n",
    "    c1,c2,shared=0,0,0\n",
    "\n",
    "    for i in range(len(v1)):\n",
    "        if v1[i]!=0 or v2[i]!= 0:\n",
    "            if v1[i]!=0: c1+=1 # in v1\n",
    "            if v2[i]!=0: c2+=1 # in v2\n",
    "            if v1[i]!=0 and v2[i]!=0: shared+=1 # in both\n",
    "    \n",
    "    # we need distance here - \n",
    "    # we convert tanimoto similarity into distance\n",
    "    return 1.0-(float(shared)/(c1+c2-shared))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. K-means clustering algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "# k-means clustering\n",
    "def kcluster(rows,distance=euclidean,k=4):\n",
    "    # Determine the minimum and maximum values for each point\n",
    "    ranges=[(min([row[i] for row in rows]),max([row[i] for row in rows]))\n",
    "    for i in range(len(rows[0]))]\n",
    "\n",
    "    # Create k randomly placed centroids\n",
    "    clusters=[[random.random()*(ranges[i][1]-ranges[i][0])+ranges[i][0]\n",
    "                            for i in range(len(rows[0]))] for j in range(k)]\n",
    "  \n",
    "    lastmatches=None\n",
    "    bestmatches = None\n",
    "\n",
    "    for t in range(100):\n",
    "        print ('Iteration %d' % t)\n",
    "        bestmatches=[[] for i in range(k)]\n",
    "    \n",
    "        # Find which centroid is the closest for each row\n",
    "        for j in range(len(rows)):\n",
    "            row=rows[j]\n",
    "            bestmatch=0\n",
    "            for i in range(k):\n",
    "                d=distance(clusters[i],row)\n",
    "                if d<distance(clusters[bestmatch],row): bestmatch=i\n",
    "            bestmatches[bestmatch].append(j)\n",
    "\n",
    "        # If the results are the same as last time, this is complete\n",
    "        if bestmatches==lastmatches: break\n",
    "        lastmatches=bestmatches\n",
    "    \n",
    "        # Move the centroids to the average of the cluster members\n",
    "        for i in range(k):\n",
    "            avgs=[0.0]*len(rows[0])\n",
    "            if len(bestmatches[i])>0:\n",
    "                for rowid in bestmatches[i]:\n",
    "                    for m in range(len(rows[rowid])):\n",
    "                        avgs[m]+=rows[rowid][m]\n",
    "                for j in range(len(avgs)):\n",
    "                    avgs[j]/=len(bestmatches[i])\n",
    "                clusters[i]=avgs\n",
    "      \n",
    "    return bestmatches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Toy demo: clustering papers by title\n",
    "### 3.1. Data preparation\n",
    "The input is a list of Computer Science paper titles from file [titles.txt](titles.txt)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "file_name = \"titles.txt\"\n",
    "f = open(file_name, \"r\", encoding=\"utf-8\")\n",
    "i = 1\n",
    "for line in f:\n",
    "    print(\"document\", i, \": \", line.strip())\n",
    "    i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To compare documents written in Natural Language, we need to decide which attributes of a document should be used as a document dimensions.  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. \n",
    "\n",
    "First, we collect all different words occuring across all the document collection (called corpora in NLP). These will become our dimensions.\n",
    "We create a vector as big as the entire vocabulary in a given corpora.\n",
    "Next we represent each document as a numeric vector: the number of occurrences of a given word becomes value in the corresponding vector dimension.\n",
    "\n",
    "Here are the functions for converting documents into bag of words:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "# Returns dictionary of word counts for a text\n",
    "def get_word_counts(text, all_words):\n",
    "    wc={}\n",
    "    words = get_words(text)\n",
    "    # Loop over all the entries\n",
    "\n",
    "    for word in words:\n",
    "        if (word not in stopwords) and (word in all_words):\n",
    "            wc[word] = wc.get(word,0)+1\n",
    "\n",
    "    return wc\n",
    "\n",
    "# splits text into words\n",
    "def get_words(txt):\n",
    "    # Split words by all non-alpha characters\n",
    "    words=re.compile(r'[^A-Z^a-z]+').split(txt)\n",
    "\n",
    "    # Convert to lowercase\n",
    "    return [word.lower() for word in words if word!='']\n",
    "\n",
    "\n",
    "# converts counts into a vector\n",
    "def get_word_vector(word_list, wc):\n",
    "    v = [0]*len(word_list)\n",
    "    for i in range(len(word_list)):\n",
    "        if word_list[i] in wc:\n",
    "            v[i] = wc[word_list[i]]\n",
    "    return v\n",
    "\n",
    "\n",
    "# prints matrix\n",
    "def print_word_matrix(docs):\n",
    "    for d in docs:\n",
    "        print (d[0], d[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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''."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "stop_words_file = \"stop_words.txt\"\n",
    "f = open(stop_words_file, \"r\", encoding=\"utf-8\")\n",
    "\n",
    "stopwords = []\n",
    "for line in f:\n",
    "    stopwords.append(line.strip())\n",
    "    \n",
    "f.close()\n",
    "\n",
    "print(stopwords[:20])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We collect all unique words and for each document we will count how many times each word is present."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "file_name = \"titles.txt\"\n",
    "f = open(file_name, \"r\", encoding=\"utf-8\")\n",
    "\n",
    "documents = []\n",
    "doc_id = 1\n",
    "all_words = {}\n",
    "\n",
    "# transfer content of a file into a list of lines\n",
    "lines = [line for line in f]\n",
    "\n",
    "# create a dictionary of all words and their total counts\n",
    "for line in lines:\n",
    "    doc_words = get_words(line)\n",
    "    for w in doc_words :\n",
    "        if w not in stopwords:\n",
    "            all_words[w] = all_words.get(w,0)+1\n",
    "\n",
    "unique_words = set()\n",
    "for w, count in all_words.items():\n",
    "    if all_words[w] > 1 :\n",
    "        unique_words.add(w)\n",
    "\n",
    "# create a matrix of word presence in each document\n",
    "for line in lines:\n",
    "    documents.append([\"d\"+str(doc_id), get_word_counts(line,unique_words)])\n",
    "    doc_id += 1\n",
    "\n",
    "unique_words=list(unique_words)\n",
    "print(\"All unique words:\",unique_words)\n",
    "print(documents)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we want to convert each document into a numeric vector:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "out = open(file_name.split('.')[0] + \"_vectors.txt\", \"w\")\n",
    "\n",
    "# write a header which contains the words themselves\n",
    "for w in unique_words:\n",
    "    out.write('\\t' + w)\n",
    "out.write('\\n')\n",
    "\n",
    "# print_word_matrix to file\n",
    "for i in range(len(documents)):\n",
    "    vector = get_word_vector(unique_words, documents[i][1])\n",
    "    out.write(documents[i][0])\n",
    "    for x in vector:\n",
    "        out.write('\\t' + str(x))\n",
    "    out.write('\\n')\n",
    "out.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our data now looks like this matrix:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "doc_vectors_file = \"titles_vectors.txt\"\n",
    "f = open(doc_vectors_file, \"r\", encoding=\"utf-8\")\n",
    "s = f.read()\n",
    "print(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function will read document vectors file and produce 2D data matrix, \n",
    "# plus the names of the rows and the names of the columns.\n",
    "def read_vector_file(file_name):\n",
    "    f = open(file_name)\n",
    "    lines=[line for line in f]\n",
    "  \n",
    "    # First line is the column headers\n",
    "    colnames=lines[0].strip().split('\\t')[:]\n",
    "    # print(colnames)\n",
    "    rownames=[]\n",
    "    data=[]\n",
    "    for line in lines[1:]:\n",
    "        p=line.strip().split('\\t')\n",
    "        # First column in each row is the rowname\n",
    "        if len(p)>1:\n",
    "            rownames.append(p[0])\n",
    "            # The data for this row is the remainder of the row\n",
    "            data.append([float(x) for x in p[1:]])\n",
    "    return rownames,colnames,data\n",
    "\n",
    "\n",
    "# This function will transpose the data matrix\n",
    "def rotatematrix(data):\n",
    "    newdata=[]\n",
    "    for i in range(len(data[0])):\n",
    "        newrow=[data[j][i] for j in range(len(data))]\n",
    "        newdata.append(newrow)\n",
    "    return newdata"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As the result of all this, we have the matrix where the rows are document vectors.\n",
    "Each vector dimension represents a unique word in the collection.\n",
    "The value in each dimension represents the count of this word in a particular document."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2. Clustering documents \n",
    "\n",
    "Performing k-means clustering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "doc_vectors_file = \"titles_vectors.txt\"\n",
    "docs,words,data=read_vector_file(doc_vectors_file)\n",
    "\n",
    "num_clusters=2\n",
    "print('Searching for {} clusters:'.format(num_clusters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clust=kcluster(data,distance=pearson,k=num_clusters)\n",
    "print()\n",
    "\n",
    "print ('Document clusters')\n",
    "print ('=================')\n",
    "for i in range(num_clusters):\n",
    "    print ('cluster {}:'.format(i+1))\n",
    "    print ([docs[r] for r in clust[i]])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Does this grouping make sense?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for d in documents:\n",
    "    print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3. Clustering words by their occurrence in documents\n",
    "We 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.\n",
    "If we want to cluster words by their occurrences in the documents, all we need to do is to transpose the document matrix."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rdata=rotatematrix(data)\n",
    "num_clusters = 3\n",
    "print ('Grouping words into {} clusters:'.format(num_clusters))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clust=kcluster(rdata,distance=cosine,k=num_clusters)\n",
    "print()\n",
    "print ('word clusters:')\n",
    "print(\"=============\")\n",
    "for i in range(num_clusters):\n",
    "    print(\"cluster {}\".format(i+1))\n",
    "    print ([words[r] for r in clust[i]])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Copyright &copy; 2022 Marina Barsky. All rights reserved."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}