Вопрос или проблема
В настоящее время я читаю эту статью о изоляционных лесах. В разделе о функции счета они упоминают следующее. Для справки, $h(x)$ определяется как длина пути точки данных, проходящей через iTree, а $n$ — это размер выборки, используемый для роста iTree.
Сложность в выводе такого счета из $h(x)$ заключается в том, что хотя максимальная возможная высота iTree растет в порядке $n$, средняя высота растет в порядке $log(n)$. Нормализация $h(x)$ с использованием любого из вышеупомянутых терминов либо не ограничена, либо не может быть напрямую сравнена.
Таким образом, здесь возникает мой первый вопрос. Что они имеют в виду, говоря, что нормализация $h(x)$ с использованием любого из вышеупомянутых терминов либо не ограничена, либо не может быть напрямую сравнена? Финальная функция счета в этой статье задается как
$$s(x,n)=2^{-\frac{E(h(x))}{c(n)}}$$
где
$$c(n)=2H_{n-1}-2(n-1)/n$$
это средняя длина пути неудачного поиска из теории BST. Обратите внимание, как они берут математическое ожидание пути. Так что в этом случае мы все равно усредняем все значения, так почему мы не можем использовать рост средней высоты дерева? Кроме того, они даже не упоминают аналитическую форму средней высоты здесь, которая, как я понимаю, составляет $2\sqrt{\pi n}$ ссылка, хотя я не читал эту ссылку тщательно и могу быть неправ.
Я что-то упускаю здесь?
Я не уверен насчет вашего первого вопроса; статья действительно кажется плохо написанной в этой части. Они, похоже, утверждают, что брать просто $E(h(x))/n$ или $E(h(x))/\log n$ неуместно. Первое стремится к нулю независимо от $x$, но второе должно быть разумным. Действительно, поскольку $c(n)\sim 2\log n$, это не очень далеко от того, что они в конечном итоге делают. (Возведение в степень подталкивает счета в диапазон $[0,1]$, что хорошо, и использование более точного $c(n)$ лучше калибрует вещи для “(c) если все экземпляры возвращают $s\approx 0.5$, тогда вся выборка на самом деле не имеет никаких отличительных аномалий.)
Остальная часть путаницы, похоже, возникает из того, над каким множеством мы усредняем. В статье об изоляционном лесу усреднение происходит по глубинам (листа, содержащего) $x$ по нескольким деревьям в изоляционном лесу. В другой ссылке усреднение происходит по высоте всех бинарных деревьев на $n$ узлах.
Ответ или решение
Теория функции оценки в изоляционных лесах (Isolation Forest)
Изоляционные леса представляют собой метод обнаружения аномалий в данных, опирающийся на идею, что аномальные наблюдения легче изолировать, чем нормальные. Ключевым элементом этого метода является использование деревьев решений, известных как iTree (Isolation Tree), для оценки глубины (или длины пути) для каждого наблюдения. В контексте вашей проблемы возникает вопрос о нормализации веса пути (h(x)) и ее аналитическом анализе.
Понимание нормализации h(x)
В контексте изоляционного леса h(x) представляет собой длину пути, по которому проходит наблюдение x в дереве iTree. Важно отметить, что максимальная высота iTree увеличивается пропорционально n (размеру выборки), в то время как средняя высота остается на уровне порядка log(n). Это важная деталь, поскольку она указывает на разницу в росте между теоретическим максимумом и реальным средним значением.
Когда авторы утверждают, что нормализация h(x) по сравнению с n или log(n) "не ограничена" или "не может быть непосредственно сопоставлена", они имеют в виду следующее:
-
Нормализация по n: Если бы мы нормализовали h(x) по n, это значение стало бы стремиться к нулю при увеличении размера выборки, независимо от положения наблюдения x. Это сделает оценку неприемлемой, так как аномалии не будут различимы по результату.
-
Нормализация по log(n): Хотя использование log(n) более оправдано, оно все же может привести к недостаточному различению между наблюдениями, находящимися близко друг к другу. Это, в частности, связано с тем, что в больших наборах данных различия в пути могут быть менее выражены.
Таким образом, авторы выбирают более сложный путь для нормализации, который сочетает элементы теории бинарных деревьев поиска (BST). Параметр c(n) определяется как средняя длина пути с помощью:
$$c(n) = 2H_{n-1} – \frac{2(n-1)}{n}$$
где H обозначает гармоническое число, и таким образом c(n) отражает более точное представление среднего пути.
Рассмотрение E(h(x))
С помощью ожидаемого значения E(h(x)), которое берется по всем деревьям в изоляционном лесе, можно более точно оценить глубину, зависящую от конкретного наблюдения всевозможных выборок. Именно поэтому задача состоит в соединении интуитивных соображений (корректная оценка) и теоретического обоснования (гарантия ограниченности и соразмерности).
Средняя высота дерева
Ваша ссылка на остальные источники и значение средней высоты записываются как (2\sqrt{\pi n}) и правильно упоминаются как результаты, касающиеся всех бинарных деревьев, в то время как в изоляционных лесах используется специфичный подход, который может отличаться по времени.
Заключение
В заключение, нормализация длины пути h(x) в контексте изоляционных лесов требует тщательного анализа и полного понимания теории, стоящей за характеристиками деревьев. Несмотря на наличие подходов к оценке через log(n) или n, важно придерживаться более точных методов, таких как использование c(n), чтобы добиться лучшего обнаружения аномалий и избежать потенциальных ловушек в анализе данных. Акцент на E(h(x)) и его оценке через выборки деревьев обеспечит более точное нахождение аномальных паттернов, чем просто обычная нормализация по размеру выборки.
Понимание этих теоретических аспектов является ключевым для успешного применения алгоритмов обнаружения аномалий, обеспечивая тем самым их эффективность и надежность в практике.