Chào mừng đến với BIS Đăng nhập | Đăng ký | Trợ giúp
trong Tìm kiếm

Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

Bài cuối 12-07-2016 03:15 PM của chucnv. 9 trả lời.
Trang 1 trong số 1 (10 nội dung)
Sắp xếp bài viết: Trước Tiếp theo
  • 08-02-2013 05:13 PM

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 9,240

    Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Nguyễn Văn Chức - chuc1803@gmail.com

    Lý thuyết tập thô (Rough Set Theory) do Zdzisaw Pawlak (1926-2006) đề xuất vào năm 1982 đã được ứng dụng ngày càng rộng rãi trong lĩnh vực khoa học máy tính. Lý thuyết tập thô được phát triển trên một nền tảng toán học vững chắc, cung cấp các công cụ hữu ích để giải quyết các bài toán phân tích dữ liệu, phát hiện luật, nhận dạng… Đặc biệt thích hợp với các bài toán phân tích trên khối lượng dữ liệu lớn, chứa đựng thông tin mơ hồ, không chắc chắn. Mục đích chính của phân tích dữ liệu dựa trên lý thuyết tập thô nhằm đưa ra các xấp xỉ để biểu diễn các đối tượng không thể được phân lớp một cách chắc chắn bằng tri thức có sẵn. Theo quan điểm của lý thuyết tập thô, mọi tập thô đều liên kết  với 2 tập “rõ” là xấp xỉ dưới và xấp xỉ trên của nó. Xấp xỉ dưới bao gồm các đối tượng chắc chắn thuộc, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về tập đó. Các tập xấp xỉ là cơ sở để rút ra các kết luận (tri thức) từ cơ sở dữ liệu.

    Bài viết này giới thiệu cơ bản về lý thuyết tập thô và ứng dụng nó trong khai phá dữ liệu.

    1.  Giới thiệu về lý thuyết tập thô

    Một số khái niệm cơ bản

    Hệ thống thông tin

    Một tập dữ liệu có thể biểu diễn dưới dạng một bảng, trên đó mỗi dòng biểu diễn thông tin ứng với một đối tượng, mỗi cột biểu diễn một thuộc tính có thể đo được của đối tượng. Bảng này được gọi là một hệ thống thông tin.

    Hệ thống thông tin là một cặp S=(U,A), trong đó U là tập hữu hạn khác rỗng các đối tượng gọi là tập vũ trụ còn A là tập hữu hạn khác rỗng các thuộc tính.

    Với mỗi đối tượng , ta ký hiệu u(a) là giá trị của đối tượng u tại thuộc tính a. Nếu gọi Ia là tập tất cả các giá trị của thuộc tính a, thì . Bây giờ, nếu đặt  là tập con của tập thuộc tính A, ta ký hiệu bộ các giá trị u(bi) bởi u(B). Như vậy, nếu u và v là 2 đối tượng u(B)=v(B) nếu u(bi)=v(bi), với mọi i=1,2,…,k.

    Ví dụ: Một hệ thống thông tin bao gồm 8 đối tượng U={u1,u2,u3,u4,u5,u6,u7,u8}, tập thuộc tính A={Color, Size }, và miền giá trị cho từng thuộc tính là IColor = {Green, Yellow, Red}, ISize = {Small, Medium, Big }.


    Bảng 1. Hệ thống thông tin

    Bảng quyết định (Decision Table)

    Bảng quyết định là một hệ thống thông tin có dạng T=(U,A),với  U là tập các đối tượng và A là tập các thuộc tính, trong đó tập thuộc tính A được chia thành 2 tập thuộc tính rời nhau là C và D, C được gọi là tập thuộc tính điều kiện và D là tập thuộc tính quyết định. Tức là .

    Ví dụ : Bảng sau đây là một bảng quyết định. Bảng này có 8 đối tượng như trong bảng 1, nhưng có thêm thuộc tính quyết định (Shape). Trong bài toán phân lớp thì thuộc tính quyết định chính là lớp của đối tượng cần xếp lớp. Trong ví dụ này thuộc tính quyết định Shape có 3 giá trị là Circle, square và Triangle


    Bảng 2. Bảng quyết định

    Quan hệ không phân biệt được

    Xét hệ thống thông tin S = (U, A), khi đó mỗi tập thuộc tính  đều tạo ra một quan hệ 2 ngôi trên U, ký hiệu IND(B):

              .


    Ví dụ:
     Tập thuộc tính B= {Color, Size} trong Bảng 2 phân hoạch tập 8 đối tượng thành tập các lớp tương đương như sau:

    Nhận xét: 
    Ta thấy, các đối tượng u1và u6 cùng một lớp tương đương nên chúng không thể phân biệt với nhau trên tập thuộc tính {Color, Size }.

    Các tập xấp xỉ

    Các tập xấp xỉ là cơ sở để rút ra các kết luận (tri thức) từ cơ sở dữ liệu. Cho hệ thống thông tin . Với các tri thức được cho bởi tập thuộc tính B, vấn đề đặt ra là liệu chúng ta có thể biểu diễn tập các đối tượng V bằng các tri thức có sẵn hay không? Hay nói cách khác, với tập thuộc tính B cho trước, chúng ta có các lớp tương đương của quan hệ IND(B), thế thì tập các đối tượng V có thể được diễn đạt thông qua các lớp tương đương này như thế nào? Trong lý thuyết tập thô, để biểu diễn tập đối tượng V bằng tri thức có sẵn B người ta xấp xỉ chúng bởi hợp của một số hữu hạn các lớp tương tương của IND(B). Có 2 cách xấp xỉ đó là B-Xấp xỉ dưới của V, ký hiệu là và B-Xấp xỉ trên của tập V, ký hiệu là . Các tập xấp xỉ này được định nghĩa như sau:

     và 

    Tập  bao gồm tất cả các phần tử của U chắc chắn thuộc vào V

    Tập  bao gồm các phần tử của U có khả năng được phân loại vào những phần tử thuộc V.

    Từ 2 tập xấp xỉ trên và xấp xỉ dưới của V, người ta định nghĩa các tập sau:

    : B-miền biên của V. Nếu  thì V được gọi là tập thô, ngược lại V được gọi là tập rõ

    : B-vùng dương của V

    : B-vùng âm của V

    Đối với một hệ thống thông tin , ký hiệu R= IND(B), người ta gọi B-miền khẳng định dương của D là tập được xác định như sau:
     
     


    Ví dụ: 
    Xét hệ thống thông tin biểu diễn các triệu chứng của cảm cúm như sau:


    Bảng 3. Các triệu chứng cảm cúm

    Từ hệ thống thông tin trên, ta có các lớp không phân biệt được B={Đau đầu, Thân Nhiệt} là {u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.

    Nếu đặt V={u|u(Cảm cúm)=Có}={u2,u3,u6,u7}, lúc đó ta có:

    BV= {u2,u3} và = {u2,u3,u5,u7,u6,u8}.

    Từ đó ta có B-miền biên của V là tập  ={ u5,u6,u7,u8}.

    Rút gọn (Reduction) và lõi(Core)

    Trong bảng quyết định, các thuộc tính điều kiện được phân thành 3 loại, đó là: thuộc tính lõi (core), 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 không thể thiếu trong việc phân hoạch tập dữ liệu. Thuộc tính không cần thiết là những thuộc tính dư thừa (có thể loại bỏ một thuộc tính như vậy chứ không phải loại bỏ tất cả) mà không ảnh hưởng đến việc phân hoạch dữ liệu. Thuộc tính rút gọn nằm giữa 2 tập thuộc tính trên, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa nhưng với tổ hợp thuộc tính khác, nó có thể là thuộc tính lõi.

    Cho một bảng quyết định . Tập thuộc tính  được gọi là một rút gọn của C nếu  POSR(D)= POSC(D). Lõi của tập thuộc tính C, ký hiệu CORE(C) là tất cả các thuộc tính giao của tất cả các tập rút gọn của C.

    .
    Trong đó RED(C) là tập hợp tất cả các rút gọn của C.

    Ví dụ: Cho bảng quyết định về bệnh cúm như bảng bảng 4


    Bảng 4. Bảng quyết định về bệnh cúm

    Bảng này có 2 tập rút gọn là R1={Đau đầu, Thân nhiệt} và R2= {Đau cơ, Thân nhiệt}. Tập lõi Core={Thân nhiệt}. Vậy Thân nhiệt là thuộc tính cần thiết duy nhất, các thuộc tính Đau đầu, Đau cơ đều không cần thiết. Điều này có nghĩa rằng có thể loại bỏ 1 trong 2 thuộc tính Đau đầu hoặc Đau cơ (không thể bỏ đồng thời cả 2) mà không ảnh hưởng đến kết quả chuẩn đoán bệnh.

    Có rất nhiều thuật toán đã được xây dựng để tìm các tập rút gọn tối thiểu các thuộc tính điều kiện của bảng quyết định. Tuy nhiên, độ phức tạp của các thuật toán này là NP-khó. Vì vậy, người ta thường sử dụng các thuật toán rút gọn xấp xỉ, trong đó thuật toán rút gọn xấp xỉ Johnson được sử dụng rất phổ biến.

    2.     Giới thiệu công cụ triển khai lý thuyết tập thô

    Phần này giới thiệu phần mềm ROSE2, đây là phần mềm triển khai khá đầy đủ các nhiệm vụ cơ bản của lý thuyết tập thô như tìm các rút gọn tập thuộc tính (reduction), tìm lập lõi (core), tìm các luật suy diễn (Induction), xấp xỉ (Approximation), ma trận phân biệt (Discernibility Matrix)…

    Dữ liệu minh họa là bảng quyết định về dữ liệu cảm cúm (bảng 4) gồm có 6 đối tượng, 3 thuộc tính điều kiện (Đau đầu, Đau cơ, thân nhiệt) và 1 thuộc tính quyết định (Cảm cúm)

    Khởi động ROSE2, tạo file dữ liệu và nhập dữ liệu vào như sau




     
     
     
     
     
     
     
     
     
     
     
     
     
     
    Kết quả sau khi nhập dữ liệu:

    Tìm tập lõi (Core): Chọn file dữ liệu, chọn Reduction, chọn Core, chọn thuộc tính quyết định (decision attribute) là Cảm cúm. Kết quả tập lõi có 1 thuộc tính là Thân Nhiệt:

    Tìm các tập rút gọn: Chọn Reduction, chọn Lattice Search, chọn thuộc tính quyết định (decision attribute) là Cảm cúm. Kết quả có 2 tập rút gọn là {Đau đầu, Thân nhiệt} và {Đau cơ, thân nhiệt}.


    Tìm các luật suy diễn: Chọn Rule Induction, chọn Basic Minimal Covering, chọn thuộc tính quyết định (decision attribute) là Cảm cúm. Kết quả có các luật suy diễn như sau:


    Các luật được phát hiện chính là các tri thức được khai phá từ dữ liệu. Đây là cơ sở để suy đoán, ước lượng hoặc ra quyết định. Trong ví dụ này, có thể dựa vào các luật này để chuẩn đoán một người có bị bệnh cảm cúm hay không.

     Tìm các tập xấp xỉ tương đương: Trong mục Similarity Relation, chọn Approximations, chọn thuộc tính quyết định (decision attribute) là Cảm cúm. Kết quả.

     

    Công cụ ROSE2 triển khai khá đầy đủ các nhiệm vụ cơ bản của lý thuyết tập thô với giao diện dễ sử dụng, trình bày kết quả dễ hiểu. Tuy nhiên, để khai thác hết các chức năng của chương trình, bạn cần phải có kiến thức nhất định về lý thuyết tập thô.

     

    • Điểm chủ đề: 35
  • 11-24-2013 03:08 PM trả lời

    • huylong
    • Không xếp hạng
    • Tham gia 11-24-2013
    • Điểm 35

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Chào bạn,mình có đọc bài viết trên của bạn,mình thấy có phần mềm ROSE 2,đó là phần mềm gì vậy,sao mình tìm trên mạng không có,hoặc bạn có thể cho mình xin link tải về phần mềm đó không,Thanks bạn
    • Điểm chủ đề: 35
  • 11-25-2013 01:44 PM trả lời

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 9,240

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Chào bạn,
    Gởi bạn  link download phần mềm ROSE 2
    http://idss.cs.put.poznan.pl/site/rose.html
     
    • Điểm chủ đề: 50
  • 12-10-2013 08:59 PM trả lời

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Bạn ơi cho mình hỏi chút:  mình đã down và cài phần mềm Roes2 rồi nhưng khi tạo file mới không thể tác động vào dòng cột được, nó hiện lỗi 0040C1A6 và tab Attribute bị not enable. Bạn có thể chỉ kỹ thêm cách sử dụng phần mềm này được không? Mình đang cần gấp cho bài tập lớn. 
    Thank you ! 
    • Điểm chủ đề: 35
  • 01-05-2016 09:23 AM trả lời

    • bachtuoc
    • Không xếp hạng
    • Tham gia 01-05-2016
    • Điểm 50

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    mình nói rõ hơn phần anh Nguyễn Văn Chức chưa nói rõ.
    + Phần nhập dữ liệu: khi bạn nhập dữ liệu điều quan trọng là bạn phải chọn ra thuộc tính (Attribute) quan trọng (Decision). Bạn để ý thấy hình mà anh chức cho bạn xem kết quả sau khi nhập dữ liệu:

    bạn thấy chữ Drinks sau chữ CamCum chứ bạn, sau khi nhập dữ liệu song thì điều đó phải có, làm sao để có được nó:
     
    Bây giờ bạn có thể làm các bước còn lại mà không ro bị lỗi 
     
    • Điểm chủ đề: 50
  • 10-06-2016 09:56 AM trả lời

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Anh có thể cho tôi xin bản hướng dẫn sử dụng ROSE2. Cảm ơn anh.
    • Điểm chủ đề: 20
  • 11-03-2016 04:39 PM trả lời

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Bạn Hướng dẫn trực tiếp cho mình về LT Tập thô: "Rút gọn thuộc tính trên bảng quyết định" được không? Nếu được nhắn cho mình vào Email: tuanna573@gmail.com.  Xin chân thành cảm ơn và rất mong được sự giúp đỡ của bạn.
    • Điểm chủ đề: 35
  • 11-21-2016 11:14 PM trả lời

    • duyvu
    • Không xếp hạng
    • Tham gia 11-21-2016
    • Điểm 20

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    anh ơi cái này là anh có 1 số tài liệu nào liên quan đến chương trình anh thực hiện ko ạ. em đọc khó hiểu quá anh à
     
    • Điểm chủ đề: 20
  • 12-07-2016 12:27 AM trả lời

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Bạn ơi có hướng dẫn sử dụng phần mềm ROSE không bạn ơi? Giúp mình với nhé!
    • Điểm chủ đề: 35
  • 12-07-2016 03:15 PM trả lời

    • chucnv
    • 10 thành viên năng nổ nhất
    • Tham gia 12-05-2008
    • Điểm 9,240

    Re: Ứng dụng lý thuyết tập thô trong khai phá dữ liệu

    Chào bạn,
    Bạn tham khảo xem link sau có ích không nhé:
    http://idss.cs.put.poznan.pl/site/55.html
     
    • Điểm chủ đề: 20
Trang 1 trong số 1 (10 nội dung)
Powered by Community Server (Commercial Edition), by Telligent Systems