\

Trang 1
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC

PHƯƠNG PHÁP BƯỚC ĐI NGẪU NHIÊN
TRONG GIẢI QUYẾT CÁC BÀI TOÁN TIN
HỌC

\

Trang 2


tính được phát triển dựa trên những thành tựu của khoa học – kỹ thuật để ngày càng thu
nhỏ hơn và tích hợp nhiều hơn những bóng bán dẫn trên cùng một bộ vi xử lý để tăng khả
năng xử lý. Nhiều năm qua, tốc độ phát triển tính toán của máy tính đều tuân theo định
luật Moore với nội dung là sau mỗi 2 năm tốc độ tính toán máy tính lại tăng gấp đôi. Tuy
tốc độ tính toán đã những bước phát triển vượt bậc nhưng những công việc của máy tính
thực hiện về tác vụ chính chỉ ràng buộc trong một số thao tác cơ bản như lưu trữ, tìm
kiếm và cập nhật thông tin. Và để giải quyết một vấn đề nào đó trong cuộc sống, máy
tính vẫn phải dựa trên các phương pháp giải quyết của con người, để nhằm được cung
cấp cho máy tính những phương thức và quá trình giải quyết vấn đề đó.
Quá trình giải quyết các vấn đề trong cuộc sống của con người ít bị thay đổi theo thời
gian. Nó là một sự mở rộng và hoàn thiện các phương pháp nhưng tất cả đều tựu chung
theo một phương pháp tổng quan nhất:
- Quan sát và tập hợp các sự kiện ở trong quá khứ và hiện tại.
- Bổ sung, kết hợp và biến đổi những sự kiện trước đó.
- Kiểm tra và đánh giá những kết quả đạt được.
- Ghi nhận, xử lý các kết quả (kết quả đúng và sai) và đưa ra hướng giải quyết mới.
- Quay lại bước quan sát – tập hợp và lặp lại quá trình giải quyết như vậy.
Quá trình như vậy được lặp lại cho đến khi đạt được kết quả mong muốn. Kết quả
mong muốn ở đây có thể là một kết quả không cần đúng hoàn toàn, chỉ cần kết quả đúng
một phần trong một giới hạn cho phép. Ví dụ các lý thuyết trong vật lý và kinh tế, nó
được dẫn giải và giải thích đúng một số hiện tượng nhưng các lý thuyết đó vẫn chưa thể
được chứng minh đúng hoàn toàn như thuyết tương đối, thuyết thị trường hiệu quả…
Riêng đối tin học, các giải pháp đưa ra cho một vấn đề đôi khi không thể giải quyết để
thỏa mãn cùng lúc tất cả các yêu cầu của vấn đề. Đôi khi, phải sử dụng các phương pháp
gián tiếp với kết quả trả về được chấp nhận theo các điều kiện nào đó. Ví dụ: tìm kiếm
trên Google không dựa trên ngữ nghĩa mà dựa trên tìm kiếm theo từ khóa và đánh giá nội
dung theo các link các trang web bên trong nhưng vẫn cung cấp được các kết quả tìm
kiếm tương đối chính xác với nội dung tìm kiếm của người dùng.
\


một trong những mô hình biểu diễn rất tốt các đặc điểm, mối quan hệ giữa các sự vật,
thực thể khác nhau. Một số mô hình đồ thị tiêu biểu như mạng xã hội, mạng ngữ nghĩa,
mạng đặc điểm nhận dạng khuôn mặt, protein… Dưới đây một số thuật giải trên đồ thị
xuất phát từ phương pháp “bước đi ngẫu nhiên” để giải quyết một số bài toán nổi bật:

\

Trang 5

2.1.1 Thuật giải gom cụm: Markov Cluster Algorithm (MCL) [1]
Bài toán gom cụm dữ liệu là một bài toán thuộc lớp phân lớp không giám sát. Trong
đó, yêu cầu của bài toán là từ tập dữ liệu lớn sẽ được gom cụm các tài liệu trong tập
thành các nhóm tài liệu dựa trên chỉ số có thể so sánh với nhau giữa các tài liệu(độ đồng
dạng, độ khác biệt, khoảng cách Euclid…). Các thuật toán kinh điển và được sử dụng phổ
biến khi gom cụm như thuật giải K-Mean, EM đã đạt nhiều kết quả khả quan… nhưng
phần lớn các thuật toán đều không có sự ổn định khi xuất kết quả, đồng thời hiệu quả của
thuật toán không phụ thuộc hoàn toàn vào số liệu mà phụ thuộc vào thiết kế ban đầu để
chạy thuật toán như phải xác định số lượng nhóm cho trước, thiết kế quy tắc chọn phần tử
trung tâm của nhóm… mà từ đó có những ảnh hưởng rõ rệt đến kết quả của bài toán.
Từ yêu cầu bài toán gom cụm có thể mô hình hóa tập dữ liệu theo mô hình đồ thị như
sau: mỗi đỉnh của đồ thị là một tài liệu và cạnh nối giữa các tài liệu thể hiện một chỉ số so
sánh (ví dụ như độ đồng dạng của tài liệu). Lưu ý: với những cặp tài liệu độ đồng dạng
thấp thì có thể bỏ qua sự kết nối thông qua cạnh giữa 2 tài liệu đó.
Ví dụ: cho 7 tài liệu như hình 1 minh họa. Trong đó, nếu giữa 2 cặp tài liệu bất kỳ
được xem là tương đối giống nhau thì tồn tại một cạnh nối 2 tài liệu đó.

Hình 1: minh họa mô hình đồ thị
Ý tưởng của phương pháp “bước đi ngẫu nhiên” được sử dụng ở đây là nếu chúng ta
bắt đầu xuất phát tại một đỉnh bất kỳ của đồ thị và thực hiện “bước đi ngẫu nhiên” - chọn
ngẫu nhiên tới một đỉnh khác thông qua cạnh liên kết giữa chúng thì dường như chúng ta

trong cùng 1 nhóm) và làm yếu đi các liên kết được xem là yếu (các cạnh kết nối
các nhóm với nhau). Gọi A[i, j] là giá trị phần tử ma trận với n phần tử thì công
thức làm mạnh và yếu các liên kết được tính như sau:

[
,
]
=

[
,
]

∑

[
,
]





\

Trang 7

- Bước 6: Tiến hành chuẩn hóa là thành ma trận xác suất với tổng giá trị trên cột là 1
và giá trị mỗi phần tử có giá trị từ 0 đến 1.
- Bước 7: Sau khi chuẩn hóa nếu ma trận hội tụ, đạt được trạng thái cân bằng (giá trị

⎜
⎛
0.17 0.17 0.17 0.17 0 0 0
0.51 0.51 0.51 0.51 0 0 0
0.17 0.17 0.17 0.17 0 0 0
0.17 0.17 0.17 0.17 0 0 0
0 0 0 0 0.62 0.62 0.62
0 0 0 0 0.19 0.19 0.19
0 0 0 0 0.19 0.19 0.19
⎠
⎟
⎟
⎟
⎞

Sau 8 vòng lặp, ma trận đạt trạng thái hội tụ. Từ đây những dòng ma trận có giá trị
khác 0 sẽ hình thành nên các nhóm dữ liệu. Như hình bên dưới, tồn tại 2 dòng ma trận
(dòng 2 và dòng 5) tạo thành nhóm 1 gồm các đỉnh (1, 2, 3, 4) và nhóm 2 gồm các đỉnh
(5, 6, 7).
⎝
⎜
⎜
⎜
⎛
0 0 0 0 0 0 0
1 1 1 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 0 0 0

Theo thuật giải HITS thì một trang Web có một điểm Hub cao khi trang Web đó chứa
nhiều link liên kết tới các trang Web có điểm Authority cao. Ngược lại, một trang Web
có điểm Authority cao là một trang Web được liên kết (trỏ tới) từ nhiều trang Web có
\

Trang 9

điểm Hub cao. Tùy vào mục đích tìm kiếm mà căn cứ vào điểm Hub hoặc điểm Authority
để xác định nội dung trang Web, như dưới ví dụ mô tả, tính chất mà điểm Hub và điểm
Authority đóng góp cho quá trình đánh giá nội dung trang Web.
Ví dụ đơn giản hơn: như hình minh họa ở trên khi chúng ta cần mua một chiếc xe.
Chúng ta cần tham khảo trước hết từ những người bạn mà đã sử dụng qua nhiều loại xe.
Đồng thời, các loại xe của những người bạn đấy đã sử dụng phải là những loại xe tốt để
chúng ta có cái nhìn toàn diện tương ứng với chất lượng xe mà chúng ta cần tìm. Từ đó,
một người bạn thỏa các tiêu chí như sử dụng nhiều loại xe và chất lượng các dòng xe họ
dùng thuộc dạng tốt thì họ chính là những người bạn đáng cho chúng ta tham khảo khi
mua xe. Và quá trình đánh giá như vậy sẽ được tương tư cho điểm Hub – điểm Hub dành
cho những người ta cần tham khảo mua xe. Còn điểm Authority là điểm dành cho các
loại xe mà được nhiều người dùng, đồng thời những người dùng này cũng đã dùng nhiều
loại xe tốt khác (để có thể so sánh chất lượng mua xe với nhau). Vậy cuối cùng khi mua
xe, chúng ta cần tham khảo từ những người bạn có điểm Hub cao và các hãng xe được
tìm hiểu phải có điểm Authority cao để xác định được loại xe tốt nhất để mua. Như vậy,
cả hai loại điểm Hub và điểm Authority đều hỗ trợ cho việc tìm kiếm thông tin nhưng tùy
vào mục đích mà xác định ưu tiên một trong hai loại điểm Hub hoặc Authority và kết hợp
chúng lại với nhau.
Thuật giải HITS cũng dựa trên phương pháp “bước đi ngẫu nhiên” gần tương tự với
thuật giải gom cụm Markov Cluster, nhưng có một chút khác biệt so với Markov Cluster.
Vì mục đích của bài toán HITS là đánh giá trang Web, đồng thời mô hình đồ thị ở đây là
một mô hình đồ thị có hướng nên thuật giải HITS có những bước tính toán khác với
Markov Cluster. “Bước đi ngẫu nhiên” được thực hiện trong thuật giải HITS như sau:

Authority cho mỗi trang Web. Lưu ý: nếu tính HITS từ đồ thị vô hướng thì kết quả của
điểm Hub và điểm Authority là giống nhau vì khi trong đồ thị vô hướng thì 1 cạnh nối 2
đỉnh được xem như là 2 cạnh có hướng đối nghịch nhau, đỉnh A trỏ tới đỉnh B và ngược
lại.
Ví dụ từ hình 1: điểm Hub và điểm Authority cho 7 đỉnh
Đỉnh 1: Hub: 0.19 Authority: 0.19
Đỉnh 2: Hub: 0.22 Authority: 0.22
Đỉnh 3: Hub: 0.19 Authority: 0.19
Đỉnh 4: Hub: 0.19 Authority: 0.19
Đỉnh 5: Hub: 0.1 Authority: 0.1
Đỉnh 6: Hub: 0.05 Authority: 0.05
Đỉnh 7: Hub: 0.05 Authority: 0.05
Vì đây là một đồ thị vô hướng nên điểm Hub và điểm Authority của mỗi đỉnh là bằng
nhau. Đỉnh 2 có nhiều link liên kết nên có số điểm Hub và Authority cao nhất, còn các
đỉnh 6 và đỉnh 7 có số liên kết thấp nhất nên có số điểm Hub và Authority thấp nhất. \

Trang 11

2.2 Thuật giải tối ưu hóa dựa trên mô phỏng hành vi đàn kiến [3]
Thuật giải tối ưu hóa dựa trên mô phỏng hành vi của đàn kiến trong tự nhiên. Ý tưởng
xuất phát từ một công trình nghiên cứu sinh học vào năm 1989. Khi nhà bác học người
Đan Mạch Deneubourg và các cộng sự công bố kết quả nghiên cứu về thí nghiệm trên
đàn kiến Argentina, gọi là thí nghiệm trên chiếc “Chiếc cầu đôi”. Cụ thể, họ đã đặt một
chiếu cầu đôi gồm hai nhánh (nhánh dài hơn có độ dài bằng hai lần nhánh ngắn hơn) nối
tổ của đàn kiến với nguồn thức ăn, sau đó thả một đàn kiến và bắt đầu quan sát hoạt động
của chúng trong một thời gian đủ lớn. Kết quả ban đầu các con kiến đi theo cả hai nhánh
của chiếc cầu với số lượng gần như ngang nhau, nhưng càng về cuối thời gian quan sát

dữ liệu.
Minh họa cho thuật giải đàn kiến, đó là việc áp dụng thuật giải đàn kiến cho bài toán
kinh điển: bài toán người du lịch. Bài toán người du lịch là bài toán tìm đường đi ngắn
nhất cho người thương nhân hay còn gọi là người chào hàng xuất phát từ một thành phố,
đi qua lần lượt tất cả các thành phố duy nhất một lần và quay về thành phố ban đầu với
chi phí rẻ nhất, được phát biểu vào thế kỷ 17 bởi hai nhà toán học vương quốc Anh là Sir
William Rowan Hamilton và Thomas Penyngton Kirkman. Phát biểu bài toán dưới dạng
đồ thị như sau: Cho đồ thị n đỉnh đầy đủ và có trọng số G = (V-tập đỉnh, E-tập cạnh) có
hướng hoặc vô hướng. Tìm chu trình v
1
 v
2
 …  v
n
 v
1
với v
i
∈
,
v
i
<> v
j
, i, j =
1, …, n.
Phương pháp tìm đường đi mô phỏng hành vi con kiến sẽ được thực hiện như sau:
Các con kiến sẽ tiến hành tìm đường đi từ đỉnh xuất phát qua một loạt các đỉnh và
quay trở về đỉnh ban đầu, tại đỉnh u một con kiến sẽ chọn đỉnh v chưa được đi qua trong
tập láng giềng của u theo xác suất sau:

tương ứng cho mỗi xác suất. Ví dụ: p1 = 30%, p2 = 20%, p3 =50%. Gọi là vector v là
vector biểu diễn vùng giá trị cho 3 xác suất p
1
, p
2
và p
3
thì tương ứng vùng biểu diễn của
v cho p
1
là từ 0 đến 30, vùng biểu diễn của v cho p
2
là từ 31 đến 50 và vùng biểu diễn của
v cho p
3
là từ 51 đến 100. Sau khi biểu diễn vector, sẽ tiến hành chọn lựa đỉnh đi tiếp
bằng cách phát sinh 1 số ngẫu nhiên từ 0 đến 100. Nếu số ngẫu nhiên này rơi vào vùng
nào trên vector thì đỉnh tương ứng trên đó được chọn. Ví dụ: nếu số ngẫu nhiên là 20 rơi
vào vùng biểu diễn của v
1
(từ 0 đến 30) nên v
1
được chọn là đỉnh tiếp theo. Trong thuật
giải đàn kiến thì mỗi lần phát sinh số ngẫu nhiên được hiểu là quá trình mà mỗi con kiến
tiến hành lựa chọn đường đi tiếp theo.
Sau khi và kể cả trong quá trình các con kiến tìm đường đi các vết mùi sẽ được cập
nhật lại, vì chúng bị biến đổi do quá trình bay hơi và do quá trình tích lũy của các con
kiến trên đường đi đó. Có nhiều cách cập nhật mùi nhưng trong phạm vi bài luận chỉ giới
thiệu cách cập nhật mùi đơn giản nhất, vết mùi trên mỗi cạnh (đường đi) được cập nhật
lại theo công thức sau: . Trong đó  ∈[0,1] gọi là tham số bay hơi

thời đại mà kỹ thuật tính toán trên máy tính đang phát triển mạnh mẽ sẽ giúp hạn chế
điẻm yếu này. Như việc sử dụng tính toán song song, thiết kế lại cấu trúc ma trận (trên
vector đặc biệt) đồng thời, đưa việc tính toán lên điện toán đám mây sẽ giúp giải quyết
yếu điểm về tính toán phức tạp của thuật giải Markov Cluster. Thuật giải gom cụm
Markov Cluster được sử dụng cho việc gom cụm tự động các tài liệu, qua đó phân lớp
văn bản tốt hơn. Ngoài ra, Markov Cluster còn được sử dụng gom cụm – nhận dạng các
cấu trúc protein. (gom nhóm các cấu trúc protein gần giống nhau – để qua đó rút trích
được đặc điểm, tính chất nổi bật), sử dụng trong kinh tế khi phân lớp tự động danh sách
khách hàng để giúp đề ra các sản phẩm kinh doanh tốt hơn.
Thuật giải đánh giá liên kết HITS với nội dung đánh giá dựa trên điểm Hub và điểm
Authority được xem là nền tảng trong việc phát triển đánh giá nội dung trang Web trên
các máy tìm kiếm trên Internet như Google, Yahoo, Wolfram Anpha… Không chỉ áp
dụng phân tích trang Web mà thuật giải HITS còn mở rộng áp dụng cho lĩnh vực khác
như viễn thông, kinh tế. Chẳng hạn, áp dụng vào phân tích các cuộc gọi điện thoại hằng
ngày để xác định các đặc điểm, tính chất khách hàng và chất lượng cuộc gọi được đáp
ứng để đưa ra các chiến lược kinh doanh. Cũng như mô tả bảng chất lượng
Thuật toán tối ưu hóa dựa trên mô phỏng đàn kiến (thuật giải đàn kiến) đã giải quyết
nhiều các bài toán một cách tự nhiên hơn. Khác biệt với 2 thuật giải trước, chỉ giải quyết
trong phạm vi bài toán cụ thể. Thuật giải đàn kiến tương tự như thuật giải di truyền được
sử dụng để giải quyết cho nhiều bài toán khác nhau. Thuật giải đàn kiến được áp dụng
vào các bài toán cần tối ưu như tối ưu hàm đơn biến, tối ưu hàm đa biến, sắp xếp, tìm
kiếm đường đi ngắn nhất phù hợp. Sử dụng cho các bài toán mà phương pháp giải trực
tiếp không hiệu quả (hạn chế thời gian tính toán, dữ liệu sử dụng lớn) và kết quả giải
được không cần đúng hoàn toàn mà chỉ cần đúng một cách tương đối không quá sai biệt
với kết quả thực của bài toán. Một số ứng dụng thực tế như quy hoạch đô thị, giao thông,
thiết kế mạng lưới, lịch làm việc cho các tổ chức. 4. Kết luận
\

\

Trang 16

[1] cập nhật
ngày 12/04/2012
[2] cập nhật
ngày 12/04/2012
[3] cập nhật ngày 12/04/2012 Phụ lục
Chương trình minh họa một vài thuật giải áp dụng phương pháp “bước đi ngẫu nhiên”
\