Luận văn Thạc sĩ Khoa học máy tính: 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

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LỜI CẢM ƠN TRẦN NAM NGỌC Đầ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

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

PGS.TS Lê Bá Dũng - Viện CNTT - Viện KH và CN Việt nam đã tận tình NGHIÊN CỨU LUẬT KẾT HỢP VÀ ỨNG DỤNG 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 TRONG BÀI TOÁN XÂY DỰNG HỆ HỖ TRỢ nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá HỌC SINH TRUNG HỌC PHỔ THÔNG

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

Chuyên ngành: Khoa học máy tí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è

Mã số : 60 48 01 01

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.

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

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 ........................................................ 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

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

MỤC LỤC

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 để

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

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

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Ả

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

Trần Nam Ngọc

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

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

Conf

Confidence

Độ tin cậy

CSDL

Database

Cơ sở dữ liệu

Data Warehouse

Kho dữ liệu

Item

Khoản mục

Itemset

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

K- itemset K- itemset

Tập gồm K mục

KDD

Knowledge Discovery and

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

Data Mining

phá dữ liệu

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

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

Processing

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

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

pre(k, s)

Bản ghi

Record

Độ hỗ trợ

Support

Supp

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

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

Clustering of Application

địa phƣơng

with Noise

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

Data

CSDL có các trƣờng

Size

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

Itemset

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

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

DANH MỤC CÁC BẢNG

Hình 1.1. Quy trình phát hiện tri thức ........................................................................ 4 Hình 2.1. CSDL giao dịch ......................................................................................... 17 Hình 2.2. Minh họa các bước khai phá ..................................................................... 18 Hình 2.3. Kết quả tìm luật kết hợp ............................................................................ 18 Hình 3.1. Ví dụ về dữ liệu đầu vào cho thực nghiệm ............................................... 37 Hình 3.2. Giao diện chương trình thực hiện ............................................................. 37 Hình 3.3. Kết quả ...................................................................................................... 38

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

DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ

MỞ ĐẦU

Ngày nay, thông tin đƣợc coi là tài sản quan trọng của các tổ chức, doanh

nghiệp và các cá nhân. Cá nhân hoặc tổ chức nào thu thập và hiểu đƣợc thông

tin, và hành động kịp thời dựa trên các thông tin đó sẽ đạt đƣợc kết quả tốt.

Chính vì lý do đó, việc tạo ra thông tin, tổ chức lƣu trữ và khai thác thông tin

ngày càng trở nên quan trọng và gia tăng không ngừng.

Sự tăng trƣởng vƣợt bậc của các cơ sở dữ liệu (CSDL) trong các hoạt

động nhƣ: sản xuất kinh doanh, thƣơng mại, quản lý đã làm nảy sinh và thúc

đẩy sự phát triển của kỹ thuật thu thập, lƣu trữ, phân tích và khai phá dữ liệu…

không chỉ bằng các phƣơng pháp thông thƣờng nhƣ: thống kê mà đòi hỏi cách

xử lý thông minh hơn, hiệu quả hơn. Từ đó các nhà quản lý có đƣợc thông tin

hữu ích để tác động lại quá trình sản xuất, kinh doanh của mình… đó là tri

thức. Các kỹ thuật cho phép ta khai thác đƣợc tri thức hữu dụng từ CSDL (lớn)

đƣợc gọi là các kỹ thuật khai phá dữ liệu (DM – Data Mining). Khai phá luật

kết hợp là một nội dung quan trọng trong khai phá dữ liệu.

Luận văn tìm hiểu về luật kết hợp và ứng dụng thử nghiệm khai phá cơ sở

dữ liệu bảng điểm học tập của học sinh trƣờng THPT Tân Lập – Đan Phƣơng

nhằm hỗ trợ cho công tác quản lý, định hƣớng học tập cho học sinh phổ thông.

Nhằm hỗ trợ học sinh chọn trƣờng đại học, cao đẳng phù hợp với khả năng của

bản thân hoặc đi học trƣờng nghề chuyên nghiệp. Giúp cho học sinh tập chung

vào đúng khối mà mình có khả năng cũng nhƣ có thế mạnh. Đồng thời cũng

giúp nhà trƣờng và giáo viên thấy đƣợc điểm mạnh, điểm chƣa mạnh về

chuyên môn của mình. Đƣa ra những hƣớng đi đúng nhằm xây dựng nhà

trƣờng thành nhà trƣờng có chuyên môn tốt, môi trƣờng thân thiện.

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

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

Việc dùng các phƣơng tiện tin học để tổ chức và khai thác cơ sở dữ liệu

(CSDL) đã đƣợc phát triển từ những năm 60 của thế kỉ trƣớc. Từ đó cho đến

nay, rất nhiều CSDL đã đƣợc tổ chức, phát triển và khai thác ở mọi quy mô và

các lĩnh vực hoạt động của con ngƣời và xã hội. Cho đến nay, số lƣợng CSDL

đã trở nên khổng lồ bao gồm các CSDL cực lớn cỡ gigabytes và thậm chí

terabytes lƣu trữ các dữ liệu kinh doanh ví dụ nhƣ dữ liệu thông tin khác hàng,

dữ liệu bán hàng, dữ liệu các tài khoản, ... Nhiều hệ quản trị CSDL mạnh với

các công cụ phong phú và thuận tiện đã giúp con ngƣời khai thác có hiệu quả

nguồn tài nguyên dữ liệu. Mô hình CSDL quan hệ và ngôn ngữ vấn đáp chuẩn

(SQL) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác CSDL.

Tuy nhiên bên cạnh chức năng khai thác dữ liệu có tính chất tác nghiệp,

sự thành công trong công việc không còn là năng suất của các hệ thống thông

tin nữa mà là tính linh hoạt và sẵn sàng đáp ứng những yêu cầu trong thực tế,

CSDL cần đem lại những “tri thức” hơn là chính những dữ liệu trong đó. Lúc

này, các mô hình CSDL truyền thống và ngôn ngữ SQL đã cho thấy không có

khả năng thực hiện công việc này. Để lấy thông tin có tính “tri thức” trong

khối dữ liệu khổng lồ này, ngƣời ta đã tìm ra những kỹ thuật có khả năng hợp

nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành một tập

hợp các CSDL ổn định, có chất lƣợng đƣợc sử dụng chỉ cho riêng một vài mục

đích nào đó. Các kỹ thuật đó gọi chung là kỹ thuật tạo kho dữ liệu (data

warehousing) và môi trƣờng các dữ liệu có đƣợc gọi là các kho dữ liệu (data

warehouse).

Đồng thời, Công nghệ khai phá dữ liệu (data mining) ra đời đáp ứng

những đòi hỏi trong khoa học cũng nhƣ trong hoạt động thực tiễn. Đây chính

là một ứng dụng chính để khai phá kho dữ liệu nhằm phát hiện tri thức

(Knowledge Discovery) phục vụ công tác quản lý, kinh doanh,….

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

Chúng ta có thể xem tri thức nhƣ là các thông tin tích hợp, bao gồm các

sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể đƣợc hiểu

ra, có thể đƣợc phát hiện, hoặc có thể đƣợc học. Nói cách khác, tri thức có thể

đƣợc coi là dữ liệu có độ trừu tƣợng và tổ chức cao.

Phát hiện tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các

mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích,

và có thể hiểu đƣợc. Còn khai phá dữ liệu là một bƣớc trong qui trình phát

hiện tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dƣới một số

qui định về hiệu quả tính toán chấp nhận đƣợc để tìm ra các mẫu hoặc các mô

hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai

phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các

cơ sở dữ liệu nhƣng vẫn còn bị che khuất bởi hàng núi dữ liệu.

Định nghĩa: Phát hiện tri thức và khai phá dữ liệu (KDD: Knowledge

Discovery and Data Mining) là quá trình không tầm thƣờng nhận ra những

mẫu có giá trị, mới, hữu ích tiềm năng và hiểu đƣợc trong dữ liệu [7].

Còn các nhà thống kê thì xem Khai phá dữ liệu nhƣ là một qui trình phân

tích đƣợc thiết kế để thăm dò một lƣợng cực lớn các dữ liệu nhằm phát hiện ra

các mẫu thích hợp và/hoặc các mối quan hệ mang tính hệ thống giữa các biến

và sau đó sẽ hợp thức hoá các kết quả tìm đƣợc bằng cách áp dụng các mẫu đã

phát hiện đƣợc cho các tập con mới của dữ liệu. Qui trình này bao gồm ba giai

đoạn cơ bản: thăm dò, xây dựng mô hình hoặc định nghĩa mẫu, hợp thức/kiểm

chứng.

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

Hình 1.1. Quy trình phát hiện tri thức

Qui trình phát hiện tri thức đƣợc mô tả tóm tắt trên Hình 1:

Bƣớc thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là tìm hiểu

lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ cần phải

hoàn thành. Bƣớc này sẽ quyết định cho việc rút ra đƣợc các tri thức hữu ích

và cho phép chọn các phƣơng pháp khai phá dữ liệu thích hợp với mục đích

ứng dụng và bản chất của dữ liệu.

Bƣớc thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn

đƣợc gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến

đổi dữ liệu và rút gọn dữ liệu nếu cần thiết, bƣớc này thƣờng chiếm nhiều thời

gian nhất trong toàn bộ qui trình phát hiện tri thức.

Bƣớc thứ ba: Khai phá dữ liệu, rút ra các tri thức. Là trích ra các mẫu

và/hoặc các mô hình ẩn dƣới các dữ liệu. Giai đoạn này rất quan trọng, bao

gồm các công đoạn nhƣ: chức năng, nhiệm vụ và mục đích của khai phá dữ

liệu, dùng phƣơng pháp khai phá nào?

Bƣớc thứ tƣ: Sử dụng các tri thức phát hiện đƣợc. Là hiểu tri thức đã tìm

đƣợc, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bƣớc trên có thể lặp đi

lặp lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình trên tất cả các

lần thực hiện.

Tóm lại: KDD là một quá trình chiết xuất ra tri thức từ kho dữ liệu mà

trong đó khai phá dữ liệu là công đoạn quan trọng nhất.

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

Khai phá dữ liệu và phát hiện tri thức liên quan đến nhiều ngành, nhiều

lĩnh vực: thống kê, trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán học, tính toán song

song và tốc độ cao, thu thập tri thức cho các hệ chuyên gia, quan sát dữ liệu...

Đặc biệt Phát hiện tri thức và khai phá dữ liệu rất gần gũi với lĩnh vực thống kê,

sử dụng các phƣơng pháp thống kê để mô hình dữ liệu và phát hiện các mẫu,

luật... Kho dữ liệu (Data Warehousing) và các công cụ phân tích trực tuyến

(OLAP) cũng liên quan rất chặt chẽ với Phát hiện tri thức và khai phá dữ liệu.

Khai phá dữ liệu có nhiều ứng dụng trong thực tế. Một số ứng dụng điển

hình nhƣ:

- Bảo hiểm, tài chính và thị trƣờng chứng khoán: Phân tích tình hình tài

chính và dự báo giá của các loại cổ phiếu trong thị trƣờng chứng khoán. Danh

mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận, ...

- Điều trị y học và chăm sóc y tế: Một số thông tin về chuẩn đoán bệnh

lƣu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu

chứng bệnh, chuẩn đoán và phƣơng pháp điều trị (chế độ dinh dƣỡng, thuốc,

...).

- Text mining và Web mining: Phân lớp văn bản và các trang Web, tóm

tắt văn bản,...

- Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật

học, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và

một số bệnh di truyền, ...

- Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát

lỗi, sự cố, chất lƣợng dịch vụ, ...

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

Do sự phát triển mạnh mẽ của các loại hệ thống phát hiện tri thức trong

CSDL (KDD) theo yêu cầu nhằm đáp ứng những đòi hỏi trong nhiều lĩnh vực

khác nhau, việc phát hiện tri thức cũng trở lên đa dạng hơn. Do đó, nhiệm vụ

của phát hiện tri thức trong CSDL cũng trở lên phong phú và có thể phát hiện

rất nhiều kiểu tri thức khác nhau. Một trong các bƣớc đầu tiên trong quá trình

phát hiện tri thức trong CSDL là quyết định xem loại kiến thức nào mà thuật

toán phát hiện tri thức trong CSDL cần phải kết xuất từ dữ liệu. Do đó, vệc

phân loại và so sánh các kiểu nhiệm vụ phát hiện tri thức trong CSDL là vấn

đề đáng quan tâm nhằm tạo ra một hệ thống phát hiện tri thức trong CSDL hữu

ích. Ta sẽ xem xét một số kiểu nhiệm vụ phát hiện tri thức sau:

Phát hiện các luật tối ƣu truy vấn ngữ nghĩa (Sematics Query

Optimization - SQO Rules)

Các luật tối ƣu truy vấn CSDL thông thƣờng thực hiện một phép biến đổi

cú pháp, hay sắp xếp lại thứ tự của các phép toán quan hệ trong một truy vấn

và sản sinh ra một truy vấn hiệu quả hơn. Các phép biến đổi này thƣờng dựa

trên lý thuyết đại số quan hệ. Các luật đƣợc biến đổi trả lại cùng một câu trả lời

nhƣ câu truy vấn ban đầu ở bất kỳ trạng thái nào của CSDL. Ngƣợc lại, luật tối

ƣu truy vấn ngữ nghĩa biến đổi các câu truy vấn ban đầu thành một truy vấn

mới bằng cách thêm vào hoặc xoá đi các mối liên kết bằng việc sử dụng các tri

thức CSDL ngữ nghĩa bao gồm các ràng buộc về tính toàn vẹn và sự phụ thuộc

hàm để sản sinh ra các câu truy vấn hiệu quả hơn. Nhƣ vậy câu truy vấn đã

biến đổi cũng trả lại cùng câu trả lời giống nhƣ câu truy vấn ban đầu trong bất

kỳ trạng thái nào của CSDL thoả mãn kiến thức về ngữ nghĩa đƣợc sử dụng

trong phép biến đổi. Các hệ thống phát hiện luật SQO có thể đƣợc chia thành

ba lớp:

- Các hệ thống hƣớng truy vấn (hệ thống báo cáo) trong đó thuật toán

phát hiện tri thức trong CSDL nhằm phục vụ các truy vấn CSDL thực của

ngƣời dùng;

- Các hệ thống hƣớng dữ liệu (hệ thống tác nghiệp) trong đó thuật toán

phát hiện tri thức trong CSDL chủ yếu phục vụ sự phân bổ dữ liệu trong trạng

thái hiện thời của CSDL;

- Các hệ thống lai kết hợp các đặc tính của cả hệ thống hƣớng truy vấn và

hƣớng dữ liệu.

Một đặc tính quan trọng của các luật SQO, khác với các kiểu phát hiện tri

thức khác, là việc chọn các thuộc tính để tổng hợp một SQO cần phải tính đến

chi phí liên quan nhƣ dùng phƣơng pháp truy cập nào và sơ đồ chỉ số trong hệ

quản trị CSDL. Việc này là cần thiết để tiết kiệm thời gian xử lý truy vấn. Một

thuật toán phát hiện tri thức trong CSDL loại này đòi hỏi phải xem xét tối ƣu

chi phí.

Phát hiện sự phụ thuộc CSDL (Database Dependencies)

Trong mô hình dữ liệu quan hệ, chúng ta đã nghiên cứu quan hệ trong

CSDL quan hệ không tính đến quan hệ giữa các thuộc tính. Các quan hệ này

thƣờng đƣợc thể hiện thông qua sự phụ thuộc dữ liệu hoặc ràng buộc toàn vẹn.

Ở đây sẽ sử dụng thuật ngữ phụ thuộc CSDL để chỉ sự phụ thuộc dữ liệu kiểu

này. Sự phụ thuộc CSDL đƣợc sử dụng trong thiết kế và duy trì một CSDL.

Phƣơng pháp phát hiện tự động các sự phụ thuộc CSDL này chính là một kiểu

nhiệm vụ của Khai phá dữ liệu.

Phát hiện sự sai lệch (Deviation)

Nhiệm vụ này nhằm phát hiện sự sai lệch đáng kể giữa nội dung của tập

con dữ liệu thực và nội dung mong đợi. Hai mô hình sai lệch hay dùng là mô

hình sai lệch theo thời gian và sai lệch nhóm. Sai lệch theo thời gian là sự thay

đổi có ý nghĩa của dữ liệu theo thời gian. Sai lệch theo nhóm là sự khác nhau 7

không chờ đợi giữa dữ liệu trong hai tập con dữ liệu, ở đây tính đến cả trƣờng

hợp tập con này thuộc trong tập con kia, nghĩa là xác định dữ liệu trong một

nhóm con của đối tƣợng có khác đáng kể so với toàn bộ đối tƣợng không.

Theo cách này, các sai sót dữ liệu hay sự sai lệch so với giá trị thông thƣờng

đƣợc phát hiện.

Phát hiện luật kết hợp (Association Rules)

Ta xét một ví dụ: Xét một tập các mặt hàng trong một giỏ mua hàng. Vấn

đề đặt ra là tìm những mối liên quan giữa các mặt hàng trong giỏ.

Một cách chi tiết hơn, xét một tập các thuộc tính nhị phân với một tập các

bộ, mỗi bộ đƣợc gọi là một giỏ. Các thuộc tính nhị phân đƣợc gọi là các mục

hay các mặt hàng trong giỏ mà mỗi mục chỉ nhận một trong hai giá trị đúng

hoặc sai tuỳ thuộc vào khách hàng có mua mặt hàng đó trong giao dịch hay

không. Trên thực tế, loại dữ liệu này rất phổ biến và đƣợc gọi là dữ liệu giỏ.

Chúng thƣờng đƣợc thu thập thông qua công nghệ mã số, mã vạch trong các

hoạt động kinh doanh siêu thị.

Một giao dịch có thể chứa một số khoản mục, tập hợp tất cả các khoản mục

sẽ thuộc vào một không gian T nào đó mà mỗi giao dịch khi đó là một tập con

của T. Ta cần phát hiện những mối tƣơng quan quan trọng hoặc mối quan hệ,

mối kết hợp trong số các khoản mục chứa trong các giao dịch của một dữ liệu

nào đó sao cho sự xuất hiện của một số khoả mục nào đó trong giao dịch sẽ kéo

theo sự xuất hiện của một số khoản mục khác trong cùng một giao dịch đó.

Ta sẽ tìm hiểu luật kết hợp cụ thể hơn ở phần sau.

Mô hình hoá sự phụ thuộc (Dependence Modeling)

Nhiệm vụ này liên quan đến việc phát hiện sự phụ thuộc trong số các thuộc

tính. Những phụ thuộc này thƣờng đƣợc biểu thị dƣới dạng luật “nếu thì”: “nếu

(tiên đề là đúng) thì (kết luận là đúng)”. Về nguyên tắc, cả tiên đề và kết luận

của luật đều có thể là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, 8

tiên đề thƣờng là nhóm các giá trị thuộc tính và kết luận chỉ là một giá trị tuộc

tính. Lƣu ý là những luật này không phải hoàn toàn giống với sự phụ thuộc

CSDL đƣợc nêu ở phần 2.2. Hơn nữa, hệ thống có thể phát hiện các luật với

phần kết luận nhiều thuộc tính. Điều này khác với luật phân lớp trong đó tất cả

các luật cần phải có cùng một thuộc tính do ngƣời dùng chỉ ra trong kết luận.

Mô hình hoá nhân quả (Causation Modeling)

Nhiệm vụ này liên quan đến việc phát hiện mối quan hệ nhân quả trong

thuộc tính. Các luật nhân quả cũng là các luật “nếu - thì” giống các luật phụ

thuộc, nhƣng mạnh hơn. Luật phụ thuộc đơn giản chỉ ra một mối tƣơng hỗ

giữa tiên đề và kết luận của luật mà không có ý nghĩa nhân quả trong quan hệ

này. Do đó, cả tiên đề và kết luận có thể quan hệ dƣới sự ảnh hƣởng của một

biến thứ ba, tức là một thuộc tính hoặc có ở trong tiên đề hoặc có ở trong kết

luận. Luật nhân quả không chỉ chỉ ra mối tƣơng quan giữa tiên đề và kết luận

mà còn cho biết tiên đề thực sự tạo ra kết luận và mối quan hệ giữa hai thành

phần này là trực tiếp. Tập các mối quan hệ nhân quả có thể đƣợc biểu diễn

bằng đồ thị nhân quả.

Các quan hệ nhân quả cần phụ thuộc vào thời gian theo nghĩa là nguyên

nhân trƣớc kết quả (kết luận). Nguyên nhân và kết quả đều có ít nhất một sự

kiện thời gian đi kèm và thời gian của kết quả phải đi sau thời gian của nguyên

nhân. Mặc dù yếu tố thời gian làm rõ ý nghĩa nhân quả nhƣng hệ thống thƣờng

khó phân biệt các liên kết giả tạo.

Phân cụm, nhóm (Clustering).

Một nhiệm vụ của các hệ thống phát hiện tri thức là phân tích các đối

tƣợng dữ liệu dạng nhƣ các giỏ hàng mà không quan tâm tới lớp của chúng.

Các hệ thống này phải tự phát hiện ra các lớp và sinh ra một sơ đồ phân nhóm

của tập dữ liệu đó.

Tuy nhiên, chất lƣợng của việc phân nhóm này là một vấn dề khó có thể

xác định đƣợc. Bài toán phân nhóm xác định các nhóm dựa vào quan hệ nhiều

- nhiều, tức là bất kỳ thuộc tính nào cũng có thể đƣợc sử dụng để xác định các

nhóm và để dự báo các giá trị thuộc tính khác. Điều này trái với cách xác định

nhiều - một liên quan đến nhiệm vụ phân lớp các đối tƣợng, trong đó, một

thuộc tính đƣợc xem nhƣ lớp và tất cả các thuộc tính khác đƣợc sử dụng để

phán đoán giá trị cho thuộc tính lớp.

Phân lớp (Classification)

Trong nhiệm vụ phân lớp, mỗi bộ dữ liệu theo dạng giỏ mua hàng thuộc

về một lớp nào đó đã đƣợc xác định trƣớc. Các bộ dữ liệu bao gồm tập các

thuộc tính dự báo và một thuộc tính phân lớp cụ thể. Lớp của bộ đƣợc chỉ ra

bởi giá trị của thuộc tính lớp mà ngƣời dùng xác định trƣớc.

Ta xét ví dụ sau: Giả sử, mỗi bộ dữ liệu biểu diễn các thông tin về nhân

viên, trong đó các thuộc tính dự báo là tuổi, giới tính, trình độ học vấn, ... của

nhân viên đó và thuộc tính phân lớp là trình độ lãnh đạo của nhân viên. Mục

tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa các thuộc tính

dự báo và thuộc tính phân lớp, từ đó sử dụng mối quan hệ này để dự báo lớp

cho các bộ dữ liệu mới khác cùng khuôn dạng.

Trong trƣờng hợp những kiến thức đƣợc phát hiện biểu diễn dƣới dạng

các luật thì khuôn dạng của luật có thể là: “nếu các thuộc tính dự báo của một

bộ dữ liệu thoả mãn các điều kiện của tiên đề, thì bộ dữ liệu đó có lớp chỉ ra

trong kết luận”.

Hồi quy (Regression)

Về khái niệm, nhiệm vụ hồi quy tƣơng tự nhƣ phân lớp. Điểm khác nhau

chính là ở chỗ thuộc tính để dự báo là liên tục chứ không phải rời rạc. Việc dự

báo các giá trị số thƣờng đƣợc làm bởi các phƣơng pháp thống kê cổ điển, chẳng

hạn nhƣ hồi quy tuyến tính. Tuy nhiên, các phƣơng pháp mô hình hoá cũng đƣợc

sử dụng, chẳng hạn nhƣ cây quyết định, trong đó nút lá là mô hình tuyến tính phát

sinh tập các lớp giả (pseudo - class) có giá trị thuộc tính đích tƣơng tự nhau, sau

đó sử dụng phƣơng pháp quy nạp để thay thế các lớp trong luật quy nạp bằng tổ

hợp các giá trị của thuộc tính lớp cho các bộ dữ liệu theo luật.

Tổng hợp (Sumarization)

Nhiệm vụ tổng hợp chính là sản sinh ra các mô tả đặc trƣng cho một lớp.

Mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả

(hoặc hầu hết) các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp.

Các mô tả đặc trƣng thể hiện dƣới dạng luật có dạng sau: ”nếu một bộ dữ

liệu thuộc về một lớp đã chỉ ra trong tiên đề, thì bộ dữ liệu đó có tất cả các

thuộc tính đã nêu trong kết luận”. Cần lƣu ý là các luật này có những đặc trƣng

khác biệt so với luật phân lớp. Luật phát hiện đặc trƣng cho một lớp chỉ sản

sinh khi các bộ dữ liệu đã thuộc về lớp đó.

So sánh các nhiệm vụ phát hiện tri thức.

Điểm giống và khác giữa các nhiệm vụ phát hiện tri thức đƣợc tóm tắt

trong bảng sau:

Nhiệm vụ Kiểu phát hiện Mục đích Kiểu dự báo

Hƣớng hệ quản trị SQO Tối ƣu truy vấn Không học CSDL

Sự phụ thuộc Hƣớng hệ quản trị Thiết kế và duy trì Không học CSDL CSDL CSDL

Phát hiện sai lệch Mục đích chung Xác định trội Không học

Dự báo, xác định Phát hiện liên kết Mục đích chung Có học trội

Nhân quả Mục đích chung Dự báo, mô tả Không học

Phân nhóm Mục đích chung Dự báo, mô tả Không học

Phân lớp Mục đích chung Dự báo Có học

Hồi quy Mục đích chung Dự báo Có học

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

Tổng hợp Mục đích chung Dự báo Có học

Trong bảng này, cột đầu tiên chỉ ra nhiệm vụ phát hiện tri thức. Cột thứ

hai chỉ ra kiểu tri thức đƣợc phát hiện. Các kiểu có thể là hƣớng hệ quản trị

CSDL (nhƣ các luật SQO) hoặc phụ thuộc CSDL hoặc là mục đích chung (tức

là các nhiệm vụ phát hiện bổ trợ khác). Tri thức hƣớng hệ quản trị CSDL

thƣờng dùng trong thiết kế và giao dịch của một CSDL. Tuy nhiên, tri thức

hƣớng hệ quản trị CSDL cũng có thể dùng cho việc kiểm tra các luật tối ƣu

truy vấn ngữ nghĩa để cải thiện việc tìm hiểu ứng dụng. Trong khi tri thức theo

kiểu mục đích chung có thể đƣợc sử dụng theo các mục đích khác nhau tuỳ

thuộc vào nhu cầu của ngƣời dùng theo nghĩa mờ và nó có thể sử dụng hiệu

quả trong hệ quản trị CSDL. Tuy vậy, điểm khác biệt quan trọng là tri thức

hƣớng hệ quản trị CSDL yêu cầu độ chính xác cao hơn so với tri thức theo

mục đích chung.

Cột thứ ba trong bảng chỉ ra mục đích của việc phát hiện tri thức. Cột này

xuất phát từ cột hai. Mục đích chính của các tri thức hƣớng hệ quản trị CSDL

là khá cụ thể: Tối ƣu truy vấn (trong trƣờng hợp SQO) và thiết kế, duy trì

CSDL (trong trƣờng hợp sự phụ thuộc CSDL). Các tri thức theo kiểu mục đích

chung thƣờng đƣợc dùng co một sự kết hợp các mục đích dự báo, mô tả và xác

định trội. Dự báo liên quan đến xác định giá trị của các tri thức trên cơ sở xác

định giá trị của các thuộc tính khác. Kỹ thuật đặc trƣng là phân lớp và hồi quy.

Tuy nhiên, dự báo cũng dựa trên quan hệ nhân quả, mô hình hoá sự phụ thuộc

cũng nhƣ phát hiện luật kết hợp. Mô tả thƣờng gắn với tổng hợp, thông tin

gộp. Do vậy, mô tả là mục tiêu chính của phân nhóm và tổng hợp. Đối với hai

nhiệm vụ này, việc mô tả các thuộc tính chung của các tập dữ liệu đƣợc quan

tâm. Hơn nữa việc mô tả cũng khá quan trọng trong các nhiệm vụ xác định phụ

thuộc và quan hệ nhân quả. Cần chú ý là mục tiêu chính của phát hiện tri thức

phụ thuộc vào dạng mà tri thức biểu diễn, chẳng hạn, mạng nhân quả thích hợp

cho mục tiêu mô tả hơn là luật về sự phụ thuộc.

Cột thứ tƣ chỉ ra loại dự báo liên quan đến từng nhiệm vụ phát hiện tri

thức. Mặc dù các nhiệm vụ SQO và sự phụ thuộc CSDL phát hiện tri thức

hƣớng CSDL và theo mục tiêu cụ thể, nhƣng cũng có các nhiệm vụ dự báo liên

quan đến kiểu này. Nói chung, các nhiệm vụ SQO, sự phụ thuộc CSDL, liên

kết, nhân quả, sự phụ thuộc và phân cụm có kiểu dự báo nhiều - nhiều trong đó

giá trị của một vài thuộc tính có thể dùng để dự báo giá trị của các thuộc tính

khác. Một cách nhìn khác về quan hệ nhiều - nhiều là xem xét các nhiệm vụ

nhƣ một dạng phát hiện không có học, bởi vì ngƣời dùng không chỉ ra thuộc

tính mục tiêu và hệ thống có sự tự chủ hoàn toàn để quyết định thuộc tính nào

sẽ đƣợc đƣa ra trong tri thức. Nhiệm vụ phát hiện sự sai khác không hoàn toàn

đúng với mục tiêu dự báo nhƣng có thể nói nó liên quan đến việc phát hiện

không có học.

Nhiệm vụ phân lớp và hồi quy liên quan đến dự báo nhiều - một trong đó

giá trị của nhiều thuộc tính có thể đƣợc sử dụng để dự báo giá trị của một

thuộc tính do ngƣời dùng xác định trƣớc. Đối với nhiệm vụ tổng hợp, từ lớp

của một bộ dữ liệu, chúng ta có thể dự báo giá trị (hoặc khoảng giá trị, giá trị

trung bình, ...) của các thuộc tính khác. Tri thức đƣợc phát hiện phải bao gồm

quan hệ đó. Do vậy, tính tự chủ của hệ thống chỉ ở chỗ xác định các thuộc liên

quan đến giá trị thuộc tính đích và có hạn chế hơn so với các nhiệm vụ không

học. Tuy nhiên, các nhiệm vụ không học có thể chuyển thành có học.

Các đặc tính khác của phát hiện tri thức nhƣ tính thông minh và tính hữu

dụng không bao gồm trong bảng trên bởi vì chúng mang tính chủ quanvà thay

đổi lớn trong mỗi nhiệm vụ của từng kĩnh vực cụ thể.

Phát hiện tri thức hƣớng CSDL (SQO và sự phụ thuộc CSDL) có độ

chính xác cao. Đây là điểm khác biệt quan trọng so với các đòi hỏi của các

nhiệm vụ phát hiện tri thức khác. Nhiệm vụ phát hiện sự sai lệch liên quan đến

phát hiện tri thức với mức ý nghĩa do ngƣời dùng xác định. Nhiệm vụ phát

hiện liên kết cũng nhƣ thế với ngƣỡng tin cậy (ngƣỡng confidence) và tần suất

tƣơng đối (ngƣỡng hỗ trợ - support). Nhiệm vụ tổng hợp liên quan đến phát

hiện tri thức có tính phổ biến cao tức là luật đƣợc phát hiện phải bao hàm một

số dữ liệu (mà các nhiệm vụ khác nhƣ phân lớp không đòi hỏi nhƣ vậy).

Các nhiệm vụ nhƣ phát hiện sự phụ thuộc, nhân quả, phân lớp và hồi quy

chủ yếu liên quan đến phát hiện tri thức có độ chính xác cao.

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

HỢP

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

Khái niệm

Trong lĩnh vực Data Mining, mục đích của luật kết hợp (Association

Rule - AR) là tìm ra các mối quan hệ giữa các đối tƣợng trong một cơ sở dữ

liệu khổng lồ. Nội dung cơ bản của luật kết hợp đƣợc tóm tắt nhƣ sau:

-Cho cơ sở dữ liệu gồm các giao dịch T là tập các giao dịch t1, t2, …,

tn.

T = {t1, t2, …, tn}: T gọi là cơ sở dữ liệu giao dịch (Transaction

Database)

-Mỗi giao dịch ti bao gồm tập các đối tượng I (gọi là itemset).

I = {i1, i2, …, im}: Một itemset gồm k items gọi là k-itemset

-Mục đích của luật kết hợp là tìm ra sự kết hợp hay tương quan giữa

các items. Những luật kết hợp này có dạng X =>Y.

Trong kinh doanh, luật kết hợp X =>Y có thể hiểu rằng những ngƣời

mua các mặt hàng trong tập X cũng thƣờng mua các mặt hàng trong tập Y. (X

và Y gọi là itemset).

Ví dụ, nếu X = {Apple, Banana} và Y = {Cherry, Durian} và ta có luật

kết hợp X =>Y thì chúng ta có thể nói rằng những ngƣời mua Apple và

Banana thì cũng thƣờng mua Cherry và Durian.

Theo quan điểm thống kê, X đƣợc xem là biến độc

lập (Independent variable) còn Y đƣợc xem là biến phụ thuộc

(Dependent variable).

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

2.2.1. Thuật toán Apriori

- Thuật toán Apriori được dùng để phát hiện các luật kết hợp dạng

khẳng định (Positive Rule X=>Y) nhị phân (Binary Association Rules) chứ

không thể phát hiện các luật kết hợp ở dạng phủ định (Negative Association

Rule) chẳn hạn như các kết hợp dạng “Khách hàng mua mặt hàng A thường

KHÔNG mua mặt hàng B” hoặc “Nếu ủng hộ quan điểm A thường KHÔNG

ủng hộ quan điểm B”.

- Để thu đƣợc các luật kết hợp, ta thƣờng áp dụng 2 tiêu chí: minimum

support (min_sup) và minimum confidence (min_conf).

- Minimum support và Minimum confidence gọi là các giá trị ngưỡng

và phải xác định trƣớc khi sinh các luật kết hợp.

2.2.2 Ý tƣởng

- Tìm tất cả frequent itemsets: (k-itemset (itemsets gồm k items) đƣợc

dùng để tìm (k+1)- itemset): đầu tiên tìm 1-itemset (ký hiệu L1). L1 đƣợc dùng

để tìm L2 (2-itemsets). L2 đƣợc dùng để tìm L3 (3-itemset) và tiếp tục cho đến

khi không có k-itemset đƣợc tìm thấy.

- Từ frequent itemsets sinh ra các luật kết hợp mạnh (các luật kết hợp

thỏa mãn 2 tham số min_sup và min_conf).

2.2.3 Thuật toán

B1. Duyệt (Scan) toàn bộ transaction database để có đƣợc support S của

1-itemset, so sánh S với min_sup, để có đƣợc 1-itemset (L1).

B2. Sử dụng Lk-1 nối (join) Lk-1 để sinh ra candidate k-itemset. Loại bỏ

các itemsets không phải là frequent itemsets thu đƣợc k-itemset.

B3. Scan transaction database để có đƣợc support của mỗi candidate k-

itemset, so sánh S với min_sup để thu đƣợc frequent k –itemset (Lk).

B4. Lặp lại từ bƣớc 2 cho đến khi Candidate set (C) trống (không tìm

thấy frequent itemsets).

B5. Với mỗi frequent itemset I, sinh tất cả các tập con s không rỗng của

B6. Với mỗi tập con s không rỗng của I, sinh ra các luật s => (I-s) nếu

độ tin cậy (Confidence) của nó > =min_conf.

Ví dụ:

Chẳn hạn với I= {A1,A2,A5}, các tập con của I: {A1}, {A2}, {A5},

{A1,A2},{A1,A5},{A2,A5} sẽ có các luật sau

 {A1} => {A2,A5},{A2} =>{A1,A5},{A5} =>{A1,A2}

 {A1,A2} =>{A5},{A1,A5} =>{A2},{A2,A5} => {A1}

Ví dụ: Giả sử ta có có sở dữ liệu giao dịch (Transaction Database -

Hình 2.1. CSDL giao dịch

TDB) nhƣ sau :

Thuật toán Apriori khai phá luật kết hợp đƣợc mô tả qua các bƣớc sau(

với min-sup=2 (50%) và min-con =80%):

Hình 2.2. Minh họa các bước khai phá

Với frequent itemsets I ={B,C,E}, ta có tập con : {B}, {C}, {E},

{B,C},{B,E},{C,E}. Các luật đƣợc sinh ra với Confidence tƣơng ứng:

 {B} => {C,E}:2/3,{C} =>{B,E}:2/3,{E} =>{B,C}:2/3

 {B,C} =>{E}:2/2,{B,E} =>{C}:2/3,{C,E} => {B}:2/2

Với min_conf =80% ta có 2 luật kết hợp là:

Hình 2.3. Kết quả tìm luật kết hợp

{B,C} => {E} và {C,E} => {B}

Tuy nhiên thuật toán này có nhƣợc điểm sau:

- Tập C đƣợc tạo ra bằng cách kết những tập thƣờng xuyên với những

item trong giao tác, do đó phát sinh quá nhiều các tập không thƣờng xuyên

không cần thiết.

 104 frequent 1-itemsets  nhiều hơn 107 (≈104(104-1)/2) 2-

itemsets dự tuyển

 Một k-itemset cần ít nhất 2k -1 itemsets dự tuyển trƣớc đó.

- Với mỗi tập ứng cử viên C, thuật toán phải duyệt lại toàn bộ cơ sở dữ

liệu để tính độ hỗ trợ, điều này làm tăng quá nhiều thời gian xử lý. Vì vậy,

thuật toán sẽ không đạt hiệu quả tốt đối với các cơ sở dữ liệu lớn.

 Chi phí lớn khi kích thƣớc các itemsets tăng lên dần.

 Nếu k-itemsets đƣợc khám phá thì cần kiểm tra tập dữ liệu k+1

lần.

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

2.3.1 Thuật toán Fp_Growth

Thuật toán kinh điển Apriori tìm tập mục phổ biến thực hiện tốt bởi rút

gọn kích thƣớc các tập ứng cử nhờ kỹ thuật tỉa. Tuy nhiên, trong tình huống

mà số các mẫu nhiều, mẫu dài hoặc độ hỗ trợ cực tiểu thấp, các thuật toán

Apriori gặp phải chi phí lớn.

Chi phí cho số lƣợng khổng lồ các tập ứng cử. Ví dụ: nếu cứ 10^4 tập 1-

mục phổ biến thì thuật toán Apriori sẽ cần sinh ra hơn 10^7 các ứng cử 2-item

và thực hiện kiểm tra sự xuất hiện của chúng. Hơn nữa, để khám phá đƣợc một

số mẫu phổ biến kích thƣớc (độ dài) là l, thuật toán phải kiểm tra (2^l-2 ) các

mẫu phổ biến tiềm năng. Ví dụ l=100, chẳng hạn là {a1,a2,....,a100}, nó phải

sinh ra tổng số 2^100 =10^30 các ứng cử (đấy chính là số tập con của tập có

100 phần tử).

Đòi hỏi lặp lại nhiều lần duyệt CSDL để kiểm tra tập rất lớn các ứng cử.

Số lần duyệt CSDL của thuật toán Apriori bằng độ dài của mẫu phổ biến dài

nhất tìm đƣợc. Trong trƣờng hợp mẫu phổ biến dài hơn và CSDL lớn, có nhiều

bản ghi, điều này là không thể thực hiện đƣợc. Thuật toán Apriori chỉ thích

hợp cho các CSDL thƣa (sparse), với các CSDL dày (dense) thì thuật toán thực

hiện kém hiệu quả hơn.

Thuật toán tìm các tập phổ biến hiệu quả hơn thuật toán Apriori là thuật

toán Fp-tree và Fp-Growth.

2.3.2 Thuật toán Fp_Tree

Đƣợc gọi là cây mẫu phổ biến (frequent pattern tree hoặc gọi tắt là FP-

tree) dùng để nén dữ liệu thích hợp. Chỉ có các mục độ dài l (l-item) ở trong

cây và các nút của cây đƣợc sắp đặt để các nút xuất hiện thƣờng xuyên hơn có

thể dễ dàng chia sẻ với các nút xuất hiện ít hơn. CSDL lớn đƣợc nén chặt tới

cấu trúc dữ liệu nhỏ hơn (FP-tree), tránh đƣợc chi phí lặp lại duyệt qua CSDL.

Thuật toán xây dựng FP-tree:

Input: Cơ sở dữ liệu giao dịch DB và ngƣỡng hỗ trợ tối thiểu là ξ.

Output: Cây FP-Tree, cây chứa các mẫu phổ biến.

FP-tree được xây dựng theo các bước sau đây:

B1. Duyệt DB lần đầu để thu đƣợc tập F gồm các đối tƣợng phổ biến

(frequent item) và độ hỗ trợ (support count) của chúng. Sắp xếp các đối tƣợng

(item) trong F giảm dần theo supprort count ta đƣợc danh sách L.

B2. Tạo nút gốc T.

Tạo bảng Header H có |F| dòng và đặt tất cả các node –link chỉ đến null.

B3. For each giao tác G thuộc DB

a. Chọn các đối tƣợng phổ biến của G và sắp xếp theo thứ tự của danh

sách L đƣợc dạng [p, P], trong đó p là phần tử đầu tiên và P là danh sách còn

lại.

b. Call Insert_Tree([p,P], T);

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

Khai phá luật kết hợp là một vấn đề khai phá dữ liệu quan trọng đã đƣợc

nghiên cứu rông rãi. Một thuật toán nhanh và đơn giản cho danh sách các

thuộc tính giao nhau sử dụng Bảng dữ liệu hỏng đƣợc trình bày. FIT đƣợc

thiết kế để tính toán một cách hiệu quả tất cả các tập phổ biến trong cơ sở dữ

liệu lớn. Nó triển khai các ý tƣởng tƣơng tự nhƣ Eclat nhƣng có hiệu suất tính

toán tốt hơn nhiều so với Eclat do hai khía cạnh:

1) FIT có tổng số các phép so sánh ít hơn cho từng hoạt động giao nhau

giữa hai danh sách thuộc tính,

2) FIT giảm đáng kể tổng số hoạt động giao nhau. Các kết quả thực nghiệm

chứng minh rằng hiệu suất của FIT là tốt hơn nhiều so với các thuật toán

Apriori và Eclat

Với một cơ sở dữ liệu D, và minsup, mô tả chính thức của các phƣơng pháp

đơn giản đƣợc thể hiện nhƣ sau :

Bƣớc 1)

Chuyển đổi D vào các thuộc tính định dạng danh sách và tính toán

L1. Sắp xếp tài liệu và danh sách thuộc tính tƣơng ứng trong L1 vào trật

tự không tăng theo số lƣợng các thuộc tính trong danh sách. Đánh dấu

tất cả các tập phổ biến ở L1 không truy cập

Bƣớc 2)

Thiết lập một bảng băm (hb) với | D | mục.

Thiết lập từng mục trong hb đến -1. Đặt k đến 1.

Bƣớc 3)

Nếu tất cả các tập phổ biến trong Lk đã đƣợc truy cập, và k bằng 1, các

tính toán chấm dứt. Nếu tất cả các tập phổ biến trong Lk đã đƣợc truy

cập, và k không bằng 1, giảm k bằng 1.

Bƣớc 4)

Quét các danh sách thuộc tính của các tập phổ biến không truy cập đầu

tiên (X) trong Lk ,. Đối với mỗi thuộc tính (vx) bộ hb [vx] tới 1. Đánh

dấu X truy cập.

Bƣớc 5)

Quét các danh sách thuộc tính của bất kỳ của các tập phổ biến khác (Y)

theo sau X trong Lk. Đối với mỗi thuộc tính (ty), nếu hb [vy] bằng 0, loại

bỏ ty. Nếu hb [vy] bằng 1, đặt vy vào danh sách thuộc tính kết quả. Nếu

số lƣợng các thuộc tính trong danh sách thuộc tính kết quả là không ít

hơn minsup, đặt các tập phổ biến (X∩Y) và danh sách thuộc tính kết quả

vào Lk + 1. Đánh dấu các tập phổ biến X∩Y không truy cập trong Lk + 1

Bƣớc 6)

Thiết lập lại các mục trong hb đến -1. Nếu Lk+1 không phải là trống, tăng

k bằng 1 và quay trở lại bƣớc 4). Nếu không, đi đến bƣớc 3).

2.3.4 Thuật toán NSFI ALGORITHM

Khai thác tập phổ biến là một yếu tố cơ bản liên quan đến nhiều vấn đề

khai thác dữ liệu hƣớng vào việc tìm kiếm mô hình thú vị trong dữ liệu. Gần

đây các thuật toán PrePost, một thuật toán mới cho khai thác tập phổ biến dựa

trên ý tƣởng của N-list, mà trong nhiều trƣờng hợp làm tốt hơn. Tác giả đã đề

xuất một phiên bản cải tiến của PrePost, N-list và bao hàm dựa trên thuật toán

khai thác tập phổ biến (NSFI) thuật toán có sử dụng một bảng băm để tăng

cƣờng quá trình tạo ra các N-list liên kết với 1 tập phổ biến và tồn tại đƣợc cải

thiện N-list thuật toán giao nhau. Hơn nữa, hai định lý mới đƣợc đề xuất để

xác định '' bao hàm index '' của thƣờng xuyên 1-tập phổ biến dựa trên khái

niệm N-list. Sử dụng chỉ số bao hàm, NSFI có thể xác định các nhóm của tập

phổ biến mà không xác định N-list ch liên kết với chúng. Kết quả cho thấy

NSFI nhanh hơn so PrePost về thời gian chạy và sử dụng bộ nhớ và nhanh hơn

so với clat triển về mặt thời gian chạy.

Deng et al. [3] đề xuất một chức năng giao điểm N-danh sách để xác

định giao điểm của hai N-danh sách đó là O (n + m + k) trong đó n, m và k là

độ dài của đầu tiên, thứ hai và kết quả là N-danh mục (chức năng di chuyển

qua danh sách N- kết quả nhƣ vậy là để hợp nhất cùng PP-mã). Trong phần

này chúng tôi trình bày một chức năng giao điểm N-list đƣợc cải tiến để cung

cấp cho O (n + m). Chức năng cải tiến này cung cấp những lợi thế mà nó

không đi qua các kết quả N-list để hợp nhất các mã PP- cùng. Hơn nữa, chúng

tôi cũng đề xuất một chiến lƣợc đầu bỏ bao gồm ba bƣớc: (i) xác định tổng tần

số đầu tiên và thứ hai N-danh sách ký hiệu là SF, (ii) cho mỗi Ci PP-mã, mà

không thuộc về kết quả N-list, cập nhật SF = SF - C.frequency, và (iii) nếu SF

giảm xuống dƣới \ minSup xn] dừng lại (các tập phổ biến hiện đang đƣợc coi

là không thƣờng xuyên). Với các chức năng trên giao điểm N-list cải thiện

Thuật toán N-list cải tiến

function NL_intersection (PS1, PS2)

1. let PS3 ← ∅, sF ← σ(PS1) + σ (PS2), i = 0, j = 0 and f = 0

2. while i < |PS1 | and j < |PS2| do

3. if PS1[i].pre < PS2[j].pre then

4. if PSi[i].post > PS2[j].post then

5. if |PS3| > 0 and pre value of the last element in PS3 equal

to PS1[i].pre then

6. increase the frequency value of the last element in PS3 by

PS2[j ] .frequency

7. else

8. add the tuple (PS1[i].pre, PS1[i].post, PS2[j]. frequency)

to PS3

9. increase f by PS2[j ].frequency and increase j by 1

10. else

11. sF = sF - PSi[i] .frequency and increase i by 1

12. else

13. sF = sF - PS2[j].frequency and increase j by 1

14. if sF < threshold then

15. return null // stop the procedure

16. return PS3 and f

procedure Find_Subsume (l1) // chỉ số bao hàm thủ tục

1. for i ← 1 to | l1 | - 1 do 2. for j ← i - 1 to 0 do 3. if j ϵ l1 [i] .Subsumes then continue 4. if checkSubsume (l1 [i] N-list, l1 [j ] .N-list) is true then

5. add l1 [ j ] . name and its index, j, to l1[i].Subsumes

6. . add all elements in l1[j ]. Subsumes to l1[i] . Subsumes

function checkSubsume (Na, Nb)

1. . let i = 0 and j = 0

2. while j < | Na | and i < |Nb| do

3. if Nb [i] .pre < Na[j] .pre and Nb[i].post > Na[j].post then

4. increase j by 1

5. else increase i by 1

6. if j = |Na| then

7. return true

8. return false

Định lý đƣợc đề xuất trong Song et al, đƣợc đại diện trong phái. 2.5,

cũng đã đƣợc thông qua trong thuật toán NSFI để tăng tốc độ Thông qua hoạt

động của định lý này cũng giúp làm giảm nhu cầu sử dụng bộ nhớ các thuật

toán của NSFI, bởi vì nó không phải là cần thiết để xác định và lƣu trữ các N-

danh sách liên kết với một nhóm các tập phổ biến để xác định ngƣỡng hỗ trợ.

Đầu tiên các thuật toán NSFI tạo PPC-cây, sau đó đi qua cây này để tạo

ra N-danh sách liên quan đến việc thƣờng xuyên 1-itemset. Sau đó, một chiến

lƣợc chia-và-chinh phục, cùng với khái niệm chỉ số bao hàm, đƣợc sử dụng để

tôi tập phổ biến. Đối với mỗi phần tử X, nếu chỉ số bao hàm của nó có các yếu

tố, tập hợp các tập phổ biến đƣợc sản xuất bằng cách kết hợp với các yếu tố X

trong chỉ số bao hàm của nó là thƣờng xuyên và có sự hỗ trợ tƣơng tự nhƣ X.

Đối với mỗi nguyên tố còn lại không đƣợc chứa trong các bao hàm chỉ số của

X, thuật toán sẽ kết hợp chúng với X để tạo ra các tập phổ biến ứng cử viên

thƣờng xuyên. Lƣu ý rằng đối với 2 tập phổ biến hoặc nhiều hơn, thuật toán

không sử dụng các chỉ số bao hàm.

Thuật toán NSFI ALGORITH

Input: A dataset DB and minSup

Output: FIs, the set of all frequent itemsets

1. Construct_PPC_tree (DB, minSup) to generate R., l1, H1 and threshold

2. Generate_NList (R, l1)

3. Find_Subsume (l1)

4. let FIs ← l1 and Subsume ← {}

5. Find_FIs (l1, Subsumes)

6. return FIs

procedure Generate_NList (R, l1)

1. let C ← (R.pre, R.post, R. frequency)

2. add C to H1[R. .name] .N-list

3. increase H1 [R. .name] . frequency by C. frequency

4. for each child in R. .children do

5. Generate_NList(child)

procedure Find_FIs (Is, S)

1. for i ← Is. size - 1 to 0 do

2. let FIsnext ← 0

3. if | Is [i] . Subsumes | > 0 then

4. let S be the set of subset generated from all elements of

Is [i] . Subsumes

5. for each s in S do

6. add (s. Is [i] . frequency) to FIs //using theorem 4

7. else if |Is[i] | = 1 then

8. S ← {}

9. indexS = |Is [i] .Subsumes | - 1

10. for j ← i - 1 to 0 do

11. if indexS ≥ 0 and Is [i].Subsumes[indexS] = j then 12. indexS = indexS - 1 and continue

13. let efirst be the first item of Is[j]

14. FI ← { efirst } + Is[i] 15. (FI.N-list and FI. frequency) ← NL_intersection (Is [j ] .N-list, Is [i] .N-list)

16. if FI.N-list = null then continue

17. if(FI.frequency ≥ threshold) then

18. add FI to FIs

19. insert FI at first in FIsnext

20. for each subsume in S do

21. let f = FI + subsume

22. f.frequency = FI.frequency

23. add f to FIs // using theorem 4

24. Find_FIS (FIsnext, S)

2.4 Thuật toán FSM

Năm 2005, Yu-Chiang Li và đồng nghiệp tại Khoa Khoa học máy tính và

Kỹ thuật thông tin của Đại học Chung Chen, Đài Loan giới thiệu thuật toán

FSM (Fast Share Measure), đây là một thuật toán hiệu quả tìm ra tất cả các tập

mục cổ phần cao. Thay vì khai thác tính chất Apriori, thuật toán FSM sử dụng

một số tính chất của tập mục cổ phần cao để rút gọn các tập mục ứng viên.

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

Ký hiệu:

 Giá trị cổ phần tối thiểu (minimum local measure value) là min_lmv,

min_lmv= minShare x Tmv;

 Độ dài cực đại (maximum length) của các giao tác trong cơ sở dữ liệu là

ML,

;

 Giá trị cực đại (maximum value) của tất cả các mục trong cơ sở dữ liệu

là MV,

Cơ sở lý thuyết của thuật toán đƣợc thể hiện trong mệnh đề sau:

Cho minShare và k-itemset X không là tập mục cổ phần cao. Nếu:

thì tất cả các tập cha của X không là tập mục cổ phần cao.

Đặt , CF(X) gọi là hàm tới hạn.

Mệnh đề trên đảm bảo rằng: nếu X không là tập mục cổ phần cao và

thì không có tập cha nào của X là tập mục cổ phần cao.

Thuật toán FSM dựa vào mệnh đề này để tỉa các tập mục ứng viên.

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

Thuật toán duyệt nhiều lần CSDL, ở lần duyệt thứ k, Ck lƣu các tập mục

ứng viên, RCk lƣu các tập mục nhận đƣợc sau khi kiểm tra hàm tới hạn CF, Fk

lƣu các tập mục cổ phần cao nhận đƣợc.

Giống nhƣ thuật toán Apriori, ban đầu mỗi mục dữ liệu là một ứng viên.

Trong lần duyệt thứ nhất, thuật toán duyệt cơ sở dữ liệu, tính giá trị của mỗi

mục dữ liệu. Mỗi ứng viên 1- tập mục X sẽ bị tỉa nếu CF(X)< min_lmv. Trong

mỗi lần duyệt tiếp theo, các tập mục ứng viên đƣợc tạo ra bằng cách nối hai (k-

1)-itemset trong RCk-1 nếu chúng có (k-2) mục đầu giống nhau và nhận đƣợc k-

itemset, kết nạp vào tập Ck (giả sử các mục của cơ sở dữ liệu đã đƣợc sắp thứ

tự). Tất cả k tập con với độ dài (k-1) của mỗi k-itemset trong Ck là phải thuộc

RCk-1 , nếu không k-itemset này sẽ bị tỉa. Sau khi Ck đƣợc sinh ra, xóa tập RCk-1

. Tiếp theo, thuật toán duyệt cơ sở dữ liệu để tìm tập mục cổ phần cao. Với mỗi

thì X là tập mục cổ tập mục X trong Ck , nếu tập mục này có

phần cao và đƣợc thêm vào Fk; Ngƣợc lại, xét hàm tới hạn CF, nếu

thì tập ứng viên X bị loại khỏi RCk. Quá trình trên cứ lặp

cho đến khi không có tập mục ứng viên nào đƣợc sinh ra.

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

Cho tập các mục (item) . Một giao tác (transaction) T là một

tập con của I, TI. Cơ sở dữ liệu là một tập các giao tác .

Mỗi giao tác đƣợc gán một định danh TID. Một tập mục con , gồm k

mục phân biệt đƣợc gọi là một k-itemset. Giao tác T gọi là chứa tập mục X

nếu .

MV (Measure Value – Giá trị tập mục trong giao tác): Ta ký hiệu giá trị

, có giá trị là số tự nhiên của mục ip trong giao tác Tq là

(nhƣ số lƣợng đã bán của một mặt hàng trong giao tác), tức là,

nếu và nếu .

TMV (Transaction Measure Value – Giá trị giao tác): Giá trị của giao tác

Tq là tổng giá trị các mục dữ liệu trong giao tác, ký hiệu là tmv(Tq), tức là

. Tổng giá trị các mục dữ liệu trong cơ sở dữ liệu DB,

ký hiệu là Tmv, . Tƣơng tự, với cơ sở dữ liệu con

, .

Ví dụ 2.1 : Cho cơ sở dữ liệu bảng 2.1, mv(D,T01)=1, mv(C,T03)=3,

tmv(T01)=7, tmv(T03)=10, Tmv(DB) = 56.

TID A C D E F G H tmv B

T01 T02 T03 T04 T05 T06 T07 T08 lmv 1 0 0 0 0 0 0 4 5 1 0 4 0 3 3 3 0 14 1 0 3 0 2 1 1 0 8 1 0 0 1 0 0 2 0 4 0 4 0 0 0 0 0 1 5 1 0 0 0 0 0 0 1 2 1 3 0 0 0 0 0 0 4 7 7 10 5 5 6 10 6 56

1 0 3 4 0 2 4 0 14 Bảng 2.1. Cơ sở dữ liệu

Ký hiệu là tập các giao tác chứa tập mục X,

IMV (Itemset Measure Value): Cho giao tác Tq chứa tập mục X. Giá trị của

tập mục X trong Tq, ký hiệu , là tổng giá trị của các mục ip trong

thuộc X, , với .

LMV (Local Measure Value):Cho tập mục X, là tập các giao tác chứa X.

Giá trị của tập mục X ký hiệu lmv(X), là tổng giá trị của tập mục X tại các

giao tác trong , tức là .

Sh (Share Value): Cổ phần hay đóng góp của tập mục X , ký hiệu là Sh(X), là

tỉ số giữa giá trị của tập mục X và tổng giá trị của tất cả các mục trong cơ sở dữ

liệu, tức là: .

Sh(X) cho biết trong tổng giá trị của tất cả các mục dữ liệu trong cơ sở dữ

liệu thì giá trị của tập X chiếm bao nhiêu phần trăm. Ví dụ, với CSDL giao tác

bán hàng, Sh(X)=30% tức là trong tổng số lƣợng hàng đã bán đƣợc thì số

lƣợng các mặt hàng trong X chiếm 30%.

MinShare: ngƣỡng cổ phần (minimum share) minShare s% và tập mục X. X

đƣợc gọi là tập mục cổ phần cao nếu Sh(X) ≥ minShare. Trƣờng hợp ngƣợc

lại, X đƣợc gọi là tập mục cổ phần thấp.

Ký hiệu giá trị cổ phần tối thiểu (minimum local measure value) là

min_lmv, min_lmv= minShare x Tmv, có thể thay điều kiện Sh(X) ≥ minShare

trong định nghĩa 2.4 bởi điều kiện .

Ví dụ: Xét cơ sở dữ liệu cho ở bảng 2.1 và minShare=30% . Bảng 2.2 là

giá trị của các mục dữ liệu và cổ phần của chúng.

Mục dữ liệu A B C D E F G H Tổng số

5 14 14 8 4 5 2 4 56 lmv(ip)

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.

8,9% 25,0% 25,0% 14,3% 7,1% 8,9% 3,6% 7,1% 100% Sh(ip)

Xét , giá trị của tập mục X là:

Đóng góp của tập mục X:

Do đó, là tập mục cổ phần cao.

Bảng 2.3 biểu diễn tất cả các tập mục cổ phần cao của cơ sở dữ liệu bảng

2.1.

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

Tập mục BD BCD BC

cổ phần cao lmv(X) 22 27 21

Sh(X) 37,5% 39,3% 48,2%

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

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

Cho CSDL giao tác DB và ràng buộc cổ phần minShare, khai phá tập mục cổ

phần cao là tìm tập HS (High Share), chứa tất cả các tập mục cổ phần cao, tức

là tập .

Thủ tục mô tả thuật toán FSM nhƣ sau :

Thuật toán FSM

Input: Cơ sở dữ liệu giao tác DB, ngƣỡng cổ phần minShare (s%).

Output: Tập F gồm các tập mục cổ phần cao.

Method:

1. k:=1, F1:=, C1:=I;

2. for each TDB // duyệt cơ sở dữ liệu DB

3. tính giá trị lmv(ip) và CF(ip) của các mục ip trong C1 ;

4. for each ipC1

5. if lmv(ip) ≥min_lmv then

7. else if then

11. for k:=2 to h

12. begin

13. for each Xp, Xq ∈RCk-1

14. Ck :=Apriori-join(Xp, Xq);

15. for each T∈DB // duyệt cơ sở dữ liệu DB

16. tính giá trị lmv(X) và CF(X) của các ứng viên X trong Ck;

17. for each X∈Ck

18. if lmv(X)≥ min_lmv

19.

20. else if CF(X)

21.

22. RCk:= Ck;

22. end

23. return ;

Nhận xét:

- Dữ liệu cho khai phá tập mục phổ biến là trƣờng hợp đặc biệt của dữ liệu

cho khai phá cổ phần cao khi tất cả các mục dữ liệu trong các giao tác có giá trị

là 0 hoặc 1.

- Tập mục cổ phần cao mang ý nghĩa khác với tập mục phổ biến. Tập mục

phổ biến chỉ quan tâm đến số lần xuất hiện của tập mục trong các giao tác,

trong khi đó tập mục cổ phần cao quan tâm đến tổng giá trị các mục dữ liệu

của tập mục trong các giao tác. Tập mục phổ biến quan tâm xem nhóm hàng X

(tập mục) có bán đƣợc hay không mà bỏ qua các tham số rất quan trọng là tổng

số lƣợng hàng bán đƣợc hoặc tổng lợi nhuận mang lại,…Với ngƣỡng

minShare cho trƣớc, một tập mục X có thể chỉ chứa trong một số ít giao tác của

CSDL nhƣng lại là tập mục cổ phần cao nếu cổ phần Sh(X) của nó vƣợt

ngƣỡng minShare. Kể cả khi khai phá trên tập dữ liệu có giá trị nhị phân ( 0

hoặc 1) thì khai phá tập mục cổ phần cao cũng cho kết quả khác với khai phá

tập mục phổ biến. Chẳng hạn, với CSDL cho trong bảng 2.4, tập mục

chỉ xuất hiện trong giao tác T01, có cổ phần

và độ hỗ trợ . Nếu ngƣỡng cổ phần minShare=30% thì X là

tập mục cổ phần cao, cũng lấy ngƣỡng độ hỗ trợ minsup=30% thì X không

phải tập mục phổ biến.

TID A B C D E F G H tmv

1 0 0 1 0 2 1 1 1 0 0 3 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 0 0 1 0 1

6 1 T01 1 0 T02 2 0 T03 2 0 T04 1 1 T05 12 2 lmv Bảng 2.4. CSDL minh họa ngữ nghĩa của tập mục cổ phần cao.

- Tính chất cơ bản đƣợc khai thác để xây dựng các thuật toán khai phá tập

mục phổ biến là tính chất Apriori. Dễ thấy, tính chất này không còn đúng với

ràng buộc cổ phần. Ví dụ, xét cơ sở dữ liệu ở bảng 2.1 với minShare=30%,

lmv(BCD)=27, lmv(BC)=21, lmv(B)=14, Sh(BCD)=27/56=48,2%,

Sh(BC)=21/56=37,5%, Sh(B)=14/56=25,0%. Nhƣ vậy, BCD là tập mục cổ

phần cao, tập con của nó BC là tập mục cổ phần cao nhƣng tập con khác B lại

không phải.

Do đó không thể áp dụng các thủ pháp sử dụng tính chất Apriori vào việc

khai phá tập mục cổ phần cao. Đã có nhiều công trình nghiên cứu các thuật

toán tìm tập mục cổ phần cao, các tác giả đã đề xuất một số thuật toán nhƣ

thuật toán ZP, ZSP, SIP, FSM. Trong số các thuật toán đó, thuật toán FSM là

một thuật toán hiệu quả.

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

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

Vào thời điểm cuối năm học, sau khi có bảng điểm của lớp, của trƣờng

và muốn đƣa ra một vài kết luận nào đó về tình hình học tập của học sinh

trƣờng mình phụ trách. Nhà trƣờng cùng các thầy cô bộ môn sẽ làm sẽ thực

hiện:

- Thứ nhất : tính điểm trung bình. Đây là một trong những cách đơn giản

nhất. Dựa vào điểm trung bình có thể đƣa ra vài nhận xét về tình hình học tập

của học sinh. Giả sử năm nay điểm trung bình tổng kết của của một học sinh là

7.5 nhƣ vậy có thể nhận xét “nóng vội” cho rằng rằng năm nay học sinh này

học chƣa tốt. Tất nhiên những nhận xét này là “nóng vội” vì có thể có học sinh

điểm rất cao, ngƣợc lại cũng có điểm rất thấp. Rõ ràng tính trung bình rất đơn

giản và “mạnh mẽ” nhƣng không đánh giá hết đƣợc năng lực của học sinh đó.

Ví dụ: học sinh đó học môn Toán, Sinh học,Thể dục học rất tốt thì em đó có

thể phát triển năng khiếu Thể dục thể thao….

- Thứ hai, dựa vào điểm tổng kết trung bình môn khó có thể đánh giá đƣợc

hết đƣợc các môn yếu kém của học sinh hoặc những năng khiếu của học sinh

cũng nhƣ trình độ chuyên môn của giáo viên. Ban giám hiệu không có đánh giá

chính xác đƣợc cần khắc phục yếu kém môn nào, cần đầu tƣ trọng điểm.

- Thứ 3: Học sinh không biết mình nên tập chung chọn môn nào để thi đại

học, hay không biết chọn nghành nghề trong tƣơng lai.

Vài dòng nêu trên để chúng ta thấy đƣợc rằng việc phân tích, đánh giá

kết quả học tập của học sinh trong nhà trƣờng không phải là chuyện đơn giản.

Nó đòi hỏi Ban giám hiệu nhà trƣờng, các nhà quản lý giáo dục có một sự đầu

tƣ, nghiên cứu, tìm tòi và sáng tạo nhằm đƣa ra đƣợc các phân tích, đánh giá

đúng đắn nhất, chính xác nhất về kết quả học tập của học sinh từ đó đề ra định

hƣớng, hoạch định cho nhà trƣờng trong việc đầu tƣ bồi dƣỡng giáo viên bộ

môn còn yếu, phát hiện học sinh giỏi để bồi dƣỡng, học sinh kém để phụ đạo,

có kế hoạch tăng giờ, tăng tiết, định hƣớng nghề nghiệp cho học sinh dựa trên

sở thích, năng khiếu môn học v.v… Bản thân cũng đã và đang từng trải qua

những khó khăn, vất vả trên và em cố gắng vận dụng những kiến thức đƣợc

học tại lớp Cao học ngành khoa học máy tính của Trƣờng Đại học Công nghệ

thong tin và truyền thông Thái Nguyên để đƣa ra một công cụ hỗ trợ phân tích

điểm số của học sinh ra đa dạng hơn, đa chiều hơn, nhiều góc độ hơn nhằm

giúp cho Ban giám hiệu, các nhà quản lý giáo dục có thêm cơ sở để đánh giá

đúng đắn nhất, chính xác nhất về tình hình học tập của học sinh, hoạt động

giảng dạy của giáo viên và giúp các em có sự đánh giá chính xác năng lực và

năng khiếu của mình trong việc định hƣớng tƣơng lai.

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

Trong các thuật toán luật kết họp đã tìm hiểu ở Chƣơng 2 thì thuật toán

FMS có tốc độ tƣơng đối nhanh, thích hợp với dữ liệu số khi không có phần tử

ngoại lai hay giá trị nhiễu. Và thật vậy, dữ liệu điểm của học sinh hiện nay đáp

ứng tốt yêu cầu của thuật toán FSM (dữ liệu số, điểm số trải dài chỉ từ 0- 10 và

không có phần tử nhiễu). Từ đó, em mạnh dạn đề xuất sử dụng thuật toán FSM

để giải quyết bài toán đƣa ra.

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

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

Chƣơng trình minh họa các thuật toán phân mảnh đƣợc viết bằng ngôn

ngữ C# trên bộ Visual Studio 2013 sử dụng phiên bản .Net Framewok 4.0. Yêu

cầu tối thiểu của hệ thống khi sử dụng chƣơng trình:

- Cài đặt .Net Framework phiên bản 4.0 trở lên.

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

Mô tả dữ liệu đầu vào

Dữ liệu về điểm số của trƣờng Trung học đƣợc lƣu trữ dƣới dạng tệp excel

nhƣ sau:

Để chuẩn hóa dữ liệu sử dụng trong thuật toán, tệp đầu vào cần đƣợc xử lý

qua các bƣớc sau:

 Loại bỏ các môn học mà có điểm số là chữ (ví dụ mộ Mỹ thuật ở

hình trên)

 Chuyển tên các môn học về dạng không dấu và xóa bỏ dấu cách

 Lƣu lại tệp dƣới dạng file .csv

Sau bƣớc xử lý, tệp dữ liệu đầu vào của chƣơng trình sẽ có cấu trúc nhƣ

 Dòng đầu tiên ghi tên của các môn hoc, mỗi môn học đƣợc phân

cách nhau bằng dấu phẩy

 Mỗi bản ghi về điểm đƣợc biểu diễn trên một dòng, mỗi dòng chứa

giá trị về điểm của các môn học

 Các giá trị của mỗi môn học đƣợc biểu diễn bằng số thực, phân cách

nhau bởi dấu phẩy, các điểm không có giá trị thì đƣợc biểu diễn bằng

giá trị 0.

Hình 3.1. Ví dụ về dữ liệu đầu vào cho thực nghiệm

Ví dụ về tệp dữ liệu điểm học sinh sau khi chuyển đổi về dạng chuẩn:

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

Hình 3.2. Giao diện chương trình thực hiện

Giao diện chính của chƣơng trình nhƣ sau:

Để thực hiện thuật toán, chọn vào nút “Chọn tệp” và lựa chọn tệp dữ liệu

theo đúng định dạng đƣợc mô tả trong 3.3.2. Sau khi chƣơng trình tải dữ liệu

vào bộ nhớ, ta nhập ngƣỡng cổ phần tối thiểu (minShare) để tìm tập mục cổ

phần cao và ngƣỡng tin cậy tối thiểu (minConf) để tìm các luật kết hợp thỏa

mãn, sau đó nhấn nút “Thực hiện”. Kết quả thử nghiệm với bộ dữ liệu mẫu

trong hình 3.1 với ngƣỡng minShare = 40% và minConf = 95% nhƣ sau:

Hình 3.3.Kết quả

3.4 Đánh giá:

- Dựa vào kết quả

*, Với các tập phổ biến có trọng số( NguVan, Toan, VatLy, TinHoc)

đƣợc các tập luật sau:

NguVan  Toan,VatLy, TinHoc có độ tin cậy là : 100%

Toan  NguVan, VatLy,TinHoc có độ tin cậy là : 100%

VatLy  NguVan, Toan, TinHoc có độ tin cậy là : 100%

TinHoc  NguVan, Toan,VatLy, có độ tin cậy là : 100%

NguVan, Toan VatLy, TinHoc có độ tin cậy là : 100%

NguVan, VatLy  Toan, TinHoc có độ tin cậy là : 100%

Toan,VatLy  NguVan, TinHoc có độ tin cậy là : 100%

Toan,Tin Hoc  NguVan, VatLy có độ tin cậy là : 100%

VatLy,Tin Hoc  NguVan, Toan có độ tin cậy là : 100%

NguVan, Toan, VatLy  TinHoc có độ tin cậy là : 100%

NguVan, Toan, TinHoc  VatLy có độ tin cậy là : 100%

NguVan, VatLy, TinHoc  Toan có độ tin cậy là : 100%

Toan, VatLy, TinHoc  NguVan có độ tin cậy là : 100%

*, Với các tập phổ biến có trọng số( NguVan, Toan, SinhHoc, TinHoc)

đƣợc các tập luật sau:

NguVan  Toan,SinhHoc, TinHoc có độ tin cậy là : 100%

Toan  NguVan, SinhHoc,TinHoc có độ tin cậy là : 100%

SinhHoc  NguVan, Toan, TinHoc có độ tin cậy là : 100%

TinHoc  NguVan, Toan,SinhHoc, có độ tin cậy là : 100%

NguVan, Toan SinhHoc, TinHoc có độ tin cậy là : 100%

NguVan, SinhHoc  Toan, TinHoc có độ tin cậy là : 100%

Toan,SinhHoc  NguVan, TinHoc có độ tin cậy là : 100%

Toan,Tin Hoc  NguVan, SinhHoc có độ tin cậy là : 100%

SinhHoc,Tin Hoc  NguVan, Toan có độ tin cậy là : 100%

NguVan, Toan, SinhHoc  TinHoc có độ tin cậy là : 100%

NguVan, Toan, TinHoc  SinhHoc có độ tin cậy là : 100%

NguVan, SinhHoc, TinHoc  Toan có độ tin cậy là : 100%

Toan, SinhHoc, TinHoc  NguVan có độ tin cậy là : 100%

*, Với các tập phổ biến có trọng số( NguVan, Toan, LichSu, TinHoc)

đƣợc các tập luật sau:

NguVan  Toan,LichSu, TinHoc có độ tin cậy là : 100%

Toan  NguVan, LichSu,TinHoc có độ tin cậy là : 100%

LichSu  NguVan, Toan, TinHoc có độ tin cậy là : 100%

TinHoc  NguVan, Toan,LichSu, có độ tin cậy là : 100%

NguVan, Toan LichSu, TinHoc có độ tin cậy là : 100%

NguVan, LichSu  Toan, TinHoc có độ tin cậy là : 100%

Toan, LichSu  NguVan, TinHoc có độ tin cậy là : 100%

Toan,Tin Hoc  NguVan, LichSu có độ tin cậy là : 100%

LichSu,Tin Hoc  NguVan, Toan có độ tin cậy là : 100%

NguVan, Toan, LichSu  TinHoc có độ tin cậy là : 100%

NguVan, Toan, TinHoc  LichSu có độ tin cậy là : 100%

NguVan, LichSu, TinHoc  Toan có độ tin cậy là : 100%

Toan, LichSu, TinHoc  NguVan có độ tin cậy là : 100%

*, Với các tập phổ biến có trọng số( NguVan, Toan, LichSu, CongNghe)

đƣợc các tập luật sau:

NguVan  Toan,LichSu, CongNghe có độ tin cậy là : 100%

Toan  NguVan, LichSu,CongNghe có độ tin cậy là : 100%

LichSu  NguVan, Toan, CongNghe có độ tin cậy là : 100%

CongNghe  NguVan, Toan,LichSu, có độ tin cậy là : 100%

NguVan, Toan LichSu, CongNghe có độ tin cậy là : 100%

NguVan, LichSu  Toan, CongNghe có độ tin cậy là : 100%

Toan, LichSu  NguVan, CongNghe có độ tin cậy là : 100%

Toan, CongNghe  NguVan, LichSu có độ tin cậy là : 100%

LichSu, CongNghe  NguVan, Toan có độ tin cậy là : 100%

NguVan, Toan, LichSu  CongNghe có độ tin cậy là : 100%

NguVan, Toan, CongNghe  LichSu có độ tin cậy là : 100%

NguVan, LichSu, CongNghe  Toan có độ tin cậy là : 100%

Toan, LichSu, CongNghe  NguVan có độ tin cậy là : 100%

*, Với các tập phổ biến có trọng số( NguVan, Toan, DiaLy, CongNghe)

đƣợc các tập luật sau:

NguVan  Toan, DiaLy, CongNghe có độ tin cậy là : 100%

Toan  NguVan, DiaLy, CongNghe có độ tin cậy là : 100%

DiaLy  NguVan, Toan, CongNghe có độ tin cậy là : 100%

CongNghe  NguVan, Toan, DiaLy, có độ tin cậy là : 100%

NguVan, Toan  DiaLy, CongNghe có độ tin cậy là : 100%

NguVan, DiaLy  Toan, CongNghe có độ tin cậy là : 100%

Toan, DiaLy  NguVan, CongNghe có độ tin cậy là : 100%

Toan, CongNghe  NguVan, DiaLy có độ tin cậy là : 100%

DiaLy, CongNghe  NguVan, Toan có độ tin cậy là : 100%

NguVan, Toan, DiaLy  CongNghe có độ tin cậy là : 100%

NguVan, Toan, CongNghe  DiaLy có độ tin cậy là : 100%

NguVan, DiaLy, CongNghe  Toan có độ tin cậy là : 100%

Toan, DiaLy, CongNghe  NguVan có độ tin cậy là : 100%

*, Với các tập phổ biến có trọng số( NguVan, Toan, DiaLy, TinHoc)

đƣợc các tập luật sau:

NguVan  Toan, DiaLy, TinHoc có độ tin cậy là : 100%

Toan  NguVan, DiaLy, TinHoc có độ tin cậy là : 100%

DiaLy  NguVan, Toan, TinHoc có độ tin cậy là : 100%

TinHoc  NguVan, Toan, DiaLy, có độ tin cậy là : 100%

NguVan, Toan  DiaLy, TinHoc có độ tin cậy là : 100%

NguVan, DiaLy  Toan, TinHoc có độ tin cậy là : 100%

Toan, DiaLy  NguVan, TinHoc có độ tin cậy là : 100%

Toan, TinHoc  NguVan, DiaLy có độ tin cậy là : 100%

DiaLy, TinHoc  NguVan, Toan có độ tin cậy là : 100%

NguVan, Toan, DiaLy  TinHoc có độ tin cậy là : 100%

NguVan, Toan, TinHoc  DiaLy có độ tin cậy là : 100%

NguVan, DiaLy, TinHoc  Toan có độ tin cậy là : 100%

Toan, DiaLy, TinHoc  NguVan có độ tin cậy là : 100%

*, Với các tập phổ biến có trọng số( NguVan, Toan, TiengAnh, TinHoc)

đƣợc các tập luật sau:

NguVan  Toan, TiengAnh, TinHoc có độ tin cậy là : 100%

Toan  NguVan, TiengAnh, TinHoc có độ tin cậy là : 100%

TiengAnh  NguVan, Toan, TinHoc có độ tin cậy là : 100%

TinHoc  NguVan, Toan, TiengAnh, có độ tin cậy là : 100%

NguVan, Toan  TiengAnh, TinHoc có độ tin cậy là : 100%

NguVan, TiengAnh  Toan, TinHoc có độ tin cậy là : 100%

Toan, TiengAnh  NguVan, TinHoc có độ tin cậy là : 100%

Toan, TinHoc  NguVan, TiengAnh có độ tin cậy là : 100%

TiengAnh, TinHoc  NguVan, Toan có độ tin cậy là : 100%

NguVan, Toan, TiengAnh  TinHoc có độ tin cậy là : 100%

NguVan, Toan, TinHoc  TiengAnh có độ tin cậy là : 100%

NguVan, TiengAnh, TinHoc  Toan có độ tin cậy là : 100%

Toan, TiengAnh, TinHoc  NguVan có độ tin cậy là : 100%

….

Một số ý nghĩa rút ra đƣợc từ các luật trên:

- Đa số các em học sinh có kết quả học tập tốt thì có rất nhiều lựa chọn

cho mình học theo khối nào mình yêu thích

- Đây là tín hiệu đáng mừng cho thành tích của nhà trƣờng và giáo viên

vì đây là nguồn học sinh giỏi cần bồi dƣỡng để thi học sinh giỏi cấp thành phố

và quốc gia

- Bên cạnh đó nhà trƣờng cũng quan tâm tới các lớp có số lƣợng học

sịnh còn yếu, phụ đạo cho các em để các em có thành tích tôt hơn. Để các em

có thể thi vào các trƣờng Đại học, Cao đẳng hoặc các trƣờng dạy nghề.

- Nhà trƣờng cũng sẽ quan tâm tới các giáo viên bộ môn còn yếu trong

trình độ chuyên môn và năng lực. Các giáo viên bộ môn còn yếu về trình độ và

năng lực thì tự mình nâng cao cho phù hợp với điều kiện hiện tại của trƣờng.

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN

Kết Luận

Luận văn đề cập đến các nội dung về kho dữ liệu và ứng dụng của lƣu trữ

và khai phá tri thức trong kho dữ liệu nhằm hỗ trợ ra quyết định.

Về mặt lý thuyết, khai phá tri thức bao gồm các bƣớc: Hình thành, xác

định và định nghĩa bài toán; thu thập và tiền xử lý dữ liệu; khai phá dữ liệu, rút

ra các tri thức; sử dụng các tri thức phát hiện đƣợc. Phƣơng pháp khai phá dữ

liệu có thể là: phân lớp, hồi quy, cây quyết định, suy diễn, quy nạp, K- láng

giềng gần, … các phƣơng pháp trên có thể áp dụng trong dữ liệu thông thƣờng

và trên tập mờ.

Về thuật toán khai phá tri thức, luận văn trình bày một số thuật toán và

minh hoạ một số thuật toán kinh điển về phát hiện tập chỉ báo phổ biến và

khai phá luật kết hợp, nhƣ: Apriori, AprioriTid, Fp_Growth , NSFI

ALGORITHM ,FIT, PPC-tree.

Về mặt cài đặt thử nghiệm, luận văn giới thiệu kỹ thuật khai phá dữ liệu theo

thuật toán FSM áp dụng vào bài toán xây dựng hỗ trợ học sinh phổ thông Tân

Lập. Bƣớc đầu ít nhiều đã giúp cho Ban giám hiệu nhà trƣờng, các nhà quản lý

giáo dục có đƣợc một cái nhìn nhiều chiều hơn, đa dạng hơn, nhiều góc cạnh

hơn về điểm số của học sinh từ đó thu đƣợc một số kết quả:

- Lựa chọn học sinh giỏi để bồi dƣỡng.

- Phát hiện học sinh yếu kém để phụ đạo cũng nhƣ đề ra kế hoạch giảng dạy.

- So sánh kết quả học tập giữa các khối lớp hay các lớp.

- Định hƣớng cho học sinh nên thi theo khối học nào, bậc học nào cho phù

hợp với năng lực và khả năng.

Trong quá trình thực hiện luận văn, tôi đã cố gắng tập trung tìm hiểu và

tham khảo các tài liệu liên quan. Tuy nhiên, với thời gian và trình độ có hạn

nên không tránh khỏi những hạn chế và thiếu sót. Tôi rất mong đƣợc sự nhận

xét và góp ý của các thầy cô giáo và bạn bè, đồng nghiệp và những ngƣời cùng

quan tâm để hoàn thiện hơn các kết quả nghiên cứu của mình.

* Hƣớng phát triển

Tiếp tục hoàn thiện và mở rộng chƣơng trình trong luận văn này để có thể

áp dụng vào thực tế không chỉ áp dụng trong phạm vi nhỏ mà áp dụng trên

phạm vi lớn một cách triệt để nhất.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] PGS.TS Ngô Quốc Tạo(2013),“Bài giảng môn Data Mining” – lớp CHK12

- ĐH Thái Nguyên

[2] Đặng Thị Thu Hiền(2013), “Bài giảng cao học môn học Data mining”,

Trƣờng Đại học Giao thông vận tải.

[3] Nguyễn Ngọc Hải (2013), “ Tìm hiểu về luật kết hợp và ứng dụng thử

nghiệm khai phá cơ sở dữ liệu Bảo hiểm y tế nhằm hỗ trợ cho công tác quản

lý, sử dụng quỹ BHYT tại tỉnh Bắc Giang”. Luận văn Thạc sỹ, Đại học công

nghệ thông và truyền thông Thái Nguyên.

mục thường xuyên và tập mục cổ phần cao trong cơ sở dữ liệu”. Luận văn

[4] Bế Quang Huấn (2012),“ Nghiên cứu một số thuật toán khai phá tập

Thạc sỹ, Đại học công nghệ thông và truyền thông Thái Nguyên.

Tiếng Anh

[1] Anuradha Rehal, M.Tech. Scholar, An Effective Algorithmic Appoach for

Associative Classification using Metaheuristics, International Journal of

Computing and Business Research (IJCBR), ISSN (Online) : 2229-6166,

Volume 5 Issue 3 May 2014

[2] A Review, NCI2TM: 2014, Shikha Dubey, Dr. Shivaji D. Mundhe, Association Rule Mining Algorithm: 2014, International Journal on Natural Language Computing (IJNLC) Vol. 3, No.1, February 2014, DOI : 10.5121/ijnlc.2014.3103 21

[3] Bay Vo, Tuong Le, Frans Coenen & Tzung-Pei Hong , Mining frequent itemsets using the N-list and subsume concepts, International Journal of Machine Learning and Cybernetics, ISSN 1868-8071, DOI 10.1007/s13042- 014-0252-2. 2014.

[4] Bay Vo, Tuong Le, A Hybrid Approach for Mining Frequent Itemsets,

IEEE International Conference on Systems, Man, and Cybernetics, 2013.

[5] D. Bhalodiya, K. M. Patel and C. Patel. An Efficient way to Find Frequent Pattern with Dynamic Programming Approach. NIRMA UNIVERSITY INTERNATIONAL CONFERENCE ON ENGINEERING, NUiCONE-2013, 28-30 NOVEMBER, 2013

[6] Jun Luo and Sanguthevar Rajasekaran, FIT: A Fast Algorithm for Discovering Frequent Itemsets in Large Databases.

[7] Jiawei Han, Micheline Kamber and Jian Pei, Data Mining

Concepts and Techniques 2nd Edition,2008.

[8] Jiawei Han, Micheline Kamber and Jian Pei, Data Mining Concepts and Techniques Third Edition.

[9] Jiawei Han (2006), Data mining: concepts and techniques, University of Illinois at Urbana'Champaign.

[10] Mohammed Al-Maolegi, Bassam Arkok, Computer Science, An Improved Apriori Algorithm For Association Rules, Jordan University of Science and Technology, Irbid, Jordan, 2014

[11] Mohammed Zaki and Wagner Meira Jr (2014),Data Mining and Analysis: Fundamental Concepts and Algorithms, Cambridge University Press.

[12] Ramezani, Reza, Mohamad Saraee, and Mohammad Ali Nematbakhsh; MRAR: Mining Multi-Relation Association Rules, Journal of Computing and Security, 1, no. 2 (2014).

[13] Vo, B., Hong, T.P., Le B.: A Lattice – based Approach for Mining Most Generalization Association Rules. Knowledge - Based Systems, 45, 20-30, 2013.

[14] Z. H. Deng and S. L. Lv. Fast mining frequent itemsets using Nodesets. Expert Systems with Applications, 41(10): 4505–4512, 2014.

PHỤ LỤC

CÀI ĐẶT SOURCE CODE

*, Mã nguồn của chƣơng trình.

Các hàm xử lý chính

B1. Tìm giá trị tmv và lmv

// Tính giá trị transaction measure value

private int tmv(string values, DataGridView DB)

{

int t = 0;

foreach (DataGridViewRow row in DB.Rows)

if (!row.IsNewRow)

if (exist(values, row))

for (int i = 0; i < row.Cells.Count; i++)

t += (int)row.Cells[i].Value;

return t;

}

// Tính giá trị local measure value

private int lmv(string values, DataGridView DB)

{

int t = 0;

foreach (DataGridViewRow row in DB.Rows)

if (!row.IsNewRow)

if (exist(values, row))

for (int i = 0; i < values.Length; i++)

t +=

(int)row.Cells[values[i].ToString()].Value;

return t;

}

B2. Kết nối Apriori

// Xây dựng kết nối Apriori

private string Candidate_Join(string L_k_sub_1, int

k_sub_1)

{

string join = "";

//Bước kết nối

string[] xyz = L_k_sub_1.Split(new char[] { ',' });

if (!k_sub_1.Equals(1))

{

for (int i = 0; i < xyz.Length - 1; i++)

for (int j = i + 1; j < xyz.Length; j++)

if (xyz[i].Substring(0, k_sub_1 - 1) ==

xyz[j].Substring(0, k_sub_1 - 1) && xyz[i][k_sub_1 - 1] <

xyz[j][k_sub_1 - 1])

join += xyz[i] + xyz[j][k_sub_1 - 1] +

",";

}

else

{

for (int i = 0; i < xyz.Length - 1; i++)

{

for (int j = i + 1; j < xyz.Length; j++)

{

join += xyz[i] + xyz[j] + ",";

}

//Bước tỉa

xyz = join.Split(new char[] { ',' });

for (int i = xyz.Length - 2; i > 0; i--)

for (int j = i - 1; j >= 0; j--)

if (xyz[i].Equals(xyz[j]))

{

xyz[i] = "";

break;

}

string str = "";

for (int i = 0; i < xyz.Length; i++)

if (!xyz[i].Equals(""))

str += xyz[i] + ",";

return (join.Equals("") ? join : str.Substring(0,

str.Length - 1));

}

B3. Vòng lặp tìm các tập phổ biến từ tập ứng viên

{

k++;

string RC = null;

C = Candidate_Join(C, k);

if (C.Equals(""))

break;

itemsC = C.Split(new char[] { ',' });

for (int i = 0; i < itemsC.Length; i++)

if (tmv(itemsC[i], GridData) >= min_lmv)

{

RC += itemsC[i] + ",";

if (lmv(itemsC[i], GridData) >= min_lmv)

HS += itemsC[i] + ",";

}

if (RC != null) C = RC.Substring(0, RC.Length - 1);

} while (!C.Equals(null));

Mã nguồn AFSMProgram

using System;

using System.Collections.Generic;

using System.Data;

using System.IO;

using System.Windows.Forms;

namespace AFSM

{

public partial class AFSMProgram : Form

{

public AFSMProgram()

{

InitializeComponent();

GridData.AutoSizeColumnsMode =

DataGridViewAutoSizeColumnsMode.DisplayedCells;

}

private DataTable viewTable(string fileName)

{

using (StreamReader sr = File.OpenText(fileName))

{

DataTable dataSource = new DataTable();

// Doc dong dau tien

string s = sr.ReadLine();

string[] colName = s.Split(new char[] { ',' });

int length = colName.Length;

// Tạo cấu trúc bảng dữ liệu

for (int i = 0; i < length; i++)

{

dataSource.Columns.Add(colName[i], typeof(double));

}

while ((s = sr.ReadLine()) != null)

{

dataSource.Rows.Add(s.Split(new char[] { ',' }));

}

return dataSource;

}

private void BtnBrowser_Click(object sender, EventArgs e)

{

if (OpenFileDialog.ShowDialog() == DialogResult.OK)

{

try

{

string fileName = OpenFileDialog.FileName;

TxtFileName.Text = fileName;

// Hiển thị thông tin dữ liệu

DataTable dataSource = viewTable(fileName);

GridData.DataSource = null;

GridData.DataSource = dataSource;

for (int i = 0; i < GridData.Columns.Count; i++)

GridData.Columns[i].Name = Convert.ToChar(i + 65).ToString();

//GridData.DataSource = AutoNumberedTable(dataSource);

TxtNumOfItems.Text = dataSource.Columns.Count.ToString();

TxtNumOfTrans.Text = dataSource.Rows.Count.ToString();

GroupThres.Enabled = true;

GroupData.Enabled = true;

}

catch { }

}

private DataTable AutoNumberedTable(DataTable SourceTable)

{

DataTable ResultTable = new DataTable();

DataColumn AutoNumberColumn = new DataColumn();

AutoNumberColumn.ColumnName = "TID";

AutoNumberColumn.DataType = typeof(int);

AutoNumberColumn.AutoIncrement = true;

AutoNumberColumn.AutoIncrementSeed = 1;

AutoNumberColumn.AutoIncrementStep = 1;

ResultTable.Columns.Add(AutoNumberColumn);

ResultTable.Merge(SourceTable);

return ResultTable;

}

// Tính giá trị local measure value

private double lmv(string values, DataGridView DB)

{

double t = 0;

foreach (DataGridViewRow row in DB.Rows)

if (!row.IsNewRow)

if (exist(values, row))

for (int i = 0; i < values.Length; i++)

t += (double)row.Cells[values[i].ToString()].Value;

return t;

}

// Tính giá trị transaction measure value

private double tmv(string values, DataGridView DB)

{

double t = 0;

foreach (DataGridViewRow row in DB.Rows)

if (!row.IsNewRow)

if (exist(values, row))

for (int i = 0; i < row.Cells.Count; i++)

t += (double)row.Cells[i].Value;

return t;

}

private double sum_exist(string values, DataGridView DB)

{

double t = 0;

foreach (DataGridViewRow row in DB.Rows)

if (!row.IsNewRow)

if (exist(values, row))

t++;

return t;

}

private bool exist(string values, DataGridViewRow DGVRow)

{

for (int i = 0; i < values.Length; i++)

{

if ((double)DGVRow.Cells[values[i].ToString()].Value == 0)

return false;

}

return true;

}

// Xây dựng kết nối Apriori

private string Candidate_Join(string L_k_sub_1, int k_sub_1)

{

string join = "";

//Bƣớc kết nối

string[] xyz = L_k_sub_1.Split(new char[] { ',' });

if (!k_sub_1.Equals(1))

{

for (int i = 0; i < xyz.Length - 1; i++)

for (int j = i + 1; j < xyz.Length; j++)

if (xyz[i].Substring(0, k_sub_1 - 1) == xyz[j].Substring(0, k_sub_1 - 1) &&

xyz[i][k_sub_1 - 1] < xyz[j][k_sub_1 - 1])

join += xyz[i] + xyz[j][k_sub_1 - 1] + ",";

}

else

{

for (int i = 0; i < xyz.Length - 1; i++)

{

for (int j = i + 1; j < xyz.Length; j++)

{

join += xyz[i] + xyz[j] + ",";

}

//Bƣớc tỉa

xyz = join.Split(new char[] { ',' });

for (int i = xyz.Length - 2; i > 0; i--)

for (int j = i - 1; j >= 0; j--)

if (xyz[i].Equals(xyz[j]))

{

xyz[i] = "";

break;

}

string str = "";

for (int i = 0; i < xyz.Length; i++)

if (!xyz[i].Equals(""))

str += xyz[i] + ",";

return (join.Equals("") ? join : str.Substring(0, str.Length - 1));

}

private bool validateInput(TextBox txtBox)

{

if (txtBox.Text.Length == 0)

{

errorProvider.SetError(txtBox, "Chƣa nhập giá trị");

return false;

}

else

{

try

{

if (Double.Parse(txtBox.Text) > 100 || Double.Parse(txtBox.Text) < 0)

{

errorProvider.SetError(txtBox, "Nhập giá trị giữa 0 và 100");

return false;

}

else

{

errorProvider.SetError(txtBox, "");

return true;

}

catch

{

errorProvider.SetError(txtBox, "Giá trị không đúng định dạng");

return false;

}

private string getNameItem(string names, DataGridView dgW)

{

string lviItem = "";

for (int j = 0; j < names.Length; j++)

{

int index = names[j] - 65;

lviItem += dgW.Columns[index].HeaderText + ", ";

}

lviItem = lviItem.Substring(0, lviItem.Length - 2);

return lviItem;

}

private class clssRules

{

string strCombination, strRemaining;

double _confidence;

public clssRules(string strCombination, string strRemaining, double Confidence)

{

this.strCombination = strCombination;

this.strRemaining = strRemaining;

this._confidence = Confidence;

}

public string X { get { return strCombination; } }

public string Y { get { return strRemaining; } }

public double Confidence { get { return _confidence; } }

}

private void GenRule(string ruleItem, List lstRule)

{

if (ruleItem.Length > 1)

{

string strcombination;

for (int i = 1; i < ruleItem.Length; i++)

{

strcombination = "";

bool[] checki = new bool[ruleItem.Length];

for (int j = 0; j < checki.Length; j++)

checki[j] = true;

GeneKRule(1, 0, ref checki, i, ruleItem, strcombination, lstRule);

}

private void GeneKRule(int i, int ti, ref bool[] checki, int k, string ruleItem, string

strcombination, List lstRule)

{

for (int j = ti; j < checki.Length; j++)

{

if (checki[j])

{

strcombination += ruleItem[j].ToString();

checki[j] = false;

if (i == k)

{

string remaining = getRemaining(strcombination, ruleItem);

clssRules clsRule = new clssRules(strcombination, remaining,

confidence(strcombination, ruleItem));

lstRule.Add(clsRule);

}

else

GeneKRule(i + 1, j, ref checki, k, ruleItem, strcombination, lstRule);

strcombination = strcombination.Substring(0, strcombination.Length - 1);

checki[j] = true;

}

private string getRemaining(string strCombination, string strAFSMItem)

{

string temp = strAFSMItem;

foreach (char ch in strCombination)

{

temp = temp.Replace(ch.ToString(), "");

}

return temp;

}

private double confidence(string strCombination, string strAFSMItem)

{

return (double)sum_exist(strAFSMItem, GridData) / sum_exist(strCombination,

GridData);

}

public static string HS;

private void TxtExecute_Click(object sender, EventArgs e)

{

if (validateInput(TxtMinShare) && validateInput(TxtMinConf))

{

//Tính tổng giá trị của bảng dữ liệu DB Tdb

try

{

HS = "";

double T = 0;

int k = 0;

foreach (DataGridViewRow row in GridData.Rows)

if (!row.IsNewRow)

foreach (DataGridViewCell cell in row.Cells)

T += (double)cell.Value;

double min_lmv = T * double.Parse(TxtMinShare.Text) / 100;

double min_conf = double.Parse(TxtMinConf.Text) / 100;

string C1 = null, C = null;

foreach (DataGridViewColumn col in GridData.Columns)

C1 += col.Name.ToString() + ",";

C1 = C1.Substring(0, C1.Length - 1);

string[] itemsC = C1.Split(new char[] { ',' });

for (int i = 0; i < itemsC.Length; i++)

if (tmv(itemsC[i], GridData) >= min_lmv)

{

C += itemsC[i] + ",";

if (lmv(itemsC[i], GridData) >= min_lmv)

HS += itemsC[i] + ",";

}

C = C.Substring(0, C.Length - 1);

{

k++;

string RC = null;

C = Candidate_Join(C, k);

if (C.Equals(""))

break;

itemsC = C.Split(new char[] { ',' });

for (int i = 0; i < itemsC.Length; i++)

if (tmv(itemsC[i], GridData) >= min_lmv)

{

RC += itemsC[i] + ",";

if (lmv(itemsC[i], GridData) >= min_lmv)

HS += itemsC[i] + ",";

}

if (RC != null) C = RC.Substring(0, RC.Length - 1);

} while (!C.Equals(null));

//In kết quả ra form Result

if (!HS.Equals(""))

{

Result frmResult = new Result();

string[] itemAFSM = HS.Split(new char[] { ',' });

for (int i = 0; i < itemAFSM.Length; i++)

{

if (itemAFSM[i] != "")

{

ListViewItem lvi = new ListViewItem(getNameItem(itemAFSM[i],

GridData));

lvi.SubItems.Add(lmv(itemAFSM[i], GridData).ToString());

frmResult.lv_Frequent.Items.Add(lvi);

}

//In tập luật

List lstRules = new List();

for (int i = 0; i < itemAFSM.Length; i++)

if (itemAFSM[i].Length > 1)

{

GenRule(itemAFSM[i], lstRules);

}

foreach (clssRules rule in lstRules)

{

if (rule.Confidence >= min_conf)

{

ListViewItem lvi = new ListViewItem(getNameItem(rule.X, GridData)

+ "->" + getNameItem(rule.Y, GridData));

lvi.SubItems.Add(String.Format("{0}%", Math.Round(rule.Confidence

* 100, 2)));

frmResult.lv_Rules.Items.Add(lvi);

}

frmResult.ShowDialog();

}

else

{

MessageBox.Show("Không tìm thấy tập mục thỏa mãn");

}

catch(Exception ex1)

{

String msg = ex1.StackTrace;

MessageBox.Show("Không tìm thấy tập mục thỏa mãn");

}

Mã nguồn Result.Designer

namespace AFSM

{

partial class Result

{

Required designer variable.

private System.ComponentModel.IContainer components = null;

Clean up any resources being used.

true if managed resources should be disposed;

otherwise, false.

protected override void Dispose(bool disposing)

{

if (disposing && (components != null))

{

components.Dispose();

}

base.Dispose(disposing);

}

#region Windows Form Designer generated code

Required method for Designer support - do not modify

the contents of this method with the code editor.

private void InitializeComponent()

{

System.ComponentModel.ComponentResourceManager resources = new

System.ComponentModel.ComponentResourceManager(typeof(Result));

this.gb_FrequentItems = new

System.Windows.Forms.GroupBox();

this.lv_Frequent = new System.Windows.Forms.ListView();

this.colItem = ((System.Windows.Forms.ColumnHeader)(new

System.Windows.Forms.ColumnHeader()));

this.colLmv = ((System.Windows.Forms.ColumnHeader)(new

System.Windows.Forms.ColumnHeader()));

this.gb_StrongRules = new

System.Windows.Forms.GroupBox();

this.lv_Rules = new System.Windows.Forms.ListView();

this.colRule

((System.Windows.Forms.ColumnHeader)(new

System.Windows.Forms.ColumnHeader()));

this.colConfidence =

((System.Windows.Forms.ColumnHeader)(new

System.Windows.Forms.ColumnHeader()));

this.gb_FrequentItems.SuspendLayout();

this.gb_StrongRules.SuspendLayout();

this.SuspendLayout();

gb_FrequentItems

this.gb_FrequentItems.Anchor =

((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorS

tyles.Top | System.Windows.Forms.AnchorStyles.Bottom)

| System.Windows.Forms.AnchorStyles.Left)

| System.Windows.Forms.AnchorStyles.Right)));

this.gb_FrequentItems.Controls.Add(this.lv_Frequent);

this.gb_FrequentItems.Location = new System.Drawing.Point(3, 12);

this.gb_FrequentItems.Name = "gb_FrequentItems";

this.gb_FrequentItems.Size = new System.Drawing.Size(536, 261);

this.gb_FrequentItems.TabIndex = 2;

this.gb_FrequentItems.TabStop = false;

this.gb_FrequentItems.Text = "Các tập phổ biến có trọng số";

lv_Frequent

this.lv_Frequent.Anchor =

((System.Windows.Forms.AnchorStyles)((((System.Windows.Forms.AnchorStyles.

Top | System.Windows.Forms.AnchorStyles.Bottom)

| System.Windows.Forms.AnchorStyles.Left)

| System.Windows.Forms.AnchorStyles.Right)));

this.lv_Frequent.Columns.AddRange(new

System.Windows.Forms.ColumnHeader[] {

this.colItem,

this.colLmv});

this.lv_Frequent.Location = new System.Drawing.Point(3, 16);

this.lv_Frequent.Name = "lv_Frequent";

this.lv_Frequent.Size = new System.Drawing.Size(530, 242);

this.lv_Frequent.TabIndex = 0;

this.lv_Frequent.UseCompatibleStateImageBehavior = false;

this.lv_Frequent.View = System.Windows.Forms.View.Details;

colItem

this.colItem.Text = "Tập các môn học";

this.colItem.Width = 402;

colLmv

this.colLmv.Text = "LMV";

this.colLmv.Width = 0;

gb_StrongRules

this.gb_StrongRules.Anchor =

((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.B

ottom | System.Windows.Forms.AnchorStyles.Left)

| System.Windows.Forms.AnchorStyles.Right)));

this.gb_StrongRules.Controls.Add(this.lv_Rules);

this.gb_StrongRules.Location = new System.Drawing.Point(3, 279);

this.gb_StrongRules.Name = "gb_StrongRules";

this.gb_StrongRules.Size = new System.Drawing.Size(536, 336);

this.gb_StrongRules.TabIndex = 3;

this.gb_StrongRules.TabStop = false;

this.gb_StrongRules.Text = "Các luật kết hợp thỏa mãn ngƣỡng tin cậy";

lv_Rules

this.lv_Rules.Columns.AddRange(new

System.Windows.Forms.ColumnHeader[] {

this.colRule,

this.colConfidence});

this.lv_Rules.Dock = System.Windows.Forms.DockStyle.Fill;

this.lv_Rules.Location = new System.Drawing.Point(3, 16);

this.lv_Rules.Name = "lv_Rules";

this.lv_Rules.Size = new System.Drawing.Size(530, 317);

this.lv_Rules.TabIndex = 1;

this.lv_Rules.UseCompatibleStateImageBehavior = false;

this.lv_Rules.View = System.Windows.Forms.View.Details;

colRule

this.colRule.Text = "Luật";

this.colRule.Width = 408;

colConfidence

this.colConfidence.Text = "Độ tin cậy";

this.colConfidence.Width = 115;

Result

this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);

this.AutoScaleMode =

System.Windows.Forms.AutoScaleMode.Font;

this.ClientSize = new System.Drawing.Size(542, 620);

this.Controls.Add(this.gb_StrongRules);

this.Controls.Add(this.gb_FrequentItems);

this.FormBorderStyle =

System.Windows.Forms.FormBorderStyle.FixedSingle;

this.Icon =

((System.Drawing.Icon)(resources.GetObject("$this.Icon")));

this.MaximizeBox = false;

this.MinimizeBox = false;

this.Name = "Result";

this.SizeGripStyle =

System.Windows.Forms.SizeGripStyle.Show;

this.StartPosition =

System.Windows.Forms.FormStartPosition.CenterScreen;

this.Text = "Kết quả";

this.gb_FrequentItems.ResumeLayout(false);

this.gb_StrongRules.ResumeLayout(false);

this.ResumeLayout(false);

}

#endregion

private System.Windows.Forms.GroupBox gb_FrequentItems;

public System.Windows.Forms.ListView lv_Frequent;

private System.Windows.Forms.ColumnHeader colItem;

private System.Windows.Forms.ColumnHeader colLmv;

private System.Windows.Forms.GroupBox gb_StrongRules;

private System.Windows.Forms.ColumnHeader colRule;

private System.Windows.Forms.ColumnHeader colConfidence;

public System.Windows.Forms.ListView lv_Rules;

}

Luận văn Thạc sĩ Khoa học máy tính: 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

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LỜI CẢM ƠN TRẦN NAM NGỌC Đầ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

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

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

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

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

HỢP

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

PHỤ LỤC

CÀI ĐẶT SOURCE CODE

Các hàm xử lý chính

Mã nguồn AFSMProgram

Mã nguồn Result.Designer

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok