ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN HẠNH PHÚC

ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG
KHAI THÁC CƠ SỞ DỮ LIỆU TÍCH HỢP
NGÀNH GIAO THÔNG VẬN TẢI

LUẬN VĂN THẠC SĨ

HÀ NỘI - 2006


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN HẠNH PHÚC

ỨNG DỤNG KHAI PHÁ DỮ LIỆU TRONG
KHAI THÁC CƠ SỞ DỮ LIỆU TÍCH HỢP
NGÀNH GIAO THÔNG VẬN TẢI

Ngành

: CÔNG NGHỆ THÔNG TIN

Mã số

: 1.01.10


MỞ ĐẦU.................................................................................................................5
CHƢƠNG 1 - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU..................................... 7
1. Tổ chức và khai thác cơ sở dữ liệu truyền thống................................................7
2. Tổng quan về kỹ thuật phát hiện tri thức và khai phá dữ liệu.............................8
2.1. Phát hiện tri thức và khai phá dữ liệu là gì?.....................................................8
2.2. Qui trình phát hiện tri thức [7].........................................................................9
2.3. Các phƣơng pháp khai phá dữ liệu [7]..........................................................10
2.4. Các lĩnh vực liên quan đến phát hiện tri thức và khai phá dữ liệu [7]...........12
3. Các nhiệm vụ trong khai phá dữ liệu................................................................12
3.1. Phát hiện các luật tối ƣu truy vấn ngữ nghĩa.................................................13
3.2. Phát hiện sự phụ thuộc CSDL (Database Dependencies)..............................14
3.3. Phát hiện sự sai lệch (Deviation)...................................................................14
3.4. Phát hiện luật kết hợp (Association Rules)....................................................14
3.5. Mô hình hoá sự phụ thuộc (Dependence Modeling).....................................15
3.6. Mô hình hoá nhân quả (Causation Modeling)...............................................15
3.7. Phân cụm, nhóm (Clustering) [6]..................................................................16
3.8. Phân lớp (Classification)...............................................................................16
3.9. Hồi quy (Regression).....................................................................................17
3.10. Tổng hợp (Sumarization).............................................................................17
3.11. So sánh các nhiệm vụ phát hiện tri thức......................................................17
4. Phân lớp dữ liệu................................................................................................20
4.1. Khái niệm về phân lớp...................................................................................20
4.2. Ứng dụng của phân lớp..................................................................................21
4.3. Các vấn đề nghiên cứu trong phân lớp..........................................................22
4.4. Các yêu cầu đối với bài toán phân lớp...........................................................23
5. Một số phƣơng pháp phân lớp.........................................................................24
5.1. Phƣơng pháp phân hoạch..............................................................................25
5.2. Phân lớp dựa trên cây quyết định [6].............................................................25
5.3. Phƣơng pháp dựa vào mật độ........................................................................27
5.4. Phân lớp và mạng nơron nhân tạo.................................................................28

Cải tiến 1 - Giảm số lƣợng các luật đƣợc phát sinh & cần ph
4.2.
Cải tiến 1.a – Tránh phát sinh các luật không có ý nghĩa ......
4.3.
Một số kỹ thuật khác trong việc tối ƣu hóa chi phí tính độ co
5. Đánh giá, nhận xét .............................................................................................
CHƢƠNG 3 - ỨNG DỤNG, THỬ NGHIỆM KHAI PHÁ DỮ LIỆU TÍCH
HỢP NGÀNH GIAO THÔNG VẬN TẢI............................................................
1. Bài toán .............................................................................................................
1.1.
Phát biểu bài toán ..................................................................
1.2.
Đặc tả dữ liệu ........................................................................
1.3.
Minh họa chƣơng trình ...........................................................
1.4.
Phân tích, đánh giá ................................................................
2. Hƣớng phát triển ...............................................................................................
KẾT LUẬN ...........................................................................................................
TÀI LIỆU THAM KHẢO.....................................................................................


4

DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Từ viết tắt
Ck
Conf
CSDL
DW

MỞ ĐẦU
Trong những năm gần đây, việc nắm bắt đƣợc thông tin đƣợc coi là cơ
sở của mọi hoạt động sản xuất, kinh doanh. Cá nhân hoặc tổ chức nào thu
thập và hiểu đƣợc thông tin, và hành động dựa trên các thông tin đƣợc kết
xuất từ các thông tin đã có sẽ đạt đƣợc thành công trong mọi hoạt động.
Chính vì lý do đó, việc tạo ra thông tin, tổ chức lƣu trữ và khai thác ngày
càng trở nên quan trọng và gia tăng không ngừng.
Sự tăng trƣởng vƣợt bậc của các cơ sở dữ liệu (CSDL) trong cuộc sống
nhƣ: thƣơng mại, quản lý và khoa học đã làm nảy sinh và thúc đẩy sự phát
triển của kỹ thuật thu thập, lƣu trữ, phân tích và khai phá dữ liệu… không chỉ
bằng các phép toán đơn giản thông thƣờng nhƣ: phép đếm, thống kê… mà đòi
hỏi cách xử lý thông minh hơn, hiệu quả hơn. Từ đó các nhà quản lý có đƣợc
thông tin có ích để tác động lại quá trình sản xuất, kinh doanh của mình… đó
là tri thức. Các kỹ thuật cho phép ta khai thác đƣợc tri thức hữu dụng từ
CSDL (lớn) đƣợc gọi là các kỹ thuật khai phá dữ liệu (DM – Data Mining).
Khai phá luật kết hợp là một nội dung quan trọng trong khai phá dữ liệu.
Luận văn nghiên cứu về những khái niệm cơ bản về khai phá dữ liệu,
luật kết hợp và ứng dụng một số thuật toán khai phá luật kết hợp trong CSDL
lớn.
Luận văn có cấu trúc nhƣ sau:
CHƢƠNG I - TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÁT
HIỆN TRI THỨC
Trình bày kiến thức tổng quan về khai thác và xử lý thông tin.
Định nghĩa kho dữ liệu, khai phá dữ liệu, các phƣơng pháp khai phá dữ
liệu phổ biến và ứng dụng của chúng.
CHƢƠNG II - CƠ SỞ LÝ THUYẾT LUẬT KẾT HỢP. ỨNG DỤNG
LUẬT KẾT HỢP VÀO KHAI PHÁ DỮ LIỆU
Trình bày các bài toán trong khai phá dữ liệu, phát hiện luật kết hợp
Khái niệm về luật kết hợp và các phƣơng pháp khai phá luật kết hợp.
Khai phá luật kết hợp dựa trên sự phân chia không gian tìm kiếm.

cao cùng với sự phát triển của các hệ thống viễn thông, ngƣời ta đã và đang
xây dựng các hệ thống thông tin nhằm tự động hoá mọi hoạt động của con
ngƣời. Điều này đã tạo ra một dòng dữ liệu tăng lên không ngừng vì ngay cả
những hoạt động đơn giản nhƣ gọi điện thoại, tra cứu sách trong thƣ viện, ...
đều đƣợc thực hiện thông qua máy tính. Cho đến nay, số lƣợng CSDL đã trở
nên khổng lồ bao gồm các CSDL cực lớn cỡ gigabytes và thậm chí terabytes
lƣu trữ các dữ liệu kinh doanh ví dụ nhƣ dữ liệu thông tin khác hàng , dữ liệu
bán hàng, dữ liệu các tài khoản, ... Nhiều hệ quản trị CSDL mạnh với các
công cụ phong phú và thuận tiện đã giúp con ngƣời khai thác có hiệu quả
nguồn tài nguyên dữ liệu. Mô hình CSDL quan hệ và ngôn ngữ vấn đáp chuẩn
(SQL) đã có vai trò hết sức quan trọng trong việc tổ chức và khai thác CSDL.
Cho đến nay, không một tổ chức nào sử dụng tin học trong công việc mà
không sử dụng các hệ quản trị CSDL và các hệ công cụ báo cáo, ngôn ngữ hỏi
đáp nhằm khai thác CSDL phục vụ cho các hoạt động tác nghiệp của mình.
Cùng với việc tăng không ngừng khối lƣợng dữ liệu, các hệ thống thông tin
cũng đƣợc chuyên môn hoá, phân chia theo lĩnh vực ứng dụng nhƣ sản xuất,
tài chính, hoạt động kinh doanh, .... Nhƣ vậy bên
cạnh chức năng khai thác dữ liệu có tính chất tác nghiệp, sự thành công trong
công việc không còn là năng suất của các hệ thống thông tin nữa mà là tính
linh hoạt và sẵn sàng đáp lại những yêu cầu trong thực tế, CSDL cần đem lại
những “tri thức” hơn là chính những dữ liệu trong đó. Các quyết định cần phải
có càng nhanh càng tốt và phải chính xác dựa trên những dữ liệu sẵn có trong
khi khối lƣợng dữ liệu cứ sau 20 tháng lại tăng gấp đôi làm ảnh hƣởng


8

đến thời gian ra quyết định cũng nhƣ khả năng hiểu hết đƣợc nội dung dữ
liệu. Lúc này, các mô hình CSDL truyền thống và ngôn ngữ SQL đã cho thấy
không có khả năng thực hiện công việc này. Để lấy thông tin có tính “tri thức”

giữa chúng. Các mối quan hệ này có thể đƣợc hiểu ra,


9

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.
Phát hiện tri thức trong các cơ sở dữ liệu là một qui 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: hợp thức, mới, khả ích,
và có thể hiểu đƣợc. Còn khai thác dữ liệu là một bƣớc trong qui trình phát
hiện 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 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 vẫn còn bị che khuất bởi hàng núi dữ liệu.
Định nghĩa: “KDD là quá trình không tầm thƣờng nhận ra những mẫu có
giá trị, mới, hữu ích tiềm năng và hiểu đƣợc trong dữ liệu”. [7]
Còn các nhà thống kê thì xem Khai phá dữ liệu nhƣ là một qui trình
phân tích đƣợc thiết kế để thăm dò một lƣợng cực lớn các dữ liệu nhằm phát
hiện ra các mẫu thích hợp và/hoặc các mối quan hệ mang tính hệ thống giữa
các biến và sau đó sẽ hợp thức hoá các kết quả tìm đƣọc bằng cách áp dụng
các mẫu đã phát hiện đƣợc cho các tập con mới của dữ liệu. Qui trình này bao
gồm ba giai đoạn cơ bản: thăm dò, xây dựng mô hình hoặc định nghĩa mẫu,
hợp thức/kiểm chứng.
2.2. Qui trình phát hiện tri thức [7]
Qui trình phát hiện tri thức đƣợc mô tả tóm tắt trên Hình 1:

Hình 1. Quy trình phát hiện tri thức



Phân lớp, phân loại (Classification): Là việc học 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 xác định trƣớc đó.
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.


11

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.
Tổng hợp (Summarization): Là công việc lên quan đến các phƣơng
pháp tìm kiếm một mô tả tập con dữ liệu, 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.
Mô hình ràng buộ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: phụ thuộc cục
bộ vào cấu trúc của mô hình, phụ thuộc vào thƣớc đo, ƣớc lƣợng của một
định lƣợng nào đó.
Dò tìm biến đổi và độ lệch (Change and Deviation Dectection): Chú ý
vào những thay đổi quan trọng trong dữ liệu từ các giá trị chuẩn hoặc đã đƣợc
xác định trƣớc đó.
Biểu diễn mô hình (Model Representation): Là việc dùng một ngôn
ngữ L_ Language nào đó để mô tả các mẫu mô hình có thể khai phá đƣợ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.
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ả

Đ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ụ, ...
3. Các nhiệm vụ trong khai phá dữ liệu
Do sự phát triển mạnh mẽ của các loại hệ thống phát hiện tri thức trong
CSDL (KDD) theo yêu cầu nhằm đáp ứng những đòi hỏi trong nhiều lĩnh vực
khác nhau, việc phát hiện tri thức cũng trở lên đa dạng hơn. Do đó, nhiệm vụ


13

của phát hiện tri thức trong CSDL cũng trở lên phong phú và có thể phát hiện
rất nhiều kiểu tri thức khác nhau. Một trong các bƣớc đầu tiên trong quá trình
phát hiện tri thức trong CSDL là quyết định xem loại kiến thức nào mà thuật
toán phát hiện tri thức trong CSDL cần phải kết xuất từ dữ liệu. Do đó, vệc
phân loại và so sánh các kiểu nhiệm vụ phát hiện tri thức trong CSDL là vấn
đề đáng quan tâm nhằm tạo ra một hệ thống phát hiện tri thức trong CSDL
hữu ích. Ta sẽ xem xét một số kiểu nhiệm vụ phát hiện tri thức sau:
3.1. Phát hiện các luật tối ƣu truy vấn ngữ nghĩa (Sematics Query
Optimization – SQO Rules)
Các luật tối ƣu truy vấn CSDL thông thƣờng thực hiện một phép biến

3.2. Phát hiện sự phụ thuộc CSDL (Database Dependencies)
Trong mô hình dữ liệu quan hệ, chúng ta đã nghiên cứu quan hệ trong
CSDL quan hệ không tính đến quan hệ giữa các thuộc tính. Các quan hệ này
thƣờng đƣợc thể hiện thông qua sự phụ thuộc dữ liệu hoặc ràng buộc toàn vẹn.
Ở đây sẽ sử dụng thuật ngữ phụ thuộc CSDL để chỉ sự phụ thuộc dữ liệu kiểu
này. Sự phụ thuộc CSDL đƣợc sử dụng trong thiết kế và duy trì một CSDL.
Phƣơng pháp phát hiện tự động các sự phụ thuộc CSDL này chính là một kiểu
nhiệm vụ của Khai phá dữ liệu.

3.3. Phát hiện sự sai lệch (Deviation)
Nhiệm vụ này nhằm phát hiện sự sai 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 sai lệch hay dùng là mô
hình sai lệch theo thời gian và sai lệch nhóm. Sai lệch theo thời gian là sự thay
đổi có ý nghĩa của dữ liệu theo thời gian. Sai lệch theo nhóm là sự khác nhau
không chờ đợi giữa dữ liệu trong hai tập con dữ liệu, ở đây tính đến cả trƣờng
hợp tập con này thuộc trong tập con kia, nghĩa là 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, các sai sót dữ liệu hay sự sai lệch so với giá trị thông thƣờng
đƣợc phát hiện.
3.4. Phát hiện luật kết hợp (Association Rules)
Ta xét một ví dụ: Xét một tập các mặt hàng trong một giỏ mua hàng.
Vấn đề đặt ra là tìm những mối liên quan giữa các mặt hàng trong giỏ.
Một cách chi tiết hơn, xét một tập các thuộc tính nhị phân với một tập
các bộ, mỗi bộ đƣợc gọi là một giỏ. Các thuộc tính nhị phân đƣợc gọi là các
mục hay các mặt hàng trong giỏ mà mỗi mục chỉ nhận một trong hai giá trị
đúng hoặc sai tuỳ thuộc vào khách hàng có mua mặt hàng đó trong giao dịch
hay không. Trên thực tế, loại dữ liệu này rất phổ biến và đƣợc gọi là dữ liệu
giỏ. Chúng thƣờng đƣợc thu thập thông qua công nghệ mã số, mã vạch trong
các hoạt động kinh doanh siêu thị.
Một giao dịch có thể chứa một số khoản mục, tập hợp tất cả các khoản

Nhiệm vụ này liên quan đến việc phát hiện mối quan hệ nhân quả trong
thuộc tính. Các luật nhân quả cũng là các luật “nếu - thì” giống các luật phụ
thuộc, nhƣng mạnh hơn. Luật phụ thuộc đơn giản chỉ ra một mối tƣơng hỗ
giữa tiên đề và kết luận của luật mà không có ý nghĩa nhân quả trong quan hệ
này. Do đó, cả tiên đề và kết luận có thể quan hệ dƣới sự ảnh hƣởng của một
biến thứ ba, tức là một thuộc tính hoặc có ở trong tiên đề hoặc có ở trong kết
luận. Luật nhân quả không chỉ chỉ ra mối tƣơng quan giữa tiên đề và kết luận
mà còn cho biết tiên đề thực sự tạo ra kết luận và mối quan hệ giữa hai thành
phần này là trực tiếp. Tập các mối quan hệ nhân quả có thể đƣợc biểu diến
bằng đồ thị nhân quả.


16

Thuật toán phát hiện các luật nhân quả CAUDISCO áp dụng các phép
kiểm tra sự độc lập thống kê của từng cặp thuộc tính. Sau đó, đối với các
thuộc tính phụ thuộc lẫn nhau, thuật toán sẽ xác định mối quan hệ có là xác
thực, tiềm năng hay chỉ là một liên kết giả tạo, không phụ thuộc vào tập các
điều kiện thoả mãn bởi quan hệ nhân quả.
Các quan hệ nhân quả cần phụ thuộc vào thời gian theo nghĩa là nguyên
nhân trƣớc kết quả (kết luận). Nguyên nhân và kết quả đều có ít nhất một sự
kiện thời gian đi kèm và thời gian của kết quả phải đi sau thời gian của
nguyên nhân. Mặc dù yếu tố thời gian làm rõ ý nghĩa nhân quả nhƣng hệ
thống thƣờng khó phân biệt các liên kết giả tạo.
3.7. Phân cụm, nhóm (Clustering) [6]
Một nhiệm vụ của các hệ thống phát hiện tri thức là phân tích các đối
tƣợng dữ liệu dạng nhƣ các giỏ hàng mà không quan tâm tới lớp của chúng.
Các hệ thống này phải tự phát hiện ra các lớp và sinh ra một sơ đồ phân nhóm
của tập dữ liệu đó.
Tuy nhiên, chất lƣợng của việc phân nhóm này là một vấn dề khó có thể

hoá cũng đƣợc sử dụng, chẳng hạn nhƣ cây quyết định, trong đó nút lá là mô
hình tuyến tính phát sinh tập các lớp giả (pseudo - class) có giá trị thuộc tính
đích tƣơng tự nhau, sau đó sử dụng phƣơng pháp quy nạp để thay thế các lớp
trong luật quy nạp bằng tổ hợp các giá trị của thuộc tính lớp cho các bộ dữ
liệu theo luật.
3.10. Tổng hợp (Sumarization)
Nhiệm vụ tổng hợp chính là sản sinh ra các mô tả đặc trƣng cho một lớp.
Mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả
(hoặc hầu hết) các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp.
Các mô tả đặc trƣng thể hiện dƣới dạng luật có dạng sau: ”nếu một bộ
dữ liệu thuộc về một lớp đã chỉ ra trong tiên đề, thì bộ dữ liệu đó có tất cả các
thuộc tính đã nêu trong kết luận”. Cần lƣu ý là các luật này có những đặc
trƣng khác biệt so với luật phân lớp. Luật phát hiện đặc trƣng cho một lớp chỉ
sản sinh khi các bộ dữ liệu đã thuộc về lớp đó.
3.11. So sánh các nhiệm vụ phát hiện tri thức.
Điểm giống và khác giữa các nhiệm vụ phát hiện tri thức đƣợc tóm tắt
trong bảng sau:
Nhiệm vụ
SQO
Sự phụ thuộc CSDL
Phát hiện sai lệch
Phát hiện liên kết


18

Nhiệm vụ
Nhân quả
Phân nhóm
Phân lớp

sự phụ thuộc.


19

Ta sử dụng thuật ngữ xác định trội (highlighting) để xác định các mẫu,
những quy luật hay những bất thƣờng đặc biệt trong dữ liệu. Tính chất cơ bản
của các mẫu đặc biệt này là chúng có một giá trị bất ngờ hoặc tần suất tƣơng
đối không mong đợi. Hơn nữa, khác với tri thức đƣợc phát hiện cho các mục
đích mô tả, các mẫu này không cần thiết thể hiện dƣới dạng trừu tƣợng. Ví dụ
điển hình là thăm dò sự sai khác với thông tin đƣợc phát hiện chỉ đơn giản là
danh sách các điểm dữ liệu lệch ra ngoài. Nhiệm vụ phát hiện luật liên kết có
thể đƣợc xem là một dạng xác định trội, bởi lẽ, một trong các đòi hỏi rõ ràng
của luật liên kết là tần suất tƣơng đối tối thiểu (giá trị support) trong dữ liệu.
Cột thứ tƣ chỉ ra loại dự báo liên quan đến từng nhiệm vụ phát hiện tri
thức. Mặc dù các nhiệm vụ SQO và sự phụ thuộc CSDL phát hiện tri thức
hƣớng CSDL và theo mục tiêu cụ thể, nhƣng cũng có các nhiệm vụ dự báo
liên quan đến kiểu này. Nói chung, các nhiệm vụ SQO, sự phụ thuộc CSDL,
liên kết, nhân quả, sự phụ thuộc và phân cụm có kiểu dự báo nhiều - nhiều
trong đó giá trị của một vài thuộc tính có thể dùng để dự báo giá trị của các
thuộc tính khác. Một cách nhìn khác về quan hệ nhiều - nhiều là xem xét các
nhiệm vụ nhƣ một dạng phát hiện không có học, bởi vì ngƣời dùng không chỉ
ra thuộc tính mục tiêu và hệ thống có sự tự chủ hoàn toàn để quyết định thuộc
tính nào sẽ đƣợc đƣa ra trong tri thức. Nhiệm vụ phát hiện sự sai khác không
hoàn toàn đúng với mục tiêu dự báo nhƣng có thể nói nó liên quan đến việc
phát hiện không có học.
Nhiệm vụ phân lớp và hồi quy liên quan đến dự báo nhiều - một trong đó
giá trị của nhiều thuộc tính có thể đƣợc sử dụng để dự báo giá trị của một
thuộc tính do ngƣời dùng xác định trƣớc. Đối với nhiệm vụ tổng hợp, từ lớp
của một bộ dữ liệu, chúng ta có thể dự báo giá trị (hoặc khoảng giá trị, giá trị

định một đối tƣợng mới vào lớp của nó. Thay vào đó trong quá trình phân lớp
ta không hề biết trƣớc tính chất của các lớp mà phải dựa vào mối quan hệ
giữa các đối tƣợng để tìm ra sự giống nhau giữa các đối tƣợng theo một độ
đo nào đó đặc trƣng cho lớp.
Việc phân lớp không bao giờ sử dụng độc lập mà nó thƣờng đƣợc sử
dụng kèm với các phƣơng pháp khác. Khi một cách phân lớp đƣợc đƣa ra
cũng phải có một phƣơng pháp áp dụng để đƣa ra ý nghĩa của lớp đó.
Quá trình phân lớp đƣợc chia làm hai giai đoạn. Ta có thể hình dung về
quá trình này qua hình vẽ sau:


21

Xây dựng mô hình

Sử dụng mô hình để dự
báo

Dữ liệu huấn
luyện

Hình 2: Các giai đoạn của quá trình phân lớp

Giai đoạn xây dựng mô hình có nhiệm vụ mô tả một tập hợp các lớp đã
xác định trƣớc. Giả sử ta có một tập các bộ dữ liệu đƣợc giả định rằng đã
thuộc vào một lớp đã xác định trƣớc. Lớp của mỗi bộ đƣợc chỉ ra trong thuộc
tính nhãn lớp của bộ đó. Tập dữ liệu này dùng để xây dựng mô hình và đƣợc
gọi là tập dữ liệu huấn luyện. Mô hình đƣợc xây dựng có thể là các luật phân
lớp, cây quyết định hoặc có thể là công thức toán học.
Trong giai đoạn sử dụng mô hình, mô hình đã đƣợc xác định đƣợc dùng

dữ liệu trong đó. Các thuật toán này thƣờng đòi hỏi thực hiện trên các lớp đã
đƣợc phát hiện.
4.3. Các vấn đề nghiên cứu trong phân lớp
Ngày nay, có nhiều vấn đề nghiên cứu về phân lớp trong các lĩnh vực
khác nhau nhƣ khai phá dữ liệu, thống kê, học máy, công nghệ dữ liệu không
gian, sinh học. Do kích thƣớc của các CSDL tăng lên rất nhanh, phân lớp
đang là vấn đề đƣợc quan tâm trong nghiên cứu về khai phá dữ liệu.
Trong lĩnh vực thống kê, phân lớp đã đƣợc nghiên cứu phát triển trong
nhiều năm, các vấn đề tập trung chủ yếu vào phân tích các lớp dựa vào
khoảng cách. Các công cụ phân tích lớp dựa trên một số phƣơng pháp nhƣ kmeans, k-medoids đã đƣợc xây dựng trong nhiều hệ thống phần mềm phân
tích thống kê nhƣ S-Plus, SPSS và SAS. Trong học máy, phân lớp là một ví
dụ về học không quan sát. Không giống nhƣ phân loại, phân lớp và học
không giám sát không dựa vào các lớp đã định nghĩa trƣớc và các mẫu đã
đƣợc gán nhãn trƣớc. Theo định nghĩa này, phân lớp là một dạng của học qua
quan sát hơn là học bằng mẫu.
Trong khai phá dữ liệu, các vấn đề nghiên cứu trong phân lớp chủ yếu
tập trung vào tìm kiếm các phƣơng pháp phân lớp hiệu quả và tin cậy trong
CSDL lớn. Các yêu cầu đặt ra đối với các phƣơng pháp phân lớp đó là độ
hiệu quả (effectiveness) và độ tuyến tính (scalability) của thuật toán, khả năng
làm việc với các kiểu dữ liệu và các lớp có hình dạng phức tạp, các kĩ thuật
phân lớp nhiều chiều và các phƣơng pháp phân lớp gồm dữ liệu số và dữ liệu
xác thực trong CSDL lớn.


23

4.4. Các yêu cầu đối với bài toán phân lớp
Phân lớp luôn là vấn đề nghiên cứu với nhiều thách thức bởi các ứng
dụng của nó thƣờng đòi hỏi rất nhiều các yêu cầu đặc biệt. Sau đây là các yêu
cầu chính đối với phân lớp trong khai phá dữ liệu:

Không phụ thuộc vào thứ tự của các bản ghi đầu vào: Một số thuật
toán phân lớp là rất nhạy cảm với thứ tự dữ liệu đầu vào. Cùng một tập dữ
liệu, khi biểu diễn với thứ tự khác nhau đối với các thuật toán có thể tạo ra
những lớp rất khác nhau. Nhƣ vậy yêu cầu thuật toán không phụ thuộc vào
thứ tự đầu vào dữ liệu là rất quan trọng.