Методы поиска ассоциативных правил

2. Кластеризация

3. Сокращение описания

4. Ассоциация (поиск повтор. образцов)

5. Прогнозирование

6. Анализ отклонений

7. Визуализация

Одним из типов алгоритмов в Data Mining – ассоциативные правила находят закономерности между связными событиями. Правила формируются на основные часто встречающихся наборов данных. Является одной из легких форм восприятия данных Если … то …

Перечень обозначений:

множество исследуемых объектов (I) Транзакция (наборы объектов из I - T) Множество транзакций, доступных для анализа (D) Произвольный набор объектов (F) Множество транзакций, в которое входит

Задача: L={F|Supp(F)> }. Требуется найти некоторое множество L всех част наборов F, поддержка, которая превышает некий минимальный уровень. Поддержка – это , D=100

Атр: 10 Пр: Если и , то

Достоверность – .

Лекция 2

Методы поиска ассоциативных правил

AIS – появляется в 1993 – первый алгоритм поиска

AIS -> SETM ->Apriori

Работа данного алгоритма состоит из нескольких этапов. Каждый этап состоит из двух шагов.

Формирование кандидата – алгоритм сканирует БД, создает множество i - элементных кандидатов, i – номер этапа. Подсчет кандидатов – рассчитывается поддержка для каждого кандидата и сравнивается с неким min.

N	Покупки
1	а, b, c
2	b, d
3	b, a, d, c
4	e, d
5	а, b, c, d
6	f

1-7	S
a	3
b	4
c	3
d	4
e	1
f	1

A	3
B	4
C	3
D	4

2-э

a	b
A	c
a	d
B	c
B	d
C	d

2-э

ab	3
ac	3
ad	2
bc	3
bd	3
cd	2

ab	3
ac	3
ad	3
bc	3

3э

abc	3
abd	2
bcd	2
acd	2

->abc

Если A и B, то С

Различают 4 характерных типа правил

правила точные, но не полные (точность=достоверность, полнота=поддержка) правила неточные, но полные. Пример: Курильщик рано или поздно заболевает раком легких правила точные и полные. Пример: в прямоугольном треугольнике из трех углов имеются два, сумма которых составляет прямой угол. Правила неточные и неполные. Пример: Если у человека родинка на щеке, то он альбинос.

Существует две основные функциональные проблемы решаемые средствами ИИ:

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

Сферы применения ИИ:

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

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

ИИС – система, которая способна принимать решения в условиях:

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

Все ИИС можно разбить на 2 класса:

Системы общего назначения – те, которые не только используют заданные процедуры, но и на основе мета-процедур поиска создают и используют процедуры решения новых задач.

Технология использования таких систем состоит в следующем:

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

Специализированные системы – выполняют решение фиксированного набора задач, который был определен при проектировании.

Данные и знания.

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

Знания

З1. Знания находятся в человеческой памяти.

З2. Знания материализованные.

З3. Совокупность З1 и З2.

З4. Знания на языке представления знаний.

З5. Базы знаний.

Данные

Д1. Результат наблюдения над объектами или данными в памяти человека.

Д2. Фиксация данных на материальном носителе.

Д3. Модель данных.

Д4. Данные на языке описания данных.

Д5. БД.

Обычно рассматривают 1,3,5.

Знания задаются двумя способами:

Экстенсионально – через набор конкретных фактов, касающихся данной предметной области.

Интенсионально – через свойства данной предметной области и систему связи между атрибутами.

Лекция 3.

Свойства знаний:

Внутренняя интерпретируемость знаний – каждая информационная единица (и. е.) должна иметь уникальное имя, по которому ИИС будет находить ее и отвечать на запросы, в которых упомянуто ее имя. Структурируемость – и. е. должна обладать гибкой структурой, т. е. для них должен выполнятся «принцип матрешки» каждая и. е. может быть включена а состав другой и. е. и наоборот. Связность – в информационной базе между и. е. должна быть предусмотренная возможность восстановления различных взаимосвязей. При этом различают следующие связи (отношения): связи структуризации – задается иерархия в и. е.; функциональные отношения – описывают информацию о функциях; казуальные отношения – используются для задания причинно-следственной связи; семантические связи – все остальное. Семантическая метрика – позволяет задать отношения, которые характеризуют ситуационную близость между и. е., другими словами определяет ассоциативную связь. Активность знаний – с момента появления компьютеров используемые в них и. е. разделены на данные и команды. Данные пассивны, а команды – активны.

Классификация знаний

Поверхностные – совокупность эмпирических ассоциаций и причинно-следственных отношений между понятиями предметной области.

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

Жесткие знания позволяют получать однозначные четкие рекомендации при заданных начальных условиях. Мягкие знания допускают множественные, «размытые» решения и различные варианты рекомендаций.

Деревья решений.

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

Область применения достаточно широка. Задачи которые они решают:

Описание данных. Классификация. Регрессия – поиск зависимостей.

Построение дерева решений.

Пусть задано обучающее множество Т, оно содержит объекты, каждые из которых характеризуются неким набором атрибутов m, причем один из этих атрибутов указывает на принадлежность объекта к определенному классу. Обозначим все классы и тогда возможны три ситуации:

Множество Т содержит 1 или более примеров, относящихся к одному из классов. В этом случае дерево решений – лист, определяющий класс решений . Т не содержит ни одного примера. В этом случае дерево решений – это пустой лист и класс, к которому его нужно отнести, будет выбираться из связного с ним множества. В множестве есть примеры относящиеся к разным классам, тогда множество можно разбить на ряд множеств и для этого выбрать признак и по нему произвести разделение множества Т.

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

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

Как разбивать на подмножества:

Для каждого узла найти такое условие, которое разбивало множество на два подмножества. Для этого используется один из атрибутов и правила для выбора можно записать в виде: выбранный атрибут должен разбить множество так чтобы полученные в итоге подмножества состояли из объектов одного класса или были максимально приближены к этому.

Для того чтобы избежать излишней «ветвистости» деревьев используют т. н. отсечение которое, по определенному «подстригает» деревья так, чтобы полученное дерево было компактным и работало с максимальной эффективностью.

Преимущества деревьев решений.

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

Недостатки:

Размер дерева – найти «золотую середину» между ветвистостью и компактностью достаточно трудно.

Типы алгоритмов:

012.jpg - 016.jpg + pdf

Основы искусственных нейронных сетей.

Нейронные сети – самообучающиеся системы, имитирующие деятельность человеческого мозга.

Искусственный нейрон – имитирует свойства и работу своего биологического прототипа.

Схема нейрона.

Из рисунка видно, что искусственный нейрон, так же, как и живой, состоит из синапсов (Однонаправленная входная связь нейрона, соединенная с выходом другого нейрона), связывающих входы нейрона с ядром; ядра нейрона, которое осуществляет обработку входных сигналов и аксона (Единственный отросток биологического нейрона, по которому он передает свой выходной сигнал), который связывает нейрон с нейронами следующего слоя. Каждый синапс имеет вес, который определяет, насколько соответствующий вход нейрона влияет на его состояние. Состояние нейрона определяется по формуле:

, где: n – число входов нейрона, xi – значение i-го входа нейрона, wi – вес i-го синапса.

Затем определяется значение аксона нейрона по формуле: Y = f(S), где f – некоторая функция, которая называется активационной (пороговой). Наиболее часто в качестве активационной функции используется так называемый сигмоид (т. е. функция, график которой похож на букву "S"), который имеет следующий вид:

Основное достоинство этой функции в том, что она дифференцируема на всей оси абсцисс и имеет очень простую производную:

При уменьшении параметра a сигмоид становится более пологим, вырождаясь в горизонтальную линию на уровне 0,5 при a=0. При увеличении a сигмоид все больше приближается к функции единичного скачка.

Обучение нейронных сетей.

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

Существует два способа обучения:

- с учителем

- без учителя

Сети, обучающиеся без учителя, просматривают выборку только один раз. Сети, обучающиеся с учителем, просматривают выборку множество раз, при этом один полный проход по выборке называется эпохой обучения. При обучении с учителем набор исходных данных делят на две части – собственно обучающую выборку и тестовые данные; принцип разделения может быть произвольным. Обучающие данные подаются сети для обучения, а проверочные используются для расчета ошибки сети (проверочные данные никогда для обучения сети не применяются). Таким образом, если на проверочных данных ошибка уменьшается, то сеть действительно выполняет обобщение. Если ошибка на обучающих данных продолжает уменьшаться, а ошибка на тестовых данных увеличивается, значит, сеть перестала выполнять обобщение и просто «запоминает» обучающие данные. Это явление называется переобучением сети или оверфиттингом. В таких случаях обучение обычно прекращают.

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

Персептоны.

Первые работы по созданию нейросетей были начаты в 40-х годах и первой нейросетью была сеть состоящая из одного нейрона.

019

=============================================================================

Проблемы исключающие или

x1=x, x2=y

OUT принимает значение 0 когда NET <0,5 и 1, когда NET0,5

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