Презентация Классификация и кластеризация документов доклад по теме Информатика

Вашему вниманию предлагается доклад и презентация по теме Презентация Классификация и кластеризация документов. Данны материал, представленный на 30 страницах, поможет подготовится к уроку Информатика. Он будет полезен как ученикам и студентам, так и преподавателям школ и вузов. Вы можете ознакомиться и скачать этот и любой другой доклад у нас на сайте. Все материалы абсолютно бесплатны и доступны. Ссылку на скачивание Вы можете найти вконце страницы. Если материал Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте сайт в закладки в своем браузере.
Страница #1
Классификация и кластеризация документов
Страница #2
Что такое классификация?
Объединение документов или их представлений в одну группу, которая в дальнейшем может рассматриваться и использоваться как единая сущность
Сами группировки могут определяться заранее либо формироваться алгоритмически
Процесс группировки может выполняться вручную либо автоматически
Полезность классификации заключается в том, что элементы группировки могут с большой вероятностью оказаться релевантными
Что такое классификация? Объединение документов или их представлений в одну группу, которая в дальнейшем может рассматриваться и использоваться как единая сущность Сами группировки могут определяться заранее либо формироваться алгоритмически Процесс группировки может выполняться вручную либо автоматически Полезность классификации заключается в том, что элементы группировки могут с большой вероятностью оказаться релевантными
Страница #3
Автоматическая классификация
Два способа:
на основе заранее заданной схемы классификации и уже имеющегося множества классифицированных документов
полностью автоматизированная кластеризация
Автоматическая классификация Два способа: на основе заранее заданной схемы классификации и уже имеющегося множества классифицированных документов полностью автоматизированная кластеризация
Страница #4
Использование автоматической классификации при информационном поиске
Фильтрация входящих документов
Сжатие информации (аннотирование, реферирование)
Расширение запросов за счет характеризующих тематику класса терминов
Реализация обратной связи по релевантности путем предварительной классификации результатов выборки по классам и выбора  пользователем релевантных классов
Снятие омонимии путем отображения слов в обобщенные концепты
Увеличение эффективности поиска путем сведения к поиску классов
(Полу-)автоматическое структурирование порталов – автоматическое формирование тематических каталогов.
Использование автоматической классификации при информационном поиске Фильтрация входящих документов Сжатие информации (аннотирование, реферирование) Расширение запросов за счет характеризующих тематику класса терминов Реализация обратной связи по релевантности путем предварительной классификации результатов выборки по классам и выбора пользователем релевантных классов Снятие омонимии путем отображения слов в обобщенные концепты Увеличение эффективности поиска путем сведения к поиску классов (Полу-)автоматическое структурирование порталов – автоматическое формирование тематических каталогов.
Страница #5
Классификация вручную. Эксперимент.
10 человек, 5 запросов
Наиболее частые запросы с существенно различающимися терминами
Количество документов по каждому запросу: 15, 16, 16, 11, 10
6 человек работали только с заголовками и URL, остальные 4 – с полными текстами документов
Ставилась задача разбить документы на минимально пересекающиеся классы; ограничение по времени отсутствовало.
Классификация вручную. Эксперимент. 10 человек, 5 запросов Наиболее частые запросы с существенно различающимися терминами Количество документов по каждому запросу: 15, 16, 16, 11, 10 6 человек работали только с заголовками и URL, остальные 4 – с полными текстами документов Ставилась задача разбить документы на минимально пересекающиеся классы; ограничение по времени отсутствовало.
Страница #6
Классификация вручную. Результаты эксперимента.
Наблюдается разброс в результатах классификации документов разными людьми
Степень подобия между результатами разных людей очень маленькая
Люди склонны создавать очень маленькие классы
Использование полного текста документа значительно помогает при классификации, при этом получается меньше классов, но они в большей степени пересекаются
Человек склонен привязывать результат классификации к контексту
Классификация невозможна без знания смысла запроса
Классификация вручную. Результаты эксперимента. Наблюдается разброс в результатах классификации документов разными людьми Степень подобия между результатами разных людей очень маленькая Люди склонны создавать очень маленькие классы Использование полного текста документа значительно помогает при классификации, при этом получается меньше классов, но они в большей степени пересекаются Человек склонен привязывать результат классификации к контексту Классификация невозможна без знания смысла запроса
Страница #7
Кластеризация
Основой методов кластеризации является кластерная гипотеза (C.J. van Rijsbergen), которая гласит:
	Тесно связанные между собой документы оказываются релевантными по отношению к тем же запросам.
Кластеризация может быть использована для распределения документов в коллекции по классам (классификации), что позволяет повысить скорость поиска документов и точность ответа.
Кластеризация включает в себя две процедуры: генерацию кластеров и поиск кластеров по запросу пользователя.
Кластеризация Основой методов кластеризации является кластерная гипотеза (C.J. van Rijsbergen), которая гласит: Тесно связанные между собой документы оказываются релевантными по отношению к тем же запросам. Кластеризация может быть использована для распределения документов в коллекции по классам (классификации), что позволяет повысить скорость поиска документов и точность ответа. Кластеризация включает в себя две процедуры: генерацию кластеров и поиск кластеров по запросу пользователя.
Страница #8
Кластеризация. Предыстория.
Fairthorne  “The Mathematics of Classification” (1961)
Эксперименты Марона (1961), Борко и Берника (1963)
Работы по численной таксономии и ее приложениям при информационном поиске – Джардайна (Jardine), Сибсона, ван Рийсбергена, Сэлтона (1970). Кластеризация рассматривалась исключительно с точки зрения эффективности поиска нежели в семантическом аспекте.
Интерес к кластеризации утрачен в 80-х годах, возрождение интереса в 90-х годах в приложениях, связанных с навигацией и обработкой данных.
Работа Спарк-Джонс по кластеризации терминов.
Кластеризация. Предыстория. Fairthorne “The Mathematics of Classification” (1961) Эксперименты Марона (1961), Борко и Берника (1963) Работы по численной таксономии и ее приложениям при информационном поиске – Джардайна (Jardine), Сибсона, ван Рийсбергена, Сэлтона (1970). Кластеризация рассматривалась исключительно с точки зрения эффективности поиска нежели в семантическом аспекте. Интерес к кластеризации утрачен в 80-х годах, возрождение интереса в 90-х годах в приложениях, связанных с навигацией и обработкой данных. Работа Спарк-Джонс по кластеризации терминов.
Страница #9
Кластеризация. Методы.
Кластеризация – удобный инструмент при работе с документальным пространством, имеющим, как правило,  высокую размерность.
Среди автоматических методов кластеризации выделяют следующие:
Методы иерархической кластеризации 
Методы кластеризации, основанные на разбиении множеств.
Гибридные методы.
Кластеризация. Методы. Кластеризация – удобный инструмент при работе с документальным пространством, имеющим, как правило, высокую размерность. Среди автоматических методов кластеризации выделяют следующие: Методы иерархической кластеризации Методы кластеризации, основанные на разбиении множеств. Гибридные методы.
Страница #10
Методы кластеризации. 
Критерии адекватности.
Обработка вновь поступающих документов не должна существенным образом изменять результат кластеризации
Устойчивость: незначительные ошибки в описании объектов могут вызывать также незначительные изменения в результатах кластеризации
Независимость результата кластеризации от исходного порядка на множестве объектов
Выполнение этих критериев не является обязательным во всех приложениях
Методы кластеризации. Критерии адекватности. Обработка вновь поступающих документов не должна существенным образом изменять результат кластеризации Устойчивость: незначительные ошибки в описании объектов могут вызывать также незначительные изменения в результатах кластеризации Независимость результата кластеризации от исходного порядка на множестве объектов Выполнение этих критериев не является обязательным во всех приложениях
Страница #11
Методы кластеризации, 
основанные на разбиении множеств
Целью является разбиение исходного множества из N документов на k кластеров. 
Из них можно выделить 
глобально оптимальные алгоритмы, которые  исчерпывающе перечисляют все разбиения 
эффективные эвристические методы, например метод К-средних.
Методы кластеризации, основанные на разбиении множеств Целью является разбиение исходного множества из N документов на k кластеров. Из них можно выделить глобально оптимальные алгоритмы, которые исчерпывающе перечисляют все разбиения эффективные эвристические методы, например метод К-средних.
Страница #12
Метод К-средних
Документы описываются векторами с вещественными компонентами
Каждый кластер идентифицируется с помощью центроида, который вычисляется как усредненный вектор от всех его элементов:
Далее происходит перераспределение документов по кластерам в зависимости от их расстояния до центроидов кластеров
Метод К-средних Документы описываются векторами с вещественными компонентами Каждый кластер идентифицируется с помощью центроида, который вычисляется как усредненный вектор от всех его элементов: Далее происходит перераспределение документов по кластерам в зависимости от их расстояния до центроидов кластеров
Страница #13
Алгоритм К-средних
Задается метрика d для вычисления расстояния между элементами множества.
Случайным образом выбираются k. зерновых элементов {s1, s2, …, sk}
До тех пор пока не выполнится условие остановки:
Для каждого элемента xi:
поместить xi в кластестер cj такой, что d(xi, sj) минимально
Сделать центроиды классов зерновыми элементами, т.е. для каждого кластера cj 
				sj=μ(cj)
Алгоритм К-средних Задается метрика d для вычисления расстояния между элементами множества. Случайным образом выбираются k. зерновых элементов {s1, s2, …, sk} До тех пор пока не выполнится условие остановки: Для каждого элемента xi: поместить xi в кластестер cj такой, что d(xi, sj) минимально Сделать центроиды классов зерновыми элементами, т.е. для каждого кластера cj sj=μ(cj)
Страница #14
Алгоритм К-средних
Возможное условие остановки цикла:
Количество итераций
Группировка документов по кластерам не изменяется
Позиции центроидов не изменяются
Временная сложность алгоритма O(n*log n)
Алгоритм К-средних Возможное условие остановки цикла: Количество итераций Группировка документов по кластерам не изменяется Позиции центроидов не изменяются Временная сложность алгоритма O(n*log n)
Страница #15
Метод К-средних
Недостатки:
Результат кластеризации зависит от выбора стартовых элементов.
Значение k выбирается вне алгоритма.
Кластеры не пересекаются (жесткая кластеризация), т.е. для документа исключена возможность принадлежности к нескольким кластерам одновременно.
Модификация: “мягкая” кластеризация.
Метод К-средних Недостатки: Результат кластеризации зависит от выбора стартовых элементов. Значение k выбирается вне алгоритма. Кластеры не пересекаются (жесткая кластеризация), т.е. для документа исключена возможность принадлежности к нескольким кластерам одновременно. Модификация: “мягкая” кластеризация.
Страница #16
Иерархическая 
аггломеративная кластеризация
Используется матрица сопряженности типа “документ-документ” (матрица подобия).
Начальное количество кластеров совпадает с исходным количеством документов, затем итерационно происходит объединение кластеров в суперкластеры по степени подобия.
В итоге получается один общий кластер, являющийся корнем древовидной структуры – дендограммы.
Иерархическая аггломеративная кластеризация Используется матрица сопряженности типа “документ-документ” (матрица подобия). Начальное количество кластеров совпадает с исходным количеством документов, затем итерационно происходит объединение кластеров в суперкластеры по степени подобия. В итоге получается один общий кластер, являющийся корнем древовидной структуры – дендограммы.
Страница #17
Иерархическая 
аггломеративная кластеризация
Иерархическая аггломеративная кластеризация
Страница #18
Иерархическая 
аггломеративная кластеризация
Порог принятия решения о подобии кластеров задается вне алгоритма.
Иерархическая аггломеративная кластеризация Порог принятия решения о подобии кластеров задается вне алгоритма.
Страница #19
Поиск кластера
Входной запрос представляется в виде t-мерного вектора и сравнивается с центроидами кластеров. 
Поиск продолжается в кластерах, степень подобия для которых превысила заданный порог.
Для вычисления степени подобия часто используется косинусная метрика.
Поиск кластера Входной запрос представляется в виде t-мерного вектора и сравнивается с центроидами кластеров. Поиск продолжается в кластерах, степень подобия для которых превысила заданный порог. Для вычисления степени подобия часто используется косинусная метрика.
Страница #20
Кластеризация в распределенных системах
Существует необходимость распределенного хранения документов в кластерной системе
По какому принципу распределять?
административным и т.п. способами;
по тематике.
Как определять тематику, если она заранее не задана?
	Решение – кластеризация.
Кластеризация в распределенных системах Существует необходимость распределенного хранения документов в кластерной системе По какому принципу распределять? административным и т.п. способами; по тематике. Как определять тематику, если она заранее не задана? Решение – кластеризация.
Страница #21
Подходы к кластеризации в распределенных системах
Вырожденный случай – единая система
Гетерогенные коллекции
кластеры построены заранее
Глобальная кластеризация
все помещается в общее хранилище и выполняется кластеризация
для каждого кластера строится тематическая модель
Локальная кластеризация
кластеризуется каждая из гетерогенных коллекций
внутри каждой коллекции формируются тематические модели для каждого полученного кластера (т.е. модель указывает на кластер внутри локальной коллекции)
Политематическое представление
кластеризуется каждая из гетерогенных коллекций
тематические модели для каждой из коллекций собираются вместе (т.е. модель указывает на коллекцию)
Подходы к кластеризации в распределенных системах Вырожденный случай – единая система Гетерогенные коллекции кластеры построены заранее Глобальная кластеризация все помещается в общее хранилище и выполняется кластеризация для каждого кластера строится тематическая модель Локальная кластеризация кластеризуется каждая из гетерогенных коллекций внутри каждой коллекции формируются тематические модели для каждого полученного кластера (т.е. модель указывает на кластер внутри локальной коллекции) Политематическое представление кластеризуется каждая из гетерогенных коллекций тематические модели для каждой из коллекций собираются вместе (т.е. модель указывает на коллекцию)
Страница #22
Выполнение запроса в распределенной системе
Выполнение запроса:
Ранжирование коллекций относительно запроса
Выбор n лучших коллекций
Выборка N лучших документов из каждой коллекции
Слияние списков из коллекций в общий список на основе показателя доверия
Выполнение запроса в распределенной системе Выполнение запроса: Ранжирование коллекций относительно запроса Выбор n лучших коллекций Выборка N лучших документов из каждой коллекции Слияние списков из коллекций в общий список на основе показателя доверия
Страница #23
Кластеризация в распределенных системах: выводы
Тематическая кластеризация эффективна для распределенного информационного поиска
Лучшие результаты получаются при глобальной тематической кластеризации, поскольку подобные документы оказываются вместе
При невозможности глобальной кластеризации относительно хорошим решением является локальный вариант, при этом
сохраняется административное распределение коллекций;
довольно большая нагрузка приходится на локальные сайты
Хорошим решением является множество тематик, указывающих на единую коллекцию:
это лучше чем модель единой системы
кластеризация и формирование моделей затрагивает только локальный сайт
в дальнейшем исключается нагрузка на сайты, содержащие коллекции
Кластеризация в распределенных системах: выводы Тематическая кластеризация эффективна для распределенного информационного поиска Лучшие результаты получаются при глобальной тематической кластеризации, поскольку подобные документы оказываются вместе При невозможности глобальной кластеризации относительно хорошим решением является локальный вариант, при этом сохраняется административное распределение коллекций; довольно большая нагрузка приходится на локальные сайты Хорошим решением является множество тематик, указывающих на единую коллекцию: это лучше чем модель единой системы кластеризация и формирование моделей затрагивает только локальный сайт в дальнейшем исключается нагрузка на сайты, содержащие коллекции
Страница #24
Классификация документов 
на основе гиперссылок
	Соседние в гиперссылочном графе документы могут содержать информацию, полезную при классификации:
На текущий документ Di может ссылаться другой документ Dj , содержащий высокоспецифичные термины, отсутствующие в самом документе Di 
На текущий документ Di может ссылаться другой документ Dj , содержащийся в релевантном разделе каталога, созданного вручную
На текущий документ Di может ссылаться другой документ Dj , содержащий ссылки также на многие другие документы, которые были использованы для настройки классификатора на релевантную тему (раздел каталога)
Классификация документов на основе гиперссылок Соседние в гиперссылочном графе документы могут содержать информацию, полезную при классификации: На текущий документ Di может ссылаться другой документ Dj , содержащий высокоспецифичные термины, отсутствующие в самом документе Di На текущий документ Di может ссылаться другой документ Dj , содержащийся в релевантном разделе каталога, созданного вручную На текущий документ Di может ссылаться другой документ Dj , содержащий ссылки также на многие другие документы, которые были использованы для настройки классификатора на релевантную тему (раздел каталога)
Страница #25
Использование свойств документов-соседей 
в графе гиперссылок
Идея: использовать при классификации термины и метки классов документов-соседей по графу
Подход 1:
описание документа расширяется за счет терминов документов-соседей, находящихся в графе в пределах радиуса r ≤ R (возможен учет расстояния r в виде весовой функции 1/r)
недостаток: чувствительность к смещению темы
Подход 2:
учет меток классов документов-соседей по графу в процессе классификации
Использование свойств документов-соседей в графе гиперссылок Идея: использовать при классификации термины и метки классов документов-соседей по графу Подход 1: описание документа расширяется за счет терминов документов-соседей, находящихся в графе в пределах радиуса r ≤ R (возможен учет расстояния r в виде весовой функции 1/r) недостаток: чувствительность к смещению темы Подход 2: учет меток классов документов-соседей по графу в процессе классификации
Страница #26
Модификация запросов
Переформулировка запроса
Расширение запроса
Добавление терминов в запрос для уточнения информационной потребности
Обратная связь
Оценка документов в выдаче как релевантных/нерелевантных
Представление результатов
Кластеризация выданных результатов
Модификация запросов Переформулировка запроса Расширение запроса Добавление терминов в запрос для уточнения информационной потребности Обратная связь Оценка документов в выдаче как релевантных/нерелевантных Представление результатов Кластеризация выданных результатов
Страница #27
Обратная связь по релевантности
Метод Rocchio:
где
Q0 – вектор начального запроса
Ri – вектор i-го релевантного документа
Si - вектор i-го нерелевантного документа
n1 – число выбранных пользователем релевантных документов
n2 - число выбранных пользователем нерелевантных документов
α,β,γ – параметры настройки
Обратная связь по релевантности Метод Rocchio: где Q0 – вектор начального запроса Ri – вектор i-го релевантного документа Si - вектор i-го нерелевантного документа n1 – число выбранных пользователем релевантных документов n2 - число выбранных пользователем нерелевантных документов α,β,γ – параметры настройки
Страница #28
Латентно-семантическое индексирование как кластеризация
LSI может рассматриваться как метод кластеризации (спектральная кластеризация) 
Вариант реализации для k кластеров:
Каждый элемент представляется точкой в k-мерном пространстве
Каждая точка проецируется на ось, соответствующую наибольшей по величине координате этой точки
Латентно-семантическое индексирование как кластеризация LSI может рассматриваться как метод кластеризации (спектральная кластеризация) Вариант реализации для k кластеров: Каждый элемент представляется точкой в k-мерном пространстве Каждая точка проецируется на ось, соответствующую наибольшей по величине координате этой точки
Страница #29
Литература
Литература
Страница #30
Литература
J. Xu, W.B.Croft "Cluster-based language models for distributed retrieval." In Proceedings of the 22nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 99), 1999. 
S. Chakrabarti	“Mining the Web. Discovering Knowledge from Hypertext Data”. Morgan Kaufmann Publishers, 2003.
S.Deerwester,S.T.Dumais,G.W.Furnas,T.K.Landauer,R.Harshman  “Indexing by Latent Semantic Indexing”. JASIS, 1990.
Литература J. Xu, W.B.Croft "Cluster-based language models for distributed retrieval." In Proceedings of the 22nd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 99), 1999. S. Chakrabarti “Mining the Web. Discovering Knowledge from Hypertext Data”. Morgan Kaufmann Publishers, 2003. S.Deerwester,S.T.Dumais,G.W.Furnas,T.K.Landauer,R.Harshman “Indexing by Latent Semantic Indexing”. JASIS, 1990.

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

Оставьте свой комментарий