<jupyter_start><jupyter_text>Implementation of DBSCAN using a K-D-Tree to improve performance<jupyter_code># imports 
import numpy as np
import pandas as pd
from collections import defaultdict
from sklearn.neighbors import KDTree
from collections import deque

from sklearn import datasets
iris = datasets.load_iris()
class DBSCAN:
    
    def __init__(self, points, max_dist, min_points):
        
        self.points = points
        self.max_dist = max_dist
        self.min_points = min_points + 1
        self.tree = KDTree(points)
        self.lookup = defaultdict(lambda:None)
    
    # iterate through points, when it has a label continue, otherwise query for neighbours, if it is core start expanding the cluster, 
    # when cluster is done increase label counter by one
    
    def range_query(self,point):
        
        index, = self.tree.query_radius([point], self.max_dist)
        
        return self.points[index]
           
    def fit(self):
        
        label = 0
        
        for point in self.points:
            
            # if point already has a label continue
            if self.lookup[tuple(point)] != None:
                
                continue
                
            # count neighbors
            neighbors = self.range_query(point) 
            
            # if point has less than min_points as neighbors classify as noise
            if len(neighbors) < self.min_points:
                
                self.lookup[tuple(point)] = -1
                
            # otherwise point is core and the cluster needs to be expanded from there
            else:
                
                # set label
                self.lookup[tuple(point)] = label
                
                # add all neighbors to a queue, the cluster will be expanded using bft
                queue = deque()
                
                for neighbor in neighbors:
                    
                    queue.appendleft(neighbor)
                
                while len(queue) > 0:
                    
                    next_point = queue.pop()
                    
                    # if next point was marked as noise it is now part of a cluster but not a core
                    if self.lookup[tuple(next_point)] == -1:
                        
                        self.lookup[tuple(next_point)] = label
                        continue
                    
                    # if point already has a label it was already assigned a cluster
                    if self.lookup[tuple(next_point)] is not None:
                        
                        continue
                    
                    # if next point had no label it gets assigned to the current cluster
                    self.lookup[tuple(next_point)] = label
                    
                    # now we need to check if next point is core too
                    next_neighbors = self.range_query(next_point) 
                    
                    # if next point is not core nothing else needs to be done
                    if len(next_neighbors) < self.min_points:
                        
                        continue
                    
                    # otherwise all neighbors of next core need to be checked too
                    else:
                        
                        for next_neighbor in next_neighbors:
                            
                            queue.appendleft(next_neighbor)
                            
                # when cluster is expanded to its limits increase label by 1
                label += 1
                            
test = DBSCAN(iris.data, 0.5, 5)
test.fit()
test.lookup<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.04938271604938271, 'fraction_numerical': 0.0026838432635534087, 'mean_word_length': 1.1444188722669735, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 6, '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': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '363014', 'license': 'MIT', 'n_tokens_mistral': 884, 'n_tokens_neox': 826, 'n_words': 295, 'path': 'DBSCAN.ipynb', 'repo_name': 'RobinSrimal/CS-Buildweek1', 'size': '3726'}