- 1 -
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
TIỂU LUẬN MÔN HỌC
DATA MINING
CHỦ ĐỀ :
Web mining Trong Search Engine
Giảng viên : Trần Đình Quế
Sinh viên : Nguyễn Huy Sơn
HÀ NỘI – 4/2011
I.Giới thiệu
Sự quan trọng của Search Engine
Hãy thử tưởng tượng một cuộc sống hoàn toàn không có niên giám điện thoại
hay một trợ giúp nào khác. Sử dụng điện thoại lúc đó sẽ trở nên rất khó khăn.
Điều này cũng tương tự như dùng Web mà không có công cụ tìm kiếm (search
engine). Với search engine, bạn chỉ cần biết một vài thông tin hay từ khoá là có
thể tìm được nơi cần đến.
Theo một nghiên cứu do công ty Zona Research (Mỹ) tiến hành năm 1999 thì
search engine hiện là phương thức tìm kiếm thông tin trên Web được sử dụng
nhiều nhất, nó chiếm tới 77% tổng thời gian tìm kiếm. Theo kết quả khảo sát
người tiêu dùng của một công ty khác vào năm 1999 thì 88% người dùng trực
tuyến có sử dụng một search engine và 72% có dùng một search engine để tìm
kiếm hàng hoá bán lẻ.
Đối với nhiều người dùng, search engine là yếu tố định hình nên bức tranh về
kho thông tin trên Web. Tuy nhiên, một nghiên cứu gần đây của NEC Research
Institute và Inktomy cho thấy có tới hơn một tỷ trang Web riêng biệt trên Internet
và hầu hết các search engine đã bỏ qua không lập chỉ mục cho 1/4 số trang này.
Mặt khác, khoảng 7-14% những nội dung đã được lập chỉ mục lại không còn tồn
tại trên Net.
Search Engine là gì ?
Search engine phần mềm cung cấp các địa chỉ Web có chứa một hay nhiều
thông tin, từ khoá mà người dùng cần tìm kiếm. Thuật ngữ search engine đôi lúc

kiếm chưa.
Công nghệ Search engine có thế tạo cho người sử dụng Internet một lượng
lớn tri thức mà có thể truy cập trên nhiều đường khác nhau. Hiện nay phần lớn
mọi người dùng Search engine cung cấp khả năng tìm kiếm trên cơ sở dữ liệu
của hàng tỉ trang Web, nơi mà những câu truy vấn được thực hiện ngay tức khắc.
Trọng tâm là quá trình chuyển số lượng lớn (sự duy trì và lập chỉ mục trên cơ sở
dữ liệu lớn của trang Web và quá trình chọn nhanh những trang thoả một vài tiểu
chuẩn) đến đặc trưng ( quá trình nhận dạng trang với đặc trưng lớn của người sử
dụng). Một phương hướng thúc đẩy sự phát triển tự nhiên của người sử dụng
Internet đó là bây giờ họ có thể chọn công cụ tìm kiếm và sẳn sàng trả tiền cho
nhà cung cấp hệ thống và chờ đợi để truy vấn của họ được trả lời tốt hơn. Trong
khung cảnh đó, có vài vấn đề được đề cập sử dụng của khai phá dữ liệu và kỹ
thuật tối ưu hoá, mà thường được gọi là Web mining (khai phá dữ liệu Web). Ở
đây, chúng ta mô tả phương thức cải tiến cho kết quả tìm kiếm chuẩn trong
Search engine, ở tài liệu và trang có giá trị giới hạn của số tiêu đề, và người dùng
có các mô tả hạn chế. Sử dụng phương thức kỹ thuật phân cụm (cluster) để khai
báo, trong tập hợp của trang kết quả từ truy vấn đơn, những tập hợp con đồng
nhất một khía cạnh nào đó với vector nền tảng trong ngữ cảnh hoặc mô tả; khi
chúng ta xây dựng số nhỏ và tiềm năng của tập hợp con tốt của những trang, thì
mỗi đoạn của mỗi phân cụm (cluster) trang với điểm cao hơn. Hoạt động trên tập
hợp con của thuật toán di truyền, chúng ta khai báo một tập hợp con với tất cả
điểm tốt và ở bên trong tính không đồng dạng cao. Mỗi tập hợp con cung cấp cho
người sử dụng một vài trang không giống hệt nhau rằng miêu tả sự đúng của cấu
trúc của tập hợp ban đầu của trang. Bởi vì những trang chúng ta thấy bằng thuật
toán vector có chiều cố định, vai trò ngữ cảnh hoặc mô tả cơ bản vector trung
tâm và cụ thể thuộc cách tiếp cận của phương thức này.
- 3 -
Web Minning là gì ?
Để làm rõ sự mơ hồ về những gì các hình thức của Web mining. Ko-Sa La và
Blockeel đã đề xuất các thành phần của Web mining theo các nhiệm vụ sau đây:

Trích xuất các mẫu từ các siêu liên kết trong trang web: một siêu liên
kết là một thành phần cấu trúc kết nối các trang web đến một vị trí khác
nhau.
Khai thác các tài liệu được cấu trúc: phân tích các cấu trúc cây giống
như các cấu trúc trang để mô tả cách sử dụng tag HTML hay XML.
Dưới đây là mô hình quan hệ giữa chúng
- 4 -
II. Nền tảng (Background)
Với P là tập hợp của những trang Web, với
p P∈
chỉ số trang trong tập
hợp. Bây giờ cho rằng P là kết quả của truy vấn chuẩn đến cơ sở dữ liệu của
trang, và như vậy đại diện tập hợp của trang mà thoả mãn một vài điều kiện biểu
diễn của người sử dụng. Mỗi trang
p P∈
kết hợp với điểm cơ bản trong truy vấn
tạo ra P, mà xác định thứ tự những trang có mặt trình bày trong truy vấn. Vai trò
của thứ tự quyết định đặc trưng của tìm kiếm: Trên thực tế, nếu chiều của P có
liên quan, khả năng có thể xảy ra người sử dụng trang P có thể giảm những vị trí
của p cũng có thể tăng. Với những khả năng như vậy dẫn đến hai hạn chế sau:
Trang năm ở vị trí đầu tiên có khả năng là đồng dạng (hoặc bằng nhau) với mỗi
trang cùng vị trí; những trang mà không có điểm cao nhưng điển hình của một
vài hướng của tập hợp P mà xuất hiện những vị trí rất thấp trong phân cấp, với
khả năng xảy ra không đáng kể khi người sử dụng bắt đầu.
Phương thức này chúng ta cố gắn vượt qua hai hạn chế, trọng tâm của việc
chọn từ ban đầu của tập hợp P nhỏ của tập hợp các trang với điểm cao và tách ra
đầy đủ từ mỗi trang. Với điều kiện cần áp dụng cách tiếp cận có giá trị cộng thêm
thông tin từ người sử dụng, tạo ra một ngữ cảnh tìm kiếm ( tạo ra tiêu đề chung
để tìm kiếm có thể tìm đến, không nhất thiết liên kết với từ khoá tìm kiếm cho
việc tạo ra tập hợp P), và người sử dụng khai báo ( nhận ra sự chủ quan của

hiệu quả được giử lại sử dụng cho sau này. Sự nhất thiết và rõ ràng, mỗi thành
phần của vector là số biến cố một từ đặc biệt; chúng ta có thể xem xét đặc điểm
vừa phải mà nó không đặc biệt liên kết với từ chứa đựng trong trang, thí dụ như
sự có mặt của bức tranh, bảng biểu, tiêu đề và v.v Với những gì đã đề cập trước
đó, vector dựa vào ngữ cảnh cơ bản hoặc khai báo được chọn bởi người sử dụng.
Bạn có thể giả thiết rằng với mỗi ngữ cảnh/ khai báo mà có thể thực hiện trong
Search engine, một danh sách những từ mà có liên quan đến ngữ cảnh/ khai báo
có giá trị, và vector liên quan của trang được lưu lại. Nhiều phương pháp tinh vi
với cách tiếp cận đơn giản có thể và cần được xem xét. Số chiều của vector m
(nghĩa là số của những từ thích đáng liên quan đến ngữ cảnh) không phải giới
hạn về mặt lý thuyết một cách đặc biệt nhỏ, nhưng chúng ta nên tránh suy nghĩ
để mà áp dụng phương thức lên số các trang quan trọng, nó được xem xét một
cách hợp lý
100m ≤
. Chúng ta đề xuất hai phương thức để xác định một danh
sách các từ:
- Những từ được xác định trong một pha cài đặt, khi quản lý Search
engine quyết định các ngữ cảnh / các khai báo được hỗ trợ và từ nào là tiểu biểu
của ngữ cảnh / khai báo đó. Thao tác này được hoàn thành với người sử dụng
thuộc công cụ dành cho môi trường đặc biệt.
- 6 -
- Những từ được xác định bắt đầu từ một tập hợp ban đầu của trang được
sử dụng làm mẫu huấn luyện cho ngữ cảnh / khai báo. Khi khai báo của người
dùng được sử dụng, chúng ta có thể xem xét một mẫu huấn luyện cho một khai
báo của trang mà các trang được duyệt qua bởi người sử dụng mới đây mà khai
báo đến các từ kết hợp với những khai báo phát sinh bởi hành vi của người sử
dụng.
V. Phân cụm trang (Page Clustering)
Nghiên cứu rộng là làm sao để cải thiện những kết quả lấy ra bởi phương
pháp phân cụm. Trong nghiên cứu chiến lược để xây dựng phân cụm của toàn bộ

k n k
−
− =
− −
, trong đó
2
( ) /R SST SSE SST= −
với SST là tổng của khoản cách có thứ tự của mỗi đối
tượng từ trọng tâm đến toàn bộ, và SSE là tổng của khoản cách của đối tượng từ
trọng tâm của nhóm. Từ những thí nghiệm trong thực tế và sử dụng dữ liệu mô
phỏng số giả F chất lượng cụm được đo lường, chúng ta thừa nhận thuật toán k-
mean phân cụm thực hiện tốt trong giới hạn thời gian tính toán – nên định kiểu
trong ứng dụng, nơi số của trang và chiều của vector có thể lớn.
VI. Giải thuật di truyền (Genetic Algorithm)
Giải thuật di truyền thực hiện một cách hiệu quả và thông tin đó được lấy
từ nhiều nhà nghiên cứu khác nhau. Chen (1995) sử dụng giải thuật di truyền để
tối ưu hoá từ khoá để gợi ý cho những tài liệu. Giữa hai nhóm Kraft, Petry,
Buckles, Sadavisan (1997) và Sanchez, Pierre (1994) giới thiệu cách tiếp cận
tăng cừng mô tả câu truy vấn dựa vào giải thuật di truyền. Boughanem,
Chrisment và Tamine (1999) một giải thuật di truyền được triển khai để tìm và
tối ưu tập hợp các tài liệu tốt nhất phù hợp với nhu cầu người sử dụng. Horng và
Yeh (2000) đưa ra phương pháp để rút từ khoá từ tài liệu và gán cho nó trọng số.
Mục tiêu là lựa chọn tập hợp con nhỏ P’ của tập hợp trang P gốc của tổng
các điểm lớn, nhưng sự giống nhau giữa các trang được chọn lọc một cách thận
- 7 -
trọng. Chúng ta chọn tập hợp con bằng cách sử dụng giải thuật di truyền (GA).
Có vài lý do để chúng ta lựa chọn giải thuật này. Thứ nhất sử dụng kỹ thuật
Metaheuristic tốt trong việc tối ưu hoá các vấn đề với hàm đối tượng và những
ràng buộc không có trong biểu thức toán học đơn giản. Thứ hai, chúng ta phải
xác định một giải pháp tốt trong một thời gian tính toán nhỏ, và chiều của vấn đề

khác có tập hợp cao hơn của một trang đại diện bằng một nhiễm sắc thể nào đó.
Chúng ta cho biết với dc là số của trang bao gồm mỗi nhiễm sắc thể trong quần
thể ban đầu và nc là số nhiễm sắc thể. Một quần thể gồm có np=dc*nc trang.
Hàm fitness tính toán cho mỗi nhiễm sắc thể được biểu diễn bằng giá trị
dương cao “tốt” cho nhiễm sắc thể và như vậy hàm được làm cực đại. Nó bao
gồm ba giai đoạn: Thứ nhất là tính tổng các điểm của trang trong nhiễm sắc thể
C, nghĩa là
1
( ) ( )
i
i
p C
t C score p
∈
=
∑
với score(p
i
) là điểm gốc của trang p
i
được mô tả
trước đó. Cần xem xét giới hạn khả năng dương của nhiều trang dương có điểm
cao trong nhiễm sắc thể mà còn trả lại những nhiễm sắc thể của trang có điểm
thấp. Hạn chế thứ hai của hàm fitness đó là cân bằng.
- 8 -
Với ID là số chiều; tỷ lệ
2
/ (| | ) 1t np abs C ID= − +
cấu thành từ 2 số hạn của
hàm fitness. np đạt cực đại khi chiều của C chính xác bằng chiều của ID và

tổng của các khoảng cách giữa hai cặp của trang trong nhiễm sắc thể C và đánh
giá tổng biến thiên rõ ràng của C. Mẫu cuối cùng của hàm fitness của nhiễm sắc
thể C và
1 2 3
( ) . ( ) . ( ) . ( )ff C t C t C t C= α +β + γ
với tham số
α,β, γ
phụ thuộc vào độ lớn
của điểm ban đầu và vector biểu diễn trang. Đặc biệt
α,β, γ
được chọn đóng góp
cân bằng của
1 2 3
( ), ( ), ( )t C t C t C
. Ngoài ra, chúng có thể biểu thị sự thích ứng của
các thuộc tính khác nhau được biểu diễn bằng ba thời thời điểm. Mục tiêu của
GA tìm bằng phương thức di truyền, một nhiễm sắc thể C
*
sao cho:
*
1, ,
( ) max ( )
nc
ff C ff C=
.
VII. Hướng phát triển
Ứng dụng phân tích dữ liệu tinh xảo và kỹ thuật khai phá dữ liệu trong tìm
kiếm của thông tin trên Web là lĩnh vực được quan tâm ngày càng nhiều trong
nghiên cứu và công nghiệp. Là chiến lược quan trọng của công cụ này nó không
được đánh giá thấp và ý nghĩa của thông tin ngày một tăng. Như vậy phương