Моделирование информационного портала ОСУ УлГУ "Династия"

APRIORI - масштабируемый алгоритм поиска ассоциативных правил. Создание официального информационного портала для студенческого совета УлГУ "Династия". Принципы построение и создания хранилища данных. Перенос информационного портала на сервер ulsu.ru.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 21.12.2015
Размер файла 1,5 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

УЛЬЯНВОСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Факультет Математики и Информационных технологий

Кафедра Телекоммуникационные технологии и сети

КУРСОВАЯ РАБОТА

Моделирование информационного портала ОСУ УлГУ «Династия»

Информационные системы и технологии 230400

Проект выполнил студент ИС-о-12/1

Ледюков О.Н.

Научный руководитель

Чекал Е.Г

Введение

На сегодняшний день существует проблема получения информационного ресурса по проведения и участию в мероприятиях созданных студенческих самоуправления и студенческим советом УлГУ «Династия» для студентов ульяновского государственного университета. У студенческого самоуправления УлГУ отсутствует официальный информационный портал, где бы была собрана информация со всех альтернативных информационных ресурсов. Таких как:

Официальный сайт УлГУ.(вкладка студент)

Группы в социальных сетях

Цель данной работы создания официального информационного портала для студенческого совета УлГУ «Династия» и объедения всех альтернативных информационных ресурсов в единый информационный портал для студентов Ульяновского государственного университета.

Объектом исследования в работе является система студенческого совета УлГУ «Династия», развивающая молодежную политику в ульяновском государственном университете.

Предметом разработки и исследования являются информационная система и её модели.

Для программной реализации и экспериментальных исследований использовались методы структурного и объектно-ориентированного программирования, инструментальные средства WordPress, СУБД MySQL.

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

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

В первой главе рассматриваются системы интеллектуальной обработки данных. В данной работе исследуются алгоритмы поиска ассоциативных правил, такие как FPG и Apriori. А так же приведена сравнительная характеристика этих алгоритмов.

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

В третьей главе рассмотрен вопрос особенности реализации при построение и переносе информационного портала на сервер ulsu.ru, а так же найдены пути решения при возникновения ошибок с работой БД.

В заключении кратко изложены основные результаты курсовой работы в виде выводов.

информационный портал алгоритм ассоциативный

Глава 1 Интеллектуальные система обработки данных

1.1FPG - альтернативный алгоритм поиска ассоциативных правил

Алгоритм Frequent Pattern-Growth Strategy (FPG)

В основе метода лежит предобработка базы транзакций, в процессе которой эта база данных преобразуется в компактную древовидную структуру, называемую Frequent-Pattern Tree - дерево популярных предметных наборов (откуда и название алгоритма). В дальнейшем для краткости будем называть эту структуру FP-дерево

Рассмотрим работу алгоритма FPG на конкретном примере. Пусть имеется БД транзакций (табл. 1).

Таблица 1

N

Предметный набор

1

a b c d e

2

a b c

3

a c d e

4

b c d e

5

b c

6

b d e

7

c d e

Для данной БД требуется обнаружить все популярные предметные наборы с минимальной поддержкой, равной 3, используя алгоритм FPG.

Производится первое сканирование БД транзакций, и отбирается множество часто встречающихся предметов, т.е. предметов, которые встречаются три или более раза. Упорядочим обнаруженные частые предметы в порядке возрастания их поддержки и получим следующий набор: (c, 6), (b, 5), (d, 5), (e, 5), (a, 3).

Построим FP-дерево. Сначала упорядочим предметы в транзакциях по убыванию значений их поддержек (табл. 2).

Таблица 2

N

Исходный предметный набор

Упорядоченный предметный набор

1

a b c d e

c b d e a

2

a b c

c b a

3

a c d e

c d e a

4

b c d e

c b d e

5

b c

c b

6

b d e

b d e

7

c d e

c d e

Правило 1. Если для очередного предмета в дереве встречается узел, имя которого совпадает с именем предмета, то предмет не создает нового узла, а индекс соответствующего узла в дереве увеличивается на 1. В противном случае для этого предмета создается новый узел и ему присваивается индекс 1.

Рис. 1. Построение FP-дерева на транзакции № 1

Сначала берем предмет с из транзакции №1. Поскольку он является первым, то формируем для него узел и соединяем с родительским (корневым) (рис. 1, а). Затем берем следующий предмет b и поскольку других узлов с тем же именем дерево пока не содержит, добавляем его в виде нового узла, потомка узла с (рис 1, б).Таким же образом формируем узлы для предметов d, e и a из транзакции № 1 (случаи в, г, и д на рис 1). На этом использование первой транзакции для построения дерева закончено.

Для транзакции № 2, содержащей предметы c, b и a, выбираем первый предмет, c. Поскольку дочерний узел с таким именем уже существует, то в соответствии с правилом построения дерева новый узел не создается, а добавляется к уже имеющемуся (рис. 2, а). При добавлении следующего предмета b используем то же правило: поскольку узел b является дочерним по отношению к текущему (т.е.c), то мы также не создаем новый узел, а увеличиваем индекс для имеющегося (рис. 2, б). Для следующего предмета из второй транзакции a в соответствии с правилом построения FP-дерева придется создать новый узел, поскольку у узла b дочерние узлы с именем a отсутствуют (рис. 2, в).

Рис. 2. Построение FP-дерева на транзакции № 2

Транзакция № 3 содержит предметы (c d e a). В соответствии с правилом построения FP-дерева, предмет c не создаст нового узла, а увеличит индекс уже имеющегося узла на 1 (рис. 3, а). Следующий предмет d породит в дереве новый узел, дочерний к c, поскольку тот не содержит потомков с таким именем (рис 3, б). Аналогично предметы e и a создадут новые узлы - потомки d (рис. 3 в, г).

Рис. 3. Использование транзакции № 3 для построения FP-дерева

Использование транзакции № 4, содержащей набор предметов (c b d e), не создаст новых узлов, а увеличит индексы узлов с аналогичной последовательностью имен. Дерево, полученное в результате использования четвертой транзакции, представлено на рис 4.

Рис. 4. Дерево, полученное в результате использования четвертой транзакции

Транзакция № 5 содержит набор c b, предметы которого увеличат индексы одноименных узлов в дереве, как показано на рис. 5.

Рис. 5. Дерево, полученное в результате использования пятой транзакции

Транзакция № 6 содержит предметы (b d e). Поскольку корневой узел не содержит непосредственного потомка с именем b, то в соответствии с правилом построения дерева для него будет создан новый узел, который «потянет» за собой два других - d и e. Все узлы будут добавлены с индексами 1. В результате дерево примет вид, представленный на рис. 6.

Рис. 6. Дерево, полученное в результате использования 6-й транзакции

И, наконец, последняя транзакция № 7, содержащая предметный набор (c d e), увеличит на 1 индексы соответствующих узлов. Получившееся дерево, которое также является результирующим для всей БД транзакций, представлено на рис. 7.

Рис. 7. Результирующее дерево, построенное по всей БД транзакций

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

Представление базы данных транзакций в виде FP-дерева очевидно. Если в исходной базе данных каждый предмет повторяется многократно, то в FP-дереве каждый предмет представляется в виде узла, а его индекс указывает на то, сколько раз данный предмет появляется. Иными словами, если предмет в исходной базе данных транзакций появляется 100 раз, то в дереве для него достаточно создать узел и установить индекс 100.

Извлечение частых предметных наборов из FP-дерева

Для каждого предмета в FP-дереве, а точнее, для связанных с ними узлов, можно указать путь, т.е. последовательность узлов, которую надо пройти от корневого узла до узла, связанного с данным предметом. Если предмет представлен в нескольких ветвях дерева (что чаще всего и происходит), то таких путей будет насколько. Например, для FP-дерева на рис. 7 для предмета a можно указать 3 пути: {cbdea, cba, cdea}. Такой набор путей называется условным базисом предмета (англ.: conditional base). Каждый путь в базисе состоит из двух частей - префикса и суффикса. Префикс - это последовательность узлов, которые проходит путь для того чтобы достичь узла, связанного с предметом. Суффикс - это сам узел, к которому «прокладывается» путь. Таким образом, в условном базисе все пути будут иметь различные префиксы и одинаковый суффикс. Например, в пути cbdea префиксом будет cbde, а суффиксом - a.

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

Выбираем предмет (например, a) и находим в дереве все пути, которые ведут к узлам этого предмета Иными словами, для a это будет набор {cbdea, cba, cdea}. Затем для каждого пути подсчитываем, сколько раз данный предмет встречается в нем, и записываем это в виде (cbdea, 1), (cba, 1) и (cdea, 1).

Удалим сам предмет (суффикс набора) из ведущих к нему путей, т.е. {cbdea, cba, cdea}. После это останутся только префиксы: {cbde, cb, cde}.

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

На его основе построим новое FP-дерево, которое назовем условным FP-деревом (conditional FP-tree), поскольку оно связано только с одним объектом (в нашем случае, a).

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

Начиная с верхушки дерева, записываем пути, которые ведут к каждому узлу, для которого поддержка/индекс больше или равны 3, возвращаем назад предмет (суффикс шаблона), удаленный на шаге 2, и подсчитываем индекс/поддержку, полученную в результате. Например, если предмет a имеет индекс 3, то можно записать (c b a, 3), что и будет являться популярным предметным набором.

Для пояснения методики извлечения шаблонов из FP-дерева продолжим рассмотрение примера для БД транзакций из табл. 1 и построенного для неё FP-дерева.

Начнем с предмета a, который имеет поддержку 3 и соответственно является часто встречающимся предметом. Префиксы путей, ведущих к узлам, связанным с a, будут: (c b d e a, 1), (c b a, 1), (c d e a, 1). На основе полученного условного базиса для суффикса a, построим условное FP-дерево (рис. 8).

Рис. 8. Условное FP-дерево для предмета a

Поскольку предметы d и e встречаются два раза, то их индексы суммируются, и в итоге мы получим следующий порядок предметов: (c, 3), (b, 2), (d, 2), (e, 2). Таким образом, только узел cудовлетворяет уровню минимальной поддержки 3. Следовательно, для предмета a может быть сгенерирован только один популярный набор (c, a, 3).

Затем переходим к следующему предмету b с поддержкой 5. Условное FP-дерево, построенное для него, будет содержать только один узел c, поскольку в дереве присутствует один путь с=>b, а суффикс b исключается. Это проиллюстрировано на рис. 9.

Рис. 9. Условное FP-дерево для суффикса b

Таким образом, префиксы путей будут (c b, 4) и (b, 1), и, следовательно, для предмета b будет иметь место только один популярный набор (c b, 4).

Для предмета c, поскольку он является непосредственным потомком корневого узла, нельзя указать путь (см. рис 7). Значит, префикс путей для него будет пустым, из чего следует, что и популярные предметные наборы отсутствуют.

Следующий предмет, для которого мы произведем поиск популярных предметных наборов, будет d с поддержкой равной 5. Условное FP-дерево, связанное с предметом d представлено на рис. 10.

Рис. 10. Условное FP-дерево для предмета d

Префиксы путей для условного дерева, связанного с предметом d, будут: (c b d, 2), (c d, 2) и (b dd, 1). Учитывая, что индексы для узлов b суммируются, то соответствующие популярные предметные наборы будут (c, d, 4) и (b, d, 3).

И, наконец, для последнего предмета е, имеющего поддержку 5, условное FP-дерево представлено на рис. 11.

Рис. 11. Условное FP-3 дерево для предмета e

Префиксы путей, ведущих в условном дереве к узлам, связанным с предметом e, будут: (c b d e, 2) (c d e, 2) (b d e, 1). Подсчитав суммарную поддержку каждого предмета в условном дереве и упорядочив предметы по ее убыванию, получим: (d, 5), (c, 4), (b, 3). Следовательно, популярными предметными наборами для предмета e будут: (d, e, 5), (d, c, e, 4), (d, b, e, 3).

Таким образом, мы получили следующие популярные предметные наборы:

(c, a, 3), (c, b, 4), (c, d, 4), (b, d, 3), (d, e, 5), (d, c, e, 4), (d, b, e, 3).

1.2APRIORI - масштабируемый алгоритм поиска ассоциативных правил

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

Обычный вид базы данных транзакций:

Номер транзакции

Наименование элемента

Количество

1001

А

2

1001

D

3

1001

E

1

1002

А

2

1002

F

1

1003

B

2

1003

A

2

1003

C

2

Таблица 1

Нормализованный вид:

TID

A

B

C

D

E

F

G

H

I

K

...

1001

1

0

0

1

1

0

0

0

0

0

1002

1

0

0

0

0

1

0

0

0

0

1003

1

1

1

0

0

0

0

0

1

0

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

Более того, как видно из таблицы, все элементы упорядочены в алфавитном порядке (если это числа, они должны быть упорядочены в числовом порядке). Как вы, наверное, уже догадались, это сделано неслучайно. Но, не будем забегать вперед, всему свое время.

Итак, данные преобразованы, теперь можно приступить к описанию самого алгоритма. Как было сказано в предыдущей статье, такие алгоритмы работают в два этапа, не является исключением и рассматриваемый нами алгоритм Apriori. На первом шаге необходимо найти часто встречающиеся наборы элементов, а затем, на втором, извлечь из них правила. Количество элементов в наборе будем называть размером набора, а набор, состоящий из k элементов, - k-элементным набором.

Свойство анти-монотонности

Выявление часто встречающихся наборов элементов - операция, требующая много вычислительных ресурсов и, соответственно, времени. Примитивный подход к решению данной задачи - простой перебор всех возможных наборов элементов. Это потребует O(2|I|) операций, где |I| - количество элементов. Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора {Хлеб, Масло, Молоко} будет всегда меньше или равна поддержке 2-элементных наборов {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}. Дело в том, что любая транзакция, содержащая {Хлеб, Масло, Молоко}, также должна содержать {Хлеб, Масло}, {Хлеб, Молоко}, {Масло, Молоко}, причем обратное не верно.

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

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

Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем на 1 уровне 1-элементные наборы, на 2-м - 2-элементные и т.д. На k уровне представлены k-элементные наборы, связанные со всеми своими (k-1)-элементными подмножествами.

Рассмотрим рисунок 1, иллюстрирующий набор элементов I - {A, B, C, D}. Предположим, что набор из элементов {A, B} имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с {A, B}, выделена фоном. Использование этой эвристики позволяет существенно сократить пространство поиска.

Алгоритм Apriori

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

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

Описанный выше алгоритм можно записать в виде следующего псевдо-кода:

F1 = {часто встречающиеся 1-элементные наборы}

для (k=2; Fk-1 <> ; k++) {

Ck = Apriorigen(Fk-1) // генерация кандидатов

для всех транзакций t T {

Ct = subset(Ck, t) // удаление избыточных правил

для всех кандидатов c Ct

c.count ++

}

Fk = { c Ck | c.count >= minsupport} // отбор кандидатов

}

Результат Fk

Опишем функцию генерации кандидатов. На это раз нет никакой необходимости вновь обращаться к базе данных. Для того, чтобы получить k-элементные наборы, воспользуемся (k-1)-элементными наборами, которые были определены на предыдущем шаге и являются часто встречающимися.

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

Объединение. Каждый кандидат Ck будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)- элементного набора.

Приведем алгоритм этой функции Apriorigen в виде небольшого SQL-подобного запроса.

insert into Ck

select p.item1, p.item2, …, p.itemk-1, q.itemk-1

From Fk-1 p, Fk-1 q

where p.item1= q.item1, p.item2 = q.item2, … , p.itemk-2 = q.itemk-2, p.itemk-1 < q.itemk-1

Удаление избыточных правил. На основании свойства анти-монотонности, следует удалить все наборы c Ck если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.

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

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

Хэш-дерево с кандидатами-наборами построено, теперь, используя хэш-дерево, легко подсчитать поддержку для каждого кандидата. Для этого нужно "пропустить" каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, т.е. Ck Ti = Ck. На корневом уровне хэш-функция применяется к каждому элементу из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым элементам и т.д. На k-уровне хэшируется k-элемент. И так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.

После того, как каждая транзакция из исходного набора данных "пропущена" через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения (k+1)-элементных наборов и т.д.

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

Извлечение правил - менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку самого набора и множества, лежащего в условии правила. Например, имеется часто встречающийся набор {A, B, C} и требуется подсчитать достоверность для правила AB C. Поддержка самого набора нам известна, но и его множество {A, B}, лежащее в условии правила, также является часто встречающимся в силу свойства анти-монотонности, и значит его поддержка нам известна. Тогда мы легко сможем подсчитать достоверность. Это избавляет нас от нежелательного просмотра базы транзакций, который потребовался в том случае если бы это поддержка была неизвестна.

Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s мы сможем сформулировать правило s (F - s), если достоверность правила conf(s (F - s)) = supp(F)/supp(s) не меньше порога minconf.

Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента. Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил. Если мы начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога. Например, если правило A BCDE удовлетворяет минимальному порогу достоверности minconf, тогда AB CDE также удовлетворяет. Для того, чтобы извлечь все правила используется рекурсивная процедура. Важное замечание: любое правило, составленное из часто встречающегося набора, должно содержать все элементы набора. Например, если набор состоит из элементов {A, B, C}, то правило A B не должно рассматриваться.

1.3Сравнительная характеристика алгоритмов поиска ассоциативных правил

Узким местом в алгоритме a priori является процесс генерации кандидатов в популярные предметные наборы. Например, если база данных (БД) транзакций содержит 100 предметов, то потребуется сгенерировать 2100~1030sup> кандидатов. Таким образом, вычислительные и временные затраты, которые нужны на их обработку, могут быть неприемлемыми. Кроме этого, алгоритм a priori требует многократного сканирования базы данных транзакций, а именно столько раз, сколько предметов содержит самый длинный предметный набор. Поэтому был предложен ряд алгоритмов, которые позволяют избежать генерации кандидатов и сократить требуемое число сканирований набора данных.

Одним из наиболее эффективных процедур поиска ассоциативных правил является алгоритм, получивший название Frequent Pattern-Growth (алгоритм FPG), что можно перевести как «выращивание популярных (часто встречающихся) предметных наборов». Он позволяет не только избежать затратной процедуры генерации кандидатов, но уменьшить необходимое число проходов БД до двух. Рассмотрим его более подробно. . К основным преимуществам данного метода относятся:

Сжатие БД транзакций в компактную структуру, что обеспечивает очень эффективное и полное извлечение частых предметных наборов;

При построении FP-дерева используется технология разделения и захвата (англ.: divide and conquer), которая позволяет выполнить декомпозицию одной сложной задачи на множество более простых;

Позволяет избежать затратной процедуры генерации кандидатов, характерной для алгоритма a priori.

Сравнительные исследования классического алгоритма a priori и FPG показали, что с увеличением числа транзакций в БД временные затраты на поиск частых предметных наборов растут для FPG намного медленнее, чем для a priori (рис. 12).

Рис. 12. Сравнение алгоритмов FPG и a priori

Повышение эффективности обработки популярных наборов

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

информационный портал алгоритм хранилище

Глава 2.Система хранение и поиска информации

2.1 Хранилище данных

Хранилище данных (англ. Data Warehouse) -- предметно-ориентированная информационная база данных, специально разработанная и предназначенная для подготовки отчётов и бизнес-анализа с целью поддержки принятия решений в организации. Строится на базе систем управления базами данных и систем поддержки принятия решений. Данные, поступающие в хранилище данных, как правило, доступны только для чтения. Данные из OLTP-системы копируются в хранилище данных таким образом, чтобы при построении отчётов и OLAP-анализе не использовались ресурсы транзакционной системы и не нарушалась её стабильность. Есть два варианта обновления данных в хранилище:

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

Инкрементальное обновление -- обновляются только те данные, которые изменились в OLTP-системе.

Принципы организации хранилища.

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

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

Некорректируемость. Данные в хранилище данных не создаются: т.е. поступают из внешних источников, не корректируются и не удаляются.

Зависимость от времени. Данные в хранилище точны и корректны только в том случае, когда они привязаны к некоторому промежутку или моменту времени.

Источниками данных могут быть:

Традиционные системы регистрации операций

Отдельные документы

Наборы данных

Операции с данными:

Извлечение - перемещение информации от источников данных в отдельную БД, приведение их к единому формату.

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

Загрузка - помещение данных в хранилище, производится атомарно, путем добавления новых фактов или корректировкой существующих.

Анализ - OLAP, Data Mining, сводные отчёты.

Представление результатов анализа.

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

Задача словаря метаданных состоит в том, чтобы освободить разработчика от необходимости стандартизировать источники данных.

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

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

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

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

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

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

С точки зрения пользователя в процессе извлечения знаний из БД должны решаться следующие преобразования: данные > информация > знания > полученные решения.

2.2Ветрина данных

Витрина данных (англ. Data Mart; другие варианты перевода: хранилище данных специализированное, киоск данных, рынок данных) -- срез хранилища данных, представляющий собой массив тематической, узконаправленной информации, ориентированный, например, на пользователей одной рабочей группы или департамента.

Концепция витрин данных была предложена Forrester Research ещё в 1991 году. По мысли авторов, витрины данных -- множество тематических баз данных (БД), содержащих информацию, относящуюся к отдельным аспектам деятельности организации.

Концепция имеет ряд несомненных достоинств:

Аналитики видят и работают только с теми данными, которые им реально нужны.

Целевая БД максимально приближена к конечному пользователю.

Витрины данных обычно содержат тематические подмножества заранее агрегированных данных, их проще проектировать и настраивать.

Для реализации витрин данных не требуется высокомощная вычислительная техника.

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

первый уровень -- общекорпоративная БД на основе реляционной СУБД с нормализованной или слабо денормализованной схемой (детализированные данные);

второй уровень -- БД уровня подразделения (или конечного пользователя), реализуемые на основе многомерной СУБД (агрегированные данные);

третий уровень -- рабочие места конечных пользователей, на которых непосредственно установлен аналитический инструментарий;

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

компактное хранение детализированных данных и поддержка очень больших БД, обеспечиваемые реляционными СУБД;

простота настройки и хорошие времена отклика, при работе с агрегированными данными, обеспечиваемые многомерными СУБД.

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

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

Создание витрины данных

Одной из основных сложностей при создании витрин является организация трех ключевых этапов - извлечения данных из исходных систем (extract), преобразования их в нужную форму (transform) и последующей загрузки в целевую систему (load). Для этого используется специальный ETL-инструмент (Extract, Transform, Load).

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

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

реструктурирование файлов данных, записей и полей;

удаление избыточных данных;

декодирование и трансляцию значений полей;

повышение качества представления читаемых данных;

проверку их достоверности;

расчет новых значений для одного или нескольких исходных столбцов;

упрощение данных и изменение их типов.

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

После установки ETL-инструмент автоматически запускается по определенному расписанию.

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

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

Глава 3Особенности реализации при построение информационного портала

3.1 Перенос информационного портала на сервер ulsu.ru

1)Первое что необходимо сделать -- выключить все плагины.Если вы не отключите плагины,могут возникнуть проблемы с переносом wordpress на хостинг.

2)Второе ,что необходимо сделать -- поставить правильное имя для домена.

Идем в консоль wordpress->Параметры->Общие

И вписываем в Адрес сайта (URL) и Адрес WordPress (URL)- доменное имя

3)Сделать копию БД.

В шаге №2 Вы создали БД в phpmyadmin, теперь необходимо создать копию данной БД.

Переходим в phpmyadmin:

Из выпадающего списка выбираем нужную БД

Выбираем “Экспорт”

Нажимаем кнопку “Выделить все” и снизу кнопку “Ок”.

Произойдет загрузка файла в формате SQL.Сохраните его к себе на компьютер,он нам понадобится при восстановлении БД на хостинге.

Хостинг wordpress.

4)Создаем БД на хостинге.

Зайдите в панель управления хостингом,и перейдите в phpmyadmin на хостинге.

Реквизиты для доступа к MySQL Вам прислали на почту по email, кстати вместе с реквизитами для доступа к FTP.

Вводим реквизиты в окошко:

5)Восстанавливаем дамп сделанный в пункте №3.

Выбираем “Импорт” и файл ,который Вы сохранили.

Жмем “Ок”.

Теперь необходимо внести изменения в файл wp-config.php. В данный файл следует вписать реквизиты,которые хостинг провайдер прислал Вам на email.

3.2 Особенности переноса БД на сервер и пути решения ошибок

Первым делом стоит убедиться, что данное сообщение об ошибке выводится и на сайте, и в административной панели. Для этого попробуйте зайти под администратором сайта (wp-admin).

Если же вы получили сообщение «Одна или несколько таблиц базы данных недоступны», тогда нужно будет выполнить автоматическое исправление таблиц механизмами WordPress.

Для этого нужно выполнить следующие шаги:

Открыть файл wp-config.php и добавить в него следующую строку:

1

define('WP_ALLOW_REPAIR', true);

После этого зайти по адресу http://ваш-сайт.ru/wp-admin/maint/repair.php. Текст программы изложен в приложение.

Нажать кнопку «Починить базу данных» и дождаться завершения операции.

Это может занять некоторое время, в зависимости от размера данных в таблицах базы вашего сайта.

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

Создаёте на компьютере файл, назовём его test.php и добавляем в него следующий код:

1

2

3

4

5

6

7

<?php

$resource = mysql_connect('localhost', 'пользователь', 'пароль');

if (!$resource) {

die('Ошибка при подключении: ' . mysql_error());

}

echo 'Подключено успешно!';

mysql_close($link);

Вместо «пользователь» и «пароль» укажите свои данные для подключения к базе данных.

Загружайте этот файл на FTP вашего хостинга

Открывайте в браузере адрес http://ваш-сайт.ru/test.php

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

Если же отобразилось «Подключено успешно», тогда внесите используемые ваши логин и пароль для подключения к базе данных в файл wp-config.php.

Заключение

В курсовой работе были рассмотрены алгоритмы построение интеллектуальных систем обработки данных, а так же принципы создания хранилища данных. Описаны особенности реализации и переноса информационного портала на сервер ulsu.ru и пути решение при возникновения ошибок при переносе базы данных.

Список литературы

Колисниченко Д.Н., «PHP и MySQL. Разработка Web-приложений», 4 издание, перераб. и доп. - СПб.: БХВ-Петербург, 2013. - 560 с.: ил. - (Профессиональное программирование).

Котеров Д.В., Костарев А.Ф. «PHP 5»/ СПб.: БХВ-Петербург, 2005. - 1120 с.:ил.

R. Agrawal, T. Imielinski, A. Swami. 1993. Mining Associations between Sets of Items in Massive Databases. In Proc. of the 1993 ACM-SIGMOD Int'l Conf. on Management of Data, 207-216.

R. Agrawal, R. Srikant. "Fast Discovery of Association Rules", In Proc. of the 20th International Conference on VLDB, Santiago, Chile, September 1994.

Сайт http://php-myadmin.ru/

Сайт http://ru.wordpress.org/

Дронов Владимир PHP, MySQL и Dreamweaver MX 2004. Разработка интерактивных Web-сайтов; БХВ-Петербург - Москва, 2010. - 448 c.

Дронов Владимир РНР 5/6, MySQL 5/6 и Dreamweaver CS4. Разработка интерактивных Web-сайтов; БХВ-Петербург - Москва, 2009. - 544 c.

Дронов, Владимир Macromedia Dreamweaver 4: разработка Web-сайтов; M.: БХВ - Москва, 2014. - 608 c.

Китинг, Джоди Flash MX. Искусство создания web-сайтов; ТИД ДС - Москва, 2012. - 848 c.

Костин С. П. Самоучитель создания Web-сайтов; Триумф - Москва, 2009. - 176 c.

Приложение

Скрипт repair.php

<?php

/**

* Database Repair and Optimization Script.

*

* @package WordPress

* @subpackage Database

*/

define('WP_REPAIRING', true);

require_once( dirname( dirname( dirname( __FILE__ ) ) ) . '/wp-load.php' );

header( 'Content-Type: text/html; charset=utf-8' );

?>

<!DOCTYPE html>

<html xmlns="http://www.w3.org/1999/xhtml" <?php language_attributes(); ?>>

<head>

<meta name="viewport" content="width=device-width" />

<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />

<title><?php _e( 'WordPress &rsaquo; Database Repair' ); ?></title>

<?php

wp_admin_css( 'install', true );

?>

</head>

<body class="wp-core-ui">

<h1 id="logo"><a href="<?php echo esc_url( __( 'https://wordpress.org/' ) ); ?>" tabindex="-1"><?php _e( 'WordPress' ); ?></a></h1>

<?php

if ( ! defined( 'WP_ALLOW_REPAIR' ) ) {

echo '<p>' . __( 'To allow use of this page to automatically repair database problems, please add the following line to your <code>wp-config.php</code> file. Once this line is added to your config, reload this page.' ) . "</p><p><code>define('WP_ALLOW_REPAIR', true);</code></p>";

} elseif ( isset( $_GET['repair'] ) ) {

$optimize = 2 == $_GET['repair'];

$okay = true;

$problems = array();

$tables = $wpdb->tables();

// Sitecategories may not exist if global terms are disabled.

$query = $wpdb->prepare( "SHOW TABLES LIKE %s", $wpdb->esc_like( $wpdb->sitecategories ) );

if ( is_multisite() && ! $wpdb->get_var( $query ) ) {

unset( $tables['sitecategories'] );

}

/**

* Filter additional database tables to repair.

*

* @since 3.0.0

*

* @param array $tables Array of prefixed table names to be repaired.

*/

$tables = array_merge( $tables, (array) apply_filters( 'tables_to_repair', array() ) );

// Loop over the tables, checking and repairing as needed.

foreach ( $tables as $table ) {

$check = $wpdb->get_row( "CHECK TABLE $table" );

echo '<p>';

if ( 'OK' == $check->Msg_text ) {

/* translators: %s: table name */

printf( __( 'The %s table is okay.' ), "<code>$table</code>" );

} else {

/* translators: 1: table name, 2: error message, */

printf( __( 'The %1$s table is not okay. It is reporting the following error: %2$s. WordPress will attempt to repair this table&hellip;' ) , "<code>$table</code>", "<code>$check->Msg_text</code>" );

$repair = $wpdb->get_row( "REPAIR TABLE $table" );

echo '<br />&nbsp;&nbsp;&nbsp;&nbsp;';

if ( 'OK' == $check->Msg_text ) {

/* translators: %s: table name */

printf( __( 'Successfully repaired the %s table.' ), "<code>$table</code>" );

} else {

/* translators: 1: table name, 2: error message, */

echo sprintf( __( 'Failed to repair the %1$s table. Error: %2$s' ), "<code>$table</code>", "<code>$check->Msg_text</code>" ) . '<br />';

$problems[$table] = $check->Msg_text;

$okay = false;

}

}

if ( $okay && $optimize ) {

$check = $wpdb->get_row( "ANALYZE TABLE $table" );

echo '<br />&nbsp;&nbsp;&nbsp;&nbsp;';

if ( 'Table is already up to date' == $check->Msg_text ) {

/* translators: %s: table name */

printf( __( 'The %s table is already optimized.' ), "<code>$table</code>" );

} else {

$check = $wpdb->get_row( "OPTIMIZE TABLE $table" );

echo '<br />&nbsp;&nbsp;&nbsp;&nbsp;';

if ( 'OK' == $check->Msg_text || 'Table is already up to date' == $check->Msg_text ) {

/* translators: %s: table name */

printf( __( 'Successfully optimized the %s table.' ), "<code>$table</code>" );

} else {

/* translators: 1: table name, 2: error message, */

printf( __( 'Failed to optimize the %1$s table. Error: %2$s' ), "<code>$table</code>", "<code>$check->Msg_text</code>" );

}

}

}

echo '</p>';

}

if ( $problems ) {

printf( '<p>' . __('Some database problems could not be repaired. Please copy-and-paste the following list of errors to the <a href="%s">WordPress support forums</a> to get additional assistance.') . '</p>', __( 'https://wordpress.org/support/forum/how-to-and-troubleshooting' ) );

$problem_output = '';

foreach ( $problems as $table => $problem )

$problem_output .= "$table: $problem\n";

echo '<p><textarea name="errors" id="errors" rows="20" cols="60">' . esc_textarea( $problem_output ) . '</textarea></p>';

} else {

echo '<p>' . __( 'Repairs complete. Please remove the following line from wp-config.php to prevent this page from being used by unauthorized users.' ) . "</p><p><code>define('WP_ALLOW_REPAIR', true);</code></p>";

}

} else {

if ( isset( $_GET['referrer'] ) && 'is_blog_installed' == $_GET['referrer'] )

echo '<p>' . __( 'One or more database tables are unavailable. To allow WordPress to attempt to repair these tables, press the &#8220;Repair Database&#8221; button. Repairing can take a while, so please be patient.' ) . '</p>';

else

echo '<p>' . __( 'WordPress can automatically look for some common database problems and repair them. Repairing can take a while, so please be patient.' ) . '</p>';

?>

<p class="step"><a class="button button-large" href="repair.php?repair=1"><?php _e( 'Repair Database' ); ?></a></p>

<p><?php _e( 'WordPress can also attempt to optimize the database. This improves performance in some situations. Repairing and optimizing the database can take a long time and the database will be locked while optimizing.' ); ?></p>

<p class="step"><a class="button button-large" href="repair.php?repair=2"><?php _e( 'Repair and Optimize Database' ); ?></a></p>

<?php

}

?>

</body>

</html>

Размещено на Allbest.ru


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.