PHÂN CỤM DỮ LIỆU TRONG DATAMING.doc

48

Phân cụm dữ liệu trong Dataming

MỤC LỤC

Chương 1: PHÂN CỤM DỮ LIỆU

1. Khai phá dữ liệu và phân cụm dữ liệu

1.1 Khai phá dữ liệu

1.1.1 Giới thiệu chung

1.1.2 Khai phá dữ liệu là gì

1.2 Quá trình khai phá tri thức trong cơ sơ dữ liệu

1.3 Các dạng dữ liệu có thể khai phá được

1.3.1 Phân cụm dữ liệu

1.3.2 Các đặc trưng cơ bản để phân cụm

2. Các phương pháp phân cụm dữ liệu

2.1 Phương pháp dựa trên phân hoạch

2.1.1 Phương pháp gom cụm k-means

2.1.2 Thuật toán PAM

2.1.3 Thuật toán CLARA

2.1.4 Thuật toán CLARANS

2.1.5 Nhận xét chung về các thuật toán phân hoạch

2.2 Phương pháp dựa trên phân cấp

2.2.1 Thuật toán BIRCH

2.2.2 Thuật toán CURE

2.3 Phương pháp dựa trên mật độ

2.3.1 Thuật toán DBSCAN

2.3.2 Thuật toán OPTICS

Sinh Viên thực hiện: Nguyễn Thị Hướng- K54A-CNTT- ĐHSPHN

48

Phân cụm dữ liệu trong Dataming

3. Một số thuật toán phân cụm dữ liệu đặc thù

3.1 Thuật toán STING

3.2 Thuật toán CRIQUE

3.3 Thuật toán EM

4. Phân cụm dữ liệu nhờ mạng nơ-ron

Chương 2: MẠNG NƠ-RON NHÂN TẠO

1. Mang nơ-ron sinh học

1.1 Khái niệm

1.2 Mô hình

2. Mạng nơ-ron nhân tạo

2.1 Khái niệm

2.2 Đặc điểm

2.3 Cấu trúc mạng nơ-ron nhân tạo

2.3.1 Nút

2.3.2 Phân loại cấu trúc mạng nơ-ron

2.3.3 Các hàm hoạt động

2.4 Kiến trúc mạng nơ-ron

2.5 Một số ứng dụng của mạng nơ-ron

2.5.1 Mạng nơ-ron trong phân lớp

2.5.2 Mạng nơ-ron trong nhận dạng

2.5.3 Mạng nơ-ron trong dự báo

2.5.4 Mạng nơ-ron và tối ưu

2.6 Tiến trình học

Chương 3: SOM VÀ THUẬT TOÁN HUẤN LUYỆN MẠNG NÀY

Sinh Viên thực hiện: Nguyễn Thị Hướng- K54A-CNTT- ĐHSPHN

48

Phân cụm dữ liệu trong Dataming

Lời mở đầu

Ngày nay, cùng với sự phát triển mạnh mẽ của công nghệ phần cứng và truyền

thông, các hệ thống dữ liệu phục vụ cho các lĩnh vực kinh tế - xã hội cũng không ngừng

tăng lên, lượng dữ liệu được tạo ra ngày càng lớn. Sự phong phú về dữ liệu, thông tin

cùng với khả năng kịp thời khai thác chúng đã mang đến những năng suất và chất

lượng mới cho công tác quản lý, hoạt động kinh doanh,…Nhưng rồi các yêu cầu về

thông tin trong các lĩnh vực hoạt động đó, đặc biệt trong lĩnh vực ra làm quyết định,

ngày càng đòi hỏi cao hơn, người quyết định không những cần dữ liệu mà còn cần có

thêm nhiều hiểu biết, nhiều tri thức để hỗ trợ cho việc ra quyết định của mình. Cho đến

những năm 90 của thế kỷ trước, nhu cầu khám phá tri thức mới thực sự bùng nổ, theo

đó, hàng loạt các lĩnh vực nghiên cứu về tổ chức các kho dữ liệu và kho thông tin, các

hệ trợ giúp quyết định, các thuật toán nhận dạng mẫu và phân lớp mẫu, …và đặc biệt là

khai phá dữ liệu (Data Mining) ra đời.

Từ khi ra đời, khai phá dữ liệu đã trở thành một trong những hướng nghiên cứu

phổ biến trong lĩnh vực khoa học máy tính và công nghệ tri thức. Nhiều kết quả nghiên

cứu, ứng dụng của khai phá dữ liệu trong các lĩnh vực khoa học, kinh tế, xã hội. Khai

phá dữ liệu bao hàm nhiều hướng nghiên cứu quan trọng, một trong số đó là phân cụm

dữ liệu (Data Clustering). Phân cụm dữ liệu là quá trình tìm kiếm và phát hiện ra các

cụm hoặc các mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn. Các kỹ thuật chính được áp

dụng trong phân cụm dữ liệu phần lớn được kế thừa từ lĩnh vực thống liệu cho việc giải

quyết các vấn đề trong các lĩnh vực như tài chính, thông tin địa lý, sinh học, nhận dạng

ảnh,… Trong thời gian gần đây, trong lĩnh vực phân cụm dữ liệu, người ta tập trung

chủ yếu vào nghiên cứu, phân tích các mô hình dữ liệu phức tạp như dữ liệu văn bản,

Web, hình ảnh,…và đặc biệt là mô hình dữ liệu hỗn hợp để áp dụng chúng trong phân

cụm dữ liệu.

Chương 1: PHÂN CỤM DỮ LIỆU

1. Khai phá dữ liệu và phân cụm dữ liệu

1.1. Khai phá dữ liệu

1.1.1 Giới thiệu chung

Sinh Viên thực hiện: Nguyễn Thị Hướng- K54A-CNTT- ĐHSPHN

48

Phân cụm dữ liệu trong Dataming

Những năm 60 của thế kỉ trước, người ta bắt đầu sử dụng các công cụ tin học để

tổ chức và khai thác các cơ sở dữ liệu. Cùng với sự phát triển vượt bậc của các công

nghệ điện tử và truyền thông, khả năng thu thập, lưu trữ và xử lí dữ liệu cho các hệ

thống tin học không ngừng được nâng cao, theo đó lượng thông tin được lưu trữ trên

các thiết bị nhớ không ngừng được tăng lên. Thống kê sơ bộ cho thấy, lượng thông tin

trên các hệ thống tin học cứ sau 20 tháng lại tăng lên gấp đôi. Cuối thập kỉ 80 của thế kỉ

XX, sự phát triển rộng khắp của các cơ sở dữ liệu ở mọi quy mô đã tạo sự bùng nổ

thông tin trên toàn cầu. Vào thời gian này, người ta bắt đầu đề cập đến khái niệm phân

tích dữ liệu tác nghiệp để cung cấp thông tin với yêu cầu chất lượng ngày càng cao cho

người làm quyết định trong các tổ chức tài chính, thương mại, khoa học,…

Đúng như John Naisbett đã cảnh báo “Chúng ta chìm ngập trong dữ liệu mà vẫn

đói tri thức”. Lượng dữ liệu khổng lồ này thực sự là nguồn tài nguyên có nhiều giá trị

bởi thông tin là yếu tố then chốt trong mọi hoạt đọng quản lý, kinh doanh, phát triển

sản xuất và dịch vụ,…nó giúp những người điều hành và quản ly có nhiều hiểu biết về

môi trường và tiến trình hoạt động của tổ chức mình trước khi ra quyết định để tác

động đến quá trình hoạt động nhằm đạt được cá mục tiêu một cách hiệu quả và bền

vững.

Khai phá dữ liệu (Data mining), là một lĩnh vực mới xuất hiện, nhằm tự động

khai thác những thông tin, những tri thức có tính tiềm ẩn, hữu ích từ những cơ sơ dữ

liệu lớn cho các đơn vị, tổ chức, doanh nghiệp,…từ đó làm thức đẩy khả năng sản xuất,

kinh doanh, cạnh tranh cho các đơn vị, tổ chức này. Các kết quả khoa học cùng những

ứng dụng thành công trong khám phá tri thức, cho thấy khai phá dữ liệu là một lĩnh vực

phát triển bền vững, mang lại nhiều lợi ích và có nhiều triển vọng, động thời có ưu thế

hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Hiện nay, khai phá dữ liệu

đã ứng dụng ngày càng rộng rãi trong các lĩnh vực như: thương mại, tài chính, điều trị y

học, viễn thông, tin- sinh,…

1.1.2 Khai phá dữ liệu là gì?

Khai phá dữ liệu là một hướng nghiên cứu mới ra đời hơn một thập niên trở lại

đây, các kĩ thuật chính được áp dụng trong lĩnh vực này phần lớn được thừa kế từ lĩnh

vực cơ sơ dữ liệu, máy học, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê, và

tính toán hiệu năng cao. Do sự phát triển nhanh của khai phá dữ liệu về phạm vi ứng

dụng và các phương pháp tìm kiếm tri thức, nên đã có nhiều quan điểm khác nhau về

khai phá dữ liệu. Tuy nhiên ở mức độ trừu tượng nhất định chúng ta định nghĩa khai

phá dữ liệu như sau:

Định nghĩa: Khai phá dữ liệu là một quá trình tìm kiếm, phát hiện các tri thức

mới, tiềm ẩn, hữu dụng trong cơ sơ dữ liệu lớn.

Khai phá tri thức trong cơ sơ dữ liệu (Knowledge Discovery in Database - KDD)

là mục tiêu chính của khai phá dữ liệu, do vậy hai khái niệm khai phá dữ liệu và KDD

Sinh Viên thực hiện: Nguyễn Thị Hướng- K54A-CNTT- ĐHSPHN