Tóm tắt luận văn Thạc sĩ: Sánh lược đồ cho khám phá dịch vụ Web

Chia sẻ: Nguyễn Thị Thu Trang | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

66
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn thạc sĩ tập trung vào kỹ thuật sánh lược đồ, nghiên cứu kỹ thuật sánh lược đồ cho khám phá dịch vụ web, tập trung vào vấn đề mô hình hóa các thao tác sánh dịch vụ Web bằng lược đồ cây và các vấn đề liên quan.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt luận văn Thạc sĩ: Sánh lược đồ cho khám phá dịch vụ Web

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG -------------------------------------------------- BÙI VĂN CÔNG SÁNH LƯỢC ĐỒ CHO KHÁM PHÁ DỊCH VỤ WEB 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Ĩ Hà Nội - 2012
Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: PGS.TS TRẦN ĐÌNH QUẾ Phản biện 1: ……………………………………………………. Phản biện 2: ………………………………………………………… Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... 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à các thành phần ứng dụng sử dụng các giao thức mở như HyperText Transfer Protocol (HTTP), Extensible Markup Language (XML) và Simple Object Access Protocol (SOAP) [2]. Chúng được thiết kế để hỗ trợ khả năng tương tác giữa các máy tính với nhau trong mạng. Cho đến nay, nhiều công ty cung cấp dịch vụ Web tới các khách hàng. Ví dụ như dịch vụ web APIs của Google cho phép các nhà phát triển phần mềm truy vấn trực tiếp hàng tỉ trang web từ các chương trình máy tính cá nhân của họ. Nhà phát triển có thể sử dụng ngôn ngữ lập trình mà họ ưa thích ví dụ như Java, Perl, Visual Studio.Net để phát triển các ứng dụng truy cập tới các dịch vụ web của Google. Số lượng các dịch vụ Web đang tăng trưởng với một tốc độ bùng nổ, điều này đặt ra những thách thức lớn về độ chính xác, tính hiệu quả và tự động truy xuất dịch vụ cho người dùng. Khám phá dịch vụ là quá trình đánh giá một truy vấn cho một dịch vụ và trả về một tập hợp các dịch vụ tương thích. Mục đích của khám phá dịch vụ là để tìm dịch vụ Web thích hợp với một tập hợp các yêu cầu của người dùng. Luận văn tập trung vào kỹ thuật sánh lược đồ, nghiên cứu kỹ thuật sánh lược đồ cho khám phá dịch vụ web, tập trung vào vấn đề mô hình hóa các thao tác sánh dịch vụ Web bằng lược đồ cây và các vấn đề liên quan. Qua đó áp dụng kỹ thuật đã nghiên cứu, tiến hành cài đặt, thử nghiệm để đưa ra đánh giá, so sánh từ các kết quả đạt được. Ngoài phần mở đầu, phần kết luận và các phụ lục, nội dung luận văn được trình bày trong ba chương.  Chương 1: Dịch vụ web và khám phá dịch vụ web. Phần này trình bày về lý do sự ra đời của dịch vụ web; một số khái niệm trong dịch vụ web; kiến trúc; cách biểu diễn dịch vụ web; các giai đoạn trong vòng đời của dịch vụ web.
2  Chương 2: Kỹ thuật sánh lược đồ cho khám phá dịch vụ web. Chương này tập trung nghiên cứu kỹ thuật sánh lược đồ cho khám phá dịch vụ web; tập trung vào vấn đề mô hình hóa các thao tác sánh dịch vụ web bằng lược đồ cây và các vấn đề liên quan; các tiêu chí để phân loại kỹ thuật khám phá dịch vụ web; một số thuật toán khám phá.  Chương 3: Thực nghiệm và kết quả. Chương này sẽ mô tả chi tiết về các công cụ, dữ liệu, phương pháp, kỹ thuật lựa chọn thực nghiệm và toàn bộ quá trình tiến hành thực nghiệm. Kết quả thực nghiệm sẽ được phân tích, so sánh và đánh giá.
3 CHƯƠNG 1: DỊCH VỤ WEB VÀ KHÁM PHÁ DỊCH VỤ WEB 1.1 Dịch vụ web Một kiến trúc của dịch vụ Web gồm có 3 chuẩn chính: SOAP (Simple Object Access Protocol), WSDL (Web Service Description Language) và UDDI (Universal Description, Discovery, and Integration). Giao tác UDDI sử dụng SOAP để nói chuyện với UDDI server, sau đó các ứng dụng SOAP yêu cầu một dịch vụ Web. Các thông điệp SOAP được gửi đi chính xác bởi HTTP và TCP/IP. 1.1.1 Các thành phần của dịch vụ web: XML, WSDL, UDDI, SOAP 1.1.1.1 Thành phần XML (eXtensible Markup Language) Là một chuẩn mở do W3C đưa ra cho cách thức mô tả dữ liệu, nó được sử dụng để định nghĩa các thành phần dữ liệu trên trang web và cho những tài liệu B2B. Về hình thức, XML hoàn toàn có cấu trúc thẻ giống như ngôn ngữ HTML nhưng HTML định nghĩa thành phần được hiển thị như thế nào thì XML lại định nghĩa những thành phần đó chứa cái gì. Với XML, các thẻ có thể được lập trình viên tự tạo ra trên mỗi trang web và được chọn là định dạng thông điệp chuẩn bởi tính phổ biến và hiệu quả mã nguồn mở. Mỗi tài liệu XML bao gồm một prolog, một số các phần tử (element) và một epilog (tùy chọn). Prolog bao gồm một khai báo XML và các tham chiếu đến các tài liệu bên ngoài. Các phần tử XML có thể có một số thuộc tính giống như HTML. Các thuộc tính cung cấp thêm thông tin về một phần tử, thông tin này không phải là một phần dữ liệu. Một thuộc tính là một cặp tên – giá trị bên trong thẻ mở của phần tử:
4 1.1.1.2 Thành phần WSDL (Web Service Description Language) WSDL định nghĩa cách mô tả dịch vụ Web theo cú pháp tổng quát của XML, bao gồm các thông tin: + Tên dịch vụ + Giao thức và kiểu mã hóa sẽ được sử dụng khi gọi các hàm của dịch vụ Web + Loại thông tin: thao tác, tham số, những kiểu dữ liệu (có thể là giao diện của dịch vụ Web cộng với tên cho giao diện này). 1.1.1.3 Thành phần UDDI (Universal Description, Discovery, and Integration) Cấu trúc UDDI : Trang trắng - White pages: chứa thông tin liên hệ và các định dạng chính yếu của dịch vụ Web, chẳng hạn tên giao dịch, địa chỉ, thông tin nhận dạng… Những thông tin này cho phép các đối tượng khác xác định được dịch vụ. Trang vàng - Yellow pages: chứa thông tin mô tả dịch vụ Web theo những loại khác nhau. Những thông tin này cho phép các đối tượng thấy được dịch vụ Web theo từng loại với nó. Trang xanh - Green pages: chứa thông tin kỹ thuật mô tả các hành vi và các chức năng của dịch vụ Web. Loại dịch vụ - tModel: chứa các thông tin về loại dịch vụ được sử dụng. 1.1.1.4 Thành phần SOAP (Simple Object Access Protocol) Cấu trúc một thông điệp theo dạng SOAP Thông điệp theo định dạng SOAP là một văn bản XML bình thường bao gồm các phần tử sau: Phần tử gốc - envelop: phần tử bao trùm nội dung thông điệp, khai báo văn bản XML như là một thông điệp SOAP. Phần tử đầu trang – header: chứa các thông tin tiêu đề cho trang, phần tử này không bắt buộc khai báo trong văn bản. Header còn có thể mang những dữ
5 liệu chứng thực, những chứ ký số, thông tin mã hóa hay cài đặt cho các giao dịch khác. Phần tử khai báo nội dung chính trong thông điệp – body: chứa các thông tin yêu cầu và thông tin được phản hồi. Phần tử đưa ra các thông tin về lỗi – fault: cung cấp thông tin lỗi xảy ra trong qúa trình xử lý thông điệp. 1.2 Khám phá dịch vụ web Để có thể thành công với dịch vụ Web cần phải quan tâm đến khá nhiều vấn đề, bao gồm việc triển khai, giám sát và tích hợp hệ thống. Giám sát (monitoring) Xác định đường đi dữ liệu (Data routing) Triển khai (Deployment) Quản lý (Management) Cấu hình và quản lý phiên bản (Configuration and version management) Bảo mật (Security) Các phương pháp khám phá dịch vụ web Việc tìm kiếm các thao tác dịch vụ web tương tự là kết nối lỏng lẻo được liên quan tới ba vấn đề sánh khác: sánh tài liệu văn bản, sánh lược đồ, sánh các thành phần phần mềm. Sánh tài liệu văn bản: Việc sánh và phân loại các tài liệu là một vấn đề lớn trong việc trích rút thông tin. Sánh lược đồ: Cơ sở dữ liệu chung được xem xét đối với vấn đề tự động hóa của việc sánh các lược đồ [17]. Sánh các thành phần phần mềm: Việc sánh các thành phần phần mềm được xem như là việc quan trọng đối với việc tái sử dụng phần mềm [9]. 1.3 Kết luận chương Dịch vụ Web hiện tại đang được tích hợp với nhiều hệ thống ứng dụng trong tất cả các lĩnh vực bởi khả năng phát triển và giảm độ phức tạp của hệ
6 thống, đặc biệt là đối với các dịch vụ B2B. Với dịch vụ Web, các doanh nghiệp, khách hàng và cả đối tác kinh doanh có thể dễ dàng hoạt động và gắn kết với nhau. Việc xây dựng một dịch vụ Web cần phải quan tâm đến nhiều yếu tố: kiến trúc, chức năng và các tiến trình nghiệp vụ của hệ thống, ngôn ngữ sử dụng… Do đó, với một dịch vụ Web, việc giao tiếp và truyền nhận dữ liệu trở nên dễ dàng và hiệu quả hơn, đồng thời đem lại chi phí thấp hơn và tăng cường những khả năng giao tiếp thời gian thực, kết nối với mọi người trên khắp thế giới. Bản chất của nền tảng công nghệ này là kiến trúc hướng dịch vụ và sự phát triển của dịch vụ Web có tương lai rất khả quan.
7 CHƯƠNG 2: KỸ THUẬT SÁNH LƯỢC ĐỒ CHO KHÁM PHÁ DỊCH VỤ WEB 2.1 Khảo sát đặc trưng của các dịch vụ web Có 4 giai đoạn chính để xây dựng một dịch vụ Web là xây dựng, triển khai, tiến hành và quản lý. Giai đoạn xây dựng: bao gồm phát triển và chạy thử ứng dụng dịch vụ Web, xây dựng các chức năng và định nghĩa dịch vụ. Giai đoạn triển khai: công bố định nghĩa dịch vụ, xây dựng WSDL và triển khai mã thực thi của dịch vụ Web. Giai đoạn tiến hành: tìm kiếm và gọi thực thi dịch vụ Web bởi những người dùng muốn sử dụng dịch vụ. Quản lý: quản lý và quản trị dịch vụ, duy trì sự ổn định của dịch vụ, cập nhật thông tin mới, sửa lỗi khi nó xảy ra. Qui trình xây dựng một dịch vụ Web bao gồm các bước sau: a. Định nghĩa và xây dựng các chức năng, các dịch vụ mà dịch vụ sẽ cung cấp (sử dụng ngôn ngữ Java chẳng hạn). b. Tạo WSDL cho dịch vụ c. Xây dựng SOAP server d. Đăng ký WSDL với UDDI registry để cho phép các client có thể tìm thấy và truy xuất. e. Client nhận file WSDL và từ đó xây dựng SOAP client để có thể kết nối với SOAP server f. Xây dựng ứng dụng phía client (như sử dụng Java) và sau đó gọi thực hiện dịch vụ thông qua việc kết nối tới SOAP server. Lựa chọn một ngôn ngữ, xây dựng các tiến trình nghiệp vụ, bắt đầu tạo nên một dịch vụ Web và cung cấp dịch vụ trên Internet.
8 2.2 Kỹ thuật sánh lược đồ Các phương thức sánh lược đồ đã được đề xuất ở [20]. Phương thức đầu tiên là sự nỗ lực để xác định sự tương tự ngữ nghĩa giữa các yếu tố của hai lược đồ. Bởi vậy công việc khảo sát cần bắt đầu với các kỹ thuật tương tự ngữ nghĩa mà nó đã được sử dụng để sánh giữa hai lược đồ. 2.2.1 Định nghĩa kỹ thuật sánh lược đồ Kỹ thuật sánh lược đồ có thể được hình thức hóa như sau: “Cho hai lược đồ, S1 và S2, tìm kiếm các thành phần tốt nhất giữa lược đồ S1 và lược đồ S2. Việc khám phá tất cả các thông tin sẵn có trong các lược đồ, các nguồn thể hiện dữ liệu và các nguồn từ vựng”. 2.2.2 Biểu đồ truyền thống Sánh lược đồ truyền thống được xây dựng dựa trên ý tưởng mà có hai lược đồ cần phải sánh với nhau. Khi số lượng lớn hơn 2 thì việc sánh được thực hiện trong mỗi cặp với nhau. Vấn đề chính trong sánh lược đồ truyền thống cho phép độ tương tự tương ứng giữa các thành phần trong hai lược đồ input Định nghĩa 1: Một ánh xạ là một tập của các ánh xạ thành phần, mỗi trong số chúng chỉ định các thành phần cụ thể của bất kỳ lược đồ input tương ứng. Công thức xây dựng như sau: cho hai lược đồ S1 và S2 một ánh xạ được viết như sau M T  M 1 , M 2 ,..., M k  , trong đó Mi đại diện cho một ánh xạ như một biến nhị phân. Ví dụ: Gi1  Gi2 , sao cho Gi1  S1 , Gi2  S 2 và Gi j  1 . 2.2.3 Biểu đồ Holistic Việc sánh lược đồ là việc khám phá ngữ nghĩa tương ứng giữa các thuộc tính trong các lược đồ khác nhau dựa trên nền tảng của việc tìm kiếm và trao đổi dữ liệu thông qua các nguồn thông tin. Cách tiếp cận Holistic tạo ra một lược đồ trong thực tế. Việc xây dựng này dựa trên “nội dung ngang hàng với nhau” giữa các lược đồ. Dựa trên nội dung thông tin, việc sánh Holistic sẽ có nhiều lợi ích chẳng hạn như độ chính
9 xác sẽ tỷ lệ với số nguồn thông tin đầu vào. Như ví dụ trong cách tiếp cận MGS và DCM, cả hai đều là phương pháp thống kê mà lợi ích thu được từ các quan sát với cách tiếp cận Holistic việc sánh lược đồ đại diện cho hai phương pháp. 2.2.4 Kiến trúc hệ thống sánh Do việc phổ biến rộng rãi của việc sánh lược đồ đưa đến sự hình dung giải pháp chung, phù hợp đối với các ngôn ngữ lược đồ khác nhau và các miền ứng dụng chẳng hạn như một giải pháp có tiềm năng cao được phát triển, do đó việc trích rút các yêu cầu để phát triển một vài giải pháp đặc biệt để đạt được mục tiêu này cần một sự linh hoạt vào tùy chỉnh trong kiến trúc. Trong đó có thể dễ dàng hơn trong việc mở rộng để hỗ trợ ngôn ngữ lược đồ mới, hoặc miền ứng dụng. 2.2.5 Phân loại các cách tiếp cận sánh Cách tiếp cận sánh được chia làm bốn giai đoạn sánh:cây với cây (giữa các tập hợp của các nút automic của hai lược đồ cây), các bộ phận với các bộ phận, giữa tập hợp của các nút trên các bộ phận của hai nút automic, nút tới nút giữa tập hợp của các từ trong các nhãn của hai nút giữa các từ với các từ (giữa các từ kép của hai từ). Bao gồm các giải thuật sánh sau: o Giải thuật sánh với trọng số lớn nhất o Giải thuật sánh với trọng số cực đại có thứ tự o Giải thuật sánh lược đồ tổng thể 2.3 Kỹ thuật sánh lược đồ cho khám phá dịch vụ web 2.3.1 Giới thiệu về tìm kiếm dịch vụ web Việc tìm kiếm các thao tác dịch vụ web tương tự là kết nối lỏng lẻo được liên quan tới ba vấn đề sánh sau: sánh tài liệu văn bản, sánh lược đồ, sánh các thành phần phần mềm o Sánh tài liệu văn bản: việc sánh và phân loại các tài liệu là một vấn đề lớn trong việc trích rút thông tin.
10 o Sánh lược đồ: Là cơ sở dữ liệu chung được xem xét đối với vấn đề tự động hóa của việc sánh các lược đồ [12,13], thông qua đó nó xác định ngữ nghĩa của các lược đồ và đề xuất các thao tác sánh dựa trên chúng. o Sánh các thành phần phần mềm: việc sánh các thành phần phần mềm được xem như là việc quan trọng đối với việc tái sử dụng phần mềm [9]. 2.3.2 Thao tác sánh dịch vụ web 2.3.2.1 Mô hình hóa bằng lược đồ cây Dựa trên hai định nghĩa: Định nghĩa 1: một dịch vụ Web là bộ ba ws = (TpSet, MsgSet, OpSet), trong đó TpSet là một tập các kiểu dữ liệu; MsgSet là một tập các bản tin biến đổi thành kiểu dữ liệu định nghĩa trong TpSet; OpSet = {opI(inputi,outputi) | i = 1,2,…,n} là một tập các thao tác, trong đó inputi và outputi là các tham số (thông điệp) cho việc trao đổi dữ liệu giữa các thao tác dịch vụ Web. Định nghĩa 2: Mỗi thao tác dịch vụ Web là một hàm MIMO (multi-input- multi-output – nhiều dữ liệu vào và nhiều dữ liệu ra) có dạng f : s1s2 ,..., si  t1 , t2 ,..., t j trong đó si và t j là kiểu dữ liệu tương ứng với đặc tả trong lược đồ XML. Gọi f là một phụ thuộc và si / t j là một thuộc tính phụ thuộc. 2.3.2.2 Hiệu chỉnh khoảng cách cây Bao gồm các thao tác hiệu chỉnh cơ bản như sau: - Thay đổi: Để thay đổi nhãn của một nút thành nút khác - Xóa: Để xóa một nút (tất cả các nút con của nút được xóa b trở thành các nút con của nút cha a) - Chèn: Để chèn một nút ( Một chuỗi tuần tự liên tiếp giữa các nút con, anh, chị, em của nút a trở thành nút con của nút b) Một số ràng buộc  để nó là một khoảng cách metric đó là: (i) (a b)  0; (aa) = 0 (ii) (a b)= (ba); và
11 (iii) (a c) ≤ (ab) + (bc). i S Việc mở rộng  đối với chuỗi S như sau  ( S )   i 1  ( Si ) . Công thức khoảng cách giữa T1 và T2 được xác định như sau:  (T1 , T2 )  min  ( S ) | S là một chuỗi thao tác hiệu chỉnh T1 thành T2  . Việc định nghĩa  tạo ra  cũng là một khoảng cách metric. Ánh xạ Cho T1 và T2 là hai cây với N1 và N2 là các nút tương ứng, việc đánh thứ tự đối với mỗi cây T[20] có nghĩa rằng nút thứ i của cây T trong thứ tự được đưa ra. Các thao tác hiệu chỉnh đưa ra một ánh xạ là một đồ thị đặc biệt của những gì mà các thao tác hiệu chỉnh được áp dụng đối với mỗi nút trong hai cây. Việc định nghĩa một bộ (M, T1 , T2 ) là một ánh xạ từ T1 đến T2 trong đó M là bất kỳ một tập hợp nào đó của một cặp các số nguyên (i,j) thỏa mãn: (1)1≤ i ≤ N1, 1≤ j ≤ N2; (2)Đối với một cặp bất kỳ (i1, j1) và (i2, j2) trong M. Nếu: (a) i1 = i2 nếu và chỉ nếu j1=j2 (b) T1 i1  là cây bên trái của cây T1 i2  nếu và chỉ nếu T2  j1  là cây bên trái của cây T2  j2  (thứ tự các nút anh, chị, em được bảo toàn ). (c) T1 i1  là một cây cha của cây T1 i2  nếu và chỉ nếu cây T2 [j1] là một cây cha cây T2 [j2] (tính chất tổ tiên được bảo toàn). Việc sử dụng M thay vì tập (M, T1 , T2 ) nếu không có sự nhầm lẫn gì thì ta sẽ sử dụng M thay cho bộ đó. Cho M là một ánh xạ từ T1 T2 cho I và J là các tập của các nút trong cây T1 và T2 tương ứng và nó không thuộc bất kỳ đường thẳng nào trong M. Từ đó, có thể định nghĩa hàm chi phí M như sau:  (M)    (T[i] T [j])   (T [i] )   (T [j]). (2.1) (i , j )M 1 2 iI 1 jJ 2
12 2.3.2.3 Mô hình chi phí cho lược đồ cây Định nghĩa như sau: weight  n / W T1 ,T2  , if  = insert  n   weight  n / W T1 ,T2  , if  = delete  n  cost      (2.2)   wd  node1, node2  , if  relabels    sd  node , node  node to node  1 2 1 2 Trong đó  bao gồm một thao tác sửa đổi cây, weight(n) chỉ là trọng số của node n, wd(node1, node2) và sd(node1, node2) cho biết sự chênh lệch của trọng số và ngữ nghĩa giữa node1 và node2.  và  là trọng số của wd và sd, thỏa mãn     1 . W(T1,T2) được định nghĩa như sau: W(T1,T2) = weight(T1) + weight(T2) trong đó weight(Ti) là tổng trọng số của tất cả các node cây Ti(i=1,2), wd(node1,node2) được định nghĩa như sau: weight(node1 ) - weight(node 2 ) wd  node1 , node2   (2.3) W(T1 ,T2 ) Trong đó và node2 T2 2.3.2.4 Chuyển đổi lược đồ cây XML Định nghĩa 4: Tên tên node của một node thường là một chuỗi các từ móc xích với nhau, với chữ cái đầu tiên của mỗi từ là chữ in hoa (ví dụ, Việt Nam). Một tập các từ đó được coi là một nhóm từ. Sử dụng  (n) để biểu diễn một nhóm từ của node n. Định nghĩa 5: Hai nhóm từ  (n1 ) và  (n2 ) được coi là giống nhau chỉ khi chúng có cùng các từ. Hai node được coi là khác nhau nếu chúng có nhóm từ khác nhau. Nhóm từ phản ánh ngữ nghĩa của mỗi một node. Định nghĩa 6: Coi cấp độ (n) là cấp của node n trong cây lược đồ T. Trọng số của node n được định nghĩa với hàm trọng số: Trọng số (n) = 2độ sâu cây lược đồ (T) – mức (n)với mọi nT
13 Trọng số của tất cả các node rơi vào khoảng [2,2độ sâu cây lược đồ (T)]. Mỗi trọng số phản ánh tầm quan trọng của một node trong cây lược đồ T. Các thao tác hiệu chỉnh, bao gồm các thao tác sau: - Split (phân chia): Luật này áp dụng cho các dãy node. - merge (kết hợp): Luật này áp dụng cho các node liên kết. Sau quá trình kết hợp, mỗi node liên kết được thay thế bởi tất cả các node tùy chọn của nó, ví dụ được thay thế bởi tất cả node con của nó. - delete (xóa): luật này được áp dụng cho các node đa dạng. 2.3.2.5 Xác định tính tương tự giữa các thao tác dịch vụ web Việc xác định tính tương tự giữa các thao tác dịch vụ Web thực chất là việc mô tả cấu trúc của các dịch vụ Web thông qua việc đi xác định giải quyết vấn đề tìm kiếm: Cấu trúc của các dịch vụ Web: Đối với mỗi dịch vụ web có một file WSDL được liên kết để mô tả chức năng và giao diện của nó. Một dịch vụ web được công bố bởi việc đăng ký file WSDL của nó và một mô tả trong UDDI. 2.3.3 Giải thuật phân cụm các thao tác dịch vụ Web Kỹ thuật sánh lược đồ được phân cụm - Một kỹ thuật nhằm nâng cao hiệu năng cho việc sánh lược đồ bằng cách sử dụng giải thuật phân cụm. Giải thuật phân cụm chia các lược đồ thành các cụm. Việc sánh lược đồ được phân cụm được thực hiện bằng cách thêm một bước của mỗi bước phân cụm trong hệ thống sánh lược đồ. Theo nguyên tắc hiệu năng của bất kỳ hệ thống tính toán nào có thể được nâng cao theo hai cách. Trong thời gian chạy hệ thống tính toán với số lượng lớn các phép tính toán và hiệu năng của hệ thống này có thể được cải thiện bằng cách: Tiền tính toán, trong trường hợp này các giai đoạn của quá trình tính toán được thực hiện trước đó. Các kết quả được lưu trữ và được tái sử dụng trong thời gian chạy.
14 Việc tỉa của các phép tính toán trong trường hợp này trong thời gian chạy các kỹ thuật khác nhau được sử dụng để tái sử dụng nhằm tối ưu số lượng các phép toán được thực hiện Hai thuộc tính quan trọng của việc nâng cao hiệu năng của hệ thống đó là Ánh xạ - bảo toàn hoặc không ánh xạ - không bảo toàn, và tương tự - bảo toàn hoặc không tương tự - bảo toàn. Định nghĩa 1: Hệ thống sánh lược đồ S2 là một ánh xạ - tiền xử lý nhằm nâng cao hiệu năng cho hệ thống S1 nếu với mọi vấn đề sánh lược đồ P, Cả S1 và S2 tạo ra các tập ánh xạ lược đồ A1=A2. Định nghĩa 2: Hệ thống sánh lược đồ S2 là một ánh xạ - bảo toàn nhằm nâng cao cho hiệu năng cho hệ thống S1 nếu với mọi vấn đề sánh lược đồ P, và T    A1  A2 cho với mọi ánh xạ lược đồ cả hai hệ thống S1 và S2 tính toán  S1 T ,    S2  T ,   . cùng các giá trị của hàm mục tiêu, tức là Cải thiện hiệu năng dựa trên tiền tính toán bao gồm các kỹ thuật: Kỹ thuật gán nhãn các nút; Lập chỉ mục; Chuỗi so sánh với q-gram; Thuật toán Heuristic. 2.3.3.2 Chọn các thuật toán phân cụm Tổng quan về các thuật toán phân cụm Phân cụm là sự sắp xếp không có giám sát của các yếu tố vào các nhóm của các yếu tố. Các yếu tố trong cùng một cụm chia sẻ một số thuộc tính chung trong khi các thành phần từ các cụm khác nhau không. Trong phân cụm đối sánh lược đồ, thuộc tính chung được chia sẻ bởi các thành phần trong một cụm là tiềm năng của các thành phần để cung cấp giá trị ánh xạ lược đồ. Tất cả các thuật toán phân cụm được chia thành hai nhóm: • Thuật toán phân cấp • Thuật toán phân vùng. Giải thuật phân cấp
15 Một khoảng cách (tương tự) ngưỡng trước tiên phải được lựa chọn. Ngưỡng này là các khoảng cách tối đa cho phép giữa các yếu tố trong phân cụm. Đối với một ngưỡng khoảng cách nhỏ mọi phần tử thuộc về một cụm khác nhau. Tăng khoảng cách ngưỡng một số yếu tố sẽ thuộc về cùng một cụm. Thuật toán phân vùng Không giống như các thuật toán phân cấp, các thuật toán phân vùng, chỉ tạo ra một tập hợp các cụm. Một tập hợp các điểm cần phải được nhóm lại. Trọng tâm được sử dụng là các điểm xung quanh các cụm được hình thành. Cụm được hình thành bằng cách chỉ định tất cả các điểm đến trọng tâm gần nhất. So với các thuật toán phân cấp, thuật toán phân vùng là hiệu quả hơn khi chúng tạo ra các cụm trong một lần chạy trên các thiết lập của các yếu tố. Tuy nhiên, vấn đề là những thuật toán cần phải biết trước số cụm, và để ước tính một cách chính xác nơi để hình thành các cụm. 2.4 Kết luận chương Trong chương này đã mô tả một giải pháp để xác định ngữ nghĩa dựa trên giá trị tối ưu của việc sánh lược đồ XML bằng cách sử dụng các mô hình toán học. Giải pháp này xác định giá trị tối ưu của việc sánh giữa hai lược đồ XML với giả định rằng vấn đề sánh cây với cây có thể là vấn đề tối ưu toàn cục được chia nhỏ thành các vấn đề đơn giản hơn như sánh bộ phận với bộ phận, nút với nút và từ với từ.
16 CHƯƠNG 3: THỰC NGHIỆM VÀ KẾT QUẢ 3.1. Nền tảng phân cụm Trong phần này trình bày ba pha chính trong quá trình phân cụm bao gồm: tiền xử lý, tính toán độ tương tự, và phân cụm. - Tiền xử lý: Pha này xem xét sự biểu diễn không đồng nhất của các lược đồ XML như một chuỗi tuần tự. Bao gồm hai bước phân tích cú pháp và xây dựng chuỗi priifer. - Tính toán độ tương tự: Pha này xem xét và tính toán độ tương tự giữa mỗi cặp lược đồ XML theo một cách có thứ tự để xây dựng nên ma trận độ tương tự mà sau đó ma trận này được sử dụng bởi giải thuật phân cụm. Để thực hiện điều này cần sử dụng hai bộ sánh: bộ sánh ngôn ngữ và bộ sánh cấu trúc. Bộ sánh ngôn ngữ: Bước này xác định các giá trị khởi tạo độ tương tự giữa các nút của các lược đồ cây, dựa trên thuộc tính ngữ nghĩa của các nút, trong thử nghiệm, sử dụng cả thuộc tính tên và thuộc tính kiểu dữ liệu. Để xác định độ tương tự giữa hai thẻ, sim(t1, t2), ta sử dụng độ tương tự của hai chuỗi được tính bởi công thức sau: max  t1 , t 2   editDistance  t1 , t 2  simedit (t1 , t 2 )= (3.1) max  t1 , t 2  Trong đó editDistance  t1 , t 2  là số lượng nhỏ nhất cần thiết của các thao tác chèn và xóa để chuyển đổi một chuỗi thành một chuỗi khác. 2  tri  t1   tri  t2  simtri  t1 , t2   . (3.2) tri  t1   tri  t2  Trong đó tri  t1  là một tập các trigram trong t1 . Bộ sánh cấu trúc: Bộ sánh ngôn ngữ chỉ xem xét thông tin các nhãn và bỏ quả thông tin cấu trúc. Điều này có thể chỉ định việc sánh bội trong đó các cấu trúc khác nhau được gán cùng một nhãn.
17 - Phân cụm: Giải thuật này được thực hiện trên phần mềm gCluto, nó cho phép thực hiện phân cụm các lược đồ XML. Trước tiên, giải thuật tính toán độ tương tự để đạt được ma trận độ tương tự và ma trận này như là input cho gCluto, sau đó, giải thuật phân cụm phân cấp được lựa chọn và các tham số được điều chỉnh. 3.2 Kết quả thử nghiệm Tập dữ liệu: Trong thử nghiệm sử dụng 2 tập dữ liệu khác nhau với các đặc điểm được mô tả trong bảng 3.1. Các tập dữ liệu này được thu thập từ các nguồn. http://uisacad2.uis.edu/dstar/data/clusteringdata.html Bảng 3.1: Bộ tóm tắt dữ liệu sử dụng để đánh giá các chức năng phân cụm theo các tiêu chí khác nhau. STT Tên tập dữ liệu Kích cỡ dữ liệu 1 cacmcisi 4658 2 classic 7089 Các tham số được sử dụng trong phần thực nghiệm: bao gồm phương pháp agglomerative (agglo) và hai tham số I1 và UPGMA agglo Phương pháp này mong muốn đạt được k-phân cụm được tính toán bằng cách sử dụng biểu đồ agglomerative với mục tiêu là đạt được giá trị tối ưu địa phương cực tiểu hoặc cực đại với hàm điều kiện phân cụm được lựa chọn bằng cách sử dụng tham số -crfun. Phương pháp này đạt được bằng cách dừng quá trình tích tụ khi số cụm còn lại là k. - Công cụ thực nghiệm: Công cụ dùng làm thực nghiệm trong luận văn là gCULUTO (Graphical CLustering Toolkit - http://www.cs.umn.edu/~cluto/gcluto.). Đây là một bộ công cụ khai phá dữ liệu khá phổ biến được phát triển bởi Matt Rasmussen, Mark Newman, George Karypis của đại học Minnesota. Phần mềm cho phép phân cụm dữ liệu, trực quan hóa dữ liệu. Phần mềm gCluto cho phép lựa chọn các tham số khi phân cụm nhằm đạt được kết quả tối ưu cho từng tiêu chí cần đạt được của người
18 dùng và phù hợp với yêu cầu và dữ liệu của bài toán. Với yêu cầu dữ liệu đầu vào có định dạng tập tin như sau:  matrix file (*.mat) - chứa một ma trận dày đặc, ma trận thưa, hoặc đồ thị tương tự biểu diễn cho các dữ liệu được phân cụm.  row lables (*.rlabel) - chứa các nhãn đối với các hàng của ma trận dữ liệu.  column labels (*.clabel) - chứa các nhãn đối với các cột của ma trận dữ liệu.  class labels (*.rclass) – chứa các nhãn lớp đối với các hàng của ma trận dữ liệu. Chất lượng trong các cụm được đánh giá bằng cách tính toán giá trị trung bình của độ tương tự giữa các cụm và bên trong mỗi cụm theo công thức k  n i  IntraSim  Ci  IntraSim = i=1 . (3.3) n Chỉ số này đánh giá chất lượng tổng thể của cây phân cấp bằng cách chỉ sử dụng một tập con nhỏ của các nút của nó. Nó được tính toán theo công thức như sau cho Sr là số nút có kích cỡ là nr entropy của nút này dược xác định bằng công thức: 1 q nri nri E  Sr     log n , (3.4) log q i 1 nr r Trong đó q là số lượng các lớp trong tập dữ liệu và nri là số lượng các tài liệu của lớp thứ i mà được chỉ định tới nút thứ r. Mà entropy của toàn bộ cây được xác định bởi công thức sau: t 1 E T    E  S r  , (3.6) r 1 t Trong đó t là số nút của cây T. Chỉ số entropy thấp nhất là giá trị tốt nhất. Trước tiên, hai tập dữ liệu đưa vào thử nghiệm là các ma trận độ tương tự được mô tả theo định dạng trình bày ở phần trên.