Khai phá dữ liệu trên hệ thông tin đa trị

Bài viết trình bày phương pháp khai phá luật xếp thứ tự bằng cách chuyển đổi hệ thông tin đơn trị xếp thứ tự thành hệ thông tin đơn trị nhị phân và áp dụng các kỹ thuật sinh luật trong lý thuyết tập thô trên hệ thông tin đơn trị nhị phân thu được.
Nội dung trích xuất từ tài liệu:
Khai phá dữ liệu trên hệ thông tin đa trịPhùng Thị Thu HiềnTạp chí KHOA HỌC & CÔNG NGHỆ185(09): 103 - 110KHAI PHÁ DỮ LIỆU TRÊN HỆ THÔNG TIN ĐA TRỊPhùng Thị Thu Hiền*Trường Đại học Kinh tế Kỹ thuật Công nghiệpTÓM TẮTDựa trên ý tưởng thu nhỏ kích thước tập dữ liệu ban đầu, trong bài báo này tác giả đề xuất phươngpháp lựa chọn tập đối tượng đại diện, gọi tắt là mẫu đại diện, từ tập đối tượng ban đầu cho bài toántìm tập thuộc tính tối ưu của hệ thông tin đa trị. Tác giả chứng minh tập thuộc tính tối ưu trên tậpđối tượng ban đầu và tập thuộc tính tối ưu trên mẫu đại diện là tương đương, từ đó khẳng định tínhđúng đắn của phương pháp. Vì kích thước mẫu đại diện nhỏ hơn kích thước tập đối tượng ban đầunên thời gian thực hiện các thuật toán tìm tập thuộc tính tối ưu trên mẫu đại diện giảm thiểu đángkể. Kích thước mẫu đại diện được chọn lớn hay nhỏ phụ thuộc vào đặc thù mỗi hệ thông tin đa trịtrong thực tế. Đồng thời bài báo trình bày phương pháp khai phá luật xếp thứ tự bằng cách chuyểnđổi hệ thông tin đơn trị xếp thứ tự thành hệ thông tin đơn trị nhị phân và áp dụng các kỹ thuật sinhluật trong lý thuyết tập thô trên hệ thông tin đơn trị nhị phân thu được.Từ khóa: Hệ thông tin đa trị, tập thô, tập thuộc tính tối ưu, quan hệ dung saiMỞ ĐẦU*Lý thuyết tập thô truyền thống do Pawlak [1],[2] đề xuất được xây dựng dựa trên quan hệtương đương nhằm giải quyết bài toán tìm tậpthuộc tính tối ưu và sinh luật quyết định trêncác hệ thông tin đơn trị. Trong các bài toánthực tế, giá trị một đối tượng tại một thuộctính trên hệ thông tin có thể là một tập hợpnhiều giá trị.Trên cả hệ thông tin đơn trị và hệ thông tin đatrị, tìm tập thuộc tính tối ưu là bài toán quantrọng nhất, đã và đang thu hút sự quan tâmcủa cộng đồng nghiên cứu về tập thô. Với bàitoán tìm tập thuộc tính tối ưu, vấn đề đangđược các nhà nghiên cứu quan tâm hàng đầulà xây dựng các phương pháp pháp nhằm tốiưu thời gian thực hiện các thuật toán, nhờ đócó thể áp dụng trên các hệ thông tin kíchthước lớn. Trên hệ thông tin đơn trị, cho đếnnay nhiều phương pháp tìm tập thuộc tính tốiưu đã được công bố [3], tuy nhiên các phươngpháp này đều thực hiện trên tập đối tượng banđầu. Trên hệ thông tin đa trị, các công trìnhnghiên cứu [4], [5], [6] đã đề xuất giải phápnén dữ liệu với mục đích thu nhỏ kích thướctập dữ liệu ban đầu nhằm giảm thiểu thời gianthực hiện các thuật toán.*Tel: 0914 770070, Email: Thuhiencn1@gmail.comBài báo này tác giả đề xuất phương pháp lựachọn tập đối tượng đại diện, gọi tắt là mẫu đạidiện, từ tập đối tượng ban đầu cho bài toántìm tập thuộc tính tối ưu của hệ thông tin đatrị, và trình bày phương pháp khai phá luậtxếp thứ tự.Cấu trúc bài báo như sau. Phần 2 trình bàymột số khái niệm cơ bản và một số kết quảtrên hệ thông tin đa trị và phương pháp khaiphá luật xếp thứ tự trên hệ thông đơn trị. Phần3 đề xuất phương pháp chọn mẫu đại diệntrên hệ thông tin đa trị. Phần 4 là kết luận vàđịnh hướng nghiên cứu tiếp theoCÁC KHÁI NIỆM CƠ BẢNHệ thông tin đa trịHệ thông tin đa trị [7], [8] là một bộ bốnIS  U , AT ,V , f  trong đó U là tập hữu hạn,khác rỗng được gọi là tập vũ trụ hoặc tập cácđối tượng; AT là tập là hữu hạn khác rỗng cácf là hàm thông tin,thuộc tính;f : U  A  2V là ánh xạ tương ứng mỗi cặp(u,a) tới một tập giá trị thuộc V.Bài báo quy ước viết tắt IS  U , AT ,V , f  làIS  U , AT  .Ký hiệu giá trị của thuộc tính a  AT tại đốitượng u U là a  u  , khi đó mỗi tập conthuộc tính A  AT xác định một quan hệtương đương:103Phùng Thị Thu HiềnIND  A  Tạp chí KHOA HỌC & CÔNG NGHỆu, v  U U a  A,a u   a  v Định nghĩa 2.1.[7]. Quan hệ dung sai tronghệ thông tin đa trịCho hệ thông tin đa trị IS  U , AT  . Vớimỗi tập con thuộc tính B  AT , quan hệSB  u, v  U  Ub  B , u (b)  v  b   là một quan hệ dung sai và được gọi là quanhệ dung sai tương ứng với B. Rõ ràng làB  AT : S B   Sb .bBĐặt u S  v U | (u , v)  S B  thì  u S đượcBBgọi là một lớp dung sai tương ứng với quan hệSB. Ký hiệu U / S B  u S | u U biểu diễnBtập tất cả các lớp dung sai tương ứng với quanhệ SB, khi đó U / SB hình thành một phủ của Uvì các lớp dung sai trong U / SB có thể giaonhau và  [u ]S B  U . Rõ ràng là nếu C  BuUthì u S  u S với mọi u U .BCTương tự trong hệ thông tin không đầy đủ [9],với hệ thông tin đa trị IS  U , AT  , tập thuộctính R  AT được gọi là tập thuộc tính tối ưucủa IS nếu SR  S AT và B  R, S B  S AT ,điều này tương đương với SR  u   S AT  u với mọi u U và B  R tồn tại u U saocho SB  u   S AT  u  .Hệ quyết định đa trị là hệ thống gồm cácthành phần DS  U , AT  d  trong đó ATlà các thuộc tính điều kiện và d là thuộc tínhquyết định, với giả thiết d  u  chứa một giátrị với mọi u U .Với u U ,  AT (u )  d  v  v  S AT (u ) đượcgọi là hàm quyết định suy rộng của đối tượngu trên tập thuộc tí ...