Exercise 8.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f4c9a966-68e2-42b8-aa4e-0eb5334b5b34",
   "metadata": {},
   "source": [
    "# Assignment 8"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "655e3eca-9edf-4ce3-9da8-1f35ea2b5077",
   "metadata": {},
   "source": [
    "## Assignment 8.1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21478f35-4aab-44b6-8862-bfee99cf9ea4",
   "metadata": {},
   "source": [
    "Compare must-link, cannot-link, and must-link-before constraints in terms of their\n",
    "expressiveness."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e17ffea2-ec5d-471b-a216-971347e78540",
   "metadata": {},
   "source": [
    "Must-link and cannot-link constraints are both binary, symmetric pair-wise limitations imposed on the clustering process. Their expressiveness is very similar with one exception being that must-link constraints are transitive (other data points clustered with one must-link data point must also link to other data point from that must-link) whereas cannot-link constraints aren't (although one useful property is that a cannot-link between two data points establishes the data points linked to one or the other cannot link to their respective clusters). They can be used to extend k-means clustering for example. \n",
    "\n",
    "Must-link-before constraints are useful for a different sort of clustering. It can be used in hierarchical clustering. The idea in hierarchical clustering is that all items will eventually link up, however the order matters. \n",
    "\n",
    "Expressiveness definition from the tutorial: how complex the pattern in the data can be caputured by the constraints. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a462ad7b-1f32-4f9b-9d56-6d025e4ac623",
   "metadata": {},
   "source": [
    "## Assignment 8.2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "aa865f1b-b9d2-4223-a10e-6c5ab0d7282e",
   "metadata": {},
   "source": [
    "Discuss the basic ideas of the COP-k-Means algorithm using the points and constraints\n",
    "of assignment 4.2. Where are the initial cluster centers placed? How are they updated?\n",
    "What are the differences to PCK- and MPCK-Means?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "68b713a6-3949-4868-a816-cf938a6399ee",
   "metadata": {},
   "source": [
    "COP-k-means uses random initialisation, or some more sophisticated method like KMPP to ensure a better spread of the cluster centres, and it coems with initialised constraints. Only hard constraints are possible. \n",
    "\n",
    "PCK-means can also incorporate soft constraints which may be violated. MPCK-means is a metric-based extension of PCK-means wherein a metric (Euclidian distance) is learned. \n",
    "\n",
    "Initialisation of PCK-means relies on neighbourhood sets. If there are 3 clusters, we randomly take 3 neighbourhood sets and place the centroids in their average. \n",
    "\n",
    "A paradoxical early termination of the COP-k-Means can occur with unfortunate initialisation should there be no possible cluster assignment. This cannot occur in PCK-means because of the objective function which allows violations. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c5cb542-2f7e-4989-bfcc-8f3a9f87d0a5",
   "metadata": {},
   "source": [
    "## Assignment 8.3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d7905f6-b88d-4fa9-b779-b7cf7a2b9542",
   "metadata": {},
   "source": [
    "Imagine how must-link and cannot-link constraints can be integrated into the fuzzy cmeans algorithm. How could the target function be adjusted?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a99614a-ae0a-47d1-aca9-8624a9b3c451",
   "metadata": {},
   "source": [
    "The fuzzy c-means algorithm, dispensing with the need for a crisp assignment, could theoretically softly integrated both of these constraints by modifying the loss function such that a larger penalty is incurred if two data points with a cannot-link between them share cluster assignment with the penalty being proportional to the amount of shared assignment. Must-link assignment will similarly add penatly every time they are violated, proportional to the cluster assingment. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cb62d3c7-3abb-440f-82b2-570fcaf86cb6",
   "metadata": {},
   "source": [
    "## Assignment 8.4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b61e3ae-80fc-4457-b8d7-a9d8c9e23fb8",
   "metadata": {},
   "source": [
    "What is the basic idea of constrained hierarchical clustering? Discuss how an hierarchical\n",
    "clustering of webpage bookmarks could be improved by user-defined constraints."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}