Giáo trình Khai phá dữ liệu - Trường Đại học Hàng Hải
TRƢỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN HỆ THỐNG THÔNG TIN
-----***-----
BÀI GIẢNG
KHAI PHÁ DỮ LIỆU
TÊN HỌC PHẦN:
MÃ HỌC PHẦN:
KHAI PHÁ DỮ LIỆU
17409
TRÌNH ĐỘ ĐÀO TẠO:
ĐẠI HỌC CHÍNH QUY
DÙNG CHO SV NGÀNH: CÔNG NGHỆ THÔNG TIN
HẢI PHÒNG - 2011
2
MỤC LỤC
Nội dung
Trang
Chƣơng 1. Tổng quan kho dữ liệu (Data warehouse)
1.1. Các chiến lược xử lý và khai thác thông tin
1.2. Định nghĩa kho dữ liệu
1.3. Mục đích của kho dữ liệu
1.4. Đặc tính của dữ liệu trong kho dữ liệu
1.5. Phân biệt kho dữ liệu với các cơ sở dữ liệu tác nghiệp
Chƣơng 2. Tổng quan về khai phá dữ liệu
2.1. Khai phá dữ liệu là gì?
2.2. Phân loại các hệ thống khai phá dữ liệu
2.3. Những nhiệm vụ chính
2.4. Tích hợp hệ thống khai phá dữ liệu với cơ sở dữ liệu hoặc kho
2.5. Các phương pháp khai phá dữ liệu
2.6. Lợi thế của khai phá dữ liệu so với phương pháp cơ bản
2.7. Lựa chọn phương pháp
2.8. Những thách thức trong ứng dụng và nghiên cứu trong kỹ thuật khai phá dữ liệu
Chƣơng 3. Tiền xử lý dữ liệu
3.1. Mục đích
3.2. Làm sạch dữ liệu
3.3. Tích hợp và biến đổi dữ liệu
Chƣơng 4. Khai phá dựa trên các mẫu phổ biến và luật kết hợp
4.1. Khái niệm cơ bản
4.2. Luật kết hợp
4.3. Phát biểu bài toán phát hiện luật kết hợp
4.4. Phát hiện luật kết hợp dựa trên hệ thông tin nhị phân
4.5. Khai phá luật kết hợp trên hệ thông tin mờ
Chƣơng 5. Phân lớp và dự đoán
5.1. Khái niệm cơ bản
5.2. Phân lớp dựa trên cây quyết định
3
Tên học phần: Khai phá dữ liệu
Bộ môn phụ trách giảng dạy: Hệ thống Thông tin
Mã học phần: 17409
Loại học phần: 2
Khoa phụ trách: CNTT.
Tổng số TC: 2
Tổng số tiết Lý thuyết
45 30
Thực hành/ Xemina
Tự học
Bài tập lớn
Đồ án môn học
không
15
0
không
Học phần học trƣớc: Cơ sở dữ liệu; Cơ sở dữ liệu nâng cao; Hệ quản trị CSDL
Học phần tiên quyết: Không yêu cầu.
Học phần song song: Không yêu cầu.
Mục tiêu của học phần:
Cung cấp các kiến thức cơ bản về kho dữ liệu lớn và các kỹ thuật khai phá dữ liệu.
Nội dung chủ yếu:
Tổng quan về kho dữ liệu và khai phá dữ liệu; Phương pháp tổ chức lưu trữ dữ liệu lớn, và
các kỹ thuật khai phá dữ liệu; Phân tích dữ liệu sử dụng phương pháp phân cụm; Ứng dụng kỹ
thuật khai phá dữ liệu.
Nội dung chi tiết:
PHÂN PHỐI SỐ TIẾT
TÊN CHƢƠNG MỤC
Chƣơng 1. Tổng quan kho dữ liệu (Data warehouse)
1.1. Các chiến lược xử lý và khai thác thông tin
1.2. Định nghĩa kho dữ liệu
TS
LT
TH
BT KT
6
4
2
1.3. Mục đích của kho dữ liệu
1.4. Đặc tính của dữ liệu trong kho dữ liệu
1.5. Phân biệt kho dữ liệu với các cơ sở dữ liệu tác
nghiệp
Chƣơng 2. Tổng quan về khai phá dữ liệu
2.1. Khai phá dữ liệu là gì?
9
6
3
2.2. Phân loại các hệ thống khai phá dữ liệu
2.3. Những nhiệm vụ chính
2.4. Tích hợp hệ thống khai phá dữ liệu với cơ sở dữ liệu
hoặc kho
2.5. Các phương pháp khai phá dữ liệu
2.6. Lợi thế của khai phá dữ liệu so với phương pháp cơ
bản
2.7. Lựa chọn phương pháp
2.8. Những thách thức trong ứng dụng và nghiên cứu
trong kỹ thuật khai phá dữ liệu
Chƣơng 3. Tiền xử lý dữ liệu
3.1. Mục đích
3.2. Làm sạch dữ liệu
3.3. Tích hợp và biến đổi dữ liệu
Chƣơng 4. Khai phá dựa trên các mẫu phổ biến và
luật kết hợp
9
6
8
3
4
12
4.1. Khái niệm cơ bản
4.2. Luật kết hợp
4.3. Phát biểu bài toán phát hiện luật kết hợp
4.4. Phát hiện luật kết hợp dựa trên hệ thông tin nhị phân
4.5. Khai phá luật kết hợp trên hệ thông tin mờ
Chƣơng 5. Phân lớp và dự đoán
5.1. Khái niệm cơ bản
9
6
3
5.2. Phân lớp dựa trên cây quyết định
4
Nhiệm vụ của sinh viên:
Tham dự các buổi học lý thuyết và thực hành, làm các bài tập được giao, làm các bài thi giữa
học phần và bài thi kết thúc học phần theo đúng quy định.
Tài liệu học tập:
1. J. Han, M. Kamber, Data Mining: Concepts and Techniques, 2nd edition, Morgan
Kaufmann, 2006.
2. P. N. Tan, M. Steinbach, V. Kumar, Introduction to Data Mining, Addison-Wesley, 2006.
3. Paulraj Ponnian, Data Warehousing Fundamentals, John Wiley.
Hình thức và tiêu chuẩn đánh giá sinh viên:
- Hình thức thi: tự luận hoặc trắc nghiệm.
- Tiêu chuẩn đánh giá sinh viên: căn cứ vào sự tham gia học tập của sinh viên trong các buổi
học lý thuyết và thực hành, kết quả làm các bài tập được giao, kết quả của các bài thi giữa học phần
và bài thi kết thúc học phần.
Thang điểm: Thang điểm chữ A, B, C, D, F.
Điểm đánh giá học phần: Z = 0,3X + 0,7Y.
Bài giảng này là tài liệu chính thức và thống nhất của Bộ môn Hệ thống Thông tin, Khoa
Công nghệ Thông tin và được dùng để giảng dạy cho sinh viên.
Ngày phê duyệt:
Trƣởng Bộ môn
/
/
5
Chương 1. Tổng quan về kho dữ liệu (Datawarehouse)
1.1.
Các chiến lƣợc xử lý và khai thác thông tin
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 nhiều 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 luỹ nhiều lên. Họ lưu trữ các dữ liệu này vì cho rằng
trong nó ẩn chứa những giá trị nhất định nào đó. Tuy nhiên, theo thống kê thì chỉ có một lượng nhỏ
của những dữ liệu này (khoảng từ 5% đến 10%) là luôn được phân tích, số còn lại họ không biết sẽ
phải làm gì hoặc có thể làm gì với chúng nhưng họ vẫn tiếp tục thu thập rất tốn kém với ý nghĩ lo sợ
rằng sẽ có cái gì đó quan trọng đã bị bỏ qua sau này có lúc cần đến nó. Một vấn đề đặt ra là làm thế
nào để tổ chức, khai thác những khối lượng dữ liệu khổng lồ và đa dạng đó được?
Về phía người sử dụng, các khó khăn gặp phải thường là:
Không thể tìm thấy dữ liệu cần thiết
Dữ liệu rải rác ở rất nhiều hệ thống với các giao diện và công cụ khác nhau, khiến
tốn nhiều thời gian chuyền từ hệ thống này sang hệ thống khác.
Có thể có nhiều nguồn thông tin đáp ứng được đòi hỏi, nhưng chúng lại có những
khác biệt và khó phát hiện thông tin nào là đúng.
Không thể lấy ra được dữ liệu cần thiết
Thường xuyên phải có chuyên gia trợ giúp, dẫn đến công việc bị dồn đống.
Có những loại thông tin không thể lấy ra được nếu không mở rộng khả năng làm
việc của hệ thống có sẵn.
Không thể hiểu dữ liệu tìm thấy
Mô tả dữ liệu nghèo nàn và thường xa rời với các thuật ngữ nghiệp vụ quen thuộc.
Không thể sử dụng được dữ liệu tìm thấy
Kết quả thường không đáp ứng về bản chất dữ liệu và thời gian tìm kiếm.
Dữ liệu phải chuyên đổi bằng tay vào môi trường làm việc của người sử dụng.
Những vấn đề về hệ thống thông tin:
“Phát triển các chương trình ứng dụng khác nhau là không đơn giản”.
Một chức năng được thể hiện ở rất nhiều chương trình, nhưng việc tổ chức và sử
dụng nó là rất khó khăn do hạn chế về kỹ thuật.
Chuyển đổi dữ liệu từ các khuôn dạng tác nghiệp khác nhau để phù hợp với người sử
dụng là rất khó khăn.
“Duy trì những chương trình này gặp rất nhiều vấn đề”
Một thay đổi ở một ứng dụng sẽ ảnh hưởng đến các ứng dụng khác có liên quan.
6
Thông thường sự phụ thuộc lẫn nhau giữa các chương trình không rõ ràng hoặc là
không xác định được.
Do sự phức tạp của công việc chuyển đổi cũng như toàn bộ quá trình bảo trì dẫn đến
mã nguồn của các chương trình trở nên hết sức phức tạp.
“Khối lượng dữ liệu lưu trữ tăng rất nhanh”
Không kiểm soát được khả năng chồng chéo dữ liệu trong các môi trường thông tin
dẫn đến khối lượng dữ liệu tăng nhanh.
“Quản trị dữ liệu phức tạp”
Thiếu những định nghĩa chuẩn, thống nhất về dữ liệu dẫn đến việc mất khả năng
kiểm soát môi trường thông tin.
Một thành phần dữ liệu tồn tại ở nhiều nguồn khác nhau.
Giải pháp cho tất cả các vấn đề nêu trên chính là việc xây dựng một kho dữ liệu (Data
Warehouse) và phát triển một khuynh hướng kỹ thuật mới đó là kỹ thuật phát hiện tri thức và khai
phá dữ liệu (KDD - Knowledge Discovery and Data Mining).
Trước hết, chúng ta nhắc lại một vài khái niệm cơ bản liên quan đến dữ liệu, cơ sở dữ liệu,
kho dữ liệu…
1.2. Định nghĩa kho dữ liệu
Thông thường chúng ta coi dữ liệu như một dãy các bit, hoặc các số và các ký hiệu, hoặc 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.
Chúng ta sử dụng các bit để đo lường các thông tin và xem nó như là các dữ liệu đã được lọc bỏ các
dư thừa, được 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. Chúng ta có thể
xem tri thức như 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ệ giữa 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ói cách khác,
tri thức có thể được coi là dữ liệu có độ trừu tượng và tổ chức cao .
Theo John Ladley, kỹ nghệ kho dữ liệu (DWT - Data Warehouse Technology) là tập các
phương pháp, kỹ thuật và các công cụ có thể kết hợp, hỗ trợ nhau để cung cấp thông tin cho người
sử dụng trên cơ sở tích hợp từ nhiều nguồn dữ liệu, nhiều môi trường khác nhau.
Kho dữ liệu (Data Warehouse), là tuyển chọn các cơ sở dữ liệu tích hợp, hướng theo các
chủ đề nhất định, được thiết kế để hỗ trợ cho chức năng trợ giúp quyết định, mà mỗi đơn vị dữ liệu
liên quan đến một khoảng thời gian cụ thể.
Kho dữ liệu thường có dung lượng rất lớn, thường là hàng Gigabytes hay có khi tới hàng
Terabytes.
Kho dữ liệu được xây dựng để tiện lợi cho việc truy cập từ nhiều nguồn, nhiều kiểu dữ liệu
khác nhau sao cho có thể kết hợp được cả những ứng dụng của các công nghệ hiện đại và vừa có thể
kế thừa được từ các hệ thống đã có từ trước. Dữ liệu được phát sinh từ các hoạt động hàng ngày và
được thu thập xử lý để phục vụ công việc nghiệp vụ cụ thể của một tổ chức, vì vậy thường được gọi
7
là dữ liệu tác nghiệp và hoạt động xử lý dữ liệu này gọi là xử lý giao dịch trực tuyến (OLPT - On
Line Transaction Processing).
Dòng dữ liệu trong một tổ chức (cơ quan, xí nghiệp, công ty, vv…) có thể mô tả khái quát
như sau:
Dữ liệu tác nghiệp
Kho dữ liệu
Kho dữ liệu cá nhân
HỆ THỐNG
DI SẢN
Kho dữ liệu cục bộ
Siêu dữ liệu
(có sẵn)
Hình 1.1. Luồng dữ liệu trong một tổ chức
Dữ liệu cá nhân không thuộc phạm vi quản lý của hệ quản trị kho dữ liệu. Nó chứa các
thông tin được trích xuất ra từ các hệ thống dữ liệu tác nghiệp, kho dữ liệu và từ những kho dữ liệu
cục bộ của những chủ đề liên quan bằng các phép gộp, tổng hợp hay xử lý theo một cách nào đó.
1.3. Mục đích của kho dữ liệu
Mục tiêu chính của kho dữ liệu nhằm đáp ứng các tiêu chuẩn cơ bản:
Phải có khả năng đáp ứng mọi yêu cầu về thông tin của người sử dụng.
Hỗ trợ để các nhân viên của tổ chức thực hiên tốt, hiệu quả công việc của mình, như có
những quyết định hợp lý, nhanh và bán được nhiều hàng hơn, năng suất cao hơn, thu được
lợi nhuận cao hơn ..v..v..
Giúp cho tổ chức xác định, quản lý và điều hành các dự án, các nghiệp vụ một cách hiệu quả
và chính xác.
Tích hơp dữ liệu và siêu dữ liệu từ nhiều nguồn khác nhau.
Muốn đạt được những yêu cầu trên thì DW phải:
Nâng cao chất lượng dữ liệu bằng các phương pháp làm sạch và tinh lọc dữ liệu theo những
hướng chủ đề nhất định.
Tổng hợp và kết nối dữ liệu.
Đồng bộ hoá các nguồn dữ liệu với DW.
Phân định và đồng nhất các hệ quản trị cơ sở dữ liệu tác nghiệp như là các công cụ chuẩn để
phục vụ cho DW.
8
Quản lí siêu dữ liệu (metadata)
Cung cấp thông tin được tích hợp, tóm tắt hoặc được liên kết, tổ chức theo các chủ đề.
Các kết quả khai thác kho dữ liệu được dùng trong hệ thống hỗ trợ quyết định (Decision
Support System - DSS), các hệ thống thông tin tác nghiệp hoặc hỗ trợ cho các truy vấn đặc biệt.
Mục tiêu cơ bản của mọi tổ chức là lợi nhuận và điều này được mô tả như sau:
Lợi nhuận
Lợi tức
Chi phí
Bán hàng
Xác định giá
Chi phí cố định
Chi phí biến đổi
Đề xuất kinh doanh
Chi phí trong sản xuất
Hình 1.2. Mối quan hệ về cách nhìn nhận trong hệ thống
Để thực hiện chiến lược kinh doanh hiệu quả, các nhà lãnh đạo vạch ra phương hướng kinh
doanh hàng hoá. Việc xác định giá của hàng hoá và quá trình bán hàng sẽ sản sinh lợi tức. Tuy
nhiên, để có được hàng hóa kinh doanh thì cần phải mất các khoản chi phí. Lợi tức trừ đi chi phí sẽ
cho lợi nhuận của đơn vị.
1.4. Đặc tính của dữ liệu trong kho dữ liệu
Đặc điểm cơ bản của kho dữ liệu là một tập hợp dữ liệu có các đặc tính sau :
-
-
-
-
Tính tích hợp
Tính hướng chủ đề
Tính ổn định
Dữ liệu tổng hợp
1.4.1. Tính tích hợp (Intergration)
Dữ liệu trong kho dữ liệu được tổ chức theo nhiều cách khác nhau sao cho phù hợp với các
quy ước đặt tên, thống nhất về số đo, cơ cấu mã hoá và cấu trúc vật lý của dữ liệu, ..v..v.. Một kho
dữ liệu là một khung nhìn thông tin mức toàn bộ đơn vị sản xuất kinh doanh đó, thống nhất toàn bộ
các khung nhìn khác nhau thành một khung nhìn theo một chủ điểm nào đó. Ví dụ, hệ thống xử lý
giao dịch trực tuyến (OLAP) truyền thống được xây dựng trên một vùng nghiệp vụ. Một hệ thống
bán hàng và một hệ thống tiếp thị (marketing) có thể có chung một dạng thông tin khách hàng. Tuy
nhiên, các vấn đề về tài chính cần có một khung nhìn khác về khách hàng. Khung nhìn đó bao gồm
các phần dữ liệu khác nhau về tài chính và marketing.
9
Tính tích hợp thể hiện ở chỗ: dữ liệu tập hợp trong kho dữ liệu được thu thập từ nhiều
nguồn được trộn ghép với nhau thành một thể thống nhất.
1.4.2. Tính hướng chủ đề
Dữ liệu trong kho dữ liệu được tổ chức theo chủ đề phục vụ cho tổ chức dễ dàng xác định
được các thông tin cần thiết trong từng hoạt động của mình. Ví dụ, trong hệ thống quản lý tài chính
cũ có thể có dữ liệu được tổ chức cho các chức năng: cho vay, quản lý tín dụng, quản lý ngân sách,
..v..v.. Ngược lại, trong kho dữ liệu về tài chính, dữ liệu được tổ chức theo chủ điểm dựa vào các
đối tượng: khách hàng, sản phẩm, các xí nghiệp, ..v..v.. Sự khác nhau của 2 cách tiếp cận trên dẫn
đến sự khác nhau về nội dung dữ liệu lưu trữ trong hệ thống.
* Kho dữ liệu không lưu trữ dữ liệu chi tiết, chỉ cần lưu trữ dữ liệu mang tính tổng hợp phục
vụ chủ yếu cho quá trình phân tích để trợ giúp quyết định.
* CSDL trong các ứng dụng tác nghiệp lại cần xử lý dữ liệu chi tiết, phục vụ trực tiếp cho
các yêu cầu xử lý theo các chức năng của lĩnh vực ứng dụng hiện thời. Do vậy, các hệ thống ứng
dụng tác nghiệp (Operational Application System - OAS) cần lưu trữ dữ liệu chi tiết. Mối quan hệ
của dữ liệu trong hệ thống này cũng khác, đòi hỏi phải có tính chính xác, có tính thời sự, ..v..v..
* Dữ liệu cần gắn với thời gian và có tính lịch sử. Kho chứa dữ liệu bao hàm một khối
lượng lớn dữ liệu có tính lịch sử. Dữ liệu được lưu trữ thành một loạt các snapshot (ảnh chụp dữ
liệu). Mỗi bản ghi phản ánh những giá trị của dữ liệu tại một thời điểm nhất định thể hiện khung
nhìn của một chủ điểm trong một giai đoạn. Do vậy cho phép khôi phục lại lịch sử và so sánh tương
đối chính xác các giai đoạn khác nhau. Yếu tố thời gian có vai trò như một phần của khoá để đảm
bảo tính đơn nhất của mỗi sản phẩm hàng hoá cà cung cấp đặc trưng về thời gian cho dữ liệu. Ví dụ,
trong hệ thống quản lý kinh doanh cần có dữ liệu lưu trữ về đơn giá cuả mặt hàng theo ngày (đó
chính là yếu tố thời gian). Cụ thể mỗi mặt hàng theo một đơn vị tính và tại một thời điểm xác định
phải có một đơn giá khác nhau (sự biến động về giá cả mặt hàng xăng dầu trong thời gian qua là
một minh chứng điển hình).
Dữ liệu trong OAS thì cần phải chính xác tại thời điểm truy cập, còn ở DW thì chỉ cần có
hiệu lực trong khoảng thời gian nào đó, trong khoảng 5 đến 10 năm hoặc lâu hơn. Dữ liệu của
CSDL tác nghiệp thường sau một khoảng thời gian nhất định sẽ trở thành dữ liệu lịch sử và chúng
sẽ được chuyển vào trong kho dữ liệu. Đó chính là những dữ liệu hợp lý về những chủ điểm cần lưu
trữ.
10
So sánh về CSDL tác nghiệp và ảnh chụp dữ liệu, ta thấy:
CSDL tác nghiệp
Ảnh chụp dữ liệu
Thời gian ngắn (30 – 60 ngày)
Có thể có yếu tố thời gian hoặc không
Dữ liệu có thể được cập nhật
Thời gian dài (5 – 10 năm)
Luôn có yếu tố thời gian
Khi dữ liệu được chụp lại thì không cập
nhật được
Bảng 1.1. Tính thời gian của dữ liệu
1.4.3. Dữ liệu có tính ổn định (nonvolatility)
Dữ liệu trong DW là dữ liệu chỉ đọc và chỉ có thể được kiểm tra, không thể được thay đổi
bởi người dùng đầu cuối (terminal users). Nó chỉ cho phép thực hiện 2 thao tác cơ bản là nạp dữ
liệu vào kho và truy cập vào các cung trong DW. Do vậy, dữ liệu không biến động.
Thông tin trong DW phải được tải vào sau khi dữ liệu trong hệ thống điều hành được cho là
quá cũ. Tính không biến động thể hiện ở chỗ: dữ liệu được lưu trữ lâu dài trong kho dữ liệu. Mặc dù
có thêm dữ liệu mới nhập vào nhưng dữ liệu cũ trong kho dữ liệu vẫn không bị xoá hoặc thay đổi.
Điều đó cho phép cung cấp thông tin về một khoảng thời gian dài, cung cấp đủ số liệu cần thiết cho
các mô hình nghiệp vụ phân tích, dự báo. Từ đó có được những quyết định hợp lý, phù hợp với các
quy luật tiến hoá của tự nhiên.
1.4.4. Dữ liệu tổng hợp
Dữ liệu tác nghiệp thuần tuý không được lưu trữ trong DW. Dữ liệu tổng hợp được tích hợp
lại qua nhiều giai đoạn khác nhau theo các chủ điểm đã nêu ở trên.
1.5. Phân biệt kho dữ liệu với các cơ sở dữ liệu tác nghiệp
Trên cơ sở các đặc trưng của DW, ta phân biệt DW với những hệ quản trị CSDL tác nghiệp
truyền thống:
Kho dữ liệu phải được xác định hướng theo chủ đề. Nó được thực hiện theo ý đồ của người
sử dụng đầu cuối. Trong khi đó các hệ CSDL tác nghiệp dùng để phục vụ các mục đích áp
dụng chung.
Những hệ CSDL thông thường không phải quản lý những lượng thông tin lớn mà quản lý
những lượng thông tin vừa và nhỏ. DW phải quản lý một khối lượng lớn các thông tin được
lưu trữ trên nhiều phương tiện lưu trữ và xử lý khác nhau. Đó cũng là đặc thù của DW.
DW có thể ghép nối các phiên bản (version) khác nhau của các cấu trúc CSDL. DW tổng
hợp thông tin để thể hiện chúng dưới những hình thức dễ hiểu đối với người sử dụng.
DW tích hợp và kết nối thông tin từ nhiều nguồn khác nhau trên nhiều loại phương tiện lưu
trữ và xử lý thông tin nhằm phục vụ cho các ứng dụng xử lý tác nghiệp trực tuyến.
DW có thể lưu trữ các thông tin tổng hợp theo một chủ đề nghiệp vụ nào đó sao cho tạo ra
các thông tin phục vụ hiệu quả cho việc phân tích của người sử dụng.
11
DW thông thường chứa các dữ liệu lịch sử kết nối nhiều năm trước của các thông tin tác
nghiệp được tổ chức lưu trữ có hiệu quả và có thể được hiệu chỉnh lại dễ dàng. Dữ liệu trong
CSDL tác nghiệp thường là mới, có tính thời sự trong một khoảng thời gian ngắn.
Dữ liệu trong CSDL tác nghiệp được chắt lọc và tổng hợp lại để chuyển sang môi trường
DW. Rất nhiều dữ liệu khác không được chuyển về DW, chỉ những dữ liệu cần thiết cho
công tác quản lý hay trợ giúp quyết định mới được chuyển sang DW.
Nói một cách tổng quát, DW làm nhiệm vụ phân phát dữ liệu cho nhiều đối tượng (khách hàng),
xử lý thông tin nhiều dạng như: CSDL, truy vấn dữ liệu (SQL query), báo cáo (report) ..v..v..
12
BÀI TẬP:
LÝ THUYẾT:
1. Kho dữ liệu là gì?
2. Cho ví dụ về các hệ thống hoặc lĩnh vực nào đó có đủ điều kiện để xây dựng các kho
dữ liệu lớn?
3. Một bảng dữ liệu có 50.000 bản ghi liệu có thể được gọi là một kho dữ liệu lớn hay
chưa? Lý giải cho câu trả lời?
4. Cho ví dụ về một nguồn dữ liệu lưu trữ có cấu trúc bảng, cấu trúc semi-structured,
hoặc không cấu trúc?
5. Phân biệt kho dữ liệu với cơ sở dữ liệu tác nghiệp?
THỰC HÀNH:
1. Cài đặt bộ ứng dụng Microsoft Visual Studio 2005?
2. Cài đặt và tìm hiệu dịch vụ Data analysis?
3. Quan sát và tìm hiểu cơ sở dữ liệu NorthWind?
13
Chương 2: Tổng quan về khai phá dữ liệu
2.1. Khai phá dữ liệu
Khai phá dữ liệu được dùng để mô tả quá trình phát hiện ra tri thức trong CSDL. Quá trình
này kết xuất ra các tri thức tiềm ẩn từ dữ liệu giúp cho việc dự báo trong kinh doanh, các hoạt động
sản xuất, ... Khai phá dữ liệu làm giảm chi phí về thời gian so với phương pháp truyền thống trước
kia (ví dụ như phương pháp thống kê).
Sau đây là một số định nghiã mang tính mô tả của nhiều tác giả về khai phá dữ liệu.
Đị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”.
2.2. Các ứng dụng của khai phá dữ liệu
Phát hiện tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực: thống kê,
trí tuệ nhân tạo, cơ sở dữ liệu, thuật toán, tính toán song song và tốc độ cao, thu thập tri thức cho
các hệ chuyên gia, quan sát dữ liệu... Đặc biệt phát hiện tri thức và khai phá dữ liệu rất gần gũi với
lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và phát hiện các mẫu, luật
... Ngân hàng dữ liệu (Data Warehousing) và các công cụ phân tích trực tuyến (OLAP- On Line
Analytical Processing) cũng liên quan rất chặt chẽ với phát hiện tri thức và khai phá dữ liệu.
Khai phá dữ liệu có nhiều ứng dụng trong thực tế, ví dụ như:
Bảo hiểm, tài chính và thị trường chứng khoán: phân tích tình hình tài chính và dự báo giá của
các loại cổ phiếu trong thị trường chứng khoán. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín
dụng, phát hiện gian lận, ...
Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định. Ví dụ như bảng sau:
Dân số thế giới
(triệu ngƣời)
Dân số thế giới
(triệu ngƣời)
Dân số thế giới
(triệu ngƣời)
Năm
1950
Năm
1970
Năm
2555
2593
2635
2680
3708
3785
3862
3938
1990
1991
1992
1993
5275
5359
5443
5524
1951
1952
1953
1971
1972
1973
14
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
2728
2779
2832
2888
2945
2997
3039
3080
3136
3206
3277
3346
3416
3486
3558
3632
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
4014
4087
4159
4231
4303
4378
4454
4530
4610
4690
4769
4850
4932
5017
5102
5188
1994
1995
1996
1997
1998
1999
2000
2001
2002
5604
5685
5764
5844
5923
6001
6078
6153
6228
Nguồn: U.S. Bureau of the Census, International Data Base. Cập nhật ngày 10/10/2002.
Bảng 2.1. Dân số thế giới tính tại thời điểm giữa năm
Điều trị y học và chăm sóc y tế: một số thông tin về chuẩn đoán bệnh lưu trong các hệ thống
quản lý bệnh viện. Phân tích mối liên hệ giữa các triệu chứng bệnh, chuẩn đoán và phương
pháp điều trị (chế độ dinh dưỡng, thuốc, ...)
Sản xuất và chế biến: Quy trình, phương pháp chế biến và xử lý sự cố.
Text mining và Web mining: Phân lớp văn bản và các trang Web, tóm tắt văn bản,...
Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm kiếm, so sánh
các hệ gene và thông tin di truyền, mối liên hệ gene và một số bệnh di truyền, ...
Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi, sự cố, chất lượng
dịch vụ, ...
2.3. Các bƣớc của quá trình khai phá dữ liệu
Quy trình phát hiện tri thức thường tuân theo các bước sau:
15
Hình 2.1. Quy trình phát hiện tri thức
Bước thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là tìm hiểu lĩnh vực ứng dụng
từ đó hình thành bài toán, xác định các nhiệm vụ cần phải hoàn thành. 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à tiền xử lý dữ liệu. Là thu thập và xử lý thô, còn được gọi là tiền
xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu), xử lý việc thiếu dữ liệu (làm già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ộ qui trình phát hiện tri thức. Do dữ liệu được lấy từ nhiều nguồn khác nhau, không đồng nhất, …
có thể gây ra các nhầm lẫn. Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn và rời rạc hoá.
Bước thứ ba: Khai phá dữ liệu, rút ra các tri thức. Là 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. Giai đoạn này rất quan trọng, bao gồm
các công đoạn như: chức năng, nhiệm vụ và mục đích của khai phá dữ liệu, dùng phương pháp khai
phá nào? Thông thường, các bài toán khai phá dữ liệu bao gồm: các bài toán mang tính mô tả - đưa
ra tính chất chung nhất của dữ liệu, các bài toán dự báo - bao gồm cả việc phát hiện các suy diễn
dựa trên dữ liệu hiện có. Tuỳ theo bài toán xác định được mà ta lựa chọn các phương pháp khai phá
dữ liệu cho phù hợp.
Bước thứ tư: Sử dụng các tri thức phát hiện được. Là 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. Các kết quả của quá trình phát hiện tri thức
có thể được đưa và ứng dụng trong các lĩnh vực khác nhau. Do các kết quả có thể là các dự đoán
hoặc các mô tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hoá
quá trình này.
Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ
liệu là công đoạn quan trọng nhất.
16
2.4. Nhiệm vụ chính trong khai thác dữ liệu
Quá trình khai phá dữ liệu là quá trình phát hiện ra mẫu thông tin. Trong đó, giải thuật khai
phá tìm kiếm các mẫu đáng quan tâm theo dạng xác định như các luật, phân lớp, hồi quy, cây quyết
định, ...
2.4.1. Phân lớp (phân loại - classification)
Là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã được biết
trước đó. Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và
thuộc tính phân lớp. Như thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các
mục mới. Các kiến thức được phát hiện biểu diễn dưới dạng các luật theo cách sau: “Nếu các thuộc
tính dự báo của một mục thoả mãn điều kiện của các tiền đề thì mục nằm trong lớp chỉ ra trong kết
luận”.
Ví dụ: Một mục biểu diễn thông tin về nhân viên có các thuộc tính dự báo là: họ tên, tuổi,
giới tính, trình độ học vấn, … và thuộc tính phân loại là trình độ lãnh đạo của nhân viên.
2.4.2. Hồi qui (regression)
Là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực.
Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo
là liên tục chứ không phải rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp
thống kê cổ điển, chẳng hạn như hồi quy tuyến tính. Tuy nhiên, phương pháp mô hình hoá cũng
được sử dụng, ví dụ: cây quyết định.
Ứng dụng của hồi quy là rất nhiều, ví dụ: dự đoán số lượng sinh vật phát quang hiện thời
trong khu rừng bằng cách dò tìm vi sóng bằng các thiết bị cảm biến từ xa; ước lượng sác xuất người
bệnh có thể chết bằng cách kiểm tra các triệu chứng; dự báo nhu cầu của người dùng đối với một
sản phẩm, …
2.4.3. Phân nhóm (clustering)
Là việc mô tả chung để tìm ra các tập hay các nhóm, loại mô tả dữ liệu. Các nhóm có thể
tách nhau hoặc phân cấp hay gối lên nhau. Có nghĩa là dữ liệu có thể vừa thuộc nhóm này lại vừa
thuộc nhóm khác. Các ứng dụng khai phá dữ liệu có nhiệm vụ phân nhóm như phát hiện tập các
khách hàng có phản ứng giống nhau trong CSDL tiếp thị; xác định các quang phổ từ các phương
pháp đo tia hồng ngoại, … Liên quan chặt chẽ đến việc phân nhóm là nhiệm vụ đánh giá dữ liệu,
hàm mật độ xác suất đa biến/ các trường trong CSDL.
2.4.4. Tổng hợp (summarization)
Là công việc liên quan đến các phương pháp tìm kiếm một mô tả tập con dữ liệu [1, 2, 5].
Kỹ thuật tổng hợp thường áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động.
Nhiệm vụ chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng
hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trưng thể
17
hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả
các thuộc tính đã nêu trong kết luận”. Lưu ý rằng luật dạng này có các khác biệt so với luật phân
lớp. Luật phát hiện đặc trưng cho lớp chỉ sản sinh khi các mục đã thuộc về lớp đó.
2.4.5. Mô hình hoá sự phụ thuộc (dependency modeling)
Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính theo hai mức:
Mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị). Trong đó, các biến phụ thuộc bộ phận
vào các biến khác. Mức định lượng mô hình mô tả mức độ phụ thuộc. Những phụ thuộc này thường
được biểu thị dưới dạng theo luật “nếu - thì” (nếu tiền đề là đúng thì kết luận đúng). Về nguyên tắc,
cả tiền đề và kết luận đều có thể là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiền đề
thường là nhóm các giá trị thuộc tính và kết luận chỉ là một thuộc tính. Hơn nữa hệ thống có thể
phát hiện các luật phân lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do người dùng
chỉ ra trong kết luận.
Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy Bayes. Đó là đồ thị có
hướng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của liên kết phụ thuộc giữa các nút
đó.
2.4.6. Phát hiện sự biến đổi và độ lệch (change and deviation dectection)
Nhiệm vụ này tập trung vào khám phá hầu hết sự thay đổi có nghĩa dưới dạng độ đo đã biết
trước hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu thực và nội
dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian hay lệch theo nhóm. Độ lệch
theo thời gian là sự thay đổi có ý nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự khác
nhau của giữa dữ liệu trong hai tập con dữ liệu, ở đây tính cả trường hợp tập con dữ liệu này thuộc
tập con kia, nghĩa xác định dữ liệu trong một nhóm con của đối tượng có khác đáng kể so với toàn
bộ đối tượng không? Theo cách này, sai sót dữ liệu hay sai lệch so với giá trị thông thường được
phát hiện.
Vì những nhiệm vụ này yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng
thường ảnh hưởng đến việc thiết kế và chọn phương pháp khai phá dữ liệu khác nhau. Ví dụ như
phương pháp cây quyết định (sẽ được trình bày dưới đây) tạo ra được một mô tả phân biệt được các
mẫu giữa các lớp nhưng không có tính chất và đặc điểm của lớp.
2.5. Các phƣơng pháp khai phá dữ liệu
Khai phá dữ liệu là lĩnh vực mà con người luôn tìm cách đạt được mực đích sử dụng thông
tin của mình. Quá trình khai phá dữ liệu là quá trình phát hiện mẫu, trong đó phương pháp khai phá
dữ liệu để tìm kiếm các mẫu đáng quan tâm theo dạng xác định. Có thể kể ra đây một vài phương
pháp như: sử dụng công cụ truy vấn, xây dựng cây quyết định, dựa theo khoảng cách (K-láng giềng
gần), giá trị trung bình, phát hiện luật kết hợp, … Các phương pháp trên có thể được phỏng theo và
được tích hợp vào các hệ thống lai để khai phá dữ liệu theo thống kê trong nhiều năm nghiên cứu.
18
Tuy nhiên, với dữ liệu rất lớn trong kho dữ liệu thì các phương pháp này cũng đối diện với thách
thức về mặt hiệu quả và quy mô.
2.5.1.
Các thành phần của giải thuật khai phá dữ liệu
Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, kiểm
định mô hình và phương pháp tìm kiếm.
Biểu diễn mô hình: Mô hình được biểu diễn theo một ngôn ngữ L nào đó để miêu tả các mẫu
có thể khai thác được. Mô tả mô hình rõ ràng thì học máy sẽ tạo ra mẫu có mô hình chính xác cho
dữ liệu. Tuy nhiên, nếu mô hình quá lớn thì khả năng dự đoán của học máy sẽ bị hạn chế. Như thế
sẽ làm cho việc tìm kiếm phức tạp hơn cũng như hiểu được mô hình là không đơn giản hoặc sẽ
không thể có các mẫu tạo ra được một mô hình chính xác cho dữ liệu. Ví dụ mô tả cây quyết định
sử dụng phân chia các nút theo 1 trường dữ liệu, chia không gian đầu vào thành các siêu phẳng song
song với trục các thuộc tính. Phương pháp cây quyết định như vậy không thể khai phá được dữ liệu
dạng công thức X = Y dù cho tập học có quy mô lớn thế nào đi nữa. Vì vậy, việc quan trọng là
người phân tích dữ liệu cần phải hiểu đầy đủ các giả thiết miêu tả. Một điều cũng khá quan trọng là
người thiết kế giải thuật cũng phải diễn tả được các giả thiết mô tả nào được tạo ra bởi giải thuật
nào. Khả năng miêu tả mô hình càng lớn thì càng làm tăng mức độ nguy hiểm do bị học quá và làm
giảm đi khả năng dự đoán các dữ liệu chưa biết. Hơn nữa, việc tìm kiếm sẽ càng trở lên phức tạp
hơn và việc giải thích mô hình cũng khó khăn hơn.
Mô hình ban đầu được xác định bằng cách kết hợp biến đầu ra (phụ thuộc) với các biến độc
lập mà biến đầu ra phụ thuộc vào. Sau đó phải tìm những tham số mà bài toán cần tập trung giải
quyết. Việc tìm kiếm mô hình sẽ đưa ra được một mô hình phù hợp với tham số được xác định dựa
trên dữ liệu (trong một số trường hợp khác thì mô hình và các tham số lại thay đổi để phù hợp với
dữ liệu). Trong một số trường hợp, tập các dữ liệu được chia thành tập dữ liệu học và tập dữ liệu
thử. Tập dữ liệu học được dùng để làm cho tham số của mô hình phù hợp với dữ liệu. Mô hình sau
đó sẽ được đánh giá bằng cách đưa các dữ liệu thử vào mô hình và thay đổi các tham số cho phù
hợp nếu cần. Mô hình lựa chọn có thể là phương pháp thống kê như SASS, … một số giải thuật học
máy (ví dụ như cây quyết định và các quyết định học có thầy khác), mạng neuron, suy diễn hướng
tình huống (case based reasoning), các kỹ thuật phân lớp.
Kiểm định mô hình (model evaluation): Là việc đánh giá, ước lượng các mô hình chi tiết,
chuẩn trong quá trình xử lý và phát hiện tri thức với sự ước lượng có dự báo chính xác hay không
và có thoả mãn cơ sở logic hay không? Ước lượng phải được đánh giá chéo (cross validation) với
việc mô tả đặc điểm bao gồm dự báo chính xác, tính mới lạ, tính hữu ích, tính hiểu được phù hợp
với các mô hình. Hai phương pháp logic và thống kê chuẩn có thể sử dụng trong mô hình kiểm
định.
Phương pháp tìm kiếm: Phương pháp này bao gồm hai thành phần: tìm kiếm tham số và tìm
kiếm mô hình. Trong tìm kiếm tham số, giải thuật cần tìm kiếm các tham số để tối ưu hóa các tiêu
19
chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một mô tả mô hình đã định. Việc
tìm kiếm không cần thiết đối với một số bài toán khá đơn giản: các đánh giá tham số tối ưu có thể
đạt được bằng các cách đơn giản hơn. Đối với các mô hình chung thì không có các cách này, khi đó
giải thuật “tham lam” thường được sử dụng lặp đi lặp lại. Ví dụ như phương pháp giảm gradient
trong giải thuật lan truyền ngược (backpropagation) cho các mạng neuron. Tìm kiếm mô hình xảy
ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: mô tả mô hình bị thay đổi tạo nên
một họ các mô hình. Với mỗi một mô tả mô hình, phương pháp tìm kiếm tham số được áp dụng để
đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm
kiếm heuristic vì kích thước của không gian các mô hình có thể thường ngăn cản các tìm kiếm tổng
thể, hơn nữa các giải pháp đơn giản (closed form) không dễ đạt được.
2.5.2.
Phương pháp suy diễn / quy nạp
Một cơ sở dữ liệu là một kho thông tin nhưng các thông tin quan trọng hơn cũng có thể được
suy diễn từ kho thông tin đó. Có hai kỹ thuật chính để thực hiện việc này là suy diễn và quy nạp.
Phương pháp suy diễn: Nhằm rút ra thông tin là kết quả logic của các thông tin trong cơ sở
dữ liệu. Ví dụ như toán tử liên kết áp dụng cho bảng quan hệ, bảng đầu chứa thông tin về các nhân
viên và phòng ban, bảng thứ hai chứa các thông tin về các phòng ban và các trưởng phòng. Như vậy
sẽ suy ra được mối quan hệ giữa các nhân viên và các trưởng phòng. Phương pháp suy diễn dựa trên
các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất được bằng cách
sử dụng phương pháp này thường là các luật suy diễn.
Phương pháp quy nạp: phương pháp quy nạp suy ra các thông tin được sinh ra từ cơ sở dữ
liệu. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức
đã biết trước. Các thông tin mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao
diễn tả về các đối tượng trong cơ sở dữ liệu. Phương pháp này liên quan đến việc tìm kiếm các mẫu
trong CSDL. Trong khai phá dữ liệu, quy nạp được sử dụng trong cây quyết định và tạo luật.
2.5.3.
Phương pháp ứng dụng K-láng giềng gần
Sự miêu tả các bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều chiều là rất có ích đối
với việc phân tích dữ liệu. Việc dùng các miêu tả này, nội dung của vùng lân cận được xác định,
trong đó các bản ghi gần nhau trong không gian được xem xét thuộc về lân cận (hàng xóm – láng
giềng) của nhau. Khái niệm này được dùng trong khoa học kỹ thuật với tên gọi K-láng giềng gần,
trong đó K là số láng giềng được sử dụng. Phương pháp này rất hiệu quả nhưng lại đơn giản. Ý
tưởng thuật toán học K-láng giềng gần là “thực hiện như các láng giềng gần của bạn đã làm”.
Ví dụ: Để dự đoán hoạt động của cá thể xác định, K-láng giềng tốt nhất của cá thể được xem
xét, và trung bình các hoạt động của các láng giềng gần đưa ra được dự đoán về hoạt động của cá
thể đó.
20
Kỹ thuật K-láng giềng gần là một phương pháp tìm kiếm đơn giản. Tuy nhiên, nó có một
số mặt hạn chế giới là hạn phạm vi ứng dụng của nó. Đó là thuật toán này có độ phức tạp tính toán
là luỹ thừa bậc 2 theo số bản ghi của tập dữ liệu.
Vấn đề chính liên quan đến thuộc tính của bản ghi. Một bản ghi gồm hiều thuộc tính độc
lập, nó bằng một điểm trong không gian tìm kiếm có số chiều lớn. Trong các không gian có số
chiều lớn, giữa hai điểm bất kỳ hầu như có cùng khoảng cách. Vì thế mà kỹ thuật K-láng giềng
không cho ta thêm một thông tin có ích nào, khi tất cả các cặp điểm đều là các láng giềng. Cuối
cùng, phương pháp K-láng giềng không đưa ra lý thuyết để hiểu cấu trúc dữ liệu. Hạn chế đó có thể
được khắc phục bằng kỹ thuật cây quyết định.
2.5.4.
Phương pháp sử dụng cây quyết định và luật
Với kỹ thuật phân lớp dựa trên cây quyết định, kết quả của quá trình xây dựng mô hình sẽ
cho ra một cây quyết định. Cây này được sử dụng trong quá trình phân lớp các đối tượng dữ liệu
chưa biết hoặc đánh giá độ chính xác của mô hình. Tương ứng với hai giai đoạn trong quá trình
phân lớp là quá trình xây dựng và sử dụng cây quyết định.
Quá trình xây dựng cây quyết định bắt đầu từ một nút đơn biểu diễn tất cả các mẫu dữ liệu.
Sau đó, các mẫu sẽ được phân chia một cách đệ quy dựa vào việc lựa chọn các thuộc tính. Nếu các
mẫu có cùng một lớp thì nút sẽ trở thành lá, ngược lại ta sử dụng một độ đo thuộc tính để chọn ra
thuộc tính tiếp theo làm cơ sở để phân chia các mẫu ra các lớp. Theo từng giá trị của thuộc tính vừa
chọn, ta tạo ra các nhánh tương ứng và phân chia các mẫu vào các nhánh đã tạo. Lặp lại quá trình
trên cho tới khi tạo ra được cây quyết định, tất cả các nút triển khai thành lá và được gán nhãn.
Quá trình đệ quy sẽ dừng lại khi một trong các điều kiện sau được thỏa mãn:
-
-
-
Tất cả các mẫu thuộc cùng một nút.
Không còn một thuộc tính nào để lựa chọn.
Nhánh không chứa mẫu nào.
Phần lớn các giải thuật sinh cây quyết định đều có hạn chế chung là sử dụng nhiều bộ nhớ.
Lượng bộ nhớ sử dụng tỷ lệ thuận với kích thước của mẫu dữ liệu huấn luyện. Một chương trình
sinh cây quyết định có hỗ trợ sử dụng bộ nhớ ngoài song lại có nhược điểm về tốc độ thực thi. Do
vậy, vấn đề tỉa bớt cây quyết định trở nên quan trọng. Các nút lá không ổn định trong cây quyết
định sẽ được tỉa bớt.
Kỹ thuật tỉa trước là việc dừng sinh cây quyết định khi chia dữ liệu không có ý nghĩa.
2.5.5.
Phương pháp phát hiện luật kết hợp
Phương pháp này 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. Mẫu đầu ra của giải thuật khai phá dữ liệu là tập luật kết hợp tìm được. Ta có thể lấy một ví
dụ đơn giản về luật kết hợp như sau: sự kết hợp giữa hai thành phần A và B có nghĩa là sự xuất hiện
của A trong bản ghi kéo theo sự xuất hiện của B trong cùng bản ghi đó: A => B.
Tải về để xem bản đầy đủ
78 trang
14360
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Khai phá dữ liệu - Trường Đại học Hàng Hải", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_khai_pha_du_lieu_truong_dai_hoc_hang_hai.pdf
