Суррогат файла статический анализ файловой системы (1187430), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Выбор наилучшего из этих признаков можетосуществляться различными способами. В оригинальном коде Бреймана ис­пользуется критерий Гини. В некоторых реализациях алгоритма вместо негоиспользуется критерий прироста информации.3. Дерево строится до полного исчерпания подвыборки.Классификация объектов проводится путём голосования: каждое дерево комитетаотносит классифицируемый объект к одному из классов, и побеждает класс, закоторый проголосовало наибольшее число деревьев.9Достоинства∙ Высокое качество получаемых моделей, сравнимое с SVM и бустингом, илучшее, чем у нейронных сетей [4].∙ Способность эффективно обрабатывать данные с большим числом призна­ков и классов.∙ Нечувствительность к масштабированию (и вообще к любым монотоннымпреобразованиям) значений признаков.∙ Одинаково хорошо обрабатываются как непрерывные, так и дискретные при­знаки.

Существуют методы построения деревьев по данным с пропущенны­ми значениями признаков.∙ Существует методы оценивания значимости отдельных признаков в модели.∙ Внутренняя оценка способности модели к обобщению (тест out-of-bag).∙ Высокая параллелизуемость и масштабируемость.Недостатки∙ Алгоритм склонен к переобучению на некоторых задачах, особенно на за­шумленных задачах [5].∙ Большой размер получающихся моделей. Требуется ( ) памяти для хра­нения модели, где – размер обучающей выборки, – число деревьев.3.3. Градиентный бустингОписаниеБустинг(англ. Boosting) - объединение ансамбля слабых классификаторовс целью получить сильный классификатор и уменьшить смещение.

Здесь сла­10бым классификатором называется классификатор, дающий лишь слегка лучшийрезультат, чем случайное угадывание(его предсказания слабо коррелированы систинным распределением классов). Предсказания же сильного классификаторасильно коррелированы с истинным распределением.Финальный классификатор ищется в виде линейной комбинации классифи­каторов.

Поиск оптимальных значений коэффициентов этой линейной комбина­ции - слишком трудоемкая задача, поэтому в градиентном бустинге используетсяжадный алгоритм постепенного добавления классификаторов.[9]Достоинства∙ Хорошая обобщающая способность. В реальных задачах (не всегда, но ча­сто) удаётся строить композиции, превосходящие по качеству базовые алго­ритмы. Обобщающая способность может улучшаться (в некоторых задачах)по мере увеличения числа базовых алгоритмов.∙ Простота реализации.∙ Собственные накладные расходы бустинга невелики.

Время построения ком­позиции практически полностью определяется временем обучения базовыхалгоритмов.∙ Возможность идентифицировать объекты, являющиеся шумовымивыбросами.[7]∙ Устойчивость к переобучению.Недостатки∙ Жадная стратегия последовательного добавления приводит к построениюнеоптимального набора базовых алгоритмов. Для улучшения композицииможно периодически возвращаться к ранее построенным алгоритмам и обу­чать их заново. Для улучшения коэффициентов можно оптимизировать их11ещё раз по окончании процесса бустинга с помощью какого-нибудь стандарт­ного метода построения линейной разделяющей поверхности.∙ Бустинг может приводить к построению громоздких композиций, состоя­щих из сотен алгоритмов.

Такие композиции исключают возможность со­держательной интерпретации, требуют больших объёмов памяти для хра­нения базовых алгоритмов и существенных затрат времени на вычислениеклассификаций.[7]12Глава 4Результаты4.1. Признаковое описаниеРассматривается решение двуклассовой задачи классификации. Интересую­щий класс - кэш операционной системы или приложений. Здесь и далее:∙ Класс 1 - кэш∙ Класс 2 - все остальноеБудем говорить, что объект классифицирован положительно, если в результатеклассификации он отнесен к классу 1, иначе говорим, что объект классифициро­ван отрицательно.Чтобы решать задачу классификации, необходимо определить пространствопризнаков.

Были выбраны следующие признаки:1 – размер файла в байтах,2 – расширение файла, преобразованное в число(использован хэш md5),3 – глубина вложенности файла в дереве файловой системы,4 – средний размер файлов в данной папке у данного пользователя,5 – средний размер файлов у данного пользователя.Использование хэша для представления расширения файла считаю обоснован­ным, так как различные расширения соответствуют различным типам файлови должны соответствовать различным точками в признаковом пространстве. Ве­роятностью колллизий при вычислении хэша пренебрегаем.

По сути, расширение- категориальный признак.Глубина вложенности у файлов кэшей, в среднем, больше, чем у остальныхфайлов(8.55 против 7.47 соответственно). Данное отличие статистически значимо,проверка выполнена с помощью t-теста Стьюдента и рангового критерия Уилкок­сона(в обоих случаях ≈ 0). Аналогично средний размер файла в папке и13средний размер по пользователю для кэшей значимо меньше, чем для остальныхфайлов.Таким образом, размерность пространства признаков равна пяти, каждомуфайлу соответствует точка = (1 , 2 , . . .

, 5 ) ∈ R5+ .4.2. СемплированиеСтратегия семплирования: выбирается репрезентативная выборка файлов(размервыборки 2428105 файлов), с соотношением положительных примеров к общемучислу примеров 0.155. Далее, выборка случайно разделяется на три равных ча­сти: обучающая, тестовая и контрольная. Доли положительных примеров в каж­дой части: 0.19, 0.13, 0.14.

Подбор параметров осуществляется с использованиемобучающей и тестовой выборок. Заключительная проверка выполняется на кон­трольной выборке.4.3. Оценка качестваЧтобы иметь возможность оценивать качество классификатора и сравниватьих между собой, необходимо ввести меру качества. Ввиду несбалансированностиклассов в задаче, в качестве таковой была выбрана F1-мера, т.к. в нее не вхо­дит количество верно классифицированных отрицательных примеров(доля такихпримеров может достигать 96-98%).

F1-мера определяется так:1 =| ∩ |,| ∪ |где - множество объектов, классифицированных положительно, - множество объектов, на самом деле принадлежащих классу 1. Мак­симальное значение меры равно 1, чем ее значение меньше тем больше классифи­катор пропускает положительных примеров и неверно классифицирует отрица­тельных.144.4. Выбор классификатораОснова всех нижеприведенных алгоритмов - решающие деревья, так как онилегко интерпретируемы и хорошо обрабатывают категориальные и числовые при­знаки одновременно.4.4.1.

Решающее деревоИспользуемый классификатор - решающее дерево. Имеется два параметра,существенно влияющих на качество классификации: число объектов в листе и по­рог классификации(если вероятность отнесения объекта к классу 1 больше этогопорога, объект классифицируется положительно). Первый настраиваемый пара­метр - минимальное число объектов в листе дерева(min samples per leaf). Былиисследованы значения параметра от 1 до 100. График зависимости качества клас­сификации от настраиваемого параметра(при построении дерева использован кри­терий Джини):Максимум качества достигается при минимальном числе объектов в листе рав­ном 10. Качество при этом составляет 81.9%. Аналогичный график при использо­вании критерия прироста информации для построения дерева:15Максимум качества достигается при числе объектов в листе 12, качество при этомуже выше: 83.4%.

Для дальнейшей настройки используем критерий прироста ин­формации. Посмотрим на качество при различных порогах:Максимум качества приходится на порог 0.50–0.56. Будем считать порог равным0.5. Итоговые параметры классификатора: минимальное число объектов в листедерева 12, качество на тестовой выборке 83.4%. Значение F-меры на контрольнойвыборке: 0.52.164.4.2. Случайный лесУ случайного леса имеются три интересующих меня параметра: число де­ревьев в ансамбле, порог классификации и минимальный размер листа.

Так какпостроение леса не детерминировано, необходимо усреднение результатов предска­заний по нескольким экспериментам. Выбираются некоторые значения парамет­ров, строится график зависимости среднего и стандартного отклонения качестваот числа деревьев в ансамбле:17Как и следовало ожидать, дисперсия качества уменьшается с ростом числа дере­вьев. При достаточно большом числе деревьев, проведения нескольких экспери­ментов для усреднения не требуется. Далее при настройке параметров используем100 деревьев.Далее, так как число признаков мало(равно пяти), нет необходимости в слу­чайном выборе подмножества признаков при построении деревьев. Осталось про­варьировать порог классификации:Видно, что максимум качества достигается при пороге классификации 0.25, каче­ство при этом составляет 79%.

Итоговые параметры: минимальное число объектовв листе: 12, количество деревьев: 100, порог классификации: 0.25, качество на те­стовой выборке: 79%. Значение F-меры на контрольной выборке: 0.60.4.4.3. Градиентный бустинг над решающими деревьямиИсследовался алгоритм градиентного бустинга над решающими деревьями.Настраивались два параметра: коэффициент обучения(англ. learning rate) - вкладкаждого классификатора, и число деревьев. Использовать поиск по каждому изпараметров последовательно не получится, так как параметры сильно взаимосвя­заны.

Двумерная карта зависимости качества от коэффициента обучения и от18числа деревьев, значения качества кодируются цветом:Путем поиска по двумерной сетке этих параметров были выбраны оптимальныезначения коэффициент обучения = 0.75, число деревьев = 40. Значение F-мерыпри этом 0.80. Значение F-меры на контрольной выборке: 0.65.19Глава 5Заключение5.1. Возможные улучшенияЕсть обширные возможности для улучшения качества классификации дляприменения к реальным задачам.

Далее приведены некоторые из них:∙ Использование более информативных признаков, например: время созда­ния, последнее время доступа, права доступа(категориальная переменная),количество изменений файла за определенный промежуток времени.∙ Обучение классификатора на более вариативной выборке.∙ Уменьшение шага подбора параметров, т.е. более точная настройка класси­фикаторов.∙ Использование смесей классификаторов(формирование результата как ли­нейной комбинации ответов нескольких классификаторов).5.2. ВыводыВ работе поставлена и решена задача бинарной классификации файлов нареальной компьютерной системе. В качестве интересующей группы файлов бы­ла выбрана группа "кэш приложений".

Характеристики

Список файлов ВКР