Luận văn Thạc sĩ Khoa học máy tính: Phát hiện mối quan hệ trong cơ sở dữ liệu và ứng dụng trong y học

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

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN

THÔNG

VY ĐẠI NGHĨA

PHÁT HIỆN MỐI QUAN HỆ TRONG

CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG TRONG Y

HỌC

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

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

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN

THÔNG

VY ĐẠI NGHĨA

PHÁT HIỆN MỐI QUAN HỆ TRONG

CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG TRONG Y

HỌC

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

Mã số: 60 48 01

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

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Đỗ Trung Tuấ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

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Lời cả m ơn

Trước tiên, tôi xin được gửi lời cảm ơn đến tất cả quý thầy cô đã giảng dạy

trong chương trình Cao học do Trường Đại học Công nghệ thông tin và truyền thông

tổ chức, những người đã truyền đạt cho tôi những kiến thức hữu ích về khoa học máy

tính làm cơ sở cho tôi thực hiện tốt luận văn này.

Tôi xin chân thành cảm ơn PGS. TS. Đỗ Trung Tuấn đã tận tình hướng dẫn cho

tôi trong thời gian thực hiện luận văn. Mặc dù trong quá trình thực hiện luận văn có

giai đoạn không được thuận lợi nhưng những gì Thầy đã hướng dẫn, chỉ bảo đã cho tôi

nhiều kinh nghiệm trong thời gian thực hiện đề tài.

Tôi cũng xin gửi lời cảm ơn đến tất cả các Thầy Cô đang làm việc tại Phòng

khám đa khoa trường Cao đẳng Y tế Phú Thọ đã tận tình giúp đỡ trong việc thu thập

thông tin, lấy số liệu về bệnh và thuốc làm cơ sở dữ liệu cho luận văn.

Sau cùng tôi xin gửi lời biết ơn sâu sắc đến các anh chị trong lớp và gia đình đã

luôn tạo điều kiện tốt nhất cho tôi trong suốt quá trình học cũng như thực hiện luận

văn.

Do thời gian có hạn và kinh nghiệm nghiên cứu khoa học chưa nhiều nên luận

văn còn nhiều thiếu sót, rất mong nhận được ý kiến góp ý của Thầy/Cô và các anh chị

học viên.

Phú Thọ, tháng 7 năm 2015

Học viên

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Vy Đại Nghĩa

iii

Lời cam đoan

Tôi cam đoan những kết quả trong luâ ̣n văn là củ a viê ̣c tìm hiểu, có trích dẫn và tham chiếu đến các nguồn tư liê ̣u tin cậy. Nội dung luận văn không sao chép từ các kết

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

quả củ a các luâ ̣n văn, luận án khác.

MỤC LỤC

Lời cả m ơn .................................................................................................................. i

Lời cam đoan ........................................................................................................... iii

MỤC LỤC ................................................................................................................. iv

DANH MỤC CÁC TỪ VIẾT TẮT ........................................................................... vi

DANH MỤC CÁC BẢNG, HÌNH VẼ ..................................................................... vii

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

CHƯƠNG 1 ................................................................................................................ 6

TỔNG QUAN VỀ PHÁT HIỆN MỐI QUAN HỆ GIỮA CÁC DỮ LIỆU TRONG

CƠ SỞ DỮ LIỆU ....................................................................................................... 6

1. 1. Mục tiêu của việc phát hiện mối quan hê ̣ giữa các dữ liệu ......................... 6

1. 2. Các bước chính của quá trình khai phá tri thức .......................................... 6

1. 3. Các dạng dữ liệu có thể khai phá ............................................................... 7

1. 4. Các hướng tiếp cận chính trong khai phá dữ liệu ....................................... 8

1. 5. Phân loại và ứng dụng các hệ thống khai phá dữ liệu ............................... 11

1. 5. 1. Phân loại các hệ thống khai phá dữ liệu ....................................... 11

1. 5. 2. Ứng dụng của khai phá dữ liệu .................................................... 12

1. 6. Kết luận chương ...................................................................................... 12

CHƯƠNG 2 .............................................................................................................. 13

MỘT SỐ MỐI QUAN HỆ DỮ LIỆU ĐƯỢC PHÁT HIỆN THÔNG QUA NGÔN

NGỮ TRUY VẤN .................................................................................................... 13

2. 1. Luật kết hợp ............................................................................................ 13

2. 1. 1. Các khái niệm cơ bản ................................................................... 13

2. 1. 2. Bài toán khai phá luật kết hợp ...................................................... 16

2. 2. Khai thác tập phổ biến dựa trên ngôn ngữ truy vấn .................................. 17

2. 2. 1. Ngôn ngữ truy vấn ....................................................................... 17

Số hóa bởi Trung tâm Học liệu – ĐHTN

2. 2. 2. Tìm tập phổ biến bằng K-way join ............................................... 20 http://www.lrc.tnu.edu.vn

2. 2. 3. Kết quả thử nghiệm 3 phương pháp đếm độ hỗ trợ....................... 27

2. 2. 4. Phân tích các cải tiến của thuật toán k-way join ........................... 32

2. 2. 5. Phát sinh luật kết hợp ................................................................... 38

2. 2. 6. Rút ngọn luật kết hợp ................................................................... 42

2. 3. Kết luận chương ...................................................................................... 49

CHƯƠNG 3 .............................................................................................................. 51

ỨNG DỤNG TRONG TÍNH TOÁN THỬ NGHIỆM ............................................ 51

3. 1. Các bài toán ............................................................................................. 51

3. 1. 1. Bài toán tìm luật kết hợp dạng X Y .......................................... 51

3. 1. 2. Bài toán tìm độ hỗ trợ và độ tin cậy của luật ................................ 52

3. 1. 3. Bài toán đánh giá độ tin cậy của luật theo ngưỡng ....................... 53

3. 1. 5. Giải pháp giúp thực hiện các bài toán .......................................... 54

3. 2. Chương trình thử nghiệm ........................................................................ 56

3. 2. 1. Cơ sở dữ liệu của bài toán ............................................................ 57

3. 2. 2. Kết quả khai phá dữ liệu khi thực hiện các bài toán ..................... 58

3. 3. Kết luận chương ...................................................................................... 65

KẾT LUẬN .............................................................................................................. 67

PHỤ LỤC ................................................................................................................. 68

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

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

DANH MỤC CÁC TỪ VIẾT TẮT

Active X Data Object ADO

Chuẩn quốc gia Hoa Kì ANSI

Khách/ chủ Client/ server

Độ tin cậy confidence

Cơ sở dữ liệu CSDL

Tên hệ quản trị cơ sở dữ liệu của IBM DB2

Hệ quản trị cơ sở dữ liệu DBMS

Hệ quản trị cơ sở dữ liệu HQTCSDL

Tổ chức tiêu chuẩn hóa quốc tế ISO

multidimensional OLAP MOLAP

Online Analysis Processing OLAP

Tên công ty ORACLE, tên hệ quản trị ORACLE

cơ sở dữ liệu

Relational OLAP ROLAP

Ngôn ngữ truy vấn SQL

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Độ hỗ trợ, trợ giúp support

vii

DANH MỤC CÁC BẢNG, HÌNH VẼ

Hình. Thí dụ về xử lí dữ liệu y tế tại trường Cao đẳng Y tế Phú Thọ ............................ 2

Hình 1. 1: Các bước trong quá trình khai phá tri thức ................................................... 6

Hình 1. 2: Các kiến trúc khai phá tích hợp với cơ sở dữ liệu ........................................ 9

Hình 1. 3: Kiến trúc gắn kết lỏng ................................................................................. 9

Hình 1. 4: Kiến trúc thủ tục nội và hàm do người dùng định nghĩa ............................ 10

Hình 1. 5: Kiến trúc dựa trên truy vấn SQL ............................................................... 10

Hình 2. 1: Minh họa luật kết hợp ............................................................................... 16

Bảng 2. 1: Cấu trúc bảng ban đầu .............................................................................. 20

Bảng 2. 2: Cấu trúc bảng dùng để khai khác .............................................................. 21

Hình 2. 2: Tiến trình phát sinh tập ứng viên Ck .......................................................... 23

Hình 2. 2: Đếm độ hỗ trợ bằng cách tiếp cận K-way Join ........................................... 24

Hình 2. 3: Biểu đồ hình cây cho Sub Query Qi ........................................................... 26

Hình 2. 4: Đồ thị thời gian thực thi của 3 thuật toán khi minsup=10% và D=100000 . 28

Hình 2. 5: Đồ thị thời gian thực thi 3 thuật toán khi minsup=10% và D=50000 ......... 29

Hình 2. 7: Đồ thị thời gian thực thi của 3 thuật toán khi minsup=10% và D=10000 ... 29

Hình 2. 6: Đồ thị tổng hợp thời gian thực thi của 3 thuật toán khi minsup lớn ............ 29

Hình 2. 7: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=100000 ......... 30

Hình 2. 8: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=50000 ........... 30

Hình 2. 9: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=10000 ........... 30

Hình 2. 10: Đồ thị tổng hợp thời gian thực thi 3 thuật toán khi minsup trung bình ..... 31

Hình 2. 11: Đồ thị thời gian thực thi 3 thuật toán khi minsup = 1% và D = 100000.... 31

Hình 2. 12: Đồ thị thời gian thực thi 3 thuật toán khi minsup = 1% và D= 50000 ...... 32

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 2. 13: Đồ thị thời gian thực thi của 3 thuật toán khi minsup =1% và D=10000 .. 32

viii

Hình 2. 154: Đồ thị tổng hợp thời gian thực thi của 3 thuật toán khi minsup nhỏ ....... 32

Bảng 2. 3: Cơ sở dữ liệu ban đầu D ........................................................................... 44

Bảng 2. 4: Cơ sở dữ liệu sau khi chuyển đổi .............................................................. 44

Bảng 2. 5: Kết quả F1 ................................................................................................. 45

Bảng 2. 6: Kết quả F2 ................................................................................................. 46

Bảng 2. 7: Kết quả C3 ................................................................................................ 46

Bảng 2. 8: Kết quả Comb3 ......................................................................................... 47

Bảng 2. 9: Kết quả F3 ................................................................................................. 47

Bảng 2. 10: Kết quả C4 .............................................................................................. 48

Bảng 2. 11: Kết quả Comb4........................................................................................ 49

Bảng 2. 12: Kết quả F4 ............................................................................................... 49

Bảng 2. 13. Kết quả ................................................................................................... 49

Bảng 3. 1. Cấu trúc bảng dữ liệu ban đầu ................................................................... 55

Bảng 3. 2. Cấu trúc bảng dùng để khai phá dữ liệu .................................................... 56

Hình 3. 1. Mẫu đơn thuốc của Phòng khám đa khoa Trường cao đẳng Y Phú Thọ ..... 57

Hình 3. 2. Minh họa cấu trúc dữ liệu ban đầu ............................................................. 58

Hình 3. 3. Cấu trúc dữ liệu dùng để khai phá ............................................................. 58

Hình 3. 4. Tính độ hỗ trợ và độ tin cậy của luật {Cefalecin} => {Paracetamol} ......... 61

Hình 3. 5. Tính độ hỗ trợ và độ tin cậy của một luật {Decolgen}=>{Vitamin C} ....... 61

Hình 3.6. Đánh giá độ tin cậy của luật {Decolgen}=>{Vitamin B1} .......................... 65

Hình 3.7. Đánh giá độ tin cậy của luật {Cefalecin}=>{Vitamin C} ............................ 65

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình PL1: Minh họa dữ liệu đầu vào ......................................................................... 68

MỞ ĐẦU

1. Lý do chọn đề tài

Theo [1] người ta thấy với sự phát triển rất mạnh mẽ về công nghệ lưu trữ,

và khả năng đáp ứng của máy tính đã cho phép ta lưu trữ và xử lý khối lượng dữ

liệu khổng lồ. Hầu hết các tổ chức, cơ quan đang lưu trữ dữ liệu theo thời gian. Kết

quả là, sau một thời gian dài, lượng dữ liệu ngày càng nhiều. Tuy nhiên, những nhà

quản lý lại chưa chú tâm lắm về giá trị tiềm ẩn bên trong khối dữ liệu này. Những

tri thức có ích ẩn bên trong đó không dễ dàng để lấy hay rút trích ra. Ngày này, tính

cạnh trạnh trên thị trường rất cao, đòi hỏi người ra quyết định cần phải đưa ra quyết

định, chính sách một cách thận trọng, chính xác và hiệu quả. Những thông tin để

giúp cho họ đạt hiệu quả hơn trong việc ra quyết định có thể được phân tích, rút

trích từ những dữ liệu lưu trữ hiện tại (dữ liệu thô).

Khai phá dữ liệu sẽ giúp ta giải quyết được vấn đề trên. Công việc khai phá

sẽ phân tích, rút trích một cách tự động thông tin trong khối dữ liệu lớn nhằm tóm

tắt dữ liệu theo cách mới để tiện cho người dùng khai phá, tìm ra các mẫu mới,

những mối liên hệ và những dự đoán, xu hướng thông tin trong tương lai.

Về cơ bản, khai phá dữ liệu là về xử lý dữ liệu và nhận biết các mẫu và các

xu hướng trong thông tin đó để bạn có thể quyết định hoặc đánh giá. Các nguyên tắc

khai phá dữ liệu đã được dùng nhiều năm rồi, nhưng với sự ra đời của big data (dữ

liệu lớn), nó lại càng phổ biến hơn.

Những nhu cầu hướng kinh doanh này đã thay đổi cách lấy ra và thống kê dữ

liệu đơn giản sang việc khai phá dữ liệu phức tạp hơn. Vấn đề kinh doanh hướng tới

việc xem xét dữ liệu để giúp xây dựng một mô hình để mô tả các thông tin mà cuối

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

cuộc sẽ dẫn đến việc tạo ra báo cáo kết quả.

Hình. Thí dụ về xử lí dữ liệu y tế tại trường Cao đẳng Y tế Phú Thọ

Quá trình phân tích dữ liệu, khám phá dữ liệu và xây dựng mô hình dữ liệu

thường lặp lại khi bạn tập trung vào và nhận ra các thông tin khác nhau để bạn có

thể trích ra. Bạn cũng phải hiểu cách thiết lập quan hệ, ánh xạ, kết hợp và phân cụm

thông tin đó với dữ liệu khác để tạo ra kết quả. Quá trình nhận ra dữ liệu nguồn và

các định dạng nguồn, rồi ánh xạ thông tin đó tới kết quả đã cho của chúng tôi có thể

thay đổi sau khi bạn phát hiện ra các yếu tố và các khía cạnh khác nhau của dữ liệu.

Khai phá dữ liệu không phải là tất cả về các công cụ hay phần mềm cơ sở dữ

liệu mà bạn đang sử dụng. Bạn có thể thực hiện khai phá dữ liệu bằng các hệ thống

cơ sở dữ liệu bình thường và các công cụ đơn giản, bao gồm việc tạo và viết phần

mềm riêng của bạn hoặc sử dụng các gói phần mềm bán ngoài cửa hàng. Khai phá

dữ liệu phức tạp được hưởng lợi từ kinh nghiệm trong quá khứ và các thuật toán đã

định nghĩa với phần mềm và các gói phần mềm hiện có, với các công cụ nhất định

để thu được một mối quan hệ hoặc uy tín lớn hơn bằng các kỹ thuật khác nhau.

Liên quan đến xử lí dữ liệu trong các bài toán với dữ liệu lớn, trên các hệ

quản trị cơ sở dữ liệu như Oracle, DB2, ngườ i ta đã sử du ̣ng tiếp cận nối K-way join

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

[10] để tăng tốc độ xử lí dữ liệu, và để thuận tiện cho việc phát hiện các mối quan

hê ̣ giữa các dữ liệu, chẳng hạn như luật kết hợp. Do đó, tôi đã chọn đề tài về xử lí

dữ liệu y tế, trong cơ sở dữ liệu về y tế tại trường Cao đẳng Y tế Phú Thọ áp dụng kĩ thuâ ̣t của tiếp cận K-way join để phát hiện các mối quan hê ̣.

Trong luận văn này, tôi sử dụng ngôn ngữ truy vấn SQL và chọn cách tiếp

cận K-way join làm trọng tâm để đưa ra được các tri thức về thuốc theo nhiều bệnh

lý khác nhau nhằm hỗ trợ cho y, bác sỹ và người quản lý trong công việc khám

chữa bệnh, kinh doanh dược. . . . Dựa trên bài toán đề ra, tôi đã tính toán một bài

toán thực tế lấy dữ liệu từ các đơn thuốc của phòng khám trường Cao đẳng Y tế Phú

Thọ, đơn thuốc mẫu trong các tài liệu giáo trình của nhà trường theo các bệnh khác

nhau. . .

2. Tính thực tiễn của đề tài

Y học là môn khoa học không ngừng phát triển. Tiếp cận và cập nhật hóa

thông tin y học từ những cơ sở dữ liệu, để nâng cao chất lượng chăm sóc sức khỏe

cho nhân dân là điều không thể thiếu trong thực hành lâm sàng. Với sự phát triển

mạnh mẽ của ngành Công nghệ thông tin, một trong những ngành mũi nhọn của

nhiều quốc gia trên thới giới. Sự phát triển vượt bậc đó là kết quả tất yếu của việc

ứng dụng của nó trong nhiều lĩnh vực khác nhau trong cuộc sống như: giáo dục, y

tế, kinh tế, khoa học, xây dựng nó đã trở thành một phần không thể thiếu được trong

cuộc sống hàng ngày của con người. Trong kỷ nguyên bùng nổ thông tin, việc áp

dụng các phương pháp tìm kiếm thông tin từ những nguồn dữ liệu khác nhau là nhu

cầu thiết thực cho toàn xã hội. Trong các phương pháp tìm kiếm thông tin đó, khai

phá dữ liệu để tìm ra tri thức, phục vụ đời sống xã hội là một phương pháp mới,

đang được các nhà nghiên cứu khoa học quan tâm. Tuy nhiên, khai phá dữ liệu

trong lĩnh vực y học ở nước ta quả thật còn rất ít, gặp nhiều khó khăn, do hiện nay

nhiều bệnh viện ở nước ta chưa có bệnh án điện tử. Việc khai phá trong lĩnh vực

này thực sự mang lại nhiều ý nghĩa cho y học để hỗ trợ cho các bác sĩ kê đơn, chẩn

đoán bệnh sớm và điều trị bệnh có hiệu quả, giảm bớt tử vong cũng như chi phí điều

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

trị, đây là một nhu cầu thiết thực trong các bệnh viện. Xuất phát từ những thực tế

trên, tôi đã chọn đề tài “Phát hiện mối quan hệ trong cơ sở dữ liệu và ứng dụng

trong y học” để nghiên cứu cho luận văn thạc sĩ của mình.

3. Mục tiêu nghiên cứu

Mục tiêu và nội dụng của luận văn này là tìm hiểu các phương pháp khai

thác dữ liệu dựa trên ngôn ngữ truy vấn SQL và chọn tiếp cận K-way join làm trọng

tâm. Dựa trên cách tiếp cận này chúng ta sẽ phân tích và đánh giá các cải tiến cho

K-way join, đề xuất phương pháp phát sinh và rút gọn luật kết hợp dựa trên tập luật

mẫu.

4. Đối tượng và phạm vi nghiên cứu

 Tìm hiểu các khái niệm cơ bản về luật kết hợp, các cách tiếp cận khai phá

dữ liệu, đặc biệt là cách tiếp cận K-way join

 Đề xuất phương pháp phát sinh và rút gọn luật kết hợp trên tập luật mẫu

 Tính toán thử nghiệm để đưa ra các tri thức về thuốc cho trường Cao

đẳng Y tế Phú Thọ, so sánh và đánh giá hiệu năng, độ tối ưu của cách tiếp

cận K-way join với các cách tiếp cận khác.

5. Phương pháp nghiên cứu

 Tìm hiểu các tài liệu về các vấn đề liên quan.

 Tham gia thảo luận và trình bày xemina.

 Tính toán thử nghiệm.

6. Bố cục luận văn

Luận văn bao gồm: mục lục, phần mở đầu, phụ lục.

 Chương I: Tổng quan về phát hiện mối quan hệ giữa các dữ liệu trong cơ

sở dữ liệu.

 Chương II: Một số mối quan hệ dữ liệu được phát hiện thông qua ngôn

ngữ truy vấn

 Chương III: Ứng dụng trong tính toán thử nghiệm.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Kết luận và hướng phát triển.

CHƯƠNG 1

TỔNG QUAN VỀ PHÁT HIỆN MỐI QUAN HỆ GIỮA CÁC DỮ LIỆU

TRONG CƠ SỞ DỮ LIỆU

1. 1. Mục tiêu của việc phát hiện mối quan hê ̣ giữa các dữ liệu

Mục tiêu của việc khai khác dữ liệu có các nhiệm vụ chính như sau [2]:

 Khám phá dữ liệu, khám phá mẫu, và dự đoán mẫu nhằm khám phá tri

thức trong kho dữ liệu;

 Rút trích các thông tin có giá trị tiềm ẩn trong kho dữ liệu;

 Phân tích tự động trong kho dữ liệu;

 Biểu diễn dữ liệu để thân thiện với người dùng hơn;

 Dự báo các thông tin mới dựa trên dữ liệu hiện tại để từ đó hỗ trợ, và ra

quyết định.

1. 2. Các bước chính của quá trình phát hiện tri thức

Quá trình phát hiện tri thức được chia thành các bước như sau [1, 2]:

Hình 1. 1: Các bước trong quá trình khai phá tri thức

 Trích chọn dữ liệu (data selection): Là bước trích chọn những tập dữ liệu

cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses).

 Tiền xử lý dữ liệu (data preprocessing): Là bước làm sạch dữ liệu (xử lý

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, . . . ), rút

gọn dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy

mẫu, . . . ), rời rạc hoá dữ liệu (dựa vào histograms, entropy, phân

khoảng, . . . ). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn,

và được rời rạc hoá.

 Biến đổi dữ liệu (data transformation): Là bước chuẩn hoá và làm mịn dữ

liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật

khai thác ở bước sau.

 Khai phá dữ liệu (data mining): Đây là bước quan trọng và tốn nhiều thời

gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá

(phần lớn là các kỹ thuật của học máy) để khai phá, trích chọn được các

mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu.

 Đánh giá và biểu diễn tri thức (knowledge representation & evaluation):

Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri

thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai phá ở bước trên

biểu diễn theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu,

luật, . . . Đồng thời bước này cũng đánh giá những tri thức khám phá

được theo những tiêu chí nhất định.

Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều

chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận được cũng có thể được

lưu và sử dụng lại.

1. 3. Các dạng dữ liệu có thể khai phá

Khai phá dữ liệu có khả năng chấp nhận một số kiểu dữ liệu khác nhau điển

hình như sau [3, 4]:

 Cơ sở dữ liệu quan hệ (relational databases): Là các dữ liệu tác nghiệp

được tổ chức theo mô hình dữ liệu quan hệ rất phổ biến trong hệ thống

quản lý và quán lý bán hàng nói riêng, do hầu hết các hệ quản trị cơ sở dữ

liệu đều hỗ trợ dạng cơ sở dữ liệu quan hệ như Oracle, MS SQL Server,

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

IBM DB2, MS Access, . . .

 Cơ sở dữ liệu đa chiều (multidimention structures, data warehouses, data

mart): Là các kho dữ liệu được tập hợp và chọn lọc từ nhiều nguồn dữ liệu

khác nhau. Dạng dữ liệu này chủ yếu phục vụ cho quá trình phân tích cũng

như khai phá tri thức và hỗ trợ quá trình ra quyết định.

 Cơ sở dữ liệu giao tác (transactional databases): Đây cũng là dạng dữ

liệu tác nghiệp có các bản ghi thường là các giao tác. Dạng dữ liệu này

cũng phổ biến hiện nay trong đó có ngành thương mại.

 Cơ sở dữ liệu quan hệ – hướng đối tượng (object relational databases):

Là dạng dữ liệu lai giữa hai mô hình quan hệ và hướng đối tượng.

 Dữ liệu không gian và thời gian (spatial, temporal, and time-series data):

Là dạng dữ liệu có tích hợp thuộc tính về không gian như dữ liệu bản đồ

mạng cáp điện thoại hoặc thời gian như dữ liệu cước điện thoại, phát hành

báo chí.

 Cơ sở dữ liệu đa phương tiện (Multimedia database): Là dạng dữ liệu âm

thanh (audio), hình ảnh (video), văn bản và WWW, . . . Dạng dữ liệu này

đang rất phổ biến trên Internet và lưu tại các web server của các đơn vị

trực thuộc doanh nghiệp hoặc tổ chức.

1. 4. Các hướng tiếp cận chính trong khai phá dữ liệu

Một số hướng tiếp cận chính của khai phá dữ liệu được phân chia theo chức

năng hay lớp các bài toán khác nhau [2, 4]:

 Phân lớp và dự đoán (classification & prediction): Xếp đối tượng vào

một trong các lớp đã biết trước. Ví dụ: phân lớp loại cước hoặc loại dịch

vụ dựa trên số máy bị gọi của cuộc gọi, phân lớp khu vực dựa trên số máy

chủ gọi, phân lớp giờ cao điểm, thấp điểm dựa trên giờ bắt đầu đàm thoại.

. . . Phân lớp là một lĩnh vực rất quan trọng trong khai phá dữ liệu. Phân

lớp còn được gọi là học có giám sát (supervised learning), hướng tiếp cận

này thường sử dụng một số kỹ thuật của học máy như cây quyết định

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

(decision tree), mạng nơ ron nhân tạo (neural network). . .

Trong việc khai phá dữ liệu, một số kiến trúc đã được đề xuất cho việc tích

hợp tiến trình khai phá với hệ quản trị cơ sở dữ liệu (HQTCSDL). Những kiến trúc

này được biểu diễn như sau:

Hình 1. 2: Các kiến trúc khai thác tích hợp với cơ sở dữ liệu

 Sự gắn kết lỏng hay khai phá dựa trên việc lưu trữ (Loose coupling or

Cache based mining): Đây là kiến trúc dạng Client/Server. Phần khai phá

được xem là ứng dụng phía server. Theo kiến trúc này, đầu tiên dữ liệu

được đọc từ database bằng cursor, sau đó nó sẽ đưa vào nhân khai phá

(mining kernel). Khai phá xong sẽ đưa kết quả vào cơ sở dữ liệu. Điều này

dẫn đến hiệu năng chậm. Kiến trúc được mô tả như hình vẽ bên dưới:

Hình 1. 3: Kiến trúc gắn kết lỏng

 Thủ tục nội và hàm do người dùng định nghĩa (Stored procedure and

user defined functions): Theo kiến trúc này, công việc khai phá được xem

như là một ứng dụng trên máy chủ cơ sở dữ liệu. Các xử lý được thực thi

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

trên cùng không gian địa chỉ là HQTCSDL. Thuật toán khai phá được viết

dưới dạng thủ tục nội (stored procedure) nên việc lập trình khá uyển

chuyển, và có thể tái sử dụng.

Hình 1. 4: Kiến trúc thủ tục nội và hàm do người dùng định nghĩa

 Cách tiếp cận dựa trên SQL (SQL based approach): Theo kiến trúc này,

sử dụng các câu truy vấn SQL để khai phá. Bộ xử lý tối ưu của HQTCSDL

(query optimizer) được dùng để tối ưu các truy vấn phức tạp, những truy

vấn xử lý với thời gian dài dựa trên ngữ nghĩa. Khai phá được tính xử lý

song song những câu truy vấn SQL.

Hình 1. 5: Kiến trúc dựa trên truy vấn SQL

 Cách tiếp cận tích hợp (Intergrated approach): Đây là kiến trúc chặt chẽ

nhất, không có giới hạn giữa việc truy vấn, OLAP, hay khai phá. Các toán

tử khai phá hay SQL được mở rộng cho việc khai phá được tối ưu dựa trên

hệ thống bên trong mà không có sự tác động của người dùng.

 Khai phá mẫu tuần tự (sequential/temporal patterns): Tương tự như khai

phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô

tả mẫu tuần tự có dạng tiêu biểu X  Y phản ánh sự xuất hiện của biến cố

X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính

dự báo.

 Phân cụm (clustering/segmentation): Sắp xếp các đối tượng theo từng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

cụm (số lượng và tên của cụm chưa được biết trước). Các đối tượng được

gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng một cụm

là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các cụm

khác nhau là nhỏ nhất. Phân cụm còn được gọi là học không có giám sát

(unsupervised learning).

1. 5. Phân loại và ứng dụng các hệ thống khai phá dữ liệu

1. 5. 1. Phân loại các hệ thống khai phá dữ liệu

Phân loại khai phá dữ liệu dựa trên các tiêu chí khác nhau [3]:

 Phân loại dựa trên kiểu dữ liệu được khai phá: Cơ sở dữ liệu quan hệ,

kho dữ liệu, cơ sở dữ liệu giao tác, cơ sở dữ liệu hướng đối tượng, cơ sở

dữ liệu không gian, cơ sở dữ liệu đa phương tiện, cơ sở dữ liệu văn bản. . .

 Phân loại dựa trên dạng tri thức được khám phá: Tóm tắt và mô tả, luật

kết hợp, phân lớp, phân cụm, khai phá chuỗi. . .

 Phân loại dựa trên lĩnh vực được áp dụng: Thương mại, viễn thông, tài

chính, y học, web mining, . . .

 Phân loại dựa trên kỹ thuật được áp dụng: Phân tích trực tuyến (Online

Analytial Processing - OLAP), học máy (cây quyết định, mạng nơ ron

nhân tạo, K-Means, giải thuật di truyền, tập thô, tập mờ. . . ). Thông

thường sử dụng tập mờ là thích hợp cho việc tìm ra và hiểu được sự liên

quan của các mô hình dữ liệu chưa đầy đủ, tạp nhiễu, thông tin hỗn tạp và

tác động của con người, và từ đó có thể cung cấp giải pháp xấp xỉ nhanh

hơn. Mạng nơ ron có khả năng tổng quát, không giới hạn, mạnh và học tốt

trong môi trường dữ liệu giàu (data-rich). thuật toán di truyền cung cấp

khả năng tìm các thuật toán để chọn mẫu từ các dữ liệu hỗn tạp dựa trên

một số hàm tiêu chuẩn/ mục tiêu thường dùng. Tập thô thì phù hợp cho

tìm ra các mẫu khác nhau của tình trạng không rõ ràng trong dữ liệu. Một

số yêu cầu khai phá dữ liệu cần phải áp dụng phương pháp tính toán mềm

(Tính toán mềm là sự kết hợp của các phương pháp logic mờ, thuật toán di

truyền, khám phá tri thức, mạng nơ ron, tính toán neuro- fuzzy, tập thô, rút

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

ra luật. )

1. 5. 2. Ứng dụng của 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ư [3, 4]:

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

 Phân tích dữ liệu và hỗ trợ ra quyết định.

 Đ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 triệu

chứng bệnh, chuẩn đoán và phương pháp điều trị (chế độ dinh dưỡng,

thuốc. . ).

 Sản xuất và chế biến: Qui trình, phương pháp chế biến và xử lý sự cố;

 Text mining & 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. 6. Kết luận chương

Chương 1 trình bày chi tiết các khái niệm cơ bản, mục tiêu của việc phát hiện

mối quan hệ dữ liệu, các bước chính khai phá tri thức, các dạng dữ liệu có thể khai

phá, các hướng tiếp cận, phân loại và ứng dụng khai phá dữ liệu. Giúp chúng ta có

cái nhìn tổng quan về các mối quan hệ trong cơ sở dữ liệu, từ đó làm cơ sở để phát

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

triển chương 2, chương 3 của luận văn.

Chương hai và chương ba của luận văn trình bày về thuật toán k-way join

tìm tập phổ biến, các đề xuất tối ưu để thuật toán chạy đạt hiệu quả cao hơn và ứng

dụng thử nghiệm đối với cơ sở dữ liệu y khoa.

CHƯƠNG 2

MỘT SỐ MỐI QUAN HỆ DỮ LIỆU ĐƯỢC PHÁT HIỆN THÔNG QUA

NGÔN NGỮ TRUY VẤN

2. 1. Luật kết hợp

2. 1. 1. Các khái niệm cơ bản

Khai phá luật kết hợp là một kỹ thuật quan trọng của khai phá dữ liệu. Mục

tiêu khai phá là phát hiện những mối quan hệ giữa các giá trị dữ liệu trong cơ sở dữ

liệu. Mô hình đầu tiên của bài toán khai phá luật kết hợp là mô hình nhị phân (hay

còn gọi là mô hình cơ bản) được R. Agrawal, T. Imielinski và A. Swami đề xuất

vào năm 1993, xuất phát từ nhu cầu phân tích dữ liệu của cơ sở dữ liệu giao tác,

phát hiện các mối quan hệ giữa các tập mục hàng hóa (Itemsets) đã bán được tại các

siêu thị [15]. Việc xác định các quan hệ này không phân biệt vai trò khác nhau cũng

như không dựa vào các đặc tính dữ liệu vốn có của các thuộc tính mà chỉ dựa vào sự

xuất hiện cùng lúc của chúng. Dưới đây là một số các khái niệm cơ bản của luật kết

hợp [6]:

2. 1. 1. 1. Cơ sở dữ liệu giao tác

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 giao tác 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-tập mục. Giao tác T gọi là chứa tập

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

mục X nếu .

2. 1. 1. 2. Tập mục phổ biến và luật kết hợp

Độ hỗ trợ tập mục: Cho tập mục X  I. Ta gọi độ hỗ trợ (Support) của X

trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm các giao tác chứa

X trên tổng số các giao tác trong DB, tức là:

Ta có: 0 ≤ sup(X) ≤ 1 với mọi tập mục X  I.

Tập mục phổ biến: Cho tập mục X  I và ngưỡng hỗ trợ tối thiểu

(minimum support) (được xác định trước bởi người sử dụng). X

được gọi là tập phổ biến (frequent itemset hoặc large itemset) với độ hỗ trợ tối thiểu

minsup nếu , ngược lại X gọi là tập mục không phổ biến.

Luật kết hợp: Một luật kết hợp là một biểu thức dạng , trong đó X

và Y là các tập con của I, ; X gọi là tiền đề, Y gọi là kết luận của luật.

Luật kết hợp có hai thông số quan trọng là độ hỗ trợ và độ tin cậy.

Độ hỗ trợ của luật: Độ hỗ trợ (Support) của một luật kết hợp , ký

hiệu là , là độ hỗ trợ của tập mục , .

Như vậy độ hỗ trợ của luật kết hợp chính là xác suất P(XY) của sự

xuất hiện đồng thời của X và Y trong một giao tác.

Ta có: .

Độ tin cậy của luật: Độ tin cậy (Confidence) của một luật , ký hiệu

, là tỷ lệ phần trăm giữa số giao tác chứa và số giao tác chứa

X trong cơ sở dữ liệu DB.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Độ tin cậy của luật kết hợp chính là xác suất có điều kiện P(Y/X) :

và ta có

Các luật thoả mãn cả hai ngưỡng độ hỗ trợ tố i thiểu (minsup) và độ tin cậy tố i thiểu

(minconf), tức thỏa mãn và ,

được gọi là luật kết hợp mạnh.

Tính chất cơ bản của tập phổ biến :

Cho cơ sở dữ liệu giao tác DB và ngưỡng độ hỗ trợ tối thiểu minsup. Tập

mục phổ biến có các tính chất sau:

(1) Nếu X, Y là các tập mục và thì .

(2) Nếu một tập mục là không phổ biến thì mọi tập cha của nó cũng không

phổ biến.

(3) Nếu một tập mục là phổ biến thì mọi tập con khác rỗng của nó cũng là

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

Ví dụ:

Luật kết hợp là những luật có dạng như “ 80% khách hàng mua máy điện

thoại di động thì mua thêm simcard, 30% có mua cả máy máy điện thoại di động lẫn

simcard”. “mua máy điện thoại di động” ở đây được xem là vế trái (tiền đề) của

luật, còn “mua simcard” là vế phải (kết luận) của luật. Các con số 30% là độ hỗ trợ

của luật (support – số phần trăm các giao tác chứa cả vế trái và vế phải), còn 80% là

độ tin cậy của luật (confidence – số phần trăm các giao tác thoả mãn vế trái thì cũng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thoả mãn vế phải

Hình 2. 1: Minh họa luật kết hợp

Độ hỗ trợ (support) và Độ tin cậy (confidence) là hai thước đo cho một luật

kết hợp. Chẳng hạn phân tích cơ sở dữ liệu bán hàng nhận được thông tin về những

khách hàng mua máy tính có khuynh hướng mua phần mềm quản lý tài chính trong

cùng lần mua được mô tả trong luật kết hợp sau

 “Máy tính => Phần mềm quản lý tài chính ” [Độ hỗ trợ: 2%, độ tin cậy:

60%]

 Độ hỗ trợ 2% có nghĩa là 2% của tất cả các khách hàng mua máy tính

kèm theo phần mềm quản lý tài chính.

 Độ tin cậy 60% có nghĩa là 60% các khách hàng mua máy tính cũng mua

phần mềm.

Chúng ta nhận thấy rằng tri thức đem lại bởi luật kết hợp ở dạng trên có sự

khác biệt cơ bản so với thông tin thu được từ các câu lệnh truy vấn dữ liệu thông

thường như ngôn ngữ SQL. Đó là những tri thức, những mối liên hệ chưa biết trước

và mang tính dự báo đang tiềm ẩn trong dữ liệu. Những tri thức này không đơn giản

chỉ là kết quả của phép nhóm, tính tổng hay sắp xếp mà là kết quả của một quá trình

tính toán khá phức tạp và tốn nhiều thời gian. Thông tin mà dạng luật này đem lại là

rất đáng kể và hỗ trợ không nhỏ trong quá trình ra quyết định. Tìm kiếm được các

luật kết hợp “quý hiếm” và mang nhiều thông tin từ Cơ sở dữ liệu tác nghiệp là một

trong những hướng tiếp cận chính của lĩnh vực khai phá dữ liệu.

2. 1. 2. Bài toán khai phá luật kết hợp

Cho cơ sở dữ liệu giao tác DB, ngưỡng độ hỗ trợ tối thiểu minsup và ngưỡng

độ tin cậy tối thiểu minconf.

Yêu cầu: Tìm tất cả các luật kết hợp trên cơ sở dữ liệu DB sao cho

và .

Bài toán khai phá luật kết hợp này được gọi là bài toán cơ bản hay bài toán

nhị phân, vì ở đây, giá trị của mục dữ liệu trong cơ sở dữ liệu là 0 hoặc 1 (xuất hiện

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

hay không xuất hiện).

Bài toán khai phá luật kết hợp được chia thành hai bài toán con. Bài toán thứ

nhất là tìm tất cả các tập mục thỏa mãn độ hỗ trợ tối thiểu cho trước, tức là tìm tất

cả các tập phổ biến. Bài toán thứ hai là sinh ra các luật kết hợp từ các tập phổ biến

đã tìm được thỏa mãn độ tin cậy tối thiểu cho trước.

Bài toán thứ hai được giải quyết như sau : giả sử đã tìm được X là tập phổ

biến, ta sinh ra các luật kết hợp bằng cách tìm , kiểm tra độ tin cậy của luật

có thỏa mãn độ tin cậy tối thiểu không. Bài toán thứ hai này đơn giản,

mọi khó khăn nằm ở bài toán thứ nhất, hầu hết các nghiên cứu về luật kết hợp đều

tập trung giải quyết bài toán thứ nhất là tìm các tập phổ biến.

2. 2. Khai thác tập phổ biến dựa trên ngôn ngữ truy vấn

2. 2. 1. Ngôn ngữ truy vấn

2. 2. 1. 1. Khái niệm về ngôn ngữ truy vấn

Theo [4, 10] ngôn ngữ xử lý dữ liệu quan hệ là ngôn ngữ bao gồm tập các chỉ

thị cho phép hỏi, thay đổi, thêm bớt và sửa thông tin của một CSDL.

Trong các ngôn ngữ thao tác dữ liệu SQL, SEQUEL, QUEL, QBE. . . thì

ngôn ngữ SQL (Structure Query Language) là ngôn ngữ hỏi đáp dữ liệu có cấu trúc,

phi thủ tục, chuẩn mực và điển hình được xác nhận là mạnh, phổ dụng lại dễ sử

dụng.

Ngôn ngữ này được phát triển từ ngôn ngữ SEQUEL-2, thử nghiệm và cài

đặt tại trung tâm nghiên cứu của hãng IBM (tại SALJOISE, CALIFONIA) cho hệ

thống quản trị cơ sở dữ liệu lớn điển hình là SYSTEM-R. Trong SYSTEM-R, SQL

vừa đóng vai trò là một ngôn ngữ có thể thao tác độc lập của người dùng đầu cuối,

đồng thời lại có khả năng là một ngôn ngữ con được nhúng trong ngôn ngữ chủ

PL/1.

Hiện nay ngôn ngữ SQL đã được chuyển thành chuẩn chính thức của ANSI

và ISO (Cơ quan tiêu chuẩn quốc tế) và được rất nhiều các phần mềm Quản trị hệ

CSDL hỗ trợ cho ngôn ngữ này như Oracle, NGRESS, DB2, SYBASE, INFOMIC.

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

. . v. v.

2. 2. 1. 2. Các đặc điểm của ngôn ngữ SQL

Đây là một ngôn ngữ rất phù hợp cho CSDL phân tán theo mô hình Client-

Server, nó cho phép nhiều người dùng cùng truy nhập đến một cơ sở dữ liệu với độ

an toàn ổn định và tính bảo mật cao. Ngôn ngữ SQL đảm bảo lưu lượng truyền

thông tin trên mạng tối thiểu vì Client chỉ gửi câu hỏi và nhận về kết quả từ Server

chứ không phải gửi cả CSDL đi để xử lý. Đặc biệt là do được các hệ quản trị CSDL

hỗ trợ nên phương thức chung để giao tiếp giữa các phần mềm quản trị CSDL (như

dùng ODBC) và điều này làm cho hệ thống có tính mở. Thật vậy, có thể sử dụng

một hệ quản trị CSDL tốt (đòi hỏi cấu hình phần cứng mạnh) nhưng có thể vẫn

dùng phần mềm yêu cầu phần cứng thấp trên các Client hoặc có thể dùng các máy

Net computer. Mặt khác cũng có thể dùng nhiều hệ quản trị CSDL trong cùng một

hệ thống để khai thác các thế mạnh của chúng, ví dụ có thể dùng Lotus Notes trên

các Client (giao diện người dùng thân thiện, ưu việt về truyền thông, xử lý tốt văn

bản) và kết nối vào CSDL Oracle trên Server (tính bảo mật cao, đa người dùng,

quản lý tốt các giao tác-Transaction).

Ngôn ngữ SQL còn có khả năng thực hiện được những câu hỏi phức tạp mà

các dạng ngôn ngữ khác không đáp ứng được và một câu lệnh SQL có thể thay thế

cho một tập hợp các câu lệnh lập trình CSDL thông thường.

Ngoài cơ cấu xử lý dữ liệu SQL còn có các công cụ để xây dựng các ứng

dụng WEB, có khả năng xử lý dữ liệu, tạo báo cáo, thiết kế mô hình dữ liệu và quản

trị hệ thống.

2. 2. 1. 3. Các loại câu lệnh SQL thao tác với dữ liệu

Trong ngôn ngữ SQL có hai loại lệnh thao tác với dữ liệu, đó là:

 Các lệnh định nghĩa dữ liệu DDL (Data Defined Language): là các lệnh

tạo bảng, tạo Index. . . v. v

 Các lệnh cập nhật dữ liệu DML (Data Manipulation Language) như

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

SELECT, UPDATE, INSERT, DROP.

 Các lệnh cập nhật dữ liệu được sử dụng thường xuyên cho nên cần thiết

phải tìm ra phương án chọn cách viết câu lệnh, cách thực hiện câu lệnh sao

cho có hiệu quả nhất về mặt thời gian cũng như là về không gian lưu trữ.

Hệ thống cơ sở dữ liệu dùng các câu lệnh SQL [7, 8]:

1. Câu lệnh đơn: Một câu lệnh đơn là một câu lệnh INSERT, UPDATE,

DELETE hoặc SELECT thao tác duy nhất trên một bảng.

2. Query đơn: thực chất là một câu lệnh SELECT (có thể với nhiều bảng).

3. Kết nối: Một kết nối là một truy vấn dữ liệu nhiều hơn một bảng và từ kết

nối giữa các bảng nằm trong mệnh đề FROM. Phép kết nối kéo dữ liệu từ

các bảng khác nhau và so sánh chúng từng đôi tại dòng chung ở tất cả các

bảng. Có các kiểu kết nối sau (i) Liên kết ngang bằng (Equijoins): liên kết

này dựa vào sự cân bằng của điều kiện tìm kiếm mà chỉ ra mối quan hệ

giữa 2 bảng; (ii) Liên kết không ngang bằng (Non-Equijoins) là liên kết 1

bảng này với một bảng khác dựa trên sự so sánh không bằng như toán tử

<=, >=, BETWEEN; (iii) Liên kết ngoài (Outer joins): Giả sử có 2 bảng

KháchHàng và HoáĐơn cùng có 2 cột là MãKháchHàng. Khi liên kết 2

bảng cho hiện lên tên của những khách hàng có số thứ tự trùng nhau. Nếu

muốn hiện lên cả những khách hàng không thoả mãn trong bảng

KháchHàng cũng được hiện lên thì cần dùng liên kết ngoài; (iv) Liên kết

với chính nó (Self joins): Đây là kiểu liên đặc biệt giữa một bảng với

chính nó như 2 bảng riêng biệt. Để làm được việc này thì bảng đó phải có

một tên quan hệ.

4. Tích Đề-các: là kết quả của việc nhân hai tập hợp.

5. Câu lệnh phức: Một câu lệnh phức như là một câu lệnh SELECT, INSER,

UPDATE, hoặc DELETE có chứa một câu lệnh SELECT khác (được gọi

là subquery).

6. Các query kết hợp: Một query kết hợp là một query có sử dụng các toán

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

tử tập hợp như UNION, UNION ALL, INTERSECT hoặc MINUS.

7. Câu lệnh sử dụng View: View là một bảng logic mà thực chất là một câu

lệnh SELECT mà có thể thao tác giống như đối với bảng.

8. Câu lệnh phân tán: nghĩa là câu lệnh truy nhập dữ liệu từ xa.

2. 2. 2. Tìm tập phổ biến bằng K-way join

2. 2. 2. 1. Cấu trúc bảng dữ liệu

Do số item trong một giao tác không thể biết trước và có thể khác nhau nên

cấu trúc bảng dạng D (tid, item1, item2, …, itemn) là không thực tế. Ngoài ra, trong

thực tế, số item tối đa trong một giao tác có thể vượt quá số cột mà HQTCSDL (Hệ

quản trị cơ sở dữ liệu) hỗ trợ. Chẳng hạn đối với SQL 2000/2005, số cột tối đa cho

phép trong một bảng là 1024. Trong trường hợp này, cấu trúc bảng có dạng D (tid,

item1, item2, …, itemn) là không khả thi vì n phải nhỏ hơn 1024. Ngoài ra, nếu lưu

trữ bảng có nhiều cột, thì rất có thể sẽ lãng phí bộ nhớ khi mà số item trong các giao

tác khác nhau qua nhiều. Do đó, để không phụ thuộc vào số item trong một giao tác,

không phụ thuộc vào giới hạn cột trong một bảng của HQTCSDL, và để tiết kiệm

bộ nhớ, cấu trúc dữ liệu đề xuất cho việc khai thác có dạng D (Tid, item) [8, 9, 10,

11]. Trong đó:

 Tid: là chỉ danh giao tác. Mỗi giao tác có một chỉ danh duy nhất để phân

biệt với các giao tác khác

 Item: Tên item trong giao tác đó. Các item trong cùng một giao tác sẽ có

cùng Tid

Như vậy đối với cơ sở dữ liệu dạng D (tid, item1, item2, …, itemn), ta sẽ

chuyển về dạng D (tid, item) trước khi thực hiện việc khai khác bằng SQL.

Ví dụ Cấu trúc bảng ban đầu, bảng 3. 1

tid Item1 item2 item3 item4 item5

100 a c d

200 b c e

300 a b e

Bảng 2. 1: Cấu trúc bảng ban đầu

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Sẽ được đưa về cấu trúc D (tid, item) như bảng 3. 2

Item Tid

a 100

c 100

d 100

b 200

c 200

e 200

a 300

b 300

e 300

Bảng 2. 2: Cấu trúc bảng dùng để khai khác

2. 2. 2. 2. Tìm tập phổ biến bằng K-way join

2. 2. 2. 2. 1. Phát sinh ứng cử viên bằng K-way join

Theo tài liệu của Mishra, P. , S. Chakravarthy [11], việc tìm tập phổ biến sẽ

được thực hiện qua hai bước. Trong bước đầu tiên, tất cả các tập ứng viên Ck (hình

thành do sự kết hợp của k item) được phát sinh. Trong bước thứ hai, mỗi tập ứng

viên sẽ được tính độ hỗ trợ. Những tập ứng viên nào có độ hỗ trợ lớn hơn hay bằng

độ hỗ trợ tối thiểu sẽ được cộng dồn vào tập Fk tương ứng.

Phát sinh ứng cử viên bằng K-way join: Việc phát sinh các tập ứng viên Ck

được thực hiện dựa trên tập phổ biến Fk-1. Thêm vào đó, để tối ưu về mặt xử lý, việc

loại bỏ những tập ứng viên dư thừa hay còn gọi là tỉa nhánh cũng được thực hiện

song song tại bước này. Dựa trên tính chất của tập phổ biến: Tất cả các tập con của

một tập phổ biến phải là tập phổ biến. Do đó, những tập ứng viên c  Ck mà tồn tại

tập con có chiều dài (k-1) không thuộc tập phổ biến Fk-1 sẽ bị loại ra khỏi tập Ck.

Khi đó, thuật toán phát sinh tập ứng viên như sau:

INSERT INTO Ck

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

SELECT I1. item1, …, I1. itemk-1, I2. itemk-1

FROM Fk-1 I1, Fk-1 I2, …, Fk-1 Ik

WHERE

- Điều kiện phát sinh tập ứng viên

I1. item1 = I2. item1 AND

. . .

I1. itemk-2 = I2. itemk-2 AND

I1. itemk-1 < I2. itemk-1 AND

--Điều kiện tỉa nhánh item1

I1. item2 = I3. item1 AND

. . . …

I1. itemk-1 = I3. itemk-2 AND

I2. itemk-1 = I3. itemk-1 AND

--Điều kiện tỉa nhánh itemk-2

I1. item1 = Ik. item1 AND

……

I1. itemk-3 = Ik. itemk-3 AND

I1. itemk-1 = Ik. itemk-2 AND

I2. itemk-1 = Ik. itemk-1

Số tập ứng viên sau mỗi vòng lặp sẽ được giảm dần nhờ vào tính chất của tập

phổ biến: Tất cả các tập con của một tập phổ biến là tập phổ biến. Biểu đồ hình cây

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

cho tiến trình này như sau:

Hình 2. 2: Tiến trình phát sinh tập ứng viên Ck

Ví dụ F3 = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}}. Sau bước liên

kết với F3, tập ứng viên C4 sẽ là: {{1, 2, 3, 4}, {1, 3, 4, 5}}. Trong bước tỉa nhánh,

Itemset {1, 3, 4, 5} được kết hợp từ hai tập itemset {1, 3, 4} và {1, 3, 5}. Tuy nhiên,

itemset {3, 4, 5}  {1, 3, 4, 5} không tồn tại trong F3, vì vậy {1, 3, 4, 5} sẽ bị loại

khỏi C4, và C4 chỉ còn {1, 2, 3, 4}.

2. 2. 2. 2. 2. Đếm độ hỗ trợ bằng K-way join

Pha này rất quan trọng và tốn nhiều thời gian trong quá trình khai khác. Mục tiêu

của pha này là xác định ra được các itemset nào là tập phổ biến trong các tập ứng

viên. Trong cách tiếp cận dạng SQL, ta có 3 lựa chọn [14] để đếm độ hỗ trợ: K- way

join, 2-Group by, Query sub Query.

Theo [13, 14] thuâ ̣t toán K-way join: Tại mỗi vòng lặp thứ k, k bản copy của

bảng dữ liệu đầu vào được liên kết với tập ứng viên Ck theo sau bởi mệnh đề

GROUP BY trên các itemset. k bản copy của bảng dữ liệu đầu vào để so sánh k

items trong ứng viên Ck với mỗi item từ mỗi bản copy của bảng dữ liệu đầu vào.

Mệnh đề GROUP BY dùng để xác định itemset nào có độ hỗ trợ lớn hơn hay bằng

độ hỗ trợ tối thiểu sẽ là tập phổ biến. Thủ tục supcnt_k_way_join (k, minsup, T, tid,

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

item) và biểu đồ hình cây để phát sinh tập phổ biến có chiều dài k như sau:

INSERT INTO Fk

SELECT item1, …, itemk, COUNT (*)

FROM Ck, T t1, …, T tk

WHERE

t1. item = Ck. item1 AND

t2. item = Ck. item2 AND

…

tk. item = Ck. itemk AND

t1. tid = t2. tid AND

t2. tid = t3. tid AND

…

tk-1. tid = tk. tid

GROUP BY item1, item2, …, itemk

HAVING COUNT (*) ≥ minsup

Hình 2. 2: Đếm độ hỗ trợ bằng cách tiếp cận K-way Join

Khi áp dụng cách tiếp cận này vào thực tế, thời gian xử lý chấp nhận được

(tăng chậm) khi dữ liệu ngày càng nhiều.

2-Group By: Cách tiếp cận này giảm số liên kết của cách tiếp cận K-way

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

join. Cách tiếp cận này chỉ liên kết tập ứng viên Ck với bảng dữ liệu ban đầu chỉ 1

lần. Điều kiện liên kết kiểm tra xem mục (item) trong bảng dữ liệu ban đấu có giống

với bất kỳ k mục (item) trong tập ứng viên Ck hay không?. Nếu có thì gom nhóm tất

cả các item đó lại, nghĩa là gom nhóm trên tập (item1, item2, …, itemk, Tid) với điều

kiện số lượng các items như thế phải bằng k. Kết quả là một tập những item và các

tid mà tid này hỗ trợ itemset trong Ck. Khi tất cả các itemset được xác định, ta thực

hiện việc gom nhóm trên itemset (item1, item2, …, itemk). Những itemset mà có độ

hỗ trợ lớn hơn hay bằng độ hỗ trợ tối thiểu sẽ được đưa vào danh sách các tập phổ

biến. Cấu trúc câu lệnh SQL như sau:

INSERT INTO Fk

SELECT item1, item2, …, itemk, count (*)

FROM (SELECT item1, item2, …, itemk, COUNT (*)

FROM T, Ck

WHERE item = Ck. item1 OR

…. .

item = Ck. itemk

GROUP BY item1, item2, …, itemk, tid

HAVING COUNT (*) = k

) As temp

GROUP BY item1, item2, …, itemk

HAVING COUNT (*) ≥ minsup

Trong cách tiếp cận này, việc đếm độ hỗ trợ chỉ phải liên kết một lần giữa

tập ứng viên và bảng dữ liệu đầu vào. Vì vậy, số liên kết trong vòng lặp thứ k sẽ

tương đối ít so với cách tiếp cận K-way join. Tuy nhiên, cách tiếp cận này đã sử

dụng toán tử OR để so sánh các itemset, cùng với hai mệnh đề GROUP BY và

HAVING (một cho việc gom nhóm các items trong bảng dữ liệu đầu vào và một

cho lúc thực sự đếm độ hỗ trợ) cho việc đếm độ phổ biến của itemset có chiều dài k.

Do bản thân toán tử OR trong các HQTCSDL không cung cấp xử lý tối ưu nên chi

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

phí so sánh cao sẽ cao, thêm vào đó là việc sử dụng hai mệnh đề GROUP BY và

HAVING. Hai mệnh đề này tốn rất nhiều chi phí về mặt thời gian khi xử lý. Trên

thực tế, khi áp dụng cách tiếp cận này, thời gian xử lý sẽ tăng đột biến khi khối

lượng dữ liệu ngày càng nhiều.

Query sub Query: Cách tiếp cận này đã tận dụng việc sử dụng các tiền tố

chung cho việc đếm độ hỗ trợ. Có rất nhiều câu truy vấn con trung gian được phát

sinh trong quá trình đếm độ hỗ trợ. Gọi Qi là truy vấn con thứ i với i ≠ 0. (Chú ý

rằng, không có truy vấn con Q0)

Qi sẽ chọn ra những item từ truy vấn con Qi-1, Ci và bảng dữ liệu đầu vào T

với điều kiện các item trong Qi-1 bằng với các item trong Ci và Tid trong T bằng với

Tid trong Qi-1. Vì vậy, trong bất kỳ vòng lặp nào, với m cho trước thì (m-1) item

(item1, item2, …, itemm-1) trong Qm-1 bằng với (m-1) item trong Cm. Tương tự cho

Tid trong T phải bằng với Tid trong Qm-1. Nếu tất cả đều thỏa, và có độ hỗ trợ lớn

hơn hay bằng độ hỗ trợ tối thiểu thì chúng được đưa vào Fk. Biểu đồ hình cây và

cấu trúc câu truy vấn có dạng như sau:

Hình 2. 3: Biểu đồ hình cây cho Sub Query Qi

INSERT INTO Fk

SELECT item1, item2, …, itemk, count (*)

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

FROM (Subquery Qk) t

GROUP BY item1, item2, …, itemk

HAVING COUNT (*) ≥ minsup

Subquery Qi (1 ≤ i ≤ k):

SELECT item1, item2, …, itemi, tid

FROM T ti, (Subquery Qi-1) as ri-1,

(SELECT DISTINCT item1, item2, …, itemi

FROM Ck) As di

WHERE ri-1. item1 = di. item1 AND

…. .

ri-1. itemi-1 = di. itemi-1 AND

ri-1. tid = ti. tid AND

ti. item = di. itemi

Tại bất kỳ vòng lặp k nào, việc phát sinh truy vấn con Qk-1 được thực hiện để

tìm ra những item phổ biến có chiều dài (k-1). Tiếp đó, truy vấn con Qk-1 sẽ gọi

ngược lại truy vấn con Qk-2, tiến trình này sẽ gọi ngược cho đến Q1. Sau đó, Q1 sẽ

thực thi và trả về kết quả các itemset phổ biến có chiều dài 1. Kết quả này sẽ được

gửi tới Q2, để dùng cho việc phát sinh itemset phổ biến có chiều dài 2. Lặp lại tiến

trình này cho đến khi Qk-1 được thực thi. Lưu ý rằng, do các truy vấn con này phải

được thực hiện tuần tự, nên tại bất kỳ vòng lặp k nào, (k-1) truy vấn con phải được

thực thi trước. Do đặc tính của cách tiếp cận này là phát sinh quá nhiều truy vấn con

trong quá trình đếm độ hỗ trợ, nên trong thực nghiệm, thời gian thực thi của thuật

toán này là không khả thi.

2. 2. 3. Kết quả thử nghiệm 3 phương pháp đếm độ hỗ trợ

Cấu hình thử nghiệm:

 CPU Intel Pentium 4, 512 MB RAM

 Hệ quản trị cơ sở dữ liệu: Microsoft SQL Server 2000

 Hệ điều hành: Windows XP Professional, Service Pack 2

 Dữ liệu thử nghiệm: 100000 mẩu tin trong dữ liệu nghiệp vụ nhập của

http://www.lrc.tnu.edu.vn

bán hàng tại một địa điểm thu ngân Số hóa bởi Trung tâm Học liệu – ĐHTN

Việc thử nghiệm cũng được thực hiện trên những tập dữ liệu có kích thước

khác nhau (đại diện cho 3 giá trị: nhỏ, trung bình và lớn) và giá trị minsup khác

nhau (đại diện cho 3 giá trị: nhỏ, trung bình, lớn) để đánh giá tương đối chính xác

thời gian thực thi của các thuật toán. Để chú trọng vào việc so sánh các thuật toán,

chi phí chuyển đổi từ cơ sở dữ liệu dạng ngang D (Tid, item1, item2, …) sang dạng

dọc D (Tid, item) cũng không được tính vào thời gian phân tích.

Gọi D là kích thước CSDL, minsup là độ hỗ trợ tối thiểu. Ta quy ước như sau:

 0 < D ≤ 10000: Kích thước dữ liệu nhỏ

 10000 < D ≤ 50000: Kích thước dữ liệu trung bình

 D > 50000: Kích thước dữ liệu lớn

 0 < minsup ≤ 1%: Độ hỗ trợ nhỏ

 1 < minsup ≤ 5%: Độ hỗ trợ trung bình

 minsup > 5%: Độ hỗ trợ lớn

Kết quả thử nghiệm 3 phương pháp [11]:

- Với độ hỗ trợ lớn minsup =10% và các kích thước CSDL khác nhau:

Hình 2. 4: Đồ thị thời gian thực thi của 3 thuật toán khi minsup=10% và D=100000

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 2. 5: Đồ thị thời gian thực thi 3 thuật toán khi minsup=10% và D=50000

Hình 2. 7: Đồ thị thời gian thực thi của 3 thuật toán khi minsup=10% và D=10000

Hình 2. 6: Đồ thị tổng hợp thời gian thực thi của 3 thuật toán khi minsup lớn

Dựa trên đồ thị ta thấy, K-way join luôn hiệu quả hơn 2 thuật toán còn lại trong mọi

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

trường hợp khi độ hỗ trợ lớn. Khi kích thước CSDL tăng từ nhỏ lên trung bình, thời

gian xử lý của K-way join cũng tăng, nhưng tăng ít vì các cải tiến của của K-way

join đã khắc phục được nhược điểm của thuật toán gốc.

- Tiếp tục thử nghiệm với độ hỗ trợ trung bình và các kích thước CSDL khác

nhau:

Hình 2. 7: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=100000

Hình 2. 8: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=50000

Hình 2. 9: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=10000

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 2. 10: Đồ thị tổng hợp thời gian thực thi 3 thuật toán khi minsup trung bình

Dựa trên đồ thị ta thấy, thời gian thực thi của K-way join vẫn tốt hơn 2 thuật toán

còn lại trong mọi trường hợp kích thước CSDL khi minsup trung bình. Một điểm

lưu ý ở đây là khi kích thước dữ liệu nhỏ thì Sub query lại tỏ ra tốt hơn 2 group by

do thời gian thực thi các truy vấn con nhanh hơn khi thực hiện phép toán tử OR và 2

mệnh đề GROUP BY và HAVING.

- Với độ hỗ trợ nhỏ và các kích thước CSDL khác nhau:

Hình 2. 11: Đồ thị thời gian thực thi 3 thuật toán khi minsup = 1% và D = 100000

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Hình 2. 12: Đồ thị thời gian thực thi 3 thuật toán khi minsup = 1% và D= 50000

Hình 2. 13: Đồ thị thời gian thực thi của 3 thuật toán khi minsup =1% và D=10000

Hình 2. 154: Đồ thị tổng hợp thời gian thực thi của 3 thuật toán khi minsup nhỏ

Dựa trên đồ thị ta thấy, K-way join vẫn được xem là tốt nhất khi minsup nhỏ

và kích thước CSDL tuỳ ý. Và đặc biệt khi kích thước dữ liệu tăng thì K-way join

tăng rất ít trong khi các thuật toán còn lại tăng rất nhanh.

Tóm lại, với các kết quả thử nghiệm ở trên [14], việc so sánh thời gian chạy

của 3 thuật toán K-way join, 2-group by, Sub query trong việc đếm độ hỗ trợ để

khẳng định thuật toán K-way join là lựa chọn tốt nhất trong các cách tiếp cận với hệ

quản trị CSDL SQL với mọi minsup và mọi kích thươcs CSDL.

2. 2. 4. Phân tích các cải tiến của thuật toán k-way join

Dựa vào các kết quả vừa nêu trên, đề tài đưa ra các phân tích về thuật toán k-way

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

join như sau:

2. 2. 4. 1. Tối ưu hóa vòng lặp 1, 2

Quan sát thuật toán K-way join ta thấy:

 Trong tất cả các vòng lặp thì vòng lặp thứ hai tiêu tốn nhiều thời gian hơn

cả.

 Kích thước của C2 thường rất lớn nên chi phí cho việc đếm độ hỗ trợ là 2

rất cao (gồm Cn tập ứng viên được phát sinh, với n là số tập phổ biến có

chiều dài 1)

 Các tập ứng viên có chiều dài 2 được phát sinh từ tập phổ biến có chiều

dài 1, do đó không thu được lợi ích gì từ việc thu gọn/tỉa nhánh trong bước

này.

 Không có luật kết hợp nào được sinh ra từ F1, vì vậy tiến trình phát sinh

C2 từ F1 là không cần thiết

Do vậy giải pháp: Tính sẵn F1, F2

Tính F1: Sử dụng bảng dữ liệu đầu vào để tìm tập phổ biến có chiều dài 1.

Cấu trúc câu truy vấn như sau:

INSERT INTO F1

SELECT item, COUNT (*)

FROM InputTable T

GROUP BY T. item

HAVING COUNT (*)≥ minsup

Tính F2: Thực hiện phép kết 2 bảng dữ liệu đầu vào với điều kiện item trong

bảng dữ liệu đầu vào thứ nhất phải nhỏ hơn item trong bảng dữ liệu đầu vào thứ hai

và cả hai item này cùng thuộc một giao tác. Cấu trúc câu truy vấn như sau:

INSERT INTO F2

SELECT t1. item, t2. item, COUNT (*)

FROM InputTable T1, InputTable T2

WHERE T1. tid = T2. tid and T1. item < T2. item

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

GROUP BY T1. item, T2. item

HAVING COUNT (*) ≥ minsup

2. 2. 4. 2. Giảm kích thước dữ liệu đầu vào

Ta nhận thấy, trong thuật toán K-way join, ta luôn sử dụng bảng dữ liệu đầu

vào trong việc đếm độ hỗ trợ. Tuy nhiên, bản thân những item trong tập dữ liệu đầu

vào này, không phải item nào cũng là phổ biến (có chiều dài 1). Do vậy, việc loại bỏ

ngay từ ban đầu những item không là phổ biến sẽ giúp ta giảm kích thước của tập

dữ liệu đầu vào mà không làm ảnh hưởng đến việc đếm độ hỗ trợ của những vòng

lặp sau. Điều này sẽ giảm chi phí kết mỗi khi phải liên kết với bảng dữ liệu đầu vào.

Giải pháp: Xoá những item không là phổ biến trong tập dữ liệu đầu vào.

Những item không phổ biến là những item trong tập dữ liệu đầu vào và  F1.

Câu truy vấn có dạng:

DELETE InputTable T

WHERE T. item NOT IN (SELECT item FROM F1)

2. 2. 4. 3. Giảm số phép kết tại vòng lặp

Tại mỗi vòng lặp k bất kỳ phải sử dụng k bảng dữ liệu đầu vào liên kết với

Ck. Trong trường hợp dữ liệu đầu vào rất lớn thì việc kết k bảng này sẽ tốn rất nhiều

chi phí. Để giảm thiểu chi phí này, ta tính sẵn tập phổ biến từ một giao tác cụ thể

trong vòng lặp (k-1), và dùng nó trong việc đếm độ hỗ trợ tại vòng lặp thứ k. Điều

này sẽ tiết kiệm được một chuỗi các phép kết vì đã được làm trong vòng lặp trước

đó. Tối ưu này tỏ ra rất hiệu quả khi chiều dài tập phổ biến lớn, và vòng lặp nhiều.

Tập Combk (Tid, item1, item2, …, itemk) được tạo ra khi ta đếm độ hỗ trợ tại vòng

lặp thứ k. Combk là kết quả kết của 3 tập Combk-1, T, và Ck để chọn ra tất cả những

giao tác trong T mà chứa 1-extension tới tập phổ biến có chiều dài (k-1).

Giải pháp: Tính sẵn tập Combk

Cấu trúc câu truy vấn như sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

INSERT INTO Combk

SELECT T1. tid, T1. item1, T1. item2, …, T1. itemk-1, T2. item

FROM Ck, Combk-1 T1, T T2

WHERE T1. item1 = Ck. item1 AND

…

T1. itemk-1 = Ck. itemk-1 AND

T2. item = Ck. itemk AND

T1. tid = T2. tid

Trong bất kỳ vòng lặp k nào, thay vì phải sử dụng (k+1) phép kết, bây giờ ta

chỉ cần dùng có 3 phép kết. Tại vòng lặp thứ k, ta chỉ sử dụng 3 quan hệ Ck, T, và

Combk-1 cho việc kết. Tuy nhiên, ta phải tính Combk-1 trước để nó có thể được dùng

trong lần lặp kế tiếp.

Fk sau đó được phát sinh từ Combk bằng cách nhóm k items (item1, item2, …,

itemk) và chọn ra những mục có độ hỗ trợ lớn hơn hay bằng độ hỗ trợ tối thiểu. Câu

truy vấn sẽ có dạng:

INSERT INTO Fk

SELECT item1, item2, …, itemk

FROM Combk

GROUP BY item1, item2, …, itemk

HAVING COUNT (*) >= minsup

Một lưu ý nổi bật ở đây là F1, F2 đã được tính sẵn, nên nhu cầu tính Comb1,

Comb2 là không cần thiết. Đây là một tối ưu rất hiệu quả, vì nếu phải tính Comb1,

Comb2 thì kết quả của 2 tập này sẽ rất lớn. Và như vậy chi phí tính toán sẽ khá cao.

Ta chỉ cần tính bắt đầu từ Comb3 như sau.

INSERT INTO Comb3

SELECT T1. tid, t1. item, t2. item, t3. item

FROM InputTable T1, InputTable T2, InputTable T3, C3

WHERE

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

T1. item = C3. item1 and

T2. item = C3. item2 and

T3. item = C3. item3 and

T1. tid = T2. tid and

T2. tid = T3. tid

Sau khi có Comb3, ta tính sẵn F3 bằng cách

INSET INTO F3

SELECT item1, item2, item3

FROM Comb3

GROUP BY item1, item2, item3

HAVING COUNt (*)  minsup

Combk sẽ được tính từ Combk-1, Ck, và T với k ≥ 4

2. 2. 4. 4. Tối ưu chỉ mục cho tập dữ liệu đầu vào

Ta nhận thấy, tập dữ liệu đầu vào được dùng nhiều lần trong việc so khớp để

tính F1, F2, Combk (k ≥ 3). Để giảm thiểu chi phí so khớp, ta sẽ tạo chỉ mục (index)

cho tập dữ liệu đầu vào. Khi đó, thay vì dò tìm trong tập dữ liệu đầu vào, việc dò

tìm sẽ được thực hiện trong bảng chỉ mục trước, sau đó kết quả sẽ được ánh xạ vào

tập dữ liệu đầu vào (nếu việc dò tìm trong bảng chỉ mục tồn tại). Việc tạo chỉ mục

trên bảng dữ liệu đầu vào được thực hiện như sau:

CREATE INDEX InputTable_index ON InputTable (tid, item)

2. 2. 4. 5. Thuật toán tìm tập phổ biến bằng K-way join

Với các cải tiến ở trên, thuật toán K-way join cải tiến được mô tả như sau [14, 15]:

Input:

CSDL: D (tid_attr, item_attr)

Độ hỗ trợ tối thiểu: minsup

Output

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Các tập phổ biến Fi, i =1. . n

Giải thuật:

F1 = gen_F1 (D)//Tối ưu tính toán sẵn F1

D = delete_redundant_input_data (F1)// Tối ưu giảm kích thước dữ liệu đầu

vào

size_of_D = get_attr_count (D)

F2 = gen_F2 (D) //Tối ưu tính toán sẵn F2

--Tối ưu giảm số lượng liên kết từ k -> 3

C3 = get_C3 (F2)

Comb3 = get_Comb3 (D, C3)

F3 = gen_F3 (Comb3) //Tối ưu tính toán sẵn F3

level_current = 3 //Chiều dài của tập phổ biến hiện tại

f_current = get_attr_count (F2)

Lặp (f_current >0) // Tìm và phát sinh Ck với k≥ 4

level_current = level_current + 1

Clevel_current = candi_sql_gen (level_current)

candidate_count= get_attr_count (Clevel_current)

Nếu candidate_count > 0

Combk = gen_Combk (level_current)

End nếu

Nếu candidate_count > 0

Flevel_current = supcnt_k_way_join_optimize (level_current, minsup)

f_current= get_attr_count (Flevel_current)

End nếu

Ngược lại

f_current = 0

End nếu

f_current = f_current -1

End lặp

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Trong đó:

 gen_F1 (D): Phát sinh tập phổ biến có chiều dài 1 từ D

 gen_F2 (D): Phát sinh tập phổ biến có chiều dài 2 từ D

 gen_F3 (Combo3): Phát sinh tập phổ biến có chiều dài 3 từ Comb3

 get_attr_count (table_name): Trả về số lượng mẩu tin trong bảng

table_name

 candi_sql_gen (k): Phát sinh tập ứng viên có chiều dài k

 gen_Combk (k): Phát sinh tập Combk có chiều dài k

 supcnt_k_way_join_optimize (k, minsup): Phát sinh tập phổ biến có

chiều dài k sử dụng cách tiếp cận k-way join cải tiến: Sử dụng Combk để

phát sinh

2. 2. 5. Phát sinh luật kết hợp

2. 2. 5. 1. Giới thiệu

Đề tài đề xuất một phương pháp phát sinh luật kết hợp dựa trên tập luật mẫu.

Dưới đây là một số khái niệm và thuật toán:

 Gọi I = { i1, i2, …, in }: Tập n thuộc tính;

 VT, VP  I: Itemset: Tập các item của vế trái (VT), tập các item của vế

phải (VP);

 nVT, nVP  N*: Số item của vế trái, số item của vế phải;

 Gọi Rk: Là tập luật mẫu có chiều dài vế trái là k, k ≥1;

Luật mẫu có chiều dài k-TRk: là luật có dạng (VT, VP, k) và được hiểu là:

VT  VP có chiều dài vế trái là k; trong đó: VTVP = Ø, VT ≠ Ø, VP ≠ Ø.

Phát sinh tập luật mẫu TRSk: Tập luật mẫu TRSk: Là tập các TRk. Để phát

sinh tập luật mẫu TRSk ta phát sinh tập các thuộc tính vế trái có chiều dài k trước.

Việc phát sinh tập các thuộc tính vế trái có chiều dài k được dựa trên tổ hợp chập k

của n phần tử với 1≤ k ≤ n-1. VTk = Cnk 1≤ k ≤ n-1. Các thuộc tính vế phải = tập

thuộc tính ban đầu trừ đi tập các thuộc tính vế trái.

Thuật toán phát sinh tập các thuộc tính vế trái:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

VTk = Ø

For k =1 to n-1

VTk = phat_sinh_to_hop (n, k)

End for

Trong đó: thủ tục phat_sinh_to_hop (n, k): sẽ phát sinh ra tập các phần tử có

chiều dài k trong tập n phần tử.

Thuật toán phát sinh tập luật mẫu Rk như sau:

D= Tập các thuộc tính ban đầu

TRSk = Ø

For each phan_tu in VTk

nVT = len (phan_tu)

VP = D\{ phan_tu }

TRSk = TRSk{VT, VP, nVT}

End for

2. 2. 5. 2. Ví dụ 1

Với n = 2, D = {1, 2}. Kết quả phát sinh tập thuộc tính vế trái có chiều dài 1:

VT1= {{1}, {2}}; Và kết quả phát sinh tập luật mẫu tương ứng (có chiều dài 1):

TRS1 (tập luật mẫu)

TRS1 = {

{{1}, {2}, 1}, // {1}  {2} có chiều dài vế trái là 1

{{2}, {1}, 1}

}

Ví dụ 2: Với n = 3, D = {1, 2, 3}. Thì kết quả phát sinh tập thuộc tính vế trái

có chiều dài 1, và 2 như sau:

VT1= {{1}, {2}, {3}}

VT2 = {

{1, 2},

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

{1, 3},

{2, 3}

}

Và kết quả phát sinh tập luật mẫu tương ứng sẽ là:

TRS1 = {

{{1}, {2, 3}, 1}, // {1}  {2, 3} có chiều dài vế trái là 1

{{2}, {1, 3}, 1},

{{3}, {1, 2}, 1}

}

TRS2 = {

{{1, 2}, {3}, 2}, // {1, 2} 3 có chiều dài vế trái là 2

{{1, 3}, {2}, 2},

{{2, 3}, {1}, 2}

}

Sau khi đã tìm được tập các luật mẫu có chiều dài k. Bước tiếp theo là phát

sinh luật kết hợp dựa trên tập luật mẫu và các tập phổ biến tìm được. Thuật toán

phát sinh luật kết hợp như sau:

2. 2. 5. 3. Thuật toán

Thuâ ̣t toán được phát biểu như sau:

Max_len_of_rule = {frequent k-itemsets}

for (k = 2; k<= Max_len_of_rule; k++) do

TRSk = generate_template_rule_set (k)

for all subset t  Fk do

VT = generate_subset (t)

sp_LHS = find_sp (VT)

conf = t. sp/sp_LHS

if conf (t) ≥ minconf then

rk = replace_Left (TRk, VT)

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

rk = replace_Right (TRk, t\VT)

Rk = Rk{rk, sp, conf}

end if

end for

Answer = k{Rk}

Trong đó:

 Max_len_of_rule: Chiều dài tối đa của các tập phổ biến

 TRSk: Tập luật mẫu có chiều dài k

 TRk: Luật mẫu có chiều dài k

 Thủ tục con generate_template_rule_set (k): Phát sinh tập các luật mẫu có

chiều dài thuộc tính vế trái là k.

 Thủ tục generate_subset (t): Phát sinh các tập con  và  t

 Thủ tục find_sp (x): Tìm độ hỗ trợ của tập x

 Thủ tục replace_Left (TRk, x): Thay thế tập thuộc tính vế trái của luật

mẫu TRk thành tập thuộc tính x

 Thủ tục replace_Right (TRk, x): Thay thế tập thuộc tính vế phải của luật

mẫu TRk thành tập thuộc tính x

Ví dụ: Ta có tập phổ biến: {A, B}  n = 2. support (A) =2, support (B) =3,

minconf=50%, D = 4, support (A, B) = 2. Khi đó, tiến trình tìm và phát sinh luật kết

hợp như sau:

Bước 1: Phát sinh tập luật mẫu với n = 2

TRS1 = {

{{1}, {2}, 1}, // {1}  {2} có chiều dài vế trái là 1

{{2}, {1}, 1}

}

Bước 2: Tìm và phát sinh luật kết hợp dựa trên tập luật mẫu TRS1

Tập phổ biến F2 = { (A, B), 2})

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

t = {AB}:

VT t  VT = A

Sp (A) =2

Conf = sp (AB)/sp (A) = 2/2 =1 > 0. 5

rk = replace_Left ({{1}, {2}, 1}, {A}) = {{A}, {2}, 1}

rk = replace_Right ({{A}, {2}, 1}, {B}) = {{A}, {B}, 1}

Rk = Rk  {rk, sp, conf} = {{A}, {B}, 1}, 2, 1}

VT t  VT= B

Sp (B) =2

Conf = sp (AB)/sp (A) = 2/3 = 0. 67 > 0. 5

rk = replace_Left ({{1}, {2}, 1}, {B}) = {{B}, {2}, 1}

rk = replace_Right ({{B}, {2}, 1}, {A}) = {{B}, {A}, 1}

Rk = Rk  {rk, sp, conf} = {

{{A}, {B}, 1}, 2, 1},

{{B}, {A}, 1}, 2, 0. 67}

}

Tóm lại, tập luật thỏa điều kiện là:

Rk = {

{{A}, {B}, 1}, 2, 1},

{{B}, {A}, 1}, 2, 0. 67}

}

2. 2. 6. Rút ngọn luật kết hợp

Trong quá trình phát sinh luật kết hợp, có một số dạng luật có thể được rút

gọn lại cho tối ưu và giúp luật kết hợp có ý nghĩa hơn. Đề tài đề xuất 2 cách rút gọn

dựa trên hai tiêu chí:

 Những luật có cùng thuộc tính vế trái và có tần suất thuộc cùng một miền

nào đó (miền này do người dùng tự định nghĩa) sẽ được thu gọn lại thành

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

một. Ví dụ có 2 luật A B có độ tin cậy từ 80%  100% . A C có độ

tin cậy từ 80%  100% . Sau khi rút gọn ta được: A  B, C có độ tin cậy

từ 80%  100%

 Những luật có cùng thuộc tính vế phải và có tần suất thuộc cùng một

miền nào đó (miền này do người dùng tự định nghĩa) sẽ được thu gọn lại

thành một. Ví dụ có 2 luật A B có độ tin cậy từ 80%  100% ; C B

có độ tin cậy từ 80%  100% . Sau khi rút gọn ta được: A hoặc C B có

độ tin cậy từ 80%  100%.

2. 2. 6. 1. Thuật toán rút gọn vế phải

For all x in Ri

VP = x. RHS

For all y in Ri

If y. LHS=x. LHS AND x<>y AND x. tan_suat= y. tan_suat

VP = VP + y. RHS

End if

end for

ROk = ROk{x. LHS, VP, tan_suat}

end for

Answer = k{ROk}

2. 2. 6. 2. Thuật toán rút gọn vế trái

For all x in Ri

VT = x. LHS

For all y in Ri

If y. RHS = x. RHS AND x<>y AND x. tan_suat=y. tan_suat

VT = VT + y. LHS

End if

end for

ROk = ROk {VT, x. RHS, tan_suat}

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

end for

Answer = k{ROk}

Với LHS, RHS: là vế trái và vế phải; Ri: Tập các luật có chiều dài i; ROk:

Tập luật tối ưu của các luật có chiều dài k

2. 2. 6. 3. Ví dụ áp dụng K-way join

Input: Cơ sở dữ liệu D, minsup =3

TID Item

1 A

2 A, B

3 A, B, C

4 A, B, C, D

5 A, B, C, D, E

6 A, B, C, D, E, F

Bảng 2. 3: Cơ sở dữ liệu ban đầu D

Output: Các tập phổ biến Fi;

Bước 1: Đưa dữ liệu về dạng cột. Tên cơ sở dữ liệu mới là D

Bảng 2. 4: Cơ sở dữ liệu sau khi chuyển đổi

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Bước 2: Tối ưu 2 vòng lặp đầu tiên: Tính F1, F2

Tính F1:

SELECT m. item a1, COUNT (DISTINCT m. tid)sp INTO F1

FROM D m

GROUP BY m. item

HAVING COUNT (DISTINCT m. tid)> 2

Kết quả F1:

a1 sp

A 6

B 5

C 4

D 3

Bảng 2. 5: Kết quả F1

Tính F2:

SELECT t1. item a1, t2. item a2, count (*) sp INTO F2

FROM D T1, D T2

WHERE T1. tid = T2. tid and T1. item < T2. item

GROUP BY T1. item, T2. item

HAVING COUNT (*) > 2

Kết quả F2:

A1 a2 sp

A B 5

A C 4

B C 4

A D 3

B D 3

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

C D 3

Bảng 2. 6: Kết quả F2

Bước 3: Tính sẵn C3, Comb3, F3

Tính C3:

SELECT x1. a1 a1, x1. a2 a2, x2. a2 a3 INTO C3

FROM F2 x1, F2 x2, F2 x3

WHERE x1. a1 = x2. a1 AND

x1. a2 < x2. a2 AND

x1. a2 = x3. a1 AND

x2. a2 = x3. a2

a1 a2 a3

A B C

A B D

A C D

B C D

Bảng 2. 7: Kết quả C3

Tính Comb3:

SELECT T1. tid, T1. item a1, T2. item a2, T3. item a3 INTO Comb3

FROM D T1, D T2, D T3, C3

WHERE T1. item = C3. a1 AND

T2. item = C3. a2 AND

T3. item = C3. a3 AND

T1. tid = T2. tid AND

T2. tid = T3. tid

Tid a1 a2 a3

3 A B C

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

4 A B C

D 4 A B

D 4 A C

D 4 B C

C 5 A B

D 5 A B

D 5 A C

D 5 B C

C 6 A B

D 6 A B

D 6 A C

D 6 B C

Bảng 2. 8: Kết quả Comb3

Tính F3:

SELECT a1, a2, a3, count (*) sp INTO F3

FROM Comb3

GROUP BY a1, a2, a3

HAVING COUNT (*) minsup

sp a1 a3 a2

4 A C B

3 A B D

3 A C D

3 B C D

Bảng 2. 9: Kết quả F3

Bước 4: Ck, Combk, Fk với k ≥ 4; level_ct = 3; f_ct = count (F2) =4 //Số mẩu

tin trong F2. Trong khi f_ct = 4 >0 nên level_ct = level_ct +1 =3 +1 =4 và phát sinh

tập ứng viên C4 như sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

SELECT x1. a1 a1, x1. a2 a2, x1. a3 a3, x2. a3 a4 INTO C4

FROM F3 x1, F3 x2, F3 x3, F3 x4

WHERE x1. a1 = x2. a1 AND

x1. a2 = x2. a2 AND

x1. a3 < x2. a3 AND

x1. a2 = x3. a1 AND

x1. a3 = x3. a2 AND

x2. a3 = x3. a3 AND

x1. a1 = x4. a1 AND

x1. a3 = x4. a2 AND

x2. a3 = x4. a3

a1 a2 A B a3 a4 C D

Bảng 2. 10: Kết quả C4

c_ct = count (C4) =1 // Số mẩu tin trong C4. Do c_ct =1 >0 nên ta tính Comb4

và phát sinh F4 như sau:

Comb4:

SELECT T1. tid, T1. a1 a1, T1. a2 a2, T1. a3 a3, T2. item a4

INTO Comb4

FROM C4, Comb3 T1, D T2

WHERE T1. a1 = C4. a1 AND

T1. a2 = C4. a2 AND

T1. a3 = C4. a3 AND

T2. item = C4. a4 AND

T1. tid = T2. tid

tid a1 a2 a3 a4

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

4 A B C D

5 A B C D

6 A B C D

Bảng 2. 11: Kết quả Comb4

Phát sinh F4:

SELECT a1, a2, a3, a4, COUNT (*) sp INTO F4

FROM Comb4

GROUP BY a1, a2, a3, a4

HAVING COUNT (*)  3

a1 a2 a3 a4 sp

A B C D 3

Bảng 2. 12: Kết quả F4

f_ct = count (F4)= 1 >0. Giảm f_ct đi 1: f_ct = f_ct -1 = 1 – 1 =0  vòng lặp

dừng. Kết luận: Các tập phổ biến tìm được thoả mãn đề bài:

Bảng 2. 13. Kết quả

2. 3. Kết luận chương

Chương 2 nghiên cứ u, so sánh, đánh giá về sự tối ưu của thuật toán K-way

join trong áp dụng tìm tập phổ biến. Dựa vào các kết quả thời gian thực thi của thuật

toán được lọc trích từ [14, 15], luận văn đã phân tích và đưa ra các điểm tối ưu của

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thuật toán K-way join cải tiến, từ đó áp dụng thuật toán K-way join cải tiến này để

làm cơ sở trong tính toán thử nghiệm ở chương 3. Chương 2 cũng có đề xuất việc

phát sinh luật kết hợp dựa trên tập luật mẫu, tập phổ biến, các cách rút gọn luật kết

hợp.

Ở chương 3, đề tài sẽ tiến hành tính toán thử nghiệm với thuật toán K-way

join cải tiến đã được viết ở chương 2. Cơ sở dữ liệu sử dụng là các đơn thuốc về

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

một bệnh cúm của phòng khám đa khoa Trường Cao đẳng Y tế Phú Thọ.

CHƯƠNG 3

ỨNG DỤNG TRONG TÍNH TOÁN THỬ NGHIỆM

Ở chương này, luận văn đưa ra 3 bài toán trong đó bài toán 1 là tìm ra tất cả

các luật kết hợp từ cơ sở dữ liệu ban đầu theo độ hỗ trợ và độ tin cậy cho trước.

Như chúng ta đã biết công việc đưa ra tất cả các luật thì đã có rất nhiều nên bài toán

mà luận văn quan tâm đó là hai bài toán tìm độ hỗ trợ và tin cậy của luật, bài toán

đánh giá độ tin cậy của luật theo ngưỡng. Giải quyết các bài toán này giúp cho các

nhà quản lý vấn đề muốn biết, muốn kiểm nghiệm một luật bất kỳ họ đưa ra dạng X

Y thì có tin cậy hay không và độ tin cậy bao nhiêu? Từ đó áp dụng vào cơ sở dữ

liệu đơn thuốc được tổng hợp từ phòng khám đa khoa Trường Cao đẳng Y tế Phú

Thọ để đưa ra được các tri thức quan trọng, hữu ích, giúp cho việc học tập của học

sinh sinh viên được tốt hơn. Trong ứng dụng thử nghiệm, đề tài mới chỉ tổng hợp

các đơn thuốc về bệnh cúm, trong tương lai sẽ cố gắng xây dựng ứng dụng hoàn

thiện hơn, tổng hợp được nhiều loại bệnh hơn nữa nhằm có thể làm ứng dụng thực

tế được.

3. 1. Các bài toán

3. 1. 1. Bài toán tìm luật kết hợp dạng X Y

Từ cơ sở giao dịch N đã có, từ N ta xác định được tập các thuộc tính I={I1,

I2, …, In} và các giao dịch T. Xác định tất cả các luật kết hợp thỏa mãn ngưỡng α,

β cho trước.

Input: I, N, α, β

Output: Tất cả các luật kết hợp dạng XY

Để giải bài toán này chúng ta tiến hành theo các bước như sau:

- Bước 1: Tìm tất cả các tập con của của tập I, ký hiệu là P(I) (nếu I có m

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

thuộc tính ta sẽ có 2m tập con)

- Bước 2: Với mỗi tập con của P(I) gọi là X ta tính s(X), nếu s(X)≥α thì X là

tập FI được lấy.

- Bước 3: Các tập FI gồm: X1, X2, …, Xv với v ≤ 2m

- Bước 4: Từ các tập hợp FI mới tìm ra ta xét

C(X1X2)

C(X1X3)

C(X1X4)

…

C(X1Xv)

C(X2X3)

C(X2X4)

…

C(X2Xv)

…

C(X2X1)

…

C(Xv-1Xv)

Tìm ra luật kết hợp có độ tin cậy không nhỏ hơn β.

3. 1. 2. Bài toán tìm độ hỗ trợ và độ tin cậy của luật

Từ cơ sở giao dịch D đã có, từ D ta xác định được tập các thuộc tính I={I1,

I2, …, In} và các giao dịch T. Xác định một luật bất kỳ XY là có độ hỗ trợ và độ

tin cậy bao nhiêu?

Ta có thể xác định đầu vào và đầu ra của bài toán như sau:

Input: I, D, XY

Output: s(XY) và p(XY)

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Ý tưởng giải bài toán:

- Các thuộc tính tham gia vào một luật XY có là thuộc tính của D

hay không?

- Tính độ hỗ trợ của tập X, tập Y, tập chứa cả X và Y sau đó tính độ

tin cậy s( XY).

Để giải bài toán này chúng ta tiến hành theo các bước như sau:

- Bước 1: Kiểm tra các thuộc tính của tập X và các thuộc tính của

tập YI hay không?

Nếu đúng sang bước 2

Ngược lại, luật XY là KHÔNG TIN CẬY

- Bước 2: Duyệt D để tính s(X), s(Y), s(XY) = s(XY) và tính

c(XY)= s(X Y)/ s(X)

- Bước 3: Trả kết quả s(XY) và c(XY)

Người bác sĩ hay một học sinh đang học dược lý…. họ cần biết một luật bất

kỳ XY là có tin cậy hay không? Để giải quyết vấn đề này người quản trị mạng

cần đưa ra một ngưỡng độ hỗ trợ và ngưỡng độ tin cậy α và β. Dựa trên 2 độ đo α

và β cùng với sự tính toán độ tin cậy và độ hỗ trợ của luật. Để từ đó kết luận một

luật có đáng tin cậy hay không? Bài toán tiếp theo sẽ giúp giải quyết vấn đề trên.

3. 1. 3. Bài toán đánh giá độ tin cậy của luật theo ngưỡng

Từ cơ sở giao dịch D đã có, từ D ta xác định được tập các thuộc tính I={I1,

I2, …, In} và các giao dịch T. Cho trước ngưỡng độ tin cậy β và ngưỡng độ hỗ trợ

α. Xác định một luật bất kỳ XY là có tin cậy hay không?

Ta có thể xác định đầu vào và đầu ra của bài toán như sau:

Input: I, D, α, β, XY

Output: Luật XY là TIN CẬY hoặc KHÔNG TIN CẬY

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Ý tưởng giải bài toán:

- Các thuộc tính tham gia vào một luật XY có là thuộc tính của D

hay không?

- Tính độ hỗ trợ của tập X, tập Y, tập chứa cả X và Y so với ngưỡng α

biết trước.

- Tính độ tin cậy s( XY) so với ngưỡng β biết trước.

Để giải bài toán này chúng ta tiến hành theo các bước như sau:

- Bước 1: Kiểm tra các thuộc tính của tập X và Y I

Nếu đúng sang bước 2

Ngược lại, XY là KHÔNG TIN CẬY

- Bước 2: Duyệt D để tính s(X), s(Y)

- Bước 3: Kiểm tra s(X) ≥ α và s(Y) ≥ α

Nếu là đúng sang bước 4

Ngược lại, kết luận luật XY là KHÔNG TIN CẬY

- Bước 4: Duyệt D để tính s(XY)

- Bước 5: Kiểm tra nếu và s(XY) ≥ α

Nếu là đúng sang bước 6

Ngược lại, kết luận luật XY là KHÔNG TIN CẬY

- Bước 6: Duyệt D để tính c(XY)

- Bước 7: Kiểm tra c(XY) ≥ β

Nếu là đúng, kết luận luật XY là TIN CẬY

Nếu sai, kết luận luật XY là KHÔNG TIN CẬY

3. 1. 5. Giải pháp giúp thực hiện các bài toán

3. 1. 5. 1. Chọn cấu trúc bảng dữ liệu

Do số item trong một giao tác không thể biết trước và có thể khác nhau nên

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

cấu trúc bảng dạng D (tid, item1, item2, …, itemn) là không thực tế. Ngoài ra, trong

thực tế, số item tối đa trong một giao tác có thể vượt quá số cột mà Hệ quản trị

CSDL hỗ trợ. Chẳng hạn đối với SQL 2000/2005, số cột tối đa cho phép trong một

bảng là 1024. Trong trường hợp này, cấu trúc bảng có dạng D (tid, item1, item2, …,

itemn) là không khả thi vì n phải nhỏ hơn 1024. Ngoài ra, nếu lưu trữ bảng có nhiều

cột, thì rất có thể sẽ lãng phí bộ nhớ khi mà số item trong các giao tác khác nhau

quá nhiều. Do đó, để không phụ thuộc vào số item trong một giao tác, không phụ

thuộc vào giới hạn cột trong một bảng của Hệ quản trị CSDL, và để tiết kiệm bộ

nhớ, cấu trúc dữ liệu đề xuất cho việc khai thác có dạng D (Tid, List of Items).

Ví dụ:

Tid Danh sách các Items

1 Cefalecin, Paracetamol, AlphaChymotrypcin, Vitamin C, Vitamin B1

2 Cefalecin, Codacmin, Alpha Chymotrypcin, Vitamin C, Vitamin B1

3 Ameflu, Clorpheniramin, Vitamin C

4 Ameflu, Pamin, Cảm xuyên hương

Bảng 3. 1. Cấu trúc bảng dữ liệu ban đầu

Để thuận lợi trong quá trình cài đặt công việc khai thác dữ liệu tôi chuyển

đổi cấu trúc bảng dữ liệu ban đầu dạng D (Tid, List of Items) về bảng có cấu trúc

dạng D (Tid, Item).

Tid Item

1 Cefalecin

1 Paracetamol

1 AlphaChymotrypcin

1 Vitamin C

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

1 Vitamin B1

Cefalecin 2

Codacmin 2

Alpha Chymotrypcin 2

Vitamin C 2

Vitamin B1 2

Ameflu 3

Clorpheniramin 3

Vitamin C 3

Ameflu 4

Pamin 4

Cảm xuyên hương 4

Bảng 3. 2. Cấu trúc bảng dùng để khai phá dữ liệu

3. 1. 5. 2. Giảm kích thước đầu vào

Khi chúng ta xét độ tin cậy hoặc tính độ tin cậy của một luật thì trước chúng

ta phải tính độ hỗ trợ (hay độ thường xuyên của luật đó) và phải xét độ hộ trợ cho

từng thuộc tính. Để giảm thời gian duyệt trong mỗi lần thực hiện các bài toán được

đưa ra phía trên ta sẽ thực hiện giảm kích thước của bảng dữ liệu đầu vào.

Câu lệnh SQL sau đây giúp việc giảm kích thước bảng khaithac_bandau

(Tid, item)

SELECT *

FROM khaithac_bandau

GROUP BY item

HAVING COUNT (*) >= α

3. 2. Chương trình thử nghiệm

Trường Cao đẳng Y tế Phú Thọ là một trường đào tạo về y học, các học viên

đều sẽ phải trải qua các môn học về thuốc. Chương trình thử nghiệm này nhằm ứng

dụng các bài toán 2, bài toán 3, bài toán 4 vào CSDL được thu thập trong thực tế từ

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

đơn thuốc của phòng khám đa khoa trường Cao đẳng Y tế Phú Thọ về một loại bệnh

cúm. Kết quả này sẽ giúp ích cho các em học sinh sinh viên trong quá trình học

dược lý, tiến tới có thể xây dựng một chương trình lớn bao gồm nhiều tri thức về

thuốc và bệnh hơn nữa để áp dụng trong thực tiễn việc dạy và học dược lý.

Chương trình được cài đặt bằng Microsoft Visual Basic 6. 0, chạy trên máy

tính PC CPU Intel (R) Pentium (R), bộ nhớ trong 2GB RAM, sử dụng hệ điều hành

Windows XP Professional. Các thuật toán được thử nghiệm với dữ liệu khoảng 100

đơn thuốc về bệnh cúm lấy tại phòng khám đa khoa Trường Cao đẳng Y tế Phú

Thọ, đó là các đơn thuốc của phòng khám qua quá trình khám chữa bệnh từ năm

2014 cho đến nay.

Hình 3. 1. Mẫu đơn thuốc của Phòng khám đa khoa Trường cao đẳng Y Phú Thọ

3. 2. 1. Cơ sở dữ liệu của bài toán

Cấu trúc dữ liệu ban đầu được nhập vào bảng khaithac_bandau (Tid, Items) trong

đó:

 Tid: kiểu số nhập mã giao dịch

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

 Items: kiểu chuỗi ghi các mặt hàng trong mỗi lần giao dịch

Hình 3. 2. Minh họa cấu trúc dữ liệu ban đầu

Cấu trúc dữ liệu sau khi chuyển đổi được lưu vào bảng data_daxuly (Tid, Item)

trong đó:

 Tid: kiểu số nhập mã giao dịch

 Item: kiểu chuỗi ghi một mặt hàng trong mỗi lần giao dịch

Hình 3. 3. Cấu trúc dữ liệu dùng để khai phá

Với dữ liệu như trên, chương trình thiết kế mỗi một bài toán được viết riêng thành

một thủ tục, ta chạy bài toán nào chương trình sẽ gọi thủ tục đó.

3. 2. 2. Kết quả khai phá dữ liệu khi thực hiện các bài toán

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

 Bài toán tìm độ hỗ trợ và độ tin cậy của luật:

Chương trình sẽ gọi thủ tục dbo. doluat_sc, các ký tự X Y nhập vào được gán thành

các biến mh1, mh2. Sau đó chương trình chạy 2 vòng lặp cho mh1, mh2 để đếm số

lần lặp của mh1, mh2 trong bảng data_daxuly. Độ hỗ trợ và độ tin cậy được tính

như sau:

Độ hỗ trợ: Số lần lặp của X và Y/ Số các đơn thuốc

Độ tin cậy: Số lần lặp của X và Y/ Số lần lặp X

Code thử nghiệm bài toán tính độ hỗ trợ và độ tin cậy của luật:

set ANSI_NULLS ON

set QUOTED_IDENTIFIER ON

ALTER function [dbo]. [sc_11](@string1 nvarchar(100), @string2 nvarchar(100))

returns @temptable table(mh1 nvarchar(50), mh2 nvarchar(50), supp real, conf real

)

BEGIN

declare @hienthi1 nvarchar(100)

declare @hienthi2 nvarchar(100)

declare @s real

declare @c real

declare @t1 real

declare @t2 real

declare @t3 real

declare @t10 real

Set @hienthi1='{'+''+@string1+''+'}'+'=>'

Set @hienthi2='{'+''+@string2+''+'}'

select @t1=count(*) from dbo. transaction2

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

select @t2=count(distinct magd) from data_daxuly2 where

mh=ltrim(rtrim(@string1))

select @t10=supp from bang_2mh2 where (mathang1=ltrim(rtrim(@string1)) and

mathang2=ltrim(rtrim(@string2)))

if NOT exiStS(select*from data_daxuly2 where mh=ltrim(rtrim(@string1)))

OR NOT exiStS(select*from data_daxuly2 where mh=ltrim(rtrim(@string2)))

BEGIN

Set @s=0--@t10/@t1

Set @c=0--@t10/@t2

Insert into @temptable(MH1, MH2, supp, conf)

values (@hienthi1, @hienthi2, @s, @c)

end

ELSE

begin

if @t10>0 or @t10=0

begin

set @s=@t10/@t1

Set @c=@t10/@t2

end

else

begin

Set @s=0

Set @c=0

end

Insert into @temptable(mh1, mh2, supp, conf)

values (@hienthi1, @hienthi2, @s, @c)

end

Return

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

END

Màn hình kết quả thử nghiệm tính độ hỗ trợ và độ tin cậy của luật:

Hình 3. 4. Tính độ hỗ trợ và độ tin cậy của luật {Cefalecin} => {Paracetamol}

Hình 3. 5. Tính độ hỗ trợ và độ tin cậy của một luật {Decolgen}=>{Vitamin C}

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

 Bài toán đánh giá độ tin cậy của luật theo ngưỡng

Bài toán này sử dụng cách tính độ hỗ trợ và độ tin cậy của luật giống như

bên trên vừa trình bày, sau khi có kết quả sẽ so sánh với độ hỗ trợ, độ tin cậy mà

nhà quản lý, người sử dụng đưa ra để đánh giá. Nếu độ hỗ trợ, độ tin cậy mà lớn

hơn giá trị nhà quản lý, người sử dụng đưa ra thì đánh giá là “Không tin cậy”.

Ngược lại, nếu nhỏ hơn thì sẽ đánh giá là “Tin cậy”.

Code thử nghiệm bài toán đánh giá độ tin cậy của luật theo ngưỡng:

set ANSI_NULLS ON

set QUOTED_IDENTIFIER ON

ALTER function [dbo]. [DGKQ_11](@string1 nvarchar(100), @string2

nvarchar(100), @sp real, @cf real)

returns @temptable table(mh1 nvarchar(50), mh2 nvarchar(50), supp real, conf real

, danhgia nvarchar(100) )

BEGIN

declare @hienthi1 nvarchar(100)

declare @hienthi2 nvarchar(100)

declare @s real

declare @c real

declare @D nvarchar(100)

declare @t1 real

declare @t2 real

declare @t3 real

declare @t10 real

Set @hienthi1='{'+''+@string1+''+'}'+'=>'

Set @hienthi2='{'+''+@string2+''+'}'

select @t1=count(*) from dbo. transaction2

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

select @t2=count(distinct magd) from data_daxuly2 where

mh=ltrim(rtrim(@string1))

select @t3=count(distinct magd) from data_daxuly2 where

mh=ltrim(rtrim(@string2))

select @t10=supp from bang_2mh2 where (mathang1=ltrim(rtrim(@string1)) and

mathang2=ltrim(rtrim(@string2)))

if NOT exiStS(select*from data_daxuly2 where mh=ltrim(rtrim(@string1)))

OR NOT exiStS(select*from data_daxuly2 where mh=ltrim(rtrim(@string2)))

BEGIN

Set @s=0--@t10/@t1

Set @c=0--@t10/@t2

Set @D='TRONG LUAT CHUA MAT HANG KHONG TON TAI TRONG CSDL

Insert into @temptable(MH1, MH2, supp, conf, danhgia)

values (@hienthi1, @hienthi2, @s, @c, @D)

end

ELSE

begin

if @t10>0 or @t10=0

if (@t10/@t1)<@sp or (@t3/@t1)<@sp or (@t2/@t1)<@sp

begin

set @s=@t10/@t1

Set @c=@t10/@t2

Set @D='KHONG TIN CAY'

end

else

if @t10/@t2>@cf

begin

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Set @s=@t10/@t1

Set @c=@t10/@t2

Set @D='TIN CAY'

end

else

begin

Set @s=@t10/@t1

Set @c=@t10/@t2

Set @D='KHONG TIN CAY'

end

else

begin

Set @s=0

Set @c=0

Set @D='KHONG TIN CAY'

end

Insert into @temptable(mh1, mh2, supp, conf, danhgia)

values (@hienthi1, @hienthi2, @s, @c, @D)

end

Return

END

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Màn hình thử nghiệm đánh giá độ tin cậy của luật theo ngưỡng:

Hình 3.6. Đánh giá độ tin cậy của luật {Decolgen}=>{Vitamin B1}

Hình 3.7. Đánh giá độ tin cậy của luật {Cefalecin}=>{Vitamin C}

3. 3. Kết luận chương

Ở chương 3, luận văn đã đưa ra cụ thể các bài toán về tính độ hỗ trợ, tính độ

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

tin cậy của luật và đánh giá một luật có tin cậy hay không. Các bài toán được minh

họa và chạy thử nghiệm qua phần mềm được viết từ Microsoft Visual Basic 6. 0,

chạy trên máy tính PC CPU Intel (R) Pentium (R), bộ nhớ trong 2GB RAM, sử

dụng hệ điều hành Windows XP Professional. Cơ sở dữ liệu là hàng trăm đơn thuốc

của phòng khám đa khoa Trường Cao đẳng Y tế Phú Thọ về bệnh cúm từ năm 2014

đến nay. Kết quả này sẽ giúp ích cho sinh viên y dược trong quá trình học tập và các

bác sĩ, dược sĩ có được những tri thức hay về thuốc, giúp ích cho công việc hàng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

ngày.

KẾT LUẬN

Kết quả đạt được của luận văn

Về mặt lý thuyết: Đề tài đã tìm hiểu những cách tiếp cận khai thác dữ liệu

dựa trên ngôn ngữ truy vấn SQL-92 và chú trọng vào cách tiếp cận K-way join. Đề

phân tích, thử nghiệm, đánh giá và đề xuất cải tiến cho K-way join, đưa ra phương

pháp phát sinh và rút gọn luật kết hợp.

Về mặt thực hành: Đề tài đã đưa ra phương án, cách thức để tìm ra những tri

thức tốt về thuốc với cơ sở dữ liệu là các đơn thuốc.

Kết luận: Khai phá dữ liệu đã và đang là một lĩnh vực rất thu hút các nhà

nghiên cứu vì tính khoa học và ứng dụng của nó trong cuộc sống. Những thử thách

trong lĩnh vực khai phá còn rất nhiều, khai phá tri thức theo kiểu luật kết hợp cũng

còn cả một khối khổng lồ, đặc biệt là cách tiếp cận khai phá dữ liệu dựa trên truy

vấn SQL.

Hướng phát triển luận văn

 Mở rộng thuật toán sang HQTCSDL quan hệ-đối tượng (sử dụng các đặc

tính quan hệ-đối tượng trong SQL như: UDFs, BLOBs, Table functions)

 Đưa ràng buộc vào khai phá dữ liệu

 Mở rộng sang khai phá mẫu phổ biến chuỗi (sequential partern mining).

Vì đây là lĩnh vực có phạm vi ứng dụng rất rộng và hiện tại có rất ít nghiên

cứu chuyên sâu về SQL để khai phá loại dữ liệu này.

 Với những luật có độ tin cậy nhỏ hơn 100%, vấn đề luật thừa cũng cần

phải được xem lại. Lấy ví dụ, chúng ta đã có luật AB như vậy luật (A,

C)  B là luật thừa. Nhưng trong thực tế thì (A, C)  B phần lớn có độ

tin cậy cao hơn, và chính những luật có độ tin cậy cao là những luật chúng

ta cần quan tâm và tin tưởng hơn. Những luật mà vế trái càng nhiều items

thì càng quí, cũng giống như công việc điều tra mà có càng nhiều chứng

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

cứ càng tốt.

PHỤ LỤC

Luận văn sử dụng ngôn ngữ lập trình Microsoft Visual Basic 6. 0, hệ quản trị

cơ sở dữ liệu SQL Sever 2005 để tính toán thử nghiệm với dữ liệu là các đơn thuốc

cúm của phòng khám đa khoa Trường cao đẳng Y tế Phú Thọ.

Dữ liệu đầu vào: Tập các đơn thuốc bệnh cúm

Hình PL1: Minh họa dữ liệu đầu vào

Chương trình:

Giao diện chính:

Private Sub mnubaitoan2_Click() baitoan2. Show End Sub Private Sub mnubaitoan3_Click() baitoan3. Show End Sub Private Sub mnubaitoan4_Click() baitoan4. Show End Sub Private Sub mnuketnoidulie_Click() Dim str As String Set myCn = New Connection str = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn. Open str MsgBox "Ket noi thanh cong!!!", vbOKOnly, "Thong bao" End Sub

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Private Sub cmscluat_Click() Dim str1 As String Set myCn1 = New Connection str1 = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn1. Open str1 Dim sqlstr1 As String Dim rs As ADODB. Recordset sqlstr1 = "select * from dbo. doluat_sc('" & txtstr1. Text & "', '" & txtstr2. Text & "')" 'myCn. Execute (sqlstr) 'ket noi Set rs = New ADODB. Recordset rs. Open sqlstr1, myCn1, adOpenStatic, adLockOptimistic Call HienKQLenGrid1(rs) rs. Close MsgBox "Da do luat!!!" End Sub Private Sub Cmthemgd_Click() Dim str1 As String Set myCn1 = New Connection 'myCn. CursorLocation = adUseClient str1 = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn1. Open str1 Dim sqlstr As String Dim rsmathang As New Recordset sqlstr = "exec dbo. themgiaodich '" & txtdsmathang. Text & "'" rsmathang. Open sqlstr, myCn1, adOpenStatic, adLockOptimistic 'MsgBox "Them thanh cong!!!" Call hienthidsmh End Sub Private Sub Cmxulydata_Click() Dim str1 As String Set myCn1 = New Connection 'myCn. CursorLocation = adUseClient str1 = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn1. Open str1 Dim sqlstr As String sqlstr = "exec dbo. taodata_daxuly3" myCn1. Execute (sqlstr) MsgBox "Xu ly du lieu xong!!!" End Sub Private Sub HienKQLenGrid1(rs As ADODB. Recordset) Dim i As Integer 'load du lieu len grid

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Tính độ hỗ trợ và tin cậy của luật:

grdketqua1. Rows = 2 If (rs. EOF = False) Then i = 0 While (Not rs. EOF) i = i + 1 If (i >= grdketqua1. Rows - 1) Then grdketqua1. Rows = grdketqua1. Rows + 1 grdketqua1. TextMatrix(i, 0) = i End If grdketqua1. TextMatrix(i, 1) = rs!mh1 grdketqua1. TextMatrix(i, 2) = rs!mh2 grdketqua1. TextMatrix(i, 3) = rs!supp grdketqua1. TextMatrix(i, 4) = rs!conf rs. MoveNext Wend End If 'danh so thu tu cho cac cot Dim stt As Integer grdketqua1. Col = 0 For stt = 1 To grdketqua1. Rows - 2 grdketqua1. Row = stt grdketqua1. Text = stt Next stt End Sub Private Sub KtGird() grdketqua1. Clear grdketqua1. Rows = 2 grdketqua1. TextMatrix(0, 0) = "STT" grdketqua1. TextMatrix(0, 1) = "Mat hang 1" grdketqua1. TextMatrix(0, 2) = "Mat hang 2" grdketqua1. TextMatrix(0, 3) = "Supp" grdketqua1. TextMatrix(0, 4) = "Conf" grdketqua1. ColWidth(0) = 500 grdketqua1. ColWidth(1) = 2000 grdketqua1. ColWidth(2) = 2000 grdketqua1. ColWidth(3) = 1000 grdketqua1. ColWidth(4) = 1000 End Sub Public Sub KhoiTaoGird_2() grdthemgd. Clear grdthemgd. Rows = 2 grdthemgd. TextMatrix(0, 0) = "Stt" grdthemgd. TextMatrix(0, 1) = "ID" grdthemgd. TextMatrix(0, 2) = "Magd" grdthemgd. TextMatrix(0, 3) = "Mathang" grdthemgd. ColWidth(0) = 500

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

grdthemgd. ColWidth(1) = 500 grdthemgd. ColWidth(2) = 600 grdthemgd. ColWidth(3) = 5000 End Sub Private Sub Command1_Click() Unload Me End Sub Private Sub Form_Load() Dim str1 As String Set myCn1 = New Connection str1 = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn1. Open str1 baitoan2. Show Call KtGird Call KhoiTaoGird_2 Call hienthidsmh End Sub Public Sub hienthidsmh() Dim i, ii As Integer Dim sqlstr2 As String Dim rs1 As ADODB. Recordset Dim str As String Set myCn = New Connection str = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn. Open str i = 1 ii = 0 sqlstr2 = "select * from transaction2" Set rs1 = New ADODB. Recordset grdthemgd. Rows = 1 rs1. Open sqlstr2, myCn, adOpenDynamic, adLockBatchOptimistic With rs1 If (Not (. BOF And . EOF)) Then Do Until rs1. EOF grdthemgd. AddItem "" grdthemgd. TextMatrix(i, 0) = "" & ii + 1 grdthemgd. TextMatrix(i, 1) = Trim(. Fields(0). Value) grdthemgd. TextMatrix(i, 2) = "" & Trim(. Fields(1). Value) grdthemgd. TextMatrix(i, 3) = "" & Trim(. Fields(2). Value) ' grdthemgd. TextMatrix(i, 4) = "" & Trim(. Fields(3). Value) ii = ii + 1 i = i + 1 . MoveNext Loop . MoveFirst Else Exit Sub

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

End If End With End Sub

Option Explicit 'Dim WithEvents rsKhoa As Recordset Dim myCn As Connection Dim rsmathang As New Recordset Dim sqlstr As String Private Sub cmkiemtraluat_Click() Dim str As String Set myCn = New Connection str = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn. Open str Dim sqlstr As String Dim rs As ADODB. Recordset sqlstr = "select * from dbo. doluat_dg('" & txtstring1. Text & "', '" & txtstring2. Text & "', " & txtminsup. Text & ", " & txtmincof. Text & ")" 'myCn. Execute (sqlstr) 'ket noi Set rs = New ADODB. Recordset rs. Open sqlstr, myCn, adOpenStatic, adLockOptimistic Call HienKQLenGrid(rs) rs. Close MsgBox "Da kiem tra luat!!!" End Sub Private Sub Cmthemgd_Click() Dim str As String Set myCn = New Connection 'myCn. CursorLocation = adUseClient str = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn. Open str Dim sqlstr As String Dim rsmathang As New Recordset sqlstr = "exec dbo. themgiaodich '" & Me. txtdsmathang & "'" rsmathang. Open sqlstr, myCn, adOpenStatic, adLockOptimistic MsgBox "Them thanh cong!!!" Call hienthidsmh 'myCn. Execute (sqlstr) End Sub

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Đánh giá độ tin cậy của luật:

Private Sub Cmxulydata_Click() Dim str As String Set myCn = New Connection 'myCn. CursorLocation = adUseClient str = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn. Open str Dim sqlstr As String sqlstr = "exec dbo. taodata_daxuly3" myCn. Execute (sqlstr) MsgBox "Xu ly du lieu xong!!!" End Sub Private Sub HienKQLenGrid(rs As ADODB. Recordset) Dim i As Integer 'load du lieu len grid grdketqua. Rows = 2 If (rs. EOF = False) Then i = 0 While (Not rs. EOF) i = i + 1 If (i >= grdketqua. Rows - 1) Then grdketqua. Rows = grdketqua. Rows + 1 grdketqua. TextMatrix(i, 0) = i End If grdketqua. TextMatrix(i, 1) = rs!mh1 grdketqua. TextMatrix(i, 2) = rs!mh2 grdketqua. TextMatrix(i, 3) = rs!danhgia rs. MoveNext Wend End If 'danh so thu tu cho cac cot Dim stt As Integer grdketqua. Col = 0 For stt = 1 To grdketqua. Rows - 2 grdketqua. Row = stt grdketqua. Text = stt Next stt End Sub Private Sub Form_Load() 'frmketqua. Show Call KhoiTaoGird Call KhoiTaoGird_2 Call hienthidsmh End Sub Private Sub KhoiTaoGird()

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

grdketqua. Clear grdketqua. Rows = 2 grdketqua. TextMatrix(0, 0) = "STT" grdketqua. TextMatrix(0, 1) = "Mat hang 1" grdketqua. TextMatrix(0, 2) = "Mat hang 2" grdketqua. TextMatrix(0, 3) = "Danh gia" grdketqua. ColWidth(0) = 500 grdketqua. ColWidth(1) = 2000 grdketqua. ColWidth(2) = 2000 grdketqua. ColWidth(3) = 5000 End Sub Public Sub KhoiTaoGird_2() grdthemgd. Clear grdthemgd. Rows = 2 grdthemgd. TextMatrix(0, 0) = "Stt" grdthemgd. TextMatrix(0, 1) = "ID" grdthemgd. TextMatrix(0, 2) = "Magd" grdthemgd. TextMatrix(0, 3) = "Mathang" grdthemgd. ColWidth(0) = 500 grdthemgd. ColWidth(1) = 500 grdthemgd. ColWidth(2) = 600 grdthemgd. ColWidth(3) = 5000 End Sub Public Sub hienthidsmh() Dim i, ii As Integer Dim sqlstr2 As String Dim rs1 As ADODB. Recordset Dim str As String Set myCn = New Connection str = "Provider=SQLOLEDB. 1;User ID=" & mUser & ";Password=" & mPwd & _ ";Initial Catalog=" & mData & ";Data Source=" & mDataSource & "" myCn. Open str i = 1 ii = 0 sqlstr2 = "select * from transaction2" Set rs1 = New ADODB. Recordset grdthemgd. Rows = 1 rs1. Open sqlstr2, myCn, adOpenDynamic, adLockBatchOptimistic With rs1 If (Not (. BOF And . EOF)) Then Do Until rs1. EOF grdthemgd. AddItem "" grdthemgd. TextMatrix(i, 0) = "" & ii + 1 grdthemgd. TextMatrix(i, 1) = Trim(. Fields(0). Value) grdthemgd. TextMatrix(i, 2) = "" & Trim(. Fields(1). Value) grdthemgd. TextMatrix(i, 3) = "" & Trim(. Fields(2). Value) ' grdthemgd. TextMatrix(i, 4) = "" & Trim(. Fields(3). Value) ii = ii + 1 i = i + 1

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

. MoveNext Loop . MoveFirst Else Exit Sub End If End With End Sub Private Sub Text1_Change() End Sub Private Sub thoat_Click() Unload Me End Sub

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1]. Trương Ngọc Châu - Phan Văn Dũng (2002), “Nghiên cứu tính ứng

dụng của khai phá luật kết hợp trong cơ sở dữ liệu giao dịch”, Trường

đại học Bách khoa, Đại học Đà Nẵng.

[2]. Nguyễn Thanh Thủy, Khai phá dữ liệu – Kỹ thuật và ứng dụng, Hà nội

2001.

[3]. Nguyễn Huy Đức (2003), “Khai phá luật kết hợp trong cơ sở dữ liệu

lớn”, Kỷ yếu Hội thảo khoa học Quốc gia lần thứ nhất về nghiên cứu cơ

bản và ứng dụng CNTT, Hà Nội, 10/2003, tr. 128-136.

[4]. Đỗ Thái Hòa, “Tổ chức khai phá dữ liệu dựa trên ngôn ngữ truy vấn, áp

dụng vào bán hàng”. Luận văn Thạc sĩ công nghệ thông tin, Đại học Đà

Nẵng, 2009.

[5]. Vũ Đức Thi, Nguyễn Huy Đức (2008), “Thuật toán hiệu quả khai phá

tập mục thường xuyên cổ phần cao”, Kỷ yếu Hội thảo Một số vấn đề

chọn lọc về CNTT và TT, Huế, 12/2008, tr. 431-444.

[6]. Nguyễn Huy Đức (2010), “Khai phá tập mục cổ phần cao và lợi ích cao

trong cơ sở dữ liệu”. Luận án Tiến sĩ toán học, Viện khoa học và công

nghệ Việt Nam.

Tiếng Anh

[7]. Agrawal.R and Shim.K (1995), Developing tightly-couple Data mining

Applications on a Relational Database system. IBM Almaden Research

Center: San Jose, California.

[8]. Jiawei Han and Micheline Kamber: Data mining – Concepts and

Techniques, 1999.

[9]. Mehmed Kantardzic: Data mining – Concepts, Models, Methods, and

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Algorithms.

[10]. Meo. R, Psaila. G and Ceri. S (1996), A New SQL-like Operator for

Mining Association Rules. Proceedings of the 22nd VLDB Conference,

Mumbai, India.

[11]. Ye Nong: The hand book of data mining, 2003.

[12]. Pratyush Mishra, S.Chakravarthy, Peformance Evaluation and Analysis

of SQL based Approaches for Association Rule Mining, 2003.

[13]. Pratyush Mishra, S.Chakravarthy, Evaluation of K-way Join and its

variants for Association Rule Mining, Year book BNCOD, 2002.

[14]. Erwin A., Gopalan R.P & Achuthan N.R. (2007), “CTU-Mine: An Efficient

High Utility Itemset Mining Algorithm Using the Pattern Growth Approach”,

Paper presented at the IEEE 7th International Conferences on Computer and

Information Technology, Aizu Wakamatsu, Japan.

[15]. Cai C.H., Chee Fu A.W, Cheng C.H., and Kwong (2005), “Mining

Association Rules with Weighted Items”, Proceedings of the Sixth

International Conference on Intelligent Data Engineering and Automated

Learning (IDEAL 2005).

[16]. Rakesh Agrawal, Ramakrishnan Srikant, “Fast Algorithms for Mining

Số hóa bởi Trung tâm Học liệu – ĐHTN

http://www.lrc.tnu.edu.vn

Association Rules”, 1993.