BỘ GIÁO DỤC VÀ ĐÀO ĐẠO

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

NGUYỄN TIẾN TUỆ

MỘT SỐ THUẬT TOÁN PHÂN CỤM MỜ

VÀ ỨNG DỤNG PHÂN CỤM WEBSITE

LUẬN VĂN THẠC SĨ KHOA HỌC

CHUYÊN NGÀNH: ĐẢM BẢO TOÁN HỌC CHO MÁY TÍNH VÀ

HỆ THỐNG TÍNH TOÁN

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TSKH Bùi Công Cường

Hà Nội, Năm 2010

LỜI CẢM ƠN

Nhân dịp hoàn thành khóa luận tốt nghiệp, cho phép tôi được bày tỏ lòng tri

ân tới toàn thể quý thầy, cô giáo của trường ĐHBKHN nói chung, các thầy cô

giáo Khoa Toán Tin Ứng dụng – Trường ĐHBKHN, những người thầy đang

công tác tại Viện Toán học, Viện CNTT nói riêng đã truyền thụ các kiến thức

cho tôi trong những năm học cá nhân gắn bó với ngôi trường.

Tôi xin bày tỏ lòng cảm ơn sâu sắc đến PGS.TSKH Bùi Công Cường – người

thầy đã trực tiếp hướng dẫn, chỉ bảo tận tình và tạo mọi điều kiện cho tôi trong

suốt quá trình nghiên cứu và thực hiện luận văn.

Tôi xin gửi lời cảm ơn tới các đồng chí trong Ban Giám đốc Công an tỉnh

Hải Dương, các đồng chí Lãnh đạo Văn Phòng Công an tỉnh cùng toàn thể các

đồng chí trong đội Viễn thông – Tin học, Chuyên đề, Pháp chế,…đã đã kịp thời

động viên, khích lệ, tạo điều kiện thuận lợi để tôi có điều kiện nghiên cứu, tham

gia khóa học này.

Cuối cùng, tôi xin gửi lời cảm ơn chân thành nhất tới gia đình, người thân và

bạn bè, những người đã luôn sát cánh, động viên, chia sẻ và giúp đỡ tôi trong

suốt những chặng đường đã qua.

Xin trân trọng cảm ơn!

Tác giả

Nguyễn Tiến Tuệ

MỞ ĐẦU

Lý do chọn đề tài

Trước bối cảnh hội nhập toàn cầu, thế giới ngày càng “ phẳng”, đặc biệt là

sự bùng nổ của WWW, lượng thông tin đến với mỗi tổ chức, cá nhân là rất lớn.

Việc xử lý và khai thác các thông tin một cách hiệu quả là một yêu cầu bức

thiết.

Cũng khá tự nhiên khi một ngành khoa học: Kỹ thuật phát hiện tri thức và

khai phá dữ liệu (KDD - Knowledge Discovery and Data Mining) ra đời

nhằm giải quyết các bài toán trên. Bước quan trọng nhất của quá trình này là

Khai phá dữ liệu (Data Mining - DM), giúp người sử dụng thu được những

tri thức hữu ích từ những CSDL hoặc các nguồn dữ liệu khổng lồ khác.

Nhưng để làm được điều đó, sự phát triển của các mô hình toán học và các

thuật toán hiệu quả, đặc biệt là các thuật toán phân cụm là chìa khoá vô cùng

quan trọng. Trong nhiều năm qua, các nhà khoa học trên thế giới cũng như ở

Việt Nam đã đầu tư nghiên cứu và kết quả đã cho ra nhiều thuật toán hiệu quả

để giải quyết bài toán trên...Vì vậy, việc tìm hiểu và ứng dụng các thuật toán

phân cụm vào thực tế là một vấn đề rất được quan tâm.

Đó chính là lý do cá nhân tôi chọn đề tài: Một số thuật toán phân cụm mờ và

ứng dụng trong phân cụm Website.

2. Lịch sử nghiên cứu.

Hiện nay, chúng ta đang sống trong tình trạng “ giàu về dữ liệu, nghèo về

thông tin”. Việc nghiên cứu, phát triển và ứng dụng các thuật toán phân cụm là

điều đang rất được quan tâm. Trên thế giới việc nghiên cứu để giải quyết bài

toán này đã đi được một quãng đường khá xa, tuy nhiên trong nước nó mới được

quan tâm trong vài năm gần đây. Hiện nay, một số trường đại học như: ĐH Bách

Khoa, ĐH Công nghệ, ĐH Quốc gia,...vấn đề trên đã được đưa vào giảng dạy và

cũng có khá nhiều đề tài đề cập đến vấn đề phân cụm; phân cụm mờ và ứng

dụng. Tuy nhiên việc ứng dụng thuật toán phân cụm mờ cùng một số hướng mới

cải tiến giải thuật phân cụm và ứng dụng phân cụm website ở cả 2 chế độ sử

dụng Mathematica thì chưa có đề tài nào đề cập.

3. Mục đích, đối tượng, phạm vi nghiên cứu của luận văn

- Mục đích nghiên cứu: Đề tài sẽ đi tìm hiểu và nghiên cứu một số

thuật toán phân cụm dữ liệu, dữ liệu mờ nhằm tiến hành phân cụm

Website.

- Đối tượng nghiên cứu: Một số giải thuật phân cụm và các Website

- Phạm vi nghiên cứu: Đề tài nghiên cứu tập trung vào giải thuật

FCM và các Website ở 2 chế độ Online và Off line

4. Phương pháp nghiên cứu

- Phân tích tổng hợp và nghiên cứu hệ thống.

- Phân tích tài liệu.

- Thực nghiệm.

-..........................

5. Cấu trúc luận văn

Ngoài các phần Mở đầu, Mục lục, Kết luận, Tài liệu tham khảo,... luận văn

được chia làm 4 chương:

Chương I - Tổng quan về Phát hiện tri thức và Khai phá dữ liệu

Phần này giới thiệu một cách tổng quát về quá trình phát hiện tri thức nói

chung và khai phá dữ liệu nói riêng. Đặc biệt nhấn mạnh về 2 kỹ thuật chính

đó là kỹ thuật phân loại và kỹ thuật phân cụm.

Chương II – Một số thuật toán Phân cụm dữ liệu

Trình bày những khái niệm cơ bản nhất về phân cụm dữ liệu cũng như các

bước xây dựng mô hình cho bài toán phân cụm, đồng thời trình bày một số

thuật toán tiêu biểu trong PCDL chẳng hạn: BSAS, c-means,....đây là cơ sở, nền

tảng để ta nghiên cứu, mở rộng thuật toán phân cụm trong chương sau.

Chương III – Phân cụm mờ

Với mong muốn“mềm dẻo” hơn trong quá trình tính toán, trong chương này

sẽ đi sâu vào các bài toán Phân cụm mờ cùng một số chứng minh tính đúng đắn

của chúng. Sau đó là thuật toán cho bài toán này.

Chương IV – Ứng dụng Phân cụm mờ trong phân cụm Website

Phân cụm website đang là bài toán thu hút được sự quan tâm của nhiều nhà

khoa học, phần này trong khuôn khổ luận văn sẽ đi tiến hành từng bước qúa

trình thu thập, xử lý các trang Web, tìm kiếm các đặc trưng của chúng, sau đó

tiến hành phân cụm tập các kết quả đã tìm được dựa vào thuật toán trình bày

trong chương 3.

Cuối cùng là 1 phụ lục, sẽ giới thiệu sơ qua về Ngôn ngữ lập trình

Mathematica – đây là ngôn ngữ được sử dụng để lập trình trong luận văn, đồng

thời trong phần này trình bày các đoạn Code hoàn thiện thực hiện thuật toán: C-

means; FCM; tìm kiếm đặc trưng các Website và tiến hành phân cụm.

Chương 1 - TỔNG QUAN PHÁT HIỆN TRI THỨC VÀ KPDL

1.1

Giới thiệu chung

Trong những năm gần đây, sự phát triển mạnh mẽ của CNTT và

ngành công nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông

tin của các hệ thống thông tin tăng nhanh một cách đáng kể. Bên cạnh đó việc

tin học hoá một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh

cũng như nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ

liệu lưu trữ khổng lồ. Hàng triệu CSDL đã được sử dụng trong các hoạt động

sản xuất, kinh doanh, quản lí..., trong đó có nhiều CSDL cực lớn cỡ

Gigabyte, thậm chí là Terabyte. Sự bùng nổ này đã 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. Từ đó, các kĩ thuật khai phá dữ

liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay.

1.1.1 Khái niệm khai phá dữ liệu

Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những

năm cuối của thập kỷ 1980. Nó là quá trình trích xuất các thông tin có giá trị

tiềm ẩn bên trong lượng lớn dữ liệu được lưu trữ trong các CSDL, kho dữ

liệu... Hiện nay, ngoài thuật ngữ khai phá dữ liệu, người ta còn dùng một số

thuật ngữ khác có ý nghĩa tương tự như: khai phá tri thức từ CSDL, trích lọc

dữ liệu, phân tích dữ liệu/mẫu, khảo cổ dữ liệu, nạo vét dữ liệu. Nhiều người

coi Khai phá dữ liệu và một thuật ngữ thông dụng khác là Phát hiện tri thức

trong CSDL (Knowlegde Discovery in Databases - KDD) là như nhau. Tuy

nhiên trên thực tế, khai phá dữ liệu chỉ là một bước thiết yếu trong quá trình

Phát hiệ

n tri thức trong CSDL. Có thể nói Data Mining là giai đoạn quan

trọng nhất trong tiến trình Phát hiện tri thức từ cơ sở dữ liệu, các tri thức này

hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh.

1.1.2 Các bước của quá trình phát hiện tri thức

Quá trình phát hiện tri thức tiến hành qua 6 giai đoạn như hình 1.1:

Hình 1.1: Quá trình phát hiện tri thức

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...

(1) Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai

phá dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ

liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web.

(2) Trích lọc dữ liệu: Ở giai đoạn này dữ liệu được lựa chọn hoặc phân

chia theo một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn

tất cả những người có tuổi đời từ 25 - 35 và có trình độ đại học.

(3) Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này

là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong

quá trình khai phá 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ẽ, logíc. Vì vậy, dữ liệu thường chứa các giá trị vô

nghĩa và không có khả năng kết nối dữ liệu. Ví dụ: tuổi = 673. 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 phá bằng cách thực

hiện các thao tác nhóm hoặc tập hợp.

(5) Khai phá dữ liệu: Đây là bước mang tính tư duy trong khai phá 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 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 phá 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 (Knowlege)

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 hoá dữ

liệu để biểu diễn tri thức khai phá được cho người sử dụng.

Trên đây là 6 giai đoạn của quá trình phát hiện tri thức, trong đó giai đoạn

5 - khai phá dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn được quan

tâm nhiều nhất.

1.2 Các kỹ thuật khai phá dữ liệu

Hình 1.2 biểu diễn một tập dữ liệu giả hai chiều bao gồm 23 case

(trường hợp). Mỗi một điểm trên hình đại diện cho một người vay tiền ngân

hàng tại một số thời điểm trong quá khứ. Dữ liệu được phân loại vào hai

lớp: những người không có khả năng trả nợ và những người tình trạng vay nợ

đang ở trạng thái tốt tức là tại thời điểm đó có khả năng trả nợ ngân hàng).

Hai mục đích chính của khai phá dữ liệu trong thực tế là dự đoán và mô tả.

Hình 1.2: Tập dữ liệu với 2 lớp: có và không có khả năng trả nợ

1.2.1 Khai phá dữ liệu dự đoán

Nhiệm vụ của khai phá dữ liệu dự đoán là đưa ra các dự đoán dựa vào

các suy diễn trên dữ liệu hiện thời. Nó sử dụng các biến hay các trường trong

cơ sở dữ liệu để dự đoán các giá trị không biết hay các giá trị tương lai. Bao

gồm các kĩ thuật: phân loại (classification), hồi quy (regression)...

1.2.1.1 Phân loại

Mục tiêu của phương pháp phân loại dữ liệu là dự đoán nhãn lớp cho

các mẫu dữ liệu. Quá trình phân loại dữ liệu thường gồm 2 bước: xây dựng mô

hình và sử dụng mô hình để phân loại dữ liệu.

- Bước 1: Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho

trước. Mỗi mẫu thuộc về một lớp, được xác định bởi một thuộc tính gọi là

thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện.

Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi

xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát.

- Bước 2: Sử dụng mô hình để phân loại dữ liệu. Trước hết chúng ta

phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô

hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong

tương lai.

Hay nói cách khác, phân loại là học một hàm ánh xạ một mục dữ liệu

vào một trong số các lớp cho trước. Hình 1.3 cho thấy sự phân loại của các

dữ liệu vay nợ vào trong hai miền lớp. Ngân hàng có thể sử dụng các miền

phân loại để tự động quyết định liệu những người vay nợ trong tương lai có

nên cho vay hay không.

Hình 1.3: Phân loại dữ liệu cho tập dữ liệu cho vay

1.2.1.2 Hồi quy

Phương pháp hồi qui khác với phân loại dữ liệu ở chỗ, hồi qui dùng để

dự đoán về các giá trị liên tục còn phân loại dữ liệu thì chỉ dùng để dự đoán

về các giá trị rời rạc.

Hồi quy là học một hàm ánh xạ một mục dữ liệu vào một biến dự báo

giá trị thực. Các ứng dụng hồi quy có nhiều, ví dụ như đánh giá xác xuất một

bệnh nhân sẽ chết dựa trên tập kết quả xét nghiệm chẩn đoán, dự báo nhu

cầu của người tiêu dùng đối với một sản phẩn mới dựa trên hoạt động

quảng cáo tiêu dùng.

1.2.2 Khai phá dữ liệu mô tả

Kỹ thuật này 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 CSDL hiện có. Bao gồm các kỹ thuật: phân cụm

(clustering), phân tích luật kết hợp (association rules)...

1.2.2.1 Phân cụm

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 cụm 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 giám sát. Không giống như phân loại 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 loại dữ liệu là học bằng ví dụ (learning by

example). Trong phương pháp này bạn sẽ không thể biết kết quả các cụm thu

được sẽ như 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, phân đoạn

khách hàng, nhận dạng mẫu, phân loại trang Web… Ngoài ra phân cụm dữ

liệu còn có thể

được sử dụng như một bước tiền xử lí cho các thuật toán khai

phá dữ liệu khác.

Hình 1.4 cho thấy sự phân cụm tập dữ liệu cho vay vào trong 3 cụm: lưu

ý rằng các cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn

một cụm.

Hình 1.4: Phân cụm tập dữ liệu cho vay vào trong 3 cụm

1.2.2.2 Luật kết hợp

Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ

giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của thuật toán khai phá dữ

liệu là tập luật kết hợp tìm được. Khai phá luật kết hợp được thực hiện qua 2

bước:

• Bước 1: tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác

định qua tính độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.

• Bước 2: sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật

phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu.

Phương pháp này được sử dụng rất hiệu quả trong các lĩnh vực

như marketing có chủ đích, phân tích quyết định, quản lí kinh doanh,…

1.3 Lợi thế của khai phá dữ liệu so với các phương pháp khác

Khai phá dữ liệu là một lĩnh vực liên quan tới rất nhiều ngành học

khác như: hệ CSDL, thống kê,... Hơn nữa, tuỳ vào cách tiếp cận được sử

dụng, khai phá dữ liệu còn có thể áp dụng một số kĩ thuật như mạng nơ ron,

lí thuyết tập thô hoặc tập mờ, biểu diễn tri thức… Như vậy, khai phá dữ liệu

thực ra là dựa trên các phương pháp cơ bản đã biết. Tuy nhiên, sự khác biệt

của khai phá dữ liệu so với các phương pháp đó là gì? Tại sao khai phá dữ

liệu lại có ưu thế hơn hẳn các phương pháp cũ? Ta sẽ lần lượt xem xét và giải

quyết các câu hỏi này.

1.3.1 Học máy (Machine Learning)

So với phương pháp học máy, khai phá dữ liệu có lợi thế hơn ở chỗ,

khai phá dữ liệu có thể sử dụng với các cơ sở dữ liệu thường động, không đầy

đủ, bị nhiễu và lớn hơn nhiều so với các tập dữ liệu học máy điển hình.

Trong khi đó phương pháp học máy chủ yếu được áp dụng trong các CSDL

đầy đủ, ít biến động và tập dữ liệu không quá lớn.

Thật vậy, trong học máy, thuật ngữ cơ sở dữ liệu chủ yếu đề cập tới một

tập các mẫu được lưu trong tệp. Các mẫu thường là các vectơ với độ dài cố

định, thông tin về đặc điểm, dãy các giá trị của chúng đôi khi cũng được lưu

lại như trong từ điển dữ liệu. Một thuật toán học sử dụng tập dữ liệu và các

thông tin kèm theo tập dữ liệu đó làm đầu vào và đầu ra biểu thị kết quả của

việc học. Học máy có khả năng áp dụng cho cơ sở dữ liệu, lúc này, học máy

sẽ không phải là học trên tập các mẫu nữa mà học trên tập các bản ghi của

cơ sở dữ liệu. Tuy nhiên, trong thực tế, cơ sở dữ liệu thường động, không

đầy đủ và bị nhiễu, lớn hơn nhiều so với các tập

dữ liệu học máy điển hình.

Các yếu tố này làm cho hầu hết các thuật toán học máy trở nên không hiệu

quả. Khai phá dữ liệu lúc này sẽ xử lý các vấn đề vốn đã điển hình trong học

máy và vượt quá khả năng của học máy, đó là sử dụng được các CSDL

chứa nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục.

1.3.2 Hệ chuyên gia (Expert Systems)

Các hệ chuyên gia nắm bắt các tri thức cần thiết cho một bài toán nào

đó. Các kỹ thuật thu thập giúp cho việc lấy tri thức từ các chuyên gia con

người. Mỗi phương pháp hệ chuyên gia là một cách suy diễn các luật từ các

ví dụ và giải pháp đối với bài toán chuyên gia đưa ra. Phương pháp hệ

chuyên gia khác với khai phá dữ liệu ở chỗ các ví dụ của chuyên gia thường

ở mức chất lượng cao hơn nhiều so với các dữ liệu trong CSDL, và chúng

thường chỉ bao hàm được các trường quan trọng. Hơn nữa các chuyên gia sẽ

xác nhận giá trị và tính hữu ích của các mẫu phát hiện được.

1.3.3 Thống kê (Statistics)

Mặc dù các phương pháp thống kê cung cấp một nền tảng lý thuyết

vững chắc cho các bài toán phân tích dữ liệu nhưng chỉ có tiếp cận thống kê

thuần tuý thôi chưa đủ bởi:

Các phương pháp thống kê không phù hợp với các kiểu dữ liệu có cấu

trúc trong rất nhiều các cơ sở dữ liệu

- Thống kê hoàn toàn tính toán trên dữ liệu, nó không sử dụng tri thức

sẵn có về lĩnh vực quan tâm

- Các kết quả của phân tích thống kê có thể rất nhiều và khó có thể làm rõ

được.

- Các phương pháp thống kê cần có sự hướng dẫn của người dùng để xác

định phân tích dữ liệu như thế nào và ở đâu.

Phương pháp thống kê là một trong những nền tảng lí thuyết của khai

phá dữ liệu. Sự khác nhau cơ bản giữa khai phá dữ liệu và thống kê ở chỗ

khai phá dữ liệu là một phương tiện được dùng bởi người sử dụng đầu cuối

chứ không phải là các nhà thống kê. Khai phá dữ liệu đã khắc phục được các

yếu điểm trên của thống kê, tự động quá trình thống kê một cách hiệu quả vì

thế giảm bớt công việc của người dùng đầu cuối, tạo ra một công cụ dễ sử dụng

hơn.

1.4 Các ứng dụng của KDD và những thách thức đối với KDD

1.4.1 Các ứng dụng của KDD

Các kỹ thuật KDD có thể được áp dụng vào trong nhiều lĩnh vực:

•

Thông tin thương mại: Phân tích dữ liệu tiếp thị và bán hàng, phân

tích vốn đầu tư, chấp thuận cho vay, phát hiện gian lận, .

•

Thông tin sản xuất: Điều khiển và lập lịch, quản lý mạng, phân tích

kết quả thí nghiệm, ...

•

Thông tin khoa học: Địa lý: Phát hiện động đất,...

•

...

1.4.2 Những thách thức đối với KDD

•

Các cơ sở dữ liệu lớn hơn rất nhiều: cơ sở dữ liệu với hàng trăm

trường và bảng, hàng triệu bản ghi và kích thước lên tới nhiều gigabyte là vấn

đề hoàn toàn bình thường và cơ sở dữ liệu terabyte (10

bytes) cũng đã

bắt đầu xuất hiện.

•

Số chiều cao: Không chỉ thường có một số lượng rất lớn các bản

ghi trong cơ sở dữ liệu mà còn có một số lượng rất lớn các trường (các thuộc

tính, các biến) làm cho số chiều của bài toán trở nên cao. Thêm vào đó, nó

tăng thêm cơ hội cho một thuật toán khai phá dữ liệu tìm ra các mẫu không

hợp lệ. Vậy nên cần giảm bớt hiệu quả kích thước của bài toán và tính hữu

ích của tri thức cho trước để nhận biết các biến không hợp lệ.

•

Over-fitting (quá phù hợp): Khi thuật toán tìm kiếm các tham số tốt

nhất cho một mô hình đặc biệt sử dụng một tập hữu hạn dữ liệu, kết quả là

mô hình biểu diễn nghèo nàn trên dữ liệu kiểm định. Các giải pháp có thể bao

gồm hợp lệ chéo, làm theo quy tắc và các chiến lược thống kê tinh vi khác.

•

Thay đổi dữ liệu và tri thức: Thay đổi nhanh chóng dữ liệu (động) có

thể làm cho các mẫu được phát hiện trước đó không còn hợp lệ. Thêm vào

đó, các biến đã đo trong một cơ sở dữ liệu ứng dụng cho trước có thể bị sửa

đổi, xoá bỏ hay tăng thêm các phép đo mới. Các giải pháp hợp lý bao gồm các

phương pháp tăng trưởng để cập nhật các mẫu và xử lý thay đổi.

•

Dữ liệu thiếu và bị nhiễu: Bài toán này đặc biệt nhạy trong các cơ sở

dữ liệu thương mại. Dữ liệu điều tra dân số U.S cho thấy tỷ lệ lỗi lên tới 20%.

Các thuộc tính quan trọng có thể bị mất nếu cơ sở dữ liệu không được thiết kế

với sự khám phá bằng trí tuệ. Các giải pháp có thể gồm nhiều chiến lược thống

kê phức tạp để nhận biết các biến ẩn và các biến phụ thuộc.

•

Mối quan hệ phức tạp giữa các trường: Các thuộc tính hay các giá trị

có cấu trúc phân cấp, các quan hệ giữa các thuộc tính và các phương tiện

tinh vi hơn cho việc biểu diễn tri thức về nội dung của một cơ sở dữ liệu sẽ

đòi hỏi các thuật toán phải có khả năng sử dụng hiệu quả các thông tin này.

Về mặt lịch sử, các thuật toán khai phá dữ liệu được phát triển cho các bản

ghi có giá trị thuộc tính đơn giản, mặc dầu các kỹ thuật mới bắt nguồn từ mối

quan hệ giữa các biến đang được phát triển.

•

Tính dễ hiểu của các mẫu: Trong nhiều ứng dụng, điều quan trọng

là những gì khai thác được phải càng dễ hiểu đối với con người thì càng tốt.

Các giải pháp có thể thực hiện được bao gồm cả việc biểu diễn được minh hoạ

bằng đồ thị, cấu trúc luật với các đồ thị có hướng, biểu diễn bằng ngôn ngữ

tự nhiên và các kỹ thuật hình dung ra dữ liệu và tri thức.

•

Người dùng tương tác và tri thức sẵn có: Nhiều phương pháp KDD

hiện hành và các công cụ không tương tác thực sự với người dùng và không

thể dễ dàng kết hợp chặt chẽ với tri thức có sẵn về một bài toán loại trừ theo

các cách đơn giản. Việc sử dụng của miền tri thức là quan trọng trong toàn

bộ các bước của xử lý KDD.

•

Tích hợp với các hệ thống khác: Một hệ thống phát hiện đứng một

mình có thể không hữu ích lắm. Các vấn đề tích hợp điển hình gồm có việc

tích hợp với một DBMS (tức là qua một giao diện truy vấn), tích hợp với các

bảng tính và các công cụ trực quan và điều tiết các dự đoán cảm biến thời gian

thực.

1.5 Kết luận

Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những

hướng nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về CNTT

trên thế giới. Trong những năm gần đây, rất nhiều các phương pháp và thuật

toán mới liên tục được công bố. Điều này chứng tỏ những ưu thế, lợi ích và

khả năng ứng dụng thực tế to lớn của khai phá dữ liệu. Phần này đã trình bày

một số kiến thức tổng quan về khai phá dữ liệu, cho ta một cái nhìn tổng thể

về khai phá dữ liệu, nó giúp ích cho các tiếp cận ở các chương tiếp theo.