<jupyter_start><jupyter_text>IntroductionThis notebook implements test some neearest neighbor algorithms. Brutal Force<jupyter_code>class brutal_force_nearest_neighbor:
    def __init__(self, data_lst):
        self.data_lst = data_lst
        
    def reset_datalst(self, data_lst):
        self.data_lst = data_lst
        
    def find_top_k(self, x, k = 5):
        dist_lst = [[np.linalg.norm(x - ele), idx] \
                for idx, ele in enumerate(self.data_lst)]
        dist_lst.sort()
        return [self.data_lst[i] for i in \
                [idx for dist, idx in dist_lst[:k]]]    
raw_data = np.random.normal(size = (10000, 3))
bf_nn = brutal_force_nearest_neighbor(raw_data)
bf_nn.find_top_k(np.zeros(3))<jupyter_output><empty_output><jupyter_text>Smarter Brutal Force with Heap<jupyter_code>class heap_nearest_neighbor:
    def __init__(self, data_lst):
        self.data_lst = data_lst
        
    def reset_datalst(self, data_lst):
        self.data_lst = data_lst
        
    def find_top_k(self, x, k = 5):
        
        dist_lst = [[np.linalg.norm(x - ele), idx] \
                for idx, ele in enumerate(self.data_lst)]
        
        return [self.data_lst[i] for i in \
                [idx for dist, idx in heapq.nsmallest(k, dist_lst)]]    
h_nn = heap_nearest_neighbor(raw_data)
h_nn.find_top_k(np.zeros(3))<jupyter_output><empty_output><jupyter_text>K-d Tree<jupyter_code>from scipy.spatial import KDTree
class kdtree_nearest_neighbor:
    def __init__(self, data_lst):
        self.kdtree = KDTree(data_lst)
        
    def reset_datalst(self, data_lst):
        self.kdtree = KDTree(data_lst)
        
    def find_top_k(self, x, k = 5):
        dist, indices = self.kdtree.query(x, k) 
        return [self.kdtree.data[i] for i in indices]
kdt_nn = kdtree_nearest_neighbor(raw_data)
kdt_nn.find_top_k(np.zeros(3))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10551431601272535, 'fraction_numerical': 0.006362672322375398, 'mean_word_length': 2.9559748427672954, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, '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': '533520', 'license': 'MIT', 'n_tokens_mistral': 724, 'n_tokens_neox': 705, 'n_words': 132, 'path': 'Data-structure/.ipynb_checkpoints/Nearest Neighbor Algorithm Comparison-checkpoint.ipynb', 'repo_name': 'xiaozhi-alan-zhu/ML-practice-repo', 'size': '1886'}