Tóm tắt Luận văn Phương pháp phân cụm dữ liệu web và xây dựng ứng dụng trong máy tìm kiếm

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

ĐẠI HỌC ĐÀ NẴNG

NGUYỄN ĐÌNH ĐỊNH

PHƢƠNG PHÁP PHÂN CỤM DỮ LIỆU WEB VÀ

XÂY DỰNG ỨNG DỤNG TRONG MÁY TÌM KIẾM

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

Mã số: 60.48.01

TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT

Đà Nẵng - Năm 2012

Công trình đƣợc hoàn thành t

ại

ĐẠI HỌC ĐÀ N NG

Ẵ

Ngƣời hƣớng dẫn khoa học: PGS.TS. Lê Văn Sơn

Phản biện 1: TS. Nguyễn Thanh Bình

Phản biện 2: TS. Lê Xuân Việt

Luận văn sẽ được bảo vệ tại Hội ñồng chấm Luận văn tốt

nghiệp Thạc sĩ Kỹ thuật họp tại Đại học Đà Nẵng vào ngày

19 tháng 01 năm 2013.

* Có thể tìm hiểu Luận văn tại:

- Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng

- Trung tâm Học liệu, Đại học Đà Nẵng.

1

MỞ ĐẦU

1. Tính cấp thiết của đề tài

- Sư ph ꢀt triꢁn nhanh chꢂng cꢃa cꢀc ꢄng dụng công nghệ

thông tin va Internet vao nhiêu linh vưc đơi sông xa hôi , quản lꢅ kinh

tê, khoa hoc ky thuât … đa tao ra nhiêu cơ sơ dư liêu không lô . Cꢀc

cơ sơ dư liêu nay không phai khi nꢆo cꢇng bất biꢈn theo thꢉi gian mꢆ

cꢊng vꢋi sꢌ phꢀt triꢁn trên , cꢀc cơ sꢍ dꢎ liệu cꢇng không ngꢏng thay

đôi đê đap ưng nhu câu sư dung cua con ngươ . Quꢀ trình tiꢈn hꢂa

̣

̀

̃

̣

̀

́

̃

̣

́

̣

̃

̣

̃

̣

̀

̉

̃

̣

̉

̀

̉

̃

̣

̀

̉

́

̀

̉

̣

̉

̀ i

cꢃa lĩnh vꢌc cơ sꢍ dꢎ liệu (CSDL) tạo nên việc khai phꢀ dꢎ liệu

(Data Mining) được coi lꢆ giai đoạn tiꢈn hꢂa mꢋi cꢃa công nghệ

CSDL, việc thu thập vꢆ lưu trꢎ cꢀc kho chꢄa dꢎ liệu khổng lồ được

liệt kê ꢍ ngoꢆi mục đích khai phꢀ dꢎ liệu, nhằm phꢀt hiện cꢀc tri thꢄc

mꢋi giúp ích cho hoạt động cꢃa con ngưꢉi trong tập hợp dꢎ liệu.

Chẳng hạn, tꢏ một giải phꢀp phân cụm trong khai phꢀ dꢎ liệu Web

(Web Mining), cꢂ thꢁ phꢀt triꢁn thꢆnh một thꢆnh phần cꢃa mꢀy tìm

kiꢈm (Search Engine) đꢁ khi một trang Web mꢋi được tải về, mꢀy

tìm kiꢈm sẽ tꢌ động nꢂ vꢆo một cụm trang Web đã được xꢀc định;

việc phân cụm sẽ tạo ra thuận lợi cho việc tìm kiꢈm về sau cho ngưꢉi

dꢊng. Chính vì lꢅ do nꢆy mꢆ tôi nghiên cꢄu vꢆ chọn đề tꢆi: “Phương

pháp phân cụm dữ liệu Web và xây dựng ứng dụng trong máy tìm

kiếm” lꢆ điều cấp thiꢈt hiện nay, dưꢋi sꢌ hưꢋng dẫn cꢃa thầy PGS-

TS. Lê Văn Sơn.

2. Mục tiêu nghiên cứu

Mục tiêu lꢆ nắm được một số phương phꢀp phân cụm dꢎ liệu

Web tꢏ đꢂ xây dꢌng dꢎ liệu tìm kiꢈm nhanh thông qua cꢀc địa chỉ tꢏ

khꢂa cần tìm. Đꢁ thꢌc hiện mục đích ꢅ tưꢍng đề ra cần nghiên cꢄu

và tiꢈn hành triꢁn khai các nội dung như sau:

2

- Nghiên cꢄu cơ sꢍ lý thuyꢈt về các khai phá dꢎ liệu Web

trong việc tìm kiꢈm.

- Thu thập, phân loại các phân cụm Web tꢏ thuật toán cổ điꢁn

đꢈn hiện tại.

- Tìm hiꢁu các thuật toán phân cụm hiện có.

- Xây dꢌng được chất lượng cꢃa các kꢈt quả tìm kiꢈm sẽ tốt

hơn trong việc phân cụm văn bản trên Web.

- Xử lý tꢏng mẫu thông tin ngay khi lấy được tꢏ Web có kꢈt

quả tꢄc thꢉi ꢄng vꢋi tại mỗi thꢉi điꢁm.

- Tạo các liên kꢈt vꢋi các trang Web tìm kiꢈm qua URL.

3. Đối tƣợng và phạm vi nghiên cứu

Tꢏ nhꢎng yêu cầu cꢃa đề tꢆi ta xꢀc định được đối tượng vꢆ

phạm vi nghiên cꢄu như sau:

* Đối tượng nghiên cứu:

- Xây dꢌng khai phꢀ dꢎ liệu số, phân loại theo dạng văn bản.

- Cấu trúc đối tượng lꢆ CSDL quan hệ, khai phꢀ dꢎ liệu Text

tꢌ do.

* Phạm vi nghiên cứu:

- Áp dụng phương phꢀp phân cụm trong việc tìm kiꢈm nhanh

cꢀc trang Web theo chꢃ đề tꢏ khꢂa cần tìm.

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

- Thu thập vꢆ phân tích cꢀc tꢆi liệu vꢆ thông tin liên quan đꢈn

đề tꢆi.

- Xem xét, lꢌa chọn phương phꢀp đꢁ giải quyꢈt vấn đề.

- Triꢁn khai xây dꢌng chương trình ꢄng dụng.

- Kiꢁm tra, thử nghiệm vꢆ đꢀnh giꢀ kꢈt quả.

5. Bố cục của đề tài

Luận văn được trình bꢆy bao gồm cꢀc phần chính như sau:

3

+ Phần mꢍ đầu

+ Chương 1: Tổng quan về khai phꢀ dꢎ liệu Web.

+ Chương 2: Một số phương phꢀp phân cụm dꢎ liệu.

+ Chương 3: Xây dꢌng phương phꢀp tìm kiꢈm vꢆ kꢈt quả thꢌc

nghiệm.

+ Phần kꢈt luận.

6. Tổng quan về tài liệu nghiên cứu

Mꢀy tìm kiꢈm (Search Engine) đã phꢀt triꢁn khꢀ hoꢆn thiện

vꢆo cuối thꢈ kỷ 20 ꢍ cꢀc nưꢋc phꢀt triꢁn. Ở Việt Nam, nghiên cꢄu vꢆ

ꢄng dụng mꢀy tìm kiꢈm đang trong giai đoạn phꢀt triꢁn ban đầu.

Trong luận văn nꢆy tꢆi liệu nghiên cꢄu vꢆ tham khảo cꢃa nhiều tꢀc

giả thưꢉng tìm hiꢁu sâu vꢆo cꢀc công nghệ quan trọng cꢃa mꢀy tìm

kiꢈm: phương phꢀp phân cụm dꢎ liệu, bộ lập chỉ mục (indexing), bộ

tìm kiꢈm (searching), bộ xꢈp hạng (ranking). Đồng thꢉi nghiên cꢄu

kiꢈn trúc cꢀc hệ thống URL sẵn cꢂ phục vụ mục đích xây dꢌng một

hệ tìm kiꢈm cho trang Web. Áp dụng nhꢎng thꢆnh tꢌu cꢃa khoa học

mꢀy tính đꢁ hoꢆn thiện cỗ mꢀy tìm kiꢈm lꢆ một công việc quan trọng

. Bꢍi tìm kiꢈm nhꢎng thꢄ tốt nhất phục vụ cho công việc vꢆ cuộc

sống lꢆ một nhu cầu rất cần thiꢈt cꢃa mỗi ngưꢉi.

Mỗi ngꢆnh cụ thꢁ lại cꢂ cꢀc phương phꢀp vꢆ công cụ tìm kiꢈm

đặc thꢊ khꢀc nhau, nhưng kꢈt quả cuối cꢊng lꢆ cho ra kꢈt quả tìm

kiꢈm tốt nhất. Trong quꢀ trình hoꢆn thꢆnh luận văn, tôi đã tìm hiꢁu

vꢆ sử dụng cꢀc nguồn tꢆi liệu rất cꢂ giꢀ trị sau đây:

Các tài liệu về phương phꢀp phân cụm dꢎ liệu; Hoꢆng Văn

Dꢇng, “Khai phá dữ liệu Web bằng kỹ thuật phân cụm”, luận văn

thạc sĩ, Trưꢉng ĐHSP Hꢆ Nội, 2007; Hà Quang Thụy, “Khai phá dữ

liệu Web”, Bꢆi giảng, Trưꢉng Đại học công nghệ, ĐHQGHN,2008;

Ho Tu Bao, Knowledge Discovery and Data Mining, 2000.

4

Các tài liệu về phân cụm và áp dụng bộ máy tìm kiꢈm; Hà

Quang Thụy, “Giáo trình khai phá dữ liệu Web”, Nhꢆ xuất bản giáo

dục Việt nam, 2009; Lizhen Liu, Junjie Chen, Hantao Song, The

research of Web Mining, IEEE, 2002; các nguồn dꢎ liệu hiện có hiện

nay bing.com .v.v.

5

CHƢƠNG 1

TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU

1.1. KHAI PHÁ DỮ LIỆU

1.1.1. Tại sao cần phải khai phá dữ liệu (datamining)

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

1.1.3. Các hƣớng tiếp cận và các kỹ thuật trong KPDL

1.1.4. Các loại dữ liệu có thể khai phá

1.1.5. Các ứng dụng của khai phá dữ liệu (KPDL)

a. Các ứng của khai phá dữ liệu (KPDL)

b. Những vấn đề chú trọng trong khai phá dữ liệu

1.2. KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU

1.2.1. Tổng quan về kỹ thuật phân cụm

1.2.2. Phân cụm là gì

1.2.3. Một số ứng dụng của phân cụm dữ liệu

1.2.4. Các yêu cầu đối với kỹ thuật phân cụm

1.2.5. Các kiểu dữ liệu và độ đo tƣơng tự

a. Các kiểu dữ liệu dựa trên kích thước miền

b. Khái niệm độ đo tương tự, phi tương tự và khoảng cách

1.3. KHAI PHÁ WEB

1.3.1. Giới thiệu về khai phá web và nhu cầu khai thác

thông tin

1.3.2. Đặc điểm của dữ liệu Web

1.3.3. Các hƣớng tiếp cận khai phá dữ liệu Web

1.3.4. Các kiểu dữ liệu Web

a. Sơ đồ dữ liệu Web

b. Dữ liệu văn bản

1.3.5. Một số xử lý văn bản trong khai phá dữ liệu Web

a. Xử lý dữ liệu văn bản

b. Loại bỏ từ dừng

6

Trong ngôn ngꢎ tꢌ nhiên thông thưꢉng cꢀc tꢏ thưꢉng biꢁu

diễn về cấu trúc câu chꢄ không biꢁu đạt nội dung cꢃa nꢂ. Do đꢂ cꢀc

tꢏ như giꢋi tꢏ, tꢏ nối … thưꢉng xuất hiện nhiều lần mꢆ không liên

quan gì về chꢃ đề hoặc nội dung văn bản nên ta phải loại bỏ đi đꢁ

giảm số chiều cꢃa vector biꢁu diễn văn bản, nhꢎng tꢏ như vậy được

gọi lꢆ nhꢎng tꢏ dꢏng.

c. Chọn từ gốc (Word stemming)

Trong tiꢈng anh hay trong nhiều ngôn ngꢎ khꢀc, nhiều tꢏ cꢂ

chung một nguồn gốc, hoặc lꢆ biꢈn sang tꢏ gốc nꢆo đꢂ. Chẳng hạn,

cꢀc tꢏ “computer”, “computers”, “computing” đều cꢂ chung một

nguồn gốc lꢆ “comput”. Ý tưꢍng chọn tꢏ gốc đꢁ biꢁu diễn cꢀc tꢏ

trong văn bản thông qua tꢏ gốc.

d. Kết hợp các từ có chung nguồn gốc

Hầu hꢈt trong cꢀc ngôn ngꢎ đều cꢂ rất nhiều tꢏ cꢂ chung

nguồn gốc vꢋi nhau, chúng mang ꢅ nghĩa tương tꢌ nhau. Đꢁ giảm

bꢍt số chiều trong biꢁu diễn văn bản, ta sẽ kꢈt hợp cꢀc tꢏ cꢂ cꢊng gốc

thꢆnh một tꢏ.

Ví dụ: Trong tiꢈng Anh cꢀc tꢏ user, users, used, using cꢂ cꢊng

tꢏ gốc vꢆ sẽ được quy về lꢆ use; cꢀc tꢏ engineering, engineered,

engineer cꢂ cꢊng tꢏ gốc sẽ được quy về lꢆ engineer. Ví dụ xử lꢅ tꢏ

gốc trong tiꢈng Anh:

- Nꢈu một tꢏ kꢈt thúc bằng “ing” thì xꢂa “ing”, ngoại trꢏ

trưꢉng hợp sau khi xꢂa còn lại một kꢅ tꢌ hoặc còn lại “th”.

- Nꢈu một tꢏ kꢈt thúc bằng “ies” nhưng không phải lꢆ “eies”

hoặc “aies” thì thay thꢈ “ies” bằng “y”.....

- Nꢈu một tꢏ kꢈt thúc bằng “es” thì bỏ “s”.

- Nꢈu một tꢏ kꢈt thúc bằng "s" vꢆ đꢄng trưꢋc nꢂ lꢆ một phụ

âm khꢀc “s” thì xꢂa “s”.

7

- Nꢈu một tꢏ kꢈt thúc bằng “ed”, nꢈu trưꢋc nꢂ lꢆ một phụ âm

thì xꢂa “ed” ngoại trꢏ sau khi xꢂa tꢏ chỉ còn lại một kꢅ tꢌ, nꢈu đꢄng

trưꢋc lꢆ nguyên âm “i” thì đổi “ied” thꢆnh “y”.

e. Đinh luật Zipf

Đꢁ mô tả định luật Zipf, ta gọi tổng số tần số xuất hiện cꢃa tꢏ t

trong tꢆi liệu D là f_t. Sau đꢂ sắp xꢈp tất cả cꢀc tꢏ trong tập hợp theo

chiều giảm dần cꢃa tần số xuất hiện f vꢆ gọi thꢄ hạng cꢃa mỗi tꢏ t là

r_t.

Định luật Zipf được phꢀt biꢁu dưꢋi dạng công thꢄc như sau:

(vꢋi K lꢆ một hằng số).

rt.ft K

Trong tiꢈng Anh, ngưꢉi ta thấy rằng hằng số:

K N/10

( N lꢆ số tꢏ trong văn bản bản)

Ta cꢂ thꢁ viꢈt lại định luật Zipf như sau:

r_tK/ f_t

Giả sử tꢏ t_iđược sắp xꢈp ꢍ vị trí thấp nhất vꢋi tần số xuất hiện

là b nꢆo đấy và tꢏ t_jcꢇng được sắp ꢍ vị trí thấp kꢈ tiꢈp vꢋi một tần số

xuất hiện là b+1. Ta có thꢁ thu được thꢄ hạng xấp xỉ cꢃa các tꢏ này

là:

rt_iK/b và rt_jK/(b+1)

Ta bắc đầu trꢏ 2 biꢁu thꢄc này cho nhau ta xấp xỉ đối vꢋi các

tꢏ riêng biệt có tần số xuất hiện là b.

rt_i- rt_jK/b-K/(b+1) = K/b(b+1)

8

Ta xấp xỉ giá trị cꢃa tꢏ trong tập hợp có thꢄ hạng cao nhất.

Một cách tổng quát, một tꢏ chỉ xuất hiện một lần trong tập hợp, ta có

rmax=K.

Xét phân bố cꢃa các tꢏ duy nhất xuất hiện b lần trong tập hợp,

chia 2 vꢈ cho nhau ta được K/b. Do đꢂ, định luật Zipf cho ta thấy sꢌ

phân bố đꢀng chú ꢅ cꢃa các tꢌ riêng biệt trong 1 tập hợp được hình

thành bꢍi các tꢏ xuất hiện ít nhất trong tập hợp.

Một câu hỏi thưꢉng đặt ra lꢆ: Tần số cꢂ phải lꢆ yꢈu tố quan

trọng trong văn bản hay không? Xét ví dụ trong [1][26] như sau:

Hình 1.1. Lược đồ thống kê tần số của từ theo định luật Zipf

1.3.6. Các phƣơng pháp biểu diễn dữ liệu văn bản

a. Phương pháp Booble

Cho một tập gồm m văn bản, D={d₁, d₂, ..., d_m}. Tập tꢏ vꢌng

được biꢁu diễn dưꢋi dạng một vector gồm n thuật ngꢎ T={t1,

t2,...,tn}. Gọi W={w_ij} lꢆ ma trận trọng số, w_ijlꢆ giꢀ trị trọng số cꢃa

thuật ngꢎ t_itrong tꢆi liệu d_j.

9

1 nꢈu t_id_j

0 nꢈu t_id_j

W_ij=

b. Phương pháp dựa trên tần số

*Phương pháp dựa trên tần số xuất hiện các từ khóa (TF-Term

Frequency)

Trong phương pháp dꢌa trên tần số xuất hiện tꢏ khóa (TF-

Term Frequency) giá trị cꢃa các tꢏ được tính dꢌa vào số lần xuất

hiện cꢃa nó trong tài liệu, gọi tf_ijlà số lần xuất hiện cꢃa tꢏ t_itrong tài

liệu d_j, khi đꢂ w_ijcó thꢁ được tính theo một trong các công thꢄc sau:

- W_ij= tf_ij

- W_ij= 1+log(tf_ij)

tf_ij

- W_ij=

* Phương pháp dựa trên nghịch đảo tần số văn bản (IDF- inverse

document Frequency)

Gọi df_ilꢆ trọng số văn bản cꢂ chꢄa tꢏ khꢂa t_itrong tập m văn

bản đang xét, thì giꢀ trị trọng số tꢏ W_ijđược tính bꢍi công thꢄc:

m

W log

log(m) log(df_i)

ij

df_i

* Phƣơng pháp kết hợp TF-IDF

Phương phꢀp nꢆy lꢆ tổng hợp hai phương phꢀp TF vꢆ IDF,

giꢀ trị cꢃa ma trận trọng số được tính như sau:

W_ij=

nꢈu tf_ij

1

[1 log(tf_ij)]log( )

df_i

0

nꢈu tf_ij= 0

10

1.3.7. Thu gọn đặc trƣng biểu diễn

Theo Dunja Mladenic bꢆi toꢀn lꢌa chọn (thu gọn) đặc trưng lꢆ

tꢏ một tập F cꢀc tập con F*, tập con cꢃa F cꢂ lꢌc lượng 2 ^Fphần tử

nꢂi trên, một số phương phꢀp tìm kiꢈm tập con F* điꢁn hình lꢆ:

- Lꢌa chọn “tiꢈn”: Xuất phꢀt tꢏ tập con rỗng, bổ sung dần

cꢀc đặc trưng tốt nhất vꢆo.

- Loại bỏ “lꢊi”: Xuất phꢀt tꢏ tập F, loại dần cꢀc đặc trưng

kém giꢀ trị ra.

- Lꢌa chọn “tiꢈn bậc thang”: Xuất phꢀt tꢏ tập con rỗng, trong

mỗi bưꢋc dꢊng chiꢈn thuật tham lam bổ sung vꢆ loại bỏ đặc trưng.

- Loại bỏ “lꢊi bậc thang”: Xuất phꢀt tꢏ tập F, trong mỗi bưꢋc

dꢊng chiꢈn thuật tham lam bổ sung vꢆ loại bỏ đặc trưng.

11

CHƢƠNG 2

MỘT SỐ PHƢƠNG PHÁP PHÂN CỤM DỮ LIỆU

2.1. PHÂN CỤM PHÂN HOẠCH

2.1.1. Thuật toán k-means

Tham số đầu vꢆo cꢃa thuật toꢀn lꢆ số cụm k, tập CSDL gồm n

phần tử vꢆ tham số đầu ra cꢃa thuật toꢀn lꢆ cꢀc trọng tâm cꢃa cꢀc

cụm dꢎ liệu. Độ đo khoảng cꢀch D giꢎa cꢀc đối tượng dꢎ liệu thưꢉng

được sử dụng dụng lꢆ khoảng cꢀch Euclide

Thuật toꢀn k-means là sinh ra k cụm dꢎ liệu {C₁, C₂,…, C_k} tꢏ

một tập dꢎ liệu ban đầu gồm n đối tượng trong không gian d chiều

Xi =(xi1, xi2, …,xid) (

), sao cho hꢆm tiêu chuẩn:

i 1,n

k

2(

)

x m_i

E

D

đạt giꢀ trị tối thiꢁu.

x Ci

i 1

2.1.2. Thuật toán Pam

PAM bắt đầu bằng cꢀch lꢌa chọn k đối tượng medoid bất kỳ.

Sau mỗi bưꢋc thꢌc hiện, PAM cố gắng hoꢀn chuyꢁn giꢎa đối tượng

medoid Om vꢆ một đối tượng Op không phải lꢆ medoid, miễn lꢆ sꢌ

hoꢀn chuyꢁn nꢆy là C_jmpnhằm cải tiꢈn chất lượng cꢃa phân cụm, quꢀ

trình nꢆy kꢈt thúc khi chất lượng phân cụm không thay đổi.

+ Nꢈu Oj hiện thꢉi thuộc về cụm cꢂ đại diện lꢆ Om, nhưng Oj

ít tương tꢌ vꢋi Om,2 so vꢋi Op (d(Oj,Op)< d(Oj,Om,2)). Lúc này giá

trị Cjmp được xꢀc định như sau: Cjmp=(Oj,Op)- d(Oj, Om). Cjmp ꢍ

đây cꢂ thꢁ lꢆ âm hoặc dương.

+ Giả sử Oj hiện thꢉi không thuộc về cụm cꢂ đối tượng đại

diện lꢆ Om mꢆ thuộc về cụm cꢂ đại diện lꢆ Om,2. Mặt khꢀc, giả sử

Oj tương tꢌ vꢋi Om,2 hơn so vꢋi Op, khi đꢂ, nꢈu Om được thay thꢈ

bꢍi Op thì Oj vẫn sẽ ꢍ lại trong cụm cꢂ đại diện lꢆ Om,2. Do đꢂ:

Cjmp = 0.

12

+ Giả sử lúc nꢆy Oj hiện thꢉi thuộc về cụm cꢂ đại diện lꢆ Om

và Oj tương tꢌ vꢋi Om,2 hơn Op (d(Oj, Op) d(Oj, Om,2)). Vì vậy,

giꢀ trị hoꢀn chuyꢁn Cjmp được xꢀc định như sau: Cjmp = d(Oj,

Om,2) – d(Oj, Om). Giꢀ trị Cjmp là không âm.

+ Nꢈu trưꢉng hợp Oj hiện thꢉi thuộc về cụm cꢂ đại diện lꢆ

Om,2 nhưng Oj ít tương tꢌ tꢋi Om,2 hơn so vꢋi Op. Do đꢂ, giꢀ trị

hoꢀn chuyꢁn Cjmp được xꢀc định lꢆ: Cjmp= (Oj,Op)- d(Oj, Om,2).

Cjmp ꢍ đây luôn âm.

2.1.3. Thuật toán CLARA

2.1.4. Thuật toán CLARANS

2.2. THUẬT TOÁN PHÂN CỤM TRÊN MẬT ĐỘ

2.2.1. Thuật toán phân cụm DBSCAN

2.2.2. Thuật toán phân cụm Optics

- 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 CSDL, đồ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.

- Phân cụm OPTICS xꢀc định cꢀc lꢆng giềng phꢊ hợp mật độ

thông tin tương đương vꢋi phân cụm dꢌa trên mật độ vꢋi dãy cꢀc

tham số đầu vꢆo.

2.2.3. Thuật toán phân cụm DENCLUDE

- 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 tất cả cꢀc hꢆm ảnh hưꢍng cꢃa cꢀc đối tượng.

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

2.3. THUẬT TOÁN PHÂN CẤP

2.3.1. Thuật toán CURE

13

- Chọn ngẫu nhiên tꢏ một tập dꢎ liệu ban đầu

- Phân hoạch mẫu nꢆy thꢆnh nhiều nhꢂm dꢎ liệu cꢂ kích thưꢋc

bằng nhau.

- Phân cụm cꢀc điꢁm cꢃa mỗi nhꢂm vꢆ loại bỏ cꢀc phần tử

ngoại lai sau đꢂ đꢀnh dấu dꢎ liệu vꢋi cꢀc nhãn tương ꢄng.

2.3.2. Thuật toán BIRCH

- Duyệt tấc cả cꢀc đối tượng trong CSDL gồm n đối tượng,

ngưỡng T vꢆ xây dꢌng cây CF khꢍi tạo.

- Nꢈu cây CF hiện thꢉi không đꢃ bộ nhꢋ thì tiꢈn hꢆnh xây

dꢌng một cây CF nhỏ hơn bằng cꢀch điều khiꢁn bꢍi tham số T.

- Thꢌc hiện phân cụm: cꢀc nút lꢀ cꢃa cây CF lưu giꢎ cꢀc đại

lượng thông kê cꢃa cꢀc cụm con..

- phân phối lại cꢀc dꢎ liệu trung tâm cho cꢀc cụm nhằm đꢁ gꢀn

cho cꢀc nhãn dꢎ liệu khꢍi tạo vꢆ loại bỏ cꢀc đối tượng ngoại lai.

2.3.3. Thuật toán ANGNES

- Thuật toán này bắt đầu ꢍ ngoài vꢋi mỗi đối tượng dꢎ liệu

trong các cụm riêng lẻ, các cụm được hòa nhập theo một số loại cꢃa

cơ sꢍ luật, cho đꢈn khi chỉ có một cụm ꢍ đỉnh cꢃa phân cấp, hoặc

gặp điều kiện dꢏng. Hình dạng này cꢃa phân cụm phân cấp cꢇng liên

quan đꢈn tiꢈp cận Bottom-up bắt đầu ꢍ dưꢋi vꢋi các nút lá trong mỗi

cụm riêng lẻ và duyệt lên trên phân cấp tꢋi nút gốc, nơi tìm thấy cụm

đơn cuối cùng vꢋi tất cả cꢀc đối tượng dꢎ liệu được chꢄa trong cụm

đꢂ.

2.3.4. Thuật toán Chameleon

- Thuật toꢀn nꢆy dꢌa trên tiꢈp cận đồ thị k-lꢀng giềng gần nhất

- Chameleon chỉ ra sꢌ tương đồng giꢎa mỗi cặp cꢀc cụm C_ivà

C_jtheo liên kꢈt nối tương đối RI(C_i,C_j) vꢆ độ chặt tương đối

RC(C_i,C_j) cꢃa chúng. Liên kꢈt nối tương đối RI(C_i,C_j) giꢎa hai cụm

14

C_ivà C_jđược định nghĩa như liên kꢈt nối tuyệt đối giꢎa C_ivà C_jđã

tiêu chuẩn hꢂa đối vꢋi liên kꢈt nối nội tại cꢃa hai cụm C_ivà C_j. Đꢂ lꢆ

EC_{C ,C}

i

j

RI(C_i,C_j)

;

1

2

EC_CEC_C

i

j

Vꢋi

lꢆ cạnh cắt (edge-cut) cꢃa cụm chꢄa cả C_ivà C_jđꢁ

EC_{C ,C}

i

j

cụm nꢆy được rơi vꢆo trong C_ivà C_j, tương tꢌ như vậy (hay

EC_C

i

_Cj) lꢆ kích thưꢋc cꢃa Min-cut bisector ( tꢄc lꢆ tổng số cꢃa cꢀc

EC

cạnh mꢆ chia đồ thị thꢆnh hai phần thô bằng nhau).

Độ chặt tương đối giꢎa một cặp cꢀc cụm C_ivà C_jlà

được định nghĩa như lꢆ độ chặt tuyệt đối giꢎa C và C

RI(C_i,C_j)

i

j

được tiêu chuẩn hꢂa đối vꢋi liên kꢈt nối nội tại cꢃa hai cụm C_ivà C_j.

Đꢂ lꢆ:

S _EC

Ci,Cj

RC(C_i,C_j)

;

C_i

C_iC_j

C_i

C_iC_j

* S _EC

Ci

Cj

Vꢋi

lꢆ trọng số trung bình cꢃa cꢀc cạnh kꢈt nối cꢀc đỉnh

S_EC

Ci,Cj

trong C_itꢋi cꢀc đỉnh C_jvà

(hay

) lꢆ trọng số trung bình

S

EC_Ci

EC_Cj

cꢃa cꢀc cạnh thuộc về Min-cut bisector cꢃa cụm C_ivà C_j.

2.4. PHƢƠNG PHÁP PHÂN CỤM DỰA TRÊN LƢỚI

2.4.1. Thuật toán STING

- Xác định cꢀc tầng, mỗi tầng nꢆy tính toꢀn khoảng tin cậy cꢃa

xꢀc xuất Cell nꢆy liên quan tꢋi truy vấn.

- Tính khoảng tin cậy cꢃa tính toꢀn trên, gꢀn nhãn cho cꢂ hoặc

không liên quan

- Nꢈu lꢋp nꢆy lꢆ lꢋp cuối cꢊng thì đăc tả truy vấn; nꢈu không

thì duyệt xuống dưꢋi cấu trúc cây phân cấp một mꢄc

15

- Nꢈu đặc tả truy vấn, tìm thấy miền cꢂ cell liên quan trả lại

miền phꢊ hợp vꢋi yêu cầu cꢃa truy vấn vꢆ dꢏng ; nꢈu không truy lục

lại dꢎ liệu vꢆo trong cꢀc Cells liên quan vꢆ thꢌc hiện xử lꢅ trả lại kꢈt

quả phꢊ hợp vꢆ dꢏng.

2.4.2. Thuật toán WaveCluster

- Dꢎ liệu vꢆo lꢆ cꢀc vectơ đặc trưng cꢃa cꢀc đối tượng dꢎ liệu

đa chiều.

- Lượng tử hꢂa không gian đặc trưng, sau đꢂ phân cꢀc ĐT vꢆo

cꢀc unit; sau đꢂ ꢀp dụng biꢈn đổi wavelet trong không gian đặc

trưng;

- Tìm cꢀc thꢆnh phần đã kꢈt nối cꢀc cụm

- Gán các nhãn vào các Unit

- Lꢆm cꢀc bảng tra cꢄu vꢆ ꢀnh xạ cꢀc đối tượng vꢆo cꢀc cụm;

2.4.3. Thuật toán Clique

- Phân hoạch tập dꢎ liệu thꢆnh cꢀc hình hộp chꢎ nhật vꢆ tìm

cꢀc hình hộp chꢎ nhật đặc.

- Xác định không gian con chꢄa cꢀc cụm được sử dụng nguyên

lý apriori

- Hợp cꢀc hình hộp nꢆy tạo thꢆnh cꢀc cụm dꢎ liệu

- Xác định cꢀc cụm: trưꢋc hꢈt nꢂ tìm cꢀc cell đặc đơn chiều,

tiꢈp đꢈn chúng tìm cꢀc hình chꢎ nhật 2 chiều, rồi 3 chiều, v.v. cho

đꢈn khi hình hộp chꢎ đặc k chiều tìm thấy.

2.5. CÁC THUẬT TOÁN PHÂN CỤM DỰA TRÊN MÔ HÌNH

2.5.1. Thuật toán Cobweb

- Khꢍi tạo cây bắt đầu bằng một nút rỗng.

- Sau khi thêm vꢆo tꢏng nút một vꢆ cập nhật lại cây cho phꢊ

hợp tại mỗi thꢉi điꢁm.

- Cập nhật cây bắt đầu tꢏ lꢀ bên phải trong mỗi trưꢉng hợp,

sau đꢂ cấu trúc lại cây.

16

- Quyꢈt định cập nhật dꢌa trên sꢌ phân hoạch vꢆ cꢀc hꢆm tiêu

chuẩn phân loại.

2.5.2. Thuật toán EM

Thuật toꢀn EM dꢌa trên cꢀc tính chất cꢃa dꢎ liệu: Cꢂ thꢁ nén,

cꢂ thꢁ sao lưu trong bộ nhꢋ vꢆ cꢂ thꢁ hꢃy bỏ.

17

CHƢƠNG 3

XÂY DỰNG PHƢƠNG PHÁP TÌM KIẾM VÀ KẾT QUẢ

THỰC NGHIỆM

3.1. KHAI PHÁ TRONG QUÁ TRÌNH TÌM KIẾM VÀ DUYỆT

WEB

3.2. HOẠT ĐỘNG VÀ TÍNH TOÁN ĐẠI LƢỢNG PAGERANK

- Cꢀc hệ số cần tìm giúp đưa ra kꢈt quả cꢂ độ chính xꢀc cao.

- Liên kꢈt cꢃa Web đꢁ tính toꢀn độ quan trọng cho tꢏng trang

Web.

- Sử dụng liên kꢈt nꢆy đꢁ xꢈp hạng kꢈt quả (Ranking) tính toán

nhanh chꢂng đại lượng PageRank.

* Đại lượng pagerank được định nghĩa như sau:

Giả sử trang A cꢂ cꢀc trang T₁, T₂, ...,T_ntrỏ tꢋi. Tham số d lꢆ

hệ số hãm cꢂ giꢀ trị trong khoảng 0 vꢆ 1. Chúng ta thưꢉng đặt

d=0.85. C(A) lꢆ số liên kꢈt ra tꢏ trang A. Khi đꢂ Pagerank cꢃa A

được tính như sau :

PR(A)=(1-d)+d(PR(T₁)/C(T₁) + ....+PR(Tn)/C(T(n)).

Ta thấy lập chỉ mục cꢀc liên kꢈt giꢎa cꢀc trang Web site vꢆ thꢁ

hiện một liên kꢈt tꢏ A đꢈn B như lꢆ xꢀc nhận cꢃa B bꢍi A. Cꢀc liên

kꢈt cꢂ nhꢎng giꢀ trị khꢀc nhau. Nꢈu A cꢂ nhiều liên kꢈt tꢋi nꢂ vꢆ C

có ít các liên kꢈt tꢋi nꢂ thì một liên kꢈt tꢏ A đꢈn B cꢂ giꢀ trị hơn một

liên kꢈt tꢏ C đꢈn B.

18

Hình 3.1. Mô tả liên kết của các trang Web của thuật toán

PageRank

3.3. QUY TRÌNH PHÂN CỤM VÀ TÌM KIẾM TÀI LIỆU

- Tìm kiꢈm cꢀc trang Web tꢏ cꢀc trang Website phải thỏa mãn

nội dụng truy vấn.

- Trích chọn thông tin tꢏ cꢀc trang Web vꢆ lưu trꢎ nꢂ cꢊng vꢋi

cꢀc URL tương ꢄng.

- Dꢊng thuật toꢀn phân cụm tꢌ động trên cꢀc trang Web, sao

cho cꢀc trang trong cụm tương tꢌ nhau về nội dung trang Web.

Hình 3.2. Quy trình phân cụm tìm kiếm trên Web

3.3.1. Tìm kiếm dữ liệu trên Web

Ta phải tìm tập tꢏ khꢂa đꢁ tìm kiꢈm vꢆ trả về tập gồm toꢆn văn

tꢆi liệu, tiêu đề, mô tả tꢂm tắt, URL, … tương ꢄng vꢋi cꢀc trang Web

đꢂ.