Secure Association Rule Sharing
Tóm tắt
Những chia sẻ của luật kết hợp thường có lợi trong ngành công nghiệp,nhưng đòi hỏi phải có biện pháp bảo vệ quyền riêng tư. Họcó thể quyết định tiết lộ chỉmột phầncác kiến thức và che giấu các mẫu chiến lược mà chúng ta gọi là các luậthạn chế. Những luậthạn chế phải được bảo vệ trước khi chia sẻ vì chúnglà tối quan trọng cho các quyết định chiến lược và cần phải giữ riêng tư. Giải quyết vấn đề khó khăn này, chúng tôi đề xuất một hướng bảo vệkiến thức nhạy cảm trước khi chia sẻ. Hướngnày bao gồm: (a)một thuật toánloại bỏ các luật hạn chế, và ngăn chặn một số kênh suy luận. Xác nhận thuật toán đối với các tập dữ liệu thực tế và tổng hợp;(b) một tập hợp các số liệu đánh giá các cuộc tấn công chống lại các kiến thứcnhạy cảm và tác động của việc làm sạch. Chúng tôi cũng giới thiệu một nguyên tắc phân loại cácthuật toán làm sạchvà một nguyên tắc phân loại các cuộc tấn công chống lại các kiến thức nhạy cảm.
1. Giới thiệu
Bảo vệ chống lại suy luận trong khai thác dữ liệu đã bắt đầu nhận được sự chú ý.Đặc biệt, vấn đề bảo đảm riêng tư khi chia sẻ dữ liệu trong khimuốn che giấu một số mẫu phổ biến đã được đề cập trong các tài liệukhác. Các giải pháp được đề xuất bao gồm việc chuyển đổi cơ sở dữ liệu giao dịchđể khi chia sẻ, các mẫu phổ biếnkhông thể được phát hiện. Quá trình nàyđược gọi là chuyển đổidữ liệu. Hiệu quả của việc chuyển đổidữ liệu được đobởi tỷ lệ ẩn hiệu quả của mẫu phổ biến (giấu thất bại), tỷ lệ các luật vô tình ẩn (chi phí bỏ lỡ) và số lượng luật tạo ra bởi quá trình. Giải quyết vấn đề chúng tôi ở đây khác hơn và thực tế hơn, đó là vấn đề loại bỏ các luật. Thay vì chia sẻ các dữ liệu, các cộng tác viên thích khai thác dữ liệu riêng của họ và chia sẻ các mẫu được phát hiện.
Chúng ta hãy xem xét một ví dụ. Giả sử chúng ta có một máy chủ và nhiều khách hàng, trong đó mỗi khách hàng có một số mặt hàng bán ra (ví dụ như sách, phim ảnh, vv). Các khách hàng muốn máy chủ thu thập thông tin thống kê về liên kết trong số các mặt hàng để cung cấp các khuyến cáo cho các khách hàng. Tuy nhiên, các khách hàng không muốn máy chủ biết một số luật kết hợp hạn chế. Trong tình huống này, clients đại diện cho các công ty và các server là một hệ thống khuyến cáo cho một ứng dụng thương mại điện tử. Khi một khách hàng gửi tập phổ biến của họ hoặc các luật kết hợp tới máy chủ, nó loại bỏ một số tập phổ biến hạn chế theo một số chính sách cụ thể. Sau đó các máy chủ tập hợp thông tin thống kê từ các tập phổ biến được loại bỏ và phục hồi chúng từ các liên kết thực tế.
Các giải pháp đơn giản để giải quyết ví dụ trên là thực hiện một bộ lọc sau giai đoạn khai thác để loại bỏ/ ẩn các luật bị hạn chế được phát hiện. Tuy nhiên, chúng tôi cho rằng cắt tỉa một số luật ra không đảm bảo việc bảo vệ đầy đủ. Việc loại bỏ được áp dụng cho tập luật không để lại một dấu vết có thể bị khai thác bởi kẻ thù. Chúng ta phải đảm bảo rằng một số kênh suy luận đã bị chặn là tốt.
Bài này giới thiệu các khái niệm về quy tắc loại bỏ. Những đóng góp chính của bài báo này là một hướng mới để bảo vệ kiến thức nhạy cảm trước khi chia sẻ luật kết hợp. Hướng này bao gồm: (a) một thuật toán gọi là Downright Sanitizing Algorithm (DSA). Thuật toán này loại bỏ một tập các luật hạn chế trong khi ngăn chặn một số kênh suy luận; (b) một tập các số liệu để đánh giá các cuộc tấn công chống lại kiến thức nhạy cảm và tác động của việc loại bỏ. Đóng góp khác là một nguyên tắc phân loại của các thuật toán thanh lọc. Cuối cùng, chúng tôi trình bày một phân loại của các cuộc tấn công chống lại kiến thức nhạy cảm.
Bài viết này được tổ chức như sau. Công việc liên quan được xem xét trong phần 2. Các định nghĩa vấn đề được nêu tại mục 3. Trong phần 4, chúng tôi trình bày khuôn khổ của cho bảo vệ kiến thức nhạy cảm. Trong phần 5, chúng tôi giới thiệu thuật toán (DSA). Các thuật toán mở rộng cải tiến được thảo luận trình bày trong phần 6. Cuối cùng, Phần 7 trình bày kết luận của chúng tôi và một cuộc thảo luận về công việc tương lai.
2. Công việc liên quan
Một số nỗ lực đã được thực hiện để giải quyết vấn đề bảo vệ kiến thức nhạy cảm trong khai thác luật kết hợp bởi việc làm sạch dữ liệu. Các thuật toán được phân thành hai loại chính: phương pháp tiếp cận Data-Sharing và cách tiếp cận Pattern-Sharing (trong hình 1A). Trước đây, quá trình thanh lọc thực hiện trên dữ liệu để loại bỏ hoặc ẩn nhóm của luật kết hợp hạn chế có chứa kiến thức nhạy cảm. Để làm như vậy, một số nhỏ các giao dịch có chứa các luật hạn chế đã được sửa đổi bằng cách xóa một hoặc nhiều mục từ chúng hoặc thậm chí thêm một số các mục mới ban đầu không có mặt trong các giao dịch như vậy. Phần thứ hai, thuật toán chuyển đổi hoạt động trên các quy tắc khai thác từ một cơ sở dữ liệu, thay vì các dữ liệu chính nó. Các thuật toán chỉ được biết đến trong thể loại này là thuật toán DSA của chúng tôi trình bày ở đây. Các thuật toán loại bỏ tất cả các luật hạn chế trước khi chia sẻ.Trong số các thuật toán của phương pháp tiếp cận Data-Sharing, chúng tôi phân loại như sau loại: Item Restriction-Based, Item Addition-Based và Item Obfuscation-Based.
Item Restriction-Based: Các thuật toán này loại bỏ một hoặc nhiều mục từ một nhóm các giao dịch có chứa luật hạn chế. Khi làm như vậy, thuật toán giấu luật hạn chế bằng cách giảm độ hỗ trợ ở dưới một ngưỡng riêng. Các thuật toán khác nằm trong loại này, ẩn luật bằng cách đáp ứng một ngưỡng kiểm soát tiết lộ ψ của chủ sở hữu cơ sở dữ liệu. Khi ψ = 0%, không có luật kết hợp hạn chế được phép phát hiện. Khi ψ = 100%, không giới hạn trên các luật kết hợp hạn chế.
Item Addition-Based: Không giống như các thuật toán trước đó, các thuật toán này dựa trên mục sửa đổi các thông tin hiện có trong cơ sở dữ liệu giao dịch bằng cách thêm một số mặt hàng ban đầu không được hiện diện trong một số giao dịch. Các mục được thêm vào phần tiền đề X của một luật X → Y trong các giao dịch bảo đảm một phần hỗ trợ nó. Khi làm như vậy, độ tin cậy các luật là giảm. Cách tiếp cận này có thể tạo ra các luật kết hợp nhân tạo và nó sẽ không tồn tại trong cơ sở dữ liệu ban đầu.
Item Obfuscation-Based: Các thuật toán này quy tắc ẩn bằng cách đặt một dấu"?" (ẩn số) trong hạng mục của một số giao dịch có chứa luật hạn chế, thay vì xóa các mục. Khi làm như vậy, các thuật toán làm mờ một tập hợp các luật hạn chế bằng cách thay thế các giá trị được biết đến với ẩn số. Cũng giống như các thuật toán dựa trên giảm mục, các thuật toán giảm tác động trong cơ sở dữ liệu làm sạch bảo vệ khai thác từ việc học các quy tắc lỗi.
Các công việc trình bày ở đây khác với các công việc liên quan trong một số khía cạnh như sau: đầu tiên thuật toán của chúng tôi giải quyết vấn đề Pattern-Sharing và loại bỏ các luật, không giao dịch. Thứ hai, chúng ta nghiên cứu các cuộc tấn công chống lại các kiến thức nhạy cảm.
3. Định nghĩa vấn đề
Các vấn đề cụ thể được đề cập trong báo cáo này có thể được phát biểu như sau: Cho D là một cơ sở dữ liệu, R là tập các luật khai thác từ D dựa trên một ngưỡng hỗ trợ tối thiểu σ, và RR là một tập hợp các luật hạn chế phải được bảo vệ theo một số chính sách bảo mật/ riêng tư. Mục đích là để chuyển R thành R’, trong đó R’đại diện cho tập các luật không hạn chế. Trong trường hợp này, R’ trở thành tập được lấy ra từ các luật đó, được làm sẵn để chia sẻ.
Lý tưởng nhất, R’= R-RR. Tuy nhiên, có thể có một bộ luật r trong R’ từ đó người ta có thể lấy được hoặc suy ra một luật hạn chế trong RR. Vì vậy, trong thực tế, R’= R- (RR + RSE), với RSE là tập hợp các luật không hạn chế được loại bỏ như tác dụng phụ của quá trình làm sạch để tránh phục hồi của RR.
Hình 1B minh họa các vấn đề xảy ra trong quá trình dọn dẹp. Vấn đề 1 chuyển tải các luật không hạn chế được loại bỏ như một tác dụng phụ của quá trình (RSE). Vấn đề này là side effect. Nó liên quan đến vấn đề các chi phí bỏ lỡ trong chuyển đổi dữ liệu. Vấn đề 2 xảy ra khi sử dụng một số luậtkhông hạn chế, một đối thủ có thể phục hồi một số những hạn chế của các kênh suy luận. Chúng tôi tham khảo đến như một vấn đề như hệ số phục hồi.
4. Framework For Protecting Sensitive Knowledge
Trước khi giới thiệu hướng bảo vệ kiến thức nhạy cảm, chúng tôi xem xét ngắn gọn một số thuật ngữ từ lý thuyết đồ thị.
4.1. Các định nghĩa cơ bản
Các tập phổ biến trong một cơ sở dữ liệu có thể được biểu diễn dưới dạng một đồ thị có hướng, như một đồ thị tập phổ biến thường xuyên (Frequent Itemset Graph) và định nghĩa nó như sau:
Định nghĩa 1: (Frequent Itemset Graph). Một đồ thị tập phổ biến thường xuyên, kí hiệu bằng G = (C, E), là một biểu đồ chỉ dẫn bao gồm một tập hợp khác rỗng của tập phổ biến C, một tập các cạnh E được xếp thứ tự cặp các thành phần của C, như vậy ∀u, v ∈ C có một cạnh từ u đến v nếu u ∩ v = u và nếu | v | - | u| = 1 với | x | là kích thước của tập phổ biến x.
Hình 2b cho thấy một đồ thị tập phổ biến cho các cơ sở dữ liệu giao dịch mẫu (mô tả trong hình 2a). Trong ví dụ này, σ ngưỡng hỗ trợ tối thiểu được thiết lập là 2. Có thể được nhìn thấy trong hình 2b, trong biểu đồ tập phổ biến G, có một sự sắp xếp cho mỗi tập phổ biến. Một sắp đặt như itemset level và định nghĩa:
Định nghĩa 2: (itemset Level). Cho G = (C, E) là một tập đồ thị phổ biến. Level của một tập phổ biến u, mà u ⊂ C, là chiều dài của con đường kết nối một tập phổ biến tới u.
Dựa trên định nghĩa 2, chúng tôi xác định level của một tập phổ biến đồ thị G như sau:
Định nghĩa 3: (Frequent Itemset Graph Level). Cho G = (C, E). Level của G là chiều dài của con đường tối đa kết nối một tập phổ biến u cho bất kỳ tập phổ biến v khác, như vậy mà u, v ∈ C, và u ⊂ v.
Nói chung, sự phát hiện của các tập phổ biến trong G là kết quả hướng từ trên xuống dưới của G được hạn chế bởi một σ ngưỡng hỗ trợ tối thiểu. Quá trình phát hiện sử dụng một cách tiếp cận lặp trong đó k-tập phổ biến được sử dụng để khám phá (k + 1) –itemsets.
4.2. Phân loại tấn công
Một cuộc tấn công xảy ra khi một người nào đó khai thác một tập các luật đã loại bỏ dựa trên luậtkhông hạn chế. Chúng tôi đã xác định được một số cuộc tấn công chống lại các luật loại bỏ như sau:
Tấn công Forward-Inference: Xem xét đồ thị tập phổ biến trong hình 3A. Giả sử chúng ta muốn làm sạch các luật hạn chế xuất phát từ các tập phổ biến ABC. Cách tiếp cận bình thường chỉ đơn giản là để loại bỏ các tập phổ biến ABC. Tuy nhiên, nếu AB, AC, và BC là phổ biến, một người khai thác có thể suy luận rằng ABC là phổ biến. Một chủ cơ sở dữ liệu phải thừa nhận rằng một đối thủ có thể sử dụng bất kỳ kênh suy luận để tìm hiểu một cái gì đó nhiều hơn là chỉ các luật kết hợp được phép. Chúng tôi đề cập đến cuộc tấn công này là tấn công forward - inference. Để xử lý các cuộc tấn công này, chúng ta cũng phải loại bỏ ít nhất một tập hợp con của ABC ở mức 1 của đồ thị tập phổ biến. Bổ sung nàylà cần thiết. Trong trường hợp của một đồ thị sâu hơn, việc loại bỏ được thực hiện đệ quy đến cấp 1. Chúng ta bắt đầu loại bỏ từ level 1 bởi vì chúng ta giả định rằng liên kết quy định phục hồi từ các tập phổ biến có ít nhất 2 sản phẩm. Do đó, các mặt hàng ở mức 0 của đồ thị tập phổ biến không được chia sẻ với bên thứ hai. Khi làm như vậy, chúng ta giảm các kênh suy luận và giảm thiểu các tác dụng phụ.
Tấn công Backward-Inference: Một kiểu tấn công xảy ra khi chúng ta làm sạch một tập phổ biến chưa phải là kết thúc. Dựa trên hình 3B, giả sử chúng ta muốn làm sạch bất kỳ luật có nguồn gốc từ các tập phổ biến AC. Nếu chúng ta chỉ cần loại bỏ AC, nó là đơn giản để suy ra các luật khai thác từ AC khi một trong hai ABC hoặc ACD là phổ biến. Chúng ta tham khảo cuộc tấn công này là tấn công suy luận ngược. Để chặn cuộc tấn công này, chúng ta phải loại bỏ bất kỳ tập có chứa AC. Trong trường hợp cụ thể này, ABC và ACD phải gỡ bỏ là tốt.
5. Rule Sanitization: The DSA Algorithm
5.1. The General Approach
Cách tiếp cận của chúng tôi về cơ bản có ba bước như sau. Các bước này được áp dụng sau giai đoạn khai thác, ví dụ, chúng ta giả định rằng đồ thị tập phổ biến G được xây dựng. Các thiết lập của tất cả các tập có thể được khai thác từ G, dựa trên một ngưỡng hỗ trợ σ tối thiểu, là ký hiệu là C.
Bước 1: Xác định các tập phổ biến hạn chế. Đối với mỗi quy tắc hạn chế trong RR, chuyển đổi nó thành một tập phổ biến ci∈ C và đánh dấu nó để được làm sạch.
Bước 2: Chọn các tập con để làm sạch. Trong bước này, mỗi tập phổ biến ci để được làm sạch, chúng tôi tính toán cặp items của nó từ cấp độ 1 trong G trở đi, các tập con của ci. Nếu chúng chưa được đánh dấu, chúng ta ngẫu nhiên chọn một trong số đó và đánh dấu nó phải được loại bỏ.
Bước 3: Làm sạch các tập con của cặp đánh dấu ở cấp độ 1. Sanitization của một tập hạn chế chỉ đơn giản là việc loại bỏ các bộ supersets của tất cả tập phổ biến ở mức 1 của G được đánh dấu để loại bỏ. Khối quá trình suy luận kênh.
5.2. The Downright Sanitizing Algorithm
Các yếu tố đầu vào cho DSA là tập phổ biến đồ thị G, tập hợp tất cả các luật kết hợp R được khai thác từ một cơ sở dữ liệu G, và tập các luật hạn chế RR để được loại bỏ. Các đầu ra là tập các luật kết hợp được dọn dẹp R’.
Downright_Sanitizing_Algorithm.
Input: G, R, RR
Output: R’
Step1: For each association rule rri RRdo
patternirri // chuyển mỗi rrivào một mẫu trình tự phổ biến
Step 2: For each patterni in the level k of G, với k>1 do
2.1. Pairs(patterni) //tính toán tất cả các cặp mục của patterni
2.2. If (Pais(patterni) MarkedPair = ) then
2.2.1. pi random(Pairs(patterni)) // lựa chọn ngẫu nhiên một cặp pi patterni
2.2.2. MarkedPair MarkPair pi // cập nhật danh sách MarkPair
Step 3: R’ R
3.1. For each itemset ci G do
if a MarkPair p, such that pMarkPair and pcithen
Remove(ci) from R’ // ci thuộc tập phụ của p
EndAlgorithm.
5.3. Chạy tay từng bước thuật toán DSA
TID List of Items
T1 A B C D
T2 A B C
T3 A C D
T4 A B C
T5 A B
Cho cơ sở dữ liệu giao dịch:
5.3.1. Tạo tập phổ biến
Bằng giải thuật Apriori cho cơ sở dữ liệu giao dịch này với các ngưỡng được lựa chọn là minsup = 2/5.Dùng để xây dựng đồ thị G.
Bước 1: Duyệt CSDL giao dịch để xác định độ hỗ trợ cho các tập phổ biến có độ dài 1. Các tập mục có độ hỗ trợ nhỏ hơn 2/5 sẽ bị loại bỏ. Trong trường hợp này chưa có tập mục nào bị loại, tất cả các tập đều là tập phổ biến.
Tập mục Số lần xuất hiện Độ hỗ trợ
A 5 5/5
{B} 4 4/5
{C} 4 4/5
{D} 2 2/5
Tập mục Số lần xuất hiện Độ hỗ trợ
A 5 5/5
{B} 4 4/5
{C} 4 4/5
{D} 2 2/5
Bước 2: Tạo ra các tập mục có độ dài 2 bằng cách kết nối các tập mục có độ dài 1, duyệt CSDL giao dịch để xác định độ hỗ trợ cho từng tập mục và loại bỏ các tập mục có độ hỗ trợ nhỏ hơn 2/5 để thu được các tập phổ biến.
Tập mục Số lần xuất hiện Độ hỗ trợ
AB 4 4/5
{AC} 4 4/5
{AD} 2 2/5
{BC} 3 3/5
{BD} 1 1/5
{CD} 2 2/5
Tập mục Số lần xuất hiện Độ hỗ trợ
AB 4 4/5
{AC} 4 4/5
{AD} 2 2/5
{BC} 3 3/5
{CD} 2 2/5
Trong bước 2 này ta chưa cần sử dụng nguyên lý Apriori để tỉa bớt các tập mục không thỏa mãn vì tập con của các tập mục độ dài 2 là những tập mục có độ dài 1 và như đã xét ở bước 1, những tập mục có độ dài 1 đều là tập phổ biến.
Bước 3: Kết nối các tập mục có độ dài 2 để thu được các tập mục có độ dài 3. Trong bước này ta phải sử dụng đến nguyên lý Apriori để loại bỏ bớt những tập mục mà tập con của nó không phải là tập phổ biến.
Sau khi kết nối ta thu được các tập sau đây: {ABC}, {ABD}, {ACD}
Tập {ABD}bị loại bỏ vì tồn tại những tập con ({BD}) không phải là tập phổ biến. Cuối cùng ta còn các tập mục sau đây:
Tập mục Số lần xuất hiện Độ hỗ trợ
ABC 3 3/5
{ACD} 2 2/5
Tập mục Số lần xuất hiện Độ hỗ trợ
ABC 3 3/5
{ACD} 2 2/5
Các tập phổ biến T thu được là:
{A}, {B}, {C}, {D}, {AB}, {AC}, {BC}, {AD}, {CD}, {ABC}, {ACD}.
5.3.2. Xây dựng đồ thị G
Kí hiệu G = (C, E), là một biểu đồ chỉ dẫn bao gồm một tập hợp khác rỗng của tập phổ biếnC.Một tập các cạnh E được xếp thứ tự cặp các thành phần của T, ∀u, v ∈T có một cạnh từ u đến v nếu u ∩ v = u và nếu | v | - | u| = 1 với | u | là kích thước củatập phổ biến u.
Hình Frequent Itemset Graph G.
5.3.3. Sinh ra các luật kết hợp
Để sinh ra các luật kết hợp, cần tách các tập phố biến thành hai tập không giao nhau và tính độ tin cậy cho các luật tương ứng. Luật nào có độ tin cậy vượt ngưỡng minconf (ví dụ: minconf = 70%) sẽ được giữ lại. Ví dụ: xét tập phổ biến {ABC}. Ta có các luật sau đây:
R1: A, B → C
conf(R1) = supp({ABC})/supp({AB}) = 3/4 = 75%.
R2: A, C → B
conf(R2) = supp({ABC })/supp({AC}) = 3/4 = 75%
R3: C, B → A
conf(R3) = supp({ABC })/supp({BC}) = 3/3 = 100%
R4: A → C, B
conf(R4) = supp({ABC })/supp({A}) = 3/5 = 60% (R4 bị loại)
R5: B → A, C
conf(R5) = supp({ABC })/supp({B}) = 3/4 = 75%.
R6: C → A, B
conf(R6) = supp({ABC })/supp({C}) = 3/4 = 75%.
5.3.4. Áp dụng thuật toán DSA
Bước 1: Giả sử chúng ta muốn loại bỏ các luật hạn chế xuất phát từ các tập phổ biến ABC. Bình thường chỉ đơn giản là loại bỏ tập phổ biến ABC (đánh dấu nó để loại bỏ).
Bước 2: Tính các cặp của ABC là một tập hợp con ở mức 1 của đồ thị tập phổ biến G gồm có AB, AC, và BC là chưa được chọn, chọn ngẫu nhiên một cặp để đánh dấu (cặp AC).
Bước 3: Loại bỏ bất kỳ luật có nguồn gốc từ các tập phổ biến AC (tập phổ biến có chứa AC). Trong trường hợp cụ thể này, ABC và ACD phải được gỡ bỏ.
6. Một số thuật toán cải tiến DSA
Kẻ tấn công vẫn có thể suy luận thông tin nhạy cảm từ kết quả thanh lọc của DSA. Ví dụ: Cho CSDL
Đối với mỗi q ∈ Ps (tập phổ biến nhạy cảm) DSA chọn ngẫu nhiên một mẫu con q’ ⊆ q với | q’ | = 2, và tạo ra một tập con F’ của F bằng cách loại bỏ bất kỳ mô hình q’’ ⊇ q từ F. Tuy nhiên, F’ được tạo ra bởi DSA không phải là luôn luôn là một tập mẫu an toàn và nên được chia sẻ. Ví dụ, hãy xem xét các cơ sở dữ liệu giao dịch và các mẫu tuần tự của nó trong hình, giả sử rằng q = abcd là một mẫu riêng, và DSA chọn q’= ab ⊂ q, tập các mẫu phổ biến được loại bỏ là {ab, abc, abd, abcd} ta có F’là tập sau khi lọc các mẫu có chứa ab: {a, b, c, d, ac, ad, bc, bd, cd, acd, bcd}. Tuy nhiên, F’ không phải là một tập mẫu an toàn và chia sẻ. bởi vì theo với nguyên tắc inclusion-exclusion principle:
chúng ta có thể suy ra rằng sup (q) ≥ sup (acd) + sup (bcd) - sup (cd) = 40% ≥ σ.
Để tạo ra một tập mẫu an toàn và được chia sẻ, cần phải chặn tất cả các kênh mà kẻ tấn công có thể suy ra từ các mẫu không riêng. Chúng tôi có định lý sau đây để đánh giá xem F’ là một tập mẫu an toàn được chia sẻ hay không.
Bổ đề 1. Cho q ∈ Ps, nếu ∃q’ ⊂ q ∧ | q’ | ≥ 1 mà F’ |≠ (sup (q’) ≥ σ) thì F’|≠ (sup (q) ≥ σ).
c/m: Giả sử rằng F’ | = (sup (q) ≥ σ), nhưng ∃q’ ⊂ q (| q’ | ≥ 1) và F’ |≠ (Sup (q’) ≥ σ). Từ định lý 1, ta có sup (q’) ≥ sup (q). Do đó F’ | = (Sup (q’) ≥ σ). Điều này mâu thuẫn với giả định rằng F’ |≠ (Sup (q’) ≥ σ). Đpcm.
Bổ đề 2: Cho q ∈ Ps và | q | = 1, nếu ∀p ⊇ q, (p, sup (p)) F’, thì F’|≠ (Sup (q) ≥σ).
c/m: Giả sử q = {x}, trong đó x là một mục. Khi ∀p ⊇ q, (p, sup (p)) F’, một kẻ tấn công không thể nói có tồn tại mục x trong cơ sở dữ liệu ban đầu hay không. Do đó, F’|≠ (Sup (q) ≥ σ).
Định lý 2. Đối với mỗi q ∈ Ps, nếu ∃q’ ⊆ q và | q’| = 1 (nghĩa là, q’ là một mục của q) mà ∀p ⊇ q’, (p, sup (p)) F’, thìF’ là một tập mẫu an toàn và có khả năng chia sẻ.
c/m: Đối với mỗi q ∈ Ps, nó thuộc một trong những trường hợp sau đây:
(1) Khi | q | = 1, ta có q’ = q. Từ bổ đề 2, chúng ta biết F’ |≠ (Sup (q) ≥ σ);
(2) Khi | q | > 1, ta có q’ ⊂ q. Đầu tiên, chúng ta có F’ |≠ (Sup (q’) ≥ σ) từ bổ đề 2: thì F’ | ≠ (Sup (q) ≥ σ) từ bổ đề 1.
Vì vậy, F’ là một tập mẫu an toàn và có thể được chia sẻ.
Dựa vào định lý 2, chúng tôi đề xuất một dạng đặc biệt của mô hình làm sạch, gọi là Item-based Pattern Sanitization, được mô tả như sau: cho kết quả F của khai thác mẫu tuần tự, cho Ps⊂ {p | (p, sup (p)) ∈ F} là tập các mẫu riêng . Đầu tiên, chúng ta khởi tạo F’ = F. Sau đó cho mỗi q ∈ Ps, chúng ta chọn một mục x ∈ q, và loại bỏ tất cả các mẫu tuần tự có chứa item x từ F’. Các item x là gọi là nạn nhân của mẫu tin q.
Định lý 3. Item-based Pattern Sanitization có thể tạo ra một tập mẫu an toàn và chia sẻ.
c/m: Khi cho mỗi q ∈ Ps, có tồn tại mục x ∈ q mà cho bất kỳ mẫu p ⊇{x}, (p, sup (p))F’. chúng ta biết từ định lý 2 là F’ được tạo ra bằng Item-based Pattern Sanitization là một tập mẫu an toàn và chia sẻ.
Tuy nhiên, làm thế nào để tối đa hóa số lượng các mẫu tuần tự F’ được tạo ra bằng Item-based Pattern Sanitization. Chúng tôi gọi vấn đề này là Maximal Item-based Pattern Sanitization.
Định lý 4. Các vấn đề của Maximal Item-based Pattern Sanitization là NP-hard.
c/m: NP-hard tối đa của mẫu dựa trên item làm sạch có thể được chứng minh bằng việc giảm từ vấn đề Np-hard tác dụng vào tập [5]. Do sự hạn chế của không gian, các chi tiết của chứng minh được bỏ qua ở đây.
Thanh lọc các mẫu dựa trên item, chúng ta có hai chiến lược để tạo ra một tập mẫu an toàn và chia sẻ. Một chiến lược là phải thanh lọc mẫu sau khi khai thác mẫu phổ biến, hai là để tích hợp thanh lọc vào khai thác mẫu phổ biến.
6.1. Thanh lọc kết quả khai thác
Một chiến lược để tạo ra một tập mẫu an toàn là lọc mẫu sau khi khai thác mẫu phổ biến. Đầu tiên chúng tôi khai thác cơ sở dữ liệu giao dịch D để có được tập F của tất cả các mẫu phổ biến với sự hỗ trợ của nó. Sau đó tập Ps của tập mẫu riêng được xác định, sau đó chúng tôi thanh lọc F để có được một tập mẫu an toàn và chia sẻ F’. Dựa trên ý tưởng này, chúng tôi trình bày hai thuật toán heuristic, MINSS (thanh lọc độ hỗ trợ tối thiểu) và MINNS (thanh lọc số lượng tối thiểu).
Các chi tiết của MINSS được thể hiện trong hình 2. Đầu tiên MINSS khởi tạo F’ = F. Sau đó cho từng q ∈ Ps, MINSS chọn một mục x ∈ q mà độ hỗ trợ của x là không lớn hơn so với bất kỳ mục khác trong q. Nếu có nhiều mục với cùng độ hỗ trợ tối thiểu, thì một mục được chọn ngẫu nhiên. Cuối cùng, bất kỳ mẫu phổ biến p chứa x sẽ được gỡ bỏ từ F’. Dựa vào định lý 3, F’ tạo ra bởi MINSS là một tập mẫu an toàn và có thể được chia sẻ.
Một thuật toán khác MINNS được mô tả trong hình 3. Đối với mỗi q ∈ Ps, MINNS chọn x ∈ q mà số lượng các mẫu tuần tự có chứa item x là không lớn hơn so với bất kỳ mục khác trong q. Nếu có nhiều mục đáp ứng yêu cầu, một mục được lựa chọn ngẫu nhiên. Bằng cách này, việc lựa chọn một nạn nhân có thể bảo đảm số lượng nhiều hơn của các mẫu trong F’. Dựa trên lý 3, MINNS cũng tạo một tập mẫu an toàn và có thể được chia sẻ F’.
6.2. Lồng ghép thanh lọc vào khai thác
Những phát hiện của nghiên cứu này cho thấy nếu một mẫuq là riêng tư, thì bất kỳ mẫu q’ ⊇ q không nên xuất hiện trong tậpmẫu an toàn và chia sẻ.
Định lý 5. Với q ∈ Ps, nếu F’ là một tập mẫu an toàn và chia sẻ, thì chúng ta có ∀q’ ⊇ q, (q’, sup (q’)) F’.
c/m: Giả sử rằng ∃q’ ⊇ q, (q’, sup (q’)) ∈ F’. Từ định lý 1, ta có sup (q) ≥ sup (q’) ≥ σ. Điều này mâu thuẫn với điều kiện là F’ là một tập mẫu an toàn và chia sẻ.
Theo Định lý 5, chúng tôi trình bày một thuật toán khai thác mẫu phổ biến nhận biết riêng tư được gọi là S-Apriori (Sanitization-Apriori). Chi tiết của nó được đưa ra trong hình 4. S-Apriori được dựa trên Apriori, và tích hợp mô hình làm sạch vào khai thác mẫu phổ biến. Trong hình 4, Lk là tập các mẫu phổ biến với chiều dài k. hàm apriori-gen tạo ra một tập Ck + 1 của ứng viên mẫu phổ biến với chiều dài k + 1 từ Lk.
S-Apriori hoạt động một cách tương tác. Sau khi nó tìm thấy tập Lk các mẫu phổ biến với chiều dài k, chủ sở hữu dữ liệu có thể chỉ định tập Psk của mẫu riêng trong Lk. Đối với bất kỳ q ∈ Ps, S-Apriori di chuyển (q, sup (q)) từ Lk, và thêm q vào Ps. Tuy nhiên, S-Apriori là một thuật toán bảo thủ. Bởi vì nó chỉ loại bỏ các mẫu tin từ Lk, có cơ hội mà kẻ tấn công có thể suy ra các mẫu riêng từ những mẫu không riêng. Do đó, để tạo ra một tập mẫu an toàn và chia sẻ, S-Apriori vẫn cần gọi MINSS hoặc MINNS như là bước cuối cùng của nó.
Trong hình 5, chúng tôi trình bày một thuật toán tích cực hơn, gọi MINSS-Apriori, trong đó kết hợp các ý tưởng của MINSS vào khai thác mẫu tuần tự. Khi một mẫu q xác định là mẫu riêng tư, chúng tôi chọn một mục x ∈ q chẳng hạn rằng độ hỗ trợ của x là không lớn hơn so với bất kỳ mục khác trong q, và loại bỏ mẫu bất kỳ có chứa x từ cả hai Lk và F’. Trong MINSS-Apriori, mô hình thanh lọc hoàn toàn được tích hợp vào khai thác mẫu phổ biến. Khi Lk rỗng, từ định lý 3 F’ là một tập mẫu an toàn và được chia sẻ.
Bên cạnh MINSS-Apriori, chúng tôi cũng trình bày thuật toán khác gọi là Minns-Apriori. Minns-Apriori là tương tự như MINSS-Apriori, nhưng nó kết hợp các ý tưởng của MINNS trong khai thác mẫu phổ biến. Minns-Apriori cũng có thể tạo ra một tập mẫu an toàn và được chia sẻ trực tiếp.
7. Kết luận
Bởi vì sự tồn tại của các kênh suy luận, chỉ loại bỏ mẫu nhạy cảm là không đủ để bảo vệ chúngkhi chia sẻ các kết quả của khai thác mẫu phổ biến. Những đóng góp của chúng tôi trong bài viết này có thể được tóm tắt như sau: một thuật toán Downright Sanitizing Algorithm (DSA). DSA chặn một số suy luận kênh để đảm bảo rằng một kẻ thù không thể tái tạo lại luật hạn chế từ không hạn chế. Ngoài ra, DSA làm giảm các yếu tố tác động bên trong quá trình làm sạch. Thí nghiệm của chúng tôi đã chứng minh rằng DSA là một cách tiếp cận đầy hứa hẹn để bảo vệ kiến thức nhạy cảm trước khi chia sẻ luật kết hợp. Hướng này bao gồm các thước đo để đánh giá hiệu quả của các quy tắc quá trình làm sạch. Đóng góp khác là một nguyên tắc phân loại các thuật toán thanh lọc hiện có. Chúng tôi cũng giới thiệu một nguyên tắc phân loại của các cuộc tấn công chống lại các kiến thức nhạy cảm.
Đối với nghiên cứu trong tương lai, chúng tôi sẽ nghiên cứu khả năng phát triển các thuật toán hiệu quả hơn. Chúng tôi cũng kế hoạch mở rộng nghiên cứu cho các nhiệm vụ khác của khai thác dữ liệu, như phân loại và phân nhóm, vv.
Nguồn: Sharecode.vn