<commit_before>'''
Created : Jan 16, 2017
Last major update : June 29, 2017

@author: <NAME>

    Purpose:
        Fast density clustering
'''

import numpy as np
import time
from numpy.random import random
import sys, os
from .density_estimation import KDE
    
class FDC:

    """ Fast Density Clustering via kernel density modelling 

    Parameters
    ----------

    nh_size : int, optional (default = 40)
        Neighborhood size. This is the scale used for identifying modes in the density distribution.
        If a point has the maximum density among it's nh_size neighbors, it is marked as 
        a potential cluster center.
    
    noise_threshold : float, optional (default = 0.4)
        Used to merge clusters. This is done by quenching directly to the specified noise threshold
        (as opposed to progressively coarse-graining). The noise threshold determines the extended 
        neighborhood of cluster centers. Points that have a relative density difference of less than 
        "noise_threshold" and that are density-reachable, are part of the extended neighborhood.

    random_state: int, optional (default = 0)
        Random number for seeding random number generator. By default, the
        method generates the same results. This random is used to seed
        the cross-validation (set partitions) which will in turn affect the bandwitdth value

    test_ratio_size: float, optional (default = 0.1)
        Ratio size of the test set used when performing maximum likehood estimation.

    verbose: int, optional (default = 1)
        Set to 0 if you don't want to see print to screen.

    bandwidth: float, optional (default = None)
        If you want the bandwidth for kernel density to be set automatically or want to set it yourself.
        By default it is set automatically.
    
    merge: bool, optinal (default = True)
        Optional merging at zero noise threshold, merges overlapping minimal clusters
    
    atol: float, optional (default = 0.000005)
        kernel density estimate precision parameter. determines the precision used for kde.
        smaller values leads to slower execution but better precision
    
    rtol: float, optional (default = 0.00005)
        kernel density estimate precision parameter. determines the precision used for kde.
        smaller values leads to slower execution but better precision
    
    xtol: float, optional (default = 0.01)
        precision parameter for optimizing the bandwidth using maximum likelihood on a test set
    
    search_size int, optional (default = 20)
        when performing search over neighborhoods, size of each local neighborhood to check when
        expanding. This drastically slows the coarse-graining if chosen to be too big !
    """

    def __init__(self, nh_size=40, noise_threshold=0.4,
                random_state=0, test_ratio_size=0.1, verbose=1, bandwidth=None,
                merge=True,
                atol=0.000005,
                rtol=0.00005,
                xtol=0.01,
                search_size = 20
                ):

        self.test_ratio_size = test_ratio_size
        self.random_state = random_state
        self.verbose = verbose
        self.nh_size = nh_size
        self.bandwidth = bandwidth
        self.noise_threshold = noise_threshold
        self.merge=merge
        self.atol = atol
        self.rtol = rtol
        self.xtol = xtol 
        self.cluster_label = None
        self.search_size = search_size

    def fit(self,X):
        """ Performs density clustering on given data set

        Parameters
        ----------

        X : array, (n_sample, n_feature)
            Data to cluster. 

        Returns
        ----------
        self : fdc object
            To obtain new cluster labels use self.cluster_label
        """
        from sklearn.neighbors import NearestNeighbors

        t = time.time()

        self.X = X  # shallow copy

        if self.nh_size < 100 :
            self.nbrs = NearestNeighbors(n_neighbors = 100, algorithm='kd_tree').fit(X)
        else:
            self.nbrs = NearestNeighbors(n_neighbors = self.nh_size, algorithm='kd_tree').fit(X)    

        self.nn_dist, self.nn_list = self.nbrs.kneighbors(X) # this scales like X.shape[0] * self.nh_size 

        if self.verbose == 0:
            blockPrint()

        n_sample = X.shape[0]
        print("[fdc] Starting clustering with n=%i samples..." % n_sample)
        start = time.time()

        print("[fdc] Fitting kernel model for density estimation ...")
        self.density_model = KDE(bandwidth=self.bandwidth, test_ratio_size=self.test_ratio_size,
            atol=self.atol,rtol=self.rtol,xtol=self.xtol, nn_dist = self.nn_dist)

        self.density_model.fit(X)
        self.bandwidth = self.density_model.bandwidth
        
        print("[fdc] Computing density ...")
        self.rho = self.density_model.evaluate_density(X)
        
        print("[fdc] Finding centers ...")
        self.compute_delta(X, self.rho)
        
        print("[fdc] Found %i potential centers ..." % self.idx_centers_unmerged.shape[0])

        # temporary idx for the centers :
        self.idx_centers = self.idx_centers_unmerged
        self.cluster_label = assign_cluster(self.idx_centers_unmerged, self.nn_delta, self.density_graph)

        if self.merge: # usually by default one should perform this minimal merging .. 
            print("[fdc] Merging overlapping minimal clusters ...")
            self.check_cluster_stability_fast(X, 0.) # given 
        
        if self.noise_threshold >= 1e-3 :
            print("[fdc] Iterating merging up to specified noise threshold ...")
            self.check_cluster_stability_fast(X, self.noise_threshold) # merging 'unstable' clusters
        
        print("[fdc] Done in %.3f s" % (time.time()-start))
        
        enablePrint()

        return self
    
    def check_cluster_stability_fast(self, X, noise_threshold = None): # given 
        if self.verbose == 0:
            blockPrint()

        if noise_threshold is None:
            noise_threshold =  self.noise_threshold

        while True: # iterates untill number of cluster does no change ... 

            self.cluster_label = assign_cluster(self.idx_centers_unmerged, self.nn_delta, self.density_graph) # first approximation of assignments 
            self.idx_centers, n_false_pos = check_cluster_stability(self, X, noise_threshold) 
            self.idx_centers_unmerged = self.idx_centers

            if n_false_pos == 0:
                print("      # of stable clusters with noise %.6f : %i" % (noise_threshold, self.idx_centers.shape[0]))
                break
                
        enablePrint()

    def coarse_grain(self, noise_iterable):
        """Started from an initial noise scale, progressively merges clusters.
        If specified, saves the cluster assignments at every level of the coarse graining if specified.

        Parameters
        -----------
        compute_hierarchy : bool
            Specifies if hierarchy should be stored (list of cluster assignments at all steps)
            If True, hierarchy is stores in self.hierarchy
        """
        if self.verbose == 0:
            blockPrint()
        
        print("[fdc] Coarse graining until desired noise threshold ...")

        noise_range = [n for n in noise_iterable]
            
        hierarchy = []
        self.max_noise = -1<commit_msg>fdc coarse_grain updated<commit_after>'''
Created : Jan 16, 2017
Last major update : June 29, 2017

@author: <NAME>

    Purpose:
        Fast density clustering
'''

import numpy as np
import time
from numpy.random import random
import sys, os
from .density_estimation import KDE
    
class FDC:

    """ Fast Density Clustering via kernel density modelling 

    Parameters
    ----------

    nh_size : int, optional (default = 40)
        Neighborhood size. This is the scale used for identifying modes in the density distribution.
        If a point has the maximum density among it's nh_size neighbors, it is marked as 
        a potential cluster center.
    
    noise_threshold : float, optional (default = 0.4)
        Used to merge clusters. This is done by quenching directly to the specified noise threshold
        (as opposed to progressively coarse-graining). The noise threshold determines the extended 
        neighborhood of cluster centers. Points that have a relative density difference of less than 
        "noise_threshold" and that are density-reachable, are part of the extended neighborhood.

    random_state: int, optional (default = 0)
        Random number for seeding random number generator. By default, the
        method generates the same results. This random is used to seed
        the cross-validation (set partitions) which will in turn affect the bandwitdth value

    test_ratio_size: float, optional (default = 0.1)
        Ratio size of the test set used when performing maximum likehood estimation.

    verbose: int, optional (default = 1)
        Set to 0 if you don't want to see print to screen.

    bandwidth: float, optional (default = None)
        If you want the bandwidth for kernel density to be set automatically or want to set it yourself.
        By default it is set automatically.
    
    merge: bool, optinal (default = True)
        Optional merging at zero noise threshold, merges overlapping minimal clusters
    
    atol: float, optional (default = 0.000005)
        kernel density estimate precision parameter. determines the precision used for kde.
        smaller values leads to slower execution but better precision
    
    rtol: float, optional (default = 0.00005)
        kernel density estimate precision parameter. determines the precision used for kde.
        smaller values leads to slower execution but better precision
    
    xtol: float, optional (default = 0.01)
        precision parameter for optimizing the bandwidth using maximum likelihood on a test set
    
    search_size int, optional (default = 20)
        when performing search over neighborhoods, size of each local neighborhood to check when
        expanding. This drastically slows the coarse-graining if chosen to be too big !
    """

    def __init__(self, nh_size=40, noise_threshold=0.4,
                random_state=0, test_ratio_size=0.1, verbose=1, bandwidth=None,
                merge=True,
                atol=0.000005,
                rtol=0.00005,
                xtol=0.01,
                search_size = 20
                ):

        self.test_ratio_size = test_ratio_size
        self.random_state = random_state
        self.verbose = verbose
        self.nh_size = nh_size
        self.bandwidth = bandwidth
        self.noise_threshold = noise_threshold
        self.merge=merge
        self.atol = atol
        self.rtol = rtol
        self.xtol = xtol 
        self.cluster_label = None
        self.search_size = search_size

    def fit(self,X):
        """ Performs density clustering on given data set

        Parameters
        ----------

        X : array, (n_sample, n_feature)
            Data to cluster. 

        Returns
        ----------
        self : fdc object
            To obtain new cluster labels use self.cluster_label
        """
        from sklearn.neighbors import NearestNeighbors

        t = time.time()

        self.X = X  # shallow copy

        if self.nh_size < 100 :
            self.nbrs = NearestNeighbors(n_neighbors = 100, algorithm='kd_tree').fit(X)
        else:
            self.nbrs = NearestNeighbors(n_neighbors = self.nh_size, algorithm='kd_tree').fit(X)    

        self.nn_dist, self.nn_list = self.nbrs.kneighbors(X) # this scales like X.shape[0] * self.nh_size 

        if self.verbose == 0:
            blockPrint()

        n_sample = X.shape[0]
        print("[fdc] Starting clustering with n=%i samples..." % n_sample)
        start = time.time()

        print("[fdc] Fitting kernel model for density estimation ...")
        self.density_model = KDE(bandwidth=self.bandwidth, test_ratio_size=self.test_ratio_size,
            atol=self.atol,rtol=self.rtol,xtol=self.xtol, nn_dist = self.nn_dist)

        self.density_model.fit(X)
        self.bandwidth = self.density_model.bandwidth
        
        print("[fdc] Computing density ...")
        self.rho = self.density_model.evaluate_density(X)
        
        print("[fdc] Finding centers ...")
        self.compute_delta(X, self.rho)
        
        print("[fdc] Found %i potential centers ..." % self.idx_centers_unmerged.shape[0])

        # temporary idx for the centers :
        self.idx_centers = self.idx_centers_unmerged
        self.cluster_label = assign_cluster(self.idx_centers_unmerged, self.nn_delta, self.density_graph)

        if self.merge: # usually by default one should perform this minimal merging .. 
            print("[fdc] Merging overlapping minimal clusters ...")
            self.check_cluster_stability_fast(X, 0.) # given 
        
        if self.noise_threshold >= 1e-3 :
            print("[fdc] Iterating merging up to specified noise threshold ...")
            self.check_cluster_stability_fast(X, self.noise_threshold) # merging 'unstable' clusters
        
        print("[fdc] Done in %.3f s" % (time.time()-start))
        
        enablePrint()

        return self
    
    def check_cluster_stability_fast(self, X, noise_threshold = None): # given 
        if self.verbose == 0:
            blockPrint()

        if noise_threshold is None:
            noise_threshold =  self.noise_threshold

        while True: # iterates untill number of cluster does no change ... 

            self.cluster_label = assign_cluster(self.idx_centers_unmerged, self.nn_delta, self.density_graph) # first approximation of assignments 
            self.idx_centers, n_false_pos = check_cluster_stability(self, X, noise_threshold) 
            self.idx_centers_unmerged = self.idx_centers

            if n_false_pos == 0:
                print("      # of stable clusters with noise %.6f : %i" % (noise_threshold, self.idx_centers.shape[0]))
                break
                
        enablePrint()

    def coarse_grain(self, noise_iterable):
        """Started from an initial noise scale, progressively merges clusters.
        If specified, saves the cluster assignments at every level of the coarse graining if specified.

        Parameters
        -----------
        noise_iterable : iterable of floats
            Should be an iterable containg noise values at which to perform coarse graining. Usually
            one should start from 0 and go to larger values by small increments. The whole clustering
            information is stored in self.hierarchy
        """
        if self.verbose == 0:
            blockPrint()
        
        print("[fdc] Coarse graining until desired noise threshold ...")

        noise_range = [n for n in noise_iterable]
            
        hierarchy = []
        self.max_noise = -1
{'fraction_non_alphanumeric': 0.07655342721751318, 'fraction_numerical': 0.011412934659280519, 'mean_word_length': 2.2531480677377336, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 7, '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': '6359766', 'n_tokens_mistral': 4255, 'n_tokens_neox': 3909, 'n_words': 1368}