432_PCI_Ch03.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "432-PCI-Ch03.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true,
      "authorship_tag": "ABX9TyOqG8QuvyJnEHM/ZbfBS4TW",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/cs432-websci-master/public/blob/main/432_PCI_Ch03.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "UPcUF4Cwfr9O"
      },
      "source": [
        "## Source from Ch 3, PCI\n",
        "https://github.com/arthur-e/Programming-Collective-Intelligence/blob/master/chapter3/clusters.py"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yVyt9hyGYDS"
      },
      "source": [
        "### General functions\n",
        "* required imports\n",
        "* `readfile(filename)` - returns arrays of rownames, colnames, data\n",
        "* `pearson(v1, v2)` - returns Pearson correlation between two vectors of numbers\n",
        "* `rotatematrix(data)` - returns rotated matrix (rows become columns and columns become rows)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Lux6h3A_epkT"
      },
      "source": [
        "from PIL import Image, ImageDraw\n",
        "from math import sqrt\n",
        "import random\n",
        "import csv"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AhuQ_N1xerDJ"
      },
      "source": [
        "def readfile(filename):\n",
        "  # This is a function that I wrote from scratch   -MCW\n",
        "  data = []\n",
        "  rownames = []\n",
        "  colnames = []\n",
        "  num_rows = 0\n",
        "  with open(filename) as tsvfile:\n",
        "    reader = csv.reader(tsvfile, delimiter='\\t')\n",
        "    for row in reader:\n",
        "      if num_rows > 0:\n",
        "        rownames.append(row[0])    # save the row names\n",
        "        data.append([float(x) for x in row[1:]])  # save the values as floats\n",
        "      else:\n",
        "        for col in row[1:]:\n",
        "          colnames.append(col)    # save the column names\n",
        "      num_rows = num_rows + 1\n",
        "  return (rownames, colnames, data)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ztJtGeeWetY3"
      },
      "source": [
        "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(len(v1))])\n",
        "\n",
        "  # Calculate r (Pearson score)\n",
        "    num = pSum - sum1 * sum2 / len(v1)\n",
        "    den = sqrt((sum1Sq - pow(sum1, 2) / len(v1)) * (sum2Sq - pow(sum2, 2)\n",
        "               / len(v1)))\n",
        "    if den == 0:\n",
        "        return 0\n",
        "\n",
        "    return 1.0 - num / den"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "boq1M_Y2fHid"
      },
      "source": [
        "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"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "TJs3_RMqG57z"
      },
      "source": [
        "### Hierarchical Clustering\n",
        "\n",
        "* class `bicluster` - data structure to hold the clustering information\n",
        "* `hcluster(rows, distance=pearson)` - does the hierarchical clustering, default distance function is pearson()\n",
        "* `printclust(clust, labels=None, n=0)` -  traverses the cluster and prints an ASCII text representation"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "upTWwSumevbe"
      },
      "source": [
        "class bicluster:\n",
        "\n",
        "    def __init__(self, vec, left=None, right=None, distance=0.0, id=None,):\n",
        "        self.left = left\n",
        "        self.right = right\n",
        "        self.vec = vec\n",
        "        self.id = id\n",
        "        self.distance = distance"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-2DxU45Wew67"
      },
      "source": [
        "def hcluster(rows, distance=pearson):\n",
        "    distances = {}\n",
        "    currentclustid = -1\n",
        "\n",
        "  # Clusters are initially just the rows\n",
        "    clust = [bicluster(rows[i], id=i) for i in range(len(rows))]\n",
        "\n",
        "    while len(clust) > 1:\n",
        "        lowestpair = (0, 1)\n",
        "        closest = distance(clust[0].vec, clust[1].vec)\n",
        "\n",
        "    # loop through every pair looking for the smallest distance\n",
        "        for i in range(len(clust)):\n",
        "            for j in range(i + 1, len(clust)):\n",
        "        # distances is the cache of distance calculations\n",
        "                if (clust[i].id, clust[j].id) not in distances:\n",
        "                    distances[(clust[i].id, clust[j].id)] = \\\n",
        "                        distance(clust[i].vec, clust[j].vec)\n",
        "\n",
        "                d = distances[(clust[i].id, clust[j].id)]\n",
        "\n",
        "                if d < closest:\n",
        "                    closest = d\n",
        "                    lowestpair = (i, j)\n",
        "\n",
        "    # calculate the average of the two clusters\n",
        "        mergevec = [(clust[lowestpair[0]].vec[i] + clust[lowestpair[1]].vec[i])\n",
        "                    / 2.0 for i in range(len(clust[0].vec))]\n",
        "\n",
        "    # create the new cluster\n",
        "        newcluster = bicluster(mergevec, left=clust[lowestpair[0]],\n",
        "                               right=clust[lowestpair[1]], distance=closest,\n",
        "                               id=currentclustid)\n",
        "\n",
        "    # cluster ids that weren't in the original set are negative\n",
        "        currentclustid -= 1\n",
        "        del clust[lowestpair[1]]\n",
        "        del clust[lowestpair[0]]\n",
        "        clust.append(newcluster)\n",
        "\n",
        "    return clust[0]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aiLuXIoXe7Nh"
      },
      "source": [
        "def printclust(clust, labels=None, n=0):\n",
        "  # indent to make a hierarchy layout\n",
        "    for i in range(n):\n",
        "        print (' ', end =\" \")\n",
        "    if clust.id < 0:\n",
        "    # negative id means that this is branch\n",
        "        print ('-')\n",
        "    else:\n",
        "    # positive id means that this is an endpoint\n",
        "        if labels == None:\n",
        "            print (clust.id)\n",
        "        else:\n",
        "            print (labels[clust.id])\n",
        "\n",
        "  # now print the right and left branches\n",
        "    if clust.left != None:\n",
        "        printclust(clust.left, labels=labels, n=n + 1)\n",
        "    if clust.right != None:\n",
        "        printclust(clust.right, labels=labels, n=n + 1)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8VzgMCrBG_Wt"
      },
      "source": [
        "### Dendrogram"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6dCTaXFle87P"
      },
      "source": [
        "def getheight(clust):\n",
        "  # Is this an endpoint? Then the height is just 1\n",
        "    if clust.left == None and clust.right == None:\n",
        "        return 1\n",
        "\n",
        "  # Otherwise the height is the same of the heights of\n",
        "  # each branch\n",
        "    return getheight(clust.left) + getheight(clust.right)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mW_38VKxe-oA"
      },
      "source": [
        "def getdepth(clust):\n",
        "  # The distance of an endpoint is 0.0\n",
        "    if clust.left == None and clust.right == None:\n",
        "        return 0\n",
        "\n",
        "  # The distance of a branch is the greater of its two sides\n",
        "  # plus its own distance\n",
        "    return max(getdepth(clust.left), getdepth(clust.right)) + clust.distance"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Urzd-sgOfA6d"
      },
      "source": [
        "def drawdendrogram(clust, labels, jpeg='clusters.jpg'):\n",
        "  # height and width\n",
        "    h = getheight(clust) * 20\n",
        "    w = 1200\n",
        "    depth = getdepth(clust)\n",
        "\n",
        "  # width is fixed, so scale distances accordingly\n",
        "    scaling = float(w - 150) / depth\n",
        "\n",
        "  # Create a new image with a white background\n",
        "    img = Image.new('RGB', (w, h), (255, 255, 255))\n",
        "    draw = ImageDraw.Draw(img)\n",
        "\n",
        "    draw.line((0, h / 2, 10, h / 2), fill=(255, 0, 0))\n",
        "\n",
        "  # Draw the first node\n",
        "    drawnode(\n",
        "        draw,\n",
        "        clust,\n",
        "        10,\n",
        "        h / 2,\n",
        "        scaling,\n",
        "        labels,\n",
        "        )\n",
        "    img.save(jpeg, 'JPEG')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "xYrCsE2tfCG-"
      },
      "source": [
        "def drawnode(\n",
        "    draw,\n",
        "    clust,\n",
        "    x,\n",
        "    y,\n",
        "    scaling,\n",
        "    labels,\n",
        "    ):\n",
        "    if clust.id < 0:\n",
        "        h1 = getheight(clust.left) * 20\n",
        "        h2 = getheight(clust.right) * 20\n",
        "        top = y - (h1 + h2) / 2\n",
        "        bottom = y + (h1 + h2) / 2\n",
        "    # Line length\n",
        "        ll = clust.distance * scaling\n",
        "    # Vertical line from this cluster to children\n",
        "        draw.line((x, top + h1 / 2, x, bottom - h2 / 2), fill=(255, 0, 0))\n",
        "\n",
        "    # Horizontal line to left item\n",
        "        draw.line((x, top + h1 / 2, x + ll, top + h1 / 2), fill=(255, 0, 0))\n",
        "\n",
        "    # Horizontal line to right item\n",
        "        draw.line((x, bottom - h2 / 2, x + ll, bottom - h2 / 2), fill=(255, 0,\n",
        "                  0))\n",
        "\n",
        "    # Call the function to draw the left and right nodes\n",
        "        drawnode(\n",
        "            draw,\n",
        "            clust.left,\n",
        "            x + ll,\n",
        "            top + h1 / 2,\n",
        "            scaling,\n",
        "            labels,\n",
        "            )\n",
        "        drawnode(\n",
        "            draw,\n",
        "            clust.right,\n",
        "            x + ll,\n",
        "            bottom - h2 / 2,\n",
        "            scaling,\n",
        "            labels,\n",
        "            )\n",
        "    else:\n",
        "    # If this is an endpoint, draw the item label\n",
        "        draw.text((x + 5, y - 7), labels[clust.id], (0, 0, 0))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ownwQTBOHCFp"
      },
      "source": [
        "### k-Means Clustering"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ywMrcsBAfKn0"
      },
      "source": [
        "def kcluster(rows, distance=pearson, 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",
        "    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):\n",
        "                    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:\n",
        "            break\n",
        "        lastmatches = bestmatches\n",
        "\n",
        "    # Move the centroids to the average of their 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"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HZqYK3B8HUNZ"
      },
      "source": [
        "### Multidimensional Scaling\n",
        "* `scaledown(data, distance=pearson, rate=0.01)` - performs the MDS algorithm, returns a vector with the x,y coordinates of each item, learning rate (how much to move items) is default 0.01\n",
        "* `draw2d(data, labels, jpeg=\"mds2d.jpg\")` - function to display the labels in 2d space"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "0ijgjc45fPRO"
      },
      "source": [
        "def scaledown(data, distance=pearson, rate=0.01):\n",
        "    n = len(data)\n",
        "\n",
        "  # The real distances between every pair of items\n",
        "    realdist = [[distance(data[i], data[j]) for j in range(n)] for i in\n",
        "                range(0, n)]\n",
        "\n",
        "  # Randomly initialize the starting points of the locations in 2D\n",
        "    loc = [[random.random(), random.random()] for i in range(n)]\n",
        "    fakedist = [[0.0 for j in range(n)] for i in range(n)]\n",
        "\n",
        "    lasterror = None\n",
        "    for m in range(0, 1000):\n",
        "    # Find projected distances\n",
        "        for i in range(n):\n",
        "            for j in range(n):\n",
        "                fakedist[i][j] = sqrt(sum([pow(loc[i][x] - loc[j][x], 2)\n",
        "                                      for x in range(len(loc[i]))]))\n",
        "\n",
        "    # Move points\n",
        "        grad = [[0.0, 0.0] for i in range(n)]\n",
        "\n",
        "        totalerror = 0\n",
        "        for k in range(n):\n",
        "            for j in range(n):\n",
        "                if j == k:\n",
        "                    continue\n",
        "        # The error is percent difference between the distances\n",
        "                errorterm = (fakedist[j][k] - realdist[j][k]) / realdist[j][k]\n",
        "\n",
        "        # Each point needs to be moved away from or towards the other\n",
        "        # point in proportion to how much error it has\n",
        "                grad[k][0] += (loc[k][0] - loc[j][0]) / fakedist[j][k] \\\n",
        "                    * errorterm\n",
        "                grad[k][1] += (loc[k][1] - loc[j][1]) / fakedist[j][k] \\\n",
        "                    * errorterm\n",
        "\n",
        "        # Keep track of the total error\n",
        "                totalerror += abs(errorterm)\n",
        "        print (totalerror)\n",
        "\n",
        "    # If the answer got worse by moving the points, we are done\n",
        "        if lasterror and lasterror < totalerror:\n",
        "            break\n",
        "        lasterror = totalerror\n",
        "\n",
        "    # Move each of the points by the learning rate times the gradient\n",
        "        for k in range(n):\n",
        "            loc[k][0] -= rate * grad[k][0]\n",
        "            loc[k][1] -= rate * grad[k][1]\n",
        "\n",
        "    return loc"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Ir7DFTArejCy"
      },
      "source": [
        "def draw2d(data, labels, jpeg='mds2d.jpg'):\n",
        "    img = Image.new('RGB', (2000, 2000), (255, 255, 255))\n",
        "    draw = ImageDraw.Draw(img)\n",
        "    for i in range(len(data)):\n",
        "        x = (data[i][0] + 0.5) * 1000\n",
        "        y = (data[i][1] + 0.5) * 1000\n",
        "        draw.text((x, y), labels[i], (0, 0, 0))\n",
        "    img.save(jpeg, 'JPEG')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GmAsQZ94fziR"
      },
      "source": [
        "## Examples"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "edXfVRopkpfW"
      },
      "source": [
        "### Hierarchical Clustering and Dendrogram\n",
        "\n",
        "pg. 37 - read in file, generate hierarchical clusters\n",
        "\n",
        "**Note:** Before running this, must load blogdata.txt (or whatever file used) locally.  In Google Colab, click the folder icon in the sidebar to upload a file.  (Download blogdata.txt from https://raw.githubusercontent.com/arthur-e/Programming-Collective-Intelligence/master/chapter3/blogdata.txt)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JfkbVJJsf1Pn"
      },
      "source": [
        "blognames, words, data = readfile(\"blogdata.txt\")"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AcTTgL1GbwXG"
      },
      "source": [
        "blognames[:5]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4O8faj38bzVE"
      },
      "source": [
        "words[:5]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "MYGkrXjAb11n"
      },
      "source": [
        "data[2][:5]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UAk3cTleg7jC"
      },
      "source": [
        "clust = hcluster(data)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "b-PSBNxkb8SG"
      },
      "source": [
        "clust"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PfuA57B3b_ay"
      },
      "source": [
        "clust.id"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Gk38nxZKieYn"
      },
      "source": [
        "clust.left"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qtBXEi0DcFPa"
      },
      "source": [
        "clust.vec"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bmS1cpI_hcox"
      },
      "source": [
        "printclust(clust, labels=blognames)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "k1PffPLsiQE4"
      },
      "source": [
        "pg. 40 - draw the dendrogram and save as jpg\n",
        "\n",
        "**Note:** In Google Colab, this file will be generated locally, so click the folder icon in the sidebar to view the generated file.  You may need to click Refresh if the file doesn't appear."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IJflP5VBiSXw"
      },
      "source": [
        "drawdendrogram(clust, blognames, jpeg='blogclust.jpg')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Lf6LP4LSip55"
      },
      "source": [
        "pg. 40 - rotate and draw dendrogram with term labels, save as jpg"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "peymQ5ODivEy"
      },
      "source": [
        "rdata = rotatematrix(data)\n",
        "wordclust = hcluster(rdata)\n",
        "drawdendrogram(wordclust, labels=words, jpeg='wordclust.jpg')"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lb2mBExkjbos"
      },
      "source": [
        "### k-Means\n",
        "pg. 44 - kmeans"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lYAiJtEJjckO"
      },
      "source": [
        "kclust = kcluster(data, k=10)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "V6Y9u0nxoN4E"
      },
      "source": [
        "kclust[0]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-qs86YcSj2Yk"
      },
      "source": [
        "[blognames[r] for r in kclust[0]]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UiesUVb0j8At"
      },
      "source": [
        "[blognames[r] for r in kclust[1]]"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1Xm1ROHbwb7J"
      },
      "source": [
        "for i in range(len(kclust)):\n",
        "  print (\"cluster \", i+1, \": \", len(kclust[i]))"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "MunDTVPFkF4p"
      },
      "source": [
        "### MDS\n",
        "\n",
        "pg. 52 - MDS"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_u-CWzEYkILC"
      },
      "source": [
        "coords = scaledown(data)"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "c4pDDW4OkPU8"
      },
      "source": [
        "draw2d(coords, blognames, jpeg='blogs2d.jpg')"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}