HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
MAI THỊ THANH NGA ỨNG DỤNG LUẬT KẾT HỢP ĐỂ PHÂN TÍCH,
ĐÁNH GIÁ CÁC BẢNG BIỂU VỀ ĐIỀU TRA DÂN SỐ Chuyên ngành:

Khoa học máy tính
Mã số:

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

HÀ NỘI - 2013
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG


hợp dữ liệu lớn (databases, data warehouses, data
repositories) mang tính lịch sử. Những công cụ khai phá
dữ liệu có thể dự đoán những xu hướng trong tương lai và
do đó cho phép doanh nghiệp ra những quyết định kịp thời
được định hướng bởi tri thức mà khai phá dữ liệu đem lại.
Sự phân tích dữ liệu một cách tự động và mang tính dự
báo có ưu thế hơn hẳn so với sự phân tích thông thường
dựa trên những sự kiện trong quá khứ của các hệ hỗ trợ ra
quyết định (decision support systems - DSSs) truyền thống
trước đây. Công cụ khai phá dữ liệu cũng có thể trả lời
những câu hỏi trong lĩnh vực kinh doanh mà trước đây
được xem là tốn nhiều thời gian để xử lý. Giờ đây, khai
phá dữ liệu đã và đang trở thành một trong những hướng
nghiên cứu chính của lĩnh vực khoa học máy tính và công
nghệ tri thức.
2

Các kết quả điều tra về dân số giữa các vùng miền
thì số liệu điều tra ngày một nhiều. Việc ứng dụng Công
nghệ thông tin (CNTT) cụ thể là ứng dụng các luật trong
khai phá dữ liệu (luật kết hợp) vào phân tích, đánh giá số
liệu đã được điều tra là một chủ trương cần thiết, quan
trọng. Sự nghiệp công nghiệp hóa, hiện đại hóa ngày càng
sâu rộng và nhất là sự bùng nổ của thông tin toàn cầu…
đang đặt ra những yêu cầu mới, đòi hỏi công tác điều tra
phải dựa trên việc ứng dụng các thành tựu của CNTT.
2. Mục đích nghiên cứu
- Khái phá luật kết hợp trong lĩnh vực khai phá dữ liệu
- Ứng dụng luật kết hợp vào việc phân tích, đánh giá
kết quả của các bảng biểu điều tra dân số về trình độ

liệu. Tri thức thể hiện tư duy của con người về một vấn đề.
Khai phá tri thức từ cơ sở dữ liệu (KDD): Là quy
trình bao gồm nhiều công
đoạn như: xác định vấn đề, tập hợp và chọn lọc dữ liệu,
khai thác dữ liệu, đánh giá kết quả, giải thích dữ liệu, áp
dụng tri thức vào thực tế.
Tại sao phải DM?
Bởi vì dữ liệu được thu thập hàng ngày là rất lớn:
Từ các cơ sở dữ liệu khổng lồ, từ Internet. Theo các báo
4

cáo của IBM, chỉ có 80% dữ liệu được khai thác, 20% còn
lại ẩn trong các cơ sở dữ liệu là những tri thức quý giá.
Khai phá dữ liệu (DM): Là một bước trong quy
trình khám phá tri thức, nhằm:
 Rút trích thông tin hữu ích, chưa biết, tiềm ẩn
trong khối dữ liệu lớn
 Phân tích dữ liệu bán tự động
 Giải thích dữ liệu trên các tập dữ liệu lớn
1.3. Quá trình khai phá dữ liệu
1.4. Các kỹ thuật khai phá dữ liệu
1.5. Các bài toán thông dụng trong khai phá dữ liệu
1.6. Các cơ sở dữ liệu phục vụ khai phá dữ liệu
1.7. Các ứng dụng của khai phá dữ liệu
1.8. Khai phá dữ liệu và các lĩnh vực liên quan
1.9. Các thách thức trong khai phá dữ liệu
1.10. Kết luận chương
Trên cơ sở các lý thuyết đưa ra ở trên chúng ta hiểu
thêm rằng DM là sự vận dụng học thuật vào các vấn đề
thiết thực đang diễn ra. Là tiến trình khái quát các sự kiện

chứng khoán, tài chính và đầu tư,
- Ví dụ về AR:
 Confidence (Bia => Nem chua) = 60%
Luật này có nghĩa: 60% khách hàng mua bia thì
mua Nem chua.
6

 Confidence(Thu nhập = 80.000.000_max =>
Tài khoản tiết kiệm=yes) = 100%
Luật này có nghĩa: Nếu thu nhập lớn hơn hoặc bằng 80
triệu một tháng thì khách hàng có tài khoản tiết kiệm với
độ tin cậy là 100%.
Từ các AR được trích rút từ chính các cơ sở dữ
liệu giao dịch, cơ sở dữ liệu khách hàng mà các siêu thị,
các ngân hàng sẽ có chiến lược kinh doanh (sắp xếp các
mặt hàng, số lượng các mặt hàng, ), chiến lược tiếp thị,
quảng cáo,… để từ đó thúc đẩy hoạt động kinh doanh của
mình.
2.2.2. Các khái niệm cơ bản
- Định nghĩa độ hỗ trợ
Định nghĩa 2.1:
Gọi T(X) là tập giao dịch chứa tập mục X

I.
Độ hỗ trợ của tập mục X

I, ký hiệu Sup(X) là tỷ số giữa
số các giao dịch chứa X trên số tất các giao dịch.
Hay Sup(X) =
T

Định nghĩa 2.3: Độ hỗ trợ (support) của luật kết hợp
XY, ký hiệu Sup(X  Y) là tỷ số giữa số lượng các
giao dịch chứa cả X và Y (
Y
X

) trên tổng số các giao
dịch có trong cơ sở dữ liệu.
Hay
T
YXT
YXSup
)(
)(


Định nghĩa 2.4: Độ tin cậy (confidence) của luật X=>Y,
ký hiệu conf(X  Y) là tỷ số giữa số lượng các giao dịch
chứa cả X và Y (
Y
X

) trên số giao dịch có chứa X.

)(
)(
)(
XT
YXT
YXConf

ngưỡng của độ hỗ trợ và độ tin cậy do người sử dụng xác
định trước. Các ngưỡng của độ hỗ trợ và độ tin cậy được
ký hiệu là minsup và minconf.
Định nghĩa 2.5: Cho một tập mục X  I và một ngưỡng
hỗ trợ tối thiểu minsup (được cho bởi người sử dụng). Tập
mục X gọi là một tập mục phổ biến (Frequent Itemset hay
Large Itemset) với độ hỗ trợ tối thiểu minsup khi và chỉ khi
sup(X)

minsup.
- Một vài tính chất liên quan đến tập phổ biến
Tính chất 2.1:
Nếu X  Y, X, Y là các tập mục thì sup(X) ≥ sup(Y) vì tất
cả các giao dịch của D chứa Y thì cũng chứa X.
Tính chất 2.2:
Một tập mục X mà sup(X) < minsup thì mọi tập cha Y của
X sẽ thỏa mãn sup(Y) ≤ sup(X) < minsup.
Tính chất 2.3:
9

Nếu tập mục X là một tập mục phổ biến trên D, nghĩa là
sup(X) ≥ minsup thì mọi tập con Y của X đều là tập phổ
biến trên D vì sup(Y) ≥ sup(X) ≥ minsup.
- Một số tính chất liên quan đến luật kết hợp
Tính chất 2.4: (Không hợp luật kết hợp)
Nếu có X

Z và Y

Z trong D thì không nhất thiết


Y và Y

Z, chúng ta không thể suy ra X

Z.
Tính chất 2.7:
Nếu luật X

(L - X) không thỏa mãn độ tin cậy tối thiểu
thì không có luật nào trong các luật Y

(L – Y) có độ tin
cậy tối thiểu, trong đó Y  X; X,Y  L.
2.2.3. Khai phá luật kết hợp
Phát biểu bài toán:
Đầu vào: - Cho một tập mục I = {i
1
, i
2,
, i
n
}
- Một tập m giao dịch T
- Độ hỗ trợ tối thiểu minsup và độ tin cậy tối
thiểu mincof
10

Đầu ra: - Tập các luật kết hợp X


Tìm các tập X  I mà Sup(X) ≥ minsup.
Đặt F = { X  I | Sup(X) ≥ minsup}.
D

i
1

i
2

i
n

T
1

0

11

T
2

1

k
gồm các tập có k phần
tử tổ hợp từ F
k-1
có độ phổ biến ≥ minsup; với k = 2, 3, …
cho đến khi không tính được nữa.
Cụ thể thuật toán có 3 pha:
11

Pha 1. Tính F
1
= { i

I: Sup({i}) ≥ minsup}
Pha 2. Repeat { lặp tính F
k
; k= 2, 3, }
F
k
= { X

I: X là hợp của hai tập trong F
k-1

mà |X| = k và Sup(X) ≥ minsup}
Until F
k
=

;

While F
k
≠

do
Begin
k= k+1;
F
k
=

;
X = S
k-1


Y
k-1
; với mọi cặp S
k-1
và Y
k-1
của F
k-1
;
If Sup( X) ≥ minsup and |X| = k then F
k
= F
k


}, các ngưỡng độ hỗ trợ
minsup, độ tin cậy minconf. Tìm tập các luật kết hợp
12

X=> Y; với X, Y  I mà Sup(X) ≥ minsup, Sup(Y) ≥
minsup và conf( X =>Y) ≥ minconf.
Đặt F = { X  I | Sup(X) ≥ minsup};
L = { X => Y | X, Y

F và conf(X=>Y) ≥ minconf}
Giải quyết bài toán 2 bằng hai pha
Pha 1: Tính F theo bài toán 1
Pha 2: Tìm tất cả các luật X => Y mà X, Y

F và
conf(X=>Y) ≥ minconf.
Thực hiện pha 2 bằng phép lặp vét cạn là thử cho
mọi căp X, Y

F: L =

;
For each X, Y

F if X

Y =

and
conf(X=>Y) ≥ minconf then L = L

2.3.3 Thuật toán khai phá luật kết hợp phân tán
2.3.3.1 Thuật toán khai phá AR phân tán nhanh (FDM)
2.3.3.2 Thuật toán khai phá phân tán luật kết hợp (DMAR)
2.4. Kết luận chương
Nội dung của chương trình bày một cách tổng
quan về AR, các định nghĩa, tính chất liên quan đến AR
như độ hỗ trợ, độ tin cậy, tập mục phổ biến và phát biểu
bài toán khai phá AR. Tiếp theo, nội dung chương này
trình bày một số thuật toán cơ bản để phát hiện tập mục
phổ biến và phát hiện AR từ các tập mục phổ biến đó.
Đây chính là cơ sở lý thuyết để từ đó chúng ta đi sâu tìm
hiểu, cài đặt thử nghiệm thuật toán (thuật toán Apriori) sẽ
áp dụng trong chương 3.
14

Chương 3. ỨNG DỤNG VÀ THỬ NGHIỆM LUẬT
KẾT HỢP PHÂN TÍCH, ĐÁNH GIÁ CÁC
BẢNG BIỂU ĐIỀU TRA DÂN SỐ
3.1. Giới thiệu
AR được ứng dụng trong nhiều lĩnh vực khác
nhau của đời sống như: khoa học, hoạt động kinh doanh,
tiếp thị, thương mại, phân tích thị trường chứng khoán,
tài chính và đầu tư, Chương này đưa ra tổng quan về
các bảng biểu của điều tra dân số và ứng dụng AR để
phân tích đánh giá.
3.2. Công tác điều tra dân số
Năm 2009, cuộc Tổng điều tra dân số và nhà ở
được thực hiện theo định số 94/2008/QĐ-TTg ngày 10
tháng 7 năm 2008 của Thủ tướng Chính phủ. Đây là
cuộc tổng điều tra dân số lần thứ tư và điều tra nhà ở lần


năm
1989 và 1999, từ công
tác tuyên truyền cho Tổng điều tra đến chương trình tập
huấn và các quy định nghiệp vụ điều tra. Kết quả là,
Tổng cục Thống kê có khả năng tiến hành tổ chức cuộc
Tổng điều tra dân số và nhà ở năm 2009 với mức tự lực
lớn hơn rất nhiều và với sự giúp đỡ về tài chính và kỹ
thuật từ các tổ chức quốc tế và nước ngoài ít hơn.
Ngay sau khi kết thúc bước điều tra thu thập thông
tin, Thường trực Ban Chỉ đạo Trung ương đã
thự
c
hiện

nhiều biện pháp để đánh giá, thẩm định kết quả.
Một số kết quả điều tra:
16

Biểu 3.1: Phân bố phần trăm diện tích Đất, Dân số và mật độ
Dân số chia theo các vùng kinh tế - xã hội, 2009
Các vùng kinh tế - xã hội
Di
ện tích

(%)
Dân s
ố

(%)

B
ắc Trung Bộ v
à Duyên h
ải miền Trung

29,0

22,0

196

Tây Nguyên

16,5

6,0

93

Đông Nam B
ộ

7,1

16,3

594

Đ
ồng bằng sông Cửu Long


thôn
Toàn

q
u
ố
c

2
3
,7

2
9
,6

3
,
4

0
,
4

Trung du và mi
ền núi phía Bắc

1
3

0
,2

B
ắc Trung Bộ v
à Duyên h
ải miền Trung

1
9
,1

2
4
,1

2
,
7

-
0
,2

Tây Nguyên

2
7
,2



Đ
ồng bằng sông Cửu Long

1
7
,2

2
2
,8

3
,
4

-
0
,1Nguồn: Tổng cục Thống kê, "Tổng điều tra dân số và nhà ở Việt
Nam 2009: Kết quả toàn bộ", NXB Thống kê, 8- 2001.
3.3. Bảng số liệu điều tra dân số

17

Biểu 3.3: Số lượng Dân số, Dân số thành thị, tỷ trọng Dân số
thành thị chia theo các vùng kinh tế - xã hội, 2009
Các vùng kinh tế - xã hội

88

25

3
7
3

29,6

Trung du và mi
ền núi phía Bắc

11

0
64

1

7
7
2

16,0

Đ
ồng bằn
g sông H
ồng


24,1

Tây Nguyên5

1
0
7

1

4
1
9

27,8

Đông Nam B
ộ

1
4
0
25

8



số
Chưa

đi học

Chưa

tốt
nghiệp

ti
ểu học
Tốt
nghiệp

tiểu học

Tốt
nghi
ệp
THCS

Tốt
nghiệp
THPT +
Toàn

q
u

,8

Thành

th
ị

1
0
0
,
0

2
,
6

1
6
,7

2
2
,9

2
0
,4

3


1
3
,8

Các

vùng

k
i
nh

t
ế

-

xã

h
ộ
i:


ồng bằng sông Hồng

1
0
0
,
0

2
,
2

1
5
,8

1
8
,9

3
3
,0

3
0
,1

B
ắc Tr

2
0
,8

1
3
,7

Đông Nam B
ộ

1
0
0
,
0

3
,
1

1
9
,7

2
9
,1

2

,3

1
0
,718

Biểu 3.5: Tỷ trọng Dân số từ 15 tuổi trở lên chia theo trình
độ CMKT, giới tính, thành thị/nông thôn và các vùng kinh tế
- xã hội, 2009
Đơn vị tính: Phần trăm

Giới tính/nơi cư trú/
các vùng kinh tế - xã hội
Tổng

số
Không
có
trình đ
ộ
CMKT

Sơ
cấp
Trung

cấp


4
,
4

Nam

1
0
0
,
0

8
4
,3

3
,
7

5
,
5

1
,
4

5

7

Thành th
ị

1
0
0
,
0

7
4
,6

4
,
4

7
,
6

2
,
5

1
0
,8

ền núi phía Bắc

1
0
0
,
0

8
6
,7

2
,
4

6
,
4

1
,
8

2
,
8

Đ
ồng bằng sông Hồng

ải
miền Trung
100,0

87,8 2,1 4,8 1,7 3,6
Tây Nguyên

1
0
0
,
0

9
0
,2

1
,
9

3
,
8

1
,
3

2

6

Đ
ồng bằng sông Cửu Long

1
0
0
,
0

9
3
,4

1
,
4

2
,
2

0
,
9

2
,
1


Khi chọn menu là Dân số thành thị thì sẽ có giao diện sau:

Hình 3.2. Giao diện Dân số thành thị
Với ngưỡng của độ tin cậy là 50 thì ta có kết quả dân số
thành thị như sau:

Hình 3.3. Giao diện kết quả phân tích, đánh giá Dân số
thành thị giữa các vùng miền với ngưỡng của độ tin cậy
là 50
21

Khi chọn menu là Trình độ học vấn có giao diện như
sau:

Hình 3.4. Giao diện trình độ học vấn
Khi đã thêm mới các Vùng kinh tế - xã hội tương ứng
với các trình độ học vấn và nhấn nút Phân tích, đánh
giá thì chương trình sẽ cho kết quả phân tích, đánh giá
như sau:

Hinh 3.5. Kết quả phân tích, đánh giá trình độ học
vấn giữa các vùng miền
22

Với menu Trình độ CMKT có giao diện như sau:

Hình 3.6. Giao diện trình độ CMKT
Với thông tin đầy đủ về trình độ CMKT giữa các vùng
miền và nhấn nút Phân tích, đánh giá chương trình sẽ

đến mô hình hình thức, các thuật toán khai phá luật kết
hợp cơ sở luật kết hợp.