1HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG PHẠM THỊ THANH MAI
ỨNG DỤNG LUẬT KẾT HỢP TRONG HỖ TRỢ TƯ
VẤN CHỌN CHUYÊN NGÀNH HỌCCHO SINH VIÊN

Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60.48.15

TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2012
2
Vào lúc: giờ ngày tháng năm

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

22

Hướng phát triển tiếp theo của luận văn:

Để quá trình đào tạo theo tín chỉ hoạt động có hiệu quả,
cần xây dựng một hệ thống hoàn chỉnh hỗ trợ cả quá
trình đào tạo (hỗ trợ thêm nhiều chức năng: sắp xếp lịch
học, sinh viên đăng ký môn học, . …)


Hiện nay, dữ liệu được lưu trữ ngày một tăng, để ứng
dụng khai phá dữ liệu vào các bài toán này cần tiếp
tục nghiên cứu các phương pháp xử lý cho bài toán có
dữ liệu lớn. Xem xét, nghiên cứu một số ứng dụng
khác của Khai phá dữ liệu.

3

MỞ ĐẦU

Bước sang thế kỷ 21 chúng ta đang phải đối mặt với sự
gia tăng, bùng nổ của dữ liệu từ mức độ Terabytes đến mức độ

Nhiệm vụ của Khai phá dữ liệu là từ dữ liệu có sẵn tìm ra
những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát
hiện cũng như tìm ra những xu hướng phát triển và các xu hướng
tác động lên chúng. Các kỹ thuật cho phép lấy được tri thức từ cơ
sở dữ liệu được gọi là các kỹ thuật khai phá dữ liệu (DM: Data
Mining). Có rất nhiều kỹ thuật khai phá dữ liệu khác nhau tuân
theo các bước của quá trình phát hiện tri thức.
1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu
1.2.1. Quá trình phát hiện tri thức
Quá trình phát hiện tri thức từ cơ sở dữ liệu bao gồm
năm giai đoạn sau:
1. Hiểu và xác định vấn đề
2. Thu thập và tiền xử lý dữ liệu
3. Khai phá dữ liệu
4. Minh họa, đánh giá tri thức được phát hiện
5. Đưa kết quả vào thực tế
21

KẾT LUẬN

Luận văn “Ứng dụng luật kết hợp trong hỗ trợ tư vấn
chọn chuyên ngành học cho sinh viên” đã trình bày một số
kết quả sau đây:
 Những nghiên cứu về khai phá dữ liệu và ứng dụng
trong nhiều lĩnh vực khác nhau nhằm khai phá nguồn
dữ liệu phong phú được lưu trữ trong các hệ thống
thông tin. Khai phá dữ liệu cũng được áp dụng nhiều
trong việc tư vấn, dự báo, đặc biệt là những ứng dụng
cho tư vấn trong giáo dục.
 Khai phá dữ liệu có rất nhiều hướng tiếp cận (nhiều
Hình 3.6.:Thuật toán tư vấn 3.4. Kết luận chương
Trong chương này đã trình bầy được những thuận lợi và
khó khăn về quá trình đào tạo theo tín chỉ. Hiểu được các bước
tiền xử lý dữ liệu từ nguồn dữ liệu thu thập được. Sử dụng
được phần mềm mã nguồn mở Weka vào việc sinh ra tập luật
kết hợp. Từ đó mô tả một tiến trình tư vấn môn học cho sinh
viên. Giúp sinh viên định hướng được việc học tập, đạt kết quả
tốt trong học tập.
FOR tất cả các luật DO
IF các cặp mamon, loaidiem
trong vế trái của luật i
trùng với cặp
mamon_loaidiem của bangdiem
THEN
Luật i là luật được tư vấn
cho người dùng
END
END

5

Hình trên mô tả 5 giai đoạn trong quá trình phát hiện tri
thức từ cơ sở dữ liệu. Quá trình phát hiện tri thức từ cơ sở dữ
liệu là một quá trình tương tác, lặp đi lặp lại theo chu trình liên
tục kiểu xoáy trôn ốc, trong đó lần lặp sau hoàn chỉnh hơn lần

và chiến lựơc học khác nhau để thực hiện các nhiệm vụ. Khi sử
dụng mạng nơron chúng ta phải phân biệt hai giai đoạn: giai
đoạn mã hoá trong mạng nơron được học trên các mẫu dữ liệu
huấn luyện, thực hiện một nhiệm vụ nào đó và giai đoạn giải
mã trong đó mạng được sử dụng để phân lớp, làm dự báo hoặc
thực hiện bắt cứ nhiệm vụ học nào liên quan.
(4) Thuật toán di truyền: Việc xây dựng các thuật toán
di truyền phỏng sinh học nhằm tìm ra các giải pháp tốt nhất bao
gồm các bước sau:
1. Tạo ra cơ chế mã di truyền dưới dạng các xâu của một
bảng mã kỹ tự hạn chế.
2. Thiết lập môi trường nhân tạo trên máy tính trên đó
các giải pháp có thể tham gia “đấu tranh sinh tồn” với nhau để
xác định độ đo thành công hay thất bại, hay còn được gọi là
“hàm thích nghi”.
3. Phát triển các “phép lai ghép” để các giải pháp kết hợp
với nhau. Khi đó các xâu mã di truyền của giải pháp cha và mẹ
bị cắt đi và xếp lại. Trong quá trình sinh sản như vậy các kiểu
đột biến có thể được áp dụng.
4. Cung cấp một quần thể các giải pháp ban đầu tương đối
đa dạng và để máy tính thực hiện “cuộc chơi tiến hoá” bằng cách
19

3.2. Kiến trúc hệ tư vấn
3.2.1. Kiến trúc chương trình
3.1. Giới thiệu về mô hình đào tạo theo tín chỉ
- Sinh viên chủ động đăng ký môn học
- Sinh viên sẽ tốt nghiệp sau khi hoàn thành 42 tín chỉ đại
cương, 69 tín chỉ chuyên ngành
- Sinh viên dễ dàng chuyển đổi chuyên ngành mà vẫn được
bảo lưu các điểm tương ứng.
- Sinh viên chủ động sắp xếp lịch học của mình sao cho
phù hợp với lực học, tài chính.
- Sinh viên có thể học lại, thi lại các môn với các lớp sau
mà không cần tổ chức thi lại
. 7

loại bỏ các giải pháp từ mỗi cá thể và thay thế chúng bằng các
con cháu hoặc các đột biến của các giải pháp tốt. Thuật toán sẽ
kết thúc khi một họ các giải pháp thành công được sinh ra.
1.4. Ứng dụng khai phá dữ liệu trong giáo dục
Hiện đã có rất nhiều nghiên cứu về ứng dụng khai phá dữ
liệu cho giáo dục. Những khai phá dữ liệu trong giáo dục đã nổi
bật lên như là một lĩnh vực nghiên cứu độc lập trong những
năm gần đây, mà cao điểm là năm 2008 với sự thành lập hội
nghị quốc tế về khai phá dữ liệu giáo dục, và những bài báo về
khai phá dữ liệu giáo. Đó là “Applying Data Mining Techniques
to e-Learning Problems” của Félix Castro1, Alfredo Vellido1,
Àngela Nebot1, và Francisco Mugica3, “Recommendation in

1
, i
2
,…,i
k
} I
được gọi là một tập mục hay một tập k-mục nếu nó chứa k
mục. Một giao tác T được gọi là chứa tập mục X chỉ khi X  T.
Mỗi giao tác là một bộ <TID, I>, I là tập mục.
Độ hỗ trợ (support)
Độ hỗ trợ của một tập mục X trong cơ sở dữ liệu D là tỉ
số giữa số các giao tác T

D có chứa tập X và tổng số giao
tác trong D (hay là phần trăm của các giao tác trong D có
chứa tập mục X), kí hiệu Supp(X). Độ hỗ trợ của luật X

Y là tỉ số của số giao tác có chứa
X

Y và số giao tác trong cơ sở dữ liệu D, kí hiệu:
Supp(X

Y)


|D|

Dữ liệu đầu ra có thể được lưu trong file dạng text
2.6. Kết luận chương
Trong chương 2 này, chúng ta đã tìm hiểu được
các khái niệm cơ bản, các thuật toán khai phá luật kết hợp
và tìm hiểu về một phần mềm mã nguồn mở Weka, cách
sử dụng Weka để sinh ra luật kết hợp - một phần mềm
đang được sử dụng rất phổ biến.
16

End
return = 
k
L
k
;
Thuật toán AprioriHibrid
Thuật toán AprioriHyrid là thuật toán lai của 2 thuật toán
Apriori và AprioriTID; nghĩa là ban đầu sử dụng thuật toán
Apriori, khi 
k
nhỏ vừa đủ bộ nhớ và số phần tử của tập ứng
viên Ck nhỏ hơn C
k-1
thì chuyển sang sử dụng thuật toán
AprioriTID. Điều kiện thứ hai để tránh hiện tượng 
k
đủ vộ
nhớn nhưng 
k+1
không đủ bộ nhớ. Kích thước của 

If (k >m+1) then begin
H
m+1
=Apriori_gen(H
m
);
For all h
m+1
 H
m+1
do begin

Conf = support (l
k
)/support (l
k
-h
m+1
);
If (conf minconf) then
Output the rule (l
k
–h
m+1
)  h
m+1

With confidence =conf and
support=support(l
k

Luật kết hợp
Cho một giao tác, mỗi giao tác là một tập mục, một luật
là một biểu thức có dạng XY, với X, Y là các tập mục, X 
Y = , X  I, Y  I, X được gọi là tiền đề, Y gọi là kết luận
của luật.
Một luật X  Y thoả mãn trên D nếu với một support tối
thiểu minsup và một ngưỡng confidence tối thiểu minconf cho
trước ta phải có:
Support (X

Y)

minsup
Và Confidence (X

Y)

minconf
(X và Y phải là các tập mục thường xuyên trên D)
Tính chất 4 Luật kết hợp không có tính bắc cầu.
Nếu X

Y và Y

Z thoả trên D thì không thể khăng
định X

Z thoả mãn trên D



Nếu luật X

(L-X) không thoả độ tin cậy cực tiểu thì
luật Y

(L-Y) cũng không thoả mãn, với các tập mục Y

X


L.
2.2. Mô tả kho dữ liệu điểm của bài toán
Với cơ sở dữ liệu (CSDL) có được của trên 6.000 sinh
viên và gần 2000 sinh viên đã tốt nghiệp (kể từ khóa 11 đến
khóa 13) (ký hiệu là một CSDL D).
Ta có thể xem cơ sở dữ liệu D là một ma trận trong đó
mỗi dòng thể hiện một giao tác và mỗi cột ứng với một mục
(thuộc tính). Ma trận này có thể trình bày theo 4 cách: Dạng
véc tơ mục ngang, Dạng danh sách mục ngang, Dạng véc tơ
định danh dọc, Danh sách định danh dọc.
Dạng véc tơ mục ngang: HIV (Horizontal Item Vecto)
cơ sở dữ liệu được tổ chức như một tập của các dòng trong đó
mỗi dòng lưu trữ định danh (TID) của giao tác và một vectơ
15

else C
k
= C
k
 {c}; kết tập c

k-1
  ; k++) do
Begin
C
k
= apriori_gen(L
k-1
);
C’
k
= ;
for tất cả t  C’
k-1
do
begin
// xác định tập ứng viên trong C
k

chứa trong giao dịch với định
//danh t. Tid (Transaction Code)
C
t
= c  C
k
| (c-c[k]) 
t.Set_of_ItemSets^(c-c[k-1]
t.Set_of_ItemSets
for những ứng viên c  C
t
do c.count ++;

T
= subset(C
k
, T); //lấy tập con của
T là ứng cử viên trong C
k

for (mỗi một ứng cử viên c

C
T
) do
c.count++; //tăng bộ đếm tần xuất 1
đơn vị
end;
L
k
= {c  C
k
| c.count  minsup}
end;
return 
k
L
k
Hàm apriori-gen
Input: tập mục phổ biến L
k-1
có kích thước k-1


1
[k-
2]=L
2
[k-2])  (L
1
[k-1]=L
2
[k-
1]))
then c = L
1
 L
2
; // kết nối
L
1
với L
2
sinh ra ứng cử viên c
If has_infrequent_subset(c,
L
k-1
)
then
remove (c) // bước tỉa (xoá
ứng cử viên c)
11

nhận giá trị 0 hoặc 1 tuỳ thuộc vào không có mặt hay có mặt

Khi đã thu được các tập mục thường xuyên ở giai đoạn 1,
thuật toán sẽ sinh ra các luật bằng cách:
- Đếm và tính toán độ hỗ trợ Support cho mỗi tập mục
thường xuyên và các tập con (subset) của chúng để tính toán độ
tin cậy confidence.
- Xây dựng luật: Dựa vào tính chất 2.3, ứng với tập
mục thường xuyên, mỗi tập con của nó là tiền đề của một luật,
các mục còn lại được đưa vào kết luận của luật.
- Chọn luật: Tính toán giá trị confidence của mỗi luật
được sinh ra, nếu giá trị này lớn hơn hoặc bằng ngưỡng
minconf thì luật đó sẽ được chọn.
13

Thuật toán phát hiện luật kết hợp từ các tập mục
thường xuyên cơ bản theo các bước như sau:
Dữ liệu vào: I, D, minsup, minconf, L tập các tập mục
thường xuyên.
Dữ liệu ra: Tất cả những luật kết hợp thoả mãn minsup
và minconf
1. Tìm tất cả những mục con không rỗng X của tập mục
thường xuyên l L.
2. Từ các tập mục X  l, tìm các luật có dạng X  (l-X) có
độ hỗ trợ lớn hơn hoặc bằng minsup và độ tin cậy lớn hơn hoặc
bằng minconf
2.4. Các thuật toán cơ bản
2.4.1. Các thuật toán sinh tập mục thường xuyên
a. Thuật toán Apriori
Các kí hiệu:
L
k