Solution UVA: 324 - Factorial Frequencies

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss324 - Factorial Frequencies	Accepted	Python	0.020	0.000	3662	1 mins ago

Suggest:

- BigNumber (so we should code python to easy)

def f(n):

    if n == 0:

        return 1

    else:

        return n * f(n - 1)

while True:

    n = int(input())

   

    if n == 0:

        break

   

    cnt = {'0': 0, '1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0, '8': 0, '9': 0}

    for c in str(f(n)):

        cnt[c] += 1

   

    print(f"{n}! --")

   

    print(f"   ({0}){cnt[str(0)]:>5}", end="")

    for i in range(1, 5):

        print(f"    ({i}){cnt[str(i)]:>5}", end="")

   

    print()

   

    print(f"   ({5}){cnt[str(5)]:>5}", end="")

    for i in range(6, 10):

        print(f"    ({i}){cnt[str(i)]:>5}", end="")

   

    print()

Rút gọn tập thuộc tính (Lý thuyết tập thô)

1. Nếu (cột cuối) của hàng này = hàng kia (vd yes = yes thì ra lamda)

Ngược lại kết quả là các thuộc tính khác nhau của 2 hàng

2. Hàm phân biệt là các giá trị của giao (AND) của tất cả các ô và hợp (OR) của của mỗi giá trị trong ô 

3. Rút gọn hàm phân biệt theo luật hút P && (P || Q) = P 

VD1

VD2

VD3

NOTE: b hoặc d GIAO VỚI a hoặc d => Chỉ còn lại d

VD4

Dicision Tree (Thuật toán phân lớp)

Ví dụ 1:  xây dựng cây quyết định từ bảng sau:

Đáp án

Ví dụ 2:

Giải

Áp dụng các công thức sau:

Entropy : E = SUM(-pi * log2(pi))

Gain : G = E - SUM(Si/S * Ei)

 

Find Root

9+, 5- E = 0.94
Age	Income	Student	Credit_rating
Youth 2+, 3- E = 0.97   Middle_aged 4+,0- E = 0   Senior 3+, 2- E = 0.97   G= 0.94 - 5/14 * 0.94 - 0 - 5/14 * 0.97 = 0.247 (max)	G = 0.029	G = 0.152	G = 0.048

=> Root is Age (Youth, Middle_aged, Senior)

 

 

 

 

Find node for brand Youth (brands: youth)

2+, 3- E = 0.97
Income	Student	Credit_rating
High 0+, 2- E = 0   Medium 1+, 1- E= 1   Low 1+, 0- E = 0   G = 0.97 - 2/5 * 1  = 0.57	G = 0.971 (max)	G = 0.02

=> Brand Youth have node is Student (no, yes)

 

Find node for brand no (brands: youth - no)

0, 3- E = 0

=> Brand no have leaf is NO

 

Find node for brand yes (brands: youth - yes)

2+, 0- E = 0

=> Brand yes have leaf is YES

 

 

Find node for brand Middle_aged (brands: middle_aged)

4+, 0- E = 0

=> Brand Middle_aged have leaf is YES

 

Find node for brand Senior (brands: senior) //i forget student, you need add student

3+, 2- E = 0.97
Income	Credit_rating
G = 0.0202	G = 0.971 (max)

=> Brand Senior have node is Credit_rating (fair, excellent)

 

Find node for brand fair (brands: senior - fair)

3+, 0- E = 0

=> Brand fair have leaf is YES

 

Find node for brand excellent (brands: senior - excellent)

0+, 2- E = 0

=> Brand excellent have leaf is NO

 

Tree:

Root			Age
Brand	Youth		Middle_aged	Senior
Node	Student			Credit_rating
Brand	Yes	No		Fair	Excellent
Leaf	YES	NO	YES	YES	NO

 

Tôi quên sinh viên, bạn cần sinh viên Caculator

Naive Bayes (Thuật toán phân lớp)

 

B1: Tìm P(c1 | x)  và P(c2 | x) //giả sử cái đầu lớn hơn => X thuộc C1

B2: Tìm P(c1) và P(x | c1) tương tự với c2 //vì P(c | x) = P(c) * P(x | c)

B3: Tìm P(x1 | c1) * P(x2 | c1) tương tự với c2 //vì x = x1 + x2

Giải 

x = (A1 = 1, A2 = 2)

Ta có P(c1 | x) = P(c1) * P(x | c1)

            P(c1) = 3/5

            P(x | c1) = P(A1 = 1 | c1) * P(A2 = 1 | c1) = 1/3 * 1/3 = 1/9

    => P(c1 | x) = 3/5 * 1/9 = 1/15

Ta có P(c2 | x) = P(c2) * P(x | c2)

            P(c2) = 2/5

            P(x | c2) = P(A1 = 1 | c2) * P(A2 = 1 | c2) = 1/2 * 1/2 = 1/4

    => P(c2 | x) = 2/5 * 1/4 = 1/10

Vì P(c1 | x) = 1/15 < P(c2 | x) = 1/10 nên X thuộc lớp c2   

Giải

Ta có P(+|X) = P(+) * P(X|+)

        P(+) = 5/10 = 1/2

        P(X|+) = P(A=0|+) * P(B=1|+) * P(C=0|+) 

                   = 2/5 * 1/5 * 1/5 = 2/15

=> P(+|X) = 1/2 * 2/15 = 1/125

Ta có P(-|X) = P(-) * P(X|-)

        P(-) = 5/10 = 1/2

        P(X|-) = P(A=0|-) * P(B=1|-) * P(C=0|-) 

                   = 3/5 * 2/5 * 0/5 = 0

=> P(-|X) = 1/2 * 0/15 = 0

Vì P(+ | x) = 1/125 > P(- | x) = 0 nên X thuộc lớp +   

Apriopi + FPGrowth Algorithm (Khai phá luật kết hợp)

 

Thuật toán tìm tập phổ biến:

B1: Đếm số lần xuất hiện của mỗi item trong db (có thể dùng map c++)

B2: Loại bỏ item (trong map) có số lần xuất hiện nhỏ hơn min_sup (ví dụ loại bỏ item có số lần xuất hiện<4)

B3: Xây dựng itemset gồm 2 phần tử từ map bằng for(i, 1, n-1) và for(j, i+1, n) 

B4: Đếm số lần xuất hiên của mỗi itemset trong db (có thể dùng map2 c++)

B5: Loại bỏ những itemset có số lần xuất hiện nhỏ hơn min_sup

B6: Xây dựng itemset gồm 3 phần tử từ map bằng for(i, 1, n-1) và for(j, i+1, n) 

B7: Lặp lại cho đến khi mapX chỉ còn 1 phần tử

Trong Apriori-gen, tập cha bị loại bỏ khi tồn tại một tập con trong tập cha không xuất hiện (ví dụ hình dưới)

THUẬT TOÁN FP Growth

B1: Tính tần suất 

B2: Sắp xếp tần suất giảm dần + loại bỏ những tần suất < minsup

B3: Tạo bảng item phổ biến từ CSDL và tần suất trên

B4: Vẽ cây fp tree

B5: Tạo bảng :

+Cột item: sắp xếp tăng dần tần suất

+Cơ sở mẫu điều kiên: lấy key từ nút [cha, root) và value là giá trị (số lần vẽ) của node con

+ FP tree dk: gộp các cơ sở mẫu đk và chỉ chọn > min_sup

+ Tập thường xuyên: item, sinh các tổ hợp FPtreedk + item

Sinh các luật kết hợp 

Độ đo LIFT:

ĐỘ đo Leverage

    

TLTK: