Lưu ý negative trong thuật toán CE

[Cang Do]

"Hello mọi người,

Mình đang đọc cái thuật toán Candidate Eliminate nhưng mà không hiểu lắm. Nhất là cái đoạn Negative á.

Trong cái slide hoặc tài liệu thì chỉ ghi ra kết quả mà không làm từng bước.

Mọi người có thể làm từng bước và giải thích sao ra kết quả như vậy cho mình được không?

Chúc mọi người thi tốt.

Thanks,

--Ngoc"

my reply 

Giả thuyết cần tìm phải 

1/ Tương thích với dữ liệu train (x3-) 

2/ Vẫn còn tổng quát hơn S

3/ Phải là thằng tổng quát nhất trong các thằng vd nếu có A,?,? và A,B,? thì chọn A,?,? vì nó tổng quát hơn --> xét  1 thằng khác ? là đủ.

Cách làm

+ Duyệt Ai (thuộc tính) (theo 3 chỉ cần theo 1 thuộc tính k cần tổ hợp làm gì vì tổ hợp chỉ tạo ra các tập không tổng quát hơn nó mà thôi)

+ Duyệt các giá trị thuột tính "không phải" của thằng x3  (theo 1)  --> để nó ra âm , mà âm thì mới tương thích.

+ nếu tại i nó vẫn còn tổng quát hơn s trong S thì nhận , ngược lại thì quăng shop (theo 2).

Xong :D

[Cang Do]

Trích

"Hi mọi người,

Ngọc có tìm được 2 cái link nói về Candidate eliminate. Nhưng Ngọc
không hiểu cái kết quả của G khi gặp cái negative thứ 2.
Mọi người xem xem rồi giải thích dùm Ngọc đc không?

http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/vspace/vs_prob1.html
http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/vspace/vs_prob2.html
"

Sau bước duyệt x1 ta có
S = { (Japan, Honda, Blue, 1980, Economy) }
G = { (?, ?, ?, ?, ?) }

Xét trường hợp bạn Ngọc hỏi là x2 =  Negative Example: (Japan, Toyota,
Green, 1970, Sports)
Thực hiện theo thuật giải đã post bên dưới ,duyệt theo thuộc tính
Origin : các giá trị khác Japan gồm USA
tuy nhiên USA không tương thích với S nên loại.
Manufacturer : các giá trị khác Toyota gồm Honda và Chrysler
tuy nhiên Chrysler không tương thích với S nên loại còn lại Honda ta
có g1 = {?,Honda,?,?,?}
Color:các giá trị khác Green gồm Blue,White,Red
         tuy nhiên chỉ giữ lại Blue vì nó tương thích S  ta có g2 =
{?,?,Blue,?,?}
Decade: các giá trị khác 1970 tương thích với S là 1980 --> g3 =
{?,?,?,1980,?}
Type: các giá trị khác Sports  tương thích với S là  Economy --> g4 =
{?,?,?,?,Economy}

vậy G = {g1,g2,g3,g4}

Các bước khác tương tự.
Any question please :)

On May 28, 9:55 pm, Cang Do <dovanc...@gmail.com> wrote:
> "Hello mọi người,
>
> Mình đang đọc cái thuật toán Candidate Eliminate nhưng mà không hiểu lắm.
> Nhất là cái đoạn Negative á.
> Trong cái slide hoặc tài liệu thì chỉ ghi ra kết quả mà không làm từng bước.
>
> Mọi người có thể làm từng bước và giải thích sao ra kết quả như vậy cho
> mình được không?
>
> Chúc mọi người thi tốt.
>
> Thanks,
> --Ngoc"
>

> *my reply *

> Giả thuyết cần tìm phải
> 1/ Tương thích với dữ liệu train (x3-)
> 2/ Vẫn còn tổng quát hơn S
> 3/ Phải là thằng tổng quát nhất trong các thằng vd nếu có A,?,? và A,B,?
> thì chọn A,?,? vì nó tổng quát hơn --> xét  1 thằng khác ? là đủ.
>

> *Cách làm*
> *+ Duyệt Ai (thuộc tính)* (theo 3 chỉ cần theo 1 thuộc tính k cần tổ hợp

> làm gì vì tổ hợp chỉ tạo ra các tập không tổng quát hơn nó mà thôi)
>

> *+ Duyệt các giá trị thuột tính "không phải" của thằng x3*  (theo 1)  -->

> để nó ra âm , mà âm thì mới tương thích.
>

> *+ nếu tại i nó vẫn còn tổng quát hơn s trong S thì nhận , ngược lại thì
> quăng shop (theo 2).*
>
> Xong :D

[Cang Do]

Sau bước duyệt x2 ta có

G =	{ (?, Honda, ?, ?, ?),  (?, ?, Blue, ?, ?), (?, ?, ?, 1980, ?), (?, ?, ?, ?, Economy) }

S =	{ (Japan, Honda, Blue, 1980, Economy) }

Xét x3 

Positive Example: (Japan, Toyota, Blue, 1990, Economy)

+ Co G : loại bõ các g không tương thích với x3 bằng cách lần lượt thay x3 vào g 

ta còn G3= {g2,g4}

+ Nở S: loại bõ các s không tương thích với x3

Tìm cách giả thuyết tổng quát hơn s tương thích với x3 mà vẫn cụ thể hơn G3 và nó phải là cụ thể nhất.
S3= {Japan,?,Blue,?,Economy}

S3= {Japan,?,Blue,?,Economy}

G3 = {g2,g4}

xét x4  

Negative Example: (USA, Chrysler, Red, 1980, Economy)

+ Loại bõ các s thuộc S3 không tương thích với x4: thay x4 vào s, ta có s(x3) negative ngay từ thuộc tính đầu tiên --> tương thích --> giữ nguyên.

+ Loại bõ các g không tương thích với x4

g2 = (?, ?, Blue, ?, ?) : g2(x4) = negative tại vị trí 3 --> tương thích --> giữ nguyên.

g4 = (?, ?, ?, ?, Economy) : g4(x4) = position --> không tương thích --> loại

Tìm g tổng quát nhỏ nhất của g4 (cụ thể hơn g4) 

lặp lại thuật toán ban đầu với các kí hiệu ? trong g4 ta có:

thuộc tính 1: phải khác USA và tổng quát hơn hoặc bằng Japan thuộc S4 --> Japan

--> kết quả g41 = (Japan, ?, ?, ?, Economy)

thuộc tính 2: phải khác Chrysler và tổng quát hơn hoặc bằng ? thuộc S4 --> không tồn tại

thuộc tính 3: phải khác Red và tổng quát hơn hoặc bằng Blue --> Blue

 --> kết quả g42 = (?, ?, Blue, ?, Economy) loại vì nó cụ thể hơn g2 đã tồn tại.

thuộc tính 4: phải khác  1980 và tổng quát hơn hoặc bằng ? --> không tồn tại.

vậy G4= {g2,g41}

Lưu ý:

Thuật giải ban đầu về negative là thuật giải mình tự tóm gọn theo lối vét cạn dựa trên mấy tiêu chuẩn lý thuyết, do đó các bạn có thể tìm 1 cách khác miễn sao thõa mãn các tiêu chuẩn đưa ra là được.

[ntnt]

ANh Cang
Theo như bài giải của anh ở bước 2

Color:các giá trị khác Green gồm Blue,White,Red
tuy nhiên chỉ giữ lại Blue vì nó tương thích S ta có g2 =
{?,?,Blue,?,?}

Thì nó phải có Blue và White
Nhưng anh chỉ lấy có Blue
??????????
Mong anh chỉ
Thanks anh

[Cang Do]

S1 = { (Japan, Honda, Blue, 1980, Economy) } 

"các giá trị khác Green gồm Blue,White,Red

        tuy nhiên chỉ giữ lại Blue vì nó tương thích(hoặc tổng quát hơn) S " là vì :

Nếu White hoặc  Red hình thành giả thuyết thì lúc đó giả thuyết là 

h = (White,?,?,?,?) 

tuy nhiên h này phải tổng quát hơn ít nhất 1 giả thuyết s trong S trường hợp này S chỉ chứa 1 con là 

s = (Japan, Honda, Blue, 1980, Economy) 

h này lại khác với s ngày từ vị trí thuộc tính đầu tiên White <> Japan nên rõ ràng nó không thõa mãn.

Một cách ngắn gọc giá trị tại vị trí thuộc tính đó phải trùng với giá trị tại vị trí thuộc tính đó ít nhất 1 trong các giả thuyết nằm trong S.

2012/5/29 ntnt <nguyentra...@gmail.com>

[Bạch Thị Mộng Hường]

Cho em hỏi, nếu trường hợp dưới đây:
Outlook Temperature Humidity Windy Play (positive) / Don't Play
(negative)
sunny hot nomal false Don't Play
sunny hot high true Don't Play
overcast hot nomal false Play
rain mid high false Play
rain cool nomal false Play
rain cool nomal true Don't Play
overcast mid nomal true Play
sunny mid high false Don't Play

trong trường hợp này, lần duyệt đầu tiên là Negative thì S1 là gì và
G1 là gì?
nếu theo như thuật toán thì S1 = {<0,0,0,0>} và G1 ={<?,?,?,?>} luôn
đúng không?


với lại cho em thắc mắc thêm ở phần trên, trong lần duyệt thứ 2,
S1 = {< Japan, Honda, Blue, 1980, Economy >}
G1 = {<?, ?, ?, ?, ?, ?>}

X2 (Negative): <Japan, Toyota, Green, 1970, Sports>

theo như thuật toán: Nếu Negative thì:
Remove từ S bất kỳ giả thuyết nào không tương thích với d.....

như vậy trong trường hợp này: trong S1 có Japan, trong d cũng có Japan
-> không tương thích: ?? sao không xóa Japan khỏi S1

[Cang Do]

1/  trong trường hợp này, lần duyệt đầu tiên là Negative thì S1 là gì và

G1 là gì?
nếu theo như thuật toán thì S1 = {<0,0,0,0>} và G1 ={<?,?,?,?>} luôn
đúng không?

Không. 

kết quả đúng là 

{

(overcast,?,?,?)

(rain,?,?,?)

(?,mid,?,?)

(?,cool,?,?)

(?,?,high,?)

(?,?,?,true)

}

2/ với lại cho em thắc mắc thêm ở phần trên, trong lần duyệt thứ 2,

S1 =  {< Japan, Honda, Blue, 1980, Economy >}
G1 = {<?, ?, ?, ?, ?, ?>}

X2 (Negative): <Japan, Toyota, Green, 1970, Sports>

theo như thuật toán: Nếu Negative thì:
       Remove từ S bất kỳ giả thuyết nào không tương thích với d.....

như vậy trong trường hợp này: trong S1 có Japan, trong d cũng có Japan
-> không tương thích: ?? sao không xóa Japan khỏi S1

x2 consistent với S1 . Tuy Japan trùng nhau nhưng thuộc tính A2 thì không trùng.