cách xác định tập hợp tham số tối thiểu mô tả tập dữ liệu

Question

Tôi có một loạt dữ liệu thử nghiệm hồi quy. Mỗi thử nghiệm chỉ là một danh sách các thông điệp (mảng kết hợp), ánh xạ các tên trường thông báo tới các giá trị. Có rất nhiều sự lặp lại trong dữ liệu này.

Ví dụ

test1 = [ 
     { sender => 'client', msg => '123', arg => '900', foo => 'bar', ... }, 
     { sender => 'server', msg => '456', arg => '800', foo => 'bar', ... }, 
     { sender => 'client', msg => '789', arg => '900', foo => 'bar', ... }, 
    ] 

tôi muốn đại diện cho dữ liệu thực địa (như một cây quyết định tối thiểu sâu?) Để mỗi tin nhắn có thể được tái sinh programatically sử dụng một số lượng tối thiểu của các thông số. Ví dụ, ở trên

• foo luôn là 'bar', vì vậy tôi không cần phải đề cập đến nó
• gửi và khách hàng có tương quan, vì vậy tôi chỉ cần đề cập đến một hay khác
• và msg là khác nhau mỗi lần

Vì vậy, tôi muốn để có thể tái tạo những thông điệp này với một chương trình dọc theo dòng của

write_msg('client', '123') 
write_msg('server', '456') 
write_msg('client', '789') 

trong đó hàm write_msg sẽ bao gồm lồng nhau nếu câu lệnh hoặc hàm subfunction sử dụng các tham số.

Dựa trên dữ liệu ban đầu của tôi, làm cách nào tôi có thể xác định các tham số 'quan trọng nhất', tức là các thông số sẽ cho phép tôi tạo lại tập dữ liệu bằng số đối số nhỏ nhất?

Answer 1

Các giấy tờ sau đây mô tả algortithms để khám phá phụ thuộc hàm:

Y. Huhtala, J. Kärkkäinen, P. PORKKA, và H. Toivonen. TANE: Thuật toán hiệu quả để khám phá chức năng và phụ thuộc gần đúng. Tạp chí máy tính, 42 (2): 100–111, 1999, doi:10.1093/comjnl/42.2.100.

I. Savnik và P. A. Flach. Bottom-up cảm ứng các phụ thuộc chức năng từ các mối quan hệ. Trong Proc. AAAI-93 Hội thảo: Knowledge Discovery trong cơ sở dữ liệu, trang 174-185, Washington, DC, Mỹ, 1993.

C. Wyss, C. Giannella, và E. Robertson. FastFDs: A Điều khiển theo hướng Heuristic, Depth-First Thuật toán cho chức năng khai thác Các phụ thuộc từ các trường hợp quan hệ. Trong Proc. Kho dữ liệu và Khám phá kiến ​​thức, các trang 101–110, Munich, Đức, 2001, doi:10.1007/3-540-44801-2.

Hong Yao và Howard J. Hamilton. "Khai thác phụ thuộc chức năng từ dữ liệu." Khai thác dữ liệu và khám phá kiến ​​thức, 2008, doi:10.1007/s10618-007-0083-9.

Cũng đã có một số công việc về phát hiện phụ thuộc đa giá trị:

I. Savnik và P. A. Flach. "Khám phá Phụ thuộc Mutlivalued từ Quan hệ". phân tích dữ liệu thông minh Journal, 4 (3): 195-211, IOS Press, 2000.

Answer 2

Điều này trông rất giống với Database Normalization.

Bạn có quan hệ (bộ dữ liệu thử nghiệm) và một số phụ thuộc chức năng đã biết ({sender} => arg, {} => foo và có thể {msg} => người gửi. Nếu thứ tự kiểm tra là quan trọng thì thêm {testNr} => msg.) và bạn muốn loại bỏ dư thừa.

Coi bộ thử nghiệm của bạn dưới dạng bảng cơ sở dữ liệu, áp dụng quy tắc chuẩn hóa và tạo các hàm tương đương (getArgFromSender (người gửi), v.v.) cho mỗi lần kết nối.

Answer 3

Nếu số lượng các lĩnh vực và các hồ sơ là nhỏ:

Brute lực nó bằng cách lặp qua mỗi sự kết hợp của các lĩnh vực, và đối với mỗi sự kết hợp phát hiện nếu có nhiều mục trong danh sách mà bản đồ với giá trị tương tự .

Nếu bạn có thể sống với một sự lựa chọn khá tốt về các lĩnh vực:

Bắt đầu giả sử bạn cần tất cả các lĩnh vực. Sau đó, chọn một trường ngẫu nhiên và xem nó có thể được loại bỏ hay không; nếu có thể, hãy vượt qua tập hợp các trường. Nếu không, hãy chọn một trường khác một cách ngẫu nhiên và thử lại. Nếu bạn không tìm thấy trường nào có thể được loại bỏ, thì bạn đã tìm thấy một bộ trường hợp lý. Nếu bạn đã chọn các lĩnh vực khác đầu tiên, bạn có thể tìm thấy một giải pháp tốt hơn. Bạn có thể lặp lại toàn bộ quy trình một vài lần và chọn giải pháp tốt nhất nếu bạn muốn. Cách tiếp cận này được gọi là hill climbing.

(Tôi nghi ngờ rằng vấn đề này là NP complete, nghĩa là chúng tôi có thể không biết giải pháp hiệu quả và mạnh mẽ để không mất ngủ khi cố gắng mơ ước một giải pháp hoàn hảo.)