ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
__
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Huỳnh Văn Trận
Dương Thị Phương Mai
KHÁM PHÁ LUẬT TRÊN HƯỚNG TIẾP CẬN TẬP THÔ
Đồ Án Môn Học
Toán Cho Khoa Học Máy Tính
TP HỒ CHÍ MINH – Năm 2014
ĐẠI HỌC QUỐC GIA TP.HỒ CHÍ MINH
__
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
Huỳnh Văn Trận
Dương Thị Phương Mai
KHÁM PHÁ LUẬT TRÊN HƯỚNG TIẾP CẬN TẬP THÔ
Ngành: Khoa Học Máy Tính
Đồ Án Môn Học
Toán Cho Khoa Học Máy Tính
GIẢNG VIÊN HƯỚNG DẪN
TS. Dương Tôn Đảm
TP HỒ CHÍ MINH – Năm 2014
2
MỤC LỤC
3
DANH SÁCH BẢNG BIỂU
4
DANH SÁCH HÌNH
5
MỞ ĐẦU
Ngay từ khi xuất hiện, lý thuyết tập thô do Zdzisaw Pawlak khởi xướng vào
những năm đầu thập niên 80 đã ngay lập tức thu hút sự quan tâm của nhiều nhà

Triết lý của tập thô dự trên nhận định rằng mọi đối tượng trong vũ trụ đều
gắn với môt loại thông tin nào đó (như dữ liệu, tri thức ). Ví dụ nếu các
đối tượng là các bệnh nhân bị một căn bệnh nào đó, thì các triệu chứng
của bệnh tạo nên thông tin về bệnh nhân.
Các đối tượng được đặc trưng bởi cùng thông tin thì không thể phân biệt
được (indiscernable). Vì vậy quan hệ tương đương là cơ sở toán học của lý
thuyết tập thô.
Một tập bất kỳ các đối tượng không thể phân biệt được (các đối tượng
tương tự) được gọi là tập cơ bản (elementary set) và tạo thành nguyên tử
(atom hay granule) của tri thức về vũ trụ.
Xấp xỉ dưới và xấp xỉ trên:
Trong lý thuyết tập thô, bất cứ một khái niệm không rõ ràng nào đều được
thay bằng một cặp khái niệm không chính xác gọi là xấp xỉ dưới (lower
approximation) và xấp xỉ trên (upper approximation) của khái niệm.
7
Xấp xỉ dưới gồm tất cả các đối tượng chắc chắn thuộc về khái niệm, xấp
xỉ trên gồm tất cả các đối tượng có thể thuộc về khái niệm. Hiệu của xấp
xỉ trên và xấp xỉ dưới tạo thành khoảng ranh giới (boundary region) của
khái niệm.
Các phép toán cơ bản của lý thuyết tập thô được sử dụng để phát hiện các
mẫu cơ sở (fundamental pattern) trong dữ liệu. Do đó, với một ý nghĩa
nhất định phương pháp lập luận thô cũng chính là học máy (machine
learning), phát hiện tri thức (knowledge discovery), suy diễn thống kê
(statistic inference) và suy diễn quy nạp (inductive inference).
1.2 Hệ thông tin
1.2.1 Một số khái niệm
1.2.1.1 Hệ thông tin (Information System)
Đôi khi ta hay gặp các tập hợp dữ liệu được miêu tả bằng một bảng, trong
đó một hàng biểu diễn một bản ghi (record), còn các cột biểu diễn một
thuộc tính. Từ những năm đầu của thập kỉ 80, Pawlak hình thức hóa bảng

p(x). Mỗi hàng trong bảng biểu diễn thông tin về một đối tượng trong U.
Trong cơ sở dữ liệu, có thuộc tính là thuộc tính quyết định, các thuộc tính
còn lại là thuộc tính điều kiện.
Ví dụ:
Bảng 1 Ví dụ về Bảng quyết định
U Cảnh quan Nhiệt độ Gió Đánh cầu lông
U1 Nắng Thấp Nhẹ yes
U2 Nắng Cao Nhẹ yes
U3 Nắng Thấp Nhẹ yes
U4 Mưa Cao Mạnh no
U5 Nắng Thấp Nhẹ no
U6 Nắng Quá cao Nhẹ no
U7 Mưa Cao Nhẹ yes
1.2.1.3 Quan hệ bất khả phân biệt (indiscernibility relation)
Cho hệ thông tin . Với mỗi tập con các thuộc tính , tồn tại một quan hệ hai
ngôi trên U, kí hiệu IND(B), xác định bởi:
9
IND(B) được gọi là quan hệ B-quan hệ bất khả phân biệt (B-
indiscernibility relation), đây là một quan hệ tương đương trên U.
Nếu thì hai đối tượng u và v không phân biệt được bởi các thuộc tính
trong B. Lớp tương đương chứa phần tử u được kí hiệu [u]
B
. Khi đó quan
hệ IND(B) được xác định hoàn toàn bởi các lớp tương đương [u]
B
, .
1.2.1.4 Rút gọn và lõi
Trong bảng quyết định, các thuộc tính điều kiện được phân thành ba
nhóm: thuộc tính lõi, thuộc tính rút gọn và thuộc tính không cần thiết.
Thuộc tính lõi là thuộc tính cốt yếu, không thể thiếu trong việc phân hoạch

10
1.2.1.5 Luật quyết định
Một công cụ thường được sử dụng để nghiên cứu bảng quyết định là luật
quyết định. Cụ thể, cho là một bảng quyết định, với mỗi , chúng ta cho
tương ứng một hàm xác định bởi , với mỗi . Hàm d
u
được gọi là một luật
quyết định và u được xem như là nhãn của luật quyết định đó.
11
Chương 2 KHÁM PHÁ TRI THỨC THEO HƯỚNG TIẾP
CẬN TẬP THÔ
2.1 Khám phá luật trong bảng quyết định
2.1.1 Luật trong bảng quyết định
Giả sử là một bảng quyết định; X biểu thị sự kết hợp giữa các từ nhận
dạng (descriptors) bao hàm trong các thuộc tính điều kiện A; Y biểu thị
một từ nhận dạng d = v trong đó v là bất kỳ một giá trị nào của thuộc tính
quyết d
Định Nghĩa (Luật theo tiếp cần tập thô)
Một luật quyết định có dạng “Nếu X thì Y” được biểu diễn bởi X  Y
với S biểu thị độ mạnh của luật.
2.1.2 Hai đặc trưng của luật: Độ mạnh và độ nhiễu
Cho luật X  Y, Độ mạnh của luật này ký hiệu là S (X  Y) được xác
định theo công thức sau:
s(X)(1-r(X  Y))
Với s(X) được gọi là độ mạnh của X:
Với,
là số các đối tượng quan sát thỏa mãn trong lần thứ i.
Trong trường hợp sử dụng tri thức kinh nghiệp thì s(X) được tính:
Độ nhiễu r(X  Y) được tính như sau:
Với là các đối số thuộc lớp Y trong các trường hợp thỏa mãn bộ sinh.

G(x)
Nắng
Thấp
Mạnh
Nắng
Thấp
Nhẹ
Mưa
Thấp
Nhẹ
Mưa
Quá
cao
Nhẹ
*Thấp
Mạnh
1/2 1/2
*Thấp
Nhẹ
1/2
*Cao
Mạnh

*Cao
Nhẹ

*Quá
Cao

13

Trong đó:
a) Từ bảng quyết định trên xét trường hợp có tỷ lệ nhiễu là = 0.
Bảng 4 Bảng tỉ lệ nhiễu = 0
u Cảnh quan Nhiệt độ Gió Đánh cầu lông
u1’ Nắng Thấp Nhẹ yes,
yes,
no
u2 Nắng Cao Nhẹ yes
u3 Nắng Thấp Nhẹ yes
u4 Mưa Cao Mạnh no
u5 Nắng Thấp Nhẹ no
u6 Nắng Quá cao Nhẹ no
14
u7 Mưa Cao Nhẹ yes
u Cảnh quan Nhiệt độ Gió Đánh cầu lông
U1’ Nắng Thấp Nhẹ
u2 Nắng Cao Nhẹ yes
u4 Mưa Cao Mạnh no
u6 Nắng Quá cao Nhẹ no
u7 Mưa Cao Nhẹ yes
Ta có: r
{yes)
(u1’) = 1 – 2/3 = 0.33 và r
{không}
(u1’) = 1 – 1/3 = 0.67
Đặt T
nhiễu
= 0 thì r
{cấm}
(u1) = 0.33 > T

Tạo luật cho u2
f
T
(u2) =
s({Nắng, Cao}) = 0.5
r({Nắng, Cao} yes) = 0
15
{Nắng, Cao} yes) với S = (1 x ½) x (1-0) = 0.5
s({Nhẹ, Cao}) = 1
r({Nhẹ, Cao} yes) = 0
{Nhẹ, Cao} yes) với S = (2 x ½) x (1-0) = 0
* Tạo vector phân biệt cho u4
Vector phân biệt u4 được tính như sau:
m
4,1’
= {Cảnh quan, nhiệt độ, gió}
m
4,2
= {Cảnh quan, gió}
m
4,4
=
m
4,6
=
m
4,7
= {Gió}
u1 u2 u4 u6 u7
u4 Cảnh quan, Nhiệt

{Cao, Nhẹ}  yes với S = 1 u2,u7
{Nắng, Nhẹ}  yes với S = 0.5 u7
{Nắng, Cao}  yes với S = 0.5 u2
Nắng, Quá Cao, Nhẹ Mưa, Cao, Mạnh
*,*,Mạnh 1/6
*, Quá Cao, * 1/4
{Mạnh}  no với S = 1/6 u4
{Quá cao} no với S = 1/4 u6
Các luật sinh ra với tỷ lệ nhiễu = 0 (T
nhiễu
= 0)
• Các luật chắc chắn
{Mạnh}  no với S = 1/6 u4
{Quá cao}  no với S = 1/4 u6
{Cao, Nhẹ}  yes với S = 1 u2,u7
• Các luật có thể
17
{Thấp}  yes với S = (1/4)(1/2)
{Nắng, Thấp}  yes với S = (1/2)(2/3)
{Nắng, Nhẹ}  yes với S = (1/3)(2/3)
{Thấp, Nhẹ}  yes với S = (1/2)(2/3)
Các trường hợp bao phủ: u1,u3,u5
b) Xét trường hợp tỷ lệ nhiễu > 0
Bảng 5 Bảng tỉ lệ nhiễu > 0
u Cảnh quan Nhiệt độ Gió Đánh cầu lông
u1’ Nắng Thấp Nhẹ yes,
yes,
no
u2 Nắng Cao Nhẹ yes
u3 Nắng Thấp Nhẹ yes

18
2.1.4 Thuật toán tối ưu hóa các luật
Giả sử bảng quyết định gồm n đối tượng và m thuộc tính, tỷ lệ nhiễu r.
Câu hỏi đặt ra là tìm tập tối ưu các luật có cùng độ mạnh.
Bước 1: các đối tượng với các giá trị thuộc tính điều kiện giống nhau được
coi như một thuộc tính đối tượng gọi là đối tượng ghép.
Bước 2: Tính toán tỷ lệ nhiễu r cho mỗi đối tượng ghép.
Bước 3: Chọc một đối tượng u từ U và tạo một vector phân biệt được cho
u.
Bước 4: Tìm tất cả các tập rút gọn cho đối tượng u sử dụng hàm phân biệt
được.
Bước 5: Tạo các luật từ tập rút gọn cho u, và xem lại độ mạnh của mỗi
luật.
Bước 6: Chọn luật tốt nhất từ các luật từ bước 5, sử dụng phương pháp
đánh giá kinh nghiệm khi lựa chọn luật.
Bước 7: U = U – {u}. Nếu U , Thi quay lại bước 3, trường hợp khác thì
tiếp bước 8.
Bước 8: kết thúc nếu số các luật được chọn trong bước 6 cho mỗi trường
hợp là 1, trường hợp còn lại thì tìm một tập tối thiểu các luật mà chứa tất
cả các trường hợp trong bản quyết định.
Độ phức tạp thời gian của thuật toán:
O(mn
2
+ mn
2
N(G
t
)) với N(G
t
) là số lần sinh và nhỏ hơn O(2

Hoạt động (Activity) được thể hiện như sau:
Tính thanh khoản (Liquidity) được thể hiện như sau:
Nợ (Debt) được thể hiện như sau:
20
Vị trí trên thị trường tài chính (Position on Financial Market) được thể
hiện như sau:
Chỉ số này thường được biết với tên Price-Earnings ratio (chỉ số P/E).
Trong đó lợi nhuận trên một chứng khoán (Earnings per share – EPS)
được tính bằng:
Trên lý thuyết và thực tế hiện nay tồn tại rất nhiều phương pháp khác nhau
để đánh giá sức mạnh, vị trí và hiệu suất của các công ty trên thị trường.
Ví dụ: có phương pháp phân loại tất cả các công ty ra thành các nhóm
ngành phụ thuộc vào ngành công nghiệp tương ứng của công ty đó. Sau
đó là đánh giá các công ty riêng biệt cho từng nhóm ngành, và cuối cùng
những kết quả riêng lẻ đó sẽ được tích hợp lại với nhau. Phương pháp này
khá là phức tạp bởi vì mỗi nhóm ngành đòi hỏi ngưỡng về chỉ tiêu kinh tế
khác nhau, và các bước đánh giá cũng khác nhau.
Phương pháp được đề xuất ở đây sẽ tương đối đơn giản nhưng hiệu quả
trong việc đánh giá hiệu suất. Chúng ta sẽ xem xét năm tiêu chí ở trên, và
so sánh hai giá trị liền kề nhau trong một khoảng thời gian t
1
và t
2
. Nếu tỉ
lệ của một tiêu chí trong hai thời điểm lớn hơn 1, ta có thể kết luận vị trí
trên thị trường tài chính và hiệu suất của công ty đó tăng. Ngược lại, nếu tỉ
lệ này nhỏ hơn 1, ta có thể kết luận vị trí trên thị trường tài chính và hiệu
suất của công ty này giảm.
Cụ thể trong đồ án này chúng ta sẽ tính toán 5 chỉ số tài chính này của một
công ty theo từng giai đoạn 3 tháng (1 quý), thời gian tính từ Quý 1/2011

R1 <=1 >1 >1 <=1 <=1 Price Increasing
R2 >1 >1 <=1 <=1 <=1
Price Increasing
R3 >1 >1 >1 <=1 <=1
Price Increasing
R4 >1 >1 >1 <=1 >1
Price Increasing
R5 >1 >1 >1 >1 >1 Price Decreasing
R6 >1 >1 >1 >1 <=1
Price Decreasing
R7 >1 >1 <=1 >1 >1
Price Decreasing
R8 >1 >1 <=1 >1 <=1
Price Decreasing
R9 >1 >1 <=1 <=1 >1 Price Increasing
R10 >1 <=1 >1 >1 >1
Price Decreasing
R11 >1 <=1 >1 >1 <=1
Price Decreasing
R12 >1 <=1 >1 <=1 >1
Price Decreasing
public rule(string _Rule_Number, string
_Profitability, string _Activity, string _Liquidity,
string _Debt, string _Market, string _Class)
{
Rule_Number = _Rule_Number;
Profitability = _Profitability;
Activity = _Activity;
Liquidity = _Liquidity;
Debt = _Debt;

public double owners_equity { get; set; }
// vốn chủ sở hữu
public double net_sale { get; set; }
// doanh thu thuần
public double gross_profit { get; set; }
// lợi nhuận gộp
public double total_equity{ get; set; }
// tổng nguồn vốn
3.4 Demo / Hướng dẫn sử dụng
Người dùng sẽ nhập vào mã cổ phiếu mà mình quan tâm (hoặc chọn trong
danh sách hiện trên giao diện), sau đó lựa chọn thời gian để lấy dữ liệu
tính toán.
Sau khi người dùng click vào nút Search, chương trình sẽ hiện lên những
thông tin tài chính cơ bản của mã cổ phiếu này, và tính toán năm chỉ số tài
chính mà ta dùng để phân tích tính hấp dẫn của cổ phiếu (Profitability,
Activity, Liquidity, Debt, Position on Market), đồng thời dựa vào bộ luật
được cung cấp phân lớp tính hấp dẫn của cổ phiếu trong khoảng thời gian
mà người dùng đang chọn.
Bên dưới là hình chụp màn hình giao diện trong hai trường hợp, cổ phiếu
được phân vào lớp “Price Increasing” và cố phiếu được phân vào lớp
“Price Decreasing”.
24
Hình 3.1 Chụp màn hình chương trình 1
25