Chương 1: Trình bày tổng quan về van dé bài toán dự đoán kết quả học tập của sinh viên. Đồng thời cũng đưa ra được mục tiêu, nội dung, phương pháp nghiên cứu và giới thiệu các nghiên cứu liên quan đã được thực hiện trước đó bao gồm cả những nghiên cứu trong và ngoài nước. Chương 2: Giới thiệu về khai thác dữ liệu chuỗi, đưa ra cái nhìn khái quát về lĩnh vực khai thác luật tuần tự trên chuỗi, phát biểu bài toán khai thác luật tuần tự qua hai giai đoạn. Trong đó, luận văn mô ta chi tiết và đưa bài toán cụ thể để khai thác luật băng giải thuật khai thác luật tuần tự đầy đủ IMSR_PreTree và giải thuật khai thác luật tuần tự không dư thừa MNSR_PreTree.
Chương 3: Tiến hành hiện thực việc cài đặt các thuật toán khai thác luật tuần tự đầy đủ và không dư thừa đã chọn ở chương hai và áp dụng hai thuật toán này để khai thác luật trên CSDL tong hop dé danh gia hiệu suat hoat động cua hai thuật toán này. Chương 4: Phát biểu bài toán dự đoán kết quả học tập của sinh viên. Dựa trên bài toán đó, luận văn đề xuất một mô hình áp dụng trong việc dự đoán kết quả học tập của sinh viên; khai thác luật tuần tự trên chuỗi kết quả học tập của những sinh viên đã tốt nghiệp; tiễn hành thực nghiệm xây dựng ứng dụng dự đoán kết quả học tập của sinh viền. Chương 5: Kết luận, nhận xét và hướng phát triển của đề tài.
CO SO LY THUYET Lĩnh vực khai thác dữ liệu trên CSDL chuỗi là một trong những lĩnh vực đã và đang được nhiều nhà khoa học tập trung nghiên cứu. Khai thác dữ liệu chuỗi tuần tự được dé xuất từ năm 1995 [2], cho đến nay nhiều kết quả nghiên cứu trong lĩnh vực này được công bồ và ứng dụng thực tiễn [5], [8]. Khai thác mẫu tuần tự trong CSDL chuỗi là xác định những mẫu mà sự xuất hiện của chúng trong CSDL thỏa ngưỡng hỗ trợ tối thiểu. Khai thác mẫu tuần tự được ứng dụng trong nhiều lĩnh vực thực tế như: phân tích thị trường, phân tích mẫu truy cập Web, dự đoán nhu cầu mua săm của khách hàng.
Từ tập dữ liệu mẫu tuần tự có thể dùng nhiều thuật toán khác nhau khai thác được luật tuần tự, luật tuần tự được xem như việc biéu diễn mối quan hệ giữa hai loạt sự kiện, loạt sự kiện nay sẽ xảy ra sau loạt sự kiện kia. Luật tuần tự mở rộng khả năng sử dụng và ý nghĩa biểu đạt của mẫu tuần tự, thé hiện tri thức tiềm ân của đữ liệu tuần tự. Dir liệu chuôi Dữ liệu chuỗi rất phố biến trong cuộc sống của chúng ta, ví dụ như những việc làm trong một ngày là một chuỗi các hoạt động hàng ngày. Nếu người dùng đầu tư vào các công ty, chuỗi dữ liệu liên quan đến lịch sử tăng giảm giá trị cổ phiếu của công ty đó là một trong những mối quan tâm.
Trong lĩnh vực y học, chuỗi tuần tự chính là các chuỗi dữ liệu sinh học bao gồm các chuỗi DNA và RNA. Đặc điểm dữ liệu chuỗi Dữ liệu chuỗi có một số đặc điểm riêng biệt so với các loại dữ liệu khác. Do đó, khai thác dữ liệu chuỗi đặt ra nhiều cơ hội và thách thức, thu hút nhiều quan tâm nghiên cứu. Dữ liệu chuỗi có đặc diém như sau [8]: Kích thước chuỗi có thé rất dài.
Trong cùng một CSDL, kích thước của mỗi chuỗi là khác nhau thậm chí có sự chênh lệch lớn. Ví dụ các chuỗi gen có độ dài tối thiểu là vài trăm nhưng độ dài tối đa lên đến hàng trăm nghìn. Một mẫu là một chuỗi con, nghĩa là các thành phần trong chuỗi con phải liên tục kể nhau trong chuỗi cha ban đầu. Một mẫu cũng có thé là một tập hợp con của chuỗi, các thành phần của mẫu không liên tục trong chuỗi cha.
- I1 - Vị trí tuyệt đối của các thành phần trong chuỗi thường không quan trọng. Chăng hạn, khi cần kiểm tra một chuỗi dữ liệu có chứa một mẫu hay không thì không cân quan tâm mau đó xuât hiện trong chuôi ở vị trí tuyệt đôi nào. Môi quan hệ về thứ tự/vị trí giữa các thành phan trong chuỗi đóng vai trò quan trọng. Ví dụ chuỗi XY hoàn toàn khác với chuỗi YX.
Hơn nữa, khoảng cách giữa hai thành phân trong chuỗi cũng có ý nghĩa. Mối quan hệ về thứ tự/vị trí giữa các thành phân trong chuỗi là đặc điểm duy nhất chỉ có ở dữ liệu chuỗi. Đây chính là điểm khác biệt cơ bản của dữ liệu chuỗi so với các loại dữ liệu khác. Một số ví dụ về dữ liệu chuỗi Chuỗi sinh học: DNA, RNA, Protein [8]: Chuỗi sinh học giúp chúng ta hiểu rõ về cầu trúc và chức năng của các loại tế bào khác nhau, hỗ trợ cho việc chân đoán và chữa bệnh.
Có ba loại chuỗi sinh học là chuỗi DNA, chuỗi protein và chuỗi RNA.2 minh họa một phan của chuỗi DNA và protein. GAATTCTCTGTAACACTAAGCTCTCTTCCTCAAAACCAGAGGTAGATAGA ATGTGTAATAATTTACAGAATITCTAGACTTCAACGATCTGATTITTTAA ATTTATTTTTATTITTTCAGGTTGAGACTGAGCTAAAGTTAATCTGTGGC Hình 2.1 - Một phân đoạn cua chuỗi DNA [8] SSQIRONYSTEVEAAVNRLVNLYLRASYTYLSLGFYFDRDDVALEGVCHFF RELAEEKREGAERLLKMONORGGRALFQDLOKPSQDEWGTTPDAMKAA IVLEKSLNOALLDLHALGSAQADPHLCDFLESHFLDEEVKLIKKMGDHLTN IQRLVGSQAGLGEYLFERLTLKHD Hình 2.2 - Một phân đoạn của chuỗi protein [8] Chuỗi sự kiện: Weblogs, System Traces, lịch sử mua hàng và lịch sử bán hàng [8]: Chiếm phan lớn các loại chuỗi là chuỗi sự kiện. Những chuỗi này có thé được sử dung dé khai thác cách thức các đối tượng hoạt động, từ đó tìm ra cách tốt nhất dé giải quyét chung. Một sô ví dụ vê chuôi sự kiện: e Chuỗi truy cập web (Weblogs) là chuỗi các cặp gồm định danh người dùng và các sự kiện (có thể là một số thông tin liên quan khác).
Một sự kiện là một yêu - 12- cầu về một tải nguyên web, chăng hạn như một trang web (thường được xác định bởi URL của trang web) hay một dịch vụ trên web. Với mỗi trang web được yêu cau, có thé có sẵn một số thông tin bé sung, như loại và nội dung cua trang web, thời lượng mà người dùng đã tiêu tốn trên trang đó. Các sự kiện trong một mẫu truy cập web được liệt kê dưới dạng danh sách thứ tự thời gian tăng dần (timestamp).3 minh họa một chuỗi truy cập web, trong đó a, b, c, đ, e là các sự kiện và 100, 200, 300, 400 là các định danh của người dùng.3 - Một chuỗi truy cập Web [8] Chuỗi vết hệ thống (System traces) là các chuỗi tương tự như chuỗi truy cập web. Các chuỗi vết hệ thống ghi nhận các hoạt động được thực hiện bởi các người dùng hoặc các tiến trình khác nhau với các dit liệu và tài nguyên khác nhau trong một hoặc nhiều hệ thống.
Chuối lịch sử mua sam của khách hàng là các chuôi các bộ, môi bộ chứa định danh khách hàng. địa chỉ, thời gian, các mặt hàng đã mua.4 mô tả một ví dụ vê các chuôi lịch sử mua săm hàng hóa của khách hàng có định danh là 223100.4 - Chuối lich sử mua sắm của một khách hàng [8] Chuỗi lịch sử bán hàng là chuỗi các bộ, mỗi bộ gồm một ID định danh của cửa hàng, thời gian (chu kỳ), tổng số mặt hàng đã bán và doanh thu tương ứng với thời gian đó và một số thông tin liên quan khác. Các chuỗi lịch sử bán hàng cũng - 13 - có thé bao gồm thông tin nhóm khách hang va một vai thông tin khác cho việc bán hàng.5 mô tả một ví dụ về chuỗi lịch sử bán hàng.5 - Chuối lịch sử bán hang [8] 2. Khai thác dữ liệu chuỗi Khai thác dữ liệu phụ thuộc vào loại thông tin mà chúng ta cần tìm kiếm thông qua hệ thống khai phá tri thức và khai thác dữ liệu.
Mỗi nhiệm vụ khai thác dữ liệu có đặc tính riêng và được thực hiện theo các bước trong quá trình khai thác tri thức. Sau đây là các nhiệm vụ khai thác dữ liệu thường được sử dụng pho bién trong ung dung khai thac di liệu chuỗi [8]. Khai thác chuỗi con pho biến (Mining frequent subsequence) hay còn gọi là khai thác mẫu tuần tự (Mining sequential pattern): khai thác các mẫu liên quan đến thời gian hoặc các sự kiện. Trong đó, mau là những chuỗi con trong CSDL chuỗi mà sự xuât hiện của chúng lớn hơn ngưỡng hô trợ do người dùng chỉ ra.
Phân lớp các chuỗi (Classification) là việc khai thác xem một phân tử có thuộc về một trong các lớp đã biết trước đó hay không. Do đó, cần phải biết trước các lớp được phân chia như thê nào dựa trên giá tri của một hoặc nhiêu trường nào đó trong mau tin. Phân cụm các chuỗi (Cluster Identification) là việc sắp xếp các đối tượng theo từng cụm. Khác với lớp, số lượng và tên của cụm chưa được biết trước.
Khi xác định các cụm, các độ đo khoảng cách được sử dụng để tính toán sao cho mức độ tương tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Khai thác luật (Mining rules) là quá trình tìm kiếm những mỗi quan hệ theo thời gian giữa các sự kiện tuần tự. Một luật mô tả mẫu tuần tự có dạng X->Y phan ánh sự xuất hiện của bién có X sẽ dẫn đến sự xuất hiện của biến có Y kế tiếp. Trên CSDL chuỗi, đã có nhiều nghiên cứu trên các loại luật khác nhau: luật tuần tự (sequential rules), luật - 14- thú vi (interesting rules), luật phân lớp tuần tự (sequential classification rules), luật tuần hoàn (recurrent rules).
Khai thác mẫu tuần tự 2. Các khái niệm về chuỗi tuần tự Item [18]: Tập các phan tử. Ví dụ: tập J = fii, iz, ., inf là 01 item gồm m phan tử. Itemset [18]: là một tập hợp khác rỗng gồm nhiễu item.
Itemset i ký hiệu là (i), i2, ., # ) với mỗi ¡; là một item. Itemset có & item được ký hiệu là k-itemset. Cac item trong itemset được sắp xếp theo thứ ty tang dan. Chuỗi (sequence) [18]: là một danh sách các itemset được sắp xếp thứ tự.
Chuỗi s được ký hiệu là (s; sa. Sn) hoặc (S¡—sa—>. —sz/) với mỗi s; là một itemset, ø là số lượng itemset. Kích thước của chuỗi bằng số lượng itemset có trong chuỗi.
Chiều dài của chuỗi là tổng số item có trong chuỗi, ký hiệu là ! = }' ` $;. Chuỗi có chiều dài còn được jai gol là k-sequence. Ví du, s = ((B)(AC)) là một 3-sequence có kích thước la 2. Chuỗi con (subsequence) [18]: Chuỗi B= (b7 be.
bm) có m itemset được gọi là chuỗi con của chuỗi @ = (a) a2. an) c6 n 1temset (hay a là chuỗi cha của B, ký hiéu B C @) néu tôn tại những số nguyên 1S j1<j2<. < j¿<m sao cho bị C đjn, b2 C đa, .