HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG Phùng Thị Anh MỘT SỐ PHƢƠNG PHÁP PHÂN LỚP DỮ LIỆU
VÀ ỨNG DỤNG PHÂN LỚP DỊCH VỤ WEB
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01

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

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

1

MỞ ĐẦU
Dịch vụ Web là sự đột phá quan trọng trong sự phát triển mạnh mẽ của ngành công
nghiệp Công nghệ thông tin, dịch vụ Web cho phép tương tác tốt như Web nhưng lại không
phụ thuộc vào nền tảng và ngôn ngữ tự nhiên, phù hợp cho việc truy cập từ môi trường không
đồng nhất. Với sự tăng trưởng mạnh mẽ về số lượng của các dịch vụ web trên mạng, việc tìm
kiếm trên khối lượng dữ liệu khổng lồ này ngày càng trở nên phức tạp. Trước đây, việc phân
loại thường được thực hiện thủ công theo cách chỉ định cho một dịch vụ vào một thể loại nào
đó đã được phân loại (hay còn gọi là được gán nhãn) theo các quy tắc đã được đặt ra. Tuy
nhiên, cách này có nhiều bất cập khi khối lượng dịch vụ trở nên khổng lồ, kéo theo các quy tắc
phân loại cũng gia tăng, có nhiều người tham gia duy trì hoặc chia sẻ dịch vụ trong một kho dữ
liệu chung. Vì vậy, việc cần thiết có một cơ chế tự động phân loại các dịch vụ web trở nên quan
trọng. Cơ chế tự động này có thể hỗ trợ các nhà xuất bản dịch vụ web (web services publisher)
trong phân loại các dịch vụ mà mình cung cấp còn người dùng chỉ cần đặt một truy vấn, trình
phân loại tự động sẽ xác định các loại phù hợp nhất. Kết quả là cả nhà cung cấp dịch vụ và
người người tiêu dùng có thể khai thác các dịch vụ web tốt hơn.
Nội dung tập trung vào các vấn đề như sau:
Tìm hiểu các thuật toán về phân lớp dữ liệu trong khai phá dữ liệu.
Nghiên cứu, xây dựng tập dữ liệu mẫu về các dịch vụ web để thử nghiệm các thuật toán
phân lớp.
Thử nghiệm các thuật toán phân lớp trên phần mềm khai phá dữ liệu để từ đó đánh giá, so
sánh các kết quả của các thuật toán phân lớp cho các dịch vụ web.
2

CHƢƠNG 1: CỞ SỞ LÝ THUYẾT VỀ PHÂN LỚP DỮ LIỆU VÀ BÀI

Hồi quy (Regression)
Tổng hợp hóa (Summarization).
1.2. Các thuật toán phân lớp điển hình
1.2.1 Support Vector Machine (SVM)
Support Vector Machine (SVM) lần đầu tiên được đề xuất bởi Vapnik trong những năm
1960 để phân loại dữ liệu và từ đó đã thu hút được sự quan tâm cao trong cộng đồng nghiên
cứu máy học.
4

SVM là một phương pháp có tính tổng quát cao nên có thể được áp dụng cho nhiều loại
bài toán nhận dạng và phân loại
Ý tưởng chính của SVM: Là chuyển tập mẫu từ không gian biểu diễn Rn của chúng sang
một không gian Rd có số chiều lớn hơn. Trong không gian Rd, tìm một siêu phẳng tối ưu để
phân hoạch tập mẫu này dựa trên phân lớp của chúng, cũng có nghĩa là tìm ra miền phân bố
của từng lớp trong không gian Rn để từ đó xác định được phân lớp của 1 mẫu cần nhận dạng.
Ta có thể hiểu, siêu phẳng là một mặt hình học f(x) trong không gian N chiều, với x RN
Các ƣu điểm chính của SVM
– SVM rất hiệu quả để giải quyết bài toán dữ liệu có số chiều lớn (ảnh của dữ liệu biểu diễn
gene,protein, tế bào)
– SVM giải quyết vấn đề overfitting rất tốt (dữ liệu có nhiễu và tách dời nhóm hoặc dữ liệu
huấn luyện quá ít)
– Là phương pháp phân lớp nhanh
– Có hiệu suất tổng hợp tốt và hiệu suất tính toán cao
Các ứng dụng của SVM:
– Nhận dạng: tiếng nói, ảnh, chữ viết tay (hơn mạng nơron)
– Phân loại văn bản, khai mỏ dữ liệu văn bản
– Phân tích dữ liệu theo thời gian
– Phân tích dữ liệu gien, nhận dạng bệnh, công nghệ bào chế thuốc
– Phân tích dữ liệu marketing
– V v

chứa các tập mục, X I. T được gán nhãn với một định danh duy nhất.
Ta nói rằng, một giao dịch T D hỗ trợ một tập X I nếu nó chứa tất cả các mục của X.
Một tập X được gọi là tập mục k phần tử (k-itemset) nếu lực lược của X bằng k (tức là
|X|=k)
Định nghĩa 1: Độ hỗ trợ của X, ký hiệu là support(X), là tỉ lệ phần trăm của các giao
dịch hỗ trợ X trên tổng các giao dịch D, nghĩa là:

Định nghĩa 2: Một luật kết hợp có dạng R:X=>Y, trong đó X,Y là tập các mục, X,Y I
và X Y =
6

– X được gọi là tiên đề
– Y được gọi là hệ quả của luật
Hai thông số quan trọng của luật kết hợp là độ hỗ trợ (support) và độ tin cậy
(confidence).
Định nghĩa 3: Độ hỗ trợ (support) của luật kết hợp X=>Y là tỉ lệ phần trăm giữa số
lượng các giao dịch chứa cả X và Y (X Y) với tổng số các giao dịch có trong cơ sở dữ liệu.
Đơn vị tính %.
Support = Tổng số lượng giao dịch hỗ trợ X Y/Tổng số giao dịch
Định nghĩa 4: Độ tin cậy (confidence) là tỉ lệ phần trăm giữa số lượng các giao dịch
chứa cả X và Y (X Y) với số giao dịch có chứa X. Đơn vị tính %.
Confidence = Tổng số lượng giao dịch hỗ trợ X Y / Tổng số giao dịch hỗ trợ X.
Một số thuật toán khai phá luật kết hợp
– Thuật toán Apriori
– Thuật toán Apriori-TID
– Thuật toán Apriori-Hybrid
– Thuật toán Count Distribution (CD)
– Thuật toán Data Distribution (DD)
– Thuật toán Candidate Distribution
– Thuật toán khai phá luật kết hợp phân tán nhanh(FDM)
Hình 1.4:Chồng giao thức của dịch vụ Web

WEBSERVICES
UDDI (Discovery)
WSDL (Description)
SOAP
(Remote sevice call)
HTTP
(Transport application protocol)
TCP/IP
(Transport protocol)
8

1.3.4 Các thành phần của Dịch vụ Web
XML – eXtensible Markup Language
WSDL – Web Service Description Language
Universal Description, Discovery, and Integration (UDDI)
SOAP – Simple Object Access Protocol
1.4 Kết luận
Chương này đã khái quát được các lý thuyết liên quan đến việc thực hiện đề tài bao gồm
các khái niệm, kỹ thuật về khai phá dữ liệu; Lý thuyết về các thuật toán phân lớp điển hình
được lựa chọn để thực hiện luận văn. Nội dung của chương nhằm mục đích cung cấp một cái
nhìn tổng quan và cơ sở để thực hiện việc giải quyết bài toán áp dụng các thuật toán phân lớp
để phân lớp các dịch vụ Web ở Chương 2 và Chương 3.
9

10

2.1.3 Kiến trúc hệ thống phân lớp dịch vụ Web
Chúng ta cần xây dựng một hệ thống phân lớp dịch vụ web. Mỗi khi một dịch vụ web
mới đưa vào, ta sẽ trích xuất tương ứng với file và tách chúng thành các token, bộ từ khóa
token trong môt tả hoạt động/dịch vụ web, tên của hoạt động và danh sách tham số chứa trong
cả tên biến đầu vào và đầu ra. Sau đó, ánh xạ tất cả chúng thành vector, chỉ phụ thuộc vào thuật
toán khác nhau và sử dụng bộ phân lớp để miêu tả nhóm có thể và lưu trữ kết quả cho việc sử
dụng về sau.

Hình 2.1: Kiến trúc hệ thống phân lớp dịch vụ Web
2.2. Áp dụng các thuật toán phân lớp cho bài toán phân lớp dịch vụ Web.
2.2.1 Phân lớp dịch vụ Web dựa trên SVM
Quá trình phân lớp các dịch vụ Web bằng SVM dựa vào cấu trúc WSDL của các trang
Web bằng việc biểu diễn dưới dạng văn bản sử dụng mô hình không gian vector. SVM xem
mỗi dịch vụ Web là một vector f(d
1
, d
2
, d
3
…,d
n
) được biểu diễn như văn bản. Áp dụng công
thức trong phương trình của siêu phẳng là:
F(x
1
, x
2
, …,x

Trình
phân
lớp

Lớp N
Lớp B
Lớp A
11

Thay thế mỗi văn bản tương ứng với mỗi dịch vụ Web vào phương trình siêu phẳng này:
F(d
1
, d
2
, …,d
n
) = C + w
i
x
i

Với I = 1,…,n.
Nếu f(d) >=0 thì dịch vụ Web thuộc lớp +1.
Nếu f(d) <0 thì dịch vụ Web thuộc lớp -1.
Có thể thấy rằng quá trình áp dụng thuật toán SVM vào bài toán phân lớp các dịch vụ
Web là việc thay thế vector trọng số biểu diễn dịch vụ Web đó vào phương trình siêu phẳng
của SVM, từ đó tì ra được nhãn lớp của các dịch vụ Web chưa gán nhãn.
Như vậy, thực chất của quá trình phân lớp các dịch vụ Web bằng SVM áp dụng với dữ
liệu huấn luyện là các dịch vụ Web còn tập working set hay còn gọi là dữ liệu chưa gán nhãn là
những dịch vụ Web được các dịch vụ Web đã có nhãn trong tập huấn luyện trỏ tới.

tất cả các lớp, khi đó P( = P( ) = … = P( ), và do đó chúng ta chỉ cần tối đa hóa P(X|
) thay vì tối đa hóa cho cả P(X| )P( ). Chú ý rằng lớp các xác suất tiền nghiệm có thể được
thiết lập bởi:

Với các tập dữ liệu cho trước có nhiều thuộc tính, nó sẽ tốn chi phí để tính P(X| ). Để
giảm bớt chi phí tính toán lượng giá P(X| ) P( ), giả thiết về sự độc lập của lớp điều kiện
được tạo ra. Nó giả định rằng giá trị của các thuộc tính điều kiện là độc lập với nhau. Xét về
mặt toán học, điều này có nghĩa là:

Các xác suất ) có thể được dễ dàng thiết lập từ tập
huấn luyện. Nhớ lại rằng, ở đây tham chiếu đến giá trị thuộc tính cho mẫu X.
Nếu là thuộc tính rời rạc, thì P( |C) được ước lượng bởi tần số liên quan của các
mẫu có giá trị cho thuộc tính thứ k trong lớp C.
Nếu là thuộc tính liên tục, thì P( |C) được ước lượng thông qua một hàm mật độ
Gaussian.
13

Chương 3 của luận văn sẽ thử nghiệm hai thuật toán của Bayes là BayesNet và Navie
Bayes để phân lớp các dịch vụ web. Từ đó đưa ra đánh giá, nhận xét chi tiết cho hai thuật toán
này nói riêng và so sánh với các thuật toán khác nói chung.
2.2. 3 Phân lớp dịch vụ Web dựa trên Luật kết hợp
Một cách tiếp cận khác cho bài toán phân lớp dịch vụ web là khai phá dữ liệu và phân
lớp tài liệu WSDL (webservice description language) dựa trên thuật toán luật kết hợp. Ứng
dụng để phân tích mức độ độc lập giữa nội dung WSDL và các mục của dịch vụ web. Một bộ
phân loại học máy được sử dụng để suy diễn một dãy các lớp được lựa chọn thành một bộ tiền
xử lý mô tả dịch vụ web (preprocessed web service description).
Trong phần nghiên cứu này, chúng ta sẽ khai thác sự phụ thuộc giữa các loại dịch vụ
Web và giao diện của nó được mô tả bởi WSDL [11a] cho việc phân lớp dịch vụ web. Luật kết
hợp được sử dụng để xây dựng bộ phân lớp dịch vụ web để tự động phân lớp dịch vụ web. Đây
là xác định các mục của dịch vụ web, cho một tập hợp các loại được xác định trước. Mục tiêu

CHƢƠNG 3: THỬ NGHIỆM, ĐÁNH GIÁ
Chương này của luận văn sẽ mô tả quá trình thiết kế, xây dựng tập dữ liệu mẫu là các
dịch vụ Web với các tham số độc lập được trích xuất từ file WSDL và thực hiện việc thử
nghiệm phân lớp các dịch vụ Web theo 3 phương pháp đã được phân tích tại Chương 2 trên
phần mềm Weka.
3.1. Phát biểu bài toán
Bài toán phân lớp dịch vụ web là bài toán xây dựng một tập dữ liệu huấn luyện của các
dịch vụ web, từ đó áp dụng một trong các thuật toán phân lớp dữ liệu, phân lớp cho các dịch vụ
web mới được đưa vào.
Để thực hiện thử nghiệm và đánh giá các thuật toán phân lớp được mô tả ở chương 2
cho việc phân lớp các dịch vụ web, chúng ta cần bộ dữ liệu đầu vào là các dịch vụ Web. Vì
vậy, yêu cầu trước tiên cần đặt ra là cần xây dựng được tập dữ liệu mẫu (hay còn gọi là tập dữ
liệu huấn luyện). Tập dữ liệu này đảm bảo phải đưa ra được các tham số đặc trưng của dịch vụ
Web đó và đồng nhất cho tất cả các dịch vụ web.
Yêu cầu tiếp theo để có thể thực hiện thử nghiệm, đánh giá là lựa chọn công cụ thử
nghiệm phù hợp, cung cấp đa dạng các công cụ khai phá dữ liệu như cho phép thay đổi dữ liệu,
thay đổi thuật toán, phương pháp đánh giá. Như đã giới thiệu ở các phần trước của luận văn,
công cụ được lựa chọn để thử nghiệm đánh giá ở đây là phần mềm khai phá dữ liệu Weka. Chi
tiết về phần mềm sẽ được giới thiệu ở mục sau.
3.2 Thiết kế và Mô tả dữ liệu
Tập dữ liệu được sử dụng trong ví dụ sẽ tập trung vào các thông số cơ bản trong một file
WSDL của dịch vụ Web. Các dịch vụ Web là các dịch vụ Web được công bố trên các trang:
Xmethods.net, SALCentral.com, service-repository.com.
Mỗi dịch vụ Web được công bố trên các trang này đều có kèm theo một file mô tả
WSDL. Bằng cách phân tích và chiết xuất dữ liệu từ file WSDL này thành các thuộc tính độc
lập, luận văn đã xây dựng thành công tập dữ liệu mẫu.
Các thuộc tính hoặc các biến độc lập được trích xuất ra từ file WSDL bao gồm:
Các thuộc tính hoặc các biến độc lập trong tập dữ liệu này là:

16

@relation Loại_Dữ_Liệu
Khai báo các thuộc tính theo cú pháp
@attribute Tên_Thuộc_Tính Kiểu_dữ_liệu
Phần 2: dữ liệu cho các thuộc tính
Phần này bắt đầu bằng từ khóa @data
17

Mối bộ dữ liệu tương ứng với một dòng,dữ liệu cho từng tham số cách nhau bằng dấu
“,”, nếu là dữ liệu dạng text thì nằm trong bộ dấu ‘’.
3.3 Giới thiệu phần mềm Weka
Như đã mô tả trong Chương 2 là các thuật toán phân lớp áp dụng cho tập dữ liệu mẫu là
các dịch vụ Web sẽ được thử nghiệm bằng phần mềm Weka. Weka là một công cụ phần mềm
viết bằng java phục vụ lĩnh vực học máy và khai phá dữ liệu. Được phát triển bởi các nhà khoa
học thuộc đại học Waikato, Newzeland với phiên bản đầu tiên được phát hành vào năm 1994.
Đến năm 1997 Weka được xây dựng lại bằng java và hoàn thiện 100% Java vào năm 1999.
Đây là một phần mềm mã nguồn mở tích hợp các thuật toán máy học và khai thác dữ
liệu với giao diện trực quan, dễ sử dụng và có thể chạy trên mọi hệ điều hành.
3.4 Thử nghiệm phân loại các dịch vụ Web
3.4.1 Tiền xử lý dữ liệu
- Khởi động Weka và mở chế độ làm việc Explorer
- Tại Tab Preprocess chọn nút Open file => chọn đến file WebServices.arff
3.4.1 Phân lớp các dịch vụ web áp dụng SVM
Phần này sử dụng Weka để phân lớp các dịch vụ web bằng thuật toán SMO – một thuật
toán của SVM.
3.3 Phân lớp các dịch vụ web áp dụng Bayes
Phần này sử dụng Weka để phân lớp các dịch vụ web bằng hai thuật toán BayesNet và
Navie Bayes.
3.4.3 Phân lớp các dịch vụ web áp dụng Luật kết hợp.
Phần này sử dụng Weka để phân lớp các dịch vụ web bằng thuật toán Decision Table–
thuật toán lai tạp của thuật toán Apriori.

lượng, đa dạng hơn về các tham số và trên nhiều loại dữ liệu khác nhau của các Dịch vụ web.