Luận văn Thạc sĩ Khoa học máy tính: Phân cụm dữ liệu dựa trên mật độ và ứng dụng

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN

THÔNG

VŨ NGỌC THANH

PHÂN CỤM DỮ LIỆU DỰA TRÊN MẬT ĐỘ

VÀ ỨNG DỤNG

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số: 60 48 01 01

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

THÁI NGUYÊN – 2016

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN

THÔNG

VŨ NGỌC THANH

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

PHÂN CỤM DỮ LIỆU DỰA TRÊN MẬT ĐỘ

VÀ ỨNG DỤNG

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số: 60 48 01 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học

TS. NGUYỄN HUY ĐỨC

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

THÁI NGUYÊN – 2016

LỜI CÁM ƠN

Để hoàn thành được luận văn này, trước hết em xin gửi lời cảm ơn

sâu sắc nhất tới TS. Nguyễn Huy Đức, đã tận tình hướng dẫn, chỉ bảo,

định hướng, đóng góp những ý kiến quý báu trong suốt quá trình em

thực hiện luận văn.

Em xin chân thành cảm ơn các thầy, cô giáo trong trường Đại học

Công nghệ thông tin và Truyền thông Thái Nguyên đã tạo mọi điều kiện

tốt nhất để em hoàn thành khóa học này. Đồng thời, em cũng xin cảm ơn

gia đình, bạn bè, những người luôn khuyến khích và giúp đỡ tôi trong

mọi hoàn cảnh khó khăn. Tôi xin cảm ơn cơ quan và các đồng nghiệp đã

hết sức tạo điều kiện cho tôi trong suốt quá trình học tập và làm luận văn

này.

Thái Nguyên, ngày 17 tháng 09 năm 2016.

Học viên

Vũ Ngọc Thanh

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

MỤC LỤC

MỤC LỤC ......................................................................................................... 1 DANH MỤC HÌNH ẢNH ................................................................................ 7

DANH MỤC TỪ VIẾT TẮT ............................................................................ 8

MỞ ĐẦU ........................................................................................................... 9

CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU ................................................................................................................ 11

1.1. Tổng quan về khai phá dữ liệu ............................................................. 11

1.1.1. Khái niệm ...................................................................................... 11

1.1.2. Tiến trình khai phá dữ liệu ............................................................ 12 1.1.3. Các mô hình khai phá dữ liệu ....................................................... 14

1.1.4. Các hướng tiếp cận và kỹ thuật sử dụng trong khai phá dữ liệu... 15

1.1.5. Các dạng dữ liệu có thể khai phá .................................................. 16

1.1.6. Các ứng dụng của khai phá dữ liệu ............................................... 17

1.2. Tổng quan về phân cụm dữ liệu ........................................................... 19 1.2.1. Khái niệm ...................................................................................... 19

1.2.2. Các mục tiêu của phân cụm dữ liệu .............................................. 20

1.2.3. Các ứng dụng của phân cụm dữ liệu ............................................. 22

1.2.4. Các yêu cầu của phân cụm dữ liệu ................................................ 23

1.2.5. Những vấn đề còn tồn tại trong phân cụm dữ liệu ........................ 26

1.2.6. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu ........... 26 1.2.7. Những kỹ thuật tiếp cận trong phân cụm dữ liệu .......................... 31

CHƯƠNG 2: PHÂN CỤM DỮ LIỆU DỰA TRÊN MẬT ĐỘ ...................... 37

2.1. Giới thiệu .............................................................................................. 37

2.2. Thuật toán DBSCAN ........................................................................... 38

2.3. Thuật toán DBRS ................................................................................. 49 2.4. Thuật toán OPTICS .............................................................................. 55

2.5. Thuật toán DENCLUDE ...................................................................... 56

CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỰC NGHIỆM ................ 60 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

3.1. Ý tưởng bài toán ................................................................................... 60

3.2. Nguồn dữ liệu đầu vào ......................................................................... 60

3.3. Phương pháp giải quyết bài toán .......................................................... 60

3.4. Kết quả thực nghiệm ............................................................................ 61 KẾT LUẬN ..................................................... Error! Bookmark not defined.

TÀI LIỆU THAM KHẢO ............................................................................... 66

PHỤ LỤC ........................................................................................................ 67

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DANH MỤC HÌNH ẢNH

Hình 1.1: Tiến trình khám phá tri thức từ cơ sở dữ liệu

Hình 1.2: Kiến trúc điển hình của một hệ khai phá dữ liệu

Hình 1.3: Ví dụ về phân cụm dữ liệu

Hình 1.4: Ví dụ phân cụm các ngôi nhà dựa trên khoảng cách

Hình 1.5: Ví dụ phân cụm các ngôi nhà dựa trên kích cỡ

Hình 2.1: Ví dụ về đối tượng nòng cốt, đối tượng biên và đối tượng nhiễu

Hình 2.2: Ví dụ về mật độ đạt được trực tiếp

Hình 2.3: Ví dụ về mật độ đạt được

Hình 2.4: Ví dụ về mật độ liên thông

Hình 2.5: Minh họa đồ thị khoảng cách 4-dist đã được sắp xếp của một CSDL

Hình 2.6: Kết quả thực nghiệm đánh giá thời gian thực hiện thuật toán (tính

theo giây) trên 2 thuật toán của nhóm tác giả

Hình 2.7: Các cụm phát hiện được bởi CLARANS (a) và DBSCAN (b)

Hình 2.8: Các cụm được phát hiện bởi DBRS(a), DBSCAN(b), K-Means(c),

CLARANS(d)

Hình 2.9: Sắp xếp cụm trong OPTICS phụ thuộc vào ɛ

Hình 2.10: DENCLUE với hàm phân phối Gaussian

Hình 3.1: Kết qua sau khi phân cụm của chương trình thực nghiệm

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DANH MỤC TỪ VIẾT TẮT

Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh

Cơ sở dữ liệu CSDL Database

KDD Khai phá tri thức trong cơ sở dữ liệu Knowledge Discovery in Databases

Khai phá tri thức KPTT Knowledge Discovery

Khai phá dữ liệu KPDL Data Mining

Phân cụm dữ liệu PCDL Data Clustering

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

MỞ ĐẦU

Trong vài thập niên gần đây, cùng với sự thay đổi và phát triển không

ngừng của ngành công nghệ thông tin nói chung và trong các ngành công

nghệ phần cứng, phần mềm, truyền thông và hệ thống các dữ liệu phục vụ

trong các lãnh vực kinh tế - xã hội nói riêng. Thì việc thu thập thông tin cũng

như nhu cầu lưu trữ thông tin càng ngày càng lớn. Bên cạnh đó việc tin học

hóa 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 cơ sở dữ liệu đã được sử dụng trong các hoạt

động sản xuất, kinh doanh, quản lí ... trong đó có nhiều cơ sở dữ liệu 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 công nghệ thông tin thế

giới hiện nay. Một vấn đề được đặt ra là phải làm sao trích chọn được những

thông tin có ý nghĩa từ tập dữ liệu lớn để từ đó có thể giải quyết được các yêu

cầu của thực tế như trợ giúp ra quyết định, dự đoán,… và khai phá dữ liệu

(Data mining) đã ra đời nhằm giải quyết các yêu cầu đó.

Ngay từ những ngày đầu khi xuất hiện, Data mining đã trở thành một

trong những xu hướng nghiên cứu phổ biến trong lĩnh vực học máy tính và

công nghệ tri thức. Nhiều thành tựu nghiên cứu của Data mining đã được áp

dụng trong thực tế. Data mining có nhiều hướng quan trọng và một trong các

hướng đó 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 để phân ra các cụm dữ liệu, các mẫu dữ liệu từ tập Cơ sở dữ

liệu lớn. Phân cụm dữ liệu là một phương pháp học không giám sát.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Phân cụm dữ liệu là một trong những kỹ thuật để khai thác dữ liệu có

hiệu quả. Phân cụm dữ liệu đã được ứng dụng trong nhiều lĩnh vực khác

nhau: kinh tế, bảo hiểm, quy hoạch đô thị, nghiên cứu về địa chấn v.v… Có rất

nhiều kỹ thuật tiếp cận trong phân cụm dữ liệu, tùy thuộc vào bài toán thực tế

mà chúng ta có thể chọn những phương pháp cho phù hợp. Trong luận văn này

em xin được trình bày những nghiên cứu của bản thân về phương pháp “Phân

cụm dữ liệu dựa trên mật độ và ứng dụng”.

Bố cục luận văn như sau:

Ngoài các phần mở đầu, mục lục, danh mục hình ảnh, kết luận, tài liệu

tham khảo, phụ lục. Luận văn được chia là 3 phần chính:

 Phần 1: Tổng quan về khai phá dữ liêu và phân cụm dữ liệu

Phần này giới thiệu các khái niệm cơ bản về khai phá dữ liệu và phân

cụm dữ liệu. Các phương pháp, lãnh vực và các hướng tiếp cận trong

phân cụm dữ liệu.

 Phần 2: Phương pháp phân cụm dữ liệu dựa trên mật độ

Phần này trình bày chi tiết phương pháp phân cụm dữ liệu dựa trên mật

độ và các thuật toán tiêu biểu của phương pháp này.

 Phần 3: Xây dựng chương trình thực nghiệm

Xây dựng chương trình thực nghiệm phân cụm dữ liệu dựa trên mật độ

với giải thuật DBSCAN.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM

DỮ LIỆU

1.1. Tổng quan về khai phá dữ liệu

1.1.1. Khái niệm

Có nhiều định nghĩa về Khai phá dữ liệu (Data Mining) được đưa ra,

nhìn chung, có thể hiểu khai phá dữ liệu là quá trình tìm ra các quy luật, các

mối quan hệ và các thông tin có ích tiềm ẩn giữa các mẫu dữ liệu trong một cơ

sở dữ liệu. Các thông tin có ích này không hoặc khó có thể được tìm ra bởi các

hệ cơ sở dữ liệu giao dịch truyền thống. Các tri thức mà khai phá dữ liệu mang

lại là công cụ hữu hiệu đối với tổ chức trong việc hoạch định chiến lược và ra

quyết định kinh doanh.

Khác với các câu hỏi mà hệ cơ sở dữ liệu truyền thống có thể trả lời như:

 Hãy hiển thị số tiền ông Smith trong ngày 5 tháng Giêng ?: thu nhận

thông tin riêng lẻ do xử lý giao dịch trực tuyến (on-line transaction

processing – OLTP).

 Có bao nhiêu nhà đầu tư nước ngoài mua cổ phiếu X trong tháng trước?:

thu nhận thông tin thống kê do hệ thống hỗ trợ quyết định thống kê

(stastical decision suppport system - DSS).

 Hiển thị mọi cổ phiếu trong CSDL với mệnh giá tăng ? thu nhận dữ liệu

đa chiều do xử lý phân tích trực tuyến (on-line analytic processing -

OLAP).

Khai phá dữ liệu giúp trả lời các câu hỏi mang tính trừu tượng, tổng quát

hơn như:

 Các cổ phiếu tăng giá có đặc trưng gì ?

 Tỷ giá US$ - DMark có đặc trưng gì ?

 Hy vọng gì về cổ phiếu X trong tuần tiếp theo ?

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Trong tháng tiếp theo, sẽ có bao nhiêu đoàn viên công đoàn không trả

được nợ của họ ?

 Những người mua sản phẩm Y thường mua những sản phẩm nào nữa ?

Khai phá dữ liệu là sự kết hợp của nhiều chuyên ngành như cơ sở dữ liệu,

học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê, tính toán hiệu

năng cao và các phương pháp tính toán mềm…

1.1.2. Tiến trình khai phá dữ liệu

Một số nhà khoa học xem khai phá dữ liệu (KPDL) là một cách gọi khác

của một thuật ngữ rất thông dụng: Khám phá tri thức từ cơ sở dữ liệu

(Knowledge Discovery in Database- KDD). Mặt khác, khi chia các bước trong

quá trình khám phá tri thức, một số nhà nghiên cứu lại cho rằng, KPDL chỉ là

một bước trong quá trình khám phá tri thức [5].

Như vậy, khi xét ở mức tổng quan thì hai thuật ngữ này là tương đương

nhau, nhưng khi xét cụ thể thì KPDL được xem là một bước trong quá trình

khám phá tri thức.

Nhìn chung, khai phá dữ liệu hay khám phá tri thức từ cơ sở dữ liệu bao

gồm các bước sau [4]:

Hình 1.1: Tiến trình khám phá tri thức từ cơ sở dữ liệu

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Trích chọn dữ liệu: Là quá trình trích lọc một lượng dữ liệu phù hợp,

cần thiết từ tập dữ liệu lớn (cơ sở dữ liệu tác nghiệp, kho dữ liệu)…

 Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy

đủ, dữ liệu nhiễu, ngoại lai, dữ liệu không nhất quán…), rút gọn dữ liệu

(lấy mẫu dữ liệu, lượng tử hóa…), rời rạc hóa dữ liệu. Kết quả sau bước

này là dữ liệu có tính nhất quán, đầy đủ, được rút gọn và được rời rạc

hóa.

 Chuyển đổi dữ liệu: Là bước chuẩn hóa khuôn dạng và làm mịn dữ liệu,

nhằm đưa dữ liệu về dạng thuận lợi nhất để phục vụ cho việc áp dụng

các giải thuật khai phá dữ liệu ở bước sau.

 Khai phá dữ liệu: Sử dụng các phương pháp, kỹ thuật, các thuật toán để

trích lọc ra mẫu có ý nghĩa cùng với các tri thức, quy luật, biểu thức mô

tả mối quan hệ của dữ liệu trong một khía cạnh nào đó. Đây là bước quan

trọng và tốn nhiều thời gian nhất của toàn bộ tiến trình KDD.

 Đánh giá và biểu diễn tri thức: Trình bày các tri thức, quy luật, biểu

thức có ý nghĩa đã tìm được ở bước trước dưới các dạng thức gần gũi, dễ

hiểu đối với người sử dụng như đồ thị, biểu đồ, cây, bảng biểu,

luật…Đồng thời đưa ra những đánh giá về tri thức khám phá được theo

những tiêu chí nhất định.

Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của con người

để điều chỉnh cách thức và kỹ thuật sử dụng trong khai phá, nhằm thu được tri

thức phù hợp nhất.

Dựa trên các bước của quá trình khai phá dữ liệu như trên, kiến trúc điển

hình của một hệ khai phá dữ liệu có thể bao gồm các thành phần như sau:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 1.2: Kiến trúc điển hình của một hệ khai phá dữ liệu [4]

1.1.3. Các mô hình khai phá dữ liệu

Mô hình khai phá dữ liệu là mô tả về phương pháp, cách thức khai phá

thông tin từ dữ liệu và định hướng kiểu tri thức cần khai phá.

Một mô hình khai phá dữ liệu có thể được mô tả ở 2 mức:

 Mức chức năng (Function level): Mô tả mô hình bằng những thuật ngữ

về dự định sử dụng. Ví dụ: Phân lớp, phân cụm…

 Mức biểu diễn (Representation level): Biểu diễn cụ thể một mô hình. Ví

dụ: Mô hình log-linear, cây phân lớp, phương pháp láng giềng gần

nhất…

Các mô hình khai phá dữ liệu dựa trên 2 kiểu học: có giám sát và không

giám sát (đôi khi được nói đến như là học trực tiếp và không trực tiếp -directed

and undirected learning) [6]. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Các hàm học có giám sát (Supervised learning functions) được sử dụng

để dự đoán giá trị. Một ví dụ của thuật toán học có giám sát bao gồm

Naive Bayes cho phân lớp (classification).

 Các hàm học không giám sát được dùng để tìm ra cấu trúc bên trong, các

quan hệ hoặc tính giống nhau trong nội dung dữ liệu nhưng không có lớp

hay nhãn nào được gán ưu tiên. Ví dụ của các thuật toán học không giám

sát gồm phân nhóm k-mean (k-mean clustering) và các luật kết hợp

Apriori.

Tương ứng có 2 loại mô hình khai phá dữ liệu:

 Các mô hình dự báo (học có giám sát):

- Phân lớp: nhóm các đối tượng thành các lớp riêng biệt và dự đoán một

đối tượng sẽ thuộc vào lớp nào.

- Hồi qui (Regression): xấp xỉ hàm và dự báo các giá trị liên tục.

 Các mô hình mô tả (học không giám sát):

- Phân cụm (Clustering): Tìm các nhóm tự nhiên trong dữ liệu.

- Các mô hình kết hợp (Association models): Phân tích “giỏ hàng”.

- Trích chọn đặc trưng (Feature extraction): Tạo các thuộc tính (đặc trưng)

mới như là kết hợp của các thuộc tính ban đầu.

1.1.4. Các hướng tiếp cận và kỹ thuật sử dụng trong khai phá dữ liệu

Xuất phát từ hai mô hình khai phá dữ liệu chủ yếu như đã đề cập ở trên,

các bài toán (hay chức năng) khai phá dữ liệu giải quyết thường được phân chia

thành các dạng sau [4]:

 Mô tả khái niệm (concept description & summarization): . Tổng quát,

tóm tắt các đặc trưng dữ liệu, Ví dụ: tóm tắt văn bản…

 Phân lớp và dự đoán (classification & prediction): Xây dựng các mô

hình (chức năng) để mô tả và phân biệt khái niệm cho các lớp hoặc khái

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

niệm để dự đoán trong tương lai, xếp một đối tượng vào một trong những

lớp đã biết trước.

 Luật kết hợp (association rules): Biểu diễn mối tương quan nhân quả

giữa dữ liệu và xu hướng của dữ liệu dưới dạng luật biểu diễn tri thức ở

dạng khá đơn giản.

 Khai phá chuỗi theo thời gian (sequential/temporal patterns): tương tự

như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian.

Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị

trường chứng khoán vì nó có tính dự báo cao.

 Phân cụm (clustering/segmentation): xếp các đối tượng theo từng cụm

(số lượng cũng như tên của cụm chưa được biết trước. Phân cụm còn

được gọi là học không giám sát (học không có thầy – unsupervised

learning).

 Phân tích bất thường (ngoại lai): Phát hiện sự bất thường của dữ liệu:

đối tượng dữ liệu không tuân theo hành vi chung của toàn bộ dữ liệu

nhằm phát hiện gian lận hoặc phân tích các sự kiện hiếm…

1.1.5. Các dạng dữ liệu có thể khai phá

Khai phá dữ liệu là kết hợp của nhiều lĩnh vực khoa học, xử lý nhiều

nhiều kiểu dữ liệu khác nhau [4]. Sau đây là một số kiểu dữ liệu điển hình:

 CSDL quan hệ (relational databases)

 CSDL đa chiều (multidimensional structures, data warehouses)

 CSDL dạng giao dịch (transactional databases)

 CSDL quan hệ - hướng đối tượng (object-relational databases)

 Dữ liệu không gian và thời gian (spatial and temporal data)

 Dữ liệu chuỗi thời gian (time-series data)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 CSDL đa phương tiện (multimedia databases) như âm thanh (audio),

hình ảnh (image), phim ảnh (video), .v.v.

 Dữ liệu Text và Web (text database & www)

1.1.6. Các ứng dụng của khai phá dữ liệu

Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều

lĩnh vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các

ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu từ ảnh viễn thám, cảnh báo

hỏng hóc trong các hệ thống sản xuất; quy hoạch và phát triển các hệ thống

quản lý và sản xuất trong thực tế như dự đoán tải sử dụng điện, mức độ tiêu thụ

sản phẩm, phân nhóm khách hàng; áp dụng cho các vấn đề xã hội như phát hiện

tội phạm, tăng cường an ninh… Có thể liệt kê ra đây một số ứng dụng điển hình

như:

 Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision

support)

 Điều trị y học (medical treatment): mối liên hệ giữa triệu chứng, chẩn

đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc men, phẫu thuật,

…).

 Text mining & Web mining: phân lớp văn bản và các trang web, tóm tắt

văn bản, .v.v.

 Tin-sinh (bio-informatics): tìm kiếm, đối sánh các hệ gene và thông tin

di truyền, mối liên hệ giữa một số hệ gene và một số bệnh di truyền, .v.v.

 Tài chính và thị trường chứng khoán (finance & stock market): 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, .v.v.

 Bảo hiểm (insurance)

 .v.v.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

1.2. Tổng quan về phân cụm dữ liệu

1.2.1. Khái niệm

Phân cụm dữ liệu là một kỹ thuật trong Data mining nhằm tìm kiếm, phát

hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ấn và quan trọng trong tập dữ liệu

lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định.

Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm

dữ liệu với trong đó các đối tượng tương tự như nhau. Trong mỗi nhóm, một

số chi tiết có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta

có thể hiểu “Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng

nhóm mà các đối tượng ở mỗi nhóm đều tương tự nhau theo một tính chất nào

đó, những đối tượng không tương tự tính chất sẽ ở nhóm khác” [1].

Phân cụm dữ liệu là quá trình nhóm một tập 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 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, trong khi phân lớp dữ liệu là học bằng ví dụ... 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 như là phân loại và mô tả đặc điểm, có tác

dụng trong việc phát hiện ra các cụm.

Như vậy, phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban

đầu thành các cụm dữ liệu sao cho các đối tượng trong một cụm “tương tự”

(Similar) với nhau và các đối tượng trong các cụm khác nhau sẽ “không tương

tự” (Dissimilar) với nhau. Số các cụm dữ liệu được phân ở đây có thể được xác

định trước theo kinh nghiệm hoặc có thể được tự động xác định.

Chúng ta có thể thấy điều này với một ví dụ đơn giản như sau [8]:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 1.3: Ví dụ về phân cụm dữ liệu

Trong trường hợp này, chúng ta dễ dàng xác định được 4 cụm dựa vào

các dữ liệu đã cho; các tiêu chí “tương tự” để phân cụm trong trường hợp này

là khoảng cách: hai hoặc nhiều đối tượng thuộc nhóm của chúng được “đóng

gói” theo một khoảng cách nhất định. Điều này được gọi là phân cụm dựa trên

khoảng cách.

Một kiểu khác của phân cụm dữ liệu là phân cụm dữ liệu dựa vào khái

niệm: hai hay nhiều đối tượng thuộc cùng nhóm nếu có một định nghĩa khái

niệm chung cho tất cả các đối tượng trong đó. Nói cách khác, đối tượng của

nhóm phải phù hợp với nhau theo miêu tả các khái niệm đã được định nghĩa,

không phải theo những biện pháp đơn giản tương tự.

1.2.2. Các mục tiêu của phân cụm dữ liệu

Mục tiêu của phân cụm dữ liệu là để xác định các nhóm nội tại bên trong

một bộ dữ liệu không có nhãn. Nhưng để có thể quyết định được cái gì tạo

thành một cụm tốt. Nhưng làm thế nào để quyết định cái gì đã tạo nên một phân

cụm dữ liệu tốt? Nó có thể được hiển thị rằng không có tiêu chuẩn tuyệt đối

“tốt nhất” mà sẽ là độc lập với mục đích cuối cùng của phân cụm dữ liệu. Do

đó, mà người sử dụng phải cung cấp tiêu chuẩn, theo cách như vậy mà kết quả

của phân cụm dữ liệu sẽ phù hợp với nhu cầu của họ cần. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Ví dụ, chúng ta có thế quan tâm đến việc tìm kiếm đối tượng đại diện

cho các nhóm đồng nhất trong “các cụm tự nhiên” và mô tả thuộc tính không

biết của chúng trong việc tìm kiếm các nhóm hữu ích và phù hợp hoặc trong

việc tìm kiếm các đối tượng bất thường trong dữ liệu (cá biệt, ngoại lệ, nhiễu)

[1].

Hình 1.4: Ví dụ phân cụm các ngôi nhà dựa trên khoảng cách

Một vấn đề thường gặp trong phân cụm là hầu hết các dữ liệu cần cho

phân cụm đều có chứa dữ liệu nhiễu do quá trình thu thập thiếu chính xác hoặc

thiếu đầy đủ, vì vậy cần phải xây dựng chiến lược cho bước tiền xử lí dữ liệu

nhằm khắc phục hoặc loại bỏ nhiễu trước khi chuyển sang giai đoạn phân tích

cụm dữ liệu. Nhiễu ở đây được hiếu là các đối tượng dữ liệu không chính xác,

không tường minh hoặc là các đối tượng dữ liệu khuyết thiếu thông tin về một

số thuộc tính... Một trong các kỹ thuật xử lý nhiễu phổ biến là việc thay thế giá

trị các thuộc tính của đối tượng nhiễu bằng giá trị thuộc tính tương ứng. Ngoài

ra, dò tìm đối tượng ngoại lai cũng là một trong những hướng nghiên cứu quan

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

trọng trong phân cụm, chức năng của nó là xác định một nhóm nhỏ các đối

tượng dữ liệu khác thường so với các dữ liệu trong cơ sở dữ liệu, tức là các đối

tượng dữ liệu không tuân theo các hành vi hoặc mô hình dữ liệu nhằm tránh sự

ảnh hưởng của chúng tới quá trình và kết quả của phân cụm.

Hình 1.5: Ví dụ phân cụm các ngôi nhà dựa trên kích cỡ

Theo các nghiên cứu đến thời điểm hiện nay thì chưa có một phương

pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu

trúc cơ sở dữ liệu. Hơn nữa, đối với các phương pháp phân cụm cần có cách

thức biểu diễn cấu trúc của cơ sở dữ liệu, với mỗi cách thức biểu diễn khác

nhau sẽ có tương ứng một thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ

liệu vẫn đang là một vấn đề khó và mở, vì phải giải quyết nhiều vấn đề cơ bản

một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối

với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu và đây

cũng là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu.

1.2.3. Các ứng dụng của phân cụm dữ liệu

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Phân cụm dữ liệu có thể ứng dụng trong nhiều lãnh vực như [7]:

 Thương mại: tìm kiếm nhóm các khách hàng quan trọng dựa vào các

thuộc tính đặc trưng tương đồng và những đặc tả của họ trong các bản

ghi mua bán của cơ sở dữ liệu;

 Sinh học: phân loại động, thực vật qua các chức năng gen tương đồng

của chúng;

 Thư viện: phân loại các cụm sách có nội dung và ý nghĩa tương đồng

nhau để cung cấp cho độc giả, cũng như đặt hàng với nhà cung cấp;

 Bảo hiểm: nhận dạng nhóm tham gia bảo hiểm có chi phí yêu cầu bồi

thường trung bình cao, xác định gian lận trong bảo hiểm thông qua các

mẫu cá biệt;

 Quy hoạch đô thị: nhận dạng các nhóm nhà theo kiểu, vị trí địa lý, giá

trị... nhằm cung cấp thông tin cho quy hoạch đô thị;

 Nghiên cứu địa chấn: phân cụm để theo dõi các tâm động đất nhằm cung

cấp thông tin cho việc nhận dạng các vùng nguy hiểm;

 WWW: tài liệu phân loại, phân nhóm dữ liệu weblog để khám phá các

nhóm về các hình thức tiếp cận tương tự trợ giúp cho việc khai phá thông

tin từ dữ liệu….

1.2.4. Các yêu cầu của phân cụm dữ liệu

Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng

dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc

biệt của chúng. Sau đây là những yêu cầu cơ bản của phân cụm trong khai phá

dữ liệu:

 Có khả năng mở rộng: nhiều thuật toán phân cụm làm việc tốt với những

tập dữ liệu nhỏ chứa ít hơn 200 đối tượng, tuy nhiên, một cơ sở dữ liệu

lớn có thể chứa tới hàng triệu đối tượng. Việc phân cụm với một tập dữ

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

liệu lớn có thể làm ảnh hưởng tới kết quả. Vậy làm cách nào để chúng ta

có thể phát triển các thuật toán phân cụm có khả năng mở rộng cao đối

với các cơ sở dữ liệu lớn ?

 Khả năng thích nghi với các kiểu thuộc tính khác nhau: nhiều thuật toán

được thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy

nhiên, nhiều ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ

liệu khác nhau, như kiểu nhị phân, kiểu tường minh (định danh - không

thứ tự), và dữ liệu có thứ tự hay dạng hỗn hợp của những kiểu dữ liệu

này.

 Khám phá các cụm với hình dạng bất kỳ: nhiều thuật toán phân cụm xác

định các cụm dựa trên các phép đo khoảng cách Euclidean và khoảng

cách Manhattan. Các thuật toán dựa trên các phép đo như vậy hướng tới

việc tìm kiếm các cụm hình cầu với mật độ và kích cỡ tương tự nhau.

Tuy nhiên, một cụm có thể có bất cứ một hình dạng nào. Do đó, việc

phát triển các thuật toán có thể khám phá ra các cụm có hình dạng bất kỳ

là một việc làm quan trọng.

 Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: nhiều

thuật toán phân cụm yêu cầu người dùng đưa vào những tham số nhất

định trong phân tích phân cụm (như số lượng các cụm mong muốn).

 Kết quả của phân cụm thường khá nhạy cảm với các tham số đầu vào.

Nhiều tham số rất khó để xác định, nhất là với các tập dữ liệu có lượng

các đối tượng lớn. Điều này không những gây trở ngại cho người dùng

mà còn làm cho khó có thể điều chỉnh được chất lượng của phân cụm.

 Khả năng thích nghi với dữ liệu nhiễu: hầu hết những cơ sở dữ liệu thực

đều chứa đựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chưa biết hoặc dữ

liệu sai. Một số thuật toán phân cụm nhạy cảm với dữ liệu như vậy và có

thể dẫn đến chất lượng phân cụm thấp.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Ít nhạy cảm với thứ tự của các dữ liệu vào: một số thuật toán phân cụm

nhạy cảm với thứ tự của dữ liệu vào, ví dụ như với cùng một tập dữ liệu,

khi được đưa ra với các thứ tự khác nhau thì với cùng một thuật toán có

thể sinh ra các cụm rất khác nhau. Do đó, việc quan trọng là phát triển

các thuật toán mà ít nhạy cảm với thứ tự vào của dữ liệu.

 Số chiều lớn: một cơ sở dữ liệu hoặc một kho dữ liệu có thể chứa một số

chiều hoặc một số các thuộc tính. Nhiều thuật toán phân cụm áp dụng tốt

cho dữ liệu với số chiều thấp, bao gồm chỉ từ hai đến 3 chiều. Người ta

đánh giá việc phân cụm là có chất lượng tốt nếu nó áp dụng được cho dữ

liệu có từ 3 chiều trở lên. Nó là sự thách thức với các đối tượng dữ liệu

cụm trong không gian với số chiều lớn, đặc biệt vì khi xét những không

gian với số chiều lớn có thể rất thưa và có độ nghiêng lớn.

 Phân cụm ràng buộc: nhiều ứng dụng thực tế có thể cần thực hiện phân

cụm dưới các loại ràng buộc khác nhau. Một nhiệm vụ đặt ra là đi tìm

những nhóm dữ liệu có trạng thái phân cụm tốt và thỏa mãn các ràng

buộc.

 Dễ hiểu và dễ sử dụng: Người sử dụng có thể chờ đợi những kết quả

phân cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể

cần được giải thích ý nghĩa và ứng dụng rõ ràng.

 Với những yêu cầu đáng lưu ý này, nghiên cứu của ta về phân tích phân

cụm diễn ra như sau:

 Đầu tiên, ta nghiên cứu các kiểu dữ liệu khác nhau và cách chúng có thể

gây ảnh hưởng tới các phương pháp phân cụm.

 Thứ hai, ta đưa ra một cách phân loại chung trong các phương pháp phân

cụm.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Sau đó, ta nghiên cứu chi tiết mỗi phương pháp phân cụm, bao gồm các

phương pháp phân hoạch, phân cấp, dựa trên mật độ,... Ta cũng khảo sát

sự phân cụm trong không gian đa chiều và các biến thể của các phương

pháp khác.

1.2.5. Những vấn đề còn tồn tại trong phân cụm dữ liệu

Có một số vấn đề với phân cụm dữ liệu, một trong số đó là [5]:

 Kỹ thuật clustering hiện nay không trình bày được tất cả các yêu cầu đầy

đủ (và đồng thời);

 Giao dịch với số lượng lớn các mẫu và số lượng lớn các mẫu tin của dữ

liệu có thể gặp vấn đề phức tạp về thời gian;

 Hiệu quả của phương pháp phụ thuộc vào định nghĩa của “khoảng cách”

(đối với phân cụm dữ liệu dựa trên khoảng cách). Nếu không tồn tại một

thước đo khoảng cách rõ ràng chúng ta “phải tự xác định”, một điều mà

không thật sự dễ dàng chút nào, nhất là trong không gian đa chiều;

 Kết quả của thuật toán phân cụm dữ liệu có thể được giải thích theo nhiều

cách khác nhau (mà trong nhiều trường hợp chỉ có thể được giải thích

theo ý riêng của mỗi người).

1.2.6. Một số khái niệm cần thiết khi tiếp cận phân cụm dữ liệu

1.2.6.1. Phân loại các kiểu dữ liệu

Trong phần này ta phân tích các kiểu dữ liệu thường được sử dụng trong

PCDL. Trong PCDL, các đối tượng dữ liệu cần phân tích có thể là con người,

nhà cửa, tiền lương, các thực thể phần mềm,… Các đối tượng này thường được

diễn tả dưới dạng các thuộc tính của nó. Các thuộc tính này là các tham số cần

cho giải quyết vấn đề PCDL và sự lựa chọn chúng có tác động đáng kể đến các

kết quả của phân cụm. Phân loại các kiểu thuộc tính khác nhau là một vấn đề

cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Dưới đây là cách

phân lớp dựa trên hai đặc trưng là: kích thước miền và hệ đo.

 Phân loại kiểu dữ liệu dựa trên kích thước miền

 Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được,

nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Ví dụ như các thuộc

tính về màu, nhiệt độ hoặc cường độ âm thanh…

 Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn hoặc đếm

được. Ví dụ như các thuộc tính về số serial của một cuốn sách, số thành

viên trong một gia đình,… trường hợp đặc biệt của thuộc tính rời rạc là

thuộc tính nhị phân mà miền giá trị chỉ có 2 phần tử, ví dụ: Yes/No,

True/False, On/Off,…

 Phân loại kiểu dữ liệu dựa trên hệ đo

Giả sử ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng với

thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau:

 Thuộc tính định danh: Dạng thuộc tính khái quát hóa của thuộc tính

nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có

nhiều hơn hai phần tử . Nếu x và y là hai đối tượng thuộc tính thì chỉ có

thể xác định là x ≠ y hoặc x = y.

 Thuộc tính có thứ tự: Là thuộc tính định danh có thêm tính thứ tự,

nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự

thì ta có thể xác định là x ≠ y hoặc x = y hoặc x > y hoặc x < y.

 Thuộc tính khoảng: Để đo các giá trị theo xấp xỉ tuyến tính, với thuộc

tính khoảng ta có thể xác định một thuộc tính là đứng trước hoặc đứng

sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi > yi thì có thể

nói x cách y một khoảng xi – yi tương ứng với thuộc tính thứ i. Ví dụ:

Thuộc tính số Serial của một đầu sách trong thư viện hoặc thuộc tính số

kênh trên truyền hình.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Thuộc tính tỉ lệ: Là thuộc tính khoảng nhưng được xác định một cách

tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc cân

nặng lấy giá trị 0 làm mốc.

Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và

thuộc tính có thứ tự gọi chung là thuộc tính hạng mục, thuộc tính khoảng và

thuộc tính tỉ lệ được gọi là thuộc tính số.

Người ta còn đặc biệt quan tâm đến dữ liệu không gian. Đây là loại dữ

liệu có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không

gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tượng, thí

dụ như thông tin về hình học,… Dữ liệu không gian có thể là dữ liệu liên tục

hoặc rời rạc:

 Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều

chiều và cho phép ta xác định được khoảng cách giữa các đối tượng dữ

liệu trong không gian.

 Dữ liệu không gian liên tục: Bao gồm một vùng trong không gian.

Thông thường, các thuộc tính số được đo bằng các đơn vị xác định như

là Kilogams hoặc Centimeter. Tuy nhiên, các đơn vị đo có ảnh hưởng đến các

kết quả phân cụm. Thí dụ như thay đổi độ đo cho thuộc tính cân nặng từ

Kilogams sang Pound có thể mang lại các kết quả khác nhau trong phân cụm.

Để khắc phục điều này người ta phải chuẩn hóa dữ liệu, tức là sử dụng các

thuộc tính dữ liệu không phụ thuộc vào đơn vị đo. Thực hiện chuẩn hóa phụ

thuộc vào ứng dụng và người dùng, thông thường chuẩn hóa dữ liệu được thực

hiện bằng cách thay thế mỗi một thuộc tính bằng thuộc tính số hoặc thêm các

trọng số cho các thuộc tính.

1.2.6.2. Độ đo tương tự và phi tương tự

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Để phân cụm, người ta phải đi tìm cách thích hợp để xác định “khoảng

cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để

đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này

hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar)

giữa các đối tượng dữ liệu.

 Không gian metric

Tất cả các độ đo dưới đây được xác định trong không gian độ đo metric.

Một không gian metric là một tập trong đó có xác định các “khoảng cách” giữa

từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học.

Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các

đối tượng dữ liệu trong CSDL D như đã đề cập ở trên được gọi là một không

gian metric nếu:

 Với mỗi cặp phần tử x,y thuộc X đều có xác định, theo một quy tắc nào

đó, một số thực δ(x,y) được gọi là khoảng cách giữa x và y.

 Quy tắc trên thỏa mãn hệ tính chất sau: δ(x,y) > 0 nếu x ≠ y; δ(x,y) = 0

nếu x = y; δ(x,y) = δ(x,y) với mọi x, y; δ(x,y) ≤ δ(x,y) +δ(x,y)

Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X

được gọi là các điểm của không gian này.

 Thuộc tính khoảng cách

Sau khi chuẩn hóa, độ đo phi tương tự của hai đối tượng dữ liệu x, y

được xác định bằng các metric khoảng cách như sau:

 Khoảng cách Minskowski: trong đó q là số tự

nhiên dương.

 Khoảng cách Euclide: đây là trường hợp đặc biệt

của khoảng cách Minskowski trong trường hợp q = 2. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Khoảng cách Manhattan: đây là trường hợp đặc biệt

của khoảng cách Minskowski trong trường hợp q = 1.

 Khoảng cách cực đại: đây là trường hợp đặc

biệt của khoảng cách Minskowski trong trường hợp q = ∞.

 Thuộc tính nhị phân

- α là tổng số các thuộc tính có giá trị là 1 trong x, y.

- β là tổng số các thuộc tính có giá trị là 1 trong x và 0 trong y.

- γ là tổng số các thuộc tính có giá trị là 0 trong x và 1 trong y.

- δ là tổng số các thuộc tính có giá trị là 0 trong x và y.

- τ = α + β + γ + δ

Các phép đo độ tương đồng đối với dữ liệu thuộc tính nhị phân được định

nghĩa như sau:

α+δ

Hệ số đối sánh đơn giản : 𝑑(𝑥, 𝑦) =

τ

ở đây cả hai đối tượng x và y có vai trò như nhau, nghĩa là chính đối

xứng và có cùng trọng số.

α

Hệ số Jacard : 𝑑(𝑥, 𝑦) =

𝛼+ 𝛽+𝛾

(Bỏ qua số các đối sánh giữa 0-0). Công thức tính này được sử dụng

trong trường hợp mà trọng số của các thuộc tính có giá trị 1 của đối tượng dữ

liệu có cao hơn nhiều so với các thuộc tính có giá trị 0, như vậy các thuộc tính

nhị phân ở đây là không đối xứng.

 Thuộc tính định danh

Giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thước miền giá trị) :

Các trạng thái Mi được sắp sếp thứ tự như sau : [1…Mi], chúng ta có thể thay

thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri, với ri ϵ {1…Mi}.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng

ta chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến

đổi sau cho mỗi thuộc tính :

Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với

các giá trị đây chính là độ phi tương tự của thuộc tính có thứ tự.

 Thuộc tính tỉ lệ

Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ.

Một trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính.

Hoặc loại bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hoá chúng,

hoặc gán trọng số cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Với mỗi

thuộc tính dữ liệu đã được gán trọng số tương ứng Wi (l ≤ i ≤ k ), độ tương đồng

dữ liệu được xác định như sau:

1.2.7. Những kỹ thuật tiếp cận trong phân cụm dữ liệu

Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng

trong thực tế, nó đều hướng tới hai mục tiêu chung đó là chất lượng của các

cụm khám phá được và tốc độ thực hiện của thuật toán. Hiện nay, các kỹ thuật

phân cụm có thể phân loại theo các phương pháp tiếp cận chính như sau :

phân cụm phân họach (Partitioning Methods); phân cụm phân cấp

(Hierarchical Methods); phân cụm dựa trên mật độ (Density-Based Methods);

phân cụm dựa trên lưới (Grid-Based Methods); phân cụm dựa trên mô hình

phân cụm (Model-Based Clustering Methods) và phân cụm có dữ liệu ràng

buộc (Binding data Clustering Methods).

1.2.7.1. Phương pháp phân cụm phân hoạch

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k

nhóm cho đến khi xác định số các cụm được thiết lập. Số các cụm được thiết

lập là các đặc trưng được lựa chọn trước. Phương pháp này là tốt cho việc tìm

các cụm hình cầu trong không gian Euclidean. Ngoài ra, phương pháp này

cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm

dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác và các điểm dữ liệu

nào không có quan hệ hoặc có quan hệ là xa nhau so với mỗi điểm khác. Tuy

nhiên, phương pháp này không thể xử lí các cụm có hình dạng kỳ quặc hoặc

các cụm có mật độ các điểm dầy đặc. Các thuật toán phân hoạch dữ liệu có độ

phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn đề phân cụm dữ

liệu, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì

vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng

cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của cụm cũng như

để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Như vậy, ý tưởng

chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến

lược ăn tham (Greedy) để tìm kiếm nghiệm.

Điển hình trong phương pháp tiếp cận theo phân cụm phân họach là

các thuật toán như : K_means, K-medoids, CLARA (Clustering Large

Applications), CLARANS (Clustering Large Applications based on

Randomized Search) . . .

1.2.7.2. Phương pháp phân cụm phân cấp

Phương pháp này xây dựng một phân cấp trên cơ sở các đối tượng dữ

liệu đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc

có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Có

hai cách tiếp cận phổ biến của kỹ thuật này đó là: hòa nhập nhóm, thường

được gọi là tiếp cận (Bottom-Up); phân chia nhóm, thường được gọi là tiếp

cận (Top-Down)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Phương pháp “dưới lên” (Bottom up) : Phương pháp này bắt đầu với

mỗi đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó

tiến hành nhóm các đối tượng theo một độ đo tương tự (như khoảng

cách giữa hai trung tâm của hai nhóm), quá trình này được thực hiện

cho đến khi tất cả các nhóm được hòa nhập vào một nhóm (mức cao

nhất của cây phân cấp) hoặc cho đến khi các điều kiện kết thúc thỏa

mãn. Như vậy, cách tiếp cận này sử dụng chiến lược ăn tham trong quá

trình phân cụm.

 Phương pháp “trên xuống” (Top Down) : Bắt đầu với trạng thái là tất

cả các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành

công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một

phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm,

hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng

chiến lược chia để trị trong quá trình phân cụm.

Điển hình trong phương pháp tiếp cận theo phân cụm phân cấp là các

thuật toán như : AGNES (Agglomerative Nesting), DIANA (Divisive

Analysis), BIRCH (1996), CURE (1998), CHAMELEON (1999) . . .

Thực tế áp dụng, có nhiều trường hợp kết hợp cả hai phương pháp

phân cụm phân hoạch và phân cụm phân cấp, nghĩa là kết quả thu được của

phương pháp phân cấp có thể cải tiến thông qua bước phân cụm phân hoạch.

Phân cụm phân hoạch và phân cụm phân cấp là hai phương pháp phân cụm

dữ liệu cổ điển, hiện đã có rất nhiều thuật toán cải tiến dựa trên hai phương

pháp này đã được áp dụng phổ biến trong khai phá dữ liệu.

1.2.7.3. Phương pháp phân cụm dựa trên lưới

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Kỹ thuật phân cụm dựa trên lưới thích hợp với dữ liệu nhiều chiều,

dựa trên cấu trúc dữ liệu lưới để phân cụm, phương pháp này chủ yếu tập

trung áp dụng cho lớp dữ liệu không gian. Mục tiêu của phương pháp này là

lượng hóa dữ liệu thành các ô tạo thành cấu trúc dữ liệu lưới. Sau đó, các thao

tác phân cụm chỉ cần làm việc với các đối tượng trong từng ô trên lưới chứ

không phải các đối tượng dữ liệu. Cách tiếp cận dựa trên lưới này không di

chuyển các đối tượng trong các ô mà xây dựng nhiều mức phân cấp của nhóm

các đối tượng trong một ô. Phương pháp này gần giống với phương pháp phân

cụm phân cấp nhưng chúng không trộn các ô, đồng thời giải quyết khắc phục

yêu cầu đối với dữ liệu nhiều chiều mà phương pháp phân phân cụm dựa trên

mật độ không giải quyết được. ưu điểm của phương pháp phân cụm dựa trên

lưới là thời gian xử lí nhanh và độc lập với số đối tượng dữ liệu trong tập dữ

liệu ban đầu, thay vào đó là chúng phụ thuộc vào số ô trong mỗi chiều của

không gian lưới.

Điển hình trong phương pháp tiếp cận theo phân cụm dựa trên lưới là

các thuật toán như : STING (a STatistical INformation Grid approach) bởi

Wang, Yang và Muntz (1997), WAVECLUSTER bởi Sheikholeslami,

Chatterjee và Zhang (1998), CLIQUE (Clustering In QUEst) bởi

Agrawal,Gehrke, Gunopulos, Raghavan (1998) . . .

1.2.7.4. Phương pháp phân cụm dựa trên mô hình

Phương này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô

hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến

lược phân cụm phân hoạch hoặc phân cụm phân cấp, dựa trên cấu trúc hoặc

mô hình mà chúng giả định về tập dữ liệu và cách chúng hiệu chỉnh các mô

hình này để nhận dạng ra các phân hoạch.

Phương pháp phân cụm dựa trên mô hình cố gắng khớp giữa các dữ liệu

với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có

hai cách tiếp cận chính: mô hình thống kê và mạng nơron. Phương pháp này

gần giống với phương pháp phân cụm dựa trên mật độ, vì chúng phát triển các

cụm riêng biệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng đôi

khi nó không bắt đầu với một số cụm cố định và không sử dụng cùng một khái

niệm mật độ cho các cụm.

Điển hình trong phương pháp tiếp cận theo phân cụm dựa trên mô hình

là các thuật toán như : EM, COBWEB, CLASSIT, AutoClass (Cheeseman

and Stutz, 1996) . . .

1.2.7.5. Phương pháp phân cụm có dữ liệu ràng buộc

Sự phát triển của phân cụm dữ liệu không gian trên cơ sở dữ liệu lớn

đã cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lí, tuy

nhiên hầu hết các thuật toán này cung cấp rất ít cách thức cho người dùng để

xác định các ràng buộc trong thế giới thực cần phải được thỏa mãn trong quá

trình phân cụm. Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên

cứu bổ sung cần được thực hiện để cung cấp cho người dùng khả năng kết

hợp các ràng buộc trong thuật toán phân cụm.

Hiện nay, các phương pháp phân cụm trên đã và đang được phát triển

và áp dụng nhiều trong các lĩnh vực khác nhau và đã có một số nhánh nghiên

cứu được phát triển trên cơ sở của các phương pháp đó như:

 Phân cụm thống kê: Dựa trên các khái niệm phân tích hệ thống,

nhánh nghiên cứu này sử dụng các độ đo tương tự để phân hoạch

các đối tượng, nhưng chúng chỉ áp dụng cho các dữ liệu có thuộc

tính số.

 Phân cụm khái niệm: Kỹ thuật này được phát triển áp dụng cho dữ

liệu hạng mục, chúng phân cụm các đối tượng theo các khái niệm

mà chúng xử lí.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Phân cụm mờ: Sử đụng kỹ thuật mờ để phân cụm dữ liệu. Các

thuật toán thuộc loại này chỉ ra lược đồ phân cụm thích hợp với tất

cả các hoạt động đời sống hàng ngày, chúng chỉ xử lí các dữ liệu

thực không chắc chắn.

 Phân cụm mạng Kohonen: Loại phân cụm này dựa trên khái niệm

của các mạng nơron. Mạng Kohonen có tầng nơron vào và các

tầng nơron ra. Mỗi nơron của tầng vào tương ứng với mỗi thuộc

tính của bản ghi, mỗi một nơron vào kết nối với tất cả các nơron

của tầng ra. Mỗi liên kết được gắn liền với một trọng số nhằm xác

định vị trí của nơron ra tương ứng.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

CHƯƠNG 2: PHÂN CỤM DỮ LIỆU DỰA TRÊN MẬT ĐỘ

2.1. Giới thiệu

Hầu hết các phương pháp phân cụm thực hiện nhóm các đối tượng dựa

trên khoảng cách giữa chúng. Các phương pháp như vậy có thể chỉ tìm được

các cụm có hình cầu và sẽ gặp khó khăn khi các cụm đang khám phá lại có hình

dạng tuỳ ý.

Để giải quyết vấn đề này, các phương pháp phân cụm được phát triển

theo hướng dựa trên khái niệm mật độ, trong đó, đưa vào số khái niệm sau:

 Eps: bán kính của vùng lân cận của một đối tượng, gọi là ε-

neighborhood.

 MinPts: số lượng đối tượng tối thiểu được yêu cầu trong vùng lân cận

Eps của một đối tượng.

Ý tưởng chung của phương pháp phân cụm dựa trên mật độ là mở rộng

cụm cho trước với điều kiện là mật độ (số các đối tượng hay các điểm dữ liệu)

trong "lân cận" của một điểm dữ liệu vượt quá ngưỡng cho trước, tức là mỗi

phần tử của một cụm phải thỏa mãn điều kiện là trong khoảng lân cận của nó

(trong vòng tròn có tâm là phần tử đó và có bán kính nhỏ hơn một ngưỡng Eps

cho trước, nếu quan niệm các điểm dữ liệu phân bố trong không gian 2 chiều)

phải chứa ít nhất một số lượng phần tử tối thiểu là MinPts. Theo tiếp cận này,

có thể lọc ra các giá trị ngoại lai (outlier) và khám phá ra các cụm có hình dạng

bất kỳ.

Một số thuật toán phân cụm dựa trên mật độ được biết là: DBSCAN,

DBRS, DENCLUE, OPTICS…

Trong đó, DBSCAN là một thuật toán điển hình, thuật toán này thực hiện

duyệt lần lượt các phần tử trong CSDL, đánh giá phần tử này là nhiễu (ngoại

lai), phần tử biên hay phần tử nhân dựa trên số lượng phần tử lân cận của nó,

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

nếu đó là phần tử nhân thì lại mở rộng cụm bằng cách xem xét các lân cận của

nó.

DBRS là thuật toán thừa hưởng tư tưởng của DBSCAN nhưng cải tiến

về tốc độ do sử dụng việc duyệt dữ liệu trên một số mẫu ngẫu nhiên chứ không

duyệt toàn bộ CSDL, do đó giảm được đáng kể số lần truy vấn không gian.

Ngoài ra, điểm mạnh của DBRS so với DBSCAN là nó còn xem xét cả thuộc

tính phi không gian của một đối tượng dữ liệu không gian.

OPTICS là một thuật toán phân cụm dựa trên mật độ, nó tính toán một

thứ tự phân cụm tăng dần cho phép phân tích cụm tự động và tương tác.

Học viên đã tập trung tìm hiểu và cài đặt thử nghiệm thành công thuật

toán DBSCAN.

2.2. Thuật toán DBSCAN

Thuật toán DBSCAN (Density Based Spatial Clustering of Applications

with Noise) được Ester và cộng sự đề xuất năm 1996, khi nghiên cứu các thuật

toán khai phá dữ liệu thông tin địa lý. DBSCAN được khẳng định qua thực

nghiệm là tốt hơn các thuật toán khác. Cụ thể so với thuật toán CLARANS thì

DBSCAN phát hiện ra các cụm bất kì nhiều hơn và thực hiện tốt trên 100 tiêu

chuẩn đánh giá hiệu quả thuật toán [3].

Ý tưởng chính của thuật toán là vùng lân cận mỗi đối tượng trong một

cụm có số đối tượng lớn hơn ngưỡng tối thiểu. Hình dạng vùng lân cận phụ

thuộc vào hàm khoảng cách giữa các đối tượng (nếu sử dụng khoảng cách

Manhattan trong không gian 2 chiều thì vùng lân cận có hình chữ nhật, nếu sử

dụng khoảng cách Eucler trong không gian 2 chiều thì vùng lân cận có hình

tròn).

Các đối tượng trong mỗi cụm được phân làm 2 loại: đối tượng bên trong

cụm (core point: đối tượng nòng cốt) và đối tượng nằm trên đường biên của

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

cụm (border point: đối tượng biên). Ngoài ra còn có những đối tượng không

thuộc trong cụm nào (noise point: đối tượng nhiễu).

Hình 2.1: Ví dụ về đối tượng nòng cốt, đối tượng biên và đối tượng nhiễu

Các tác giả của thuật toán đưa vào một số định nghĩa sau:

Định nghĩa 1: Vùng lân cận Eps của đối tượng p, ký hiệu Neps(p) là tập

hợp các đối tượng q sao cho khoảng cách giữa p và q: dist(p,q) nhỏ hơn Eps.

Neps(p) = {q∈D | dist(p,q) ≤ Eps}

Tính chất:

- Nói chung vùng lân cận của đối tượng biên có số đối tượng ít hơn đáng

kể so với đối tượng biên.

Định nghĩa 2: Đối tượng p là đối tượng có mật độ đạt được trực tiếp

(directly density-reachable) từ đối tượng q theo Eps, Minpts nếu p ∈ Neps(p) và

q là đối tượng nòng cốt (|Neps(p) | ≥ MinPts).

Tính chất:

- Nếu p, q đều là đối tượng nòng cốt thì mật độ đạt được trực tiếp là đối

xứng, nghĩa là p tới được trực tiếp theo mật độ từ q và ngược lại.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Nếu trong p, q có một đối tượng nòng cốt (core point), còn đối tượng còn

lại là đối tượng biên (border point) thì chỉ đối tượng biên là mật độ đạt

được trực tiếp từ đối tượng nòng cốt mà không có chiều ngược lại.

Hình 2.2: Ví dụ về mật độ đạt được trực tiếp

Định nghĩa 3: Đối tượng p là đối tượng mật độ đạt được từ đối tượng q

theo Eps & MinPts nếu tồn tại một dây chuyền các đối tượng p1,…,pn với p1 =

q, pn = p sao cho pi + 1 là đối tượng có mật độ đạt được trực tiếp từ pi

Tính chất:

- Mật độ đạt được là sự mở rộng của mật độ đạt được trực tiếp.

- Mật độ đạt được có tính chất bắc cầu.

- Nếu p, q đều là đối tượng nòng cốt thì mật độ đạt được là quan hệ đối

xứng nghĩa là p là mật độ đạt được từ q và ngược lại.

- Nếu p, q đều là đối tượng biên thì p không phải là mật độ đạt được từ q

và ngược lại.

- Nếu trong p, q có một đối tượng nòng cốt, một đối tượng còn lại là đối

tượng biên thì chỉ đối tượng biên là mật độ đạt được từ đối tượng nóng

cốt mà không có chiều ngược lại.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 2.3: Ví dụ về mật độ đạt được

Định nghĩa 4: Một đối tượng p là mật độ liên thông từ đối tượng q theo

Eps & MinPts nếu tồn tại đối tượng o sao cho cả p,q là đối tượng có mật độ có

thể đạt được từ o theo Eps & MinPts.

Tính chất:

- Đối với các đối tượng là mật độ đạt được với đối tượng khác thì mật độ

liên thông có tính ánh xạ.

- Mật độ liên thông có tính đối xứng.

Hình 2.4: Ví dụ về mật độ liên thông

Định nghĩa 5: Cho cơ sở dữ liệu D, cụm C thỏa Eps và MinPts là tập

con khác rỗng của D thỏa 2 điều kiện sau:

- ∀p,q: nếu p ∈C và q liên hệ theo mật độ từ p thỏa Eps và MinPts thì q∈C.

- ∀p,q∈C: p kết nối theo mật độ với p thỏa Eps và MinPts.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Cụm C thỏa định nghĩa trên sẽ có ít nhất MinPts đối tượng vì lý do sau:

C phải có ít nhất một đối tượng p (C khác rỗng), p phải liên hệ mật độ với bản

thân nó thông qua một đối tượng o (điều kiện 2 của định nghĩa 5). Vì vậy, o là

đối tượng lõi và vùng lân cận Eps của o có ít nhất MinPts đối tượng (do p có

liên hệ mật độ từ o).

Định nghĩa 6: Cho các cụm C1,…,Ck của cơ sở dữ liệu D với các tham

số Epsi and MinPtsi, (i = 1, . . ., k). Tập nhiễu là tập các đối tượng thuộc D

nhưng không thuộc bất kỳ cụm Ci nào.

Noise = {p∈D | ∀i: p ∉ Ci}

Như đã biết, các thuật toán theo hướng mật độ đều sử dụng hai tham số

là Eps và MinPts, giá trị của hai tham số này có ảnh hưởng lớn đến kết quả

phân cụm. Thực tế cho thấy không có cách xác định chính xác giá trị tối ưu của

hai tham số này. Một cách lý tưởng là xác định được một phần tử khởi tạo và

một cặp giá trị Eps –MinPts ban đầu cho mỗi cụm. Nhưng điều này là không

tưởng vì trước khi phân cụm thì chúng ta hoàn toàn không có được thông tin

về độ phân bố và đặc tính của dữ liệu trong CSDL. Nhóm tác giả DBSCAN

đưa ra một heuristic tương đối hiệu quả và đơn giản để xác định các tham số

Eps và MinPts của cụm “thưa nhất” (thinnest) trong CSDL. Sau đó, sử dụng

giá trị này làm giá trị toàn cục Eps và MinPts cho tất cả các cụm.

Nhóm tác giả còn bổ sung hai bổ đề để quan trọng để kiểm tra tính đúng

đắn của thuật toán. Với các tham số đã Eps và MinPts cho trước, có thể phát

hiện một cụm theo phương pháp dựa trên mật độ theo hai bước sau: Bước 1:

chọn một điểm bất kì trong CSDL thỏa mãn điều kiện điểm lõi, coi điểm này

là hạt giống (seed). Bước 2: tìm tất cả các điểm kề mật độ với điểm hạt giống

(điểm lõi) trong cụm.

Bổ đề 1: Gọi p là một điểm trong D và |NEps(p)| MinPts. Tập O = {o | o

D và o là điểm kề mật độ với p} là một cụm.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Không hoàn toàn chắc chắn rằng cụm C được xác định một cách duy

nhất bởi một điểm nhân nào của nó. Tuy nhiên, mỗi điểm trong C là điểm kề

mật độ với một điểm nhân bất kì của C và theo đó C chính xác chứa các điểm

mà kề mật độ với một điểm nhân bất kì của C.

Bổ đề 2: Cho C là một cụm và p là điểm bất kỳ trong C, nếu |NEps(p)|

MinPts thì C bằng với tập O = {o | o là điểm kề mật độ với p}.

 Thuật toán

Để xác định các cụm, DBSCAN bắt đầu với một điểm p bất kỳ trong

CSDL và tìm tất cả các điểm kề mật độ với p. Nếu p là điểm nòng cốt, thuật

toán sẽ tạo ra một cụm xuất phát từ p (xem bổ đề 2). Nếu p là điểm biên thì

không có điểm nào kề mật độ với p và DBSCAN sẽ duyệt điểm tiếp theo trong

CSDL.

Do các tham số Eps và MinPts là tham số toàn cục, sử dụng để tìm tất cả

các cụm trong cơ sở dữ liệu cho dù mật độ các đối tượng trong các cụm có thể

khác nhau nên DBSCAN có thể trộn 2 cụm theo định nghĩa 5 thành một cụm,

nếu hai cụm này là “gần” với nhau. Khoảng cách giữa hai tập điểm S1 và S2

được định nghĩa là dist(S1, S2) = min {dist(p,q) | p S1, q S2}. Hai tập điểm có

các điểm tối thiểu của một cụm mỏng sẽ tách rời nhau chỉ nếu khoảng cách

giữa hai tập lớn hơn Eps. Do đó, lời gọi đệ quy của DBSCAN có thể là cần thiết

để phát hiện các cụm với giá trị MinPts cao hơn.

Phiên bản cơ bản của DBSCAN như sau:

DBSCAN (SetOfPoints, Eps, MinPts)

// SetOfPoints là tập chưa phân lớp.

ClusterId := nextId(NOISE);

FOR i FROM 1 TO SetOfPoints.size DO

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Point := SetOfPoints.get(i);

IF Point.ClId = UNCLASSIFIED THEN

IF ExpandCluster(SetOfPoints, Point,ClusterId, Eps, MinPts) THEN

ClusterId := nextId(ClusterId)

END IF

END FOR

END; // DBSCAN

Trong đó, SetOfPoints là toàn bộ CSDL hoặc cụm được phát hiện từ lần

chạy trước. Eps và MinPts là các tham số mật độ toàn cục được xác định bằng

tay hoặc dựa trên heuristic. Hàm SetOfPoints.get(i) trả về phần tử thứ i của

SetOfPoints. Hàm quan trọng nhất được sử dụng bởi DBSCAN là

ExpandCluster được minh hoạ như sau:

ExpandCluster(SetOfPoints, Point, ClId, Eps,MinPts) : Boolean;

seeds:=SetOfPoints.regionQuery(Point,Eps);

IF seeds.size

SetOfPoint.changeClId(Point,NOISE);

RETURN False;

ELSE // tất cả các điểm trong seeds là kề mật độ với Point

SetOfPoints.changeClIds(seeds,ClId);

seeds.delete(Point);

WHILE seeds <> Empty DO

currentP := seeds.first();

result := SetOfPoints.regionQuery(currentP,Eps);

IF result.size >= MinPts THEN

FOR i FROM 1 TO result.size DO

resultP := result.get(i);

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

IF resultP.ClId

IN {UNCLASSIFIED, NOISE} THEN

IF resultP.ClId = UNCLASSIFIED THEN

seeds.append(resultP);

END IF;

SetOfPoints.changeClId(resultP,ClId);

END IF; // UNCLASSIFIED hoặc NOISE

END FOR;

END IF; // result.size >= MinPts

seeds.delete(currentP);

END WHILE; // seeds <> Empty

RETURN True;

END IF

END; // ExpandCluster

Hàm SetOfPoints.regionQuery(Point,Eps) trả về lân cận epsilon

(EpsNeighborhood) của Point trong SetOfPoints như một danh sách các điểm.

Các truy vấn không gian có thể được hỗ trợ một cách hiệu quả bằng cách lập

chỉ mục không gian hệ thống CSDL không gian sử dụng các phương pháp như

cây tứ phân, cây Rtree, cây R*-tree…Khi đó, chi phí cho một truy vấn không

gian chỉ còn là O(logn) với CSDL có n điểm trong trường hợp xấu nhất. Với

mỗi n điểm của CSDL, chúng ta có nhiều nhất một truy vấn không gian. Do đó,

độ phức về thời gian trung bình của DBSCAN là O(n*logn).

Giá trị ClId (clusterId) của đối tượng có trị là NOISE (nhiễu) có thể thay

đổi khi đối tượng có tới được theo mật độ từ đối tượng khác. Các đối tượng này

được không thêm vào danh sách các đối tượng hạt giống (đối tượng đại diện

cho một cụm) vì các đối tượng này không phải là đối tượng lõi (core point).

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Nếu 2 cụm C1 và C2 gần nhau, có thể có một số đối tượng p nằm trong cả

2 cụm C1 và C2. Khi đó, p là đối tượng nằm ở biên của cụm vì nếu không C1 và

C2 trùng nhau do DBSCAN sử dụng cùng thông số Eps và MinPts cho tất cả

các cụm. Trong trường hợp này, đối tượng p thuộc về cụm được phát hiện ra

trước. Ngoại trừ các tình huống hiếm xảy ra này, kết quả của DBSCAN độc lập

với thứ tự các đối tượng được duyệt do bổ đề 2.

 Xác định tham số mật độ Eps và MinPts

Các tác giả thuật toán đã xây dựng một heuristic đơn giản nhưng hiệu

quả để xác định các tham số Eps và MinPts của cụm “thưa nhất” trong CSDL.

Heuristic này dựa trên các nhận xét sau: Gọi d là khoảng cách từ điểm dữ liệu

p tới k láng giềng gần nhất, thì d láng giềng của p chứa đúng k+1 điểm đối với

hầu hết các điểm p. d láng giềng của p chứa nhiều hơn k+1 điểm chỉ khi một số

điểm có cùng khoảng cách d tới điểm p. Hơn nữa, thay đổi hệ số k đối với một

điểm trong cụm không tạo ra một sự thay đổi lớn nào đối với d. Điều này chỉ

xảy ra khi k láng giềng gần nhất của p với k=1, 2, 3… được xác định xấp xỉ

trên một đường thẳng.

Khi các điểm trong CSDL được sắp xếp theo thứ tự (giảm dần hoặc tăng

dần) giá trị k-dist của nó, thì đồ thị các giá trị k-dist của mối điểm trong CSDL

sẽ thể hiện một số dấu hiệu có liên quan đến phân bố mật độ của các điểm trong

CSDL. Gọi đồ thị này là đồ thị k-dist đã sắp xếp. Nếu chọn một điểm p bất kỳ,

gán tham số Eps với kdist(p) và gán tham số MinPts với k, tất cả các điểm bằng

hoặc nhỏ hơn giá trị k-dist sẽ là những điểm hạt nhân. Nếu chúng ta có thể xác

định điểm ngưỡng với giá trị k-dist lớn nhất trong cụm “mỏng nhất” của D, thì

chúng ta sẽ có các giá trị tham số mật độ. Điểm ngưỡng (threshold point) là

điểm đầu tiên trong vùng đầu tiên của đồ thị k-dist đã được sắp xếp. Tất cả các

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

điểm có giá trị cao hơn k-dist (ở bên trái điểm ngưỡng) có thể coi là nhiễu, tất

cả các điểm còn lại (ở bên phải điểm ngưỡng) được gán cho một số cụm nào

đó.

Hình 2.5: Minh họa đồ thị khoảng cách 4-dist đã được sắp xếp của một CSDL

Nhìn chung, việc xác định ra vùng đầu tiên một cách tự động khá khó

khăn, nhưng lại rất dễ dàng đối với người sử dụng tự xác định thấy vùng này

trên đồ thị. Vì vậy, nhóm tác giả trên đề xuất một phương pháp tương tác để

xác định điểm ngưỡng như sau:

DBSCAN cần có hai tham số, Eps và MinPts. Tuy nhiên, các thí nghiệm

đã chỉ ra rằng đồ thị k-dist với k>4 không có sai khác gì nhiều so với đồ thị 4-

dist, hơn nữa, lại phải tính toán nhiều hơn. Vì vậy, gán tham số MinPts bằng 4

với tất cả CSDL (dữ liệu 2 chiều). Nhóm tác giả trên đã đề xuất phương pháp

tương tác sau để xác định tham số Eps của DBSCAN:

 Hệ thống tính toán và hiển thị đồ thị 4-disp cho CSDL.

 Nếu người sử dụng có thể đánh giá tỷ lệ phần trăm của nhiễu, thì tỷ lệ

này được đưa vào và hệ thống lấy đánh giá này để xác định điểm ngưỡng.

 Người sử dụng chấp nhận điểm ngưỡng này hoặc tự lựa chọn điểm

ngưỡng khác. Giá trị 4-dist của điểm ngưỡng được sử dụng như giá trị

Eps trong DBSCAN.

 Hiệu quả của thuật toán

Để đánh giá hiệu quả của DBSCAN, các tác giả của thuật toán đã so sánh

với thuật toán khá nổi tiếng là CLARANS. Kết quả thực nghiệm của các tác giả

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

cho thấy thời gian thực hiện của DBSCAN là một hàm gần tuyến tính với số

điểm dữ liệu, trong khi đó thời gian thực hiện của CLARANS xấp xỉ hàm bậc

2 của số điểm dữ liệu.

Hình 2.6: Kết quả thực nghiệm đánh giá thời gian thực hiện thuật toán (tính

theo giây) trên 2 thuật toán của nhóm tác giả

Các tác giả cũng chỉ ra rằng DBSCAN tốt hơn CLARANS gấp 250 đến

1900 lần trong các thí nghiệm, hệ số này sẽ tăng lên khi kích thước của CSDL

lớn dần lên. Với cùng CSDL mẫu trong hình vẽ dưới thì CLARANS và

DBSCAN cho kết quả lần lượt như minh họa ở hình dưới (các điểm được phát

hiện cùng một cụm được minh họa bằng màu giống nhau).

Hình 2.7: Các cụm phát hiện được bởi CLARANS (a) và DBSCAN (b)

Như vậy, DBSCAN hiệu quả hơn trong việc phát hiện ra các cụm với

hình dạng bất kì, kể cả hình không lồi. Và khử nhiễu tốt hơn CLARANS. Tuy

nhiên DBSCAN hoạt động kém hiệu quả hơn khi: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

 Nếu các cụm có mật độ khác nhau nhiều thì DBSCAN sẽ không giữ được

tính hiệu quả. Trên những dữ liệu như thế ta phải áp dụng mật độ của

cụm có mật độ thấp nhất cho tất cả các cụm khác. Với các cụm có mật

độ rất cao thì DBSCAN tốn nhiều thời gian để xác định lân cận của các

điểm một cách không cần thiết.

 Nếu có quan tâm đến các thuộc tính phi không gian (non-spatial) thì sử

dụng DBSCAN không thích hợp vì DBSCAN không chú ý đến các thuộc

tính đó.

2.3. Thuật toán DBRS

Thuật toán DBRS (Density-Based Spatial Clustering Method with

Random Sampling) được tác giả Howard J.Hamilton và Xin Wang giới thiệu

năm 2003 [WAHA03]. Tư tưởng của thuật toán gần tương tự với thuật toán

DBSCAN. Tuy nhiên, DBRS khắc phục được một số hạn chế mà thuật toán

DBSCAN còn mắc phải. Như đã nói trong mục trước, thuật toán DBSCAN

hoạt động không còn hiệu quả khi mà các cụm được phát hiện có mật độ khác

nhau nhiều hoặc dữ liệu có đặc tính phi không gian. DBRS được giới thiệu là

thuật toán phân cụm dữ liệu không gian với các đặc trưng như sau:

 Các cụm được phát hiện có nhiều hình dạng khác nhau. Chẳng hạn như

dữ liệu về địa chỉ của sinh viên của một trường đại học. Khi phân cụm

sinh viên theo địa chỉ thì có thể có các cụm sinh viên tại các nhà chung

cư (cụm có dạng hình chữ nhật), cụm sinh viên dọc theo các tuyến xe

bus (cụm có dạng tuyến),...

 Các cụm có mật độ khác nhau nhiều. Một ví dụ như CSDL nghiên cứu

về sự phân bố khách hàng của một công ty, ở các thành phố lớn thì khách

hàng của công ty rất nhiều, còn ở các vùng hẻo lánh thì lượng khách hàng

thưa thớt. Vì các thành phố lớn dân số tập trung đông hơn nhiều các vùng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

hẻo lánh. Như vậy các cụm được phát hiện sẽ có mật độ khác nhau khá

lớn.

 Dữ liệu có những đặc tính phi không gian (non-spatial).

 Áp dụng tốt với các CSDL có kích thước lớn với hàng trăm nghìn điểm.

DBRS là sự mở rộng của thuật toán DBSCAN, các định nghĩa của thuật

toán DBSCAN vẫn được dùng bình thường, ngoài ra còn có thêm một số định

nghĩa sau đây, nhằm tính tới cả các ảnh hưởng của các thuộc tính phi không

gian.

Cho CSDL D, hàm khoảng cách đối xứng dist, các tham số MinPts, Eps

và thuộc tính prop (định nghĩa cho khía cạnh thuộc tính phi không gian).

Định nghĩa 7: Lân cận ghép

Lân cận ghép (matching neighborhood) của một điểm p là tập:

N’Eps = {q: dist(p,q) <= Eps và p.prop = q.prop}

DBRS sử dụng các thông tin phi không gian trong quá trình tìm lân cận,

và dùng một ngưỡng tối thiểu MinPur để quản lí độ đồng nhất (purity) của lân

cận. Một điểm gọi là điểm lõi (core point) nếu nó có lân cận ghép trù mật, tức

là lân cận đó có ít nhất MinPts điểm và có ít nhất MinPur điểm lân cận ghép.

Điểm biên (border point) là một điểm lân cận của điểm nhân, nhưng không phải

là điểm lõi. Một điểm không là điểm lõi hoặc điểm biên thì được coi là điểm

nhiễu (noise).

Định nghĩa 8: Kề mật độ đồng nhất trực tiếp

Điểm p và điểm q được gọi là kề mật độ đồng nhất trực tiếp (directly

purity-densityreachable) với nhau nếu:

Quan hệ kề mật độ đồng nhất trực tiếp là đối xứng với 2 điểm lõi hoặc 1

điểm lõi và 1 điểm biên, nhưng không đối xứng với 2 điểm biên.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Định nghĩa 9: Kề mật độ đồng nhất

Điểm p và điểm q được gọi là kề mật độ đồng nhất với nhau (purity-

density-reachable) và kí hiệu là PD(p,q) nếu có một tập điểm p1, p2, ... ,pn. p1 =

q, pn = p sao cho pi+1 là kề mật độ đồng nhất trực tiếp với pi (1 i n-1).

Định nghĩa 10: Cụm mật độ đồng nhất

Một cụm C được gọi là cụm mật độ đồng nhất (purity-density-based

cluster) là một tập con không rỗng của D thỏa mãn điều kiện sau: Với mọi điểm

p,q trong D, nếu p C và p,q là kề mật độ đồng nhất với nhau thì q C. Từ đó suy

ra ta thấy mọi cặp điểm trong C đều kề mật độ đồng nhất với nhau.

Một điều hiển nhiên là để chắc chắn tìm được các cụm mật độ đồng nhất

thì chúng ta có thể xét trực tiếp các quan hệ liên thông mật độ của các điểm

bằng việc duyệt các lân cận ghép của nó. Tuy nhiên thao tác thực hiện tuy vấn

miền là để tìm lân cận là rất tốn kém. Chúng ta sẽ cố gắng giảm truy vấn miền

nếu có thể, vì thao tác truy vấn miền là thao tác có chi phí cao nhất trong các

thuật toán phân cụm dựa trên mật độ. Thuật toán DBRS thực hiện ít truy vấn

miền hơn, vì dựa vào một điều hiển nhiên là một cụm bao gồm một số tối thiểu

các điểm lõi và các lân cận ghép của chúng. Trong một cụm trù mật (cụm có

mật độ cao) thì một lân cận có thể có nhiều hơn MinPts điểm, việc duyệt chi

tiết các lân cận của các điểm đó là không cần thiết vì chúng ta đã biết chúng

thuộc một cụm. Như vậy, để xác định một cụm ta cần tìm hết các điểm xương

của nó, tuy nhiên để tìm xương là một bài toán NP-đủ. Thay vì tìm các điểm

khung DBRS chọn ngẫu nhiên điểm mẫu, tìm lân cận của chúng rồi ghép lại

nếu chúng giao nhau. Nếu số điểm mẫu đủ lớn thì ta có thể xác định xấp xỉ các

cụm mà không cần duyệt qua mọi điểm. Điểm mẫu có thể không là điểm khung,

nhưng số truy vấn miền sẽ giảm đáng kể so với DBSCAN trên bộ dữ liệu có

mật độ thay đổi nhiều.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Thuật toán DBRS có thể được mô tả ngắn gọn như sau: DBRS bắt đầu

từ một điểm bất kì q và tìm lân cận ghép qseeds có số điểm MinPts và độ đồng

nhất MinPur thì q là điểm lõi, ngược lại coi q là điểm nhiễu hoặc điểm biên.

Nếu q là điểm lõi thì kiểm tra lân cận của q có giao với một cụm đã có không,

danh sách các cụm đã có được lưu trong ListCluster, nếu có giao với một cụm

thì trộn qseeds với cụm đó, nếu giao với nhiều cụm thì hợp các cụm đó với

qseeds. Ngược lại thì tạo ra một cụm mới. Quá trình lặp lại cho đến khi tòan bộ

các điểm của D đã được đưa vào một cụm nào đó hoặc là được gán là nhiễu.

Có thể mô tả thuật toán bằng đoạn mã giả Pascal như sau:

Algorithm DBRS(D, Eps, MinPts, MinPur)

ClusterList := Empty;

WHILE (D.isClassified = False) DO

Select one unclassified point q from D;

qseeds := D.matchingNeighbors(q, Eps);

IF ((|qseeds| < MinPts) or (qseeds.pur < MinPur)) THEN

q.clusterID := -1;/* q là điểm nhiễu hoặc điểm biên */

ELSE

isFirstMerge := True;

Ci := ClusterList.firstCluster;

/* so sánh qseeds với tất cả các cụm đã có */

WHILE (Ci <> Empty) DO

IF (hasIntersection(qSeeds, Ci)) THEN

IF (isFirstMerge) THEN

newCi := Ci.merge(qseeds);

isFirstMerge := False;

ELSE

newCi := Ci.merge(Ci)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

ClusterList.deleteCluster(C);

END IF

Ci := ClusterList.NextCluster;

END WHILE;

/* không giao với một cụm nào đã tồn tại */

IF (isFirstMerge) THEN

Create a new cluster C

j từ qseeds;

ClusterList := ClusterList.addCluste(Cj);

END IF; // isFirstMerge

END IF;

END WHILE; //D.isClassified = False

Trong thuật toán DBRS thì truy vấn miền

D.matchingNeighbors(q,Eps) là tốn nhiều thời gian nhất. Nếu sử dụng các

cấu trúc chỉ mục không gian như cây R* hoặc cây tứ phân thì độ phức tạp của

thủ tục này là O(logn). Trường hợp xấu nhất là n điểm trong CSDL đều là nhiễu

thì cần n truy vấn nên độ phức tạp là O(n logn). Tuy nhiên nếu tìm thấy một

điểm lõi thì số lần truy vấn giảm đi rất nhiều vì các điểm thuộc lân cận ghép thì

không cần truy vấn miền nữa.

Để cải tiến tốc độ thực hiện thuật toán, DBRS sử dụng một kỹ thuật

heurictis gọi là DBS-H, kỹ thuật này dựa trên nhận xét rằng: Ban đầu, bằng

cách chọn ngẫu nhiên 1 điểm p và xem xét các điểm lân cận của nó thì xác suất

tìm được một cụm mới với ít nhất MinPts điểm lớn nhất là . Gọi nj

là số điểm bị loại sau khi điểm ngẫu nhiên thứ j được chọn. Với điểm ngẫu

nhiên là điểm nhiễu thì nj = 1, với điểm ngẫu nhiên là điểm lõi thì nj ít nhất bằng

1 và nếu một cụm mới được tạo ra từ điểm lõi này thì nj ít nhất bằng MinPts

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

điểm. Đặt là tổng các điểm bị loại sau i-1 điểm ngẫu nhiên được xem

xét. Thì xác suất tìm được một cụm mới với ít nhất MinPts điểm là

, giá trị của αk bằng cách phân tích thì khó, nhưng khi

DBRS thực hiện thì xác định αk tương đối dễ dàng. Đặt Li = n - Ni , Li là số

điểm còn lại chưa được phân cụm hoặc gán nhãn là nhiễu, ban đầu α0 = 1, L0 =

n , tại bước thứ i, , Li-1 = Li-1 - ni . DBRS sẽ dừng nếu

αi ≤ αmaxhoặc là tất cả các điểm đã được phân cụm (hoặc được gán là nhiễu).

Giá trị αmax do người dùng tự đặt, chẳng hạn, trong thí nghiệm của các tác giả

thì khả năng không còn tìm ra một cụm của thuật toán, khi đặt αmax = 0.01

nào mới nữa với độ tin cậy là 99%.

 Hiệu quả của thuật toán DBRS

Hình 2.8: Các cụm được phát hiện bởi DBRS(a), DBSCAN(b), K-Means(c),

CLARANS(d)

Hình 2.8 biểu diễn các cụm phát hiện được bởi DBRS(a), DBSCAN(b),

KMeans(c), CLARANS(d) với cùng CSDL (các cụm khác nhau được biểu diễn

bởi các màu khác nhau) trong thí nghiệm của các tác giả của thuật toán. Đặc

điểm nổi bật của DBRS so với các thuật toán khác là tốc độ thực hiện nhanh

hơn rất nhiều, vì DBRS thực hiện ít truy vấn miền hơn. So với K-Means và

CLARANS thì DBRS và DBSCAN phát hiện nhiễu tốt hơn. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

2.4. Thuật toán OPTICS

Mặc dù giải thuật phân cụm dựa trên mật độ DBSCAN có thể tìm ra cụm

các đối tượng với việc lựa chọn các tham số đầu vào như s và MinPts, người

dùng vẫn chịu trách nhiệm lựa chọn các giá trị tham số tốt để tìm ra các cụm

chính xác. Trên thực tế, đây là bài toán có sự kết hợp của nhiều giải thuật phân

cụm khác. Các thiết lập tham số như vậy tương đối khó, đặc biệt trong thế giới

thực, các tập dữ liệu có số chiều cao. Hầu hết các giải thuật rất nhạy với các

tham số : các thiết lập có sự khác biệt nhỏ có thể dẫn tới các phân chia dữ liệu

rất khác nhau. Hơn nữa, các tập dữ liệu thực số chiều cao thường có phân bố

rất lệch, thậm trí ở đó không tồn tại một thiết lập tham số toàn cục cho đầu vào.

Để khắc phục khó khăn này, một phương pháp sắp xếp cụm gọi là

OPTICS (Ordering Point To Identify the Clustering Structuer) được phát triển

bởi Ankerst, Breunig , Kriegel và Sander năm 1999. nó cải tiến bằng cách giảm

bớt các tham số đầu vào. Thuật toán này không phân cụm các điểm dữ liệu mà

thực hiện tính toán và sắp xếp trên các điểm dữ liệu theo thứ tự tăng dần nhằm

tự động phân cụm dữ liệu và phân tích cụm tương tác hơn là đưa ra phân cụm

một tập dữ liệu rõ ràng. Đây là thứ tự mô tả cấu trúc phân dữ liệu cụm dựa trên

mật độ của dữ liệu, nó chứa thông tin tương ứng với phân cụm dựa trên mật độ

từ một dãy các tham số được thiết lập và tạo thứ tự của các đối tượng trong cơ

sở dữ liệu, đồng thời lưu trữ khoảng cách lõi và khoảng cách liên lạc phù hợp

của mỗi đối tượng. Hơn nữa, thuật toán được đề xuất rút ra các cụm dựa trên

thứ tự thông tin. Như vậy thông tin đủ cho trích ra tất cả các cụm dựa trên mật

độ khoảng cách bất kỳ s’ mà nhỏ hơn khoảng cách 8 được sử dụng trong sinh

thứ tự.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Việc sắp xếp thứ tự được xác định bởi hai thuộc tính riêng của các điểm

dữ liệu đó là khoảng cách nhân và khoảng cách liên lạc. Các phép đo này chính

là kích thước mà có liên quan đến quá trình của thuật toán DBSCAN, tuy nhiên,

chúng được sử dụng đế xác định thứ tự của các điếm dữ liệu đã được sắp xếp.

Thứ tự dựa trên cơ sở các điếm dữ liệu mà có khoảng cách nhân nhỏ nhất và

tăng dần độ lớn. Điều duy nhất về phương pháp này là người sử dụng không

phải xác định giá trị 8 hoặc MinPts phù hợp.

Hình 2.9: Sắp xếp cụm trong OPTICS phụ thuộc vào ɛ

Thuật toán này có thể phân cụm các đối tượng đã cho với các tham số

đầu vào như ɛ và MinPts, nhưng nó vẫn cho phép người sử dụng tùy ý lựa chọn

các giá trị tham số mà sẽ dẫn đến khám phá các cụm chấp nhận được. Các thiết

lập tham số thường dựa theo kinh nghiệm tập hợp và khó xác định, đặc biệt là

với các tập dữ liệu đa chiều.

Tuy nhiên, nó cũng có độ phức tạp thời gian thực hiện như DBSCAN

bởi vì có cấu trúc tương đương với DBSCAN: O(nlogn) với n là kích thước của

tập dữ liệu. Thứ tự cụm của tập dữ liệu có thế được biếu diễn bằng đồ thị, và

được minh họa hình sau, có thế thấy ba cụm, giá trị ɛ quyết định số cụm.

2.5. Thuật toán DENCLUDE

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DENCLUDE (Density – base Clustering) do Hinneburg và Keim vào

năm 1998 đưa ra cách tiếp cận khác với các thuật toán phân cụm dựa trên mật

độ trước đó, cách tiếp cận này xem xét mô hình được sử dụng một công thức

toán để mô tả mỗi điểm dữ liệu sẽ ảnh hưởng trong mô hình như thế nào được

gọi là hàm ảnh hưởng có thế xem như một hàm mà mô tả ảnh hưởng của điểm

dữ liệu với các đối tượng lân cận của nó. Ví dụ về hàm ảnh hưởng là các hàm

Parabolic, hàm sóng ngang, hoặc hàm Gaussian.

Như vậy, DENCLUDE là phương pháp dựa trên một tập các hàm phân

bổ mật độ và được xây dựng ý tưởng chính như sau :

 Ảnh hưởng của mỗi điểm dữ liệu có thế là hình thức được mô hình sử

dụng một hàm tính toán, được gọi là hàm ảnh hưởng, mô tả tác động của

điếm dữ liệu với các đối tượng lân cận của nó.

 Mật độ toàn cục của không gian dữ liệu được mô hình phân tích như là

tổng các hàm ảnh hưởng của tất cả các điếm dữ liệu.

 Các cụm có thế xác định chính xác bởi việc xác định mật độ cao (density

attractors), trong đó mật độ cao là các điếm cực đại hàm mật độ toàn cục.

Sử dụng các ô lưới không chỉ giữ thông tin về các ô lưới mà thực tế nó

còn chứa đựng cả các điểm dữ liệu. Nó quản lý các ô trong một cấu trúc truy

cập dựa trên cây và như vậy nó nhanh hơn so với một số các thuật toán có ảnh

hưởng như DBSCAN. Tuy nhiên, phương pháp này đòi hỏi chọn lựa kỹ lưỡng

tham biến mật độ và ngưỡng nhiễu, việc chọn lựa tham số là quan trọng ảnh

hưởng tới chất lượng của các kết quả phân cụm.

Định nghĩa : Cho x, y là hai đối tượng trong không gian d chiều ký hiệu

là Fd. Hàm ảnh hưởng của đối tượng y ϵ Fd lên đối tượng x là một hàm

mà được định nghĩa dưới dạng một hàm ảnh hưởng cơ bản

. Hàm ảnh hưởng có thế là một hàm bất kỳ; cơ bản là xác

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

định khoảng cách của hai véctơ d(x, y) trong không gian d chiều, ví dụ như

khoảng cách Euclide. Hàm khoảng cách có tính chất phản xạ và đối xứng. Ví

dụ về hàm ảnh hưởng như sau:

 Hàm ảnh hưởng sóng ngang :

trong đó ô là một ngưỡng.

 Hàm ảnh hưởng Gaussian :

Mặt khác, hàm mật độ tại điểm x ϵ Fd được định nghĩa là tổng các hàm

ảnh hưởng của tất cả các điếm dữ liệu. Cho n là các đối tượng dữ liệu được mô

tả bởi một tập véctơ D = {xi, x2, ... , xn} ϵ Fd hàm mật độ được định nghĩa như

Hàm mật độ được thành lập dựa trên ảnh hưởng Gaussian được xác định

như sau:

Ví dụ về kết quả phân cụm dữ liệu của thuật toán DENCLUE với hàm

chi phối Gausian được biểu diễn như sau. Các cực đại mật độ là các giá trị tại

đỉnh của đồ thị. Một cụm cho một cực đại mật độ x* là tập con C, khi các hàm

mật độ tại x* không bé hơn δ.

Hình 2.10: DENCLUE với hàm phân phối Gaussian

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

DENCLUE phụ thuộc nhiều vào ngưỡng nhiễu và tham số mật độ nhưng

DENCLUE có các lợi thế chính được so sánh với các thuật toán phân cụm khác

sau đây :

 Có cơ sở toán học vững chắc và tổng quát hóa các phương pháp phân

cụm khác, bao gồm các phương pháp phân cấp, dựa trên phân hoạch.

 Có các đặc tính phân cụm tốt cho các tập dữ liệu với số lượng lớn và

nhiễu.

 Cho phép các cụm có hình dạng bất kỳ trong tập dữ liệu đa chiều được

mô tả trong công thức toán.

Độ phức tạp tính toán của DENCLUDE là O(nlogn). Các thuật toán dựa

trên mật độ không thực hiện kỹ thuật phân mẫu trên tập dữ liệu như trong các

thuật toán phân cụm phân hoạch, vì điều này có thế làm tăng thêm độ phức tạp

đã có sự khác nhau giữa mật độ của các đối tượng trong mẫu với mật độ của

toàn bộ dữ liệu.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỰC NGHIỆM

Trong chương này sẽ xây dựng một chương trình thực nghiệm để áp dụng

phương pháp phân cụm dữ liệu dựa trên mật độ bằng thuật toán DBSCAN với

ý tưởng bài toán thực tế là phân nhóm các điểm phát sóng viễn thông trong một

khu vực. Do kiến thức và thời gian hạn chế nên trong khuân khổ luận văn em

chỉ xây dựng chương trình thực nghiệm với tính chất mô phỏng, nên chương

trình chưa có khả năng áp dụng vào trong thực tế. Rất mong nhận được sự đóng

góp ý kiến của thầy cô để em có thể phát triển hoàn thiện chương trình đưa vào

áp dụng trong thực tế.

3.1. Ý tưởng bài toán

Do nhu cầu nâng cao chất lượng dịch vụ viễn thông nên việc lắp đặt

thêm các trạm phát sóng địa bàn của địa phương ngày càng tăng. Để đảm bảo

việc theo dõi quản lý được tốt hơn chúng ta nên phân các điểm lắp đặt các trạm

phát này thành các nhóm nhỏ để tiện cho việc phân công theo dõi, vận hành,

bào trì, khai thác sử dụng.

3.2. Nguồn dữ liệu đầu vào

Giả sử ta có tọa độ các vị trí lắp đặt trạm phát sóng viễn thông trong một

khu vực. Dựa vào các tọa độ đó ta mô phỏng các vị trí đó thành các điểm trên

hệ thống bản đồ của chương trình.

Như vậy, dữ liệu đầu vào sử dụng trong bài toán chủ yếu là các lớp thông

tin dạng điểm, phạm vi trong một khu vực trên bản đồ.

3.3. Phương pháp giải quyết bài toán

 Lựa chọn phương pháp phân cụm:

Với đặc điểm của dữ liệu đầu vào ở trên ta lựa chọn phương pháp phân

cụm dựa trên mật độ bởi:

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

- Đối tượng dữ liệu cần phân cụm chủ yếu là các điểm, tức là các đối tượng

dạng điểm. Kiểu này khá phù hợp với phương pháp tiếp cận dựa trên mật

độ.

- Không cần thiết phải biết trước số cụm sau khi phân cụm có được, do đó

không sử dụng tiếp cận phân hoạch.

- Không cần lưu trữ thông tin các mức trung gian trong quá trình phân

cụm, do đó không sử dụng tiếp cận theo lưới.

 Lựa chọn độ đo sử dụng trong phân cụm:

Chúng ta quan tâm đến tính liên tục về mặt không gian của các điểm

trong cụm và khoảng cách giữa các điểm này chứ không quan tâm đến hướng

của chúng. Hơn nữa với các đối tượng dạng điểm, quan hệ về topology mang

ít ý nghĩa ngoại trừ các đối tượng này mang thông tin về mạng lưới liên thông

như: mạng lưới cột điện, mạng lưới cấp nước…Do vậy ta sử dụng độ đo

khoảng cách trong bài toán phân cụm đã đề ra (các độ đo đã được đề cập ở

mục 1.2.6.2, chương 1).

3.4. Kết quả thực nghiệm

Giả sử ta có dữ liệu mẫu nhập vào là 60 điểm trên hệ thống bản đồ của

chương trình, sau đó chạy thuật toán DBSCAN để phân cụm các điểm này với

Eps = 37 & MinPts = 3 ta thu được 9 cụm tương ứng với 9 màu khác nhau thể

hiện trên bản đồ.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Hình 3.1: Kết qua sau khi phân cụm của chương trình thực nghiệm

Tổng có [60] điểm:

(218, 192) (251, 197) (237, 215) (242, 249) (278, 275) (268, 233) (297, 212)

(307, 254) (366, 267) (358, 220) (399, 209) (421, 181) (412, 139) (430, 118)

(472, 124) (482, 90) (502, 77) (528, 114) (570, 151) (601, 193) (618, 235) (575,

266) (559, 220) (576, 187) (527, 180) (515, 148) (481, 206) (507, 238) (524,

271) (543, 312) (549, 360) (524, 382) (466, 364) (412, 368) (380, 344) (410,

308) (415, 261) (427, 255) (455, 319) (496, 354) (528, 352) (488, 290) (481,

270) (470, 244) (461, 220) (469, 162) (333, 233) (419, 339) (395, 246) (596,

226) (526, 297) (427, 325) (589, 241) (408, 117) (436, 143) (403, 92) (482,

188) (405, 336) (441, 345) (476, 105)

Cụm [1] chứa [6] điểm:

(218, 192) (251, 197) (237, 215) (242, 249) (268, 233) (297, 212)

Cụm [2] chứa [4] điểm:

(278, 275) (307, 254) (358, 220) (333, 233)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Cụm [3] chứa [6] điểm:

(366, 267) (399, 209) (421, 181) (415, 261) (427, 255) (395, 246)

Cụm [4] chứa [5] điểm:

(412, 139) (430, 118) (408, 117) (436, 143) (403, 92)

Cụm [5] chứa [4] điểm:

(472, 124) (482, 90) (502, 77) (476, 105)

Cụm [6] chứa [8] điểm:

(570, 151) (601, 193) (618, 235) (575, 266) (559, 220) (576, 187) (596, 226)

(589, 241)

Cụm [7] chứa [3] điểm:

(528, 114) (527, 180) (515, 148)

Cụm [8] chứa [11] điểm:

(481, 206) (507, 238) (524, 271) (543, 312) (488, 290) (481, 270) (470, 244)

(461, 220) (469, 162) (526, 297) (482, 188)

Cụm [9] chứa [13] điểm:

(549, 360) (524, 382) (466, 364) (412, 368) (380, 344) (410, 308) (455, 319)

(496, 354) (528, 352) (419, 339) (427, 325) (405, 336) (441, 345)

Không có điểm nào thuộc đối tượng nhiễu.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

KẾT LUẬN

1. Những kết quả chính của luận văn

Luận văn tìm hiểu bài toán phân cụm dữ liệu và đi sâu tìm hiểu phân cụm

dữ liệu dựa trên mật độ. Luận văn đã đạt được những kết quả chính là:

- Nghiên cứu tổng quan về khai phá dữ liệu và phân cụm dữ liệu. Các

phương pháp, lĩnh vực và các hướng tiếp cận trong phân cụm dữ liệu.

- Nghiên cứu chi tiết phương pháp phân cụm dữ liệu dựa trên mật độ và

các thuật toán liên quan. Tìm hiêu sâu thuật toán DBSCAN qua các đánh

giá và so sánh.

- Xây dựng chương trình thực nghiệm áp dụng phương pháp phân cụm dữ

liệu dựa trên mật độ bằng thuật toán DBSCAN với bài toán thực tế phân

nhóm các trạm phát sóng viễn thông trong một khu vực.

 Ý nghĩa khoa học của luận văn:

Qua quá trình thực nghiệm và nghiên cứu lý thuyết có thể đưa ra một số

kết luận như sau:

- Mỗi một giải thuật phân cụm áp dụng cho một số mục tiêu và kiểu dữ

liệu nhất định.

- Mỗi giải thuật có một mức độ chính xác riêng và khả năng thực hiện trên

từng kích thước dữ liệu là khác nhau. Điều này còn tuỳ thuộc vào cách

thức tổ chức dữ liệu ở bộ nhớ chính, bộ nhớ ngoài... của các giải thuật.

- Khai phá dữ liệu sẽ hiệu quả hơn khi bước tiền xử lý, lựa chọn thuộc

tính, mô hình được giải quyết tốt.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

2. Hướng nghiên cứu tiếp theo:

- Hướng nghiên cứu của luận văn có thể được mở rộng sang lớp dữ liệu

không gian, sử dụng trong khai phá dữ liệu liên quan đến các đối tượng

địa lý.

- Vấn đề phân cụm dữ liệu đa chiều có thể được thử nghiệm để so sánh

với phương pháp hiện tại là phân cụm đơn chiều kết hợp với phân tích

đa chiều dữ liệu không gian.

- Một số ràng buộc và trọng số có thể được đưa vào bài toán để có thể khai

phá dữ liệu một cách mềm dẻo và linh hoạt trong các điều kiện cụ thể

của bài toán.

- Phương pháp tiếp cận sử dụng phân cụm mờ có thể được thử nghiệm bởi

tính tương đối cố hữu áp dụng với bài toán tối ưu.

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] Nguyễn Hoàng Tú Anh,“Khai thác dữ liệu và ứng dụng”, Giáo trình , Đại

học KHTN Tp Hồ Chí Minh,2009.

[2] Vũ Lan Phương, “Nghiên cứu và cài đặt một số giải thuật phân cụm phân

lớp”, Luận văn thạc sĩ, Đại học Bách khoa Hà Nội, 2006.

Tiếng Anh

[3] Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996), “A density-based

algorithm for discovering clusters in large spatial databases with noise”,

Second Int. Conf. on Knowledge Discovery and Data Mining , (pp. 226-231).

Portland, Oregon.

[4] Jiawei Han, Micheline Kamber, Data Mining: Concepts and techniques,

Second Edition, Elsevier Inc, 2011.

[5] M.Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth, and Ramasamy

Uthurusamy, Advances in Knowledge Discovery and Data Mining, AAAI

Press/ The MIT Press,1996.

[6] Oracle, Oracle Data Mining Concepts 10g Release 1 (10.1), Oracle

Corporation, 2003.

[7] P. Berkhin, Survey of Clustering Data Mining Techniques, Research paper.

Accrue Software, Inc, http://www.accrue.com, 2009.

[8] http://home.deib.polimi.it/matteucc/Clustering/tutorial_html/index.html

[9] https://en.wikipedia.org/wiki/Cluster_analysis

[10] https://en.wikipedia.org/wiki/DBSCAN

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

PHỤ LỤC

 Mã code chính của chương trình:

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace DBSCAN_GUI { public class Algoritam { public const int NOISE = -1; public const int UNCLASSIFIED = 0; public List D = new List(); public double eps; public int MinPts; public List> klasteri; public String text; public void dodajTocku(int x, int y) { D.Add(new Tocka(x, y)); } public int dist(Tocka p, Tocka q) { return (int)Math.Sqrt(Math.Pow(q.X - p.X, 2) + Math.Pow(q.Y - p.Y, 2)); } public void pokreniAlgoritam(List D) { klasteri = DBSCAN(D, eps, MinPts); text += "Tổng có [" + D.Count + "] điểm:\n"; foreach (Tocka p in D) text += p; int total = 0; for (int i = 0; i < klasteri.Count; i++) { int count = klasteri[i].Count; total += count;

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

text += "\n\nCụm [" + (i + 1) + "] chứa [" + count + "] điểm:\n"; foreach (Tocka p in klasteri[i]) text += p; } total = D.Count - total; if (total > 0) { text += "\n\nCó [" + total + "] điểm không thuộc cụm nào:\n"; foreach (Tocka p in D) { if (p.C == NOISE) text += p; } } else { text += "\n\nNo points that represent noise.\n"; } } public List> DBSCAN(List D, double eps, int MinPts) { if (D == null) return null; List> klasteri = new List>(); int C = 1; for (int i = 0; i < D.Count; i++) { Tocka p = D[i]; if (p.C == UNCLASSIFIED) if (expandCluster(D, p, C, eps, MinPts)) C++; } int total = D.OrderBy(p => p.C).Last().C; if (total < 1) return klasteri; for (int i = 0; i < total; i++) klasteri.Add(new List()); foreach (Tocka p in D) {

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

if (p.C > UNCLASSIFIED) klasteri[p.C - 1].Add(p); } return klasteri; } public bool expandCluster(List NeighborPts, Tocka p, int C, double eps, int MinPts) { List seeds = regionQuery(NeighborPts, p, eps); if (seeds.Count < MinPts) { p.C = NOISE; return false; } else { for (int i = 0; i < seeds.Count; i++) seeds[i].C = C; seeds.Remove(p); while (seeds.Count > 0) { Tocka currentP = seeds[0]; List result = regionQuery(NeighborPts, currentP, eps); if (result.Count >= MinPts) { for (int i = 0; i < result.Count; i++) { Tocka resultP = result[i]; if (resultP.C == UNCLASSIFIED || resultP.C == NOISE) { if (resultP.C == UNCLASSIFIED) seeds.Add(resultP); resultP.C = C; } } } seeds.Remove(currentP); } return true; } } public List regionQuery(List D, Tocka p, double eps)

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

{ List okolina = new List(); for (int i = 0; i < D.Count; i++) { if (dist(p, D[i]) <= eps) okolina.Add(D[i]); } return okolina; } } }

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn

Luận văn Thạc sĩ Khoa học máy tính: Phân cụm dữ liệu dựa trên mật độ và ứng dụng

α+δ

τ

α

𝛼+ 𝛽+𝛾

{ List okolina = new List(); for (int i = 0; i < D.Count; i++) { if (dist(p, D[i]) <= eps) okolina.Add(D[i]); } return okolina; } } }

Có thể bạn quan tâm

Luận văn Thạc sĩ: Quản lý hoạt động phát triển nhận thức cho trẻ mẫu giáo ở các trường mầm non, huyện Hoàng Su Phì, tỉnh Hà Giang

Luận văn Thạc sĩ tóm tắt: Pháp luật về điều kiện đầu tư kinh doanh trong lĩnh vực giáo dục, đào tạo ở Việt Nam

Luận văn Thạc sĩ: Sự nghiệp nghiên cứu phê bình văn học của Hoài Thanh

Luận văn Thạc sĩ: Tiểu thuyết của Đỗ Phấn từ góc nhìn sinh thái

Luận văn Thạc sĩ: Giải pháp ứng phó với nhập cư ở Liên minh Châu Âu

Luận văn Thạc sĩ: Diễn ngôn về giới nữ trong văn xuôi nữ Việt Nam đương đại (khảo sát sáng tác của Dạ Ngân, Y Ban, Lý Lan, Nguyễn Thị Thu Huệ)

Luận văn Thạc sĩ: Xây dựng mức phát thải tham chiếu rừng khu vực huyện Bảo Lâm tỉnh Lâm Đồng

Luận văn Thạc sĩ: Đặc điểm nhân vật chính trong ba tác phẩm của Franz Kafka: Lâu đài, Vụ án, Hóa thân

Kháo luận tốt nghiệp: Vận dụng lí thuyết học tập trải nghiệm vào dạy học Thống kê - Xác suất ở lớp Hai

Luận văn Thạc sĩ: Xây dựng hệ thống điều khiển và thu nhận dữ liệu cho Robot dịch vụ

Luận văn Thạc sĩ: Thế giới nhân vật trong truyện ngắn Lê Minh Khuê sau năm 1975

Luận văn Thạc sĩ: Tác động của cấu trúc vốn đến hiệu quả hoạt động của các ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Kiểm soát rủi ro tín dụng bán lẻ tại Ngân hàng Thương mại Cổ phần Đầu tư và Phát triển Việt Nam chi nhánh Thủ Thiêm

Luận văn Thạc sĩ: Các yếu tố ảnh hưởng đến hiệu quả kinh doanh của ngân hàng thương mại cổ phần niêm yết trên thị trường chứng khoán Việt Nam

Luận văn Thạc sĩ: Các nhân tố ảnh hưởng đến hành vi sử dụng dịch vụ ngân hàng điện tử tại Ngân hàng Thương mại Cổ phần Ngoại thương Việt Nam – Chi nhánh Thủ Đức

Luận văn Thạc sĩ: Các yếu tố tác đồng đến nợ xấu tại Ngân hàng Nông nghiệp và Phát triển Nông thôn - Chi nhánh Tiền Giang

Luận văn Thạc sĩ: Yếu tố ảnh hưởng đến quyết định sử dụng dịch vụ thanh toán không dùng tiền mặt tại Ngân hàng TMCP Công thương Việt Nam (Vietinbank)

Luận văn Thạc sĩ tóm tắt: Pháp luật về du lịch biển, thực tiễn tại tỉnh Bình Định

Luận văn Thạc sĩ: Ảnh hưởng của các yếu tố thương hiệu với vai trò trung gian của Marketing truyền miệng đến quyết định chọn việc làm của nhân viên GenZ tại chuỗi nhà hàng gà rán Popeyes khu vực Thành Phố Hồ Chí Minh

Luận văn Thạc sĩ: Ảnh hưởng của Marketing mix đến ý định học cao học của sinh viên khối ngành kinh tế thuộc Trường Đại học Công nghệ Thành phố Hồ Chí Minh

Tài liêu mới

Luận án Tiến sĩ: Nghiên cứu xây dựng thuật toán thích nghi và học tăng cường cấu trúc Actor - Critic điều khiển bám quỹ đạo cho robot di động đa hướng mecanum

Luận án Tiến sĩ: Cơ cấu bệnh tim mạch và chất lượng cuộc sống của người cao tuổi mắc suy tim, rung nhĩ điều trị tại Bệnh viện Thống Nhất, thành phố Hồ Chí Minh

Tóm tắt Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

Tóm tắt Luận án Tiến sĩ: Nghiên cứu xây dựng giải pháp đảm bảo an toàn thông tin cho quá trình học liên kết dựa trên mật mã

Tóm tắt Luận án Tiến sĩ: Phát triển năng lực đánh giá công nghệ cho học sinh trong dạy học môn Công nghệ 11 ở trường trung học phổ thông

Tóm tắt Luận án Tiến sĩ: Nghiên cứu phân loại chi cầu diệp – Bulbophyllum Thouars (Orchidaceae) ở vùng Tây Nguyên bằng phương pháp hình thái và phân tử

Tóm tắt Luận án Tiến sĩ: Nghiên cứu đặc điểm phân bố và dinh dưỡng của các loài lưỡng cư ở Vườn Quốc gia Bến En và Khu bảo tồn thiên nhiên Pù Luông, tỉnh Thanh Hóa

Luận án Tiến sĩ: Tổng hợp luật dẫn và điều khiển cho một lớp tên lửa đối hải trên cơ sở ứng dụng mạng nơ ron và hệ mờ

Luận án Tiến sĩ: Nghiên cứu tổng hợp hệ điều khiển góc Pitch tua bin gió trong điều kiện có nhiễu tác động

Luận án Tiến sĩ: Nghiên cứu hóa học lipid của hai loài san hô thủy tức Millepora dichotoma và Millepora platyphylla ở Việt Nam

Luận án Tiến sĩ: Nghiên cứu kiểm soát phân phối công suất kéo trên cầu chủ động của ô tô con bằng ABS

Luận án Tiến sĩ: Ứng dụng phản ứng Domino vào tổng hợp các dẫn xuất Podophyllotoxin, Pyrimidine và đánh giá hoạt tính sinh học của các chất tổng hợp được

Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và một số hoạt tính sinh học của cây chùm ngây (Moringa oleifera)

Tóm tắt Luận án Tiến sĩ: Nghiên cứu thành phần hóa học và ứng dụng ức chế ăn mòn cho thép của cao chiết xuất từ cây Lộc vừng thuộc họ Lecythidaceae

Luận án Tiến sĩ: Nghiên cứu hiện tượng nứt dăm đê sông vùng đồng bằng sông Hồng và dự báo khả năng bị nứt của một số đoạn đê

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok