Phân loại người dùng web sử dụng kỹ thuật so sánh chuỗi

Nội dung text: Phân loại người dùng web sử dụng kỹ thuật so sánh chuỗi

1. 12 TẠP CHÍ KHOA HỌC ĐẠI HỌC MỞ TP.HCM – SỐ 55 (4) 2017 PHÂN LOẠI NGƯỜI DÙNG WEB SỬ DỤNG KỸ THUẬT SO SÁNH CHUỖI LƯU VĨNH TRUNG Trường Đại học Mở Thành phố Hồ Chí Minh – trung.lv@ou.edu.vn (Ngày nhận: 17/03/2017; Ngày nhận lại: 11/04/2017; Ngày duyệt đăng: 08/05/2017) TÓM TẮT Ngày nay cùng với sự phát triển của thương mại điện tử, nhu cầu tìm hiểu sở thích của người dùng để tối ưu hóa lợi nhuận ngày càng tăng. Sở thích được thể hiện qua hành vi của người dùng trong quá trình duyệt web hoặc các ứng dụng liên quan thương mại điện tử khác. Bài báo này trình bày cách tiếp cận sử dụng kỹ thuật so sánh chuỗi trên các phiên duyệt web để đánh giá sự tương tự trong hành vi người dùng và phân loại họ. Kết quả phân loại này có thể sử dụng để dự đoán hành vi người dùng web trong thời gian thực, và có những đề xuất duyệt web phù hợp với từng loại người dùng. Từ khóa: Khai phá dữ liệu web; so sánh chuỗi; phân loại người dùng; thương mại điện tử. Web user segmentation using sequence alignment ABSTRACT Nowadays, with the rapid advances in e-commerce, user interest understanding becomes more and more essential in order to benefit the business. Users reveal this kind of interest through their behavior during their sessions in e-commerce applications. In this paper, we present the approach using sequence alignment for web sessions to evaluate the user behavior similarity in order to segment them. The segmentation result is applicable for real-time web prediction and recommendation. Keywords: Web mining; sequence alignment; user segmentation; e-commerce. 1. Giới thiệu báo này, chúng tôi sử dụng chuỗi ký tự như A- Các chiến lược tiếp thị trên Internet dựa B-C-D-E để đại diện cho chuỗi các trang web trên hành vi người dùng đang nhận được sự được thăm viếng trong phiên truy cập. quan tâm ngày càng lớn của các doanh nghiệp Kỹ thuật so sánh chuỗi đã được ứng dụng thương mại điện tử. Hoạt động của các chiến từ rất lâu trong Công nghệ Sinh học và các lược dạng này dựa trên việc thích nghi ứng ngành liên quan, nhằm tìm ra những đoạn dụng thương mại điện tử với hành vi người tương tự nhau giữa các chuỗi RNA, ADN dùng trong thời gian thực, khi họ đang truy cập hoặc protein (Hình 1). Hai hướng tiếp cận ứng dụng. Để đạt được mục đích này, các công chính trong kỹ thuật này là so sánh toàn cục cụ tính toán nhanh sự tương tự giữa các phiên (global alignment) và so sánh cục bộ (local truy cập là thiết yếu, nhằm xác định người alignment) để đánh giá một cách toàn diện sự dùng thuộc nhóm tương ứng nào. Mức độ tương tự giữa các chuỗi. Hai thuật toán tiêu tương tự này được sử dụng để gom nhóm các biểu và được áp dụng rộng rãi, lần lượt đại phiên truy cập, và qua đó phân loại người dùng diện cho so sánh toàn cục và cục bộ là web (Cooley, R. và cộng sự, 1997). Phiên truy Needleman-Wunsh (Needleman, S.B. và cộng cập có thể được xem như chuỗi các sự kiện, sự, 1970) và Smith-Waterman (Smith, T.F., nên để đơn giản hóa phần trình bày trong bài 1981; Zahid, S.K., 2015).
2. KỸ THUẬT – CÔNG NGHỆ 13 Hình 1. So sánh các chuỗi trong Công nghệ Sinh học nhằm phát hiện mức độ tương tự 2. Phương pháp nghiên cứu của các chuỗi, vì vậy thuật toán này rất hiệu Như đã đề cập, so sánh toàn cục và so quả trên các chuỗi có chiều dài tương đương sánh cục bộ đánh giá mức độ tương tự của các nhau (Hình 2). Smith-Waterman (SW), ngược chuỗi theo những cách khác nhau. lại, tập trung vào những vùng tương tự giữa Needleman-Wunsh (NW) có xu hướng tìm hai chuỗi nên thích hợp với các chuỗi có chiều kiếm sự tương tự tổng quát trên suốt chiều dài dài chênh lệch (Hình 3). ABABCDEFGHGH ABABCDEF_GHGH A_ _BC_EFG_ GH _ _ABC_EFGGH_ _ Hình 2. So sánh chuỗi toàn cục Hình 3. So sánh chuỗi cục bộ Trong bài báo này, để đánh giá mức độ thang đo tương ứng là +2 và -1 tương ứng, vì tương tự giữa hai chuỗi cho từng thuật toán, SW tập trung vào những vùng tương tự rời rạc chúng tôi dùng thang đo +1 cho cặp phần tử giữa hai chuỗi. Với thang đo này, sự khác biệt giống nhau và -1 cho cặp phần tử khác nhau trong cách so sánh chuỗi được thể hiện rõ khi so sánh chuỗi sử dụng NW. Với SW, trong các ví dụ sau (Hình 4, 5, 6, 7, 8): ABCDEFGHIJK A Hình 4. So sánh hai chuỗi có độ dài chênh lệch có một phần tử tương tự, kết quả SW = 2 AB ABCD AB ABCE Hình 5. So sánh hai chuỗi trùng lặp, Hình 6. So sánh hai chuỗi có độ dài như nhau kết quả NW = 2 có các phần tử tương tự, kết quả NW = 2
3. 14 TẠP CHÍ KHOA HỌC ĐẠI HỌC MỞ TP.HCM – SỐ 55 (4) 2017 Cặp chuỗi trong hình 4 có độ dài rất sự khác biệt của hai thuật toán trong đánh chênh lệch và chỉ có một phần tử chung. giá độ tương tự của các cặp chuỗi. Một ví dụ Trong khi hai cặp chuỗi trong hình 5 và 6 có khác về sự khác biệt này được trình bày tại độ dài tương đương và có nội dung trùng lặp hình 7 và 8. Hai cặp chuỗi đều có điểm NW hoặc nhiều phần tử tương tự. Tuy nhiên đánh = 0, nhưng điểm SW của cặp chuỗi hình 7 giá về độ tương tự của của SW cho cặp (4) cao hơn cặp chuỗi hình 8 (3) vì độ liên chuỗi hình 4 và của NW cho hai cặp chuỗi tục của các phần tử tương tự trong hình 7 hình 5 và 6 là giống nhau. Điều này cho thấy cao hơn. ABCD ABDC XBCY XBYC Hình 7. So sánh hai chuỗi có độ dài Hình 8. So sánh hai chuỗi có độ dài tương tương đương có các phần tử tương tự đương có các phần tử tương tự theo thứ tự, theo thứ tự, kết quả SW = 4, NW = 0 kết quả SW = 3, NW = 0 Cặp chuỗi để so sánh có độ dài càng khác ABCDEFGHIJKLMNO). Do đó, NW cần biệt, NW càng cho thấy sự không phù hợp của được kết hợp với thuật giải khác tập trung vào thuật giải này trong việc đánh giá độ tương tự. sự tương tự cục bộ để có được kết quả tối ưu Như trình bày tại Bảng 1, NW đánh giá cặp và phù hợp với ngữ cảnh của các phiên truy (ABC, BCD) có độ tương tự thấp hơn (ABC, cập trên web. Bảng 1 Độ tương tự đo bởi NW trên một số cặp chuỗi có độ dài khác biệt nhau ABCDEFGHIJKLMNO ABC BCD ABCDPFQHRJSLTNU AAAAAAAAABCD ABCDEFGHIJKLMNO 3.0 3.0 3.0 -10.2 ABC 3.0 0 3.0 2.99 BCD 3.0 0 3.0 2.99 ABCDPFQHRJSLTNU 3.0 3.0 3.0 -10.2 AAAAAAAAABCD -10.2 2.99 2.99 -10.2 Chúng tôi đề xuất một sự kết hợp giữa NW 2. Ứng dụng SW và SW trong việc đánh giá sự tương tự giữa các 3. Ứng dụng kết hợp NW và SW. cặp chuỗi đại diện cho phiên truy cập web của Độ tinh khiết của cụm cho thấy hiệu quả người dùng. Để chứng minh cho ưu điểm của sự của thuật toán phân cụm. Thuật toán càng kết hợp NW và SW thay vì ứng dụng riêng lẻ, hiệu quả, các phần tử của cụm càng đồng chúng tôi đưa ra kết quả về độ tinh khiết (purity) nhất, độ tinh khiết của cụm càng cao. Hình 9 của cụm (cluster) trong ba trường hợp: minh họa độ tinh khiết của ba cụm, với các 1. Ứng dụng NW phần tử đồng nhất có màu giống nhau.
4. KỸ THUẬT – CÔNG NGHỆ 15 Hình 9. Purity = 5/6 Purity = 4/6 Purity = 3/5 3. Kết quả tương ứng, và trả về log file với các định dạng Như đề xuất trong phần trước, chúng tôi như .csv, .txt Log file được làm sạch thực nghiệm các ứng dụng riêng lẻ và kết hợp (cleaning) để loại trừ dữ liệu bị lỗi/không hợp của NW và SW trên dữ liệu người dùng được lệ trước khi áp dụng các thuật toán clustering trích xuất từ website phân cụm. Log file bao gồm nhiều phiên truy fonderie.uha.fr/. Dịch vụ được triển khai phía cập, mỗi phiên chứa ít nhất một trang web back-end của trang web này cho phép thu thập được viếng thăm, sau đây là ví dụ rút gọn của dữ liệu của các phiên truy cập, như các trang một phiên truy cập được ghi nhận trên log được thăm viếng, thời gian, thời điểm file: Mã phiên truy cập URLs 000001 000001 000001 000001 Để tăng hiệu quả của thuật toán clustering 1_2_3_4. Kết quả độ tinh khiết của cụm, sau và số lượng URL có thể xử lý, các URL sẽ khi ứng dụng riêng lẻ và kết hợp NW và SW được đại diện bằng các chữ số. Ví dụ, phiên trên log file gồm 2000 phiên truy cập, được truy cập 000001 trên bao gồm 4 URL trình bày tại Bảng 2: Bảng 2 Kết quả độ tinh khiết của cụm qua các ứng dụng riêng lẻ và kết hợp NW và SW Điểm NW > ¼ Điểm SW gấp đôi Điểm NW > ¼ độ dài chuỗi độ dài chuỗi dài độ dài chuỗi ngắn dài hơn và điểm SW gấp đôi hơn hơn độ dài chuỗi ngắn hơn Độ tinh khiết 81% 63% 92% của cụm
5. 16 TẠP CHÍ KHOA HỌC ĐẠI HỌC MỞ TP.HCM – SỐ 55 (4) 2017 Hình 10, 11, 12 lần lượt minh họa kết quả truy cập khác. Ngược lại, SW khiến 10_ 1_ phân cụm bằng NW, SW và kết hợp NW và 12_ 13_ 4_ 9_ 14, 9_3_4, 11_11_11, SW trên dữ liệu gồm 32 phiên truy cập đại 10_8_15_10, 10_8_1_9_2_4 là những phiên diện. Sau khi áp dụng NW và SW riêng lẻ và truy cập không có sự tương tự toàn cục so với kết hợp như bộ lọc, số phiên truy cập tương các phiên còn lại, xuất hiện trong các phân ứng trên hình 10, 11, 12 lần lượt là 26, 32 và cụm. Còn sự kết hợp giữa NW và SW tối ưu 23. Việc áp dụng NW khiến các phiên truy hơn trong việc gom nhóm các phiên truy cập, cập tương tự nhau một cách toàn cục, nhưng số phiên ít hơn nhưng chọn lọc được các 10_8_1_ 9_ 2_ 4 hoặc 1_ 2_ 3_ 4_ 5 là ví dụ phiên tương tự nhau về toàn cục cũng như về sự không tương tự cục bộ so với các phiên cục bộ. Hình 10. Kết quả phân cụm bằng hierarchical clustering khi điểm NW > ¼ độ dài chuỗi dài hơn Hình 11. Kết quả phân cụm bằng hierarchical clustering khi điểm SW gấp đôi độ dài chuỗi ngắn hơn
6. KỸ THUẬT – CÔNG NGHỆ 17 Hình 12. Kết quả phân cụm bằng hierarchical clustering khi điểm NW > ¼ độ dài chuỗi dài hơn và điểm SW gấp đôi độ dài chuỗi ngắn hơn. 4. Kết luận và Smith-Waterman, qua thực nghiệm đã Kỹ thuật so sánh chuỗi được sử dụng chứng tỏ sự hiệu quả và thực tế khi làm việc phổ biến Công nghệ Sinh học, cũng được trên dữ liệu các phiên truy cập của người ứng dụng trong việc phân cụm các phiên truy dùng web. cập web để tìm các nhóm người dùng tương Chúng tôi có kế hoạch phát triển một tự nhau (Wang và cộng sự, 2002). Tuy nhiên, thang đo chính thức dựa trên sự kết hợp của vì kỹ thuật so sánh chuỗi vốn không được tạo hai kỹ thuật so sánh chuỗi toàn cục và cục bộ ra để sử dụng trên dữ liệu web, nó cần phải này, để việc phân cụm các phiên truy cập được phát triển tối ưu cho mục tiêu này. web, và qua đó tự động gom nhóm người Cách tiếp cận của chúng tôi dựa trên sự kết dùng, được nhanh chóng và hiệu quả hơn với hợp của hai kỹ thuật so sánh chuỗi toàn cục lượng dữ liệu ngày càng lớn từ các thiết bị sử và cục bộ, mà đại diện là Needleman-Wunsh dụng Internet phong phú hiện nay Tài liệu tham khảo Cooley, R., Mobasher, B., & Srivastava, J. (1997). Grouping web page references into transactions for mining world wide web browsing patterns. IEEE Knowledge and Data Engineering Exchange Workshop Proceedings, 2-9. Needleman, S.B., & Wunsch, C.D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3), 443-453. Smith, T.F., & Waterman, M.S. (1981). Identification of common molecular subsequences. Journal of molecular biology, 147(1), 195-197. Wang, W., & Zaiane, O.R. (2002). Clustering web sessions by sequence alignment. Database and Expert Systems Applications Proceedings, 394-398. Zahid, S. K., Hasan, L., Khan, A. A., & Ullah, S. (2015). A novel structure of the Smith-Waterman Algorithm for efficient sequence alignment. Digital Information, Networking, and Wireless Communications, 6-9.