Sử dụng kỹ thuật so sánh chuỗi kết hợp trên các chuỗi có độ dài chênh lệch

Nội dung text: Sử dụng kỹ thuật so sánh chuỗi kết hợp trên các chuỗi có độ dài chênh lệch

1. Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 65 SỬ DỤNG KỸ THUẬT SO SÁNH CHUỖI KẾT HỢP TRÊN CÁC CHUỖI CÓ ĐỘ DÀI CHÊNH LỆCH 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: 31/07/2017; Ngày nhận lại: 09/10/2017; Ngày duyệt đăng: 05/12/2017) TÓM TẮT Bài báo này giới thiệu một thang đo kết hợp các thuật giải so sánh chuỗi toàn cục và cục bộ để đánh giá sự tương tự giữa các cặp chuỗi ký tự. Qua thực nghiệm, thang đo được chứng minh về hiệu quả khi làm việc trên các chuỗi có độ dài chênh lệch so với các thang đo khác. Thang đo hữu ích trong việc phân cụm người dùng web, nhằm dự đoán và đáp ứng yêu cầu về thông tin của các nhóm người dùng khác nhau trong thời gian thực. Từ khóa: Khai phá dữ liệu web; Phân loại người dùng; So sánh chuỗi; Thương mại điện tử. Using glocal alignment to compare sequences of significantly different lengths ABSTRACT This paper introduces a “glocal” combinatorial algorithm between global and local alignments to evaluate the similarity of symbol sequence pairs. This approach empirically proves its merit compared to competitors working on sequences of significantly different lengths. The measure is also useful for clustering web audiences to predict and meet information needs of various groups of users in real-time. Keywords: E-commerce; Sequence alignment; User segmentation; Web mining. 1. Giới thiệu thức trong bài báo này. Thang đo của chúng Kỹ thuật khai phá dữ liệu từ hành vi tôi đã chứng tỏ ưu thế so với các thang đo người dùng đang nhận được sự quan tâm ngày khác khi làm việc trên dữ liệu gồm các chuỗi càng lớn của các nhà nghiên cứu, nhằm phục có độ dài tương phản, bị nhiễu hoặc không vụ các ứng dụng thương mại điện tử trong cân bằng. việc tìm hiểu nhu cầu người dùng web. Phân 2. Phương pháp nghiên cứu cụm (clustering) là một trong những kỹ thuật Cho tập xác định ∑ gồm các ký tự, chuỗi được chú ý nhất cho mục đích phát hiện các bất kỳ có độ dài k>0 là một bộ (tuple) k được nhóm người dùng web tiềm ẩn có nhu cầu tạo thành bằng các phần tử của ∑. Ví dụ, với tương tự nhau. Sự hiểu biết về nhu cầu này ∑={A,B,C}, một tập S={s1, s2, s3, , sn} với n giúp các ứng dụng thương mại điện tử cải tiến chuỗi xác định được tạo ra từ ∑ có thể gồm s1 cách thức và nội dung cung cấp, để thông tin = AB, s2 = ABC, , sn= = ACB. Trong mô hình đến đúng người có nhu cầu nhằm tối ưu hóa của chúng tôi, các phiên truy cập của người lợi nhuận. dùng có thể được xem như chuỗi các sự kiện Trong bài báo trước (Lưu Vĩnh Trung, truy cập trang web, và tập chuỗi S như trên 2017), chúng tôi đã trình bày cách tiếp cận đại diện cho các phiên truy cập (session). S dựa trên sự kết hợp của hai kỹ thuật so sánh được phân thành các cụm (cluster) sao cho chuỗi toàn cục và cục bộ, mà đại diện là các phiên làm việc trong cùng cụm tương tự Needleman-Wunsh và Smith-Waterman, dưới nhau và khác biệt với các phiên làm việc trong hình thức các điều kiện lọc dữ liệu. Cách tiếp các cụm khác. cận đó được phát triển thành thang đo chính Dựa trên kết quả thực nghiệm về sự kết
2. 66 Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 hợp giữa Needleman-Wunsh (NW) và Smith- thực nghiệm là thuật toán Dynamic Time Waterman (SW) dưới dạng các điều kiện lọc Warping (Petitjean và cộng sự, 2014), được (Lưu Vĩnh Trung, 2017), chúng tôi phát triển sử dụng phổ biến trong việc so sánh các chuỗi một thang đo chính thức S cho độ tương tự sự kiện hoặc thời gian. của 2 chuỗi si và sj như sau: Trong các hình minh họa so sánh 3 cách tiếp cận, chúng tôi gọi Dynamic Time (1) Warping là DTW, thang đo sử dụng tham số p Với NW(si,sj) và SW(si,sj) lần lượt là là Hybrid, và thang đo của chúng tôi là điểm NW và SW của 2 chuỗi si và sj , l là độ Combination. Hình 1 trình bày kết quả của 3 dài chuỗi dài hơn trong 2 chuỗi, thang đo NW cách tiếp cận khi làm việc trên các chuỗi là +1 cho cặp phần tử giống nhau và -1 cho tương tự toàn cục và cục bộ có độ dài chênh cặp phần tử khác nhau. Với SW, thang đo lệch. Tham số p của Hybrid khiến thang đo tương ứng là +2 và -1. này (a) xem nhẹ điểm NW khi cặp chuỗi có Một cách tiếp cận của các tác giả khác, độ dài chênh lệch. Nói cách khác, theo công cũng dựa trên sự kết hợp giữa Needleman- thức (2) thì khi p tiệm cận 0, điểm NW trở Wunsh và Smith-Waterman (Chordia và nên không đáng kể. Kết quả là các chuỗi chỉ Adhiya, 2011; Dimopoulos và cộng sự, 2010), tương tự cục bộ với nhau có thể được xem là thang đo kết hợp sử dụng tham số p, với p = như tương tự, và nằm cùng nhánh theo kết quả |si|/|sj| là tỷ lệ độ dài 2 chuỗi si và sj: trên dendrogram. Combination (b) và DTW (c) cho kết quả tốt tương tự nhau, theo đó các (2) chuỗi có độ dài tương đồng và có sự tương tự Để so sánh hiệu quả trong đánh giá độ toàn cục cũng như cục bộ được nhóm lại cùng tương tự của các chuỗi giữa thang đo của nhánh. Các nhóm này có thể được thu thập dễ chúng tôi và các thang đo khác, ngoài thang dàng nếu cắt dendrogram tương ứng ở mức kề đo trên, một “competitor” nữa được đưa vào với gốc. (a) Hybrid (b) Combination
3. Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 67 (c) DTW Hình 1. Kết quả của Hybrid, Combination và DTW khi làm việc trên các chuỗi tương tự toàn cục và cục bộ có độ dài chênh lệch Với DTW, thuật toán này xem các phần tử nén hoặc giãn. Trong ngữ cảnh khai phá dữ liệu trùng lặp kề nhau trong một chuỗi như một phần người dùng web, cách tiếp cận này không phù tử duy nhất. Hình 2 minh họa cơ chế này của hợp vì nếu người dùng refresh nhiều lần một DTW, cho phép nhận dạng các chuỗi sự kiện trang web, hành vi đó không tương tự với người hoặc thời gian có hình dáng tương tự nhưng bị dùng khác truy cập trang web đó chỉ một lần. Hình 2. Cơ chế hoạt động của DTW đối với các phần tử trùng lặp nằm kề nhau khi so sánh 2 chuỗi. Chuỗi AAAABCD và ABCD được DTW đánh giá là trùng khớp nhau Hình 3 cho thấy với các chuỗi có phần tử biệt. Chỉ có cách tiếp cận của chúng tôi vẫn trùng lặp, DTW không cho ra kết quả tốt như phù hợp để gom nhóm các chuỗi tương tự Hình 1, Hybrid vẫn cho kết quả tương tự nhau, đại diện cho những hành vi tương tự Hình 1 vì đây là các chuỗi có độ dài khác của người dùng web.
4. 68 Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 (a) Hybrid (b) Combination (c) DTW Hình 3. Kết quả của Hybrid, Combination và DTW khi làm việc trên các chuỗi tương tự toàn cục và cục bộ có độ dài chênh lệch 3. Kết quả Nhóm 1: Khoảng 170 chuỗi với chiều dài Để đánh giá khách quan hiệu quả của từ 20-22 ký tự, các chuỗi này tương tự cục bộ cách tiếp cận của chúng tôi so với các với nhau, ví dụ: MNOPDFSEDF4EFSDF3F “competitor”, chúng tôi đã làm thực nghiệm SDSDF, MNOPPDPO4O3W3KER3KO3O22, trên 10 tập dữ liệu tổng hợp, mỗi tập gồm MNOPCSDCASDG632YUEWHBDH, khoảng 520 chuỗi đại diện cho các phiên làm Nhóm 2: Khoảng 170 chuỗi với chiều dài việc của người dùng, được chia làm 3 nhóm từ 3-4 ký tự, các chuỗi này tương tự cục bộ với đặc điểm như sau: với nhau, ví dụ: MNZ, OP56, NPI,
5. Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 69 Nhóm 3: Khoảng 170 chuỗi với chiều dài complete-linkage và average-linkage (PunJ và từ 18-20 ký tự, các chuỗi này chứa các ký tự Stewart, 1983). Kết quả thực nghiệm được mô trùng lặp kề nhau, ví dụ: AAAAAAAAAAM tả tại Bảng 1 cho thấy, giá trị trung bình μ của NBBBBBBBBB, XXXXXXXXXXNOYYY độ tinh khiết (purity) trên 10 tập dữ liệu của YYYYYY, Combination luôn cao hơn và độ lệch chuẩn σ Các chuỗi này được phân cụm bằng 3 của Combination luôn thấp hơn hai cách tiếp cách tiếp cận nêu trên và 3 phương pháp phân cận còn lại. chia cấp bậc phổ biến nhất, là single-linkage, Bảng 1 Giá trị trung bình μ của độ tinh khiết và độ lệch chuẩn σ trên kết quả của 3 cách tiếp cận với 3 phương pháp phân chia cấp bậc trên 10 tập dữ liệu tổng hợp Dữ liệu tổng hợp gốc Hybrid DTW Combination sing. comp. avg. sing. comp. avg. sing. comp. avg. μ 100% 58.5% 100% 90.5% 85.5% 89.7% 100% 98.2% 100% σ ±0% ±8.5% ±0% ±9.7% ±1.4% ±9.8% ±0% ±5.7% ±0% Hình 4, 5, 6 là các dendrogram minh họa nghĩa ở trên. Các cụm trong khung màu đỏ thu kết quả phân cụm trên các chuỗi của dữ liệu tổng được bằng cách cắt dendrogram từ gốc xuống để hợp, tương ứng với các nhóm 1, 2, 3 đã định thu được 3 cụm tương ứng với 3 nhóm. Hình 4. Mô tả kết quả phân cụm sử dụng cách tiếp cận Hybrid trên tập dữ liệu tổng hợp
6. 70 Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 Hình 5. Mô tả kết quả phân cụm sử dụng cách tiếp cận DTW trên tập dữ liệu tổng hợp Hình 6. Minh họa kết quả phân cụm sử dụng cách tiếp cận Combination trên tập dữ liệu tổng hợp Để mô phỏng dữ liệu trong trường hợp bị quả thực nghiệm cho trường hợp này, với nhiễu, khoảng 12 chuỗi với độ dài từ 3-24 được độ tinh khiết và lệch chuẩn của Hybrid và tạo ngẫu nhiên từ ký tự và ký số, ví dụ SDFS9, đặc biệt là DTW luôn thấp và cao hơn cách LLPP873O, 9SD0FSDFSF09SDFSD, và bổ tiếp cận của chúng tôi. Combination đã sung vào dữ liệu tổng hợp gốc để tạo nên gom dữ liệu nhiễu thành cụm riêng biệt dữ liệu tổng hợp nhiễu. Bảng 2 mô tả kết (nhóm 4). Bảng 2 Giá trị trung bình μ của độ tinh khiết và độ lệch chuẩn σ trên kết quả của 3 cách tiếp cận với 3 phương pháp phân chia cấp bậc trên 10 tập dữ liệu nhiễu Dữ liệu tổng hợp nhiễu Hybrid DTW Combination sing. comp. avg. sing. comp. avg. sing. comp. avg. μ 90.4% 84.3% 90% 65.8% 73.1% 86.7% 100% 89.2% 100% σ ±11.6% ±3% ±7.2% ±1% ±9% ±11% ±0% ±6% ±0%
7. Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 71 Tương tự, với tập dữ liệu nhiễu, các cắt dendrogram từ gốc xuống đến khi có 4 dendrogram ở Hình 7, 8, 9 đại diện cho kết cụm tương ứng với 4 nhóm (bao gồm nhiễu), quả phân cụm trên các phần tử tương ứng với chúng tôi thu được các cụm trong khung các nhóm 1, 2, 3 được định nghĩa. Bằng cách màu đỏ. Hình 7. Minh họa kết quả phân cụm sử dụng cách tiếp cận Hybrid trên tập dữ liệu nhiễu Hình 8. Minh họa kết quả phân cụm sử dụng cách tiếp cận DTW trên tập dữ liệu nhiễu
8. 72 Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 Hình 9. Minh họa kết quả phân cụm sử dụng cách tiếp cận Combination trên tập dữ liệu nhiễu Vì các nhóm người dùng web không tương ứng với các nhóm 1,2 và 3. Theo kết tương đương nhau về số lượng, chúng tôi tạo quả được trình bày tại Bảng 3, Combination là ra tập dữ liệu tổng hợp không cân bằng. Theo cách tiếp cận duy nhất trong 3 cách tiếp cận đó, số chuỗi của các nhóm 1, 2 và 3 lần lượt là có thể đạt được độ tinh khiết và lệch chuẩn 320, 170 và 10 với 3 tập dữ liệu đầu. Trong 4 hoàn hảo với phương pháp single-linkage. Với tập dữ liệu kế tiếp, các nhóm 1, 2 và 3 lần lượt các phương pháp phân chia cấp bậc khác, có số chuỗi là 170, 320 và 10. Tương tự, số Combination vẫn đạt kết quả tốt hơn so với 2 chuỗi là 10, 170 và 320 cho 3 tập dữ liệu cuối, cách tiếp cận còn lại. Bảng 3 Giá trị trung bình μ của độ tinh khiết và độ lệch chuẩn σ trên kết quả của 3 cách tiếp cận với 3 phương pháp phân chia cấp bậc trên 10 tập dữ liệu không cân bằng Dữ liệu tổng hợp không cân bằng Hybrid DTW Combination sing. comp. avg. sing. comp. avg. sing. comp. avg. μ 81.6% 73.2% 84.8% 90.9% 91.1% 91.2% 100% 93.7% 91.1% σ ±19% ±18.9% ±24.5% ±16.5% ±12.7% ±12.8% ±0% ±10% ±0% Với tập dữ liệu không cân bằng, ở Hình sau khi được phân cụm. 3 cụm tương ứng với 10, 11, 12 là các dendrogram minh họa cho 3 nhóm trong khung màu đỏ ợđư c thu thập các phần tử tương ứng với các nhóm 1, 2, 3 bằng cách cắt dendrogram từ gốc xuống.
9. Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 73 Hình 10. Minh họa kết quả phân cụm sử dụng cách tiếp cận Hybrid trên tập dữ liệu không cân bằng Hình 11. Minh họa kết quả phân cụm sử dụng cách tiếp cận DTW trên tập dữ liệu không cân bằng Hình 12. Minh họa kết quả phân cụm sử dụng cách tiếp cận Combination trên tập dữ liệu không cân bằng
10. 74 Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 Ngoài dữ liệu tổng hợp được tạo ra, được định nghĩa trước cho các phiên làm việc chúng tôi cũng làm thực nghiệm trên tập dữ như với dữ liệu tổng hợp, với Combination, liệu thật gồm 1500 phiên làm việc, được thu các phiên làm việc với độ dài tương tự nhau, thập từ trang web e-commerce. Vì số trang các trang tương tự nhau với thứ tự gần giống web vượt quá kích thước bảng chữ cái, chúng nhau có xu hướng được phân vào cùng cụm tôi sử dụng số đếm để đại diện cho các trang hơn, so với Hybrid và DTW. Hình 13, 14, 15 web được truy cập trong phiên làm việc, ví dụ minh họa cho những kết quả phân cụm này, 0_146_0_146 tương ứng với phiên làm việc với phương pháp phân chia cấp bậc single- gồm 4 trang web. Mặc dù không có các nhóm linkage. Hình 13. Minh họa kết quả phân cụm sử dụng cách tiếp cận Hybrid trên tập dữ liệu từ trang web e-commerce Hình 14. Minh họa kết quả phân cụm sử dụng cách tiếp cận DTW trên tập dữ liệu từ trang web e-commerce
11. Lưu Vĩnh Trung. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 59(2), 65-75 75 Hình 15. Minh họa kết quả phân cụm sử dụng cách tiếp cận Combination trên tập dữ liệu từ trang web e-commerce 4. Kết luận nhau. Chúng tôi dự định tiếp tục so sánh cách Thang đo giới thiệu trong bài báo này dựa tiếp cận này với PAM/k-medoids, ROCK trên sự kết hợp của kỹ thuật so sánh chuỗi hoặc Ward về hiệu quả phân cụm, cũng toàn cục và cục bộ, qua thực nghiệm đã chứng như thay thế Needleman-Wunsch và Smith- tỏ ưu thế của nó khi so sánh với một số cách Waterman bằng Hamming hoặc Levenshtein tiếp cận khác, đặc biệt với các chuỗi có độ dài để mở rộng phạm vi ứng dụng của thang đo chênh lệch hoặc chứa các phần tử trùng lặp kề nếu có thể Tài liệu tham khảo Chordia, B.S., & Adhiya, K.P. (2011). Grouping web access sequences using sequence alignment method. Indian Journal of Computer Science and Engineering (IJCSE), 2(3), 308-314. Dimopoulos, C., Makris, C., Panagis, Y., Theodoridis, E., & Tsakalidis, A. (2010). A web page usage prediction scheme using sequence indexing and clustering techniques. Data & Knowledge Engineering, 69(4), 371-382. Lưu Vĩnh Trung (2017). Phân loại người dùng web sử dụng kỹ thuật so sánh chuỗi. Tạp chí Khoa học Đại học Mở Thành phố Hồ Chí Minh, 55(4), 12-17. Petitjean, F., Forestier, G., Webb, G., Nicholson, A.E., Chen, Y., Keogh, E. (2014). Dynamic time warping averaging of time series allows faster and more accurate classication. International Conference on Data Mining, IEEE, 470-479. Punj, G., & Stewart, D. W. (1983). Cluster analysis in marketing research: Review and suggestions for application. Journal of marketing research, 134-148.