TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO BÀI TẬP LỚN HỆ CHUYÊN GIA
ĐỀ TÀI: Xây dựng hệ chuyên gia nhận dạng con vật
Gv hướng dẫn: TS. Phạm Văn Hà
Sinh viên thực hiện:
1. Lê Thanh Nghị
2. Đỗ Văn Lưỡng
Lớp: KHMT2 – K5
Hà Nội – 12/08/2013
Nhóm 27 – Lớp KHMT2-K5
Mục lục
Phân công công việc
STT Họ tên Công việc
1 Lê Thanh Nghị Tìm hiểu thuật toán suy diễn tiến, viết báo cáo
2 Đỗ Văn Lưỡng Tìm hiểu các thuật toán giải quyết dư thừa dữ liệu
2
Nhóm 27 – Lớp KHMT2-K5
I. Phân tích bài toán
1. Mục đích
Áp dụng các kiến thức đã học, lập trình một chương trình mô phỏng, dùng
hệ chuyên gia. Hệ nhận dạng một số động vật trong bài này sử dụng cơ sở tri
thức người dùng dựa trên các sự kiện người dùng đưa vào. Hệ chuyên gia sẽ sử
dụng một động cơ suy diễn thích hợp để kết hợp các sự kiện người dùng đưa
vào đó với các luật đã được xây dựng sẵn để tìm được mục tiêu thích hợp.
2. Cách thức thực hiện
- Ngôn ngữ lựa chọn: C#
- Sử dụng cơ sở dữ liệu bao gồm tập các sự kiện, các luật, lưu trữ trong
các tệp .txt.
- Sử dụng 3 giao diện: giao diện chính chạy chương trình (frmMain),
giao diện trình bày (frmExplain), giao diện quản lý tập sự kiện, tập luật

(frmManagerRule)
- Sử dụng các thuật toán như suy diễn tiến, thuật toán tìm bao đóng, loại
bỏ luật thừa, sự kiện thừa.
II. Thiết kế chương trình
1. Kiến trúc chương trình:
Một phiên làm việc gồm:
- Mục tiêu cần giải quyết
- Người dùng chọn các đặc điểm
- Đưa ra kết quả.
2. Mô hình suy diễn
- Cách lựa chọn mục tiêu:
3
Nhóm 27 – Lớp KHMT2-K5
Hệ nhận dạng động vật đưa ra kết luận đó là động vật gì dựa trên các đặc
điểm (thuộc tính) nổi bật của nó. (Các thuộc tính này được xây dựng sẵn
trong phần cơ sở tri thức).
Đối với mỗi thuộc tính, hệ sẽ ghi nhận giá trị có hay không có thuộc tính
đó thông qua các lựa chọn của người dùng, và đưa ra kết luận về con vật
đó dựa trên các đặc tính mà nó có.
Hệ sử dụng suy diễn tiến dựa trên các luật để tìm được đáp án.
- Biểu diễn tri thức:
Tri thức của hệ nhận dạng động vật gồm tập các sự kiện (gồm các đặc điểm
của động vật), tập luật
Các sự kiện được biểu diễn trong file text Node.txt.
Các luật được biểu diễn trong file Rule.txt gồm 2 mệnh đề mỗi luật, dạng
luật dẫn If….then.
- Cách thức suy diễn:
Hoạt động của hệ là đi chứng minh đó là một con vật nào đó dựa trên cơ sở
tri thức và sự lựa chọn các đặc điểm con vật của người dùng.
3. Cơ sở tri thức:

Thu thập tri thức về một số đặc điểm riêng để phân loại động vật dựa trên
phân nhóm động vật trong khoa học sinh học.
4. Các thuật toán được sử dụng
a. Thuật toán suy diễn tiến
Input:
- Tập các mệnh đề đã cho GT={gt
1
, gt
2
, gt
3
, gt
4
,… gt
m
}.
- Tập các luật R = { r
1
, r
2
, r
3
, r
4
,…, r
m
} với r
i
= p
1

^…^ p
n
 q với i = 1, , n.
- Tập KL = { q
1
,…, q
k
}.
Output:
- Thông báo thành công nếu đều được suy ra từ GT và tập luật R
Phương pháp:/**/
/*TG là tập các sự kiện(mệnh đề) đúng cho đến thời điểm đang xét*/
void SDT()
{
4
Nhóm 27 – Lớp KHMT2-K5
TG = GT
/* SAT là tập hợp các luật có dạng p
1
^…^ p
n
 q, sao
cho */
SAT = Loc(R, TG)
while (KL ₵ TG) and (SAT ≠ Ø) do
{
/*Lấy luật r trong SAT*/
/*Giả sử: r
i
= p

1
^…^ p
n
 q */
/*Bổ sung vế phải vào TG*/
/*Loại đi luật đã áp dụng*/
/*Tính lại tập SAT*/
}
If then exit (“Thành công”)
Else exit (“Không thành công”)
}
b. Thuật toán tìm bao đóng
Input: Tập thuộc tính X cần tính bao đóng trên lược đồ quan hệ R=(U,F).
Đầu ra: Tập thuộc tính X+
Phương pháp: /* Kiểm tra lần lượt từng phụ thuộc hàm  =
α→β
, nếu
α

⊆
X
+
thì kết nạp vế phải (tức
β
) vào vào X
+
:
X
+
:= X

+

∪β
.
Lặp lại cho đến khi nào X
+
= Const.*/
void TimBaoDong()
{
flag = True;
X
+
= X;
while Flag
{
Flag = False;
For mỗi fi = α→β
{
If α ⊆ X
+

5
Nhóm 27 – Lớp KHMT2-K5
{
X
+
= X
+
∪ β;
Flag = True;

}
}
}
}
c. Thuật toán tìm phủ tối thiểu
Input : Lược đồ quan hệ ban đầu Q và tập phụ thuộc hàm F, số lượng phụ
thuộc hàm trong F là m.
Output : Tập phụ thuộc hàm tối thiểu của F
Bước 1 :
Tách vế phải mỗi phụ thuộc hàm trong F sao cho vế
phải của mỗi phụ thuộc hàm chỉ chứa một thuộc tính
(điều này luôn thực hiện được do bổ đề trên)
∀ f: X → Y ∈ F
∀ A ∈ Y
g = X → A F = F ∪ g
m = m + 1
Bước 2 : Tìm tập phụ thuộc hàm đầy đủ bằng cách loại
bỏ các thuộc tính dư thừa ở vế trái của từng phụ
thuộc hàm.
∀ f X → A ∈ F
∀ B ∈ X
X' =X − B
If (X'→ A ∈ F+) X = X'
Chú ý :
Việc tìm tất cả các tập X' ⊆ X theo thuật toán trên
hoàn toàn thay thế được việc tìm X' cách tìm các tập
con của X.
Bước 3 : Loại bỏ các phụ thuộc hàm dư thừa trong F.
∀ f ∈ F
G = F − f {loại f ra khỏi F. và lưu { F − f} vào G }

If (F + = G+ ) {gọi thủ tục kiểm tra F, G tương đương
ở dưới}
6
Nhóm 27 – Lớp KHMT2-K5
III. Cài đặt chương trình
1. Thuật toán suy diễn tiến
/// <summary>
/// Thuật toán suy diễn tiến
/// </summary>
private void ForwardReasoning()
{
bool flag = false;
foreach (var item in listRule)
{
Stack THOA = new Stack();
ArrayList VET = new ArrayList();
string TGIAN = txtDacDiem.Text.Trim();
string KL = ((Rule)item).clauseRight;
if (KL.ToLower()[0] != 'b') continue;
FindTHOA(TGIAN, THOA, VET);
while (THOA.Count > 0 && !CheckedOfClause(TGIAN, KL))
{
Rule rule = (Rule)THOA.Pop();
VET.Add(rule);
TGIAN += "^" + rule.clauseRight;
if (CheckedOfClause(TGIAN, KL))
{
txtKetQua.Text = "Đây là " +
Common.ReadNameToDesc(KL) +"!";
flag = true;

break;
}
FindTHOA(TGIAN, THOA, VET);
}
temVET = VET;
}
if (!flag) txtKetQua.Text = "Không tìm thấy con vật phù hợp!";
}
7
Nhóm 27 – Lớp KHMT2-K5
2. Thuật toán giải thích lời khuyên khi người dùng nhấn nút “Giải thích”
protected void LoadExplain()
{
ArrayList listNode = new ArrayList();
LoadListNode(listNode);
if (VET == null) return;
string mes = "Quá trình suy diễn:\r\n";
string exp = "Giải thích: \r\n";
foreach (var itemV in VET)
{
Rule r = (Rule)itemV;
mes += "Theo luật "+r.nameRule +": "+ r.clauseLeft + "=>"
+ r.clauseRight + " thì:\r\n";
mes += Common.RuleToExplain(r) + "\r\n";
}
txtExplain.Text = mes;
}
public static string RuleToExplain(Rule rule)
{
string[] s = rule.clauseLeft.Split('^');

string left = "";
for (int i = 0; i < s.Length; i++)
{
if (i < s.Length - 1) left += ReadNameToDesc(s[i]) + " và
";
else left += ReadNameToDesc(s[i]);
}
return left + " => " + ReadNameToDesc(rule.clauseRight);
}
8
Nhóm 27 – Lớp KHMT2-K5
3. Thuật toán tìm bao đóng
public static string timBaoDong(string baoDong, string[] R)
{
string result = baoDong;
bool flag = false;
bool[] flagArray = new bool[R.Length];
for (int i = 0; i < R.Length; i++)
{
flagArray[i] = false;
}
int count = 0;
bool flag2 = true;
while (!flag)
{
if (flagArray[count])
{
if (count == (R.Length - 1) && flag2)
{
break;

}
count++;
if (count == R.Length) { count = 0; flag2 = true; }

continue;
}
string s = R[count].Substring(0, R[count].IndexOf('='));
if (match(result, s))
{
flag2 = false;
flagArray[count] = true;
s = R[count].Substring(R[count].IndexOf('>') + 1);
if (!match(result, s))
{
result += "^" + s;
}
9
Nhóm 27 – Lớp KHMT2-K5
}
count++;
if (count == R.Length && flag2)
{
break;
}
if (count == R.Length)
{
flag2 = true;
count = 0;
}
flag = true;

foreach (bool item in flagArray)
{
if (!item)
{
flag = false;
break;
}
}
}
return result.ToString();
}
4. Thuật toán tìm luật dư thừa
private void bttRemove_Click(object sender, EventArgs e)
{
ArrayList arr = Common.GetList();
ArrayList DuThua = new ArrayList();
foreach (var item in arr)
{
string[] split = item.ToString().Split(':');
string clauseLeft =
split[1].Substring(0,split[1].IndexOf('='));
string clauseRight =
split[1].Substring(split[1].IndexOf('>')+1);
10
Nhóm 27 – Lớp KHMT2-K5
string[] strList = Common.ArrayListToArrayString(arr,
item.ToString());
string baodong = Common.timBaoDong(clauseLeft, strList);
if (Common.match(baodong, clauseRight))
DuThua.Add(item);

}
string ms = "Các luật dư thừa:\r\n";
foreach (var item in DuThua)
{
ms += item.ToString() + "\r\n";
}
if (MessageBox.Show(ms, "Thông báo",
MessageBoxButtons.OKCancel, MessageBoxIcon.Warning) ==
System.Windows.Forms.DialogResult.OK)
{
for (int i = 0; i < lstbDSLuat.Items.Count; i++)
{
if (ms.Contains(lstbDSLuat.Items[i].ToString()))
{
lstbDSLuat.Items.RemoveAt(i );
}
}
}
Common.WriteTextToFile("Rule.txt", lstbDSLuat);
Common.LoadFileToListBox("Rule.txt",lstbDSLuat);
}
5. Thuật toán tìm sự kiện dư thừa
private void bttSuKienDuThua_Click(object sender, EventArgs e)
{
if (lstbDSLuat.SelectedIndex == -1)
{
MessageBox.Show("Bạn hãy chọn 1 luật", "Thông báo");
return;
}
ArrayList arr = Common.GetList();

11
Nhóm 27 – Lớp KHMT2-K5
string[] R = Common.ArrayListToArrayString(arr);
string re = lstbDSLuat.SelectedItem.ToString().Split(':')
[1].Split('=')[0];
string[] ev = re.Split('^');
ArrayList Events = new ArrayList();
foreach (var item in ev)
{
string bd = Common.timBaoDong(Common.RemoveEvent(re,
item), R);
if (Common.match(bd, item))
Events.Add(item);
}
if (Events.Count == 0)
{
MessageBox.Show("Không có sự kiện nào dư thừa","Thông
báo");
return;
}
string ms = "Các sự kiện dư thừa:\r\n";
foreach (var item in Events)
{
ms += item + "\r\n";
}
ms += "Bạn có muốn loại bỏ các sự kiện dư thừa ra khỏi
luật:\r\n"+lstbDSLuat.SelectedItem;
string te = lstbDSLuat.SelectedItem.ToString();
if (MessageBox.Show(ms, "Thông báo",
MessageBoxButtons.OKCancel, MessageBoxIcon.Warning) ==

System.Windows.Forms.DialogResult.OK)
{
foreach (var item in Events)
{
string a = te.Substring(0, te.IndexOf(':') + 1) +
Common.RemoveEvent(re, item.ToString()) + te.Substring(te.IndexOf('='));
lstbDSLuat.Items[lstbDSLuat.SelectedIndex] = a;
}
12
Nhóm 27 – Lớp KHMT2-K5
Common.WriteTextToFile("Rule.txt", lstbDSLuat);
}
}
13
Nhóm 27 – Lớp KHMT2-K5
IV. Demo chương trình
1. Giao diện chính
2. Giao diện quản lý sự kiện
14
Nhóm 27 – Lớp KHMT2-K5
3. Giao diện quản lý tập luật
15
Nhóm 27 – Lớp KHMT2-K5
TÀI LIỆU THAM KHẢO
1. Giáo trình Hệ Chuyên Gia
2. Các hệ cơ sở tri thức.
3. />4. />16