Быстрый способ оценки процентиля массива - PullRequest
Новая
       44

Быстрый способ оценки процентиля массива

0 голосов
/ 24 декабря 2018

Я создал код, который создает случайное двоичное дерево, выполняя случайные проверки каждого доступного узла, пока он не достигнет земли.

Итак, допустим, у нас есть корневой узел, заполненный 500 точками.Мы создадим два пустых дочерних узла (левый и правый), а затем итеративно передадим все точки в random_test(x), что решит, нужно ли передавать точку в левый или правый узел.Каждый узел должен иметь сбалансированное количество баллов (идеальное количество - 250 баллов в обоих узлах, но это необязательно).

См. Следующий код: 

import numpy as np    
def random_test(self, main_point):
        random_coefficients = self.random_coefficients()
        scale_values = [np.inner(self.random_coefficients(), point[:self.indices].ravel())
                                        for point in self.points]
        percentile = np.percentile(scale_values, self.ratio * 100)  # notice here
        main_term = np.inner(main_point[:self.indices].ravel(), random_coefficients)
        if self.is_leaf():
            return 0  # Next node is the center leaf child
        else:
            if (main_term - percentile) >= 0:  # Hyper-plane equation defined in the document
                return -1  # Next node is the left child
            else:
                return 1  # Next node is the right child

def random_coefficients(self):
    return np.random.uniform(size=self.indices)

self.ratio в этом случае равно 0,5, а процентиль составляет 50% от всех точек в узле, умноженных на случайные коэффициенты между [0, 1] (переменная scale_values).

Percentile управляет тем, насколько мелким и сбалансированным является деревобудет, процентиль, близкая к 50%, приведет к оптимально сбалансированному и неглубокому дереву, но это не является обязательным требованием.

np.percentile быстро, но может быть не так быстро, как необходимо.

Есть ли способ быстро оценить процентиль массива так, чтобы он был близок к 1-p и p (где p - процентиль)?Согласно комментариям в этом ответе , существует короткозамкнутый двоичный поиск, который может быть реализован, чтобы найти процентиль, близкий к p (в данном случае 1/2), как это можно реализовать?Есть ли лучший способ?

Спасибо!

...