Аналіз
використання Веб-ресурсів
Вилучення
Веб-структурВилучення Веб-контенту
Кластеризація
Класифікація
Асоціація
Рис. 3. Категорії Web Mining і завдання Data Mining
У бізнес-аналітиці Web Mining вирішує наступні завдання:
опис відвідувачів сайту (кластеризація, класифікація);
опис відвідувачів, які здійснюють покупки в інтернет-магазині (кластеризація, класифікація);
визначення типових сесій і навігаційних шляхів користувачів сайту (пошук популярних наборів, асоціативних правил);
визначення груп або сегментів відвідувачів (кластеризація);
знаходження залежностей при користуванні послугами сайту (пошук асоціативних правил).
Усі описані вище технології ґрунтуються на первинній технології Data Mining. Вони можуть реалізуватися із застосуванням самонавчаючихся систем, до складу яких входять нейронні мережі, дерева рішень, словники, алгоритми кластеризації, семантичні мережі зв’язків між словами та словосполученнями і по суті базуються на одних і тих самих алгоритмах і принципах. Вони направлені в основному на величезні обсяги різнорідної інформації, яку необхідно класифікувати, побудувати зв’язки та зробити певні висновки (наприклад, прогнозування).
2.3. Технології аналізу
У системах інформаційного моніторингу більш вузько направленого характеру можуть використовуватися більш спрощені способи інтеграції контенту. Для того, щоб виділити в усьому об’ємі інформації потрібні дані використовується синтаксичний аналіз або його ще називають парсингом.
Синтаксичний аналіз — це процес зіставлення лінійної послідовності лексем (слів, токенів) мови з її формальною граматикою. Результатом зазвичай є дерево розбору (синтаксичне дерево). Звичайно застосовується спільно з лексичним аналізом. Синтаксичний аналізатор або парсер — це програма або частина програми, що виконує синтаксичний аналіз [7].
При парсингу вихідний текст перетворюється в структуру даних, зазвичай — в дерево, яке відображає синтаксичну структуру вхідної послідовності і добре підходить для подальшої обробки.
Як правило, результатом синтаксичного аналізу є синтаксична структура пропозиції, представлена або у вигляді дерева залежностей, або у вигляді дерева складових, або у вигляді деякої комбінації першого і другого способів подання.
Все, що має «синтаксис», піддається автоматичному аналізу:
мови програмування — розбір вихідного коду мов програмування, в процесі трансляції (компіляції або інтерпретації);
структуровані дані — дані, мови їх опису, оформлення тощо. Наприклад, XML, HTML, CSS, ini-файли, спеціалізовані конфігураційні файли тощо;
SQL-запити (DSL-мова);
математичні вирази;
регулярні вирази (які, в свою чергу, можуть використовуватися для автоматизації лексичного аналізу);
формальні граматики;
лінгвістика — людські мови. Наприклад, машинний переклад та інші генератори текстів.
Існує дві основні стратегії синтаксичного аналізу:
низхідна (top-down parsing), коли для даної пропозиції, виходячи з початкового символу граматики, будують висновок;
висхідна (bottom-up parsing), коли даної пропозиції, виходячи з символів самої пропозиції (терміналів), будують розбір.
Таким чином, розрізняють спадні і висхідні аналізатори.
Для того, щоб уявити, як це працює технічно, у якості прикладу можна розглянути як працює спадний аналіз. Для цього граматику необхідно замінити скороченою еквівалентною граматикою.
Розпізнавання сентенціальний форми в нашій мові можна виконати алгоритмом, який реалізується кінцевим автоматом, а розпізнавач для нашої мови з кінцевим числом станів можна представити у вигляді таблиці з двома входами, яка представляє собою специфічний запис набору породжуючих правил, причому число рядків станів таблиці дорівнює числу нетермінальних символів, а число стовпців — числу термінальних символів граматики. Початковий стан — початковий символ граматики. У клітинах таблиці записані наступні стани для даної пари входів, порожні клітини — помилки [47].
Відмітна риса низхідного аналізу — це цілеспрямованість. На кожному кроці аналізу спадні розпізнавачі формують мету — знайти висновок, що починається з деякого нетермінального символу і породжує частину вхідного рядка. Розпізнавач намагається досягти цієї мети шляхом спрямованого перебору різних можливостей. Основна ідея спадного аналізу в наступному: починаючи процес аналізу вхідного рядка S1, S2 ..., Sn, розпізнавач виходить з припущення, що цей рядок є реченням вхідної мови. Звідси випливає головна мета аналізу — знайти висновок (побудувати дерево).
Якщо існує такий висновок, то існують і проміжні породжуючі правила, але для кожного нетермінального символу в граматиці може бути кілька правил з різними правими частинами і яке саме правило слід застосувати, заздалегідь не відомо. При невдалому виборі правила, допоміжна мета може виявитися недосяжною, тоді потрібно спробувати застосувати інше правило. Можливі випадки, коли для будь-якої допоміжної мети всі правила призводять до невдачі. Опис процесу завершується, коли знайдений кінцевий висновок (ланцюжок) або коли встановлено, що цього висновку не існує, тобто вхідний рядок не є реченням цієї мови. Зазвичай спадний розпізнавач переглядає символи, що входять у рядки і символи в правій частині застосовуючи правило «зліва — направо». Такі розпізнавачі називають лівобічними [8].
В пам’яті машини правила формальної граматики можуть зберігатися у вигляді синтаксичних таблиць.
Перекладачі широко застосовують комбінацію низхідних і висхідних методів синтаксичного аналізу. Наприклад, низхідний аналіз виділяє відносно великі синтаксичні конструкції (різні описи, оператори), кожен з яких потім аналізується детальніше методами висхідного аналізу.
Загальна ідея висхідного аналізу полягає в наступному: вхідний текст розглядається як рядок символів, розпізнавач описує частину рядка, яку можна звести до нетермінального символу, таку частину рядка називають фразою. Фразу, що прямо приводиться до нетермінального символу, називають такою, безпосередньо приводимою. У більшості висхідних розпізнавачів відшукується найлівіша безпосередньо приводима фраза, яка називається основою. Основа замінюється нетермінальним символом, у знову отриманому рядку знову відшукується основа, яка також замінюється нетермінальним символом і так далі. процес триває або до отримання початкового символу, або до встановлення неможливості приведення рядка до початкового символу. Послідовність проміжних рядків, яка закінчується початковим символом утворює розбір. Якщо рядок не приводиться до початкового символу, то вхідна програма синтаксично некоректна, тобто не є формою цієї мови [9].
Другою складовою методів опрацювання текстової інформації є лексичний аналіз, основною задачею якого є розбиття вхідного тексту, що складається з послідовності одиночних символів, на послідовність слів, або лексем, тобто виділити ці слова з безперервної послідовності символів. Усі символи вхідної послідовності з цієї точки зору поділяються на символи, що належать будь-яким лексемам, і символи, що розділяють лексеми (роздільники). У деяких випадках між лексемами може і не бути роздільників. З іншого боку, в деяких мовах лексеми можуть містити незначні символи [46].
Зазвичай всі лексеми поділяються на класи. Прикладами таких класів є числа (цілі, вісімкові, шістнадцяткові, дійсні і т.д.), ідентифікатори, рядки. Окремо виділяються ключові слова і символи пунктуації (іноді їх називають символи-обмежувачі). Як правило, ключові слова — це деяка кінцева підмножина ідентифікаторів. У деяких мовах сенс лексеми може залежати від її контексту і неможливо провести лексичний аналіз у відриві від синтаксичного.
З точки зору подальших фаз аналізу лексичний аналізатор видає інформацію двох сортів: для синтаксичного аналізатора, що працює слідом за лексичним, істотна інформація про послідовність класів лексем, обмежувачів і ключових слів, а для контекстного аналізу, що працює слідом за синтаксичним, важлива інформація про конкретні значеннях окремих лексем (ідентифікаторів, чисел і т.д.).
Таким чином, загальна схема роботи лексичного аналізатора така. Спочатку виділяється окрема лексема (можливо, використовуючи символи-роздільники). Ключові слова розпізнаються або явним виділенням безпосередньо з тексту, або спочатку виділяється ідентифікатор, а потім робиться перевірка на приналежність його безлічі ключових слів [57].
Якщо виділена лексема є обмежувачем, то він (точніше, певна його ознака) видається як результат лексичного аналізу. Якщо виділена лексема є ключовим словом, то видається ознака відповідного ключового слова. Якщо виділена лексема є ідентифікатором — видається ознака ідентифікатора, а сам ідентифікатор зберігається окремо. Нарешті, якщо виділена лексема належить якомусь з інших класів лексем (наприклад, лексема представляє собою число, рядок і т.д.), то видається ознака відповідного класу, а значення лексеми зберігається окремо.
Лексичний аналізатор може бути як самостійної фазою трансляції, так і підпрограмою, що працює за принципом «дай лексему». У першому випадку (рис. 4а) виходом аналізатора є файл лексем, у другому (рис. 4б) — лексема видається при кожному зверненні до аналізатору (при цьому, як правило, ознака класу лексеми повертається як результат функції «лексичний аналізатор» , а значення лексеми передається через глобальну змінну). З точки зору обробки значень лексем, аналізатор може або просто видавати значення кожної лексеми, і в цьому випадку побудова таблиць об’єктів (ідентифікаторів, рядків, чисел і т.д.) переноситься на більш пізні фази, або він може самостійно будувати таблиці об’єктів. В цьому випадку як значення лексеми видається покажчик на вхід у відповідну таблицю.