1

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN THỊ MAI
DỰ ĐOÁN LỖI PHẦN MỀM SỬ DỤNG
KỸ THUẬT HỌC MÁY
Chuyên ngành: Truyền dữ liệu và mạng máy tính
Mã số: 60.48.15 - 0009
TÓM TẮT LUẬN VĂN THẠC SĨ
Người hướng dẫn khoa học: PGS. TS TỪ MINH PHƯƠNG HÀ NỘI - 2010
2 Mở đầu
Giới thiệu
Xây dựng các dự án phần mềm thành công luôn là mối quan tâm hàng đầu đối với
mọi tổ chức doanh nghiệp, nhất là doanh nghiệp công nghiệp công nghệ thông tin. Đặc
biệt quan trọng là quá trình quản lý, kiểm soát tiến độ và đảm bảo chất lượng dự án.
Các vấn đề thường xảy ra đối với một dự án phần mềm:
 Thời gian thực hiện dự án vượt mức dự kiến.
 Nguồn lực thực hiện dự án vượt mức kiểm soát.
 Kết quả của dự án không như mong muốn .

vào nghiên cứu các ảnh hưởng tới độ chính xác khi dự đoán lỗi khi kết hợp các dạng đặc
trưng phần mềm khác nhau (gồm: OO, Delta, Process). Mục đích quan trọng là nghiên
cứu và áp dụng phương pháp rừng ngẫu nhiên (Random Forest) cho bài toán dự đoán
lỗi, đây là một mô hình phân loại/ hồi quy với nhiều ưu điểm sẽ được trình bày chi tiết
trong chương 2 của luận văn. Luận văn cũng đưa ra các kết quả khi thử nghiệm cho một
hệ thống ứng dụng Java có khả năng chứa lỗi dựa trên bộ dữ liệu có sẵn và đánh giá theo
các tiêu chí đánh giá hiệu quả khác nhau (gồm: CE, ROC) [3]. Chương trình sử dụng dữ
liệu theo nguồn: http://bug.inf.usi.ch.
Chương 1
TỔNG QUAN VỀ DỰ ĐOÁN LỖI PHÂN MỀM

Chương này trình bày tổng quan về dự đoán lỗi trong phần mềm và đặc biệt áp
dụng cho một hệ thống Java có khả năng chứa nhiều lỗi. Trong phạm vi quản lý dự
án lợi ích đem lại từ việc dự đoán lỗi phần mềm đó là làm giảm nguồn lực của dự
án, thay vì việc phải kiểm tra lỗi cho tất cả các lớp trong hệ thống bao gồm các lớp
chứa lỗi và không chứa lỗi thì sẽ dự đoán các lớp nào có khả năng chứa lỗi sau đó
tập trung nguồn lực kiểm tra trên các lớp được dự đoán là chứa lỗi đó. Hiện trên
thế giới đã có một số kỹ thuật xây dựng mô hình dự đoán lỗi phần mềm tuy nhiên
với mỗi kỹ thuật lại có các ưu nhược điểm khác nhau, trong chương này cũng sẽ
trình bày các ưu nhược điểm của các kỹ thuật này. Cuối chương sẽ trình bày một
số dạng đặc trưng của phần mềm đó chính là các tham số được sử dụng trong quá
trình dự đoán lỗi.
1.1. DỰ ĐOÁN LỖI PHẦN MỀM
1.1.1. Giới thiệu
Trong thuật ngữ của chuyên ngành kỹ nghệ phần mềm, Quản lý dự án phần mềm là
các hoạt động trong lập kế hoạch, giám sát và kiểm soát tài nguyên dự án (ví dụ như chi
phí, con người), thời gian thực hiện, các rủi ro trong dự án và cả quy trình thực hiện dự
4

án; nhằm đảm bảo thành công cho dự án. Trong đó đảm bảo chất lượng dự án phần mềm

nhiều nguồn lực để kiểm tra và sửa lỗi cho toàn bộ các lớp được sinh ra trong hệ thông
thì sẽ sử dụng kỹ thuật dự đoán lỗi để xác định những lớp nào có lỗi từ đó tập trung sửa
lỗi cho lớp đó sẽ giảm được 50% chi phí thực hiện cho việc phát triển và kiểm tra lỗi
5

ngay trong giai đoạn lập trình. Hiện nay có khá nhiều kỹ thuật được sử dụng để dự đoán
lỗi nhưng chưa có đánh giá cụ thể nào về kỹ thuật dự đoán nào là hiệu quả nhất mà sẽ
tùy thuộc vào các tiêu chí được áp dụng để đánh giá cho mô hình dự đoán. Luận văn
cũng sẽ tập trung vào một kỹ thuật dự đoán dựa trên học máy để xây dựng và thử
nghiệm cho mô hình dự đoán lỗi của một hệ thống phần mềm.
1.2. CÁC PHƯƠNG PHÁP DỰ ĐOÁN LỖI PHẦN MỀM
Có một số cách tiếp cận khác nhau trong việc dự đoán một thành phần nào có của
hệ thống phần mềm có lỗi hay không. Do luận văn chỉ tập trung vào cách tiếp cận dựa
trên học máy nên trong phần này sẽ giới thiệu ngắn gọn về một số phương pháp học máy
có thể sử dụng để dự đoán số lỗi trong phần mềm.
1.2.1. Thuật toán cây quyết định
Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự đoán (predictive
model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về
giá trị mục tiêu của sự vật/hiện tượng. Kỹ thuật học máy dùng trong cây quyết định được
gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định.
Cây quyết định là cây mà những nút bên trong của nó bao gồm việc kiểm tra một thuộc
tính xác định và những nút lá của nó đưa ra sự phân lớp mà được áp dụng cho tất cả các
mẫu đạt đến nút lá, hoặc một tập của sự phân lớp, hoặc một xác xuất phân tán qua tất cả
các lớp có thể. Để phân lớp cho một mẫu chưa biết, nó được định tuyến xuống dưới cây
dựa theo giá trị của thuộc tính được kiểm tra lần luợt theo các nút, và khi một nút lá
được tìm thấy một mẫu được phân lớp dựa theo lớp mà được gán cho nút lá [9].
Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính toán các xác
suất có điều kiện.
Thuật toán cây quyết định là một trong các thuật toán mà được sử dụng rộng rãi
nhất trong các thuật toán học máy trong việc xây dựng các mẫu phân lớp từ các nguồn

1
z
e
z
e





1.2.3. Kỹ thuật mạng nơ ron (neural net works)
Mạng nơ ron nhân tạo (Artificial neural network – ANN) là một mô phỏng xử lý
thông tin, được nghiên cứu ra từ hệ thống thần kinh của sinh vật, giống như bộ não để
xử lý thông tin. Nó bao gồm số lượng lớn các mối gắn kết cấp cao để xử lý các yếu tố
làm việc trong mối liên hệ giải quyết vấn đề rõ ràng [13]. Thuật toán máy tính mô phỏng
các kiến trúc sinh học này thường được gọi là mạng nơron nhân tạo để phân biệt với các
phần mềm trong cơ thể động vật. ANNs hoạt động giống như bộ não con người, được
học bởi kinh nghiệm, lưu những kinh nghiệm hiểu biết và sử dụng trong những tình
huống phù hợp. Đầu tiên ANN được giới thiệu năm 1943 bởi nhà thần kinh học Warren
McCulloch và nhà logic học Walter Pits. Nhưng với những kỹ thuật trong thời gian này
chưa cho phép họ nghiên cứu được nhiều.
Mạng nơron hoạt động dựa trên nguyên lý học máy. Thông qua các mẫu có sẵn và
tập mục tiêu (với phương pháp học có thầy) để đưa ra kết luận khi có một mẫu mới được
đưa vào. Mạng nơron nhân tạo là một kỹ thuật mô phỏng lại bộ não và hệ thần kinh của
con người.Nó cũng có khả năng học từ các kinh nghiệm trong quá khứ, tổng quát hóa
7

các kinh nghiệm này để đưa ra một nhận định mới nhờ rút ra được các đặc trưng cơ bản
của tập mẫu. Các việc này được thực hiện thông qua việc xử lý tín hiệu giữa các nơron
cùng với các trọng số của chúng.

và có hệ thống trong hệ thống quản lý cấu hình hoặc quản lý thay đổi.
8

Chương 2
DỰ ĐOÁN LỖI PHẦN MỀM SỬ DỤNG
KỸ THUẬT HỌC MÁY

Trong chương này sẽ trình bày về thuật toán được áp dụng để xây dựng mô
hình dự đoán phần mềm, trước đó sẽ trình bày tổng quan về kỹ thuật cây quyết định
trong học máy, các nhược điểm của thuật toán này và cách khắc phục bằng cách
sử dụng thuật toán Random Forest (thuật toán rừng ngẫu nhiên). Trình bày chi tiết
lịch sử ra đời, ưu điểm của thuật toán này trong kỹ thuật dự đoán lỗi phần mềm.
Phần tiếp sẽ trình bày các phương pháp đánh giá hiệu quả mô hình dự đoán lỗi.
Với các phương pháp đánh giá này vẫn chưa có tài liệu hoặc nghiên cứu nào
khẳng định phương pháp nào là tốt nhất mà còn phụ thuộc vào thực tế của một hệ
thống quản lý chất lượng của một tổ chức.
2.1. NGUỒN GỐC RA ĐỜI CỦA THUẬT TOÁN
2.1.1. Nhược điểm của cây quyết định
Trong lĩnh vực nghiên cứu về khai phá dữ liệu nói chung cũng như trong nghiên cứu
về các thuật toán phân lớp nói riêng, vấn đề xử lý dữ liệu lớn ngày càng trở thành vấn đề
cấp thiết và đóng vai trò chủ đạo trong việc giải quyết các bài toán thực tế. Phần lớn các
thuật toán phân lớp đã phát triển chỉ có thể giải quyết với một số lượng dữ liệu có hạn
cũng như với một độ phức tạp dữ liệu giới hạn được. Trong khi đó dữ liệu thu được càng
trở nên đa dạng phong phú nhờ sự phát triển mạnh mẽ của khoa học.
Mặc dù kỹ thuật cây quyết định là công cụ khai phá dữ liệu mạnh trong lĩnh vực học
máy tuy nhiên kỹ thuật này không hoàn toàn hoàn hảo và thích hợp với một số loại vấn
đề. Các cây phân loại dữ liệu có thể ổn định và có sự biên đổi nhỏ (các biến đổi này
được tạo ra một cách ngẫu nhiên) có thể là cơ sở cho sự khác nhau của các cây tìm kiếm
được sinh ra. Đây là đặc điểm đặc biệt trong các trường hợp mà các chia tách tối ưu cho
các biến khác nhau gần với các biến khác về mặt giá trị. Trong tường hợp này, một biến

2.2.3. Thuật toán Random Forest
Về cơ bản thuật toán Random Forest (RF) – rừng ngẫu nhiên dựa trên kỹ thuật cây
quyết định. Ý tưởng của RF chúng ta có thể liên tưởng tới việc bầu cử theo nguyên tắc
phổ thông đầu phiếu. Nếu sử dụng một cây quyết định chẳng khác nào việc bầu cử mà
chỉ có 1 người bỏ phiếu. Việc sinh các cây quyết định từ một mẫu dữ liệu nhằm đa dạng
hoá các “phiếu bầu” (giống như việc mọi thành phần, tầng lớp, giai cấp đều được đi bỏ
phiếu) cho kết luận. Việc áp dụng các kỹ thuật sinh ra các mẫu dữ liệu hay việc lựa chọn
rẽ nhánh ngẫu nhiên sẽ tạo ra các cây “dị tật” trong rừng (giống việc cho phép công dân
không cần phân biệt trình độ học vấn, sức khỏe đi bầu cử). Càng nhiều loại hình, càng
nhiều phiếu bầu sẽ cung cấp cho chúng ta cái nhìn đa chiều, chi tiết hơn và do đó kết
luận sẽ có tính chính xác, gần với thực tế hơn.
10

Định nghĩa: Một RF là một bộ phân loại gồm một tập các bộ phân loại có câu hình cây
{ h(x, ⊖

), k=1,…} trong đó { ⊖

} là các vecto ngẫu nhiên, độc lập, có cùng phân bố
xác suất, mỗi cây bầu cử một phiếu cho lớp phổ biến nhất tại đầu vào x [5].
2.2.4. Đặc tính của thuật toán Random Forest
Đối với rừng ngẫu nhiên, cận trên sẽ bắt nguồn cho các lỗi phát sinh dưới dạng hai
tham số, là cách xác định tính chính xác (Strength - Accuracy) và tính tương quan
(hay còn gọi là độ nhạy - Correlation) của các bộ phân loại riêng lẻ có trong rừng ngẫu
nhiên.
Hàm tương quan như sau:
mr(X, Y) = 
Ө
(h(X, Ө) = Y) –


nhau. Nếu tính tương quan giữa các cây trong rừng càng cao thì độ chính xác sẽ giảm.
Độ chính xác và độ nhạy nếu đứng tách nhau thì không có ý nghĩa. Hai độ đo này có sự
tương quan nghịch: độ chính xác càng cao thì độ nhạy càng thấp và ngược lại. Khi độ
chính xác hoặc độ nhạy đạt giá trị tối thiểu thì cũng là lúc hệ thống mất khả năng phân
loại. Vì vậy người ta phải kết hợp hai độ đo trên trong một độ đo thống nhất, vấn đề đặt
ra là làm sao để có thể cân bằng hai tham số này khi thực hiện phân loại để đạt hiệu quả
cao nhất. Theo công thức độ chính xác là tỷ lệ phần trăm các lớp phân loại đúng hoặc
các lớp phân loại không lỗi: (TP/ (TP + FP)). Độ nhạy là tỷ lệ phần trăm các lớp phân
11

loại sai hoặc các lớp phân loại lỗi: (TP/ (TP + FN)). Ta có bảng mô tả mối tương quan
hai tiêu chí này như ở dưới.
Thực tế
Thuộc

Không thuộc

Mô hình dự đoán

Thuộc TP
i
FP
i

Không thuộc

FN
i
TN
i

p


;
ii
i
i
FNTP
TP
r



Độ chính xác chung là: A =
FN
FP
TN
TP
FNTP



Độ sai chung là: E = 1 – A

2.2.5. Phân tích thuật toán
Để cải thiện tính chính xác trong phân lớp, kỹ thuật rừng ngẫu nhiên bổ sung một
số phương pháp để tối ưu hóa độ nhạy nhưng vẫn đảm bảo duy trì độ chính xác. Sự ảnh
hưởng của hai tiêu chí này cũng dẫn đến sự thay đổi của các lỗi phát sinh trong quá trình
phân loại. Có nhiều phương pháp tạo rừng ngẫu nhiên đã được nghiên cứu và thử
nghiệm với tập huấn luyện khác nhau. Với phương pháp rẽ nhánh ngẫu nhiên có hiệu

sự thay đổi trong các tập mã nguồn thực hiện bởi các lập trình viên khi họ cập nhật hoặc
sửa lỗi. Đối với một hệ thống lớn, số lượng các lớp nhiều, mỗi lớp chưa nhiều hàm phức
tạp thì quá trình đánh giá sự thay đổi sẽ trở nên khó khăn. Do đó đối với các hệ thống
phần mềm lớn cần phải có các hệ thống hộ trợ quản lý mã nguồn do các lập trình viên
tạo ra. Các hệ thống này sẽ lưu trữ các bản ghi chứa dữ liệu lịch sử cần thiết sử dụng
cho các lần đánh giá ví dụ: lịch sử tạo mới hoặc cập nhật một tập tin, thời gian thay đổi,
tên lập trình viên đã thay đổi, chi tiết thông tin thay đổi như số dòng mã được thêm vào
hay xóa đi.
2.3.2. Phương pháp đánh giá sự thay đổi
Để đánh giá sự thay đổi trong tập mã nguồn, có thể áp dụng kỹ thuật trong lý thuyết
thông tin để đo lượng ngẫu nhiên entropy. Nếu chia quá trình thay đổi hệ thống thành
các chu kỳ ví dụ theo tuần hoặc theo tháng hoặc theo năm, và gọi P là xác suất tập tin
thứ i được thay đổi trong một chu kỳ đã xác định thì P chính là tỷ lệ giữa tổng sổ lần
thay đổi trong một chu kỳ của một tập tin trên tổng số lần thay đổi của tất cả các tập tin
trong hệ thống trong một chu kỳ. Ví dụ một hệ thống có 10 tập tin thay đổi, tập tin A chỉ
bị thay đổi một lần trong một chu kỳ thì 

=


= 0.1, như vậy nếu P của tập tin A là 1
13

thì tất cả các tập còn lại không bị thay đổi khi đó ta thu được lượng entropy là nhỏ nhất.
Để tính toán sự thay đổi hiệu quả và chính xác hơn, người ta cũng xác định sự thay đổi
các dòng mã dựa vào việc tính toán các dòng mã được thêm vào hoặc xóa đi trong một
chu kỳ của một tập tin.
Để tính entropy H của thay đổi ta có công thức sau:
H(P) =





Trong đó n là số lượng tập tin trong hệ thống, 

 là lượng entropy lớn nhất trong một
phân phối.


≥ 0,

k 1, 2,…., n và
∑




= 1.
Cho một chu kỳ i, với giá trị Entropy 

mà một tập các file, 

bị thay đổi với xác xuất


cho mỗi file j € 

, ta có định nghĩa chu kỳ phức tạp lịch sử (History Complexity
Period Factor- HCP


tập tin bị ảnh hưởng dựa trên tần suất thay đổi trong suốt chu kỳ của chúng. Càng
nhiều tập tinh bị thay đổi, thì càng có nhiều hảnh hưởng bởi đơn vị phức tạp của
chu kỳ i.
 Với 

=

|

|
có nghĩa là phân bố đồng đều sự kết hợp đơn vị phức tạp trong một
chu kỳ của 

giữa tất cả các tập tin được thay đổi trong chu kỳ đó. Càng nhiều
file bị thay đổi, ảnh hưởng của chu kỳ phức tạp trên mỗi tập tin càng giảm.
2.3.3. Tiêu chí ROC (receiver operating characteristic)
Việc đánh giá các mô hình dự đoán lỗi nhằm:
14

 Cung cấp sự so sánh toàn diện giữa các mô hình.
 Đánh giá sự ảnh hưởng của việc chọn lựa tiêu chí đánh giá sẽ tác động đến thứ
hạng của các mô hình đó như thế nào.
Đường cong ROC mô tả lợi ích của việc sử dụng mô hình (đại diện bằng thuộc tính
Dương thật) và chi phí sử dụng mô hình (đại diện bằng thuộc tính Dương giả). Đường
cong ROC cho phép đánh giá hiệu quả của một mô hình nói chung mà không phụ thuộc
vào giá trị ngưỡng cụ thể nào. Phần diện tích phía dưới đường cong ROC (gọi là AUC -
area under the curve) có thể được sử dụng như một thông số thống kê mô tả. Ví dụ nếu
chọn ngẫu nhiên 2 lớp (một lớp lỗi và một lớp không lỗi) để kiểm thử bởi một mô hình
có AUC = 0.85; thu được xác xuất kết quả phát hiện lỗi của lớp lỗi thực sự cao hơn xác
suất phát hiện lỗi của lớp không bị lỗi 0.85 (hay là 85%). Do vậy, giá trị AUC của một

chuẩn hóa như dưới đây:
CE
л
= (CE
л
(model) - CE
л
(baseline))/( CE
л
(optimal) - CE
л
(baseline))
Trong đó, CE
л
(x) là diện tích dưới đường cong x (baseline, model hoặc optimal - tối ưu)
của một л phần trăm NOS cho trước.
Chương 3
THỰC NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ

Trong chương 3, luận văn sẽ trình bày các bước trong quá trình thực thi chương
trình thử nghiệm trên dữ liệu được lấy theo đường dẫn của tác giả bài báo tham
khảo. Đầu tiên sẽ mô tả các bước thu thập dữ liệu từ các công cụ MKS, WebMetric
được tập dữ liệu ban đầu, sau đó phân tích các các đặc trưng trong tập dữ liệu sẽ
đưa ra để phân loại. Mô tả các bước thực nghiệm để đưa ra các kết quả với các
loại biến đầu vào và đánh giá theo các tiêu chí hiệu quả mô hình khác nhau. Từ
các kết quả thu được khi thử nghiệm mô hình, phần cuối luận văn sẽ phân tích các
kết quả theo các tiêu chí để đưa ra phương pháp hiệu quả và phù hợp với hệ thống
quản lý chất lượng của Viettel.
3.1. THU THẬP, PHÂN TÍCH DỮ LIỆU
3.1.1. Thu thập dữ liệu

chứa 17 thuộc tính delta thông tin thay đổi của 2 phiên bản gần nhất tương ứng với 17
thuộc tính hướng đối tượng trong file oo-metric.csv trừ thuộc tính bugs.
3.2. THỰC THI CHƯƠNG TRÌNH
3.2.1. Giới thiệu công cụ thực nghiệm
Phần mềm được sử dụng để thực hiện phân lớp trên các tập dữ liệu ở trên là phần
mềm weka [19]. Tiến hành phân loại bằng thuật toán RF với thuộc tính phân loại được
lựa chọn bugs, tuy nhiên trước khi tiến hành phân loại, chúng ta sẽ phải lựa chọn chế độ
kiểm thử để xây dựng tập kiểm thử và tập huấn luyện.
Luận văn xây dựng 7 mô hình dự đoán lỗi dựa trên tập dữ liệu huấn luyện ở phần
trên theo hai tiêu chí ROC, CE
0.01
, CE
0.05
, CE
0.20
, CE
1.00
với 7 tổ hợp biến Process, OO,
17

Delta, Process + OO, OO + Delta, Process + Delta, Total. Đánh giá theo tiêu chí ROC:
Khi chạy chương trình lần lượt với hai độ đo Process và OO.
- Đánh giá theo ROC: Khi chạy chương trình lần lượt với 7 tập độ đo Process và
OO, ta thu được bảng giá trị ROC lần lượt của từng mô hình như sau:
Bảng 3.1. Tổng hợp kết quả ROC theo các biến
Tổ hợp biến ROC
Process 0.734
OO 0.83
Delta 0.82
Process+OO 0.843



=
1
.
00

Process 0.6309 0.6309 0.6309 0.2066
OO 0.4102 0.4102 0.4102 0.2066
Delta 0.4553 0.4553 0.4553 0.2066
Process+OO 0.4072 0.4072 0.4072 0.2066
OO+Delta 0.4012 0.4012 0.4012 0.2066
Delta+Process 0.4302 0.4302 0.4302 0.2066
Total 0.3941 0.3941 0.3941 0.2066
Với  = 1.00 khi chúng ta có thể thấy chi phí của tất cả các mô hình đều như nhau, bởi
vì chúng ta cùng lựa chọn thuộc tính phân lớp cho mô hình tất cả các mô hình đều cùng
18

là thuộc tính bugs. Các mô hình khi đều có ngưỡng  lớn hơn 0.20, khi  nhỏ hơn 0.20
thì chi phí của mô hình là đồng nhất. Có thể nhận thấy với  ở dưới ngưỡng 0.20 thì CE
của mô hình thương ứng với tập độ đo Process là cao nhất 0.6309, còn đối với các tập độ
đo còn lại giá trị này gần như tương đương nhau từ khoảng 0.3941 đến 0.4302.

3.2.2. Phân tích đánh giá
Theo các kết quả thực nghiệm ở trên, với trường hợp thực thi phân loại trên tổ hợp
các biến Process + Delta + OO theo cả 2 tiêu chí ROC và CE đều đạt kết quả tốt hơn khi
thực hiện phân loại chỉ trên 1 hoặc 2 biến riêng biệt.
Với đặc thù của hệ thống quản lý phần mềm của Trung tâm phần mềm – Viettel có
đầy đủ các công cụ để đánh giá các tham số như yêu cầu về dữ liệu đầu vào của mô hình
phân loại: