Nghiên cứu luật kết hợp và ứng dụng trong bài toán xây dựng hệ hỗ trợ học sinh Trung học Phổ thông

\\\

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRẦN NAM NGỌC

NGHIÊN CỨU LUẬT KẾT HỢP VÀ ỨNG

DỤNG TRONG BÀI TOÁN XÂY DỰNG HỆ HỖ

TRỢ HỌC SINH TRUNG HỌC PHỔ THÔNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2015

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

LỜI CẢM ƠN

Đầu tiên cho tôi gửi lời cảm ơn chân thành và sâu sắc nhất đến thầy

PGS.TS Lê Bá Dũng - Viện CNTT - Viện KH và CN Việt nam đã tận tình

hƣớng dẫn, chỉ bảo cho tôi trong suốt quá trình làm luận văn.

Tôi cũng gửi lời cảm ơn đến các thầy cô trƣờng Đại học Công nghệ

thông tin và Truyền thông – Đại học Thái Nguyên, các thầy cô Viện ÂNCông

nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá

trình học của mình.

Tôi cũng xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và bạn bè

những ngƣời đã động viên tạo mọi điều kiện giúp đỡ tôi trong suốt hai năm

học.

ĐẠI HỌC THÁI NGUYÊN

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRẦN NAM NGỌC

NGHIÊN CỨU LUẬT KẾT HỢP VÀ ỨNG DỤNG

TRONG BÀI TOÁN XÂY DỰNG HỆ HỖ TRỢ

HỌC SINH TRUNG HỌC PHỔ THÔNG

Chuyên ngành: Khoa học máy tính

Mã số : 60 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƢỜI HƢỚNG DẪN KHOA HỌC: TS ĐẶNG THỊ THU HIỀN

Thái Nguyên - 2015

1

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

MỤC LỤC

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ........................................................4

DANH MỤC CÁC BẢNG ....................................................................................................5

MỞ ĐẦU ...............................................................................................................................1

CHƢƠNG I TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU.......................................................2

1.1. Tổ chức và khai thác cơ sở dữ liệu truyền thống........................................................2

1.2. Tổng quan về kỹ thuật phát hiện tri thức và khai phá dữ liệu ....................................3

1.2.1. Qui trình khai phá dữ liệu và phát hiện tri thức. .................................................4

1.2.2. Các lĩnh vực liên quan đến khai phá dữ liệu và phát hiện tri thức......................5

1.3. Các nhiệm vụ trong khai phá dữ liệu và phát hiện tri thức. .......................................6

CHƢƠNG II: MỘT SỐ KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP.................................15

2.1 Lý thuyết về luật kết hợp...........................................................................................15

2.2 Thuật toán kinh điển..................................................................................................16

2.2.1. Thuật toán Apriori.............................................................................................16

2.2.2 Ý tƣởng ..............................................................................................................16

2.2.3 Thuật toán...........................................................................................................16

2.3 Một số thuật toán luật kết hợp...................................................................................19

2.3.1 Thuật toán Fp_Growth .......................................................................................19

2.3.2 Thuật toán Fp_Tree ............................................................................................20

2.3.3 Thuật toán Fast Algorithm for Discovering Frequent Itemsets (FIT)................21

2.3.4 Thuật toán NSFI ALGORITHM .......................................................................22

2.3.5 Thuật toán NSFI ALGORITH ...........................................................................25

2.4 Thuật toán FSM........................................................................................................26

2.4.1 Cơ sở lý thuyết của thuật toán FSM...................................................................27

2.4.2 Nội dung cơ bản của thuật toán FSM.................................................................27

2.4.3. Một số khái niệm của thuật toán .......................................................................28

2.4.4 Nội dung bài toán:..............................................................................................31

CHƢƠNG III: ÁP DỤNG KHAI PHÁ TRÊN CƠ SỞ DỮ LIỆU BẢNG ĐIỂM CỦA HỌC

SINH THPT TÂN LẬP - ĐAN PHƢỢNG ........................................................................34

3.1. Phát biểu bài toán: ....................................................................................................34

3.2 Lựa chọn phƣơng pháp..............................................................................................35

3.3 Cài đặt và thử nghiệm................................................................................................35

3.3.1. Môi trƣờng cài đặt và thử nghiệm.....................................................................35

3.3.2 Cài đặt thuật toán tìm luật kết hợp .....................................................................36

3.3.3 Một số giao diện chƣơng trình ...........................................................................37

3.4 Đánh giá: ..................................................................................................................38

TÀI LIỆU THAM KHẢO ...................................................................................................47

PHỤ LỤC ............................................................................................................................49

2

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Tác giả xin chân thành cảm ơn các thầy giáo, cô giáo Trƣờng Đại học Công

nghệ thông tin và Truyền thông Thái Nguyên và các thầy Viện Công nghệ thông

tin – Viện khoa học Công nghệ Việt Nam, đã tận tâm giảng dạy các kiến thức

trong hai năm học qua cùng với sự cố gắng hết mực của bản thân.

Đặc biệt tôi xin bày tỏ sự biết ơn sâu sắc đến thầy giáo Tiến sĩ Đặng Thị

Thu Hiền, PGS. TS Ngô Quốc Tạo ngƣời đã tận tình giảng dạy và hƣớng dẫn

tôi thực hiện luận văn này.

Tác giả cũng xin chân thành cảm ơn các thầy cô giáo trƣờng THPT Tân

Lập, các bạn đồng nghiệp, các bạn trong lớp cao học CK12H đã tạo điều kiện,

giúp đỡ tôi trong suốt thời gian qua.

Rất mong nhận đƣợc sự góp ý của các thầy, cô, bạn bè, đồng nghiệp để

luận văn có thể phát triển và hoàn thiện hơn.

3

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi.

Các số liệu, kết quả nêu trong luận văn và chƣa từng đƣợc ai công bố

trong bất kỳ công trình nào khác.

Thái Nguyên, tháng 12 năm 2015

TÁC GIẢ

Trần Nam Ngọc

4

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT

Từ viết tắt Tiếng Anh Tiếng Việt

Ck Ck Tập các K – itemset ứng cử

Conf Confidence Độ tin cậy

CSDL Database Cơ sở dữ liệu

DW Data Warehouse Kho dữ liệu

Item Item Khoản mục

Itemset Itemset Tập các khoản mục

K- itemset K- itemset Tập gồm K mục

KDD Knowledge Discovery and

Data Mining

Kỹ thuật phát hiện tri thức và khai

phá dữ liệu

Lk Lk Tập các K - itemset phổ biến

Minconf Minimum Confidence Độ tin cậy tối thiểu

Minsup Minimum Support Độ hỗ trợ tối thiểu

OLAP On Line Analytical

Processing

Phân tích trực tuyến

MOLAP Multidimensional OLAP Phân tích đa chiều trực tuyến

ROLAP Relational OLAP Phân tích quan hệ trực tuyến

pre(k, s) pre(k, s) Tiếp đầu dãy có độ dài k của s

Record Record Bản ghi

Supp Support Độ hỗ trợ

TID Transaction Indentification Định danh giao tác

SQL Structured Query Language Ngôn ngữ truy vấn có cấu trúc

SQO Semantic Query Optimization Tối ƣu truy vấn ngữ nghĩa

DBSCAN Density Based Spatial

Clustering of Application

with Noise

Thuật toán phân lớp dựa vào vị trí

địa phƣơng

5

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DENCLUE DENsity Based CLUstEring Thuật toán phân lớp cơ bản (tổng

quát)

ADO Activate X Data Object Đối tƣợng dữ liệu Active X

DFS Depth First Search Tìm kiếm theo chiều sâu

BFS Breadth First Search Tìm kiếm theo chiều rộng

DHP Direct Hashing and Pruning Bảng băm trực tiếp và sự cắt tỉa

PHP Perfect Hashing and Pruning Bảng băm lý tƣởng và sự cắt tỉa

I/O Input/Output Vào/ra

D Data CSDL có các trƣờng <TID, item>

Size Size Số lƣợng các Item trong tập

Itemset

DANH MỤC CÁC BẢNG

Bảng 1.1. So sánh các nhiệm vụ phát hiện tri thức...................................................12

Bảng 2.1. Cơ sở dữ liệu.............................................................................................29

Bảng 2.2. Giá trị lmv và cổ phần của các mục dữ liệu trong CSDL bảng 2.1. ........30

Bảng 2.3. Các tập mục cổ phần cao của CSDL bảng 2.1.........................................31

Bảng 2.4. CSDL minh họa ngữ nghĩa của tập mục cổ phần cao..............................33