<commit_before>{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "\n",
    "def cop_kmeans (dataset, k, ml=None, cl=None):\n",
    "    \n",
    "    clusters_, centers = initialize_clusters(dataset, k)\n",
    "    clusters = None\n",
    "\n",
    "    while not clusters != clusters_:\n",
    "        clusters = clusters_\n",
    "        clusters_ = [-1] * len(dataset)\n",
    "        for i, d in enumerate(dataset):\n",
    "            found_cluster = False\n",
    "            indices = closest_clusters(centers, d)\n",
    "            counter = 0\n",
    "            while (not found_cluster) and counter < len(indices):\n",
    "                index = indices[counter]\n",
    "                if not violate_constraints(i, index, clusters, ml, cl):\n",
    "                    found_cluster = True\n",
    "                    clusters_[i] = index\n",
    "            if not found_cluster:\n",
    "                return None\n",
    "            \n",
    "        centers = compute_centers(clusters_, dataset, k)\n",
    "        converged = test_convergence (clusters, clusters_)\n",
    "\n",
    "        \n",
    "    return clusters, centers\n",
    "\n",
    "def euclidean_distance(point1, point2):\n",
    "    return math.sqrt(sum([(i-j)^2 for (i,j) in zip(point1, point2)]))\n",
    "\n",
    "def closest_clusters(centers, datapoint):\n",
    "    distances = [euclidean_distance(center, datapoint) for \n",
    "                 center in centers]\n",
    "    return sorted(range(len(distances)), key=lambda x: distances[x])\n",
    "\n",
    "# TODO : implement carefully, maybe with a look at Davidson's work\n",
    "def initialize_clusters(dataset, k, ml, cl):\n",
    "    pass\n",
    "\n",
    "def violate_constraints(data_index, cluster_index, clusters, ml, cl):\n",
    "    for (i,j) in ml:\n",
    "        if i == data_index and clusters[j] != cluster_index:\n",
    "            return true\n",
    "        if j == data_index and clusters[i] != cluster_index:\n",
    "            return true\n",
    "    for (i,j) in cl:\n",
    "        if i == data_index and clusters[j] == cluster_index:\n",
    "            return true\n",
    "        if j == data_index and clusters[i] == cluster_index:\n",
    "            return true\n",
    "    return false\n",
    "\n",
    "def compute_centers(clusters, dataset, k=None):\n",
    "    if k == None:\n",
    "        k = max(clusters) + 1\n",
    "    dim = len(dataset[0])\n",
    "    centers = [[]] * k\n",
    "    for i in range(k):\n",
    "        center = [0.0] * dim\n",
    "        count = 1\n",
    "        for j, c in enumerate(clusters):\n",
    "            if c == i:\n",
    "                center += dataset[j]\n",
    "                count += 1\n",
    "        centers[i] = [center[d]/float(count) for d in range(dim)]\n",
    "    return centers\n"
   ]
  }<commit_msg>adding transitive closures and a few more things<commit_after>{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import math\n",
    "\n",
    "def cop_kmeans (dataset, k, ml=[], cl=[]):\n",
    "    \n",
    "    ml, cl = transitive_closure(ml, cl, len(dataset))\n",
    "    \n",
    "    centers = initialize_centers(dataset, k)\n",
    "    clusters_ = []\n",
    "    clusters = None\n",
    "\n",
    "    while not clusters != clusters_:\n",
    "        clusters = clusters_\n",
    "        clusters_ = [-1] * len(dataset)\n",
    "        for i, d in enumerate(dataset):\n",
    "            found_cluster = False\n",
    "            indices = closest_clusters(centers, d)\n",
    "            counter = 0\n",
    "            while (not found_cluster) and counter < len(indices):\n",
    "                index = indices[counter]\n",
    "                if not violate_constraints(i, index, clusters_, ml, cl):\n",
    "                    found_cluster = True\n",
    "                    clusters_[i] = index\n",
    "            if not found_cluster:\n",
    "                return None\n",
    "            \n",
    "        centers = compute_centers(clusters_, dataset, k)\n",
    "\n",
    "        \n",
    "    return clusters, centers\n",
    "\n",
    "def euclidean_distance(point1, point2):\n",
    "    return math.sqrt(sum([(i-j)**2 for (i,j) in zip(point1, point2)]))\n",
    "\n",
    "def closest_clusters(centers, datapoint):\n",
    "    distances = [euclidean_distance(center, datapoint) for \n",
    "                 center in centers]\n",
    "    return sorted(range(len(distances)), key=lambda x: distances[x])\n",
    "\n",
    "# under-specified in the paper\n",
    "def initialize_centers(dataset, k):\n",
    "    ids = range(len(dataset))\n",
    "    random.shuffle(ids)\n",
    "    return [dataset[id] for id in ids[:k]]\n",
    "\n",
    "def violate_constraints(data_index, cluster_index, clusters, ml, cl):\n",
    "    for i in ml[data_index]:\n",
    "        if cluster[i] != -1 and cluster[i] == cluster_index:\n",
    "            return True\n",
    "    \n",
    "    for i in cl[data_index]:\n",
    "        if cluster[i] == cluster_index:\n",
    "            return True\n",
    "\n",
    "    return False\n",
    "\n",
    "def compute_centers(clusters, dataset, k=None):\n",
    "    if k == None:\n",
    "        k = max(clusters) + 1\n",
    "    dim = len(dataset[0])\n",
    "    centers = [[]] * k\n",
    "    for i in range(k):\n",
    "        center = [0.0] * dim\n",
    "        count = 1\n",
    "        for j, c in enumerate(clusters):\n",
    "            if c == i:\n",
    "                center += dataset[j]\n",
    "                count += 1\n",
    "        centers[i] = [center[d]/float(count) for d in range(dim)]\n",
    "    return centers\n",
    "\n",
    "def transitive_closure(ml, cl, n):\n",
    "    def add_to_dict(d, i, j):\n",
    "        if not i in d:\n",
    "            d[i] = set()\n",
    "        d[i].add(j)\n",
    "    \n",
    "    def add_both(d, i, j):\n",
    "        add_to_dict(d, i, j)\n",
    "        add_to_dict(d, j, i)\n",
    "        \n",
    "    ml_graph = dict()\n",
    "    for (i,j) in ml:\n",
    "        add_both(ml_graph, i, j)\n",
    "    \n",
    "    def dfs(i, graph, visited, component):\n",
    "        visited[i] = True\n",
    "        for j in graph[i]:\n",
    "            if not visited[j]:\n",
    "                dfs(j, graph, visited, component)\n",
    "        component.append(i)\n",
    "        \n",
    "    visited = [False] * n\n",
    "    for i in range(n):\n",
    "        if not visited[i]:\n",
    "            component = []\n",
    "            dfs(i, ml_graph, visited, component)\n",
    "            for x1, x2 in zip(component, component):\n",
    "                if x1 != x2:\n",
    "                    add_to_dict(ml_graph, x1, x2)\n",
    "\n",
    "    cl_graph = dict()               \n",
    "    for (i,j) in cl:\n",
    "        add_both(cl_graph, i, j)\n",
    "        for x, y in zip(ml_graph[i], ml_graph[j]):\n",
    "            add_both(cl_graph, x, y)\n",
    "    \n",
    "    return ml_graph, cl_graph"
   ]
  }
{'fraction_non_alphanumeric': 0.18306418781381462, 'fraction_numerical': 0.005021034061609445, 'mean_word_length': 1.6368515205724508, 'pattern_counts': {'":': 14, '<': 5, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3088257', 'n_tokens_mistral': 2642, 'n_tokens_neox': 2603, 'n_words': 558}