ИССЛЕДОВАНИЕ МОДЕЛИ КЛАСТЕРНОГО АНАЛИЗА КОНТЕНТА WEB РЕСУРСОВ

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

Кластерный анализ представляет собой некоторую процедуру, выполняющую сбор данных, содержащих информацию о выборке объектов, и упорядочивающая объекты в сравнительно однородные группы. Отличительной особенностью кластеризации является то, что перечень групп четко не задан и определяется в процессе анализа.

Алгоритм проведения кластерного анализа:

• выбор объектов для кластеризации;
• выбор признаков, по которым будут оцениваться объекты;
• вычисление меры схожести между объектами;
• применение одного из методов кластерного анализа для формирования групп объектов.

Объектами кластеризации будут выступать Web Ресурсы. Web ресурс представляет собой набор субъектов - слова. Набор субъектов будем использовать в качестве входных векторов для метода кластеризации.

Признаками будут выступать субъекты объекта – слова (рис. 1). Слова Web ресурса составляют его контекст, по которому необходимо провести кластерный анализ.

Рисунок 1. Модель объекта кластеризации для Web ресурса

Для 3 и 4 пунктов существуют несколько вариантов реализации. Рассмотрим формулы для расчета меры схожести.

Наиболее распространенными являются формулы: евклидово расстояние и квадрат евклидова расстояния.

Евклидово расстояние

                                                (1)

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

                                                 (2)

Применяется для придания большего веса более отдаленным друг от друга объектам.

Большинство Web ресурсов так или иначе схожи друг с другом, поэтому для наиболее эффективного выделения признаков стоит использовать формулу (1), что упростит формирование кластеров из заданного множества объектов.

Рассмотрим методы кластерного анализа для формирования групп. В текущей задаче неизвестно точное количество кластеров. Существует множество методов кластеризации:

• Вероятностный подход;
• Подход на основе систем искусственного интеллекта;
• Логический подход;
• Иерархический подход.

Вероятностный подход предполагает, что каждый рассматриваемый объект относится к одному из k классов. Некоторые методы подхода:

• K-средних;
• K-медиан;
• EM-алгоритм;
• Алгоритмы семейства FOREL;
• Дискриминантный анализ.

Вычислительная сложность подхода: O(nkl), где k – число кластеров, l – число итераций.

Логический подход основан на построении дендрограммы. Построение дендрограммы осуществляется при помощи дерева решений.

Иерархический подход предполагает наличие вложенных групп. Алгоритмы в свою очередь подразделяются на агломеративные и дивизивные. По количеству признаков иногда выделяют монотетические и политетические методы классификации. К данному подходу можно отнести метод Иерархической дивизивной кластеризации.

Иерархический подход предполагает наличие вложенных кластеров, различного порядка. Он в конечном итоге может сформировать дерево кластеров контента Web ресурсов, где будут находиться кластеры как принадлежащие непосредственно к контенту, так и косвенно касающиеся контента. Такой результат содержит избыточную информацию, что усложнит выбор классификацию Web ресурса. Вычислительная сложность подхода: O(n²).

Подход подразумевает использование различных систем искусственного интеллекта, позволяющих выявлять общие признаки у выборки объектов. В основном это нейронные сети с способом обучения без учителя. К данному подходу относятся такие методы как:

• Метод нечеткой кластеризации C-средних;
• Нейронная сеть Кохонена;
• Генетический алгоритм;
• Рекуррентные нейронные сети.

Подход на основе систем искусственного интеллекта в конечном итоге определит тот или иной Web ресурс к одному кластеру, также искусственные нейронные сети позволяют анализировать контекст Web ресурса, для более точного анализа входных данных. Такими свойствами обладают рекуррентные нейронные сети (рис. 3).

Вычислительная сложность данного подхода является самой высокой среди всех подходов кластеризации и зависит от количества слоев и нейронов.

Рисунок 2. Модель рекуррентной нейронной сети

В рамках текущей задачи нет возможности выделить все возможные кластеры, что существенно облегчает выбор метода. Наиболее подходящими методами являются: иерархический подход и подход на основе систем искусственного интеллекта. Но как было указано выше, иерархический подход имеет достаточно много излишних данных, что затрудняет процесс кластерного анализа контента Web ресурсов.

Для проведения эффективного кластерного анализа необходимо определить критерии для конкретной задачи кластеризации. Контент Web ресурсов определяется набором предложений. Совокупность предложений web ресурса определяет его тематику, определение которой и является целью кластеризации контента Web ресурсов.

Критерии задачи кластеризации контента Web ресурсов:

• неопределенное количество кластеров;
• близкая схожесть кластеров между собой;
• определение смысла (тематики) контента;
• неизменность кластеров при пополнении множества объектов.

Проведем анализ подходов кластеризации. На выбор подхода кластеризации влияют критерии: неопределенное количество кластеров и определение смысла (тематики) контента.

Таблица 1.

Удовлетворение критериев подходами кластеризации

Из таблицы 1 видно, что для задачи кластеризации контента Web ресурсов больше всего подходит подход на основе систем искусственного интеллекта. Среди методов выбранного подхода все необходимые критерии удовлетворяет метод основанный на использовании рекуррентной нейронной сети.

Проведем анализ формул для расчета меры сходимости. На выбор формулы меры сходимости влияют критерии: близкая схожесть кластеров между собой и неизменность кластеров при пополнении множества объектов.

Таблица 2.

Удовлетворение критериев формулами мер сходимости

Из таблицы 2 видно, что квадрат евклидова расстояния полностью удовлетворяет критерии задачи кластеризации контента Web ресурсов.

Рисунок 3. Модель кластерного анализа контента Web ресурсов

Таким образом, кластеризация контента Web ресурсов будет наиболее эффективна при использовании подхода на основе систем искусственного интеллекта, в котором при расчете меры схожести необходимо использовать формулу квадрата евклидова расстояния. В качестве метода выбранного подхода всеми необходимыми свойствами обладает рекуррентная нейронная сеть.