import itertools
ATTRIBUTES = [
"Alt", "Bar", "Fri", "Hun", "Pat",
"Price", "Rain", "Res", "Type", "Est"
]
DOMAINS = {
"Alt": ["Yes", "No"],
"Bar": ["Yes", "No"],
"Fri": ["Yes", "No"],
"Hun": ["Yes", "No"],
"Pat": ["None", "Some", "Full"],
"Price": ["P1", "P2", "P3"],
"Rain": ["Yes", "No"],
"Res": ["Yes", "No"],
"Type": ["French", "Italian", "Thai", "Burger"],
"Est": ["0-10", "10-30", "30-60", ">60"]
}
RESTAURANT_DATA = [
(("Yes", "No", "No", "Yes", "Some", "P3", "No", "Yes", "French", "0-10"), True),
(("Yes", "No", "No", "Yes", "Full", "P1", "No", "No", "Thai", "30-60"), False),
(("No", "Yes", "No", "No", "Some", "P1", "No", "No", "Burger", "0-10"), True),
(("Yes", "No", "Yes", "Yes", "Full", "P1", "Yes", "No", "Thai", "10-30"), True),
(("Yes", "No", "Yes", "No", "Full", "P3", "No", "Yes", "French", ">60"), False),
(("No", "Yes", "No", "Yes", "Some", "P2", "Yes", "Yes", "Italian", "0-10"), True),
(("No", "Yes", "No", "No", "None", "P1", "Yes", "No", "Burger", "0-10"), False),
(("No", "No", "No", "Yes", "Some", "P2", "Yes", "Yes", "Thai", "0-10"), True),
(("No", "Yes", "Yes", "No", "Full", "P1", "Yes", "No", "Burger", ">60"), False),
(("Yes", "Yes", "Yes", "Yes", "Full", "P3", "No", "Yes", "Italian", "10-30"), False),
(("No", "No", "No", "No", "None", "P1", "No", "No", "Thai", "0-10"), False),
(("Yes", "Yes", "Yes", "Yes", "Full", "P1", "No", "No", "Burger", "30-60"), True),
]
def predict_rule(rule, x):
"""Conjunctive rule တစ်ခုက နမူနာ x ကို True ဟု ခန့်မှန်းခြင်း ရှိမရှိ စစ်ဆေးခြင်း"""
return all(r_val == "?" or r_val == x_val for r_val, x_val in zip(rule, x))
def rule_more_general_or_equal(r1, r2):
"""r1 >=_g r2 ဖြစ်မဖြစ် စစ်ဆေးခြင်း"""
return all(c1 == "?" or c1 == c2 for c1, c2 in zip(r1, r2))
def minimal_generalization_rule(r, x):
"""Rule r ကို နမူနာ x ပါဝင်လာအောင် အနည်းဆုံး ယေဘုယျပြုခြင်း"""
return tuple(r_val if r_val == x_val else "?" for r_val, x_val in zip(r, x))
def immediate_specializations_rule(r, x):
"""Rule r ကို နမူနာ x မပါဝင်အောင် တိုက်ရိုက် အထူးပြုချက်များ ဖန်တီးခြင်း"""
specs = set()
for i, attr in enumerate(ATTRIBUTES):
if r[i] == "?":
for val in DOMAINS[attr]:
if val != x[i]:
new_r = list(r)
new_r[i] = val
specs.add(tuple(new_r))
return specs
def simplify_dnf(h):
"""DNF အတွင်း အခြား rule တစ်ခုက လွှမ်းခြုံပြီးသား ဖြစ်နေသည့် ပိုလျှံနေသော rule များကို ဖယ်ရှားခြင်း"""
rules = list(h)
minimal_rules = set()
for i, r1 in enumerate(rules):
if not any(
i != j and rule_more_general_or_equal(r2, r1)
for j, r2 in enumerate(rules)
):
minimal_rules.add(r1)
return frozenset(minimal_rules)
def predict_dnf(h, x):
"""k-DNF အဆိုပြုချက် h က နမူနာ x ကို True ဟု ခန့်မှန်းခြင်း ရှိမရှိ စစ်ဆေးခြင်း"""
return any(predict_rule(r, x) for r in h)
def dnf_more_general_or_equal(h1, h2):
"""h1 >=_g h2 (h2 ထဲရှိ disjunct တိုင်းကို h1 ထဲရှိ disjunct တစ်ခုခုက လွှမ်းခြုံနိုင်ခြင်း)"""
return all(
any(rule_more_general_or_equal(r1, r2) for r1 in h1)
for r2 in h2
)
def dnf_strictly_more_general(h1, h2):
return h1 != h2 and dnf_more_general_or_equal(h1, h2)
def immediate_generalizations_dnf(s, x, k):
"""
False negative ဖြစ်နေသော k-DNF အဆိုပြုချက် s ကို နမူနာ x ပါဝင်အောင်
နည်းလမ်း ၂ သွယ်ဖြင့် ယေဘုယျပြုခြင်း:
(၁) ရှိပြီးသား disjunct တစ်ခုကို ယေဘုယျပြုခြင်း
(၂) အရေအတွက် k မပြည့်သေးပါက နမူနာ x အတွက် disjunct အသစ်တစ်ခု ထပ်ပေါင်းထည့်ခြင်း
"""
gens = set()
for r in s:
r_gen = minimal_generalization_rule(r, x)
candidate = simplify_dnf((s - {r}) | {r_gen})
if len(candidate) <= k:
gens.add(candidate)
if len(s) < k:
candidate = simplify_dnf(s | {x})
if len(candidate) <= k:
gens.add(candidate)
return gens
def immediate_specializations_dnf(g, x, k):
"""
False positive ဖြစ်နေသော k-DNF အဆိုပြုချက် g ကို နမူနာ x မပါဝင်အောင် အထူးပြုခြင်း
"""
specs = set()
matching_rules = [r for r in g if predict_rule(r, x)]
non_matching_rules = frozenset(r for r in g if not predict_rule(r, x))
per_rule_specs = [list(immediate_specializations_rule(r, x)) for r in matching_rules]
for combo in itertools.product(*per_rule_specs):
candidate = simplify_dnf(non_matching_rules | frozenset(combo))
if 1 <= len(candidate) <= k:
specs.add(candidate)
if len(g) == 1 and k >= 2:
single_specs = list(immediate_specializations_rule(matching_rules[0], x))
for r_a, r_b in itertools.combinations(single_specs, 2):
if not rule_more_general_or_equal(r_a, r_b) and not rule_more_general_or_equal(r_b, r_a):
specs.add(frozenset({r_a, r_b}))
return specs
def k_dnf_version_space_update(S, G, x, y, k=2):
S = set(S)
G = set(G)
if y is True:
G = {g for g in G if predict_dnf(g, x)}
next_S = set()
for s in S:
if predict_dnf(s, x):
next_S.add(s)
else:
for s_gen in immediate_generalizations_dnf(s, x, k):
if any(dnf_more_general_or_equal(g, s_gen) for g in G):
next_S.add(s_gen)
S = {
s for s in next_S
if not any(dnf_strictly_more_general(s, other_s) for other_s in next_S)
}
else:
S = {s for s in S if not predict_dnf(s, x)}
next_G = set()
for g in G:
if not predict_dnf(g, x):
next_G.add(g)
else:
for g_spec in immediate_specializations_dnf(g, x, k):
if any(dnf_more_general_or_equal(g_spec, s) for s in S):
next_G.add(g_spec)
G = {
g for g in next_G
if not any(dnf_strictly_more_general(other_g, g) for other_g in next_G)
}
return S, G
def format_dnf(h):
"""DNF အဆိုပြုချက်ကို လူဖတ်ရလွယ်ကူအောင် စာသားပြောင်းပေးခြင်း"""
if not h:
return "∅ (မည်သည့်နမူနာကိုမျှ လက်မခံ)"
parts = []
for r in sorted(h):
conds = [f"{attr}={val}" for attr, val in zip(ATTRIBUTES, r) if val != "?"]
parts.append("(" + (" ∧ ".join(conds) if conds else "TRUE") + ")")
return " ∨ ".join(parts)
def k_dnf_version_space_learning(examples, k=2, verbose=True):
n = len(ATTRIBUTES)
S = {frozenset()}
G = {frozenset({tuple(["?"] * n)})}
for idx, (x, y) in enumerate(examples, start=1):
S, G = k_dnf_version_space_update(S, G, x, y, k=k)
if verbose:
print(f"နမူနာ X{idx:02d} (WillWait={str(y):5s}) ပြီးနောက် -> |S| = {len(S)}, |G| = {len(G)}")
if not S or not G:
print(">>> Version Space ပြိုလဲသွားပါပြီ!")
return None, None, "COLLAPSED"
if len(S) == 1 and len(G) == 1 and S == G:
print(">>> တစ်ခုတည်းသော အဖြေအဆိုပြုချက် ရရှိပါပြီ!")
return S, G, "UNIQUE"
return S, G, "MULTIPLE"
def classify_dnf_version_space(S, G, new_x):
"""ကျန်ရှိနေသော S နှင့် G ဘောင်အဖွဲ့ဝင်များဖြင့် နမူနာအသစ်ကို ခန့်မှန်းခြင်း"""
boundary = list(S.union(G))
votes = [predict_dnf(h, new_x) for h in boundary]
true_count = sum(votes)
false_count = len(votes) - true_count
if true_count == len(votes):
return True, f"အားလုံး တညီတည်း သဘောတူသည် ({true_count}/{len(votes)})"
elif false_count == len(votes):
return False, f"အားလုံး တညီတည်း သဘောတူသည် ({false_count}/{len(votes)})"
else:
return (true_count > false_count), f"အများစုမဲစနစ် (True: {true_count}, False: {false_count})"
if __name__ == "__main__":
S_final, G_final, status = k_dnf_version_space_learning(RESTAURANT_DATA, k=2, verbose=True)
print("\n========================================================")
print(f"နောက်ဆုံးရလဒ် အခြေအနေ: {status}")
print("========================================================")
print("\n[S နယ်နိမိတ် အဖွဲ့ဝင် ဥပမာ]")
for s in list(S_final)[:2]:
print(" S:", format_dnf(s))
print("\n[G နယ်နိမိတ် အဖွဲ့ဝင် ဥပမာများ]")
for g in list(G_final)[:3]:
print(" G:", format_dnf(g))
s_rep = next(iter(S_final))
g_rep = next(iter(G_final))
s_acc = sum(predict_dnf(s_rep, x) == y for x, y in RESTAURANT_DATA)
g_acc = sum(predict_dnf(g_rep, x) == y for x, y in RESTAURANT_DATA)
print(f"\nလေ့ကျင့်ရေး ဒေတာ ၁၂ ခုလုံးအပေါ် မှန်ကန်မှု: S = {s_acc}/12, G = {g_acc}/12")
unseen_x = ("Yes", "No", "Yes", "Yes", "Full", "P1", "No", "No", "Thai", "10-30")
pred, detail = classify_dnf_version_space(S_final, G_final, unseen_x)
print(f"\nနမူနာအသစ် {unseen_x} အတွက် ခန့်မှန်းချက် -> {pred} ({detail})")