автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Исследование и разработка методов автоматической кластеризации интернет-пользователей и интернет-ресурсов для персонализации поиска

На правах рукописи

ША**

Зейн Али Нажи

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ АВТОМАТИЧЕСКОЙ КЛАСТЕРИЗАЦИИ ИНТЕРНЕТ-ПОЛЬЗОВАТЕЛЕЙ И ИНТЕРНЕТ-РЕСУРСОВ ДЛЯ ПЕРСОНАЛИЗАЦИИ ПОИСКА

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

I у ^ 2015

Москва-2015 005559350

005559350

Работа выполнена на кафедре Вычислительных машин, систем и сетей федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский университет «МЭИ» (ФГБОУ ВПО «НИУ «МЭИ»)

Научный руководитель: кандидат технических наук, доцент

Мороховец Юрий Евгенневич

Официальные оппоненты: Фаязов Хабибулло Файзуллаевич

доктор технических наук, Евразийское патентное ведомство, вице-президент.

Фоменков Андрей Вячеславович

кандидат технических наук, ООО «Ренессанс Брокер», /Г-менеджер.

Ведущая организация: ООО «Мэйл.Ру», г. Москва

Защита состоится 27 марта 2015 года в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при ФГБОУ ВПО «НИУ «МЭИ» по адресу: 111250, Москва, ул. Красноказарменная, 13, ауд. М-704.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «НИУ «МЭИ» а на сайте mpei.ru.

Автореферат разослан «09» февраля 2015 г.

Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы исследования. Интернет в 21-ом веке является неотъемлемой частью повседневной жизни. Огромное количество ресурсов и содержащейся в них информации превратило Всемирную Паутину в 1ранди-озное хранилище плохо организованных, неструктурированных данных, имеющих ограниченные возможности целенаправленного поиска.

В настоящее время реализовано множество методов повышающих эффективность Интернет-поиска, релевантность данных запросам и предпочтениям пользователей. Применяемые методы в основном базируются на классификации Интернет-пользователей (ИП) и Интернет-ресурсов (ИР).

И. Витген, К. Гуандонг, Е. Франк успешно применяли ассоциативные методы классификации и метод пересечений для таргетирования Интернет-рекламы. И.Е. Кураленок, В.В. Гулин, Шахраев А.Г. и др. предлагают применять методы классификации, основанные на машинном обучении, для сравнительной оценки систем текстового поиска, автоматической фильтрации спама, агрегации и рубрикации новостей. Реализация этих методов, по мнению их авторов, обеспечивает повышение полноты и точности результатов классификации при сокращении временных затрат на обработку исходных текстов. К сожалению, остается неясным, насколько удачно можно применять указанные методы для классификации ИП и ИР с целью персонализации Интернет-поиска?

Классические методы кластерного анализа подробно описаны в работах С .А. Айвазяна, В.М. Бухштабера, И.С. Енюкова, Л.Д. Мешалкина, других авторов. В информационных источниках можно встретить общие сведения о применении методов кластеризации для классификации ИП и ИР. Декларируются различные цели применения методов кластерного анализа к Интернет-объектам, однако в подавляющем большинстве случаев детали этих методов и способов их применения не разглашаются, оставаясь коммерческой тайной. В большинстве работ предполагается, что исследуемые объекты являются статическими, а структура кластеров меняется за счёт появления или исключения объектов. Несмотря на важные результаты, полученные перечисленными авторами, задача кластеризации таких динамичных объектов, как ИП и ИР

с целью персонализации поиска остается нерешённой.

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

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

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

Цель и задачи работы. Целью диссертационной работы является применение методов классического кластерного анализа для классификации ИП и ИР, доя персонализации информационного поиска в Интернете. Для достижения поставленной цели требуется решить следующие основные задачи.

1. Проанализировать существующие некластерные методы классификации ИП и ИР. Проанализировать существующие методы кластерного анализа ИП и ИР, выявить их преимущества и недостатки по отношению к некластерным методам классификации.

2. Предложить адекватное математическое описание объектов исследо-

вания — ИП и ИР, обеспечивающее применение существующих алгоритмов кластеризации и их компьютерную реализацию.

3. Выбрать алгоритм кластеризации ИП и ИР из числа известных методов кластерного анализа, позволяющий управлять результатом с помощью ограниченного набора существенных входных параметров.

4. Определить масштаб влияния информационной динамики Интернет-объектов на результаты их кластерного анализа. Предложить методы устранения динамических факторов при кластеризации ИП и ИР.

5. Разработать и применить подход, основанный на оригинальном принципе обобщения и одновременной кластерной обработки ИП и ИР.

6. Разработать программные средства для наблюдения за активностью ИП, сбора данных о ИР, кластеризации ИП и ИР, а также для оценки эффективности предлагаемых методов.

7. Оценить эффективность применения предлагаемых методов для пер-сонализации Интернет-поиска, с точки зрения релевантности получаемых ИП данных.

8. Разработать структуру системы персонализации поиска, использующей предлагаемые методы классификации ИП и ИР.

Объект и предмет исследования. Объектом исследования являются методы персонализации Интернет-поиска, основанные на изучении и классификации ИП и ИР при помощи кластерного анализа.

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

Научная новизна диссертации заключается в следующем.

1. Предложены оригинальные методы снижения влияния динамических компонентов ТЮМ-модели ИР на стабильность кластерной структуры: метод числовых коэффициентов усиления и метод трёхтактной кластеризации с обратной связью.

2. Дано математическое описание и исследована кластерная структура ИП и ИР как результата применения обобщенного способа векторного пред-

ставления этих объектов — единый словарь терминов, обобщённый характеристический вектор и совместная кластеризация.

3. Разработан способ структуризации данных, получаемых из поисковых историй ИП и контента ИР, предложена структура базы данных, хранящей соответствующую информацию.

Теоретическая и практическая значимость работы. Задача классификации ИП и ИР достаточно хорошо изучена. В коммерческих целях широко применяются некластерные методы классификации ИП, основанные на статической информации, и ассоциативные методы классификации ИР. Однако эти методы не учитывают интересы ИП, а качество классификации динамичных ИР оставляет желать лучшего. Существующие методы кластеризации текстов не берут во внимание особенности современных ИР - не учитываются динамические компоненты их /ЗОМ-моделей. Следует обратить внимание на тот факт, что кластеризация ИП и ИР сейчас проводится раздельно. Предлагаемый в диссертации метод обеспечивает новый подход и дает перспективную математическую модель обобщения ИП и ИР, позволяя представлять их как единый объект исследований. Изложенный в работе метод может быть применён не только для персопализации Интернет-поиска, но и для решения широкого круга задач, где имеется взаимодействие автоматизированной системы с множеством подобных субъектов, которых необходимо классифицировать в соответствии с их предпочтениями.

В диссертации разработаны и программно реализованы методы, обеспечивающие применение алгоритмов кластерного анализа для персонализации поиска в Интернете. Одна часть программных средств, поддерживающих предлагаемые методы, реализована на языке С# в среде Microsoft Visual Studio 2010 в виде соответствующего набора инструментов и инфоботов, позволяющих запускать и выполнять задания по получению текстового содержания ИР и сканирования их DOM-атруктур, а также отслеживать поисковую активность ИП. Другая часть программных средств реализована на языке T-SQL в среде Microsoft SQL Server 2012. Этими средствами поддерживается вся аналитическая часть проекта, выполняется кластеризация Интернет-объектов. Используя указанные инструменты, эксперт-аналитик на основе результатов кластерного

анализа получает чёткую картину распределения ИП и ИР по кластерам в зависимости от таких параметров, как продолжительность периода наблюдения, число кластеров, величина коэффициентов усиления и минимальная длина терминов. При достаточно низком (< 40%) показателе коэффициента попадания в целевую группу он (эксперт) может принять решение о целесообразности выполнения кластеризации с новыми входными параметрами. В случае, когда указанный показатель становится чересчур высоким (> 60%), эксперт может зафиксировать входные параметры и запустить в автоматическом режиме кластеризацию объектов на более длительный период. Предложенный подход безусловно требует значительных вычислительных затрат, но при наличии локального дата-центра или корпоративного грида может дать существенную отдачу, повысив уровень персонализации Интернет-поиска. Таким образом, в диссертационной работе.наряду с указанными выше методами, предложен целостный подход к их практическому использованию.

Методология и методы исследования. В основе диссертационного исследования лежат методы статистического и кластерного анализа, теория графов, web mining и web-технологии. При проведении исследований и при изложении полученных материалов применяется систематический подход, базирующийся на анализе натурных экспериментальных результатов. На каждом этапе работы, после проведения сравнительного анализа полученных результатов, делаются выводы и выбираются наиболее рациональные подходы для продолжения исследований.

Положения, выносимые на защиту.

1. Метод снижения влияния динамических элементов £)ОМ-модели ИР, основанный на применения числовых коэффициентов усиления. Анализ состояния кластерной структуры с помощью показателя степени принадлежности объектов к кластерам.

2. Метод трёхтактной кластеризации ИР с обратной связью, основанный на выявлении динамических элементов ZJOM-модели с последующим исключением их контента из кластерного анализа.

3. Математическое описание объектов исследования с применением обобщенного способа их векторного представления - единый словарь терми-

нов, обобщённый характеристический вектор и совместная кластеризация.

4. Способ структуризации данных, определяющий структуру базы данных, хранящей информацию о поисковой активности ИП, содержимом запросов ИП и контенте страниц ИР.

Степень достоверности и апробация результатов.

Основные результаты диссертационного исследования обсуждались на научно-практических конференциях, среди которых: VI International research and practice conference «European Science and Technology» {Munich, 2013), IV International research and practice conference «Science, Technology and Higher Education» (Westwood, 2014), Международная научно-практической конференция «Инновационное развитие современной науки» (Уфа, 2014) и Международная научно-техническая конференции «Тенденции и инновации современной науки» (Краснодар, 2014).

Положения и результаты диссертационной работы использовались в производственной деятельности компании ТНС Гэллап Эдфакт при обработке нестандартных рекламных баннеров с последующей кластеризацией динамических компонентов, принадлежащих одному баннеру, но полученных в разные моменты времени, что подтверждается актом о внедрении.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена обзору существующих подходов и методов как некластерной, так и кластерной классификации объектов. Эти методы широко используются во многих отраслях, в том числе и в Интернет-индустрии.

Дан детальный обзор применения информации о пользователях и их активности в социальных сетях для решения задач персонализации поиска. Приведены примеры использования статической пользовательской информации. Продемонстрированы ассоциативный метод и метод пересечений для

подбора товаров в Интернет-магазинах, когда анализируется содержимое

s

товарных корзин определенного множества покупателей и определяется вероятностная закономерность покупок. Продемонстрирован метод частоты терминов (7У-метод), широко применяемый для классификации статичных текстов. Эти некластерные методы могут быть использованы для предварительной сегментации ИП и ИР до их кластеризации.

Кластеризация — это автоматическое разбиение элементов некого множества на группы (кластеры) в зависимости от показателей их схожести. Различают иерархическую (дивизивную и агломеративную) и итерационную (метод Аг-средних, метод Форель и другие) кластеризацию. В наши дни методы кластерного анализа применяются для решения широкого спектра задач в Интернете. Кластерные методы со сложными алгоритмами оптимизации применяются в поисковых системах, Интернет-магазинах, системах анализа контента сайтов, системах проверки подлинности текстов диссертаций и ещё во многих сферах.

Говоря о кластеризации Интернет-объектов, необходимо определить такое базовое понятие, как объект кластеризации. Объект — элементарная единица, которая может быть представлена с помощью набора (вектора) числовых характеристик и с которой оперируют алгоритмы кластеризации. Каждому объекту х, из множества X, сопоставляется вектор числовых характеристик г, = (г/>Г, .„, ..., Кардинальность вектора п определяет размерность пространства характеристик 2. Расстояние г*) между объектами х( и х* — результат применения выбранной метрики в пространстве характеристик. В диссертационной работе в качестве метрики пространства 2 выбрано евклидово расстояние.

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

Лингвистический анализ — метод исследования текста, который может быть охарактеризован как лингвосмысловой анализ, т.к. позволяет «понимать» текст и извлекать из него необходимую информацию. Существует множество подходов к лингвистическому анализу. Среди них можно выделить статистический анализ, анализ признаков, семантический анализ и комбинированный

подход. В диссертации применяется комбинированный подход, основанный на статистическом методе, методе анализа признаков и особенностей БОМ-модели ИР.

На рисунке 1 представлены этапы процесса очистки запросов ИП и текстового содержания ИР от первичного «грязного» текста до набора лемм. Результатом выполнения этого процесса является формирование статистики лемм и наращивание словаря с помощью лингвистического эксперта. Так как на этапе выполнения рассматриваемого процесса происходит полный перебор слов поискового запроса ИП или/и текста ИР, то целесообразно

здесь же проводить подсчет встречаемости слов в тексте, применяя известные статистические методы (подсчёт число вхождений, 77*' или другие). Затем, на основании полученной информации, могут быть сформированы характеристические вектора классифицируемых Интернет-объектов и глобальный словарь терминов, с которыми будут дальше работать алгоритмы кластерного анализа.

В третьей главе подробно рассматриваются динамические явления (образование новых кластеров, слияние кластеров, расщепление или дробление кластеров, исчезновение кластеров, перемещение центров кластеров) в кластерной структуре и причины их возникновения. С целью снижения влияния динамических факторов на кластеризацию ИП предлагается метод скользящего временного окна, т.е. в иоД К,,)-мерном пространстве при анализе кластерной структуры должны учитываются только объекты, зафиксированные в

Интернет-ресурс или запрос Интернет-ользователя

Поручение

грязного содержания Интернет-страницы

Получение грязного содержания терминов

Получение отфильтрованы

ых терминов

Внешние словари Лингвистический эксперт

Рисунок 1 - Процесс лингвистической обработки запросов Ш1 и текстов ИР

последнем временном окне Atk (здесь и далее Vu - глобальный словарь терминов, используемых ИП). С этой же целью для ИР предлагаются два новых метода — метод, базирующийся на применении числовых коэффициентов усиления, и метод трёхтактной кластеризации Интернет-ресурсов с фильтрацией, основанной на анализе их DOM-моделей.

В любой момент времени можно оценить состояние кластерной структуры с помощью коэффициента принадлежности «-ого объекта к т-ому кластеру с помощью мер сходства или слияния кластеров, мер компактности кластеров и других показателей. Например, для ИП коэффициент принадлежности bin(tk) объекта usr^USR с характеристическим вектором u,{tk) к кластеру Um(tk) из кластерной структуры K(tk) в произвольный момент времени наблюдения tk е Т, завершающего временное окно Atk, рассчитывается по формулам

^ по} (%,,))

= (1) и 2>„Ж)= 1 (2),

т=1

где

(p(u,(K),eJtk))

{piuXQMh))1 J

■ naj{K(t¿)) - число кластеров в кластерной структуре;

-оЛМ'»)) ,

P("i(ek)>em(0)=J - евклидово расстояние между

К®»

t

i

характеристическим вектором u¡{tk) и центром em(tk) m-ого кластера кластерной структуры ИП.

Сказанное подразумевает, что каждому пользователю usr¡ eUSR сопоставлен характеристический (поисковый) вектор имеющий вид:

u,(h) = («ufe). • ■ •. uij{tk),..., щ„оЛУ<,0)Ю), (3)

где

- u¡j{tk) — числовая координата, соответствующая j-му поисковому термину глобального словаря V,¡(í¿). Значение u¡/tk) равно числу вхождений данного термина в запросы í-ro пользователя, наблюдаемого в течение временного окна Atk. Числовые координаты ufJ(tk), 1 <j<nqf{Vu), расположены в характеристическом векторе в том же порядке, что и термины в словаре Vv(tk). Переход от вербального к числовому представлению результатов поисковой активности ИП происходит за счет позиционного кодировании терминов и

11

подсчёта числа их вхождений в запросы пользователя в течение окна наблюдений;

- ио/[ ?"„(?*)) - размер поискового вектора 1-го пользователя, равный числу слов в глобальном словаре терминов в момент времени

В ходе натурного эксперимента со случайно выбранным ИП, принадлежащим возрастной группе от 18 до 44 лет и проживающим в Москве (самая активная группа ИП), были получены следующие значения коэффициента принадлежности в разные моменты времени (таблица 1).

Таблица 1 - Коэффициенты принадлежности Интернет-пользователя к кластерам

в разные моменты времени

Кластер N. Um временя (f»)Nv V, V, и3 V,, Кластер V« Момент времени (ft) \ Vi £/> иг о.

/о=8 0 0 0 0 20 0 0 0 0

9 0 0 0 0 21 0 0 0 0

1fr 0,5104 0,2713 0,0597 0,1586 22 0,2007 0,5915 0,1928 0,0150

11 0,6061 0,1870 0,1559 0,0510 23 0,4092 0,4497 0,1294 0,0117

12 0,1775 0;1297 0,2011 0,4917 24 0,3907 0,3057 0,0937 0,2099

13 0,1896 0,1582 щщ 0,2563 1 0 0 0 0

14 0,0436 0,1192 0,2381 2 0 0 0 0

15 0,0574 0,0857 даяя 0,3056 3 0 0 0 0

16 0,1601 0,2294 0,2614 4 0 0 0 0

17 0,2151 0,1697 0,2967 0,3185 5 0 0 0 0

18 0,0653 0,1196 0,4892 0,3259 б 0 0 0 0

19 0,2448 0,0674 0,4691 0,2187 7 0 0 0 0

В результате анализа таблицы 1 можно сделать вывод о том, что максимальная продолжительность принадлежности ИП к одному кластеру не превышает 4-х часов.

По аналогии с ИП сформируем множество наблюдаемых ИР RES, посещенных ИП из USR в течение временного окна Л tk.

В произвольный момент времени 4 ;-й наблюдаемый ресурс можно представить характеристическим вектором w,(tk) следующего вида:

W/frt) = (w/,i(ii),..Wij(tk),..wLnoAV<tk))(t^), (4)

где

- Wi/tk) — числовая координата, соответствующая j-му термину глобального словаря Vy£tk)B момент времени tk. Значение wtJ{t^ равно числу вхождений данного термина в текст /-го ресурса, наблюдаемого в течение временного

12

окна Atk-

Дня работы с текстовым содержанием ИР используются DOM-иодепи их страниц. Document Object Model (DOM) - объектная модель Интернет-документа, позволяющей получить доступ к текстовому содержимому, как статических, так и динамических (содержащих динамические компоненты) страниц наблюдаемых ресурсов.

Длительные наблюдения показали, что для DOM-моделей ресурсов характерна периодичность, то есть через nxtk моментов времени текстовое содержание этих ресурсов повторяется.

Учитывая особенности £)ОМ-моделей страниц Интернет-ресурса, каждому элементу вектора w,(tk) предлагается сопоставить весовой коэффициент, рассчитываемый по формуле

где пЖ- общее число слов в ЮОМ-модели страницы; м>р - число вхождений слова на р-оа позиции в конкретном тэге £>ОМ-модели страницы; - коэффициент усиления (к\ >1), значение которого рассчитывается, исходя из наименования тэга, определяющего контекст слова на странице; к2 - коэффициент усиления (к2 >1), значение которого рассчитывается как отношение площадей, занимаемых словами на странице:

где Sp - площадь области на р-ой позиции; cntp — число слов на /7-ой позиции; Stotai— площадь информационного текста.

Расчеты коэффициентов принадлежности случайного ИР rest е RES, проведенные без применения и с применением числовых коэффициентов усиления, иллюстрированы рисунком 2. Использование коэффициентов усиления, построенных на основании DÖM-модели, приводит к сдвигу расчетного коэффициента принадлежности в сторону одного из кластеров (график для кластера Щ). Остальные графики смещаются вниз.

(6)

Рисунок 2 - Графики коэффициентов принадлежности ИР для разных кластеров в разное время суток без применения (слева) и с применением (справа) коэффициентов усиления

Для подавления влияния динамических компонентов ИР предлагается итерационный метод кластеризации ИР с применением /)£Ж-фильтрации (рисунок 3). Проведенное исследование показало, что система достигает стабильного состояния за конечное число наблюдений N » 5. Эта величина может быть использована в качестве признака насыщения словаря. Для разных страниц одного и того же сайта величину N можно считать константой.

На вход схемы (рисунок 3) поступают ТЛИ-адреса Интернет-страниц -объектов кластеризации. Задачей первого блока является .ООМ-фильтрация -выявление компонентов БОМ-модели страницы с динамическими признаками и их удаление. Второй блок отвечает за формирование характеристического вектора на основе анализа исключительно статических компонентов йОМ-модели Интернет-страницы. Третий блок осуществляет кластеризацию объек-

Рисуиок 3 — Схема трехтактной кластеризации динамичных ИР

Применение этого метода повышает точность результата кластеризации (рисунок 4), так как сразу удаляются «мусорные» динамические компоненты страниц, которые перестают участвовать в кластеризации.

Применение трёхтактной схемы кластеризации приближает исследуемый ИР к кластеру W2, повышает значение степени принадлежности ресурса к релевантному кластеру примерно на 25%. Степень принадлежности ресурса к другим, менее релевантным кластерам кластерной структуры, уменьшается.

В четвертой главе предлагается подход к обобщению Интернет-объектов на базе вводимого здесь же понятия обобщённого характеристического вектора. Результаты интерпретируются с использованием графовой модели. В обобщённой модели кластеризации, исследуемые объекты (ИП и ИР) рассматриваются как единое множество. Для них формируется обобщённый характеристический вектор X, получаемый путём объединения текстов поисковых запросов ИП с текстовым содержимым ИР и формирования обобщённого словаря терминов V(tk) = Vu{tk)\jVw(tk).

Пусть OB = USRvjRES - множество наблюдаемых объектов и obi 6 ОВ. В произвольный момент времени tk е Г можно сформировать обобщённый характеристический вектор ¿-го объекта. По аналогии с характеристическими векторами ИП u,{tk) и ИР w,{tk) характеристический вектор для обобщённого объекта будет иметь вид:

х,(Тк) = (xa(tk),...,Xijih),..., xi:„„m,k))(tk)) (7)

Пусть в nofij0-мерном пространстве X задано расстояние между характеристическими векторами. Вектора множества X могут рассматриваться, как вершины графа, а расстояние между этими векторами - как веса ребер графа. Получаем полносвязный неориентированный граф С? = (X, Е* ), в котором X -множество вершин, - множество ребер. Для каждого ребра графа (х,-, х?) = ехг,г е Ех задан неотрицательный вес ftftjr) равный евклидову расстоянию между векторами хе и х,--

Степени принадлежности HP к кластерам до и послепрюшнешш трехтактной кластертацип

Рисунок 4 - Степени принадлежности ИР кластерам

ТТЛ П TTr»tf4Ti* г[ч11X..'[¡/.IJIJ(t !'lf}\ f_i}irriT :ч\'.:гии

В отличие от комбинированной модели, когда ИП и ИР исследуются и кластеризуются отдельно, в обобщённой модели нет необходимости рассчитывать веса вершин графа, представляющего пространство характеристических векторов ИП, рассчитываются только веса рёбер. Расчёт длины кратчайшего пути по алгоритму Дейкстры не изменится, однако общая протяженность пути будет зависеть исключительно от меры близости (евклидова расстояния) между объектами, так как у вершин отсутствуют веса. Размерность пространства, в котором расположены характеристические вектора обобщенных объектов, может сократиться почти в два раза.

Рассматриваемый подход делает Интернет-ресурсы более «социальными»: ресурсы, ассоциированные с одними пользователем, могут предлагаться другим ИП, относящимся к тому же кластеру.

Пятая глава посвящена разработке обобщённой структуры корпоративной системы персонализации поиска (KCl 111) на предприятии, обслуживающей множество однородных групп пользователей, имеющих схожие поисковые интересы (например, бухгалтеры, финансисты, маркетологи и т.д.). Здесь представлены результаты комплексного исследования результатов кластерного анализа с разными входными параметрами, а также сравнение результатов персонализированного поиска корпоративной системы с результатами поисковой системы Яндекса.

Обобщенная структура КСПП содержит множество программных модулей и хранимых процедур, реализованных с использованием Microsoft Visual Studio 2010 и Microsoft SQL Server 2012, соответственно. Одна часть программных модулей должна быть установлена на клиентских ПК конечных пользователей, другая часть - на корпоративных серверах предприятия.

Процесс кластеризации полностью автоматизирован и не требует никакого стороннего вмешательства. Эксперт-аналитик, анализирующий текущие результаты кластерного анализа, имеет возможность контролировать такие параметры процесса, как число кластеров в кластерной структуре, размер временных интервалов наблюдения за активностью ИП и мера близости объектов кластеризации. Для оценки качества кластеризации целесообразно применять показатель Та - процент попадания в целевую группу:

Та =

xlOO

(8)

CNT_UM(tk)

где CNT_UTargele/tM) - число ИП, для которых определен хотя бы один подходящий ИР в момент времени CNT_UAli(tk) - число ИП, участвовавших в кластер-анализе в момент времени t/c.

Для расчета процента попадания в целевую группу, в числителе используется число уникальных пользователей, для которых после кластеризации удалось угадать посещение хотя бы одного ИР в следующем периоде наблюдения, в знаменателе - общее число наблюдаемых пользователей. Результаты экспериментов представлены в таблице 2.

Таблица 2 - Результаты кластерного анализа

Входные параметры эксперимента Результаты

Число кластеров Дt (час) Та

2 4 38.499%

3 4 43.111%

4 4 43.617%

5 4 43.782%

4 1 63.799%

Результаты экспериментов демонстрирует существенное влияние значений входных параметров на качество кластеризации ИП и ИР. Это также указывает на важную роль, которую может играть опытный эксперт, регулирующий значения входных параметров в процессе кластеризации.

Для сравнения результатов работы поисковой системы Яндекса с результатами применения предлагаемой системы кластерного анализа (рисунок 5) была промоделирована ситуация, когда четыре ИП, интересующиеся разными сущностями, обозначаемыми термином «ягуар», осуществляли Интернет-поиск. Эти ИП выполняли заходы на определенное число ИР,

отвечающих их инте-

Гистограмма точности попадания

1 1

■ j

впав i

0,200 0,400 0,600 0,800

»Точность попадания после кластеризации ■ Точность попаданий яндекса (для первых 50 гиперссылок}

1,000

Рисунок 5 - Гистограмма точности попадания

ресам. Исходя из поисковой активности ИП и с учетом посещаемых ими ИР, формировались характеристические вектора ИП и затем строились первые

средние 4-х кластеров. Получив конечный результат распределения объектов по кластерам, рассчитывались наиболее важные коэффициенты, отражающие качество полученного результата. Для оценки качества применялись следующие показатели: точность попадания (см. рисунок 5), полнота и выпадение. Следует обратить особое внимание на тот факт, что полнота выборки и выпадение не мотуг быть представлены в качестве опорных показателей в условиях рассматриваемого эксперимента, так как в нем сравнительный анализ проводился на достаточно ограниченном числе ИР.

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

ЗАКЛЮЧЕНИЕ

В процессе работы над диссертацией лично автором получены следующие результаты:

1. Предложена и реализована процедура лингвистической обработки текстов, основанная на использовании двухуровневого словаря терминов и лемм с возможностью применения открытых словарей. При необходимости предусмотрена возможность обращения к «лингвистическому эксперту» для лемматизации новых, не включенных в словарь терминов.

2. Для достижения стабильности кластерной структуры и устранения динамического эффекта, разработан метод наблюдения за ИП, основанный на применения временного окна. С этой же целью для наблюдения за ИР разработан метод анализа содержания (сканирования) ИОМ-модели ресурса с последующим применением числовых коэффициентов усиления.

3. С целью выявления и фильтрации динамических компонентов ИОМ-модели предложена трёхтактная схема кластеризации ИР с обратной связью. Реализация схемы позволяет превращать динамичные ИР в статические ИР, применять к последним существующие алгоритмы кластерного анализа.

4. Предложен способ формирования характеристических векторов ИП и

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

5. Введено понятие обобщённого Интернет-объекта, применение которого позволяет проводить совместный кластерный анализ как ИП, так и ИР. Унификация объектов наблюдения делает кластерный анализ более транспа-рентным и глобальным. Информация об ИП, в зависимости от их интересов, может храниться вместе с информационно-релевантными ей данными об ИР.

6. Разработан набор программных модулей (программная система) для слежения за активностью ИП и получения текстового содержания ИР с учётом их DOM-моделей. В среде MS SQL Server 2012 разработаны хранимые процедуры, выполняющие все необходимые расчёты - от формирования словарей терминов до конечного распределения объектов по кластерам.

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ АВТОРОМ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК РФ.

1. Зейн А.Н., Мороховец Ю.Е. Персонализация поиска: статическая или динамическая кластеризация? // Журнал «Вестник МЭИ». - М.: Издательство МЭИ. - 2014. - № 2. - С. 76-81.

2. Мороховец Ю.Е., Зейн А.Н. Трехтактная кластеризация динамичных Интернет-ресурсов с применением DOM-моделей. // Международный журнал

«Программные продукты и системы». - Тверь: НИИ Центрпрограммсистем. — 2014. - № 3. - С. 58-63. URL: http://swsys.m/mdex.php?page=article&id =3861 (01.12.2014 г.).

Публикации в других изданиях.

1. Зейн А.Н. Статические и динамические явления в кластерной структуре Интернет-объектов. Н Сборник научных трудов «Новый взгляд. Международный научный вестник». Выпуск 2. - Новосибирск: ЦРНС. - 2013. - С. 51-60.

2. Zein А. N. Clusterization of web-sites using numeric coefficients based on DOM-model. If Materials of the VI international research and practice conference «European Science and Technology». Vol. 2. - Munich: Vela Verlag Waldkraibttrg. -2013. -PP. 372-375.

3. Зейн A.H. Динамическая активность Интернет-ресурсов в кластерной структуре. // Сборник статей Международной научно-практической конференции «Инновационное развитие современной науки». - Уфа: РИЦ БашГУ. -2014.-С. 123-127.

4. Зейн А.Н. Интернет-ресурсы: новый подход для оптимизации результатов поиска. // Материалы ХП международной научно-технической конференции «Тенденции и инновации современной науки». - Краснодар: Априори. -20Î4.-С. 54.

5. Зейн А.Н. Персонализация поиска: кластеризация Интернет-пользователей и Интернет-ресурсов. // Электронный журнал «Вычислительные сети: теория и практика». - М.: НИУ МЭИ, - 2014. - №1. URL: http^/networfc-joimiaI.mpei.ac.ni/cgi-bm/main.pl?l=TO&n===24&pa=6&ar=l (1.12. 2014 г.).

Подписано в печать Заказ â ¿1 Тир. ? О Печ.л. uf Полиграфический центр ФГБОУ ВПО «НИУ МЭИ» Красноказарменная ул., д. 13