Размещено на http://www.allbest.ru/

1

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ В.Н. КАРАЗІНА

ФАКУЛЬТЕТ КОМП'ЮТЕРНИХ НАУК

КУРСОВА РОБОТА

з дисципліни «Теорія алгоритмів»

Тема «Класифікатор Байєса»

Виконав студент

Кравченко Євгеній Миколайович

Перевірив: доц. Олешко О. І.

Харків - 2018

Вступ

Останнім часом в світі (зокрема в Україні) спостерігається стрімкий розвиток інформаційних технологій, який впливає на різноманітні процеси, явища тощо. Необхідність використання сучасних інформаційних технологій вже не викликає жодних сумнівів, оскільки саме ця індустрія є однією з найбільш динамічно розвинутих галузей сучасності.

Однак, розвиток будь-якої прикладної сфери не можливий без фундаментальної теоретичної частини, яка пояснює всі складові, процеси тощо. Безумовно інформаційні технології тісно пов'язані з математикою взагалі та з багатьма її розділами (дискретна математика, теорія алгоритмів, математична логіка тощо) зокрема.

Одним з напрямків інформаційних технологій є програмування, що відповідає за розробку програмного забезпечення з використанням різноманітних засобів та інструментів. В основі кожної програми лежать алгоритми, структури даних, функції тощо.

В даній роботі розглядається такий алгоритм я «Наївний класифікатор Байєса», описується теоретична основа, яка включає розбір структури, асимптотичної складності функцій, що можуть бути виконані, порівняльний аналіз з подібними структурами та наводиться програмна реалізація алгоритму мовою програмування Java.

Наївний алгоритм - це алгоритм класифікації, заснований на теоремі Байеса з припущенням про незалежність ознак. Іншими словами, НБА передбачає, що наявність якої-небудь ознаки в класі не пов'язана з наявністю будь-якої іншого ознаки. Наприклад, фрукт може вважатися яблуком, якщо він червоний, круглий і його діаметр становить близько 8 сантиметрів. Навіть якщо ці ознаки залежать один від одного або від інших ознак, в будь-якому випадку вони вносять незалежний внесок у ймовірність того, що цей фрукт є яблуком. У зв'язку з таким припущенням алгоритм називається «наївним».

Моделі на основі НБА досить прості і вкрай корисні при роботі з дуже великими наборами даних. При своїй простоті НБА здатний перевершити навіть деякі складні алгоритми класифікації.

1. Теоретичні основи

1.1 Область визначення завдання

Розглядається алгоритм - Наївний класифікатор Байєса, та розробляється його програмна реалізація.

Ціль роботи - проаналізувати джерела інформації щодо вищезгаданого алгоритму, виявити її сильні та слабкі сторони та реалізувати НБА мовою програмування Java.

Методи дослідження - аналіз та синтез алгоритму, порівняння з іншими алгоритмами того ж класу тощо.

Актуальність полягає в тому, що прикладні завдання можна буде вирішувати за допомогою НБА.

1.2 Історія виникнення поняття НБА»

В якості короткої історичної довідки скажу, що формула Байеса була опублікована аж в 1763 році через 2 роки після смерті її автора, Томаса Байеса. Однак, методи, які використовують її, отримали дійсно широке поширення тільки до кінця ХХ століття. Це пояснюється тим, що розрахунки вимагають певних обчислювальних витрат, і вони стали можливі тільки з розвитком інформаційних технологій.

Першою відомою програмою, що фільтрує пошту з використанням класифікатора Байєса, була програма iFile Джейсона Ренні, випущена в 1996 році. Програма використовувала сортування пошти по папках. Перша академічна публікація по наївній фільтрації спаму з'явилася в 1998 році. Незабаром після цієї публікації була розгорнута робота по створенню комерційних фільтрів спаму. Однак в 2002р Пол Грем зміг значно зменшити число хибнопозитивних спрацьовувань до такої міри, що фільтр Байєса міг використовуватися в якості єдиного фільтра спаму.

1.3 Область застосування НБА

Багато сучасних поштових клієнтів здійснюють фільтрування спаму за допомогою НБА. Користувачі можуть також встановити окремі програми фільтрування пошти. Фільтри для поштового сервера - такі, як DSPAM, SpamAssassin, SpamBayes, SpamProbe, Bogofilter, CRM114 - використовують методи фільтрування спаму Байєса. Програмне забезпечення серверів електронної пошти або включає фільтри в свою поставку, або надає API для підключення зовнішніх модулів.

1.4 Математичні основи алгоритму

Давайте припустимо, що підозріле повідомлення містить слово «Replica». Більшість людей, які звикли отримувати електронного листа, знає, що це повідомлення, швидше за все, буде спамом, а точніше - пропозицією продати підроблені копії годинників відомих брендів. Програма виявлення спаму, однак, не «знає» такі факти; все, що вона може зробити - обчислити ймовірності.

Формула, яка використовується програмним забезпеченням, для обчислення, отримана з теореми Байєса і формули повної ймовірності:

Формула 1.4.1 - Формула Байєса

- умовна ймовірність того, що повідомлення-спам, за умови, що слово «Replica» знаходиться в ньому;

-повна ймовірність того, що довільне повідомлення-спам;

- умовна ймовірність того, що слово «replica» з'являється в повідомленнях, якщо вони є спамом;

- повна ймовірність того, що довільне повідомлення не спам (тобто «ham»);

- условная вероятность того, что слово «replica» появляется в сообщениях, если они являются «ham».

Недавні статистичні дослідження показали, що на сьогоднішній день імовірність будь-якого повідомлення бути спамом становить щонайменше 80%: = 0.8; = 0.2;

Однак більшість Байєсовських програм виявлення спаму роблять припущення про відсутність апріорних переваг у повідомлення бути спамом, чи не спамом, і вважає, що у обох випадків є рівні ймовірності 50%:

= 0.5; = 0.5;

Про фільтри, які використовують цю гіпотезу, кажуть як про фільтрах «наївні». Це означає, що у них немає ніякого упередження щодо вхідних повідомлень електронної пошти. Дане припущення дозволяє спрощувати загальну формулу до:

Формула 1.4.2 - Формула Байєса для = 0.5; = 0.5;

Значення називають «спамовістю» слова W; при цьому число , що використовується в формулі (1.4.2), приблизно дорівнює частоті повідомлень, які містять слово W, ідентифікованих як спам під час фази навчання, тобто:

Формула 1.4.3 - Формула Байєса з урахуванням вірогідності кожного слова бути спамом чи не спамом

Точно так наближено до відносної частоти повідомлень, що містять слово W, ідентифікованих як «ham» під час фази навчання.

Формула 1.4.4 - Формула Байєса

Для того, щоб ці наближення мали сенс, набір навчальних повідомлень повинен бути великим і різноманітним. Також бажано, щоб набір навчальних повідомлень відповідав гіпотезі про перерозподіл між спамом і не спамом, тобто що набори повідомлень «spam» і «ham» мали один і той же розмір.

Звичайно, визначення, чи є повідомлення «spam» або «ham», що базується тільки на присутності лише одного певного слова, схильні до помилок.

Програмні спам-фільтри, побудовані на принципах наївного байєсівського класифікатора, роблять «наївне» припущення про те, що події, відповідні наявності того чи іншого слова в електронному листі або повідомленні, є незалежними по відношенню один до одного. Це спрощення в загальному випадку є невірним для природних мов - таких, як англійська, де ймовірність виявлення прикметника підвищується при наявності, наприклад, іменника. Виходячи з такого «наївного» припущення, для вирішення задачі класифікації повідомлень лише на 2 класу: (спам) і (не спам) з теореми Байеса можна вивести таку формулу оцінки ймовірності 1.4.3 спам всього повідомлення, що містить слова :

Формула 1.4.5 - Формула Байєса

Таким чином, припускаючи що маємо:

Формула 1.4.6 - Формула Байєса для повної вірогідності

де: - вірогідність того, що повідомлення яке містить слова спам;

- умовна ймовірність того, що повідомлення - спам, за умови, що воно містить перше слово (наприклад, «replica» );

- умовна ймовірність того, що повідомлення - спам, за умови, що воно містить друге слово (наприклад, «watches» );

Результат p зазвичай порівнюють з деяким порогом (наприклад, 0.5), щоб вирішити, чи є повідомлення спамом чи ні. Якщо нижче, ніж поріг, повідомлення розглядають як ймовірний «ham», інакше його розглядають як ймовірний спам.

1.5 Характеристика алгоритму

Метод оснований на теоремі Байєса простий (алгоритм елементарний), зручний (дозволяє обходитися без «чорних списків» і подібних штучних прийомів), ефективний (після навчання на досить великій вибірці відсікає до 95-97% спаму), причому в разі будь-яких помилок його можна довчити. Загалом, є всі показання для його повсюдного використання, що і є на практиці - на його основі побудовані практично всі сучасні спам-фільтри.

У метода є і принциповий недолік: він базується на припущенні, що одні слова частіше зустрічаються в спамі, а інші - в звичайних листах, і неефективний, якщо це припущення невірно. Втім, як показує практика, такий спам навіть людина не в змозі визначити «на око» - тільки прочитавши лист і зрозумівши його зміст. Існує метод Байесове отруєння, що дозволяє додати багато зайвого тексту, іноді ретельно підібраного, щоб «обдурити» фільтр.

Ще один не принциповий недолік, пов'язаний з реалізацією - метод працює тільки з текстом. Знаючи про це обмеження, спамери почали вкладати рекламну інформацію в картинку. Текст в листі або відсутній, або не несе сенсу. Проти цього доводиться використовувати або засоби розпізнавання тексту ( «дорога» процедура, застосовується тільки при гострій потребі), або старими методами фільтрації - «чорні списки» і регулярні вирази (так як такі листи часто мають стереотипну форму).

1.6 Результати тестування алгоритму

Провівши ряд експериментів з різними типами повідомлень (спам, не спам, короткі, довгі) можемо бачити результат. На графіку зображено залежність точності виявлення спаму у повідомленні від кількості слів у ньому.

Як видно на графіку класифікатор Байєса починає визначати спам досить точно вже при десяти словах у повідомленні. Після двадцяти слів спам-фільтр починає хибити, так як у великий текст можна записати багато слів, які не є спамом.

Графік 1.6.1 - Залежність точності виявлення спаму від кількості слів у повідомленні

2. Переваги та недоліки алгоритму

Байєсова фільтрація спаму стала передвісником цілого ряду технологій обробки «великих даних», в яких підвищення якості імовірнісного аналізу досягається за рахунок використання накопичених статистичних даних та іншої взаємопов'язаної інформації. Спамери адаптують методики розсилки до нових способів її відсіву, тому в чистому вигляді жоден алгоритм фільтрації довго не працює. Замість цього провайдери та фірми, що спеціалізуються на захисті даних, розвивають методи машинного навчання.

Однією з основних переваг алгоритму Байєсової фільтрації спаму є те, що його можна навчати на основі кожного користувача.

Спам, який отримує користувач, часто пов'язаний з діяльністю онлайн-користувача. Наприклад, користувач може сам обрати чи є отримане повідомлення спамом або ж ні. Цей вибір зберігається в інтернеті, ймовірно, він містить слова, які є загальними для всіх інформаційних повідомлень, наприклад, назва повідомлення та його електронну адресу. Байєсовський спам-фільтр, на основі вибраних користувачем даних призведе до більшої точності виявлення спаму, на основі конкретних шаблонів користувача.

Легітимні повідомлення, отримані користувачем, мають тенденцію бути різними. Наприклад, у корпоративному середовищі часто згадується найменування компанії та імена клієнтів або клієнтів. Фільтр призначить нижчу можливість спаму для листів, що містять ці найменування.

Ймовірнісні слова є унікальними для кожного користувача, і вони можуть розвиватися з часом з виправним тренуванням кожного разу, коли фільтр неправильно класифікує електронну пошту. Як результат, точність Байєсівської фільтрації спаму після тренувань часто перевищує попередньо визначені результати, і працю більш точно.

Він може працювати особливо добре, щоб уникнути помилкових спрацьовувань, де не спамове повідомлення неправильно класифікується як спам. Наприклад, якщо в повідомленні електронної пошти міститься слово "акція", яке часто використовується в спамі для того щоб продати якийсь непотрібний товар, фільтр заздалегідь визначеними правилами може повністю відхилити його. Байєсівський фільтр позначатиме слово "акція" як імовірне спамове слово, але враховуватиме інші важливі слова, які зазвичай вказують на правильну електронну пошту. Наприклад, ім'я дружини може чітко вказувати на те, що електронна пошта не є спамом, що може подолати використання слова "акція".

Залежно від реалізації, байєсовська фільтрація спаму може бути чутливою до так званого Байєсового отруєння, що використовується спамерами в спробі погіршити ефективність спам-фільтрів, які залежать від байєсівської фільтрації. Спамер, який практикує Байєсове отруєння, надсилатиме електронні листи з великою кількістю не спам тексту (зібрані з новин або ж літературних джерел). Тактика обману спам-фільтра включає в себе введення випадкових неспам слів, які зазвичай не пов'язані з спамом, тим самим зменшуючи оцінку спаму повідомлення, завдяки чому воно, швидше за все, пройде через фільтр спаму Байєса. Проте сучасні спам фільтри, які використовують змішані методи фільтрації спаму навчилися долати цю проблему.

Слова, які зазвичай з'являються у великих кількостях у спамі, можуть також трансформуватися спамерами. Наприклад, «Віагру» можно замінити на «Viaagra» або «V! Agra» в спам-повідомленні. Одержувач повідомлення може все-таки читати змінені слова, але кожне з цих слів зустрічається рідше у фільтрі Байєса, що перешкоджає його процесу навчання. Як правило, ця методика спаму не працює дуже добре, оскільки похідні слова в кінцевому результаті визнаються фільтром так само, як і звичайні.

Інший метод, який використовується для спроби перемогти фільтри спаму Байєса, полягає в тому, щоб замінити текст картинками. Весь текст повідомлення або його частина замінюється зображенням, де однаковий текст "намальований". Спам-фільтр, як правило, не може аналізувати це зображення, яке міститиме чутливі слова типу "Віагра". Однак, оскільки багато поштових клієнтів вимикають відображення зображень з міркувань безпеки, спамер, який надсилає посилання на віддалені зображення, може досягти меншої кількості цілей. Також розмір зображення в байтах більший, ніж еквівалентний розмір тексту, тому спамерові потрібна більша пропускна спроможність, щоб надсилати повідомлення безпосередньо, включаючи фотографії. Деякі фільтри більше схильні вирішити, що повідомлення є спамом, якщо він містить переважно графічний вміст. Рішення, яке використовує Google у своїй поштовій системі Gmail, полягає в тому, щоб виконувати OCR (Оптичне розпізнавання символів) на кожному зображенні середнього та великого розміру, аналізуючи текст на ньому.

3. Програмна реалізація

Програмна реалізація Наївного спам-фільтру Байєса була розроблена за допомогою мови програмування Java та використовуючи парадигми об'єктно орієнтованого програмування.

Були підключені стандартні бібліотеки мови програмування Java, а саме - Java.io.BufferReader - для організації роботи з потоками для зчитування з файлів, Java.io.BufferWriter - для організації роботи з потоками для запису у файлів, Java.io.FileWriter - для роботи з файлами, а саме запису, Java.io.FileReader - для зчитування з даних з файлів, Java.util.ArrayList - колекція для організації роботи з масивами, Java.util.HashMap - колекція для роботи зі структурою даних HashMap.

Було реалізовано класи Word, Main, Bayes.

Main - клас для запуску і тестування алгоритму. Складається з одного метода main.

Word - клас для роботи зі словами та їх вірогідностями належати до класу спам чи не спам. В класі Word були використані поля: word - зберігає у собі саме слово в форматі рядка, тобто масиву символів; spamCount - кількість таких слів у повідомленнях що є спамом; hamCount - кількість таких слів у повідомленнях що не є спамом; spamRate - частота появи слова у спам повідомленнях; hamRate - частота появи слова у не спам повідомленнях; probofSpam - вірогідність слова бути спамом. Також були створені методи:

1. Public void calculate Probability(int totSpam, int totHam) - розраховує вірогідність спаму на основі загальної кількості спаму і не спаму;

2. Public double getprobof Spam() - повертає значення поля probofSpam;

3. Public void setprobof Spam(double probofSpam) - змінює значення поля probofSpam;

Bayes - клас де реалізовані методи обчислення загальної вірогідності повідомлення бути спамом, метод навчання спам-фільтра, робота з файлами. В класі були реалізовані такі методи:

1. Public void train(String studyFile) - метод який приймає аргумент типу рядок в якому зазначено повний шлях до тренувального файлу. Створює хеш мапу

Висновки

В даній роботі було розглянуто алгоритм фільтрації спаму, що використовує підхід Баєса, проаналізовано різноманітні джерела інформації (книжки з теорії алгоритмів, першоджерела - статті Aragon Cecilia R., Seidel Raimund та Jean Vuillemin тощо).

Було описано історію виникнення цього алгоритму (перші спамфільтри), була визначена область застосування спам-фільтрів, описана точність виявлення спаму та не спаму, та швидкість класифікації документа, представлені результати тестування структури даних.

Також у другому розділі були представлені переваги та недоліки алгоритму фільтрації спаму Баєса.

В третьому розділі була розглянута програмна реалізація спам-фільтра за допомогою мови програмування Java, описані класи та методи, використані в програмі, та наведені приклади (код програми наведено в додатку А).

Таким чином, результатом цієї роботи є проаналізований алгоритм, з представленням вищезгаданої інформації щодо неї та програмна реалізація, що демонструє алгоритм Байєса на практиці з можливістю перевірки усіх властивостей.

математичний алгоритм програмування технологія

Список використаних джерел

1. Aragon Cecilia R., Seidel Raimund. Randomized Search Trees //Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington D.C.:IEEE Computer SocietyPress, pp. 540-545 ISBN 0-8186-1982-1

2. G. Blelloch and M. Reid-Miller Fast Set Operations Using Treaps. //Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 16-26, Puerto Vallarta, Mexico, June 1998.

3. Seidel Raimund, Aragon Cecilia R. Randomized Search Trees //Algorithmica. - 1996. - 16 (4/5). - pp. 464-497

4. Jean Vuillemin (1980). A Unifying Look at Data Structures. Commun. ACM 23 (4): 229-239.

5. Бабенко М.А., Левин М.В. Введение в теорию алгоритмов и структур данных /М.А. Бабенко, М.В. Левин // Электронное издание М.: МЦНМО, 2016 144 с. ISBN 978-5-4439-2396-3

6. Дональд Кнут. Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. -- 2-е изд. -- М.: «Вильямс», 2007. -- ISBN 0-201-89685-0.

7. О Ніл Кеті, Шатт Рейчел Data Science. Інсайдерська інформація для початківців. Включно з мовою R.

8. Кормен, Томас X. и др. А45 Алгоритмы: построение и анализ, 3-е изд.: Пер. с англ. -- М.: ООО “И. Д. Вильямс”, 2013. -- 1328 с.: ил. -- Парал. тит. англ. ISBN 978-5-8459-1794-2 (рус.)

Додаток А

Размещено на Allbest.ru