Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin
trong các lĩnh vực của đời sống, kinh tế, xã hội trong nhiều năm qua cũng đồng
nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích lũy
nhiều lên. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách
nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng
nhiều thông tin tiềm ẩn phong phú và đa dạng. Mặt khác, trong môi trường cạnh
tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc
ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả
lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các
phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp
ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật
khai phá tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data
Mining). Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri
thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn
(discovery of interesting, implicit, and previously unknown knowledge from large
databases)[5]
Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ
thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa
vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm là phân lớp
nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,
Phân cụmcơ sở dữ liệu là một trong những phương pháp quan trọng trong
quá trình tìm kiếm tri thức. Phân cụm là phương pháp học từ quan sát (learning
from obversation) hay còn gọi là học không thầy (unupervised learning or
automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi ta
không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của
cụm mà chưa biết hoặc biết rất ít về những thông tin đó. Phân cụmđược coi như
một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật
toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong tiếp thị, sử dụng
đất, bảo hiểm, hoạch định thành phố Hiện nay, phân cụm dữ liệu là một hướng
được nghiên cứu rất nhiều trong Tin học. Chính vì lý do đó mà em chọn đề tài
“Nghiên cứu các kỹ thuật phân cụm dữ liệu và Ứng dụng” là hướng nghiên cứu
chính cho luận văn của mình.
2
Nội dung chính của luận văn được trình bày trong 3 chương:
Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong
chương này trình bày tổng quan về khai phátri thức, khai phá dữ liệu; qui trình khai
phá tri thức, khai phá dữ liệu;
Chương 2: Phân cụm và các kỹ thuật phân cụm.Trong chương này trình bày
tổng quan về phân cụm dữ liệu, một số phương pháp phân cụm dữ liệu dữ liệu phổ
biến như phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ,
phân cụm dựa trên lưới; trình bày một sốgiải thuật điển hình của mỗi phương pháp
phân cụm;
Chương 3: Ứng dụng, triển khai bài toán với giải thuật DBSCAN
Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn,
đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. Phần phụ lục trình bày
một số modul chương trình cài đặt bằngthuật toán DBSCAN.
Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi những
hạn chế và thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp ý kiến của các
thầy thầy/ côgiáo cũng như bạn bè và đồng nghiệp.
101 trang |
Chia sẻ: oanhnt | Lượt xem: 1573 | Lượt tải: 3
Bạn đang xem trước 20 trang tài liệu Luận văn Nghiên cứu các kỹ thuật phân cụm dữ liệu và ứng dụng, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
i
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
===================
Nguyễn Thị Huế
NGHIÊN CỨU CÁC KỸ THUẬT PHÂN CỤM DỮ LIỆU
VÀ ỨNG DỤNG
LUẬN VĂN THẠC SỸ
HÀ NỘI - 2011
ii
LỜI CẢM ƠN
Để hoàn thành được luận văn này, trước hết tôi xin gửi lời cảm ơn sâu sắc nhất
tới GS.TS Vũ Đức Thi, Viện trưởng Viện công nghệ thông tin đã tận tình hướng
dẫn, chỉ bảo, định hướng, đóng góp những ý kiến quý báu trong suốt quá trình tôi
thực hiện luận văn.
Tôi xin chân thành cảm ơn các thầy, cô giáo trong Bộ môn Hệ thống thông tin,
Khoa Công nghệ thông tin, Phòng Đào tạo Sau đại học - Nghiên cứu Khoa học,
Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tạo mọi điều kiện tốt nhất
để tôi hoàn thành khóa học này. Đồng thời, tôi cũng xin cảm ơn gia đình, bạn bè,
những người luôn khuyến khích và giúp đỡ tôi trong mọi hoàn cảnh khó khăn. Tôi
xin cảm ơn cơ quan và các đồng nghiệp đã hết sức tạo điều kiện cho tôi trong suốt
quá trình học tập và làm luận văn này.
Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
iii
LỜI CAM ĐOAN
Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm
hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận
văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo
đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày
hoàn chỉnh trong bất cứ tài liệu nào.
Hà Nội, ngày 10 tháng 04 năm 2011
Học viên
Nguyễn Thị Huế
iv
MỤC LỤC
MỞ ĐẦU ................................................................................................................1
Chương 1.................................................................................................................3
TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU ..................3
1.1. Giới thiệu chung ...........................................................................................3
1.2. Khai phá tri thức và quá trình khai phá tri thức .............................................3
1.2.1. Khai phá tri thức ....................................................................................3
1.2.2. Quá trình khai phá tri thức .....................................................................4
1.3. Khai phá dữ liệu ...........................................................................................5
1.3.1. Khai phá dữ liệu.....................................................................................5
1.3.2. Mục tiêu của khai phá dữ liệu ................................................................6
1.3.3. Quá trình khai phá dữ liệu ......................................................................6
1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu..7
1.3.5. Thách thức – khó khăn trong khai phá tri thức và khai phá dữ liệu .......13
1.3.6. Ứng dụng của khai phá dữ liệu.............................................................13
1.3.7. Kết luận ...............................................................................................14
Chương 2. PHÂN CỤM DỮ LIỆU VÀ CÁC THUẬT TOÁN TRONG ...............15
PHÂN CỤM DỮ LIỆU .........................................................................................15
2.1. Giới thiệu....................................................................................................15
2.2. Các ứng dụng của phân cụm .......................................................................16
2.3. Các yêu cầu về thuật toán phân cụm dữ liệu................................................17
2.4. Các kiểu dữ liệu trong phân cụm.................................................................18
2.5. Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu .....................21
2.6. Các hướng tiếp cận của bài toán phân cụm dữ liệu......................................28
2.6.1. Phương pháp phân hoạch (Partitioning Methods) ...........................28
2.6.2. Phương pháp phân cấp (Hierarchical Methods) ..............................36
2.6.3. Phương pháp dựa trên mật độ (Density-Based Methods) ................44
2.6.4. Phương pháp dựa trên lưới (Gird-Based Methods)..........................51
2.6.5. Kết luận ..........................................................................................56
Chương 3: ỨNG DỤNG ........................................................................................58
KẾT LUẬN ...........................................................................................................65
TÀI LIỆU THAM KHẢO .....................................................................................66
PHỤ LỤC..............................................................................................................68
v
DANH MỤC CÁC KÝ HIỆU, TỪ VIẾT TẮT
Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh
Cơ sở dữ liệu CSDL DataBase
Khai phá tri thức trong cơ sở dữ liệu KDD Knowledge Discovery in
Databases
Khai phá dữ liệu KPDL Data Mining
Phân cụm dữ liệu PCDL Data Clustering
Khai phá tri thức KPTT Knowledge Discovery
vi
DANH MỤC HÌNH VẼ
Hình 1.2: Quá trình khai phá tri thức .....................................................................4
Hình 1.3: Qúa trình khai phá dữ liệu.......................................................................7
Hình 2.1: Mô hình về phân cụm dựa trên tiêu chuẩn thu nhập và số nợ.................15
Hình 2.2: Khoảng cách Euclidean ........................................................................24
Hình 2.3: Bảng tham số .........................................................................................26
Hình 2.4: Ví dụ quá trình phân hoạch với k=3 ......................................................30
Hình 2.6: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi K-means .....32
Hình 2.7: Các chiến lược phân cụm phân cấp .......................................................37
Hình 2.8: Ví dụ về kết quả phân cụm bằng thuật toán BIRCH. ..............................39
Hình 2.9. Khái quát thuật toán CURE ...................................................................41
Hình 2.10. Các cụm dữ liệu được khám phá bởi CURE ........................................41
Hình 2.11. Ví dụ thực hiện phân cụm bằng thuật toán CURE ...............................43
Hình 2.12: Các bước thuật toán CHAMELEON ....................................................44
Hình 2.13: Hình dạng các cụm được khám phá bởi DBSCAN ...............................45
Hình 2.14: Mật độ - đến được trực tiếp .................................................................46
Hình 2.15: Mật độ - đến được................................................................................47
Hình 2.16: Mật độ - liên thông ..............................................................................47
Hình 2.17: Cụm và nhiễu.......................................................................................48
Hình 2.18: Mô hình cấu trúc dữ liệu lưới ..............................................................52
Hình 2.19: Mô hình thuật toán STING...................................................................53
Hình 3.1: Kết quả phân cụm với Minpt = 3, Epxilon = 200000000 ......................60
Hình 3.2: Kết quả phân cụm trên dữ liệu thuộc tính và trên bản đồ .......................61
Hình 3.3: Màu của các cụm thể hiện trên bản đồ..................................................61
Hình 3.4: Giao diện chương trình Phân cụm dữ liệu bằng thuật toán DBSCAN ....68
Hình 3.5: Giao diện chương trình sau khi thực hiên phân cụm ..............................69
Hình 3.6: Kết quả phân cụm ..................................................................................70
1
MỞ ĐẦU
Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin
trong các lĩnh vực của đời sống, kinh tế, xã hội trong nhiều năm qua cũng đồng
nghĩa với lượng dữ liệu đã được các cơ quan thu thập và lưu trữ ngày một tích lũy
nhiều lên. Hơn nữa, các công nghệ lưu trữ và phục hồi dữ liệu phát triển một cách
nhanh chóng vì thế cơ sở dữ liệu ở các cơ quan, doanh nghiệp, đơn vị ngày càng
nhiều thông tin tiềm ẩn phong phú và đa dạng. Mặt khác, trong môi trường cạnh
tranh, người ta ngày càng cần có nhiều thông tin với tốc độ nhanh để trợ giúp việc
ra quyết định và ngày càng có nhiều câu hỏi mang tính chất định tính cần phải trả
lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với những lý do như vậy, các
phương pháp quản trị và khai thác cơ sở dữ liệu truyền thống ngày càng không đáp
ứng được thực tế đã làm phát triển một khuynh hướng kỹ thuật mới đó là Kỹ thuật
khai phá tri thức và khai phá dữ liệu (KDD - Knowledge Discovery and Data
Mining). Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri
thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn
(discovery of interesting, implicit, and previously unknown knowledge from large
databases)[5]
Kỹ thuật khai phá tri thức và khai phá dữ liệu đã và đang được nghiên cứu,
ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại Việt Nam kỹ
thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa
vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm là phân lớp
nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,…
Phân cụm cơ sở dữ liệu là một trong những phương pháp quan trọng trong
quá trình tìm kiếm tri thức. Phân cụm là phương pháp học từ quan sát (learning
from obversation) hay còn gọi là học không thầy (unupervised learning or
automatic classfication) trong trí tuệ nhân tạo. Phân cụm đặc biệt hiệu quả khi ta
không biết về thông tin của các cụm, hoặc khi ta quan tâm tới những thuộc tính của
cụm mà chưa biết hoặc biết rất ít về những thông tin đó. Phân cụm được coi như
một công cụ độc lập để xem xét phân bố dữ liệu, làm bước tiền xử lý cho các thuật
toán khác. Việc phân cụm dữ liệu có rất nhiều ứng dụng như trong tiếp thị, sử dụng
đất, bảo hiểm, hoạch định thành phố … Hiện nay, phân cụm dữ liệu là một hướng
được nghiên cứu rất nhiều trong Tin học. Chính vì lý do đó mà em chọn đề tài
“Nghiên cứu các kỹ thuật phân cụm dữ liệu và Ứng dụng” là hướng nghiên cứu
chính cho luận văn của mình.
2
Nội dung chính của luận văn được trình bày trong 3 chương:
Chương 1: Tổng quan về khai phá tri thức và khai phá dữ liệu. Trong
chương này trình bày tổng quan về khai phá tri thức, khai phá dữ liệu; qui trình khai
phá tri thức, khai phá dữ liệu; …
Chương 2: Phân cụm và các kỹ thuật phân cụm. Trong chương này trình bày
tổng quan về phân cụm dữ liệu, một số phương pháp phân cụm dữ liệu dữ liệu phổ
biến như phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ,
phân cụm dựa trên lưới; trình bày một số giải thuật điển hình của mỗi phương pháp
phân cụm; …
Chương 3: Ứng dụng, triển khai bài toán với giải thuật DBSCAN
Phần kết luận trình bày tóm tắt về các nội dung thực hiện trong luận văn,
đồng thời đưa ra các vấn đề nghiên cứu tiếp cho tương lai. Phần phụ lục trình bày
một số modul chương trình cài đặt bằng thuật toán DBSCAN.
Do thời gian nghiên cứu và trình độ có hạn, luận văn không tránh khỏi những
hạn chế và thiếu sót. Em rất mong nhận được sự chỉ bảo, đóng góp ý kiến của các
thầy thầy/ cô giáo cũng như bạn bè và đồng nghiệp.
Em xin chân thành cảm ơn!
3
Chương 1.
TỔNG QUAN VỀ KHAI PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU
1.1. Giới thiệu chung
Cách mạng khoa học kỹ thuật tạo ra bước nhảy vọt trong tất cả các lĩnh vực
của đời sống kinh tế, xã hội, … Một thành công không thể không kể đến của cuộc
cách mạng này là sự bùng nổ thông tin, khiến cho khối lượng thông tin mà con
người thu thập và lưu trữ ngày một khổng lồ, kích thước của CSDL tăng một cách
nhanh chóng. Trong những CSDL đó tiềm ẩn nhiều rất nhiều tri thức mà con người
chưa khám phá ra được. Đứng trước núi dữ liệu khổng lồ thu thập được, việc khám
phá tri thức và thông tin trở nên rất khó khăn. Chính vì lý do đó nhu cầu tìm kiếm
tri thức trong khối CSDL đã nảy sinh, nhu cầu này ngày một cấp thiết và dẫn tới sự
hình thành của một lĩnh vực mới – lĩnh vực khai phá dữ liệu (Data Mining) hay khai
phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in databases - KDD).
Khai phá tri thức trong cơ sở dữ liệu có thể được coi như quá trình tìm tri
thức có ích, cần thiết, tiềm ẩn và chưa được biết trước trong cơ sở dữ liệu lớn
(discovery of interesting, implicit, and previously unknown knowledge from large
databases)
Tuy mới ra đời nhưng khai phá tri thức và khai phá dữ liệu đã và đang được
nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, tại
Việt Nam kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu
và dần đưa vào ứng dụng trong những năm gần đây. Những vấn đề được quan tâm
là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu, phần tử dị biệt,…
1.2. Khai phá tri thức và quá trình khai phá tri thức
1.2.1. Khai phá tri thức
Khai phá hay phát hiện tri thức trong các cơ sở dữ liệu là một quy trình nhận
biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp,
hợp thức, khả ích, và có thể hiểu được. Còn khám phá dữ liệu là một bước trong qui
trình khám phá tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dưới
một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các
4
mô hình trong dữ liệu. Nói một cách khác, mục đích của phát hiện tri thức và khai
phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các cơ
sở dữ liệu nhưng nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu.
1.2.2. Quá trình khai phá tri thức
Việc khai phá tri thức thông thường có thể mô tả bằng sơ đồ các quy trình
sau [4]:
Hình 1.2: Quá trình khai phá tri thức
Trong đó, mỗi bước là một quy trình có vai trò riêng và nhiệm vụ khác nhau,
bao gồm:
Bước thứ nhất: tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này
sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương
pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu.
Bước thứ hai: thu thập và xử lý dữ liệu thô, còn được gọi là tiền xử lý dữ liệu
nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu
cần thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ quy trình khai
phá tri thức.
Bước thứ ba: khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và
các mô hình ẩn dưới các dữ liệu.
5
Bước thứ tư: hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và
dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể
được lấy trung bình trên tất cả các lần thực hiện.
Bước thứ năm: sử dụng tri thức đã được khám phá vào thực tế, các tri thức
phát hiện được tích hợp chặt chẽ trong hệ thống. Tuy nhiên để sử dụng được các tri
thức đó đôi khi cần đến các chuyên gia trong các lĩnh vực quan tâm vì tri thức rút ra
có thể chỉ mang tính chất hỗ trợ quyết định hoặc cũng có thể được sử dụng cho một
quá trình khai phá tri thức khác.
Mặc dù được tóm tắt thành năm bước như trên, nhưng thực chất quá trình
xây dựng và thực hiện việc khám phá tri thức không chỉ phải tuân theo các bước cố
định mà các quá trình này còn có thể được lặp đi lặp lại ở một hoặc một số giai
đoạn, lần sau sẽ hoàn thiện hơn lần trước và giai đoạn sau dựa vào kết quả của giai
đoạn trước và cứ tiếp tục như thế sẽ làm cho quá trình khai phá và tìm kiếm dữ liệu
ngày càng hoàn thiện hơn.
1.3. Khai phá dữ liệu
1.3.1. Khai phá dữ liệu
Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình KPTT. Về bản
chất nó là giai đoạn duy nhất tìm ra được thông tin mới. Việc khai phá dữ liệu còn
được coi như là việc khai phá tri thức từ dữ liệu (knowlegde mining from
databases), trích lọc tri thức (knowlegde extraction), phân tích dữ liệu - mẫu (data-
partent analysis), khảo cứu dữ liệu (data archaeology), đào xới, nạo vét dữ liệu
(data dredging).
Khai phá dữ liệu (Data Mining) được định nghĩa là quá trình trích lọc các
thông tin có giá trị ẩn trong lượng lớn dữ liệu được lưu trữ trong các CSDL hoặc
các kho dữ liệu,… Khai phá dữ liệu cũng còn được coi là một quá trình tìm kiếm,
khám phá ở nhiều góc độ để tìm ra các mối tương quan, các mối liên hệ dưới nhiều
góc độ khác nhau nhằm tìm ra các mẫu hay các mô hình tồn tại bên trong cơ sở dữ
liệu đang bị che khuất. Để trích rút các mẫu, mô hình tiềm ẩn có tính “tri thức” ta
phải tìm và áp dụng các phương pháp, kỹ thuật khai phá sao cho các kỹ thuật và
6
phương pháp này phải phù hợp với tính chất, đặc trưng của dữ liệu và mục đích sử
dụng. Tuy khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức nhưng
nó lại là bước tiên quyết, quan trọng và ảnh hưởng đến toàn bộ quá trình.
Tóm lại, khai phá dữ liệu là một quá trình tìm kiếm thông tin “tri thức” tiềm
ẩn trong cơ sở dữ liệu lớn, khổng lồ. Vì thế, có thể nói rằng hai thuật ngữ khám phá
tri thức và khai phá dữ liệu là tương đương nếu nói ở khía cạnh tổng quan, còn nếu
xét ở một góc độ chi tiết thì khai phá dữ liệu là một giai đoạn có vai trò quan trọng
trong quá trình khám phá tri thức [3][4][9].
1.3.2. Mục tiêu của khai phá dữ liệu
Qua những nội dung đã trình bày ở trên, ta có thể hiểu một cách sơ lược rằng
khai phá dữ liệu là quá trình tìm kiếm thông tin hữu ích, tiềm ẩn và mang tính dự
báo trong các cơ sở dữ liệu lớn. Việc khai phá dữ liệu nhằm các mục đích chính như sau:
- Khai thác những thông tin tiềm ẩn mang tính dự đoán từ những cơ sở dữ liệu
lớn dựa trên các công cụ khai phá dữ liệu nhằm dự đoán những xu hướng
trong tương lai nhằm giúp các đối tượng cần tri thức khai phá như: các tổ
chức, doanh nghiệp, nhà nghiên cứu, …. để hỗ trợ việc đưa ra những quyết
định kịp thời, được định hướng trên những tri thức được khám phá mang lại;
- Thực hiện phân tích xử lý, tính toán dữ liệu một cách tự động cho mỗi quá
trình xử lý dữ liệu để tìm ra tri thức.
1.3.3. Quá trình khai phá dữ liệu
KPDL là một giai đoạn quan trọng trong quá trình KPTT. Về bản chất, nó là
giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong CSDL chủ
yếu phục vụ cho mô tả và dự đoán. Dự đoán là thực hiện việc suy luận trên dữ liệu
để đưa ra các dự báo nhằm phân tích tập dữ liệu huấn luyện và tạo ra một mô hình
cho phép dự đoán các mẫu, mô hình mới chưa biết. Mô tả dữ là tổng kết hoặc diễn
tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con
người có thể hiểu được.
Quá trình KPDL bao gồm các bước như trong hình sau:
7
Hình 1.3: Qúa trình khai phá dữ liệu
Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết.
Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp.
Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền
xử lý chúng sao cho thuật toán KPDL có thể hiểu được. Đây là một
quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như:
dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp),
quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình
(nếu mô hình dữ liệu thay đổi), v.v..
Thuật toán khai phá dữ liệu: Lựa chọn thuật toán KPDL và thực hiện
việc PKDL để tìm được các mẫu có ý nghĩa, các mẫu này được biểu
diễn dưới dạng luật kết hợp, cây quyết định... tương ứng với ý nghĩa
của nó.
1.3.4. Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu
Vấn đề khai phá dữ liệu có thể được phân chia theo lớp các hướng tiếp cận
chính sau:
1.3.4.1. Phân lớp và dự đoán
Hướng tiếp cận này làm nhiệm vụ đư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. Kỹ thuật này gồm có: phân lớp (classification), hồi quy
(regression)... Là quá trình xếp một đối tượng vào một tron