<jupyter_start><jupyter_text>Clustering using Box Graph<jupyter_code>import sys
import os
import time
import math

from point import ClusterPoint as CP
from boxgraph import BoxGraph
from box import Box
from visualisations import *
import numpy as np
import matplotlib.pyplot as plt

from sklearn import cluster, datasets<jupyter_output><empty_output><jupyter_text>Below is the implementation of Box-Graph to cluster the data points.<jupyter_code>def find_core_points(bg):
    """
    Find the core points
    """

    for box in bg.boxes:
        if len(box.points) >= bg.min_pts:
            box.func = Box.Func.CORE
            for point in box.points:
                point.func = CP.Func.CORE
            
        else:
            for point in box.points:
                count = len(box.points)
                
                for neighbour in box.neighbours:
                    for nb_point in neighbour.points:
                        if nb_point.sq_distance_to(point) <= bg.eps_sqr:
                            count += 1
                            
                if count >= bg.min_pts:
                    box.func = Box.Func.CORE
                    point.func = CP.Func.CORE
                    neighbour.func = Box.Func.PARTIAL
 def compute_cluster_cores(bg):
    """
    Compute the cluster cores    
    """
    
    nr_clusters = -1
    label = 0
    
    for box in bg.boxes:
        if not box.is_labeled() and box.func == Box.Func.CORE:
            label += 1
            box.label = label
            front = [box]
            
            while len(front) > 0:
                current_box = front.pop(0)
                
                for point in current_box.points:
                    if point.func == CP.Func.CORE:
                        point.cluster_label = label
                        
                for neighbour in current_box.neighbours:
                    if not neighbour.is_labeled() and neighbour.func is not Box.Func.NONE:
                        if current_box.is_core_neighbour(neighbour, bg.eps):
                            neighbour.label = label
                            front.append(neighbour)
                            
    nr_clusters = label
    
    return nr_clusters
def assign_border_points(bg):
    """
    Assign border points to clusters
    """

    for box in bg.boxes:
        for point in box.points:
            if not point.is_labeled():
                nearest = None
                distance = math.inf
                
                for other_point in box.points:
                    if other_point.sq_distance_to(point) <= distance and other_point.is_labeled():
                        nearest = other_point
                        distance = other_point.sq_distance_to(point)
                    
                for neighbour in box.neighbours:
                    for other_point in neighbour.points:
                        if other_point.sq_distance_to(point) <= distance and other_point.is_labeled():
                            nearest = other_point
                            distance = other_point.sq_distance_to(point)
                            
                if distance <= bg.eps_sqr:
                    point.cluster_label = nearest.cluster_label
                    point.func = CP.Func.BORDER<jupyter_output><empty_output><jupyter_text>Experiment with different datasets<jupyter_code>init_times = []
total_times = []
from sklearn.datasets import make_blobs

n_samples = 20000

X, y = make_blobs(n_samples=n_samples, 
                  n_features=2, 
                  centers=4,
                  cluster_std=0.5,
                  random_state=1000)

fig=plt.figure(figsize=(8,8), dpi=80, facecolor='w', edgecolor='k')
plt.scatter(X[:, 0], X[:, 1]);
n_samples = 20000

X, y = make_blobs(n_samples=n_samples, 
                  n_features=2, 
                  centers=3,
                  cluster_std=0.4,
                  random_state=1000)
transformation = [[0.8, -0.8], [-0.4, 0.8]]
X = np.dot(X, transformation)
aniso = (X, y)

fig=plt.figure(figsize=(8,8), dpi=80, facecolor='w', edgecolor='k')
plt.scatter(X[:, 0], X[:, 1]);
from sklearn.datasets import make_circles

n_samples = 20000

X, y = make_circles(n_samples=n_samples, 
                    factor=0.3,
                    noise=0.03,
                    random_state=1000)

fig=plt.figure(figsize=(8,8), dpi=80, facecolor='w', edgecolor='k')
plt.scatter(X[:, 0], X[:, 1]);
from sklearn.datasets import make_moons

n_samples = 20000

X, y = make_moons(n_samples=n_samples,
                  noise=0.01,
                  random_state=1000)

fig=plt.figure(figsize=(8,8), dpi=80, facecolor='w', edgecolor='k')
plt.scatter(X[:, 0], X[:, 1]);
start = time.time()

# Read file and create box graph
coords = X.tolist()
points = [CP(2, coord) for coord in coords]

bg = BoxGraph(n=n_samples, d=2, epsilon=0.4, min_pts=4, points=points)

init = time.time()

# Compute the core points
find_core_points(bg)

# Cluster the core points
nr_clusters = compute_cluster_cores(bg)

# Assign border points to clusters
assign_border_points(bg)

end = time.time()
init_time = init - start
total_time = end - start
print(init_time, total_time)
init_times.append(init_time)
total_times.append(total_time)
init_times
total_times
label = [point.cluster_label for point in bg.points]
fig=plt.figure(figsize=(8,8), dpi=80, facecolor='w', edgecolor='k')
plt.scatter(X[:, 0], X[:, 1], c=label);
#plt.savefig('moon_cluster.png');<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09941839331152308, 'fraction_numerical': 0.018356961105052708, 'mean_word_length': 1.8527734577501296, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 16, '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}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '662626', 'license': 'MIT', 'n_tokens_mistral': 1756, 'n_tokens_neox': 1645, 'n_words': 385, 'path': 'box-graph/Clustering using Box Graph.ipynb', 'repo_name': 'Linh181/Density-based-Clustering', 'size': '5502'}