FGenHUSM: Một thuật toán hiệu quả khai thác các chuỗi sinh phổ biến lợi ích cao

danh DOI: 10.32913/mic-ict-research-vn.v2019.n2.872 Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: PGS.TS. Lê Hoàng Sơn Tóm tắt: Khai thác các chuỗi phổ biến và các chuỗi lợi ích cao có mức độ quan trọng khác nhau trong các ứng dụng thực tế. Gần đây, các nghiên cứu tập trung giải quyết bài toán tổng quát hơn, là khai thác tập FHUS chuỗi phổ biến lợi ích cao. Tuy nhiên, thời gian và bộ nhớ dùng để khai thác FHUS vẫn còn quá lớn. Bài báo đề xuất khái niệm tập FGHUS các chuỗi sinh phổ biến lợi ích cao, là một biểu diễn súc tích của FHUS, và một thuật toán mới hiệu quả để khai thác nó. Dựa vào hai chặn trên của độ đo lợi ích, hai chiến lược tỉa theo chiều rộng và sâu được thiết kế để loại bỏ nhanh các chuỗi ít phổ biến hoặc lợi ích thấp. Sử dụng một chặn dưới mới của lợi ích, một chiến lược tỉa địa phương mới được đề xuất để loại bỏ sớm các chuỗi không là chuỗi sinh phổ biến lợi ích cao. Dựa vào các chiến lược này, một thuật toán mới 퐹퐺푒푛퐻푈푆푀 được thiết kế để khai thác FGHUS mà tính hiệu quả của nó được thể hiện qua các thử nghiệm trên các cơ sở dữ liệu lớn. Từ khóa: Chuỗi lợi ích cao, khai thác chuỗi sinh phổ biến lợi ích cao, chặn trên và chặn dưới của độ đo lợi ích. Title: FGenHUSM: An Efficient Algorithm For Mining Frequent Generator High Utility Sequences Abstract: Mining the set of all frequent high utility sequences (FHUS) in quantitative sequential databases (QSDBs) plays an important role in many real-life applications. However, for huge QSDBs and low minimum support and utility thresholds, algorithms for discovering FHUS often exhibit poor performance in terms of runtime and memory consumption due to the enormous cardinality of the FHUS set. To address this issue, this paper introduces a novel set of all frequent generator high utility sequences (FGHUS). This set is a concise representation of FHUS having a cardinality that is often much less than that of FHUS. Thus, it is more convenient for users to analyze the information provided by the FGHUS set. This paper proposes a novel algorithm named 퐹퐺푒푛퐻푈푆푀 to efficiently mine FGHUS. The algorithm adopts the depth and width pruning strategies to quickly eliminate infrequent or low utility sequences. In addition, it also uses a novel local pruning strategy to prune non-frequent generator high utility sequences early, which is based on a new lower bound on the utility measure. Experimental results on large QSDBs show that the proposed algorithm is efficient in terms of runtime for mining FGHUS, and that the pruning strategies can greatly reduce the search space. Keywords: High utility sequence, frequent generator high utility sequence, upper and lower bounds on utility measure. I. GIỚI THIỆU Khi khai thác tập các chuỗi phổ biến (FSM: Frequent Sequence Mining) trên các cơ sở dữ liệu chuỗi tuần tự (SDB: Sequential Datadase), ta có thể đánh mất nhiều chuỗi lợi ích cao (HU: High Utility) quan trọng trong nhiều ứng dụng thực tế khi chúng ít phổ biến. Chẳng hạn, lợi ích của các mặt hàng bán được là thông tin rất hữu ích khi ra các quyết định trong kinh doanh. Vì vậy, bài toán khai thác các chuỗi HU (HUSM: High Utility Sequence Mining) trên các SDB lượng hóa (QSDB: Quantitative SDB) ra đời sau đó như một nhu cầu bức thiết. HUSM tổng quát hơn FSM và có nhiều ứng dụng như phân tích hành vi duyệt web [1], dữ liệu thương mại di động [2], hiệu chỉnh gen [3], v.v. Ta xét một ứng dụng điển hình của HUSM là phân tích dữ liệu mua hàng. Xét cơ sở dữ liệu chuỗi biểu diễn các đơn mua hàng của khách hàng trong một cửa hàng bán lẻ. Khi đó một chuỗi chứa các mặt hàng được mua bởi một khách hàng ở các thời điểm khác nhau. Chi tiết hơn, nó là một danh sách có thứ tự của các tập mặt hàng, mỗi tập mặt hàng chứa các mặt hàng được mua cùng nhau. Lấy ví dụ, ta có chuỗi 〈{kem đánh răng, bàn chải đánh răng}, {bánh Kinh đô, phô mai}, {nhang}〉. Chuỗi mặt hàng có thể được mua bởi một phụ nữ. Người 57 Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông này mua kem đánh răng và bàn chải đánh răng cùng nhau, sau đó mua bánh Kinh đô với phô mai, cuối cùng mua nhang. Mỗi mặt hàng có một giá bán ra. Khi đó, ta có thể xác định được giá trị của một tập các mặt hàng được mua cùng nhau cũng như giá trị của một danh sách con các tập mặt hàng trong chuỗi mua hàng của một khách hàng nào đó. Khi khai thác trên một tập rất lớn các đơn mua hàng, ta có thể biết được các thông tin như: (i) các mặt hàng nào thường được mua cùng nhau, (ii) lợi ích đem lại của một chuỗi các tập mặt hàng nào đó, v.v. Các thông tin này rất có ích cho việc ra các quyết định kinh doanh của cửa hàng. Cho Ψ′ là một QSDB chứa các chuỗi đầu vào, trong mỗi chuỗi có các sự kiện, trong mỗi sự kiện có các thuộc tính, mỗi thuộc tính gắn với một số lượng và một giá trị lợi ích. Do mỗi chuỗi 훼 có thể xuất hiện ở các vị trí khác nhau (với các lợi ích khác nhau) trong Ψ′, nên lợi ích của 훼 trong Ψ′ có thể được tính dưới dạng tổng [4], giá trị lớn nhất 푢max (훼) [5, 6] hoặc giá trị nhỏ nhất 푢min (훼) [7, 8] (theo nghĩa an toàn và ít rủi ro cho việc phát triển các chiến lược kinh doanh hay ra quyết định). Khi đó, lợi ích của 훼 là tổng lợi ích trên tất cả các chuỗi Ψ′ chứa 훼. Nếu lợi ích của 훼 lớn hơn hoặc bằng một ngưỡng lợi ích tối thiểu 푚푢, nó được gọi là chuỗi HU, ngược lại 훼 được gọi là chuỗi lợi ích thấp (LU: Low Utility). Mục đích của HUSM là khai thác tập chuỗi lợi ích cao (HUS) chứa các chuỗi HU trên một QSDB. Thuận lợi chính khi giải FSM là tính ‘a priori’, còn gọi là tính đơn điệu giảm (anti-monotonic) hay DCP (Downward- Closure Property), của độ đo hỗ trợ: Mọi chuỗi cha của một chuỗi ít phổ biến (LF: Low Frequent) cũng LF [5, 9]. Đặc tính này cho phép rút gọn đáng kể không gian tìm kiếm khi tiến hành khai thác các chuỗi lớn dần trên cây tiền tố. Đáng tiếc là trong HUSM, độ đo lợi ích không có tính DCP. Để khắc phục, các chặn trên (UB: Upper Bound) lợi ích được thiết kế để thu hẹp phạm vi tìm kiếm. Chặn trên SWU [5] (thỏa DCP nhưng giá trị lớn) và các chặn trên khác chặt hơn (có giá trị nhỏ và gần với lợi ích hơn) lần lượt được thiết kế và sử dụng (mặc dù chỉ thỏa mãn các tính chất tựa DCP). Với 푢max (훼), có thể kể ra SPU và SRU (2013), PEU và RSU (2016), gần đây là MEU [6] và SEU [10]. Với 푢min (훼), các tác giả trong [7] đã đề xuất hai chặn trên, RBU và LRU, thiết kế hai chiến lược tỉa theo chiều sâu (DPS: Depth Pruning Strategy) và rộng (WPS: Width Pruning Strategy), và tích hợp chúng vào thuật toán EHUSM để khai thác hiệu quả HUS. Mặc dù EHUSM có thể khai thác nhanh HUS, lực lượng tập kết quả thường rất lớn, việc quản lý và phân tích chúng gây khó khăn đối với người sử dụng. Một tiếp cận thường được dùng trong FSM là khai thác các biểu diễn súc tích của chúng, chẳng hạn như các chuỗi tối đại, đóng và sinh [11, 12]. Chú ý rằng, bằng việc tích hợp FSM và HUSM, ta xét bài toán tổng quát hơn, là FHUSM: Khai thác tập FHUS các chuỗi phổ biến lợi ích cao (FHU: Frequent High Utility), đối với độ đo lợi ích 푢min. Theo cách tiếp cận trên, nhóm tác giả trong [13] đã đề xuất các thuật toán hiệu quả nhằm khai thác hai biểu diễn súc tích của FHUS, bao gồm các chuỗi phổ biến tối đại lợi ích cao (FMaxHU) và tập FCHUS các chuỗi phổ biến đóng lợi ích cao (FCHU). Tuy nhiên, chiều dài các chuỗi FMaxHU và FCHU thường khá lớn. Vì vậy, bài báo đề xuất một biểu diễn súc tích khác FGHUS của FHUS. Trước đây, đã xuất hiện nhiều công trình nhằm khai thác các tập (tập thuộc tính) sinh phổ biến có/không có lợi ích cao [14–16]. Các chuỗi (danh sách có thứ tự các tập thuộc tính) đóng/tối đại/sinh phổ biến cũng đã là đối tượng của nhiều nghiên cứu gần đây [12, 17, 18]. Tập chứa các chuỗi sinh phổ biến lợi ích cao (FGHUS) là mở rộng tự nhiên của chuỗi sinh phổ biến truyền thống. Một chuỗi FHU được gọi là chuỗi sinh phổ biến lợi ích cao (FGHU) nếu không tồn tại chuỗi con FHU nào có cùng độ hỗ trợ. Vì các chuỗi FGHU có chiều dài thường bé hơn nhiều so với các chuỗi FMaxHU và FCHU, nên chúng có các ưu điểm sau. Thứ nhất, ta có thể xem nó như một biểu diễn nén của FHUS. Điều này cũng rất phù hợp với nguyên lý chiều dài mô tả bé nhất (MDL: Minimum Description Length) [19]. Thứ hai, nó cho độ chính xác cao trong các nhiệm vụ chọn mô hình (so với FHUS hay tập FCHUS). Ngoài ra, khai thác các mẫu sinh (với chiều dài tối thiểu) còn là một bước quan trọng trong việc tìm các luật tuần tự quan trọng, chẳng hạn, các luật với ít giả thiết (vế trái) nhưng dẫn ra nhiều kết luận (vế phải), hoặc các luật không dư thừa [20]. Khi đó, các mẫu sinh chính là vế trái, vế phải có thể là các mẫu đóng hoặc không. Do đó, các mẫu sinh trong FGHUS thường được ưa thích hơn đối với người dùng khi cần phân tích tập kết quả, vì số lượng và chiều dài của chúng khá bé so với FHUS. Tập FHUS thường được sử dụng khi lực lượng của chúng khá bé, chẳng hạn khi ngưỡng hỗ trợ (푚푠) và ngưỡng lợi ích tối thiểu (푚푢) khá cao. Ngược lại, khi các ngưỡng này khá thấp và đặc biệt trên các tập dữ liệu lớn, để vượt qua khó khăn trong việc sử dụng cũng như phân tích tập kết quả FHUS với kích thước quá lớn, tập FGHUS sẽ là một lựa chọn phù hợp hơn với người dùng. Mục tiêu của bài báo này là khai thác tập FGHUS. Để khai thác hiệu quả nó, do FGHUS ⊆ FHUS, nên một chuỗi LU hoặc LF sẽ không là FGHU. Do đó, tính chất DCP của độ hỗ trợ và hai chiến lược WPS và DPS dựa vào RBU và LRU [7, 8] có thể được sử dụng để tỉa hiệu quả các chuỗi LF hoặc LU không những từ FHUS mà cả FGHUS. Tuy nhiên, vì FGHUS không là tập con của tập tất cả các chuỗi sinh phổ biến (FGS), nên ta không thể áp dụng trực tiếp các điều kiện tỉa 3E trong [12] để loại bỏ các chuỗi không là chuỗi sinh lợi ích cao (GHU). 58 Tập 2019, Số 2, Tháng 12 Bài báo có một số đóng góp sau đây: (i) đề xuất chặn dưới SF của 푢min; (ii) dựa vào điều kiện tỉa sớm tổng quát 퐺퐸푃 [13] và SF, chiến lược tỉa địa phương (LPG) được thiết kế để loại bỏ sớm các ứng viên (và các mở rộng của chúng) không là GHU; (iii) tích hợp ba chiến lược DPS, WPS và LPG vào thuật toán 퐹퐺푒푛퐻푈푆푀 để khai thác các chuỗi sinh phổ biến lợi ích cao (FGHU); (iv) các thử nghiệm trên hai cơ sở dữ liệu lớn, thực tế và tổng hợp, đã chỉ ra tính hiệu quả của 퐹퐺푒푛퐻푈푆푀 (so với thuật toán cơ sở không áp dụng các chiến lược tỉa) về mặt thời gian chạy và lực lượng của FGHUS thường rất bé so với FHUS. Đây là thuật toán đầu tiên khai thác biểu diễn súc tích FGHUS của FHUS với độ đo lợi ích 푢min. Phần còn lại của bài báo được tổ chức như sau. Phần II trình bày các khái niệm và kết quả cơ bản. Phần xây dựng chiến lược tỉa địa phương LPG. Phần IV đưa ra thuật toán 퐹퐺푒푛퐻푈푆푀 và các kết quả thử nghiệm. Phần V đưa ra các kết luận của bài báo. II. CÁC KHÁI NIỆM VÀ KẾT QUẢ CƠ BẢN 1. Định nghĩa bài toán Mục này giới thiệu vài khái niệm cơ sở liên quan đến bài toán HUSM với 푢min trong [7]. Định nghĩa 1 ([7]): Gọi A def= {푎1, 푎2, . . . , 푎푀 } là tập các thuộc tính phân biệt. Mỗi thuộc tính 푎 gắn liền với một số dương P(푎) thể hiện giá trị lợi ích đơn vị của nó. Khi đó, ta có véctơ P(퐴) def= 〈P(푎1), P(푎2), . . . , P(푎푀 )〉. Một thuộc tính số lượng/định lượng (푞-thuộc tính) là một cặp (푎, 푞), với 푎 ∈ A và 푞 ∈ 푅+ là một số lượng dương. Tập con 퐴 của A, 퐴 ⊆ A, được gọi là một sự kiện. Không mất tổng quát, giả sử rằng các thuộc tính trong một sự kiện được sắp tăng theo thứ tự từ điển ≺. Một sự kiện số lượng (푞-sự kiện) ứng với 퐴 được định nghĩa là 퐴′ def= {(푎푖 , 푞푖) | 푎푖 ∈ 퐴, 푞푖 ∈ 푅+}. 퐴 được gọi là sự kiện chiếu của 퐴′, ký hiệu là 퐴 = proj(퐴′). Danh sách các 푞-sự kiện 〈 퐴′푘 , 푘 = 1, 2, . . . , 푝 〉 ký hiệu là 훼′ = 퐴′1 → 퐴′2 · · · → 퐴′푝 , được gọi là một 푞-chuỗi. Chuỗi chiếu 훼 của 푞-chuỗi 훼′ được định nghĩa là 훼 = proj(훼′) def= proj(퐴′1) → proj(퐴′2) → · · · → proj(퐴′푝). Để thuận tiện, ta ký hiệu 훼′[푘] def= 퐴′푘 và 훼[푘] def = proj(퐴′푘 ). Một 푞-chuỗi là rỗng () nếu tất cả các sự kiện của nó là rỗng. Một cơ sở dữ liệu chuỗi lượng hóa (QSDB) D ′ chứa hữu hạn các 푞-chuỗi đầu vào, D ′ = {Ψ′푖 , 푖 = 1, 2, . . . , 푁} và 푃(퐴). Mỗi 푞-chuỗi Ψ′푖 gắn với một định danh (SID) 푖. Cơ sở dữ liệu chuỗi (không lượng hóa SDB) D ứng với D ′ được định nghĩa là D = proj(D ′) def= {proj(Ψ′푖), 푖 = 1, 2, . . . , 푁} . Kích thước của 푞-chuỗi 훼′, ký hiệu là size (훼′), là số các 푞-sự kiện (푝) của nó. Từ đây về sau, ta xét hai 푞-chuỗi bất kỳ 훼′ = 퐴′1 → 퐴′2 → · · · → 퐴′푝 và 훽 = 퐵′1 → 퐵′2 → · · · → 퐵′푞 cùng hai chuỗi tương ứng 훼 = 퐴1 → 퐴2 → · · · → 퐴푝 và 훽 = 퐵1 → 퐵2 → · · · → 퐵푞 . Định nghĩa 2 ([7]): Xét hai 푞-sự kiện 퐴′ và 퐵′ sau: 퐴′ = { 푎푖1 , 푞푖1 ), (푎푖2 , 푞푖2 ), . . . , (푎푖푚 , 푞푖푚 ) } , 퐵′ = {(푎 푗1 , 푞 푗1 ), (푎 푗2 ), 푞 푗2 ), . . . , (푎 푗푛 , 푞 푗푛 )} , với 푚 ≤ 푛. 퐴′ được gọi là chứa trong 퐵′, ký hiệu là 퐴′ v 퐵′, nếu tồn tại các số tự nhiên 1 ≤ 푘1 < · · · < 푘푚 ≤ 푛 sao cho 푎푖푙 = 푎 푗푘푙 và 푞푖푙 = 푞 푗푘푙 , với mọi 푙 = 1, 2, . . . , 푚. Ngoài ra, ta nói 훼′ chứa trong 훽′, ký hiệu là 훼′ v 훽′, nếu 푝 ≤ 푞 và tồn tại 푝 số nguyên dương, 1 ≤ 푗1 < · · · < 푗푝 ≤ 푞 sao cho 퐴′푘 v 퐵′푗푘 , với mọi 푘 = 1, 2, . . . , 푝. Đồng thời, 훼′ @ 훽′ tương đương với ((훼′ @ 훽′) ∧ (훼′ ≠ 훽′)). Tương tự, ta cũng dùng ký hiệu v để định nghĩa quan hệ chứa trong trên tập tất cả các chuỗi. Ta nói 훼 v 훽 hoặc 훽 w 훼 (훽 được gọi là chuỗi cha của 훼) nếu tồn tại 푝 số nguyên dương, 1 ≤ 푗1 < · · · < 푗푝 ≤ 푞 sao cho 퐴푘 ⊆ 퐵 푗푘 , với mọi 푘 = 1, 2, . . . , 푝. Đồng thời, 훼 @ 훽 tương đương với ((훼 v 훽) ∧ (훼 ≠ 훽)). Ta nói 훽′ chứa 훼, ký hiệu là 훼 v 훽′ (hay 훽′ w 훼, 훽′ được gọi là 푞-chuỗi cha của 훼) nếu proj(훽′) w 훼. Gọi 휌(훼) def= {Ψ′ ∈ D ′ | Ψ′ w 훼} là tập tất cả các 푞-chuỗi đầu vào chứa 훼. Độ hỗ trợ của 훼 được định nghĩa là số các 푞-chuỗi đầu vào chứa 훼, supp(훼) def= |휌(훼) |. Định nghĩa 3 ([7]): Các lợi ích của 푞-thuộc tính (푎, 푞), 푞-sự kiện 퐴′ = (푎푖1 , 푞푖1 ), (푎푖2 , 푞푖2 ), . . . , (푎푖푚 , 푞푖푚 ), 푞-chuỗi 훼′ và QSDB D ′ lần lượt được định nghĩa là 푢((푎, 푞)) def= 푃(푎) ∗ 푞, 푢(퐴′) def= 푚∑ 푗=1 푢((푎푖 푗 , 푞푖 푗 )), 푢(훼′) def= 푝∑ 푖=1 푢(퐴′푖), 푢(D ′) def= ∑ Ψ′∈D′ 푢(Ψ′). Để tránh tính toán lặp lại lợi ích 푢 của mỗi 푞-thuộc tính (푎, 푞) trong các 푞-chuỗi Ψ′ của D ′, ta tính chúng một lần và thay 푞 bởi 푢((푎, 푞)) = P(푎) ∗푞 trong cơ sở dữ liệu. Biểu diễn tương đương này của QSDB D ′ được gọi là QSDB tích hợp của D ′, cũng được ký hiệu vắn tắt là D ′. Từ đây về sau ta chỉ xét các QSDB tích hợp. 59 Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông Bảng I D ′ −MỘT QSDB MINH HỌA SID Chuỗi 1 Ψ′1 = (푎, 9) → (푐, 2) (푒, 20) → (푐, 1) (푔, 50) → (푐, 8) (푑, 16) → (푐, 8) (푑, 16) (푒, 35) (푔, 60) → (푎, 3) (푐, 5) (푒, 2) 2 Ψ′2 = (푐, 9) ( 푓 , 28) → (푎, 15) (푐, 10) → (푑, 16) (푔, 40) (푎, 15) (푒, 20) → (푐, 6) (푑, 24) (푒, 25) 3 Ψ′3 = (푔, 20) → (푒, 40) ( 푓 , 12) → (푏, 45) (푐, 1) → (푑, 56) 4 Ψ′4 = (푒, 40) → (푐, 2) ( 푓 , 20) → (푐, 3) Xét QSDB minh họa trong Bảng I, sẽ được dùng cho các ví dụ trong suốt bài báo. Chuỗi 훼 = 푒 → 푐푒 chứa trong Ψ′1, 훼 v Ψ′1, vì nó xuất hiện trong Ψ′푖 . Lần xuất hiện đầu tiên của 훼 trong Ψ′1 là 푞-chuỗi con 훼 ′ = (푒, 20) → (푐, 8) (푒, 35) của Ψ′1. Vậy proj(훼′) = 훼 và 푢(훼′) = 20+8+35 = 63. Ngoài ra, do 훼 v Ψ′2, nên 휌(훼) = {Ψ′1,Ψ′2} và supp(훼) = 2. SDB D ứng với D ′ là D = {Ψ1 = 푎 → 푐푒 → 푐푔 → 푐푑푒푔 → 푎푐푒, Ψ2 = 푐 푓 → 푎푐 → 푑푔 → 푎푒 → 푐푑푒, Ψ3 = 푔 → 푒 푓 → 푏푐 → 푑, Ψ4 = 푒 → 푐 푓 → 푐}. Định nghĩa 4 ([7]): Giả sử 훼 v 훽′. Gọi O(훼, 훽′) def= {훼′ | (훼′ v 훽′) ∧ (proj(훼′) = 훼} là tập tất cả các lần xuất hiện 훼′ của 훼 trong 훽′. Lợi ích bé nhất (gọi tắt là lợi ích) của 훼 trong 훽′ được định nghĩa là 푢min (훼, 훽′) def= min{푢(훼′) | 훼′ ∈ O(훼, 훽′)}. Lợi ích của 훼 trong D ′ được định nghĩa là 푢min (훼) def= ∑ Ψ′∈휌(훼) 푢min (훼,Ψ′)). Lúc đó, 훼 được gọi là chuỗi lợi ích cao (HU) nếu 푢min (훼) ≥ 푚푢. Từ nay, ta viết gọn 훼푢푠 để diễn tả rằng 푢min (훼) = 푢 và supp(훼) = 푠. Lý do của việc sử dụng 푢min có thể tham khảo thêm trong [7, 8, 13]. Lấy ví dụ, xét 훼 = 푒 → 푐푒 với 휌(훼) = {Ψ′1,Ψ′2} và supp(훼) = 2. Dễ thấy rằng, O(훼,Ψ′4) = {(푒, 20) → (푐, 8) (푒, 35), (푒, 20) → (푐, 5) (푒, 20), (푒, 35) → (푐, 5) (푒, 20)}. Do đó, 푢min (훼,Ψ′1) = min{63, 45, 60} = 45 và tương tự, 푢min (훼,Ψ′1) = 51. Vì vậy, ta có 훼962 . Định nghĩa 5: Một chuỗi HU 훾 được gọi là chuỗi sinh lợi ích cao, GHU, nếu không tồn tại chuỗi con HU có cùng độ hỗ trợ với nó. Tập tất cả các chuỗi GHU được định nghĩa và ký hiệu là GHUS def= { 훾 ∈ HUS | š훾∗ ∈ HUS : (훾∗ @ 훾) ∧ (supp(훾) = supp(훾∗))}. Tập các chuỗi sinh phổ biến lợi ích cao, FGHU, được định nghĩa và ký hiệu là FGHUS def= { 훾 ∈ FHUS | š훾∗ ∈ FHUS : (훾∗ @ 훾) ∧ (supp(훾) = supp(훾∗))}. Khai thác tập FGHUS là mục tiêu của bài báo này. Ví dụ, xét 푚푢 = 226 và 푚푠 = 2. Với chuỗi 훾 = 푎 → 푔 → 푐푑푒, ta có 훾2282 ∈ FHUS. Hơn nữa, 훾 là một chuỗi FGHU, vì không tồn tại 훾∗ ∈ FHUS sao cho 훾∗ @ 훾 và supp(훾∗) = supp(훾). Đây cũng là chuỗi FGHU duy nhất, tức là FGHUS = {훾}. Để ý rằng, lực lượng của FGHUS thường bé hơn rất nhiều so với FHUS, đặc biệt khi 푚푢 và 푚푠 bé. Chẳng hạn, với 푚푢 = 1 và 푚푠 = 1, |FHUS| = 5235, trong khi đó |FGHUS| = 105 (khoảng 2% của |FHUS|). Định nghĩa 6 ([7]): Ta định nghĩa 푠-mở rộng và 푖-mở rộng của 훼 và 훽 lần lượt là 훼 푠 훽 def= 퐴1 → 퐴2 → · · · → 퐴푝 → 퐵1 → 퐵2 → · · · → 퐵푞 , 훼 푖 훽 def= 퐴1 → 퐴2 → · · · → (퐴푝 ∪ 퐵1) → 퐵2 → · · · → 퐵푞 , trong đó 푎 ≺ 푏 với mọi 푎 ∈ 퐴푝 và 푏 ∈ 퐵1. Một mở rộng tiến (hay mở rộng) của 훼 với 훽, ký hiệu là 훾 = 훼  훽, là một 푖-mở rộng hoặc là 푠-mở rộng, tức là 훼 푖 훽 hay 훼 푠 훽. Khi đó, 훼 được gọi là một tiền tố của 훾 và 훽 là một hậu tố (đối với 훼) của 훾. Ngoài ra, nếu 훿 là tiền tố bé nhất (của 훾 với v) chứa 훼, ta ký hiệu 훿 là pref (훾, 훼). Hậu tố 훽 của 훾 (đối với 훿, tức là 훾 = 훿  훽) được ký hiệu là suf (훾, 훼). Cơ sở dữ liệu chiếu (PDB) của 훼 được định nghĩa là D훼 def= {suf (Ψ, 훼) | (Ψ ∈ D) ∧ (Ψ w 훼)}. Ta nói D훽 chứa trong D훼, ký hiệu là D훽 v 퐷훼, nếu 휌(훽) ⊆ 휌(훼) và với mọi Ψ ∈ 휌(훽) ta có suf (Ψ, 훽) v suf (Ψ, 훼). Khi D훽 v D훼 và D훼 v D훽 , ta nói rằng D훽 bằng D훼 và ký hiệu D훽 = D훼. Dễ thấy rằng supp(훼) = |D훼 |. Ví dụ, với 훼 = 푒 → 푒 @ 훽 = 푒 → 푐푒, ta có 휌(훼) = 휌(훽) = {Ψ1,Ψ2}, suf (Ψ1, 훼) = _푔 → 푎푐푒 và suf (Ψ2, 훼) =. Do đó, PDB của 훼 là D훼 = {_푔 → 푎푐푒, }. Tương tự, ta có D훽 = D훼. Không gian tìm kiếm chuỗi lời giải được biểu diễn bởi một cây tiền tố với gốc là chuỗi rỗng, mỗi nút biểu diễn một chuỗi ứng viên, mỗi nút con biểu diễn một chuỗi mở rộng. Ta ký hiệu branch(훼) là nhánh có gốc tại nút biểu diễn 훼, nó chứa 훼 và các mở rộng của nó. Với một tiền tố khác rỗng 훼, 훽 = 훼  푦, chuỗi 훾 = 훼  휀  푦 mà 훾 w 훽 được gọi là một mở rộng lùi (BE) của 훽 bởi 휀, với 푦 là thuộc 60 Tập 2019, Số 2, Tháng 12 tính cuối của 훽, ký hiệu là lastItem(훽). Chẳng hạn, với 훼 = 푐푑 thì branch(훼) chứa các chuỗi: 푐푑 → 휀, 푐푑푒 → 휀 và 푐푑푒푔 → 휀, với mọi 휀, kể cả . Cho 훽 = 푐푒, các chuỗi 푐푑푒 và 푐 → 푐푔 → 푐푑푒 là các BE của 훽. Tuy nhiên, 푐푒 → 푐푔 → 푒 là BE của 푐 → 푒, nhưng không là BE của 훽. Thách thức chính của HUSM là 푢min không đơn điệu tăng cũng không đơn điệu giảm, tức là ∃훽, 훼, 훾, 훿 : (훽 A 훼) ∧ (훾 @ 훿) (푢min (훽) > 푢min (훼)) ∧ (푢min (훾) > 푢min (훿)). Nói cách khác, 푢min không thỏa mãn DCP (tính chất của supp được sử dụng trong FSM). Thật vậy, với 훼 = 푐푑, 훽 = 푐푑푔, và 훿 = 푐 → 푐 → 푐푑, dễ thấy rằng 훿 A 훼 @ 훽 và 푢min (훽) = 84 > 푢min (훼) = 54 > 푢min (훿) = 27. Để khắc phục, các chặn trên 푢min thỏa mãn các tính chất tựa đơn điệu giảm (có thể yếu hơn DCP) được đề xuất trong mục tiếp theo. 2. Hai chiến lược tỉa các chuỗi LU và LF theo chiều sâu và chiều rộng Giả sử 훼′ v Ψ′, 훼 = proj(훼′) v Ψ′, với Ψ′ = 퐵′1 → 퐵′2 → · · · → 퐵′푞 ∈ D ′, tức là tồn tại 푝 số nguyên, 1 ≤ 푖1 < 푖2 < · · · < 푖푝 ≤ 푞 sao cho 퐴′푘 v 퐵′푖푘 và 퐴푘 = proj(퐴′푘 ) ⊆ proj(퐵′푖푘 ), với mọi 푘 = 1, 2, . . . , 푝. Chỉ số cuối 푖푝 được gọi là điểm cuối của 훼 (hay 훼′) trong Ψ′, ký hiệu là end(훼,Ψ′) (hay end(훼′,Ψ′)). Thuộc tính cuối của 훼 trong 퐵′푖푝 được gọi là thuộc tính cuối ứng với 푖푝 , ký hiệu là 푒푖푝 . Khi đó, 푞-chuỗi còn lại của 훼 trong Ψ′ (đối với 푖푝) là phần còn lại của Ψ′ sau 푒푖푝 , ký hiệu là rem(훼,Ψ′, 푖푝). Gọi 푖∗푝 def= FEnd(훼,Ψ′) là điểm cuối đầu tiên của 훼 trong Ψ′. Cơ sở dữ liệu chiếu lượng hóa (PQDB) D ′훼 của 훼 chứa tất cả các chuỗi còn lại rem(훼,Ψ′, 푖∗푝), với Ψ′ ∈ D ′. Nếu 훼 =, ta quy ước 푖∗푝 def= FEnd(,Ψ′) def= 0, D ′ def= D ′ và rem(,Ψ′, 푖∗푝) = Ψ′. Với mỗi điểm cuối 푖푝 = end(훼,Ψ′), ta định nghĩa 푢(훼,Ψ′, 푖푝) def= min{푢(훼′) | 훼′ ∈ O(훼,Ψ′) ∧ end(훼′,Ψ′) = 푖푝}. Chặn trên dựa vào lợi ích còn lại của 푢min (훼,Ψ′) được định nghĩa và ký hiệu: 푢푏rem (훼,Ψ′) def= { 푢(훼,Ψ′, 푖∗푝) + 푢(rem(훼,Ψ′, 푖∗푝)), 훼 ≠, 푢(Ψ′), 훼 = . Ví dụ, xét 훽 = 푐 → 푑. Do lần xuất hiện đầu tiên của 훽 trong Ψ′1 là 푞-chuỗi con 훽 ′ = (푐, 2) → (푑, 16) v Ψ′1, nên 푖∗푝 def = FEnd(훽,Ψ′1) = 4, rem(훽,Ψ′1, 푖∗푝) = (푒, 35) (푔, 60) → (푎, 3) (푐, 5) (푒, 20), 푢(rem(훽,Ψ′1, 푖∗푝)) = 123, 푢(훽,Ψ′1, 푖∗푝) = min{푢(훽′), 푢((푐, 1) → (푑, 16))} = 17. Vì vậy 푢푏rem (훽,Ψ′1) = 17 + 123 = 140. Một độ đo 푢푏 được gọi là một chặn trên của 푢min nếu 푢min (훼) ≤ 푢푏(훼), với mọi 훼. Ngoài chặn trên truyền thống SWU(훼) def= ∑Ψ′∈휌(훼) 푢(Ψ′) [5], ta còn có các chặn trên chặt hơn sau đây. Định nghĩa 7 ([7]): Xét 푦 ∈ A và 훼 khác rỗng. Ta định nghĩa các chặn trên sau đây: RBU(훼) def= ∑ Ψ′∈휌(훼) 푢푏rem (훼,Ψ′), LRU(훼  푦) def= ∑ Ψ′∈휌(훼푦) 푢푏rem (훼,Ψ′), LRU(푦) def= SWU(푦). Với hai chặn trên 푢푏1 và 푢푏2, 푢푏1 được gọi là chặt hơn 푢푏2, ký hiệu là 푢푏1  푢푏2, nếu 푢푏1 (훼) ≤ 푢푏2 (훼) với mọi 훼. Theo [7, Định lý 1], ta có 푢min  RBU  LRU  SWU . Ví dụ, xét chuỗi 훽 = 푐 → 푐푑, 휌(훽) = {Ψ′1,Ψ′2}. Khi đó 푢min (훽,Ψ′1) = 25, 푢min (훽,Ψ′2) = 39, FEnd(훽,Ψ′1) = 4, 푢(훽,Ψ′1, 4) = 25, 푢(rem(훽,Ψ′1, 4)) = 123. Vì vậy 푢min (훽) = 푢min (훽,Ψ′1) + 푢min (훽,Ψ′2) = 64, 푢푏rem (훽,Ψ′1) = 150, 푢푏rem (훽,Ψ′2) = 64, RBU(훽) = 푢푏rem (훽,Ψ′1) + 푢푏rem (훽,Ψ′2) = 212. Ngoài ra, với 훼 = 푐 → 푐, ta dễ thấy rằng 훽 = 훼 푖 푑 và LRU(훽) = 푈퐵rem (훼,Ψ′1) + 푢푏rem (훼,Ψ′2) = 200 + 165 = 365, SWU(훽) = 푢(Ψ′1) + 푢(Ψ′2) = 229 + 208 = 437. Vì vậy ta có 푢min (훽) < RBU(훽) < LRU(훽) < SWU(훽). Để loại nhanh các chuỗi có lợi ích thấp hoặc ít phổ biến, dựa vào [7, Định lý 2], ta thiết kế hai chiến lược DPS và WPS nhằm thu hẹp hiệu quả không gian tìm kiếm. Trước hết, ta có chiến lược tỉa theo chiều sâu dựa vào RBU, viết là DPS(RBU), như sau: “Nếu RBU(훼) < 푚푢 thì branch(훼) có thể được tỉa”. Gọi hai tập thuộc tính ứng viên cho các 푖− và 푠-mở rộng lần lượt là: 퐼LRU (훼) def= {푧 | (LRU(훼 푖 푧) ≥ 푚푢) ∧ (supp(훼 푖 푧) ≥ 푚푠)}, 푆LRU (훼) def= {푧 | (LRU(훼 푠 푧) ≥ 푚푢) ∧ (supp(훼 푠 푧) ≥ 푚푠)}. 61 Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông Nếu 푢min (훼 푖 푧) ≥ 푚푢 và supp(훼 푖 푧) ≥ 푚푠, thì LRU(훼 푖 푧) ≥ 푢min (훼 푖 푧) ≥ 푚푢, tức là 푧 ∈ 퐼LRU (훼). Vì LRU(훼 푖 푦 푖 푧) ≤ LRU(훼 푖 푧), max{LRU(훾) | 훾 ∈ {훼 푖 푦 푠 푧, 훼 푠 푦 푖 푧, 훼 푠 푦 푠 푧}} ≤ LRU(훼 푠 푧), supp(훼  푦  푧) ≤ supp(훼  푧), với 훼  푦  푧 w 훼  푧. Cho nên ta có 퐼LRU (훼 푖 푦) ⊆ 퐼LRU (훼), (푆LRU (훼 푖 푦) ∪ 푆LRU (훼 푖 푦)) ⊆ 푆LRU (훼). Từ đó, ta có chiến lược tỉa theo chiều rộng dựa vào LRU, viết là WPS(LRU), như sau: “Nếu LRU(훼  푦) < 푚푢, ta không cần xét tất cả các mở rộng tiến của 훼  푦, tức là branch(훼  푦), và các mở rộng lùi của nó. Lấy ví dụ, với 푚푢 = 230 và 푚푠 = 2, ta có supp(푏) < 푚푠 và LRU(푏) = 174 < 푚푢. Các giá trị LRU của các thuộc tính còn lại, trong tập chứa các thuộc tính ứng viên cho các mở rộng, 퐼LRU () = 푆LRU () = {푎, 푐, 푑, 푒, 푓 , 푔}, đều lớn hơn hay bằng mu (chẳng hạn LRU(푎) = 447). Khi đó, do WPS(LRU), ta có thể loại thuộc tính 푏 khỏi D ′. Để minh họa tác dụng tỉa theo chiều sâu của RBU, xét hai giá trị RBU(푎푐) = 199 và RBU(푎 → 푐) = 229 đều bé hơn 푚푢. Sử dụng DPS(RBU), toàn bộ nhánh branch(푎푐) và branch(푎 → 푐) bị tỉa. Dễ thấy rằng, sử dụng supp, 퐼LRU (푎) = {푐, 푒} và 푆LRU (푎) = {푎, 푐, 푑, 푒, 푔}(⊆ 푆LRU ( )). Vì 푆LRU (푎 → 푐) ⊆ 푆LRU (푎) và với bất kỳ 푥 ∈ 푆LRU (푎), RBU(푎 → 푐 → 푥) < LRU(푎 → 푐 → 푥) = 229 < 푚푢 hay supp(푎 → 푐 → 푥) = 1 < 푚푠, 푆LRU (푎 → 푐) = ∅. Do đó, bởi DPS(RBU), ta chỉ có thể tỉa nhánh branch(푎 → 푐 → 푥), với mọi 푥 ∈ {푎, 푐, 푑, 푒, 푔}. Tuy nhiên, sử dụng WPS(LRU), ta vẫn có thể loại bỏ tất cả các nhánh mở rộng lùi của branch(푎 → 푐 → 푥), ví dụ như branch(푎 → 푐 → 푔 → 푑), branch(푎 → 푐푒 → 푐푔 → 푐푑) (của branch(푎 → 푐 → 푑)), v.v. Thật vậy, lý do là 퐼LRU (푎 → 푐푒 → 푐푔 → 푐) ⊆ 푆LRU (푎 → 푐푒) ⊆ 푆LRU (푎 → 푐) = ∅. Ngoài ra, mặc dù chặt hơn LRU, nhưng RBU không có tác dụng tỉa theo chiều rộng. Nếu dùng RBU để tỉa theo chiều rộng, ta có thể tỉa nhầm một số lời giải. Thật vậy, với 푚푢 = 225 và 푚푠 = 2, vì 퐼RBU (푎 → 푔 → 푒 → 푐) (⊆ 푆RBU (푎 → 푔 → 푒) = {푐}), nên 퐼RBU (푎 → 푔 → 푒 → 푐) = ∅. Tuy nhiên, 푎 → 푔 → 푒 → 푐푒2252 ∈ FHUS. Có thể kết luận rằng, mặc dù LRU lỏng hơn RBU, tác dụng tỉa của WPS thật sự mạnh hơn DPS. Vì vậy, DPS và WPS được dùng để tỉa các nhánh LU (và LF) trên cây tìm kiếm tiền tố, có hiệu quả với các giá trị 푚푢 cao [7]. Tuy nhiên, nhiều chuỗi HU có thể không là các chuỗi sinh HU (non-GHU). Do đó, trong phần tiếp theo, chiến lược LPG tỉa các ứng viên non-GHU sẽ được đề xuất. Để ý rằng, LPG sẽ hiệu quả với các giá trị 푚푢 thấp. III. CHIẾN LƯỢC LPG TỈA SỚM CÁC CHUỖI KHÔNG LÀ SINH LỢI ÍCH CAO 1. Điều kiện tỉa sớm tổng quát Trước hết, chúng tôi nhắc lại hai độ đo SE, SLIP và điều kiện tỉa sớm tổng quát đã được dùng để tỉa các chuỗi phổ biến đóng và các chuỗi phổ biến đóng có lợi ích cao [13], hoặc các chuỗi sinh phổ biến [12]. Định nghĩa 8 ([12]): Tổng các sự kiện còn lại trong một PDB D훼 được định nghĩa và ký hiệu là: SE(훼) def= ∑ Ψ∈D: suf (Ψ,훼) ∈D훼 ( size(Ψ) − size(pref (Ψ, 훼)) + 1) . Với chuỗi 훼, gọi 훿 là tiền tố bé nhất của Ψ chứa 훼, Ψ ∈ 휌(훼). Đặt 푓 푖(훼,Ψ) là chỉ số (trong Ψ) của sự kiện cuối của 훿 và lastEvent(훼) là sự kiện cuối của 훼. Gọi LP(훼,Ψ) là danh sách các vị trí thứ 푖 khác nhau trong Ψ mà lastEvent(훼) ⊆ Ψ[푖] và 푓 푖(훼,Ψ) ≤ 푖 ≤ size(Ψ). Không mất tổng quát, giả sử rằng các chỉ số trong LP(훼,Ψ) được sắp tăng. Khi đó, slip(훼,Ψ) def= | LP(훼,Ψ) | là số các vị trí xuất hiện của sự kiện cuối của 훿 trong Ψ. Định nghĩa 9 ([13]): Số đo SLIP của PDB D훼 được định nghĩa và ký hiệu là SLIP(훼) def= ∑ Ψ∈휌(훼) slip(훼,Ψ). Ví dụ, xét 훼 = 푒 → 푒. Vì D훼 = {_푔 → 푎푐푒, }, nên SE(훼) = 3. Ta có 휌(훼) = {Ψ1,Ψ2}. Vì sự kiện cuối 푒 xuất hiện hai lần trong Ψ1 tại vị trí thứ 4 và thứ 5, nên LP(훼,Ψ1) = {4, 5}. Tương tự, LP(훼,Ψ2) = {5}. Vì vậy, SLIP(훼) = 3. Từ SE và SLIP, ta có điều kiện tỉa sớm tổng quát (GEP) trong Định lý 1 sau đây. Định lý 1 (Điều kiện tỉa sớm tổng quát [13]): Xét hai chuỗi 훼 và 훽 thỏa mãn 훼 v 훽. Khi đó: a) Nếu SE(훼) = SE(훽), thì supp(훼) = supp(훽) và D훾 = D휆 với mọi 푠-mở rộng 훾 của 훼 và 휆 của 훽 với cùng một chuỗi khác rỗng; b) Nếu SE(훼) = SE(훽) và SLIP(훼) = SLIP(훽), thì supp(훼) = supp(훽) và D훾 = D휆 với tất cả mở rộng 훾 của 훼 và 휆 của 훽 với cùng một chuỗi khác rỗng. 2. Chiến lược LPG Dựa vào GEP và chặn dưới SF sau đây của 푢min, chiến lược LPG tỉa sớm các chuỗi non-GHU được đề xuất. Định nghĩa 10: Cho chuỗi phổ biến 훼, tức là supp(훼) ≥ 푘 , với 푘 def= 푚푠. Sau khi sắp xếp tăng dần dãy U(훼) def= {푢min (훼,Ψ′) | Ψ′ ∈ 휌(훼)}, 62 Tập 2019, Số 2, Tháng 12 ta thu được dãy {푢푖 , 1 ≤ 푖 ≤ 푛} với 푛 ≥ 푘 . Chặn dưới SF của 푢min được định nghĩa là tổng 푘 giá trị bé nhất của U(훼), SF(훼) def= ∑ 1≤푖≤푘 푢푖 . Định lý 2: Ta có: (a) SF là một chặn dưới của 푢min, tức là SF(훼) ≤ 푢min (훼), với mọi 훼; (b) SF là đơn điệu tăng đối với các mở rộng, tức là SF(훽) ≥ SF(훼), với mọi 훽 = 훼  훿 w 훼. Chứng minh: (a) Với mọi 훼, ta có SF(훼) = ∑푘푖=1 푢푖 ≤∑푛 푖=1 푢푖 = 푢min (훼). (b) Với mở rộng bất kỳ 훽 = 훼훿 w 훼, ta có 휌(훽) ⊆ 휌(훼) và 푢min (훽,Ψ′) ≥ 푢min (훼,Ψ′), với mọi Ψ′ ∈ 휌(훽). Thật vậy 푢min (훽,Ψ′) def= min{푢(훽′) | 훽′ ∈ O(훽,Ψ′)} = 푢(훽′min), ∃훼′∗ ∈ O(훼,Ψ′), 휀′∗ v 훽′min sao cho 훼 v 훽′min = 훼′∗  휀′∗ ∈ O(훽,Ψ′) và 푢(훽′min) = 푢(훼′∗) + 푢(휀′∗) ≥ 푢(훼′∗) ≥ min{푢(훼′) | 훼′ ∈ O(훼,Ψ′)} def= 푢min (훼,Ψ′). Sau khi sắp tăng U(훼) và U(훽), ta có được hai dãy {푢푖 , 1 ≤ 푖 ≤ 푛}, {푢′푗 , 1 ≤ 푗 ≤ 푚} với 푛 ≥ 푚 ≥ 푘 . Khi đó, tồn tại các số nguyên 1 ≤ 푖1 < 푖2 < · · · < 푖푚 sao cho 푢푖 푗 ≤ 푢′푗 , với 1 ≤ 푗 ≤ 푚, nên ta có SF(훼) = 푘∑ 푖=1 푢푖 ≤ 푘∑ 푗=1 푢푖 푗 ≤ 푘∑ 푗=1 푢′푗 = SF(훽). Ví dụ, khi xét hai ngưỡng 푚푢 = 85, 푚푠 = 2 và mở rộng 훽 = 푒 → 푒 của 훼 = 푒, ta có 휌(훽) = {Ψ′1,Ψ′2} ⊂ 휌(훼) = D ′, 푢min (훼) = 120, 푢min (훽) = 85, và U(훼) = {20; 20; 40; 40}, U(훽) = {40; 45}, nên SF(훼) = 20 + 20 = 40 và SF(훽) = 40 + 45 = 85. Khi đó, SF(훼) < 푢min (훼), SF(훽) ≤ 푢min (훽), và SF(훼) < SF(훽). Trên cây tiền tố với gốc Root =, với mỗi nút 푞 (1- thuộc tính), ta có chuỗi tương ứng 훼 = path(푞), trong đó path(푞) là chuỗi đầy đủ thu được bằng cách duyệt từ Root đến 푞. Nút 푞 có 푖-mở rộng và 푠-mở rộng bởi hai thuộc tính 푢 và 푣 tương ứng, ký hiệu là, 훼 푖 푢 và 훼 푠 푣. Khi đó, ta gán 푢.type = 푖-ext và 푣.type = 푠-ext. Ký hiệu tập chứa 훼 và tất cả các mở rộng (hay các 푠-mở rộng, các 푖-mở rộng) cũng như tất cả các hậu duệ của các mở rộng này (hay các 푠-mở rộng và các 푖-mở rộng) là branch(훼) (hay tương ứng là 푠-child branches(훼) và 푖-child branches(훼)). Nếu tất cả các chuỗi trong các nhánh này không là chuỗi sinh HU, ta ký hiệu chúng là non-GHU branch(훼) (hay tương ứng là non-GHU s-child branches(훼) và non-GHU i-child branches(훼)). Định lý 3 (Chiến lược LPG): Xét 푞, 푢, 푣 là các nút có cùng tiền tố và 훼 = path(푞) là chuỗi ứng với 푞. (a) Với mỗi 푖-mở rộng, 푖new = 훼 푖 푢: (i) Nếu SE(훼) = SE(푖new) và SF(훼) ≥ 푚푢, thì non-GHU s-child branches(푖new) có thể được tỉa. Hơn nữa, nếu SLIP(훼) = SLIP(푖new), thì toàn bộ nhánh non-GHU branch(푖new) cũng được tỉa; (ii) Nếu SE(path(푢)) = SE(푖new) và SF(path(푢)) ≥ 푚푢, thì non-GHU s-child branches(푖new) được tỉa. Ngoài ra, nếu SLIP(path(푢)) = SLIP(푖new), thì non-GHU branch(푖new) được tỉa; (iii) Nếu q.type = s-ext, q.Parent.Item = q.Item (tồn tại 푟 ∈ q.Parent.iChildren sao cho r.Item = u.Item), q.Parent.type = s-ext, SE(path(푟)) = SE(푖new) và SF(path(푟)) ≥ 푚푢, thì ta có thể tỉa non-GHU branch(푖new). (b) Với mỗi 푠-mở rộng, 푠new = 훼 푠 푣 sao cho v.type = s-ext, nếu SE(path(푣)) = SE(푠new) và SF(path(푣)) ≥ 푚푢, thì non-GHU branch(푠new) có thể được tỉa. Chứng minh: Ta sẽ chứng minh a(i). Các khẳng định còn lại có thể được chứng minh tương tự. Giả sử rằng SE(훼) = SE(푖new) và SF(훼) ≥ 푚푢. Vì 훼 @ 푖new, với mọi 푠-mở