Исследование алгоритмов классификации на задаче Phishing Websites Data Set

 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение

высшего образования

«Сибирский государственный аэрокосмический университет

имени академика М. Ф. Решетнева»

(СибГАУ)

 

 

Институт информатики и телекоммуникаций

Кафедра системного анализа и исследования операций

 

 

 

 

Исследование алгоритмов классификации на задаче

Phishing Websites Data Set

 

 

 

                                                                            Выполнил: ст-т гр. МСИ15-01

Полякова И.Н.

           Проверил: д.т.н., профессор 

Семёнкин Евгений Станиславович      

 

 

 

 

 

Красноярск 2015

Содержание

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Краткие теоретические сведения

 

Neural Net (искусственные нейронные сети) – построены по принципам организации и функционирования нервной системы человека. ИНС способны решать неформализуемые или плохоформализуемые задачи из множества областей: распознавания образов, классификации, аппроксимации функций, прогнозирования и управления.

k-NN (метод k-ближайших соседей) - в основе алгоритма лежит сходство объектов. Алгоритм способен выделить среди всех наблюдений k известных объектов (k-ближайших соседей), похожих на новый неизвестный ранее объект. На основе классов ближайших соседей выносится решение касательно нового объекта. Важной задачей данного алгоритма является подбор коэффициента k – количество записей, которые будут считаться похожими.

W-J48 (C4.5) — алгоритм для построения деревьев решений, разработанный Джоном Квинланом (англ. John Ross Quinlan). C4.5 является усовершенствованной версией алгоритма ID3 того же автора. В частности, в новую версию были добавлены отсечение ветвей (англ. pruning), возможность работы с числовыми атрибутами, а также возможность построения дерева из неполной обучающей выборки, в которой отсутствуют значения некоторых атрибутов.

Sequential minimal optimization (W-SMO) - Новый алгоритм обучения SVM называется последовательной минимальной оптимизацией (или SMO). В отличие от предыдущих SVM алгоритмов обучения, в которых используется численное квадратичное программирование (QP) в качестве внутреннего контура, SMO использует аналитический шаг QP. Поскольку SMO проводит большую часть времени для оценки решающей функции, а не выполняет QP, он может использовать наборы данных, которые содержат значительное количество нулевых элементов. SMO работает особенно хорошо для разреженных наборов данных, либо бинарных или недвоичных входных данных.

W-RBFNetwork В области математического моделирования, сетью радиальных базисных функций является искусственная нейронная сеть , использующая радиальные базисные функции в качестве функции активации. Выход в сеть представляет собой линейную комбинацию радиальных базисных функций входов нейрона и параметров. Радиальные базисные сети имеют множество применений, в том числе аппроксимация функций, прогнозирование временных рядов, классификация систем управления.

Naive Bayes (наивный байесовский классификатор) – простой вероятностный классификатор, основанный на применении Теоремы Байеса со строгими (наивными) предположениями о независимости.

W-SimpleLogistic - это статистическая модель, используемая для предсказания вероятности возникновения некоторого события путём подгонки данных к логистической кривой. Логистическая регрессия применяется для предсказания вероятности возникновения некоторого события по значениям множества признаков.

 Linear Discriminant Analysis (LDA) является обобщением Фишера линейный дискриминантный, метод, используемый в статистических данных, распознавания образов и машинного обучения , чтобы найти линейную комбинацию из особенностей , которая характеризует или отделяет два или более классов объектов или событий. Полученная комбинация может использоваться как линейный классификатор, или, более широко, для уменьшения размерности до поздней классификации.

 

 

 

 

Описание задачи

Для исследования алгоритмов была выбрана задача классификации Phishing Websites Data Set

1. База данных содержит 11055 наблюдений.

2. Количество признаков - 30:

3. Число классов - 2.

4. Распределение объектов по классам: 4898 относятся к 1 классу и 6157 относятся к 2 классу.

5. Параметры в выборке:

attribute having_IP_Address  { -1,1 }

attribute URL_Length   { 1,0,-1 }

attribute Shortining_Service { 1,-1 }

attribute having_At_Symbol   { 1,-1 }

attribute double_slash_redirecting { -1,1 }

attribute Prefix_Suffix  { -1,1 }

attribute having_Sub_Domain  { -1,0,1 }

attribute SSLfinal_State  { -1,1,0 }

attribute Domain_registeration_length { -1,1 }

attribute Favicon { 1,-1 }

attribute port { 1,-1 }

attribute HTTPS_token { -1,1 }

attribute Request_URL  { 1,-1 }

attribute URL_of_Anchor { -1,0,1 }

attribute Links_in_tags { 1,-1,0 }

attribute SFH  { -1,1,0 }

attribute Submitting_to_email { -1,1 }

attribute Abnormal_URL { -1,1 }

attribute Redirect  { 0,1 }

attribute on_mouseover  { 1,-1 }

attribute RightClick  { 1,-1 }

attribute popUpWidnow  { 1,-1 }

attribute Iframe { 1,-1 }

attribute age_of_domain  { -1,1 }

attribute DNSRecord   { -1,1 }

attribute web_traffic  { -1,0,1 }

attribute Page_Rank { -1,1 }

attribute Google_Index { 1,-1 }

attribute Links_pointing_to_page { 1,0,-1 }

attribute Statistical_report { -1,1 }

attribute Result  { -1,1 }

Формирование алгоритма в среде RapidMiner

 

Решение выполнялось в программном пакете RapidMiner.

 Главный процесс состоит  из 3-х блоков:

1. Read CSV – добавление базы данных
2. Loop – блок, который проводит итерацию алгоритма заданное число раз, обеспечивая вариативность и изменчивость выборки от запуска к запуску (20 итераций).

Рис. 1. Первый (главный) уровень алгоритма

Рис. 2. Второй (цикличный) уровень алгоритма

На рис.2. представлена схема второго внутреннего уровня алгоритма. Данный уровень проходит заданное количество итераций в блоке Loop.

4. Split Data – разбиение базы данных на 2 части: обучающую и тестовую, в отношении 0.7/0.3.
5. Multiply – блок размножения выходов (разветвления).
6. Apply Model – блок применения обученной модели каждого метода к тестовому множеству.
7. Performance – производится оценка точности каждого алгоритма при одном прогоне.
8. Log – формирование отчета. Сохраняет значения точностей для каждого алгоритма в файл. Каждый прогон алгоритма записывается в конец файла для вычисления критерия t-стьюдента.

T-Тest – метод статистического анализа данных в котором согласно нулевой гипотезе между средними значениями достоверного различия нет, т.е. две выборки однородны и представляют одну генеральную совокупность. Если вероятность нулевой гипотезы (р) меньше 5% (т.е. р < 0, 05), то с вероятность 0,95 нулевую гипотезу можно отбросить.

Использовались стандартные настройки алгоритмов Naive Bayes (наивный байесовский классификатор), k-NN (метод ближайших соседей) и Neural Net (нейронная сеть), Linear Discriminant Analysis (LDA), W-SimpleLogistic, W-RBFNetwork, Social media optimization (W-SMO), W-J48 (C4.5).

 

 

 

 

 

 

 

Практические результаты

Точность решения задачи классификации алгоритмами ИАД (интеллектуального анализа данных) в данной задаче сведена в таблицу 1:

 

W – Simple logistic	92,747%
W - SMO	92,6832579%
K - NN	95,8778281%
Naive bayes	72,1538462%
W - J48	95,4705882%
Neural net	95,8280543%
LDA	91,7058824%
W - RBFnet	75,647058%

Таблица 1. Средняя точность алгоритмов за 20 итераций

Результаты попарного сравнения алгоритмов сведены в таблице 2.

	92,75%	92,68%	95,88%	72,15%	95,47%	95,83%	91,71%	75,65%
	SL	SMO	K-NN	NB	W-J48	NN	LDA	WRBF
SL		0,213433	6,67077E-08	2,04213E-14	1,01134E-08	1,54259E-08	4,39707E-07	1,19141E-06
SMO			3,85374E-08	2,74976E-14	1,06055E-08	1,94728E-08	2,81407E-06	1,23544E-06
K-NN				2,71051E-15	0,040045255	0,819061838	7,87828E-10	4,74044E-07
NB					8,39982E-16	1,71812E-14	9,47553E-15	0,053628205
W-J48						0,030824742	1,26443E-11	5,2628E-07
NN							8,95489E-10	3,67435E-07
LDA								2,30548E-06
WRBF

  Таблица 2. Результаты сравнения значимости различий T-Test (жирным выделены значения, показывающие статистически не значимые различия между алгоритмами)

По результатам вычислений, наилучшую точность имеет алгоритм k-nn – 95,88%. Нейронная сеть не имеет статистически значимых различий в сравнении с алгоритмом k-nn, и ее точность составляет 95,83%. Со всеми остальными алгоритмами k-nn имеет статистически значимые различия результатов в решении задачи классификации.

Алгоритмы SMO и Simple Logistic не имеют статистически значимого различия, как и алгоритмы Naive Bayes и W-RBFNet.

 

Заключение

В результате проведенного исследования выяснено, что с данной задачей  классификации одинаково хорошо справилось 2 алгоритма: k-nn и neural net.

Для того, чтобы улучшить точность классификации можно создать ансамбли из лучших нескольких методов в задаче и сравнить его с решением ансамблей, состоящими из всех используемых методов или из некоторых. Кроме того, для повышения эффективности применяют бустинг по алгоритму AdaBoost (сокращение от AdaptiveBoosting).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список используемых источников

1. RapidMiner [Электронный ресурс]. URL: https://rapidminer.com/ (дата обращения: 18.11.2015).
2. https://www.dropbox.com/sh/mt54xy30vf2zick/AABOfse4jUErs4SXYId7i50ha?dl=0
3. https://archive.ics.uci.edu/ml/datasets/Phishing+Websites
4. Дьяконов А.Г. Анализ данных, обучение по прецедентам, логические игры, системы WEKA, RapidMiner и MatLab // Учебное пособие (практикум на эвм кафедры математических методов прогнозирования), МГУ им. М. В. Ломоносова, Москва, 2010г.