BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM
---------------
PHẠM VĂN KHANH
ỨNG DỤNG LÝ THUYẾT GIÀN GIAO TRONG
KHAI THÁC DỮ LIỆU
LUẬN VĂN THẠC SỸ
Chuyên ngành: Công nghệ Thông tin
Mã số ngành: 60480201
TP. HỒ CHÍ MINH, tháng 09 năm 2014
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM
---------------
PHẠM VĂN KHANH
ỨNG DỤNG LÝ THUYẾT GIÀN GIAO TRONG
KHAI THÁC DỮ LIỆU
LUẬN VĂN THẠC SỸ
Chuyên ngành: Công nghệ Thông tin
Mã số ngành: 60480201
CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS TSKH NGUYỄN XUÂN HUY
TP. HỒ CHÍ MINH, tháng 09 năm 2014
i
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, kết
quả nêu trong Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ
công trình nào khác.
Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã
được cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc.
Học viên thực hiện Luận văn
Phạm Văn Khanh
ii
LỜI CẢM ƠN
Trong suốt quá trình học tập và hoàn thành luận văn này, tôi đã nhận được
sự hướng dẫn, giúp đỡ quý báu của quý thầy cô, gia đình, bạn bè và đồng nghiệp.
Với lòng kính trọng và biết ơn sâu sắc tôi xin được bày tỏ lời cảm ơn chân thành
tới:
Khoa Công Nghệ Thông Tin, Phòng quản lý khoa học - Đào tạo sau đại học
trường Đại Học Công Nghệ Thành Phố Hồ Chí Minh đã tạo mọi điều kiện thuận lợi
giúp đỡ tôi trong quá trình học tập và hoàn thành luận văn này.
Thầy hướng dẫn Phó giáo sư - Tiến sĩ Khoa học Nguyễn Xuân Huy, thầy đã
truyền đạt những kiến thức rất bổ ích cho tôi trong quá trình học tập, đã hết lòng
tạo điều kiện cũng như giúp đỡ tôi trong quá trình hoàn thành luận văn này.
Phó giáo sư - Tiến sĩ Lê Hoài Bắc, thầy đã truyền đạt những kiến thức rất bổ
ích cho tôi trong quá trình học tập, thầy đã hết lòng giúp đỡ và cung cấp cho tôi
những tài liệu nghiên cứu cần thiết liên quan đến luận văn này.
Thầy Cao Tùng Anh, thầy đã hết lòng giúp đỡ, chỉ bảo, động viên và tạo mọi
điều kiện thuận lợi cho tôi trong suốt quá trình học tập và hoàn thành luận văn này.
Toàn thể quý thầy cô đã nhiệt tình giảng dạy và truyền đạt những kiến thức bổ
ích cho tôi trong suốt khóa học vừa qua.
Cuối cùng xin cảm ơn đến tất cả những người thân trong gia đình, bạn bè và
đồng nghiệp đã giúp đỡ tôi trong suối quá trình học tập và thực hiện luận văn này.
Phạm Văn Khanh
iii
MỤC LỤC
MỞ ĐẦU ................................................................................................................ 1
Chương 1. TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC VÀ KHAI THÁC DỮ
LIỆU....................................................................................................................... 4
1.1. Khám phá tri thức và khai thác dữ liệu ............................................................ 4
1.2. Quá trình khám phá tri thức .......................................................................... 6
1.3. Quá trình khai thác dữ liệu ........................................................................... 8
1.4. Các phương pháp khai thác dữ liệu ............................................................... 9
1.5. Các lĩnh vực ứng dụng thực tiễn của khai thác dữ liệu ................................ 10
1.6. Các phương pháp, và kỹ thuật áp dụng trong khai thác dữ liệu ................... 11
1.7. Các thách thức – khó khăn trong khám phá tri thức và khai thác dữ liệu ..... 13
1.8. Khai thác tập phổ biến, luật kết hợp và tương quan .................................... 15
1.8.1. Bài toán kinh điển dẫn đến việc khai thác luật kết hợp ........................ 15
1.8.2. Tập phổ biến và luật kết hợp ............................................................... 18
1.8.3. Các phương pháp khai thác tập phổ biến ............................................. 19
1.9. Khai thác dữ liệu bảo đảm tính riêng tư ...................................................... 26
1.9.1. Bài toán khai thác dữ liệu bảo đảm tính riêng tư .................................. 26
1.9.2. Phân loại các phương pháp PPDM ...................................................... 27
1.9.3. Các phương pháp giấu dữ liệu nhạy cảm ............................................. 30
1.9.3.1. Làm xáo trộn (Perturbation) ........................................................ 30
1.9.3.2 Ngăn chặn (Blocking) .................................................................. 30
1.9.3.3 Gom hoặc trộn (Aggregation / Merging) ...................................... 30
1.9.3.4. Đổi chỗ (Swapping) .................................................................... 30
1.9.3.5. Lấy mẫu ....................................................................................... 32
Chương 2. ÁNH XẠ ĐÓNG VÀ GIÀN GIAO ÁNH XẠ ĐÓNG ...................... 37
2.1. Ánh xạ đóng ............................................................................................... 37
2.1.1. Các khái niệm và tính chất ánh xạ đóng .......................................... 37
iv
2.1.2. Phép hạn chế của ánh xạ đóng ......................................................... 39
2.2. Các phép toán hội và hợp thành trên ánh xạ đóng ...................................... 39
2.2.1. Phép toán hội .................................................................................. 40
2.2.2. Phép hợp thành các ánh xạ đóng ..................................................... 40
2.3. Giàn giao ánh xạ đóng ................................................................................ 45
2.3.1. Điểm bất động................................................................................. 45
2.3.2. Giàn giao ánh xạ đóng..................................................................... 45
Chương 3. ẨN CÁC TẬP MỤC NHẠY CẢM ................................................... 49
3.1. Giàn giao AXĐ và bài toán ẩn tập mục nhạy cảm ....................................... 49
3.2. Phát biểu bài toán ....................................................................................... 50
3.3. Giàn giao .................................................................................................... 52
3.4. Các tính chất của tập mục thường xuyên..................................................... 53
3.5. Thuật toán ẩn tập mục nhạy cảm ................................................................ 56
3.6. Ví dụ minh họa cho thuật toán .................................................................... 57
Chương 4. CHƯƠNG TRÌNH THỰC NGHIỆM .............................................. 61
4.1. Giới thiệu ................................................................................................... 61
4.2. Các chức năng chính của chương trình ....................................................... 62
KẾT LUẬT .......................................................................................................... 66
TÀI LIỆU THAM KHẢO ................................................................................... 68
v
DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT
KPDL
Khai thác dữ liệu
KPTT
Khám phá tri thức
PPDM (Privacy
Data Mining)
Preserving
Khai thác dữ liệu đảm bảo tính riêng tư
AXĐ
Ánh xạ đóng
CSDL
Cơ sở dữ liệu
LĐQH
Lược đồ quan hệ
PTH
Phụ thuộc hàm
Thuộc
Không thuộc
Là tập con
Chứa tập con
\
Phép trừ tập hợp
Phép giao tập hợp
Phép hợp tập hợp
Tương đương
Khác
Với mọi
LS(f)
Tập các vế trái của luật sinh f
RS(f)
Tập các vế phải của luật sinh f
Tập rỗng
vi
DANH MỤC CÁC BẢNG
Bảng 1.1. Dấu dữ liệu bằng phương pháp đổi chỗ ............................................... 36
Bảng 3.1. Bảng trị T và các tập mục thường xuyên theo ngưỡng 4 ..................... 56
Bảng 3.2. Các tập mục thường xuyên theo ngưỡng 4 .......................................... 62
Bảng 3.3. Sửa giá trị của E trong các bộ chứa ADE ............................................ 64
Bảng 3.4. Sửa giá trị của E trong các bộ chứa ABE ............................................ 65
vii
DANH MỤC CÁC HÌNH MINH HOẠ
Hình 1.1.
Quá trình khám phá tri thức ................................................................ 12
Hình 1.2.
Quá trình khai thác dữ liệu .................................................................. 14
Hình 2.1.
Ví dụ thuật toán Apriori ...................................................................... 29
Hình 2.2.
Ví dụ thuật toán Apriori ...................................................................... 30
Hình 3.1.
Đồ thị của giàn các tập mục thường xuyên P ....................................... 58
Hình 3.2.
Giàn giao đầy đủ của Poset(ABE) ...................................................... 59
Hình 4.1
Giao diện chính chương trình.............................................................. 63
Hình 4.2
Giao diện chương trình khi tính độ hỗ trợ của tất cả các tập mục ........ 64
Hình 4.3
Giao diện chương trình khi tìm tất cả tập mục thường xuyên .............. 65
Hình 4.4
Giao diện chương trình hiển thị các tập mục thường xuyên mới.......... 66
1
MỞ ĐẦU
Ngày nay, dữ liệu chứa thông tin của người dùng được lưu trữ lại thông qua rất
nhiều hoạt động hằng ngày như giao dịch, mua hàng, khám bệnh, tìm kiếm thông
tin, truy cập web,… Các dữ liệu này đóng vai trò ngày càng quan trọng trong sự
phát triển của xã hội như làm đầu vào cho quá trình phân tích tìm ra các thông tin
hữu ích cho các hệ hỗ trợ ra quyết định, phát hiện dịch bệnh hay hoạch định kế
hoạch kinh doanh,… Tuy nhiên, các thông tin hữu ích chỉ có thể được rút trích từ
tập dữ liệu rất lớn trong quá trình thu thập dữ liệu lớn từ đầu rất khó khăn. Chính vì
vậy, chia sẻ dữ liệu đóng vai trò rất quan trọng trong quá trình phát triển xã hội.
Tuy nhiên, chia sẽ dữ liệu có thể vô tình làm tiết lộ thông tin nhạy cảm của
người dùng gây nguy hại cho các cá nhân, tổ chức trong xã hội. Một vấn đề thường
gặp là khi cung cấp dữ liệu cho các trung tâm khai thác tri thức, một số cơ sở, cá
nhân không muốn công bố các luật vi phạm đến tính riêng tư của cá nhân hoặc
doanh nghiệp. Thí dụ, nếu X là tập mục về thương hiệu xe máy Honda, Y là tập
mục về số vụ tai nạn xe máy thì việc công bố tương quan giữa X và Y sẽ mang đến
sự bất lợi cho việc kinh doanh xe máy Honda. Các tập mục X và Y như trên được
gọi là các tập mục nhạy cảm. Một lẽ đương nhiên là cơ sở cung cấp dữ liệu sẽ phải
loại bỏ hai tập mục nhạy cảm X và Y khỏi danh mục cần cung cấp. Tuy nhiên, việc
làm này đôi khi lại vi phạm luật về cung cấp thông tin. Giải pháp thứ hai thường
được các cơ sở lách luật chọn là vẫn công bố đầy đủ các tập mục nhưng tìm cách
sửa tần suất xuất hiện của các tập mục nhạy cảm xuống dưới ngưỡng thường xuyên
. Khi đó các tập mục nhạy cảm sẽ trở thành các tập mục không thường xuyên và
do đó chúng không thể trở thành các thành phần trong bất kỳ luật nào. Giải pháp
thứ hai này được gọi là ẩn các tập mục nhạy cảm (và thường xuyên). Vậy, hướng
nghiên cứu của luận văn là cần thiết cho trường hợp cần bảo vệ bí mật và tính riêng
tư của các tình huống hợp pháp, đồng thời có thể phát hiện giả mạo, lách luật trong
các tình huống cần ngăn chặn.
2
Luận văn đề xuất một tiếp cận cho bài toán ẩn các tập mục nhạy cảm. Vận
dụng lý thuyết giàn giao ta có thể xác định một cận trên đúng và một cận dưới đúng
đối với một tập mục nhạy cảm cho trước. Hướng tiếp cận này có những điểm mới
sau đây. Thứ nhất, chứng minh rằng họ các tập mục thường xuyên tạo thành một
giàn giao. Thứ hai, nhờ vận dụng các tính chất của giàn giao đã chỉ ra rằng có thể
vận dụng lý thuyết đồ thị để xác định các tập mục gây ảnh hưởng và các tập mục
chịu ảnh hưởng trực tiếp khi sửa giao tác trên tập mục nhạy cảm cần ẩn do đó làm
giảm thời gian truy xuất các giao tác và không gây ra các hiệu ứng phụ theo nghĩa là
ẩn nhầm các tập mục khác.
Bố cục luận văn
Ngoài các phần Mở đầu, Mục lục, Danh mục các ký hiệu, chữ cái viết tắt, Danh
mục bảng, Danh mục hình, Kết luận, Tài liệu tham khảo. Luận văn chia làm 4
chương.
Chương 1: Tổng quan về khám phá tri thức và khai thác dữ liệu
Chương này giới thiệu tổng quát về quá trình khám phá tri thức nói chung và
khai thác dữ liệu nói riêng. Các phương pháp, lĩnh vực, các hướng tiếp cận trong
khai thác dữ liệu. Giới thiệu các khái niệm về mẫu phổ biến, luật kết hợp và các mối
tương quan, các phương pháp khai thác tập phổ biến.
Chương 2: Sử dụng giàn giao trong ẩn các tập mục nhạy cảm
Chương này trình bày một số khái niệm và tính chất cơ bản của ánh xạ đóng,
vai trò của AXĐ trong việc ứng dụng giải quyết các bài toán về khai thác dữ liệu.
Trình bày về lý thuyết giàn giao và ứng dụng lý thuyết giàn giao trong thuật toán ẩn
các tập mục nhạy cảm.
Chương 3: Ẩn các tập mục nhạy cảm
Chương này mô tả chi tiết bài toán ẩn các tập mục nhạy cảm, đi sâu vào việc
giải quyết bài toán.
3
Chương 4. Chương trình thực nghiệm
Chương này đưa ra đề xuất phương pháp cài đặt thuật toán với ứng dụng là
CSDL thực tế. So sánh kết quả đạt được với những công trình nghiên cứu liên quan,
đưa ra hướng cải tiến của đề tài.
4
Chương 1
TỔNG QUAN VỀ KỸ THUẬT KHÁM PHÁ TRI THỨC
VÀ KHAI THÁC DỮ LIỆU
1.1. Khám phá tri thức và khai thác dữ liệu
Trong thời đại công nghệ thông tin như hiện nay, các công nghệ lưu trữ dữ
liệu ngày càng phát triển tạo điều kiện cho các đơn vị thu thập dữ liệu ngày một
thuận tiện. Với hàng triệu cơ sở dữ liệu đã được lưu trữ và sử dụng trong các hoạt
động sản xuất, kinh doanh, quản lí..., trong số đó có nhiều cơ sở dữ liệu rất lớn cỡ
Gigabyte, thậm chí là Terabyte. Sự bùng nổ này đã làm cho 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ế
dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động
chuyển đổi lượng dữ liệu khổng lồ kia thành các tri thức có ích đó là kỹ thuật phát
hiện tri thức và khai thác dữ liệu (KDD - Knowledge Discovery and Data mining).
Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và
các ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một
chương trình dưới một dạng nhất định. Các bits thường được sử dụng để đo thông
tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và rút gọn tới
mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức được xem như là
các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã được
nhận thức, khám phá, hoặc nghiên cứu. Nói cách khác, tri thức có thể được coi là dữ
liệu ở mức độ cao của sự trừu tượng và tổng quát.
Khám phá tri thức là quá trình tìm ra những tri thức, đó là những mẫu tiềm ẩn,
trước đó chưa biết và là thông tin hữu ích đáng tin cậy. Còn khai thác dữ liệu
(KPDL) là một bước quan trọng trong quá trình khám phá tri thức, sử dụng các
thuật toán KPDL chuyên dùng với một số qui định về hiệu quả tính toán chấp nhận
được để chiết xuất ra các mẫu hoặc các mô hình có ích trong dữ liệu. Nói một cách
khác, mục đích của khám phá tri thức và KPDL chính là tìm ra các mẫu hoặc mô
5
hình đang tồn tại trong các cơ sở dữ liệu (CSDL) nhưng vẫn còn bị che khuất bởi
hàng núi dữ liệu.
Khám phá tri thức từ CSDL là một quá trình sử dụng các phương pháp và
công cụ tin học, trong đó con người là trung tâm của quá trình. Do đó, con người
cần phải có kiến thức cơ bản về lĩnh vực cần khám phá để có thể chọn được tập con
dữ liệu tốt, từ đó phát hiện các mẫu phù hợp với mục tiêu đề ra. Đó chính là tri thức,
được rút ra từ CSDL, thường để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất
định trong một lĩnh vực nhất định. Tuy vậy, quá trình khám phá tri thức mang tính
chất hướng nhiệm vụ vì không phải là mọi tri thức tìm được đều có thể áp dụng
được vào thực tế.
Để có được những thông tin quý báu chúng ta phải tìm ra các mẫu có trong tập
CSDL trước. Việc đánh giá các mẫu được tìm thấy cũng là một điều thú vị và tất
yếu có tính chất quyết định đến sự sử dụng hay không sử dụng chúng. Đầu ra của
một chương trình là khám phá những mẫu có ích được gọi là tri thức. Tri thức được
khám phá có các đặc điểm chính:
-
Kiến thức cao cấp: 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ó. Quá trình để tìm ra
kiến thức như vậy không phải từ những phương pháp thống kê cổ điển mà nó
được đúc kết từ các kinh nghiệm đã có, được thể hiện trong dữ liệu, những kết
quả đó có thể lĩnh hội được.
-
Độ chính xác: Dù cho những mẫu khai thác thật sự có trong CSDL hay không
thì việc đo lường trị giá của chúng là bắt buộc phải có. Chúng ta sẽ chỉ sử dụng
những mẫu nào có độ chính xác càng cao thì hiệu quả công việc đạt được càng
lớn, những mẫu có độ chính xác chưa được xác định rõ ràng hoặc không cao thì
không nên sử ụng chúng.
-
Tính hấp dẫn: Khám phá tri thức được coi là lý thú vì nó có thể vạch ra các
xu hướng một cách hoàn thiện. Đó là những điều mới lạ hay những quy trình
tiềm năng, hữu ích ẩn chứa từ trong dữ liệu trước đó.
6
-
Tính hiệu quả: thời gian chạy của thuật toán khám phá tri thức trên CSDL
lớn có thể dự tính và chấp nhận được.
Dữ liệu là tập hợp những bộ thông tin chính xác và quá trình khám phá tri
thức được xem là sự loại bỏ các dư thừa, được rút gọn tới mức tối thiểu chỉ để
lại các đặc trưng cơ bản cho dữ liệu. Tri thức được tìm thấy là các thông tin tích
hợp, bao gồm các sự kiện và các mối quan hệ trong chúng. Các mối quan hệ này có
thể được hiểu ra, có thể được phát hiện, hoặc có thể được học.
Nếu khám phá tri thức là toàn bộ quá trình chiết xuất tri thức từ các CSDL
thì KPDL là giai đoạn chủ yếu của quá trình đó. KPDL là một quá trình phát hiện
các mẫu mới, thường bao gồm việc thử tìm mô hình phù hợp với tập dữ liệu và tìm
kiếm các mẫu từ tập dữ liệu theo mô hình đó. Sử dụng các kỹ thuật và các khái
niệm của các lĩnh vực đã được nghiên cứu từ trước như: học máy, nhận dạng, thống
kê, hồi quy, xếp loại, phân nhóm, các mô hình đồ thị, các mạng Bayes,… Nói cách
khác, mục tiêu của khai thác dữ liệu là tìm kiếm các mẫu hoặc mô hình tồn tại trong
cơ sở dữ liệu nhưng ẩn trong khối lượng lớn dữ liệu.
1.2. Quá trình khám phá tri thức
Hình 1.1. Quá trình khám phá tri thức
7
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, v.v...
Quá trình khám phá trí thức tiến hành qua 6 giai đoạn sau đây:
1. Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai thác 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.
2. Trích lọc dữ liệu: Ở giai đọan 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 nữ.
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 khai thác dữ liệu. 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ụ: Điểm Trung bình = 12.4. 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ư thừa, không có giá trị.
Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được
“làm sạch – tiền xử lý – chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch
nghiêm trọng.
4. Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra
có thể sử dụng và điều khiển được bởi việc tổ chức lại nó, tức là dữ liệu sẽ
được chuyển đổi về dạng phù hợp cho việc khai thác bằng cách thực hiện các
thao tác nhóm hoặc tập hợp.
5. Khai thác dữ liệu: Đây là bước mang tính tư duy trong khai thác dữ liệu. Ở
giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu
8
từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết,
v.v...
6. Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, các mẫu dữ liệu được
chiết xuất ra bởi phần mềm khai thác dữ liệu. Không phải bất cứ mẫu dữ liệu
nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ưu tiên
những tiêu chuẩn đánh giá để chiết xuất ra các tri thức cần chiết xuất ra. Đánh
giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép đo. Sau đó
sử dụng các kỹ thuật trình diễn và trực quan hóa dữ liệu để biểu diễn tri thức
khai thác được cho người sử dụng.
Trên đây là 6 giai đoạn của quá trình khám phá tri thức, trong đó giai đoạn 5khai thác dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn được quan tâm nhiều
nhất.
1.3. Quá trình khai thác dữ liệu
Khai thác dữ liệu (KPDL) là một giai đoạn quan trọng trong quá trình khám
phá tri thức (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.
Mô tả dữ liệu 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.
Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật được
phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất
ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của
các biến quan tâm.
Quá trình KPDL bao gồm các bước chính được thể hiện như hình 1.2 sau:
9
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 có mô hình dữ liệu thay đổi), v.v…
Thuật toán khai thác dữ liệu: Lựa chọn thuật toán KPDL và thực hiện việc
KPDL để 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.4. Các phương pháp khai thác dữ liệu
Với hai mục đích khai thác dữ liệu là Mô tả và Dự đoán, người ta thường sử
dụng các phương pháp sau cho khai thác dữ liệu:
-
Luật kết hợp (association rules)
-
Phân lớp (Classfication)
-
Hồi qui (Regression)
-
Trực quan hóa (Visualiztion)
-
Phân cụm (Clustering)
-
Tổng hợp (Summarization)
-
Mô hình ràng buộc (Dependency modeling)
-
Biểu diễn mô hình (Model Evaluation)
-
Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)
-
Phương pháp tìm kiếm (Search Method)
10
Có nhiều phương pháp khai thác dữ liệu được nghiên cứu ở trên, trong đó có
ba phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết hợp,
Phân lớp dữ liệu và phân cụm dữ liệu.
1.5. Các lĩnh vực ứng dụng thực tiễn của KPDL
Ở thập kỷ 90 của thế kỷ XX, người ta coi khai thác dữ liệu là quá trình phân
tích cơ sở dữ liệu nhằm phát hiện ra các thông tin mới và giá trị, thường thể hiện
dưới dạng các mối quan hệ chưa biết đến giữa các biến số. Những phát hiện này
được sử dụng nhằm tăng thêm tính hiệu quả của doanh nghiệp trong khi phải cạnh
tranh trên thương trường. Nhờ phân tích các dữ liệu liên quan đến khách hàng,
doanh nghiệp có khả năng dự báo trước một số hành vi ứng xử của khách hàng.
Những năm gần đây, người ta quan niệm khai thác dữ liệu (Đôi khi còn dùng
thuật ngữ khám phá dữ liệu hay phát hiện tri thức) là một quá trình phân tích dữ liệu
từ các viễn cảnh khác nhau và rút ra các thông tin bổ ích – những thông tin có thể
dùng để tăng lợi nhuận, cắt giảm chi phí hoặc cả hai mục đích. Phần mềm khai thác
dữ liệu là một công cụ phân tích dùng để phân tích dữ liệu. Nó cho phép người sử
dụng phân tích dữ liệu theo nhiều góc nhìn khác nhau, phân loại dữ liệu theo những
quan điểm riêng biệt và tổng kết các mối quan hệ đã được bóc tách. Xét về khía
cạnh kỹ thuật, khai thác dữ liệu là một quá trình tìm kiếm các mối tương quan giữa
các mẫu ẩn chứa trong hàng chục trường dữ liệu của một cơ sở dữ liệu quan hệ cỡ
lớn.
Hiện nay, kỹ thuật khai thác dữ liệu đang được áp dụng một cách rộng rãi
trong rất nhiều lĩnh vực kinh doanh và đời sống khác nhau như:
-
Thương mại: Phân tích dữ liệu bán hàng và thị trường, phân tích đầu tư, quyết
định cho vay, phát hiện gian lận, …
-
Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích
kết quả thử nghiệm, …
11
-
Thông tin khoa học: Dự báo thời tiết, CSDL sinh học: Ngân hàng gen, …
khoa học địa lý: dự báo động đất,…
-
Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet…Giáo dục...
1.6. Các phương pháp, và kỹ thuật áp dụng trong KPDL
Các kỹ thuật KPDL được chia làm 2 nhóm chính:
-
Kỹ thuật khai thác dữ liệu mô tả: Có nhiệm vụ mô tả về các tính chất hoặc
các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có. Các kỹ thuật này
gồm có: Phân cụm (clustering), tóm tắt (summerization), trực quan hóa
(visualiztation), phân tích sự phát triển và độ lệch (evolution and deviation
analyst), phân tích luật kết hợp (association rules)…
-
Kỹ thuật khai thác dữ liệu dự đoán: Có 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. Các kỹ thuật này gồm có: Phân lớp
(classification), hồi quy (regression)…
Tuy nhiên, chỉ có một số phương pháp thông dụng nhất là: Phân cụm dữ liệu,
phân lớp dữ liệu, phương pháp hồi quy và khai thác luật kết hợp.
a. Phân cụm dữ liệu: Mục tiêu chính của phương pháp phân cụm dữ liệu là
nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các
đối tượng thuộc cùng một lớp là tương đồng còn các đối tượng thuộc các
cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu là một ví dụ của
phương pháp học không có thầy. Không giống như phân lớp dữ liệu, phân
cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn
luyện. Vì thế có thể coi phân cụm dữ liệu là một cách học bằng quan sát
(learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ
(learning by example). Trong phương pháp này bạn không thể biết kết quả
các cụm thu được sẽ thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần
có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu được. Phân cụm
dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường,
- Xem thêm -