Các độ đo mô hình ước lượng

93 Chương 7: Kiểm nghiệm 7.1. Các ñộ ño mô hình ước lượng Chương 6 ñã ñề xuất một phương pháp xây dựng mô hình ước lượng dựa trên công thức bằng lập trình di truyền. Phương pháp này khắc phục ñược những hạn chế của mô hình ước lượng dựa trên công thức truyền thống trong khi vẫn phát huy những ưu ñiểm của loại mô hình này. Quá trình hiện thực hóa phương pháp ñề xuất cũng ñược trình bày chi tiết. Những khó khăn gặp phải trong việc xây dựng bộ phát sinh công thức, kiến trúc bộ thư viện EsLib hỗ trợ lập trình di truyền, cũng như ứng dụng ướng lượng công thực hiện phần mềm Estimator ñược mô tả kỹ lưỡng. Chương 7 ñi vào quá trình kiểm nghiệm những kết quả ñạt ñược của phương pháp sau khi ñã ñược hiện thực hóa. Như ñã biết, ñầu ra của phương pháp là mô hình ước lượng ñược xây dựng từ tập dữ liệu lịch sử. ðể ñánh một mô hình ước lượng, các ñộ ño khả năng ước lượng của mô hình ñược sử dụng. Mỗi ñộ ño ñánh giá một khía cạnh khác nhau của mô hình. Phần này sẽ trình bày về những ñộ ño ñược dùng trong quá trình kiểm nghiệm. 7.1.1. ðộ ño MMRE Thông thường, các mô hình ước lượng ñược ñánh giá bằng nhiều ñộ ño khác nhau và dựa vào một tập dữ liệu lịch sử ñược dùng làm thang ño. Mỗi bộ dữ liệu trong tập dữ liệu lịch sử chứa thông tin thực tế của một dự án phần mềm ñã hoàn thành trong quá khứ. Công thực tế của dự án phần mềm sẽ ñược mang ñi so sánh với giá trị ước lượng ñược từ mô hình cần kiểm nghiệm. ðộ lệch của một ước lượng thực hiện bởi mô hình ñược ño bằng ñộ ño MRE (Magnitude Relative Error). MRE càng nhỏ, ước lượng càng chính xác. 94 100× − = i ii i Actual ActualEstimated MRE Công thức 7.1. ðộ ño MRE ño ñộ lệch của một ước lượng ñược thực hiện bởi mô hình. Trong ñó: - MREi: ñộ lệch của ước lượng trên bộ dữ liệu thứ i trong tập dữ liệu lịch sử. - Estimatedi: giá trị ước lượng bởi mô hình trên bộ dữ liệu thứ i. - Actuali: giá trị thực trên bộ dữ liệu thứ i. ðể ñánh giá ñộ chính xác của mô hình ước lượng trên toàn tập dữ liệu lịch sử, ñộ ño MMRE (Mean Magnitude Relative Error) ñược sử dụng. MMRE ño mức ñộ sai lệch trung bình của các ước lượng thực hiện bởi mô hình. MMRE càng nhỏ, ñộ chính xác của mô hình càng cao. 100 11 × − == ∑∑ N i i ii N i i Actual ActualEstimated N MRE N MMRE Công thức 7.2. ðộ ño MMRE ño ñộ chính xác của mô hình trên toàn tập dữ liệu lịch sử. Trong ñó: - MMRE: ñộ lệch trung bình của mô hình trên toàn tập dữ liệu lịch sử. - MREi: ñộ lệch của ước lượng thứ i. - N: số bộ dữ liệu trong tập dữ liệu lịch sử. 7.1.2. ðộ ño PRED Mức ñộ chính xác của mô hình ước lượng ñược ño bằng ñộ ño MMRE. MMRE càng nhỏ, ñộ chính xác của mô hình càng cao. Tuy nhiên không phải lúc nào mô hình có MMRE nhỏ cũng ñều tốt. MMRE là giá trị trung bình của các ước lượng thực hiện bởi mô hình, trong ñó có thể có cả những ước lượng tốt lẫn ước lượng xấu, và chúng bù trừ lẫn nhau. Một mô hình có tỷ lệ ước lượng xấu cao ñược xem là 95 kém ổn ñịnh. Khi ñó, cho dù mô hình ñó có MMRE nhỏ thì nó cũng không thể ñược ñánh giá là tốt. ðộ ño PRED ñược dùng ñể ñánh giá ñộ ổn ñịnh của mô hình ước lượng trên toàn tập dữ liệu lịch sử. PRED ño tỷ lệ các ước lượng của mô hình ñạt một ngưỡng ñộ lệch nhất ñịnh nào ñó. PRED càng lớn, ñộ ổn ñịnh của mô hình càng cao. N KMREP KPRED )( %)( ≤ = Công thức 7.3. ðộ ño PRED ño ñộ ổn ñịnh của mô hình trên toàn tập dữ liệu lịch sử. Trong ñó: - PRED(K%): tỷ lệ ước lượng với ngưỡng K%. - P(MRE<=K): số ước lượng thực hiện bởi mô hình có MRE không quá K%. - N: số bộ dữ liệu trong tập dữ liệu lịch sử. 7.1.3. ðộ ño R2 Ngoài ra, còn một ñộ ño nữa ñược dùng trong quá trình kiểm nghiệm là hệ số tương quan R2 của mô hình. Hệ số tương quan có giá trị nằm trong ñoạn [0, 1], và ñược dùng ñể ñánh giá mức ñộ phù hợp của mô hình so với tập dữ liệu lịch sử. Hệ số tương quan càng gần bằng 1, mức ñộ phù hợp của mô hình càng cao, khi ñó, khả năng mô hình ñưa ra ñược những ước lượng chính xác cũng sẽ cao hơn. ActualEstimated N i ii SSN ActualActualEstimatedEstimated R ×× −×− = ∑ )()( 2 Công thức 7.4. ðộ ño R2 ño hệ số tương quan của mô hình. 96 Trong ñó: - R2: hệ số tương quan của mô hình ước lượng. - Estimatedi: giá trị ước lượng bởi mô hình trên bộ dữ liệu thứ i. - Estimated : giá trị trung bình của giá trị ước lượng trên tập dữ liệu lịch sử. - Actuali: giá trị thực trên bộ dữ liệu thứ i. - Actual : giá trị trung bình của giá trị thực trên tập dữ liệu lịch sử. - SEstimated: ñộ lệch chuẩn của các giá trị ước lượng. - SActual: ñộ lệch chuẩn của các giá trị thực. 7.2. Quy trình kiểm nghiệm Mô hình ước lượng xây dựng từ phương pháp ñề xuất ñược kiểm nghiệm dựa trên một tập dữ liệu lịch sử. Quá trình kiểm nghiệm ñược tiến hành qua N phiên (session). Mỗi phiên bao gồm ba bước như mô tả trong hình 7.1. Hình 7.1. Quy trình kiểm nghiệm mô hình ước lượng ở mỗi phiên. 7.2.1. Chuẩn bị dữ liệu Tập dữ liệu lịch sử ñược chia ngẫu nhiên thành hai phần theo tỷ lệ 80% và 20%. Phần 80% ñược dùng ñể xây dựng mô hình, tức làm ñầu vào cho bộ phát sinh công thức. Phần 20% ñược dùng ñể kiểm nghiệm mô hình thông qua các ñộ ño MMRE, PRED, và R2. ðiều này nhằm ñảm bảo tính khách quan của quá trình kiểm nghiệm: tập dữ liệu dùng ñể kiểm nghiệm khác với tập dữ liệu dùng ñể xây dựng mô hình. Do việc phân chia tập dữ liệu lịch sử mang tính ngẫu nhiên nên kết quả kiểm nghiệm ở mỗi phiên có thể rất khác nhau. Vì vậy, ñể tăng tính ổn ñịnh, quá trình 97 kiểm nghiệm cần ñược tiến hành qua nhiều phiên. Sau khi ñã xem xét tốc ñộ thực hiện kiểm nghiệm, số phiên ñược lựa chọn là N = 10. 7.2.2. Xây dựng mô hình Phần 80% của tập dữ liệu lịch sử ñược dùng làm ñầu vào cho quá trình xây dựng mô hình ước lượng. Bộ phát sinh công thức với nền tảng là công cụ lập trình di truyền làm nhiệm vụ phát sinh công thức cho mô hình. Do tính chất ngẫu nhiên của lập trình di truyền, công thức thu ñược ở mỗi lần phát sinh có thể rất khác nhau, ảnh hưởng ñến kết quả kiểm nghiệm mô hình. Vì vậy, ñể tăng tính ổn ñịnh, quá trình phát sinh sẽ ñược thực hiện K lần, sau ñó lấy công thức tốt nhất làm công thức của mô hình. Sau khi ñã xem xét tốc ñộ thực hiện kiểm nghiệm, số phiên ñược lựa chọn là K = 5. 7.2.3. ðánh giá mô hình Sau khi xây dựng mô hình, phần 20% của tập dữ liệu lịch sử ñược dùng ñể tính các ñộ ño MMRE, PRED, và R2 cho mô hình. Khả năng ước lượng của mô hình sẽ ñược phản ánh thông qua giá trị của những ñộ ño này. Trong trường hợp tập dữ liệu lịch sử dùng ñể kiểm nghiệm ñược thu thập theo chuẩn của một mô hình ước lượng có sẵn từ trước (ví dụ mô hình COCOMO), mô hình ñó sẽ ñược tinh chỉnh và ñem so sánh với mô hình xây dựng ñược. 7.3. Các thông số kiểm nghiệm 7.3.1. Tập dữ liệu lịch sử Trong lĩnh vực ước lượng công thực hiện phần mềm, các tập dữ liệu lịch sử ñóng một vai trò hết sức quan trọng. Nó là tiền ñề ñể xây dựng nên các mô hình ước lượng, tinh chỉnh các thông số của mô hình hiện có, hoặc là một nguồn thông tin tham khảo quan trọng về khả năng của ñội ngũ phát triển phần mềm, ñể từ ñó các chuyên gia ñưa ra những nhận ñịnh cho dự án phần mềm hiện tại. 98 Tuy nhiên, những tập dữ liệu lịch sử thường không ñược công bố rộng rãi. Nó ñược xem là thông tin mật của các công ty phần mềm. Một số ñược bán với giá cao cho những ai muốn truy xuất vào dữ liệu của nó. Luận văn thu thập ñược một vài tập dữ liệu lịch sử ñược công bố công khai trong cộng ñồng và tiến hành kiểm nghiệm phương pháp ñề xuất trên những tập dữ liệu này. Bảng 7.1. Các tập dữ liệu lịch sử công khai dùng trong kiểm nghiệm. STT Tập dữ liệu lịch sử Số dự án Mô hình ước lượng sử dụng 1 NASA 93 COCOMO 81 2 COCOMO81 63 COCOMO 81 3 Desharnais 81 Không 7.3.2. Thông số bộ phát sinh công thức Bảng 7.2 mô tả các thông số bộ phát sinh công thức ñược sử dụng trong quá trình kiểm nghiệm. ðây là những thông số tổng quát ñiều khiển việc phát sinh công thức bằng lập trình di truyền. Ngoài ra, còn một số thông số chi tiết ñược gán giá trị mặc ñịnh ñể ñạt kết quả tối ưu. 99 Bảng 7.2. Thông số bộ phát sinh công thức dùng trong kiểm nghiệm. STT Thông số Giá trị Ý nghĩa 1 Kích thước quần thể 500 Kích thước quần thể vừa ñủ ñể ñạt ñộ ña dạng cần thiết mà tốc ñộ tiến hóa không quá chậm. 2 Số thế hệ tiến hóa 10 Số thế hệ tiến hóa không ảnh hưởng nhiều ñến kết quả. 3 Tỷ lệ lai ghép 80% Tỷ lệ lai ghép do Koza ñề xuất. 4 Tỷ lệ ñột biến 1% Tỷ lệ chọn lọc do Koza ñề xuất. 5 Cách thức chọn lọc Tournament Cách thức chọn lọc cho kết quả tốt và có tốc ñộ nhanh. 6 Hàm thích nghi MMRE Những công thức có tổng ñộ lệch càng nhỏ càng thích nghi cao. 7 Tập toán tử F +, -, *, /, ^, exp 8 Tập toán hạng T Hằng, biến 9 Cách thức khởi tạo Grow Cách thức khởi tạo không ảnh hưởng nhiều ñến kết quả. Thuật toán Grow cho tốc ñộ khởi tạo nhanh. 10 ðộ sâu khởi tạo 5 ðộ sâu khởi tạo vừa ñủ ñể ñạt ñộ ña dạng cần thiết mà không ảnh hưởng ñến tốc ñộ khởi tạo. 11 ðộ sâu tối ña 10 ðộ sâu cây biểu thức vừa ñủ ñể ñạt ñộ ña dạng cần thiết mà không ảnh hưởng lớn ñến tốc ñộ tiến hóa. 100 7.4. Kết quả kiểm nghiệm trên một số tập dữ liệu lịch sử 7.4.1. Tập dữ liệu NASA Phần này trình bày kết quả kiểm nghiệm trên tập dữ liệu NASA. Tập dữ liệu này bao gồm 93 dự án phần mềm của Cơ quan Hàng không và Vũ trụ Hoa Kỳ (NASA) ñược thu thập theo mô hình COCOMO 81. Do ñây là tập dữ liệu thu thập theo mô hình có sẵn, mô hình COCOMO sẽ ñược tinh chỉnh và so sánh với mô hình xây dựng bởi phương pháp ñề xuất. Dạng của mô hình COCOMO sẽ trở thành thông tin tùy biến truyền vào bộ phát sinh công thức trong quá trình xây dựng mô hình. Kết quả kiểm nghiệm ñược mô tả ở bảng 7.3. Bảng 7.3. Kết quả kiểm nghiệm trên tập dữ liệu NASA. MMRE PRED(30%) R2 Session COCOMO GP COCOMO GP COCOMO GP 1 0.7782 0.6074 0.2778 0.4444 0.9392 0.9391 2 0.3412 0.3347 0.4444 0.3889 0.6929 0.6964 3 0.4646 0.382 0.5 0.6667 0.5994 0.6024 4 0.7999 0.6717 0.3333 0.5556 0.9301 0.9544 5 0.6274 0.4126 0.2778 0.5 0.8722 0.8826 6 1.2543 0.8663 0.4444 0.6667 0.8849 0.9186 7 0.3794 0.4044 0.3889 0.7222 0.9393 0.9448 8 0.9562 0.5547 0.5 0.7222 0.8374 0.8497 9 0.3689 0.3866 0.4444 0.5556 0.8713 0.8688 10 0.4225 0.3638 0.5 0.5 0.6704 0.7327 7.4.1.1. ðánh giá ñộ ño MMRE ðộ ño MMRE ñược dùng ñể ñánh giá ñộ chính xác của mô hình. Hình 7.2 so sánh kết quả thu ñược giữa mô hình COCOMO ñã tinh chỉnh và mô hình xây dựng bởi phương pháp ñề xuất trên tập dữ liệu NASA. 101 MMRE: COCOMO vs GP 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1 2 3 4 5 6 7 8 9 10 Session M M R E COCOMO GP Hình 7.2. So sánh ñộ ño MMRE giữa hai mô hình trên tập dữ liệu NASA. Trong hầu hết các phiên thử nghiệm, mô hình xây dựng bởi phương pháp ñề xuất có MMRE tốt hơn mô hình COCOMO ñã tinh chỉnh. Một vài trường hợp cho kết quả tốt hơn ñến 30%. Mức trung bình là 15%. ðiều này chứng tỏ với tập dữ liệu NASA, mô hình xây dựng bởi phương pháp ñề xuất có khả năng ước lượng chính xác hơn so với mô hình COCOMO ñã tinh chỉnh. 7.4.1.2. ðánh giá ñộ ño PRED ðộ ño PRED ñược dùng ñể ñánh giá ñộ ổn ñịnh của mô hình. Ở ñây, PRED(30%) ñược sử dụng. Hình 7.3 so sánh kết quả thu ñược giữa mô hình COCOMO ñã tinh chỉnh và mô hình xây dựng bởi phương pháp ñề xuất trên tập dữ liệu NASA. 102 PRED: COCOMO vs GP 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 1 2 3 4 5 6 7 8 9 10 Session P R E D COCOMO GP Hình 7.3. So sánh ñộ ño PRED giữa hai mô hình trên tập dữ liệu NASA. Trong hầu hết các phiên thử nghiệm, mô hình xây dựng bởi phương pháp ñề xuất có PRED(30%) tốt hơn hẳn mô hình COCOMO ñã tinh chỉnh. Một vài trường hợp cho kết quả tốt hơn ñến trên 20%. Mức trung bình là 15%. ðiều này chứng tỏ với tập dữ liệu NASA, mô hình xây dựng bởi phương pháp ñề xuất có ñộ ổn ñịnh cao hơn hẳn so với mô hình COCOMO ñã tinh chỉnh. 7.4.1.3. ðánh giá ñộ ño R2 ðộ ño R2 ñược dùng ñể ñánh giá khả năng ước lượng tương lai của mô hình. Hình 7.4 so sánh kết quả thu ñược giữa mô hình COCOMO ñã tinh chỉnh và mô hình xây dựng bởi phương pháp ñề xuất trên tập dữ liệu NASA. 103 R2: COCOMO vs GP 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Session R 2 COCOMO GP Hình 7.4. So sánh ñộ ño R2 giữa hai mô hình trên tập dữ liệu NASA. Mô hình xây dựng bởi phương pháp ñề xuất có ñộ ño R2 ngang ngửa với mô hình COCOMO ñã tinh chỉnh và trong khoảng chấp nhận ñược ở một mô hình ước lượng. ðiều này chứng tỏ với tập dữ liệu NASA, mô hình xây dựng bởi phương pháp ñề xuất tuy không cải thiện ñược hệ số tương quan, nhưng hoàn toàn có thể ñược dùng thay thế mô hình COCOMO ñã tinh chỉnh. 7.4.2. Tập dữ liệu COCOMO81 Phần kết quả kiểm nghiệm trên tập dữ liệu COCOMO81 cũng cho ra kết quả tương tự. Với các ñộ ño ñược sử dụng, mô hình xây dựng bởi phương pháp ñề xuất ñiều cho kết quả ngang ngửa hoặc tốt hơn mô hình COCOMO ñã tinh chỉnh. ðiều này chứng tỏ trên các tập dữ liệu ñược thu thập theo mô hình COCOMO, mô hình xây dựng bởi phương pháp ñề xuất hoàn toàn có thể ñược dùng như là một giải pháp thay thế cho mô hình COCOMO ñã tinh chỉnh. Do tính chất tương tự tập dữ liệu NASA, phần kết quả kiểm nghiệm trên tập dữ liệu COCOMO81 ñược trình bày ở phần phụ lục A của luận văn. 104 7.4.3. Tập dữ liệu Desharnais Phần này trình bày kết quả kiểm nghiệm trên tập dữ liệu Desharnais. Tập dữ liệu này bao gồm 81 dự án phần mềm của Hiệp hội Tin học Canada thu thập ñược. ðịa chỉ tải về tập dữ liệu Desharnais ở website: ðiểm ñặc biệt của tập dữ liệu này là các thông số dự án của nó không tuân theo một mô hình ước lượng có sẵn nào. Do không bị ràng buộc bởi một mô hình ước lượng có sẵn, tập dữ liệu này thật sự hữu ích trong việc kiểm nghiệm mô hình ước lượng xây dựng bởi phương pháp ñề xuất một cách hoàn toàn mới không có thông tin gợi ý. Tập dữ liệu Desharnais có tất cả 8 thông số dự án liên quan ñến công thực hiện. Luận văn trích ra bốn thông số có ý nghĩa nhất ñược mô tả ở bảng 7.4 và xây dựng mô hình ước lượng hoàn toàn mới không có thông tin gợi ý xung quanh các thông số này. Bảng 7.4. Các thông số trích ra từ tậpDesharnais dùng trong kiểm nghiệm. STT Tên thông số Ý nghĩa 1 TeamExp Kinh nghiệm của ñội ngũ phát triển dự án phần mềm. 2 Transactions Số lượng các thao tác ñọc ghi dữ liệu. 3 Entities Kích thước dữ liệu. 4 PointsAdjust Số ñiểm chức năng ñã tinh chỉnh. Kết quả kiểm nghiệm ñược mô tả ở bảng 7.5. 105 Bảng 7.5. Kết quả kiểm nghiệm trên tập dữ liệu Desharnais. MMRE PRED(30%) R2 Session GP GP GP 1 0.7365 0.2 0.5266 2 0.6026 0.2667 0.9015 3 0.6484 0.2667 0.5983 4 0.6008 0.2 0.9215 5 0.6135 0.2 0.6846 6 0.557 0.5333 0.6055 7 0.3866 0.4 0.8608 8 0.5283 0.2 0.7315 9 0.6253 0.3333 0.5227 10 0.6129 0.2667 0.4909 7.4.3.1. ðánh giá ñộ ño MMRE ðộ ño MMRE ñược dùng ñể ñánh giá ñộ chính xác của mô hình. Hình 7.5 thể hiện MMRE của mô hình xây dựng bởi phương pháp ñề xuất trên tập dữ liệu Desharnais. 106 MMRE: GP 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 1 2 3 4 5 6 7 8 9 10 Session M M R E GP Hình 7.5. ðộ ño MMRE của mô hình ñược xây dựng trên tập dữ liệu Desharnais. Mô hình xây dựng bởi phương pháp ñề xuất có MMRE trung bình từ 0.5 ñến 0.7, tức có mức sai lệch ước lượng trong khoảng từ 50% - 70%. ðây là mức sai lệch chấp nhận ñược ở một mô hình ước lượng dựa trên công thức. ðiều này chứng tỏ với tập dữ liệu Desharnais, khi không có thông tin gợi ý, mô hình xây dựng bởi phương pháp ñề xuất có ñộ chính xác ở mức thấp hơn so với khi có thông tin gợi ý, nhưng vẫn nằm trong mức chập nhận ñược và hoàn toàn khả dụng. 7.4.3.2. ðánh giá ñộ ño PRED ðộ ño PRED ñược dùng ñể ñánh giá ñộ ổn ñịnh của mô hình. Ở ñây, PRED(30%) ñược sử dụng. Hình 7.6 thể hiện PRED của mô hình xây dựng bởi phương pháp ñề xuất trên tập dữ liệu Desharnais. 107 PRED: GP 0 0.1 0.2 0.3 0.4 0.5 0.6 1 2 3 4 5 6 7 8 9 10 Session P R E D GP Hình 7.6. ðộ ño PRED của mô hình ñược xây dựng trên tập dữ liệu Desharnais. Mô hình xây dựng bởi phương pháp ñề xuất có PRED(30%) trung bình là 25%, ngang ngửa với mô hình xây dựng ñược theo hướng tiếp cận lập trình di truyền của của Colin và Martin [10]. ðiều này chứng tỏ với hướng tiếp cận lập trình di truyền, nếu không có thông tin gợi ý về dạng công thức, mô hình xây dựng ñược có ñộ ổn ñịnh không cao như khi có thông tin gợi ý, nhưng vẫn ở mức chấp nhận ñược. Trong tương lai, cần có thêm những nghiên cứu ñể khắc phục vấn ñề này. 7.4.3.3. ðánh giá ñộ ño R2 ðộ ño R2 ñược dùng ñể ñánh giá khả năng ước lượng tương lai của mô hình. Hình 7.7 thể hiện R2 của mô hình xây dựng bởi phương pháp ñề xuất trên tập dữ liệu Desharnais. 108 R2: GP 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 6 7 8 9 10 Session R 2 GP Hình 7.7. ðộ ño R2 của mô hình ñược xây dựng trên tập dữ liệu Desharnais. Mô hình xây dựng bởi phương pháp ñề xuất có ñộ ño R2 không cao như mong ñợi, ở mức dưới trung bình. ðiều này chứng tỏ với hướng tiếp cận lập trình di truyền, nếu không có thông tin gợi ý về dạng công thức, mô hình xây dựng ñược có hệ số tương quan thấp. Trong tương lai, cần có thêm những nghiên cứu ñể khắc phục vấn ñề này.