Кошелева Виктория Андреевна |
Материалы по теме выпускной работы:
Реферат | Библиотека | Ссылки |
Отчет о поиске | Индивидуальное задание |
В настоящий момент работа находится в стадии разработки! Завершение разработок планируется на декабрь 2008 года. Окончательный результат работы можно получить, связавшись с автором. Содержание:
Наступивший XXI век станет этапным для проникновения новых информационных технологий и создаваемых на их основе высокопроизводительных компьютерных систем во все сферы человеческой деятельности - управление, производство, науку, образование и т.д. Конструируемые посредством этих технологий интеллектуальные компьютерные системы призваны усилить мыслительные способности человека, помочь ему находить эффективные решения так называемых плохо формализованных и слабоструктурированных задач, характеризующихся наличием различного типа неопределенностей и огромными поисковыми пространствами. Сложность таких задач усиливается зачастую необходимостью их решения в очень ограниченных временных рамках, например, при управлении сложными техническими объектами в аномальных режимах или при оперативном разрешении конфликтных (кризисных) ситуаций. Наибольшей эффективности современные интеллектуальные системы достигают при реализации их как интегрируемых систем, объединяющих различные модели и методы представления и оперирования знаниями, а также механизмы приобретения (извлечения) знаний из различных источников. Понятие «управление знаниями» родилось в середине 1990-х годов в крупных корпорациях, где проблемы обработки информации приобрели критический характер. Постепенно пришло понимание того, что знания — это фундаментальный ресурс, базирующийся на практическом опыте специалистов и на данных, существующих на конкретном предприятии. Компании, которые осознали ценность «знания» и наладили управление им, способны лучше использовать свои традиционные ресурсы, комбинировать их особыми способами, обеспечивая большую выгоду для потребителей, чем конкуренты. [4] Знания неявно стали одним из главных источников капитала. Цена акций может во много раз превышать их покрытие материальными активами компании-эмитента. Это особенно заметно в случае компаний так называемой новой экономики. Например, для акций компании Oracle соотношение цена/активы (рыночная капитализация, деленная на активы компании за вычетом долгов) составляет 17 к 1. Поэтому многие ведущие компании уже имеют в своем составе специального сотрудника — chief knowledge officer, — ответственного за создание инфраструктуры и культуры совместного использования знаний. Главная задача специалистов такого рода — вычленять, систематизировать и тиражировать интеллектуальный капитал внутри корпораций. Знания при этом воспринимаются как ресурс, а обеспечение ими налаживается по принципу just-in-time (точно вовремя), используемому при снабжении материальными ресурсами производственного процесса. Однако применяются эти знания не столько в производственных, сколько в управленческих процессах, предполагающих принятие стратегических и оперативных решений. [5] Тема извлечения знаний привлекает внимание учёных как в Европе, так и во всём мире. Изучением данной темы занимаются У. Файяд, Г. Пятетский-Шапиро, Т. Гаврилова, Л. Григорьев, П. Смит, Дж. Сейферт, В. Фроли, Ц. Матеус, Е. Монк, Б. Вагнер, С.Хааг и др. Data Mining переводится как «добыча» или «раскопка данных». Нередко рядом с Data Mining встречаются слова «обнаружение знаний в базах данных» (knowledge discovery in databases) и «интеллектуальный анализ данных». Их можно считать синонимами Data Mining. Возникновение всех указанных терминов связано с новым витком в развитии средств и методов обработки данных. [6] До начала 90-х годов не было особой нужды переосмысливать ситуацию в этой области. Все шло своим чередом в рамках направления, называемого прикладной статистикой. Теоретики проводили конференции и семинары, писали внушительные статьи и монографии, изобиловавшие аналитическими выкладками. Вместе с тем, практики всегда знали, что попытки применить теоретические экзерсисы для решения реальных задач в большинстве случаев оказываются бесплодными. Но на озабоченность практиков до поры до времени можно было не обращать особого внимания - они решали главным образом свои частные проблемы обработки небольших локальных баз данных. В связи с совершенствованием технологий записи и хранения данных на людей обрушились колоссальные потоки информационной руды в самых различных областях. Деятельность любого предприятия (коммерческого, производственного, медицинского, научного и т.д.) теперь сопровождается регистрацией и записью всех подробностей его деятельности. Что делать с этой информацией? Стало ясно, что без продуктивной переработки потоки сырых данных образуют никому не нужную свалку. Специфика современных требований к такой переработке следующие:
Традиционная математическая статистика, долгое время претендовавшая на роль основного инструмента анализа данных, откровенно спасовала перед лицом возникших проблем. Главная причина - концепция усреднения по выборке, приводящая к операциям над фиктивными величинами (типа средней температуры пациентов по больнице, средней высоты дома на улице, состоящей из дворцов и лачуг и т.п.). Методы математической статистики оказались полезными главным образом для проверки заранее сформулированных гипотез (verification-driven data mining) и для «грубого» разведочного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP). В основу современной технологии Data Mining (discovery-driven data mining) положена концепция шаблонов (паттернов), отражающих фрагменты многоаспектных взаимоотношений в данных. Эти шаблоны представляют собой закономерности, свойственные подвыборкам данных, которые могут быть компактно выражены в понятной человеку форме. Поиск шаблонов производится методами, не ограниченными рамками априорных предположений о структуре выборке и виде распределений значений анализируемых показателей. Целью магистерской работы является изучение различных методов извлечения знаний, построение оптимальной системы Data Mining, позволяющей разбивать набор данных, представленных реляционными базами данных на кластеры. Новизна магистерской работы заключается в том, что существующие системы кластеризации данных обладают недостатками: одни медленно работают с большими объёмами данных, однако дают качественную кластеризацию на маленьких наборах объектов, другие показывают хорошие результаты по скорости обработки данных, но при этом страдает качество. Таким образом, построение эффективной системы разбиения данных на кластеры является весьма актуальной задачей, ещё не до конца исследованной. Одним из основных подходов в «обнаружении знаний в данных» (Data Mining) является кластеризация. Кластеризация служит для объединения больших объемов данных в группы (кластеры), которые характеризуются тем, что элементы внутри каждой группы имеют больше «сходства» между собой, чем между элементами соседних кластеров. В целом, все методы кластеризации можно подразделить на иерархические и неиерархические. Последние чаще всего используются при анализе больших объемов данных, т.к. они обладают большей скоростью. [8] Кластерный анализ позволяет открыть в данных ранее неизвестные закономерности, которые практически невозможно исследовать другими способами и представить их в удобной для пользователя форме. Методы кластерного анализа используются как самостоятельные инструменты исследований, так и в составе других средств Data Mining (например, нейросетей). Кластерный анализ применяется для обработки больших объемов данных, от 10 тысяч записей до миллионов, каждая из которых может содержать сотни атрибутов, и широко используется в распознавании образов, финансах, страховом деле, демографии, торговле, маркетинговых исследованиях, медицине, химии, биологии и др. К настоящему времени разработано большое число методов кластеризации, применяющихся к данным числового типа. В области нечисловых (категориальных) данных общепринятых методов гораздо меньше.(ROCK, DBSCAN, BIRTH, CP, CURE и др.) Обработка данных смешанного типа в настоящий момент вызывает значительные трудности и является областью исследований. В общем случае все этапы кластерного анализа взаимосвязаны, и решения, принятые на одном из них, определяют действия на последующих этапах. [9] Аналитику следует решить, использовать ли все наблюдения либо же исключить некоторые данные или выборки из набора данных. Выбор метрики и метода стандартизации исходных данных. Определение количества кластеров (для итеративного кластерного анализа). Определение метода кластеризации (правила объединения или связи). По мнению многих специалистов, выбор метода кластеризации является решающим при определении формы и специфики кластеров. Анализ результатов кластеризации. Этот этап подразумевает решение таких вопросов: не является ли полученное разбиение на кластеры случайным; является ли разбиение надежным и стабильным на подвыборках данных; существует ли взаимосвязь между результатами кластеризации и переменными, которые не участвовали в процессе кластеризации; можно ли интерпретировать полученные результаты кластеризации. Проверка результатов кластеризации. Результаты кластеризации также должны быть проверены формальными и неформальными методами. Формальные методы зависят от того метода, который использовался для кластеризации. Неформальные включают следующие процедуры проверки качества кластеризации:
Один из вариантов проверки качества кластеризации - использование нескольких методов и сравнение полученных результатов. Отсутствие подобия не будет означать некорректность результатов, но присутствие похожих групп считается признаком качественной кластеризации. Как и любые другие методы, методы кластерного анализа имеют определенные слабые стороны, т.е. некоторые сложности, проблемы и ограничения. При проведении кластерного анализа следует учитывать, что результаты кластеризации зависят от критериев разбиения совокупности исходных данных. При понижении размерности данных могут возникнуть определенные искажения, за счет обобщений могут потеряться некоторые индивидуальные характеристики объектов. Существует ряд сложностей, которые следует продумать перед проведением кластеризации.
При большом количестве наблюдений иерархические методы кластерного анализа не пригодны. В таких случаях используют неиерархические методы, основанные на разделении, которые представляют собой итеративные методы дробления исходной совокупности. В процессе деления новые кластеры формируются до тех пор, пока не будет выполнено правило остановки. Такая неиерархическая кластеризация состоит в разделении набора данных на определенное количество отдельных кластеров. Существует два подхода. Первый заключается в определении границ кластеров как наиболее плотных участков в многомерном пространстве исходных данных, т.е. определение кластера там, где имеется большое «сгущение точек». Второй подход заключается в минимизации меры различия объектов Наиболее распространен среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным анализом. Полное описание алгоритма можно найти в работе Хартигана и Вонга (Hartigan and Wong, 1978). В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров. [9,10] Алгоритм k-средних строит k кластеров, расположенных на возможно больших расстояниях друг от друга. Основной тип задач, которые решает алгоритм k-средних, - наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Выбор числа k может базироваться на результатах предшествующих исследований, теоретических соображениях или интуиции. Общая идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга. Описание алгоритма. 1. Первоначальное распределение объектов по кластерам. Выбирается число k, и на первом шаге эти точки считаются «центрами» кластеров. Каждому кластеру соответствует один центр. Выбор начальных центроидов может осуществляться следующим образом: - выбор k-наблюдений для максимизации начального расстояния; - случайный выбор k-наблюдений; - выбор первых k-наблюдений. В результате каждый объект назначен определенному кластеру. 2. Итеративный процесс. Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются. Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий: - кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации; - число итераций равно максимальному числу итераций. На рисунке 1 приведен пример работы алгоритма k-средних для k, равного двум. Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты. Проверка качества кластеризации. После получений результатов кластерного анализа методом k-средних следует проверить правильность кластеризации (т.е. оценить, насколько кластеры отличаются друг от друга). Для этого рассчитываются средние значения для каждого кластера. При хорошей кластеризации должны быть получены сильно отличающиеся средние для всех измерений или хотя бы большей их части. Достоинства алгоритма k-средних: • простота использования; • быстрота использования; • понятность и прозрачность алгоритма. Недостатки алгоритма k-средних: • алгоритм слишком чувствителен к выбросам, которые могут искажать среднее. Возможным решением этой проблемы является использование модификации алгоритма - алгоритм k-медианы; • алгоритм может медленно работать на больших базах данных. Возможным решением данной проблемы является использование выборки данных. Алгоритм PAM (Partitioning around Medoids) PAM является модификацией алгоритма k-средних, алгоритмом k-медианы (k-medoids). Алгоритм менее чувствителен к шумам и выбросам данных, чем алгоритм k-means, поскольку медиана меньше подвержена влияниям выбросов. PAM эффективен для небольших баз данных, но его не следует использовать для больших наборов данных. Предварительное сокращение размерности рассмотрим на примере. Есть база данных клиентов фирмы, которых следует разбить на однородные группы. Каждый клиент описывается при помощи 25 переменных. Использование такого большого числа переменных приводит к выделению кластеров нечеткой структуры. В результате аналитику достаточно сложно интерпретировать полученные кластеры. Более понятные и прозрачные результаты кластеризации могут быть получены, если вместо множества исходных переменных использовать некие обобщенные переменные или критерии, содержащие в сжатом виде информацию о связях между переменными. Т.е. возникает задача понижения размерности данных. Она может решаться при помощи различных методов; один из наиболее распространенных - факторный анализ. Остановимся на нем более подробно. Факторный анализ - это метод, применяемый для изучения взаимосвязей между значениями переменных. Вообще, факторный анализ преследует две цели: • сокращение числа переменных; • классификацию переменных - определение структуры взаимосвязей между переменными. Соответственно, факторный анализ может использоваться для решения задач сокращения размерности данных или для решения задач классификации. Критерии или главные факторы, выделенные в результате факторного анализа, содержат в сжатом виде информацию о существующих связях между переменными. Эта информация позволяет получить лучшие результаты кластеризации и лучше объяснить семантику кластеров. Самим факторам может быть сообщен определенный смысл. При помощи факторного анализа большое число переменных сводится к меньшему числу независимых влияющих величин, которые называются факторами. Фактор в «сжатом» виде содержит информацию о нескольких переменных. В один фактор объединяются переменные, которые сильно коррелируют между собой. В результате факторного анализа отыскиваются такие комплексные факторы, которые как можно более полно объясняют связи между рассматриваемыми переменными. На первом шаге факторного анализа осуществляется стандартизация значений переменных, необходимость которой была рассмотрена в предыдущей лекции. Факторный анализ опирается на гипотезу о том, что анализируемые переменные являются косвенными проявлениями сравнительно небольшого числа неких скрытых факторов. Факторный анализ - это совокупность методов, ориентированных на выявление и анализ скрытых зависимостей между наблюдаемыми переменными. Скрытые зависимости также называют латентными. Один из методов факторного анализа - метод главных компонент - основан на предположении о независимости факторов друг от друга. Обычно в статистических пакетах реализован широкий арсенал методов, что позволяет сначала провести сокращение размерности набора данных (например, при помощи факторного анализа), а затем уже собственно кластеризацию (например, методом быстрого кластерного анализа). Рассмотрим этот вариант проведения кластеризации в пакете SPSS. Для сокращения размерности исходных данных можно воспользоваться факторным анализом. Для этого в меню выбирается: Analyze (Анализ)/Data Reduction (Преобразование данных)/Factor (Факторный анализ): При помощи кнопки Extraction:(Отбор) можно выбрать метод отбора. Также можно выбрать метод вращения – например, один из наиболее популярных - метод варимакса. Для сохранения значений факторов в виде переменных в закладке «Значения» необходимо поставить отметку «Save as variables» (Сохранить как переменные). В результате этой процедуры пользователь получает отчет «Объясненная суммарная дисперсия», по которой видно число отобранных факторов - это те компоненты, собственные значения которых превосходят единицу. Полученные значения факторов, которым обычно присваиваются названия fact1_1, fact1_2 и т.д., используем для проведения кластерного анализа методом k-средних. Для проведения быстрого кластерного анализа в меню необходимо выбрать: Analyze (Анализ)/Classify(Классифицировать)/K-Means Cluster: (Кластерный анализ методом k-средних). В диалоговом окне K Means Cluster Analysis (Кластерный анализ методом k-средних) необходимо поместить факторные переменные fact1_1, fact1_2 и т.д. в поле тестируемых переменных. Здесь же необходимо указать количество кластеров и количество итераций. В результате этой процедуры получаем отчет с выводом значений центров сформированных кластеров, количестве наблюдений в каждом кластере, а также с дополнительной информацией, заданной пользователем. Таким образом, алгоритм k-средних делит совокупность исходных данных на заданное количество кластеров. Для возможности визуализации полученных результатов следует воспользоваться одним из графиков, например, диаграммой рассеивания. Однако традиционная визуализация возможна для ограниченного количества измерений, ибо, как известно, человек может воспринимать только трехмерное пространство. Поэтому, если мы анализируем более трех переменных, следует использовать специальные многомерные методы представления информации, о них будет рассказано в одной из последующих лекций курса. Итеративные методы кластеризации различаются выбором следующих параметров: - начальной точки; - правилом формирования новых кластеров; - правилом остановки. Выбор метода кластеризации зависит от количества данных и от того, есть ли необходимость работать одновременно с несколькими типами данных. В пакете SPSS, например, при необходимости работы как с количественными (например, доход), так и с категориальными (например, семейное положение) переменными, а также если объем данных достаточно велик, используется метод Двухэтапного кластерного анализа, который представляет собой масштабируемую процедуру кластерного анализа, позволяющую работать с данными различных типов. Для этого на первом этапе работы записи предварительно кластеризуются в большое количество суб-кластеров. На втором этапе полученные суб-кластеры группируются в необходимое количество. Если это количество неизвестно, процедура сама автоматически определяет его. При помощи этой процедуры банковский работник может, например,выделять группы людей, одновременно используя такие показатели как возраст, пол и уровень дохода. Полученные результаты позволяют определить клиентов, входящих в группы риска невозврата кредита. Примером кластеризации также является система COBWEB. Не претендуя на лучшую модель человеческого познания, эта система учитывает категории базового уровня и степень принадлежности элемента соответствующей категории. Кроме того, в программе COBWEB реализован инкрементальный алгоритм обучения, не требующий представления всех обучающих примеров до начала обучения. Во многих приложениях обучаемая система получает данные, зависящие от времени. В этом случае она должна строить полезные определения понятий на основе исходных данных и обновлять эти описания с появлением новой информации. В системе COBWEB также решена проблема определения корректного числа кластеров. Подход, когда количество кластеров определяется пользователем нельзя назвать гибким. В системе COBWEB для определения количества кластеров, глубины иерархии и принадлежности категории новых экземпляров используется глобальная метрика качества. [1,3,7] В системе COBWEB реализовано вероятностное представление категорий. Принадлежность категории определяется не набором значений каждого свойства объекта, а вероятностью появления значения. При предъявлении нового экземпляра система COBWEB оценивает качество отнесения этого примера к существующей категории и модификации иерархии категорий в соответствии с новым представителем. Критерием оценки качества классификации является полезность категории (category utility). Критерий полезности категории был определён при исследовании человеческой категоризации. Он учитывает влияние категорий базового уровня и другие аспекты структуры человеческих категорий. Критерий полезности категории максимизирует вероятность того, что два объекта, отнесённые к одной категории, имеют одинаковые значения свойств и значения свойств для объектов из различных категорий отличаются. Полезность категории определяется формулой: Значения суммируются по всем категориям , всем свойствам и всем значениям свойств . Значение называется предсказуемостью (predictability). Это вероятность того, что объект, для которого свойство принимает значение , относится к категории . Чем выше это значение, тем вероятнее, что свойства двух объектов, отнесённых к одной категории, имеют одинаковые значения. Величина называется предиктивностью (predictiveness). Это вероятность того, что для объектов из категории свойство принимает значение . Чем больше эта величина, тем менее вероятно, что для объектов, не относящихся к данной категории, это свойство будет принимать указанное значение. Значение – это весовой коэффициент, усиливающий влияние наиболее распространённых свойств. Благодаря совместному учёту этих значений высокая полезность категории означает высокую вероятность того, что объекты из одной категории обладают одинаковыми свойствами, и низкую вероятность наличия этих свойств у объектов из других категорий. В системе COBWEB реализован метод поиска экстремума в пространстве возможных кластеров с использованием критерия полезности категорий для оценки и выбора возможных способов категоризации. Сначала вводится единственная категория, свойства которой совпадают со свойствами первого экземпляра. Для каждого последующего экземпляра алгоритм начинает свою работу с корневой категории и движется далее по дереву. На каждом уровне выполняется оценка эффективности категоризации на основе критерия полезности. При этом оцениваются результаты следующих операций:
В результате проведенных исследований оказалось, что алгоритм COBWEB достаточно эффективен и даёт хорошие результаты кластеризации данных. Эта система выполняет разбиение на разумное число кластеров. Поскольку в нем используется вероятностное представление принадлежности, получаемые категории являются гибкими и робастными. Кроме того, в нем проявляется эффект категорий базового уровня, поддерживается прототипирование и учитывается степень принадлежности. Он основан не на классической логике, а, подобно методам теории нечетких множеств, учитывает «неопределенность» категоризации как необходимый компонент обучения и рассуждений в гибкой и интеллектуальной манере. Однако COBWEB имеет свои недостатки, которые можно устранить применив некоторые модификации, а также используя предварительную обработку данных и объединив его с другими алгоритмами кластеризации.
|
Материалы по теме выпускной работы:
Реферат | Библиотека | Ссылки |
Отчет о поиске | Индивидуальное задание |