A-priori算法是一種先驗算法,經常用于數據挖掘里面尋找關聯的子集。我們給定一個數據的集合{{1,2,3},{1,2,3,5,4}…{11,19,28}},需要尋找同時出現次數超過s次的k元集合(x1,x2...xk).其基本核心思路如下:

1：首先尋找出現次數超過s次的一元集合,由于這樣的集合不會超過元素的總數,一般可以直接計算出來,利用字典(或其他hash結構)可以在O(N)的復雜度情況下得到解。

2：假定我們已經獲取了k-1元集合的解,那么容易看出,k元集合里面一定含有k-1元的解，否則不可能出現超過s次。那么我們利用每一個集合對應的k-1元的解加上1元集合的解來構造該集合對應的k元候選集合。例如:如果第三個集合的2元解是{(2,5),(2,3),(3,5)},1元解是{(1),(4),(2),(3),(5)},那么候選的三元解則是{(2,3,4),(3,4,5),(2,5,4),(1,2,5)…(1,3,5)}。然后再去進行計算,檢測是否確實出現了s次,過濾掉不滿足的候選。

3:coding細節有這樣幾個需要注意:

[0]由于構造集合時沒有順序,所以我們必須要對集合排序,否則(1,2)與(2,1)對應的是同一個集合,但是確會輸出兩次。

[1]選取的單個元素有可能已經在k-1元的集合里面了,這時候就直接跳過這個組合。

[2]需要將原始數據復制一份,因為循環過程會改變原始的數據。

4:假設一共有n個集合,每個集合有m元素,我們直接暴力統計2元的解的復雜度是:

m22?n，而過濾之后再統計的復雜度是:m?n+∑si，其中si是代表過濾之后剩下的候選集合個數。很顯然過濾之后的元素個數要比nm2得多.更不要說3元,4元直到m2元的集合了。

def A_pri(raw_data,s,k):def get_singlgeitems():counts = {}for items in raw_data:for item in items:if item in counts:counts[item] += 1else:counts[item] = 1counts_filterd = [key for (key,val) in counts.items() if val >= s]return counts_filterddef select(backet,raw_backet):new_backet = set()for tuple_items in backet:for item in raw_backet:if item not in single_items or item in tuple_items :continuetmp = tuple_items+(item,)new_backet.add(tuple(sorted(tmp)))return new_backetdef Tuple(data):tuple_data = []for items in data:tuple_data.append(set([(item,) for item in items]))return tuple_datadef Set(data):set_data = set()for items in data:for item in items:set_data.add(tuple(sorted(item)))return set_datan = len(raw_data)data = Tuple(raw_data)single_items = get_singlgeitems()for size in range(2,k+1):for i in range(n):data[i] = select(data[i],raw_data[i])for first in range(n):items_1 = data[first].copy()for tuples in items_1:count = 0for items_2 in data:count += 1 if tuples in items_2 else 0if count < s:data[first].remove(tuples)result = Set(data)print(result) A_pri([[1,2,3,4],[1,2],[2,3,4],[1,2,4],[2,3],[3,4]],2,3)

總結

以上是生活随笔為你收集整理的A-priori算法的简单实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。