BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
TRẦN THỊ THU HIỀN
KHAI PHÁ DỮ LIỆU TRONG MÔ HÌNH
DỮ LIỆU DẠNG KHỐI
LUẬN VĂN THẠC SĨ MÁY TÍNH
HÀ NỘI, 2014
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
em hoàn thành khóa học sau đại học.
Do thời gian và kiến thức có hạn nên luận văn chắc chắn không tránh khỏi những
thiếu sót nhất định. Em rất mong nhận được những sự góp ý quý báu của thầy cô và
các bạn.
Vĩnh Phúc, ngày 15 tháng 12 năm 2014.
Học viên Trần Thị Thu Hiền
2
LỜI CAM ĐOAN
Trong quá trình hoàn thành luận văn, tôi đã tìm hiểu, nghiên cứu, tổng hợp từ
nhiều nguồn tài liệu khác nhau, dưới sự chỉ đạo, giúp đỡ của giáo viên hướng dẫn,
kết quả của đề tài là sản phẩm lao động của cá nhân tôi. Các nguồn tài liệu sử dụng
được trích dẫn rõ ràng, khoa học.
Nội dung luận văn này chưa từng được công bố hay xuất bản dưới bất kỳ hình
thức nào và cũng không được sao chép từ bất kỳ một công trình nghiên cứu nào.
Tôi xin cam đoan những điều trên là hoàn toàn đúng.
Vĩnh Phúc, ngày 15 tháng 12 năm 2014
Học viên
1.2.2. Các hướng tiếp cận của bài toán phân cụm dữ liệu 20
Kết luận chương 1 38
CHƯƠNG 2: MÔ HÌNH DỮ LIỆU DẠNG KHỐI VÀ KHAI PHÁ DỮ LIỆU
TRÊN KHỐI BẰNG KỸ THUẬT PHÂN CỤM 39
2.1. Mô hình dữ liệu dạng khối 39
2.1.1. Khối, lược đồ khối 39
2.1.2. Lát cắt 40
4
2.1.3. Đại số quan hệ trên khối 41
2.1.4. Phụ thuộc hàm 45
2.1.5. Khoá của lược đồ khối R đối với tập phụ thuộc hàm F trên R 47
2.2. Khai phá dữ liệu trên khối bằng kỹ thuật phân cụm 48
2.2.1. Tính chất của kỹ thuật phân cụm 48
2.2.2. Thuật toán K-mean trên khối 50
Kết luận chương 2 52
CHƯƠNG 3: PHÂN CỤM KẾT QUẢ HỌC TẬP TẠI TRƯỜNG CAO ĐĂNG
NGHỀ CƠ KHÍ NÔNG NGHIỆP 53
3.1. Giới thiệu Trường Cao đẳng nghề Cơ khí nông nghiệp 53
3.1.1. Cơ cấu tổ chức 55
3.1.2. Yêu cầu xây dựng CSDL: 56
3.1.3. Phạm vi thực hiện 57
3.2. Công cụ xử lý dữ liệu IBM SPSS 58
3.2.1. Giới thiệu chung 58
3.2.2. Công cụ SPSS 59
3.3. Phân cụm dữ liệu với công cụ SPSS 62
3.3.1. Thao tác phân cụm 62
3.3.2. Thống kê mô tả đối tượng 64
3.4. Phân cụm dữ liệu học sinh trường Cao đẳng nghề cơ khí nông nghiệp 65
3.4.1. Xây dựng cơ sở dữ liệu 65
là một mở rộng của mô hình dữ liệu quan hệ.
Đã có một số công trình nghiên cứu về mô hình dữ liệu dạng khối này. Tuy
nhiên việc khai phá dữ liệu trong mô hình dạng khối vẫn còn khá mới mẻ. Chính
vì những lý do trên mà tôi đã chọn đề tài: “Khai phá dữ liệu trong mô hình dữ liệu
dạng khối".
6
2. Mục đích nghiên cứu
Trên cơ sở nghiên cứu khai phá dữ liệu trong mô hình dữ liệu dạng khối sử
dụng thuật toán K-means trong kỹ thuật phân cụm.
3. Nhiệm vụ nghiên cứu
1. Tìm hiểu về khai phá dữ liệu và kỹ thuật phân cụm trong khai phá dữ liệu.
2. Tìm hiểu về mô hình dữ liệu dạng khối.
3. Nghiên cứu thuật toán K-means trên khối bằng kỹ thuật phân cụm.
4. Đối tượng và phạm vi nghiên cứu
Các vấn đề về khai phá dữ liệu, kỹ thuật phân cụm, thuật toán về kỹ thuật phân
cụm trên mô hình dữ liệu dạng khối.
5. Phương pháp nghiên cứu
Trong quá trình triển khai đề tài, tôi sử dụng chủ yếu các phương pháp: Thu
thập tài liệu, phân tích,suy luận, tổng hợp, đánh giá.
6. Những đóng góp của đề tài
1. Tìm hiểu về khai phá dữ liệu, các kỹ thuật khai phá dữ liệu nói chung và kỹ
thuật khai phá dữ liệu bằng phân cụm nói riêng.
2. Chứng minh các tính chất của khai phá dữ liệu bằng phân cụm trên mô hình
khối.
3. Sử dụng kỹ thuật khai phá dữ liệu ứng dụng vào một khối dữ liệu trong mô
hình dữ liệu dạng khối bằng cách đề ra một thuật toán mới đó là thuật toán K-means
trên khối dựa trên thuật toán K-means đã có trên mô hình quan hệ.
Hình 1.10: Phân cụm một tập các điểm bằng CURE
Hình 1.11: Mật độ tiến và mật độ liên kết trong phân cụm dựa trên mật độ
Hình 1.12: Sắp xếp cụm trong OPTICS
Hình 2.1: Biểu diễn khối điểm học sinh DHS(R)
Hình 3.1: Sơ đồ tổ chức trường CĐN Cơ khí nông nghiệp
Hình 3.2: Màn hình quản lý dữ liệu của SPSS
Hình 3.3: Màn hình khai báo tên trường sử dụng trong SPSS
Hình 3.4: Màn hình hiển thị kết quả
Hình 3.5: Màn hình tính toán dữ liệu dựa trên các biến
Hình 3.6: Thao tác phân cụm k-means
Hình 3.7: Chọn tên trường và số cụm cần phân chia
Hình 3.8: Thống kê theo số lượng phân cụm cụ thể
Hình 3.9. Biểu diễn thông tin học sinh theo mô hình khối
Hình 3.10: Kết quả trung bình của học sinh khi tham gia phân cụm
Hình 3.11: Kết quả phân cụm cả năm
Hình 3.12: Kết quả phân cụm cả năm theo vùng miền
Hình 3.13: Kết quả phân cụm theo hoàn cảnh gia đình cả năm
Hình 3.14: Phân cụm cả năm theo dân tộc
Hình 3.15: Kết quả phân cụm cả năm theo giới tính
9
DANH MỤC CÁC BẢNG
Bảng 3.1: Các chiều phân tích theo chủ đề
Bảng 3.2: Bảng xây dựng CSDL học sinh
Bảng 3.3: Kết quả phân cụm và số lượng cụ thể từng cụm
Bảng 3.4: Khoảng cách giữa các cụm của lát cắt học kỳ I
Bảng 3.5: Khoảng cách giữa các cụm của lát cắt học kỳ II
Bảng 3.6: Bảng kết quả phân cụm cả năm
Định nghĩa của Ferruzza: “Khai phá dữ liệu là tập hợp các phương pháp được
dùng trong tiến trình khám phá tri thức để chỉ ra sự khác biệt các mối quan hệ và các
mẫu chưa biết bên trong dữ liệu”.
Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định,
trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong CSDL lớn”.
Định nghĩa của Fayyad: “ Khai phá tri thức là một quá trình không tầm thường
nhận ra những mẫu dữ liệu có giá trị, mới, hữu ích, tiềm năng và có thể hiểu được”.
1.1.2. Quá trình khám phá tri thức
Quá trình khai phá tri thức được tiến hành qua 6 giai đoạn [6]. Bắt đầu của quá
trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có
vẻ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn gặp phải rất nhiều
vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình
1. Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ
liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm
chí các dữ liệu từ các nguồn ứng dụng Web.
11
2. Trích lọc dữ liệu: Ở giai đoạn này dữ liệu được lựa chọn hoặc phân chia theo
một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những em học
sinh có điểm trung bình học kỳ lớn hơn 8.0 và có giới tính là nữ
Hình 1.1: Quá trình khám phá tri thức
3. Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là giai
đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình
khám phá tri thức. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không
đủ chặt chẽ, logic. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả
năng kết nối dữ liệu. Ví dụ, tuổi = 256. Giai đoạn này sẽ tiến hành xử lý những dạng
dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được xem như thông tin dư
Hình 1.2: Tập dữ liệu với 2 lớp: có và không có khả năng trả nợ
13
1.1.3.1. Khai phá dữ liệu dự đoán
Nhiệm vụ của khai phá dữ liệu dự đoán là đưa ra các dự đoán dựa vào các suy
diễn trên dữ liệu hiện thời. Nó sử dụng các biến hay các trường trong cơ sở dữ liệu
để dự đoán các giá trị không biết hay các giá trị tương lai. Bao gồm các kĩ thuật: phân
loại, hồi quy
a. Phân loại
Mục tiêu của phương pháp phân loại dữ liệu là dự đoán nhãn lớp cho các mẫu
dữ liệu. Quá trình phân loại dữ liệu thường gồm 2 bước: Xây dựng mô hình và sử
dụng mô hình để phân loại dữ liệu.
1. Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước. Mỗi
mẫu thuộc về một lớp, được xác định bởi một thuộc tính gọi là thuộc tính lớp. Các
mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện. Các nhãn lớp của tập dữ liệu
huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp
này còn được gọi là học có giám sát.
2. Sử dụng mô hình để phân loại dữ liệu. Trước hết chúng ta phải tính độ chính
xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để
dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Hình 1.3 cho thấy sự
phân loại của các dữ liệu vay nợ vào trong hai miền lớp. Ngân hàng có thể sử dụng
các miền phân loại để tự động quyết định liệu những người vay nợ trong tương lai có
nên cho vay hay không.
loại học sinh, nhận dạng mẫu, phân loại trang Web…
Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho
các thuật toán khai phá dữ liệu khác.
15
Hình 1. 4 cho thấy sự phân cụm tập dữ liệu điểm học sinh vào trong 3 cụm: lưu
ý rằng các cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn một
cụm.
Hình 1. 4: Phân cụm tập dữ liệu kết quả học tập vào trong 3 cụm
b. Luật kết hợp
Phương pháp phát hiện các luật kết hợp (Association Rules) nhằm phát hiện ra
các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu [5]. Các giải thuật
Tìm luật liên kết tìm kiếm các mối liên kết giữa các phần tử dữ liệu, ví dụ như nhóm
các món hàng thường được mua kèm với nhau trong siêu thị. Đầu ra của thuật toán
là tập luật kết hợp tìm được. Cho trước một tập các giao tác, trong đó mỗi giao tác là
một tập các mục, tìm sự tương quan giữa các mục như là một luật và kết quả của giải
thuật khai phá dữ liệu là tập luật kết hợp tìm được. Luật kết hợp thường có dạng X
=> Y. Trong đó:
X là tiền đề, Y là hệ quả (X, Y là hai tập của mục). Ý nghĩa trực quan của luật
là các giao tác của cơ sở dữ liệu mà trong đó nội dung X có khuynh hướng đến nội
dung Y.
Có hai thông số quan trọng của luật kết hợp là độ hỗ trợ (support) và độ tin cậy
(confidence). Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật.
Chúng tương ứng phản ánh sự hữu ích và sự chắc chắn của luật đã khám phá. Khai
16
chất của từng lĩnh vực, việc vận dụng khai phá dữ liệu có những cách tiếp cận khác
nhau.
Ngân hàng: Xây dựng mô hình dự báo rủi ro tín dụng. Tìm kiếm tri thức, quy
luật của thị trường chứng khoán và đầu tư bất động sản.
Thương mại điện tử: Tìm hiểu, định hướng thúc đẩy, giao tiếp với khách hàng.
Phân tích hành vi mua sắm trên mạng và cho biết thông tin tiếp thị phù hợp với nhiều
loại khách hàng.
Marketing: Phân tích nhu cầu khách hàng dựa trên mẫu dữ liệu mua bán hàng
từ đó xác định chiến lược kinh doanh, quảng cáo, kế hoạch sản xuất, …
Khai phá dữ liệu cũng được vận dụng hiệu quả để giải quyết các bài toán phức
tạp trong các ngành đòi hỏi kỹ thuật cao [9], như tìm kiếm mỏ dầu từ ảnh viễn thám,
cảnh báo hỏng hóc trong các hệ thống sản xuất, … Các kỹ thuật Khai phá dữ liệu đã
được áp dụng thành công trong việc dự đoán tải sử dụng điện năng cho các công ty
cung cấp điện, lưu lượng viễn thông cho các công ty điện thoại, mức độ tiêu thụ sản
phẩm cho các nhà sản xuất, giá trị của sản phẩm trên thị trường cho các công ty tài
chính, …
Ngoài ra, Khai phá dữ liệu còn được áp dụng cho các vấn đề xã hội như phân
tích các kết quả phòng chống và điều trị một số loại bệnh, phân tích tác hại của ma
tuý, phát hiện tội phạm hay tăng cường an ninh xã hội, Việc vận dụng thành công
đã mang lại những hiệu quả thiết thực cho các hoạt động diễn ra hàng ngày trong đời
sống.
18
1.1.4.2. Một số khó khăn trong khai phá dữ liệu
- Cơ sở dữ liệu lớn: Các tập dữ liệu cần xử lý trong khai phá dữ liệu thường có
kích thước cực kỳ lớn về cả số lượng các bản ghi và số lượng các thuộc tính. Trong
thực tế, kích thước của các tập dữ liệu trong khai phá dữ liệu thường ở mức tera-byte
Cho x làm một tập dữ liệu: X = { x
1
, x
2
, …. , x
n
} . Ta định nghĩa m-phân cụm
của X như một sự phân chia X thành m tập (cụm) C
1
, C
2
, …. , C
m
sao cho thỏa mãn 3
điều kiện:
Hình 1.6: Gom cụm
Phân cụm dữ liệu là một kỹ thuật trong Data mining nhằm tìm kiếm, phát hiện
các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để
từ đó cung cấp thông tin, tri thức cho việc ra quyết định.
Phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm
dữ liệu sao cho các đối tượng trong một cụm "tương tự" với nhau và các đối tượng
trong các cụm khác nhau sẽ "không tương tự" với nhau. Số các cụm dữ liệu được
phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động
xác định. 20
mpE
Trong đó, x là một điểm, m
i
là giá trị trung bình của cụm C
i.
Thuật toán k-means bao gồm các bước cơ bản sau:
21
Hình 1.7: Sơ đồ khối k-means
Thuật toán k-means chi tiết như sau:
Input: Số cụm k và các trọng tâm cụm
k
jj
m
1
t
ijj
t
i
cxcxxS
for all i
*
= 1, …. , k.
Bước 3: Cập nhật lại trọng tâm cụm m
j
bằng cách xác định trung bình cộng của
vector đối tượng dữ liệu.
Kết thúc
-
+
Bắt đầu
Số cụm k
Trọng tâm
Khoảng cách các
đối tượng đến các
trọng tâm
Nhóm các đối
tượng vào các cụm
Không có
đối tượng
chuyển
nhóm
22
với việc tìm các cụm có hình dáng không lồi hay các cụm có kích thước khác xa nhau.
Hơn nữa, nó nhạy cảm với các điểm dữ liệu nhiễu và điểm giới hạn, một số lượng
nhỏ dữ liệu như vậy về căn bản có ảnh hưởng tới giá trị trung bình.
Ví dụ: Giả sử ta có 4 loại thuốc A,B,C,D, mỗi loại thuộc được biểu diễn bởi 2
đặc trưng X và Y như sau. Mục đích của ta là nhóm các thuốc đã cho vào 2 nhóm
(K=2) dựa vào các đặc trưng của chúng.
Đối tượng
Thuộc tính 1 (X)
Thuộc tính 2 (Y)
A
1
1
B
2
1
C
4
3
D
5
4
23
Bước 1: Khởi tạo
Copyright: Tài liệu đại học ©