Đề tài Quy trình Khám phá tri thức áp dụng trong cơ sở dữ liệu chuỗi thời gian

MỞ ĐẦU Ngày nay với sự phát triển như vũ bão của ngành công nghệ thông tin, cùng với đó là các công cụ hỗ trợ cho công việc tích lũy thông tin cũng trở lên cực kỳ tiện lợi, dẫn đến khối lượng thông tin của các kho cơ sở dữ liệu (CSD) tăng lên rất nhanh. Cùng với đó các yêu cầu đối với quá trính phân tích dữ liệu ngày càng cao, không những phải đáp ứng được tính thời gian thực mà còn phải đưa ra được các thông tin có ích trong một “biển” dữ liệu thô và không đầy đủ…vv, tất cả các yếu tố đó làm cho các bài toán phân tích và xử lý dữ liệu truyền thống trở lên không hiệu quả. Như vây, cần có các công cụ hoặc phương pháp mới để giải quyết vấn đề này. Hiện nay trên thế giới các nhà phát triển CSDL đang rất quan tâm đến một mô hình CSDL gọi là cở sử dữ liệu chuỗi thời gian (có một số người gọi là cơ sở dữ liệu thời thời gian). Mô hình cở sở dữ liệu loại này có một số đặc điểm như: khối lượng CSDL cực lớn, đối tượng quan sát của nó thường là kết quả hoạt động của các hệ thống “nhiễu loạn”, thay đổi liên tục theo thời gian, thông tin có ích tồn tại dưới dạng phi chuẩn, chứa nhiều tạp chất và không đầy đủ, vv… Hệ thống “nhiễu loạn” là hệ thống mà các đối tượng trong nó chịu ảnh hưởng của rất nhiều các yếu tố khác nhau, ngẫu nhiên và không xác định. Khi đó ngay cả các yêu cầu về việc lữu trữ, thống kê đối với dạng thông tin kiểu này đã là một nhiệm vụ cực kỳ phức tạp khi đối với các hệ quản trị CSDL hiện nay. Và đa số các nhà phát triển CSDL trên thế giới chọn một giải pháp là xây dựng một mô hình mới dựa trên các hệ quản trị CSDL sẵn có, như hệ quản trị cơ sở dữ liệu quan hệ để lưu giữ và quản lý các loại CSDL loại này trong khi chờ các nhà sản xuất đưa ra được một phiên bản hữu hiệu cho loại dữ liệu trên. Tuy nhiên ngay cả khi đã có những công cụ phù hợp để lưu trữ và quản lý các dạng thông tin nói trên, thì để nhận được những thông tin có ích đối với dạng CSDL loại này, các biện pháp phân tích dữ liệu thông thường cũng gặp rất nhiều khó khăn, đôi khi là không thể giải quyết được. Đó chính là cơ sở cho sự xuất hiện của kỹ thuật “Khám phá tri thức - khai phá dữ liệu”. Đây là một thuật ngữ tương đối mới mẻ đối với các nhà phan tích CSDL ở Việt nam, trong khi đó thì nó đã được áp dụng rất là rộng rãi và hiệu quả trên thế giới. Bản chất của khám phá tri thức chính là việc áp dụng một loạt các bước phân tích và xử lý dữ liệu nhằm tìm ra các thông tin có ích, các quy luật tiềm ẩn, các mẫu mới trong CSDL. Thường thì kỹ thuật Khám phá tri thức – Khai phá dữ liệu được áp dụng trên các CSDL lớn, một trong các dạng đó là CSDL chuỗi thời gian. Vì vậy việc nghiên cứu quy trình Khám phá tri thức áp dụng trong CSDL chuỗi thời gian sẽ có một ý nghĩa nhất định trong thời đại ngày nay nhất là ở Việt nam khi kỹ thuật này đang còn rất là mới mẻ. CHƯƠNG I : GIỚI THIỆU CHUNG 1.1.SỰ CẦN THIẾT CỦA QUY TRÌNH NGHIÊN CỨU QUY TRÌNH KHÁM PHÁ TRI THỨC –KHAI PHÁ DỮ LIỆU. Hiện nay trên thế giới Khám phá tri thức – Khai phá giữ liệu đã và đang được áp dụng một cách rộng rãi trong rất nhiều lĩnh vực khác nhau như : y tế , marketing , ngân hàng , viễn thông, internet… .Không ai có thể phủ định được những lợi ích to lớn mà nhờ áp dụng kĩ thuật này đem lại. Điều đó được minh chứng bằng thực tế: chẩn đoán bệnh trong y tế dựa trên kết quả xét nghiệm đã giúp cho bảo hiểm y tế Australia phát hiện ra nhiều trường hợp xét nghiệm không hợp lí tiết kiệm được 1 triệu $/năm; British Telecom đã phát hiện ra những nhóm người thường xuyên gọi cho nhau bằng mobile và thu lợi được hàng triệu USD; IBM Surf – Aid đã áp dụng Khai phá dữ liệu vào phân tích các lần đăng nhập Web vào các trang có liên quan đến thị trường để phát hiện sở thích khách hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện hoạt động của các Website; Trang Web mua bán qua mạng Amazon cũng tăng doanh thu nhờ áp dụng Khai phá dữ liệu trong việc phân tích sở thích mua bán của khách hàng….Tuy nhiên, ở Việt nam hiện thuật ngữ Khám phá tri thức – Khai phá dữ liệu đang còn rất là mới mẻ, vì vậy việc đầu tư nghiên cứu một cách tỷ mỷ nhằm nắm rõ được bản chất của kỹ thuật Khám phá tri thức là gì, các bước chính trong quy trình khám phá tri thức được thực hiện như thế nào, thực chất của việc khai phá dữ liệu cũng như các giải thuật cúa nó là rất cần thiết đối với các nhà phát triển công nghệ thông tin Việt nam nói chung, và những người muốn tìm hiểu lĩnh vực mới mẻ này nói riêng. 1.2. MỤC ĐÍCH NGHIÊN CỨU CỦA ĐỀ TÀI. Vì kỹ thuật Khám phá tri thức – Khai phá dữ liệu là một lĩnh vực mới, do đó mục đích của đề tài là nghiên cứu một cách tổng quan quy trình Khám phá tri thức – Khai phá dữ liệu, từ đó có thể nắm bắt được những luận điểm, giải thuật cơ bản nhất của kỹ thuật này làm tiền đề cho việc nghiên cứu phát triển các ứng dụng cụ thể nào đó. 1.3. PHẠM VI NGHIÊN CỨU CỦA ĐỀ TÀI. Đề tài chỉ dừng ở phạm vi nghiên cứu các bước cơ bản nhất của quy trình Khám phá tri thức, áp dụng vào việc phân tích CSDL chuỗi thời gian mà cụ thể là CSDL của thị trường chứng khoán. Giới thiệu kỹ thuật làm sạch giữ liệu bằng việc áp dụng phương pháp trung bình trượt hàm mũ, đồng thời đưa ra thuật toán phân loại trạng thái của hệ thống “nhiễu loạn” dựa trên cặp chỉ số xu hướng. Từ đó đưa ra giải thuật dự báo cho trạng thái của thị trường chứng khoán. 1.4. CÁCH THIẾT KẾ CÁC PHẦN NỘI DUNG CHÍNH TRONG BẢN THUYẾT MINH. - Chương1: Giới thiệu chung. Nói về sự cần thiết của việc nghiên cứu quy trình Khám phá tri thức – Khai phá dữ liệu, mục đích, phạm vi nghiên cứu, Cuối là phần giới thiệu về các phần chính trong bản thuyết minh - Chương2: Giới thiệu tổng quan về khám phá tri thức. Chương này đưa ra các định nghĩa, khái niệm về Khám phá tri thức – Khai phá dữ liệu, sự cần thiết của Khám phá tri thức – Khai phá dữ liệu, các lĩnh vực liên quan đến Khám phá tri thức. - Chương3: Nghiên cứu quy trình khám phá tri thức. Trong chương này giới thiệu các giai đoạn của quá trình khám phá tri thức, nhiệm vụ của quá trình khám phá tri thức, các bước chính trong quy trình khám phá tri thức, hướng tiếp cận và các kỹ thuật chính trong Khai phá dữ liệu, so sánh Khai phá dữ liệu với một số phương pháp cổ điển, hướng nghiên cứu và việc ứng dụng của Khai phá dữ liệu hiện nay. - Chương4: ứng dụng quy trình khám phá tri thức vào việc phân tích CSDL chứng khoán. Chương này sẽ đưa ra các khái niệm và định nghĩa liên quan đến CSDL chuỗi thời gian, các đặc điểm của thị trường chứng khoán, đưa ra giải thuật lọc dữ liệu tần số thấp bằng phương pháp trung bình trượt hàm mũ, thuật toán phân loại trạng thái và tích lũy thông tin thống kê dựa trên cặp chỉ số xu hướng, xây dựng thuật toán dự báo trạng thái tự do của hệ thống. - Kết luận: Phần này đưa ra các kết luận về kết quả nghiên cứu của luận văn, hướng phát triển nghiên cứu tiếp theo. CHƯƠNG II : TỔNG QUAN VE KHÁM PHÁ TRI THỨC – KHAI PHÁ DỮ LIỆU 2.1. THẾ NÀO LÀ KHÁM PHÁ TRI THỨC – KHAI PHÁ DỮ LIỆU. Nếu cho rằng các điện tử và các sóng điện tử là cốt lõi của kỹ thuật điện tử thì trong ngành công nghệ thông tin có thể coi dữ liệu, thông tin và tri thức là tiêu điểm của một lĩnh vực mới trong nghiên cứu và phát triển ứng dụng và được gọi là Khám phá tri thức và Khai phá dữ liệu. Yếu tố thành công trong mọi hoạt động kinh doanh ngày nay là việc biết sử dụng thông tin một cách có hiệu quả. Điều đó có nghĩa là từ các dữ liệu sẵn có, phải tìm ra những thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện, tìm ra những xu hướng phát triển và những yếu tố tác động lên chúng. Thực hiện công việc đó chính là thực hiện quá trình Khám phá tri thức trong các cơ sở dữ liệu mà trong đó kỹ thuật cho phép ta lấy được các tri thức chính là kỹ thuật Khai phá dữ liệu. Như John Naisbett đã nói “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”. Thông thường, chúng ta xem dữ liệu như một chuỗi các bits, các số và biểu tượng hoặc các đối tượng với một ý nghĩa nào đó khi nó được gửi tới một chương trình trong một dạng thức nhất định. Chúng ta sử dụng các bits để đo thông tin và xem nó như là các dữ liệu đã được lọc bỏ các dư thừa, được rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Dữ liệu thường được cho bởi các giá trị mô tả các sự kiện, hiện tượng cụ thể. Còn tri thức (knowledge) là gì? Có thể có những định nghĩa rõ ràng để phân biệt các khái niệm dữ liệu, thông tin và tri thức hay không? Khó mà định nghĩa chính xác nhưng phân biệt chúng trong những ngữ cảnh nhất định là rất cần thiết và có thể làm được. Thông tin là một khái niệm rất rộng, khó có thể đưa ra một định nghĩa chính xác cho khái niệm này. Cũng không thể định nghĩa cho khái niệm tri thức cho dù chỉ hạn chế trong phạm vi những tri thức được chiết xuất từ các CSDL. Tuy nhiên, chúng ta có thể coi tri thức như là các thông tin được tích hợp, bao gồm các sự kiện và các mối quan hệ giữa chúng. Các mối quan hệ này có thể được nhận biết, phát hiện hay học được. Nói cách khác tri thức có thể được coi là dữ liệu có độ trừu tượng và tổ chức cao. Nếu xét trong ngữ cảnh của ngôn ngữ thì có thể hiểu tri thức là một biểu thức trong một ngôn ngữ nào đó diễn tả một (hoặc nhiều) mối quan hệ giữa các thuộc tính trong các dữ liệu đó. Các ngôn ngữ thường được dùng để biểu diễn tri thức (trong việc phát hiện tri thức từ các CSDL) là các khung (frames), các cây và đồ thị, các luật (rules), các công thức trong ngôn ngữ logic mệnh đề hoặc tân từ cấp một, các hệ thống phương trình,... Ví dụ như ta có các luật mô tả các thuộc tính của dữ liệu, các mẫu thường xuyên xảy ra, các nhóm đối tượng trong CSDL… Khám phá tri thức và Khai phá dữ liệu - một lĩnh vực học thuật đang phát triển nhanh chóng kết hợp với quản trị CSDL, khoa học thống kê, máy học và các lĩnh vực có liên quan mà mục tiêu cuối cùng của nó là trích rút ra những tri thức hữu ích từ tập các dữ liệu lớn. Giống như Khai phá dữ liệu, Khám phá tri thức cũng có thể hiểu theo nhiều khía cạnh khác nhau, nhưng tựu chung lại chúng ta có thể khái niệm Khám phá tri thức như sau: Khám phá tri thức trong CSDL là một quá trình của việc xác định giá trị, cái mới lạ, tri thức tiềm ẩn và tri thức cuối cùng của các khuôn mẫu/mô hình trong dữ liệu. Khai phá dữ liệu là một bước trong quá trình Khám phá tri thức bao gồm các thuật toán Khai phá đặc biệt nằm trong giới hạn khả năng của máy tính để tìm ra các mẫu và mô hình trong dữ liệu.[8] 2.2. SỰ CẦN THIẾT CỦA KHÁM PHÁ TRI THỨC Có rất nhiều lý do để giải thích sự cần thiết của việc Khám phá tri thức - Khai phá dữ liệu, điển hình là: Có rất nhiều tổ chức tập hợp quá nhiều dữ liệu, vậy họ phải làm gì với chúng. Con người lưu trữ dữ liệu bởi vì họ cho rằng một số giá trị hữu ích được mã hóa hoàn toàn trong dữ liệu. Trong kinh doanh, cần thu thập các thông tin về thị trường, về các đối thủ và về khách hàng. Trong sản xuất, cần thu thập các dữ liệu về thời điểm hiệu quả và tối ưu nhất phục vụ cho mục đích cải tiến quy trình và giải quyết các sự cố. Chỉ có một phần nhỏ của dữ liệu (khoảng 5 đến 10%) là luôn được phân tích. Sự gia tăng của dữ liệu cản trở các phương pháp phân tích truyền thống. Giá trị dữ liệu là quá lớn đối với cách thức phân tích cổ điển. Chúng ta có thể không bao giờ nhìn thấy chúng một cách chọn vẹn hoặc không thể lưu dữ trong bộ nhớ. Dữ liệu cần tìm kiếm không tồn tại dưới dạng tường minh mà dưới dạng phi cấu trúc, trong các quy luật tiềm ẩn. Sự phát triển của mạng máy tính đã gia tăng khả năng truy cập vào dữ liệu. Người sử dụng cuối không phải là nhà thống kê đơn thuần, họ cần biết tri thức từ CSDL mà họ đang lưu trữ. Sự cần thiết phải nhanh chóng ra quyết định và phản ứng lại những cơ hội xuất hiện trước các đổi thủ của mình. Cùng với việc lớn lên của CSDL, khả năng để đưa ra quyết định và hỗ trợ phân tích là không thể thực hiện được với truy vấn truyền thống (SQL). Rất nhiều kiểu câu truy vấn mà con người quan tâm là rất khó thực hiện hay miêu tả trong ngôn ngữ vấn tin, đại loại như: Tìm tất cả các bản ghi nghi là gian lận. Tìm tất cả các bản ghi tương tự như các bản ghi trong bảng X. Một số vấn đề với dạng thức truy vấn: Không thể tối ưu hóa thông qua truy vấn, Không có nhiều thông tin trong các trường của CSDL hoặc trong các phương pháp thống kê cổ điển. 2.3. KHÁM PHÁ TRI THỨC VÀ CÁC LĨNH VỰC LIÊN QUAN. Khám phá tri thức - Khai phá dữ liệu là một lĩnh vực khoa học liên quan tới nhiều lĩnh vực khác như: Khoa học thống kê, Máy học, CSDL, thuật toán, trực quan hóa, thực thi cao và tính toán song song. Tri thức thu được từ các hệ thống chuyên môn thông minh và sự trực quan hóa (hình dung) dữ liệu. Một hệ thống Khám phá tri thức - Khai phá dữ liệu đặc trưng bởi các phương thức, thuật toán, kỹ thuật từ các lĩnh vực khác nhau ở trên. Nhưng mục đích chung nhất là chiết xuất ra các tri thức từ dữ liệu xem xét trong trường hợp CSDL lớn. Lĩnh vực máy học và nhận dạng mẫu đan xen với Khám phá tri thức - Khai phá dữ liệu trong hướng nghiên cứu về lý thuyết và thuật toán đối với các hệ thống nhằm trích rút các mẫu, các mô hình từ dữ liệu (phần chính của nó chính là các kỹ thuật Khai phá dữ liệu). Trọng tâm của Khám phá tri thức - Khai phá dữ liệu là mở rộng về lý thuyết và các thuật toán đối với vấn đề tìm kiếm ra các mẫu đặc trưng trong một tập rộng lớn của thế giới dữ liệu thực. Khám phá tri thức - Khai phá dữ liệu cũng có nhiều điểm chung với khoa học thống kê, đặc biệt là việc phân tích dữ liệu khám phá (EDA - Exploratory Data Analysis). Một hệ thống Khám phá tri thức - Khai phá dữ liệu thường gắn liền với các thủ tục thống kê đặc biệt đối với mô hình dữ liệu và điều quản nhiễu trong khung Khám phá tri thức chung. Bên cạnh đó Khám phá tri thức - Khai phá dữ liệu cũng liên quan mật thiết với lĩnh vực khoa học gọi là Kho dữ liệu (Data Warehousing). Kho dữ liệu ám chỉ đến xu hướng thông dụng gần đây là lựa chọn, giải quyết dữ liệu một cách rõ ràng và làm cho chúng có khả năng phục hồi trực tuyến. Một phương pháp thông dụng cho việc phân tích kho dữ liệu được gọi là OLAP - xử lý phân tích trực tuyến. Tiêu điểm của các công cụ OLAP là cung cấp cách phân tích dữ liệu đa chiều. Việc phân tích dữ liệu đa chiều này mạnh hơn so với SQL (Standard Query Language) - Ngôn ngữ vấn tin chuẩn trong việc xử lý các dữ liệu nhiều chiều. Chúng ta xem cả hai khái niệm Khám phá tri thức và OLAP là các khía cạnh về một vấn đề mới của trích rút thông tin tri thức và các công cụ quản lý. 2.4 THẾ NÀO LÀ KHÁM PHÁ DỮ LIỆU Hai thuật ngữ “Khám phá tri thức” và “Khai phá dữ liệu” đã xuất hiện và phổ biến trên thế giới, tuy nhiên ở việt nam thì những thuật ngữ này còn tương đối là mới mẻ do vậy rất nhiều người đã coi khai phá dữ liệu và khám phá tri thức trong cơ sở dữ liệu (knowledge discovery in databases - kdd ) là như nhau. Tuy nhiên thực chất , khai phá dữ liệu chỉ là một khâu trong quá trình khám phá tri thức. Tiến trình trong thu thập dữ liệu số và công nghệ lưu trữ dẫn đến sự lớn lên của các CSDL đồ sộ. Điều này đã xuất hiện trong tất cả lĩnh vực từ dữ liệu trong các hoạt động của con người (như dữ liệu giao dịch thị trường, bản ghi việc sử dụng thẻ tín dụng, thông tin về các cuộc gọi điện thoại, các thống kê của chính phủ) tới các dữ liệu thu thập được từ bên ngoài (như hình ảnh các thiên thể, CSDL về phân tử, hoặc bản ghi y tế). Cùng với sự lớn lên của dữ liệu là sự lớn lên của mối quan tâm về các vấn đề về khả năng sao lưu dữ liệu này (tapping these data), khả năng trích rút từ chúng các thông tin có giá trị . Khoa học trích ra các thông tin hữu ích từ một tập dữ liệu (các CSDL) lớn được xem là Khai phá dữ liệu (Data mining). Nó là một khoa học liên ngành mới, giao của thống kê học, học máy, quản trị dữ liệu và các CSDL, nhận dạng khuôn mẫu, trí tuệ nhân tạo, và các lĩnh vực khác. Tất cả chúng liên quan đến các khía cạnh cụ thể của phân tích dữ liệu, chúng có nhiều thứ chung, nhưng mỗi môn có các bài toán và phương pháp giải quyết phân biệt và đặc trưng. 2.5. ĐINH NGHĨA KHÁM PHÁ DỮ LIỆU Khái niệm Khai phá dữ liệu ra đời vào cuối những năm 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn. Một số tên khác được sử dụng với ý nghĩa tương tự như lĩnh vực Khai phá dữ liệu như : Khảo cổ dữ liệu, Nạo vét dữ liệu, Phân tích sự phụ thuộc chức năng, và Thu hoạch dữ liệu, ... Nhưng tựu chung lại, về bản chất, Khai phá dữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật đặc biệt để tìm ra các mẫu đặc trưng trong một tập dữ liệu khổng lồ. Có rất nhiều định nghĩa về Khai phá dữ liệu đã được các tác giả khác nhau đưa ra; sau đây là một số định nghĩa tham khảo mà các nhà khoa học nghiên cứu về lĩnh vực này phát biểu: Định nghĩa của Ferrurra: “Khai phá dữ liệu là tập hợp các phương pháp được dùng trong tiến trình Khám phá tri thức để tìm ra sự khác biệt các mối quan hệ và các mẫu chưa biết bên trong dữ liệu” Định nghĩa của Parsaye: “Khai phá dữ liệu là quá trình trợ giúp quyết định, trong đó chúng ta tìm kiếm các mẫu thông tin chưa biết và bất ngờ trong CSDL lớn” Định nghĩa của Mitchell: “Khai phá dữ liệu là việc sử dụng các dữ liệu đã có để khám phá các quy tắc và đưa đến các quyết định” Định nghĩa của Groth: “Khai phá dữ liệu là một quá trình xác định các mẫu ẩn, xu thế và mối quan hệ của dữ liệu”. Định nghĩa của Berry & Linoff: “Khai phá dữ liệu là quá trình khám phá và phân tích tự động một lượng lớn dữ liệu để khám phá ra các mẫu và các luật”. Định nghĩa của Wegman: “Khai phá dữ liệu là việc sử dụng các kỹ thuật tính toán để phân tích dữ liệu với sự tác động rất ít của con người”. Việc định nghĩa một khoa học liên ngành luôn gây tranh cãi; các nhà nghiên cứu thường không nhất trí về phạm vi chính xác và giới hạn về lĩnh vực nghiên cứu của họ. Với suy nghĩ như vậy và chấp nhận rằng có thể những người khác không đồng tình về chi tiết, chúng ta có thể khái niệm về Khai phá dữ liệu như sau: Khai phá dữ liệu là sự phân tích của các tập dữ liệu quan sát (thường là lớn) để tìm ra các mối liên hệ rõ ràng (unsuspected) và để tóm tắt dữ liệu theo các cách mới mà vừa dễ hiểu, vừa hữu ích cho người sở hữu dữ liệu. Các mối liên hệ và các tóm tắt thu được thông qua Khai phá dữ liệu thường gọi là các mô hình (models) hoặc khuôn mẫu (patterns). Ví dụ như các phương trình tuyến tính, các luật, các nhóm, các đồ thị, các cấu trúc cây, các khuôn mẫu lặp lại theo thời gian. Khái niệm ở trên nhắc đến “dữ liệu quan sát - observational data”, đối lập với “dữ liệu thực nghiệm - experimental data). Khai phá dữ liệu thường làm việc trên dữ liệu mà đã thực sự được thu thập trước đó cho mục đích khác với phân tích của Khai phá dữ liệu (chẳng hạn, chúng được thu thập nhằm cập nhật tất cả các giao dịch trong một ngân hàng). Điều đó có nghĩa rằng các mục tiêu của Khai phá dữ liệu không được xác định trong chiến lược thu thập dữ liệu. Điều này là một trong những cái để phân biệt Khai phá dữ liệu với thống kê học (statistics), đối với thống kê, dữ liệu thường được thu thập bởi sử dụng các chiến lược hiệu quả để trả lời các câu hỏi xác định trước. Với lý do này, Khai phá dữ liệu thường được coi là phân tích dữ liệu thứ cấp (“secondary”). Khái niệm trên cũng đề cập đến các tập dữ liệu trong Khai phá dữ liệu thường là lớn. Nếu chỉ làm việc trên tập dữ liệu nhỏ, chúng ta hoàn toàn mới chỉ thảo luận phân tích dữ liệu khám phá cổ điển (classical exploratory data analysis) như công việc của các nhà thống kê. Khi đối mặt với dữ liệu lớn, các bài toán mới sẽ nảy sinh. Một số bài toán thì liên quan đến các vấn đề lưu trữ và truy cập dữ liệu, một số khác thì liên quan đến các vấn đề cơ bản như là làm thế nào để xác định các đại diện của dữ liệu, làm thế nào phân tích dữ liệu trong thời gian chấp nhận được, làm thế nào để quyết định xem một mối liên hệ chỉ đơn thuần là sự xuất hiện ngẫu nhiên không phản ánh một thực tế nào cả. Thông thường, dữ liệu có sẵn chỉ bao gồm một mẫu (sample) từ một tập đầy đủ dữ liệu; mục đích là khái quát hóa (generalize) từ mẫu đó cho toàn bộ tập dữ liệu. Chẳng hạn chúng ta mong muốn dự đoán hành vi của các khách hàng tương lai, hoặc dự đoán các tính chất của cấu trúc proteins mà chúng ta chưa bao giờ nhìn thấy trước đó. Những khái quát hóa như vậy có thể không thể có được bằng các cách tiếp cận thống kê chuẩn vì dữ liệu thường không phải là các mẫu “ngẫu nhiên” mà là “mẫu tiện lợi” (“convenience samples”) hoặc “mẫu cơ hội” (“opportunity samples”). Đôi khi chúng ta muốn tóm tắt hoặc nén một tập dữ liệu lớn theo một cách sao cho kết quả là dễ hiểu, không có bất cứ một ý niệm nào của khái quát hóa cả. Vấn đề như vậy sẽ nảy sinh, chẳng hạn, nếu chúng ta đã hoàn thành dữ liệu điều tra dân số đầy đủ của một quốc gia, hoặc một CSDL gồm hàng triệu giao dịch bán lẻ. Các mối liên hệ và cấu trúc tìm thấy trong các tập dữ liệu phải là mới, điều đó là tất nhiên. Sẽ có rất ít giá trị khi tìm ra các mối liên hệ đã thiết lập trước (trừ khi mục đính của công việc là xác nhận giả thuyết, xác định xem một khuôn mẫu - pattern - tồn tại trong một tập dữ liệu mới không), hoặc các mối liên hệ cần thiết (ví dụ như tất cả bệnh nhân mang thai là nữ). Rõ ràng, tính mới (novelty) phải được đo một cách tương đối đối với tri thức đã có trước (tri thức tiên nghiệm) của người sử dụng. Không may là chỉ có một vài giải thuật Khai phá dữ liệu là đề cập đến tri thức tiên nghiệm. Trong khi tính mới là một tính chất quan trọng của các mối liên hệ chúng ta tìm kiếm, nó vẫn không đủ để đánh giá một mối liên hệ là có giá trị. Cụ thể, các mối liên hệ phải có thể hiểu được (understandable). Ví dụ các mối liên hệ đơn giản là dễ hiểu hơn các mối liên hệ phức tạp, và vì vậy được ưa thích hơn. CHƯƠNG III : NGHIÊN CỨU QUY TRÌNH KHÁM PHÁ TRI THỨC 3.1. CÁC GIAI ĐOẠN CỦA QUY TRÌNH KHÁM PHÁ TRI THỨC Quá trình trích rút tri thức từ các CSDL là sự kết hợp giữa các kỹ thuật và công cụ thống kê, máy học và các CSDL, ... để tìm ra một mô tả logic chính xác, và cuối cùng là từ các mô tả này có thể đưa ra các mẫu và các quy tắc trong dữ liệu. Việc trích rút tri thức từ một khối lượng khổng lồ dữ liệu có thể được xem như là một quá trình tương tác lặp đi lặp lại, và không phải là một hệ thống phân tích tự động. Trong trường hợp này, chúng ta không thể đơn giản trông chờ một trích rút tri thức hữu ích chỉ bằng việc xem xét một nhóm dữ liệu trong một hộp đen “black box”. Việc lặp đi lặp lại của quá trình Khám phá tri thức ám chỉ cách hiểu tổng thể lĩnh vực ứng dụng. Cách hiểu này bao gồm việc lựa chọn một tập con dữ liệu tiêu biểu, các lớp mẫu thích hợp và các phương pháp tốt để đánh giá tri thức. Để hiểu rõ hơn các chức năng của người dùng sử dụng quá trình Khám phá tri thức, chúng ta có thể chia những người dùng thành 3 lớp: Những nhà chuyên môn, là những người rất am hiểu về lĩnh vực ứng dụng. Tiếp theo là những nhà phân tích, đây là những người thực hiện quá trình Khám phá tri thức, và do đó họ có rất nhiều kiến thức về các giai đoạn của quá trình này. Thứ nữa là những người sử dụng cuối cùng, là những người không cần có nhiều kiến thức về lĩnh vực ứng dụng. Thường thì những người dùng cuối sử dụng tri thức trích rút được từ quá trình Khám phá tri thức để hỗ trợ cho họ trong việc ra quyết định. Sự thành công của quá trình Khám phá tri thức phụ thuộc một phần vào sự tác động giữa những người sử dụng. Điều đó có nghĩa là những nhà phân tích không thể tìm ra các tri thức hữu ích từ dữ liệu mà không có sự đảm bảo của các chuyên gia. Bên cạnh đó, sự tác động qua lại của quá trình đòi hỏi người sử dụng cuối và các chuyên gia cần tham gia tích cực trong việc lựa chọn và đưa ra quyết định của quá trình Khám phá tri thức. Khám phá tri thức từ dữ liệu có thể được hiểu như một quá trình bao gồm ít nhất các bước sau: Hiểu lĩnh vực ứng dụng, lựa chọn và tiền xử lý dữ liệu, Khai phá dữ liệu, đánh giá tri thức, củng cố và sử dụng tri thức đó. Quá trình Khai phá tri thức bắt đầu bằng việc hiểu lĩnh vực ứng dụng. Tiếp theo, một mẫu đại diện được lấy từ CSDL, được tiền xử lý và được lựa chọn để sau đó áp dụng các phương pháp và công cụ của giai đoạn Khai phá dữ liệu với mục tiêu là tìm ra các mẫu/mô hình (tri thức) trong dữ liệu đó. Tri thức này được đánh giá bằng chất lượng hoặc/và sự hữu ích của nó, và vì vậy nó có thể được sử dụng để hỗ trợ cho hệ trợ giúp gia quyết định. Một điều cần quan tâm đó là bởi vì đây là một quá trình lặp đi lặp lại, nên các bước của quá trình Khám phá tri thức không khép kín, điều đó có nghĩa là sự tương quan giữa kỹ thuật và phương pháp được sử dụng trong một vài giai đoạn là rất quan trọng, và do vậy chỉ cần một sự cố nhỏ trong số chúng cũng có thể ảnh hưởng một cách căn bản đến thành công của toàn bộ quá trình. Tỡm hiểu lĩnh vực ứng dụng Thu thập và tiền xử lý dữ liệu Khai phỏ trớch rỳt tri thức Phân tích và kiểm định kết quả Sử dụng tri thức phát hiện được CSDL Dữ liệu đó được tiền xử lý Cỏc mẫu / mụ hỡnh Trực quan húa dữ liệu Quá trình Khám phá tri thức có thể tổng quát thành các giai đoạn sau [1,2,3]: Hình 3.1: Các giai đoạn của quá trình khám phá tri thức Giai đoạn thứ nhất: Tìm hiểu lĩnh vực ứng dụng: nhằm tìm hiểu lĩnh vực ứng dụng và phát biểu vấn đề của bài toán. Giai đoạn này là điều kiện tiên quyết cho việc trích rút tri thức và lựa chọn phương pháp Khai phá dữ liệu thích hợp với mục đích của ứng dụng và bản chất của dữ liệu. Giai đoạn thứ hai: Thu thập và tiền xử lý dữ liệu. Giai đoạn này có nhiệm vụ thu thập và tiền xử lý dữ liệu, bao gồm việc lựa chọn dữ liệu nguồn, loại bỏ các nhiễu hay phân tách dữ liệu, xử lý dữ liệu lỗi, chuyển đổi và rút gọn dữ liệu (nếu cần thiết). Giai đoạn này thường chiếm nhiều thời gian nhất trong toàn bộ quá trình Khám phá tri thức - Khai phá dữ liệu. Giai đoạn thứ ba: Khai phá dữ liệu, trích rút tri thức. Giai đoạn này sử dụng các kỹ thuật Khai phá dữ liệu để trích rút ra các mẫu, các mô hình ẩn dấu trong dữ liệu hoặc tĩch lũy các thông tin thống kê có ích dữa trên các thuật toán phân loại rồi sử dụng chúng để thu nhận được các thông tin có ích dưới một dạng nào đó. Một mô hình có thể được xem như “sự thể hiện một cấu trúc tóm tắt một cách hệ thống các thành phần nằm dưới dữ liệu hay mô tả cách mà dữ liệu phát sinh”. Trái ngược với nó, “một mẫu là một cấu trúc cục bộ, có thể chỉ liên quan đến một nhóm các biến và một ít các trường hợp”. Các lớp chính của kỹ thuật Khai phá dữ liệu là mô hình dự báo như: phân lớp và hồi quy, phân nhóm (đoạn), mô hình phụ thuộc như: mô hình đồ họa, ước lượng mật độ, tổng hợp hay tìm mối liên hệ giữa các trường như: luật kết hợp, trực quan hóa, và mô hình phát hiện sự biến đổi và độ lệch trong dữ liệu và tri thức. Giai đoạn thứ tư: phân tích và kiểm định kết quả. Giai đoạn này nhằm làm sáng tỏ các tri thức, đặc biệt là việc làm sáng tỏ phạm vi của mô tả và dự báo - hai đích chính của hệ thống khám phá trong thực tế. Các thí nghiệm chỉ ra rằng các khuôn mẫu hoặc các mô hình từ dữ liệu không phải luôn luôn được quan tâm hay sử dụng trực tiếp, và quá trình Khám phá tri thức cần phải được lặp đi lặp lại tùy theo đánh giá của tri thức khám phá. Một cách chuẩn để đánh giá các kết quả là chia dữ liệu thành hai tập, một tập để huấn luyện và một tập để kiểm thử. Một tập có thể lặp lại quá trình một số lần với sự phân tách khác nhau và kết quả trung bình sẽ dùng để ước lượng luật thực thi. Giai đoạn cuối cùng: Sử dụng các tri thức được phát hiện. Giai đoạn này sẽ đưa các tri thức khám phá được vào ứng dụng thực tế. Trong một số trường hợp, Giai đoạn này có thể sử dụng tri thức khám phá được mà không nhúng vào hệ thống máy tính. Về mặt khác, người sử dụng có thể trông chờ vào tri thức được khám phá trên máy tính hay khai thác bởi một số chương trình. Việc đưa kết quả vào ứng dụng thực tế là đích cuối cùng của quá trình Khám phá tri thức. Chú ý rằng, không gian của các mẫu là vô hạn và việc liệt kê các mẫu đòi hỏi một số dạng thức của việc tìm kiếm trong không gian này. Khả năng của máy điện toán hạn chế vị trí hạn hẹp giới hạn của không gian con có thể được khám phá bởi các thuật toán. Thành phần Khai phá dữ liệu của quá trình Khám phá tri thức có liên quan mật thiết với ý nghĩa của các mẫu được trích rút và liệt kê từ dữ liệu. Khám phá tri thức bao gồm sự ước lượng và sự giải thích sáng tỏ các khuôn mẫu để đưa ra quyết định cái gì cấu thành lên tri thức, còn cái gì không cấu thành lên tri thức. Nó cũng bao gồm cách mã hóa, tiền xử lý, lấy mẫu và phép chiếu của dữ liệu trước các bước Khai phá dữ liệu. 3. 2. NHIỆM VỤ CỦA QUÁ TRÌNH KHÁM PHÁ TRI THỨC Như trên đã nghiên cứu, các giai đoạn của quá trình Khám phá tri thức, và trên thực tế mỗi giai đoạn là rất phức tạp. Để hiểu rõ hơn quá trình Khám phá tri thức cần phải làm những việc gì, chúng ta hãy xem xét những nhiệm vụ mà một quá trình Khám phá tri thức sẽ làm trong hình sau: Hình 3.2: Các nhiệm vụ của quá trình Khám phá tri thức Tích hợp dữ liệu: Thu thập dữ liệu từ các nguồn khác nhau. Tạo ra tập dữ liệu mục tiêu: Lựa chọn một tập dữ liệu, tập trung vào một tập con các biến hoặc các mẫu dữ liệu, trên tập dữ liệu mục tiêu đó, việc khám phá sẽ được thực hiện, Tiền xử lý và làm sạch dữ liệu: ở đây bao gồm các thao tác cơ bản như loại bỏ các nhiễu, loại bỏ các giá trị bất thường không hợp lý. Rút gọn và chiếu dữ liệu: Tìm ra các đặc trưng hữu dụng để miêu tả dữ liệu phụ thuộc vào mục tiêu của mỗi nhiệm vụ. Sử dụng việc rút gọn số chiều (kích thước) hoặc các kỹ thuật biến đổi để giảm bớt số biến có ảnh hưởng hoặc tìm ra cái bất biến đối với dữ liệu, Lựa chọn nhiệm vụ Khai phá dữ liệu: Quyết định đích của Khám phá tri thức là phân lớp, hồi quy, phân nhóm, ... Những nhiệm vụ khác nhau của giải thuật Khai phá dữ liệu cũng cần phải được đề cập ở đây, Lựa chọn kỹ thuật Khai phá dữ liệu: Lựa chọn các kỹ thuật cho việc tìm kiếm các mẫu trong dữ liệu, điều này quyết định mô hình và các tham số nào là thích hợp và kỹ thuật Khai phá dữ liệu nào phù hợp với tiêu chuẩn của quá trình Khám phá tri thức (ví dụ người sử dụng cuối cùng sẽ quan tâm đến việc hiểu dữ liệu hơn là mô hình có khả năng dự báo), Khai phá dữ liệu để trích rút các khuôn mẫu/mô hình: Tìm kiếm các khuôn mẫu liên quan đến dạng thức đặc biệt hoặc một tập các đặc trưng như: luật phân lớp, cây quyết định, hồi quy, phân nhóm ..., Giải thích và ước lượng các khuôn mẫu/mô hình, Củng cố, thống nhất tri thức khám phá: Hợp nhất các tri thức này vào trong hệ thống thực thi hoặc đơn giản là đưa ra các tài liệu báo cáo. Điều này cũng bao gồm việc kiểm tra và giải quyết các xung đột với các tri thức tin tưởng trước đó. 3.3. QUY TRÌNH KHÁM PHÁ TRI THỨC Rõ ràng, nhiệm vụ của quá trình Khám phá tri thức là rất nặng nề và liên quan đến nhiều vấn đề; nếu lĩnh vực ứng dụng hay bài toán đặt ra đã được xác định trên các tập dữ liệu lớn như kho dữ liệu, CSDL, ... cụ thể, thì một quy trình Khám phá tri thức (kết hợp cả việc Khai phá dữ liệu) có thể được thực hiện theo 5 bước như hình sau: Dữ liệu (1) Lựa chọn dữ liệu (2) Tiền xử lý dữ liệu (3) Biến đổi dữ liệu (4) Khai phá dữ liệu (5) Biểu diễn/ Đánh giá tri thức Dữ liệu đích Dữ liệu đã được tiền xử lý Dữ liệu đã được chuyển đổi Các mẫu, mô hình Tri thức Hình 3.3 : Quy trình Khám phá tri thức Trong đó: Bước thứ nhất: Trích chọn dữ liệu (Data seclection): là bước chọn ra những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (Databases, data warehouse, data repositories) theo một số tiêu chí nhất định phục vụ cho mục đích, yêu cầu mà ứng dụng đã đặt ra, Bước thứ hai: Tiền xử lý dữ liệu (Data preprocessing): là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, ...), rút gọn dữ liệu (sử dụng các phương pháp rút gọn dữ liệu, histograms, lấy mẫu, ...), rời rạc hoá dữ liệu (dựa vào histograms, entropy, phân khoảng, ...). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hoá, Bước thứ ba: Biến đổi - chuyển dạng dữ liệu (Data transformation) nếu cần : là bước chuẩn hoá và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau, Bước thứ tư: Khai phá dữ liệu (Data mining) : đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình Khám phá tri thức, áp dụng các kỹ thuật khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn được các mẫu (patterns) thông tin, các mối liên hệ đặc biệt trong dữ liệu, Bước thứ năm: Biểu diễn và đánh giá tri thức (Knowledge epresentation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu hoặc mô hình thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai thác ở bước trên biểu diễn theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, ... Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. Một điều cần lưu ý là: Trong bước Khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận được cũng có thể được lưu và sử dụng lại. 3.4. HƯỚNG TIẾP CẬN VÀ KỸ THUẬT CHÍNH TRONG KHAI PHÁ DỮ LIỆU. 3.4.1. Các dạng dữ liệu có thể khai phá: Như chúng ta đã biết, tri thức của nhân loại là tổng hòa của các mối quan hệ, liên quan mật thiết, logic với nhau và được lưu trữ dưới các dạng dữ liệu này hay dữ liệu kia. Trong thực tế có rất nhiều mô hình CSDL, tuy nhiên, trong các lĩnh vực ứng dụng cụ thể khác nhau, chúng ta có thể định nghĩa và phân biệt ra rất nhiều dạng dữ liệu sao cho thuận lợi nhất trong quá trình sử dụng. Khai phá dữ liệu có khả năng chấp nhận một số kiểu dữ liệu như sau : Cơ sở dữ liệu quan hệ (relational databases): là các dữ liệu tác nghiệp được tổ chức theo mô hình dữ liệu quan hệ rất phổ biến trong nhiền ngành, có giá trị lịch sử cũng như thực tiễn rất to lớn, do đó, hầu hết các HQTCSDL đều hỗ trợ dạng cơ sở dữ liệu quan hệ như Oracle, MS SQL Server, IBM DB2, MS Access, ... Cơ sở dữ liệu đa chiều (multidimention structures, data warehouses, data mart): là các kho dữ liệu được tập hợp và chọn lọc từ nhiều nguồn dữ liệu khác nhau. Dạng dữ liệu này chủ yếu phục vụ cho quá trình phân tích cũng như Khám phá tri thức và hỗ trợ quá trình ra quyết định. Cơ sở dữ liệu giao tác - giao dịch (transactonal databases): đây cũng là dạng dữ liệu tác nghiệp có các bản ghi thường là các giao tác. Dạng dữ liệu này cũng phổ biến hiện nay. Cơ sở dữ liệu quan hệ - hướng đối tượng (object relational databases) : là dạng dữ liệu lai giữa hai mô hình quan hệ và hướng đối tượng. Dữ liệu không gian, thời gian và chuỗi thời gian (spatial, temporal, and time-series data): là dạng dữ liệu có tích hợp thuộc tính về không gian như dữ liệu bản đồ mạng cáp điện thoại hoặc thời gian như dữ liệu cước điện thoại, phát hành báo chí, chỉ số chứng khoán ... Cơ sở dữ liệu đa phương tiện (Multimedia database): là dạng dữ liệu âm thanh (audio), hình ảnh (video), Text & WWW, ... Dạng dữ liệu này đang rất phong phú, đa dạng và được phổ biến rộng rãi nhất là trên internet. 3.4.2. Các phương pháp, kỹ thuật chính trong Khai phá dữ liệu. Bởi vì Khai phá dữ liệu và Khám phá tri thức là một lĩnh vực tương đối mới, do vậy có nhiều các tác giả đã đưa ra các nghiên cứu về phương pháp, kỹ thuật Khai phá dữ liệu theo các cách khác nhau như: Đối với Fayyad, các kỹ thuật Khai phá dữ liệu như: Mô hình dự báo (Predictive Modeling), Phân nhóm (Clustering), Tổng hợp hóa (Summarization), Mô hình sự phụ thuộc (Dependency Modeling), Phát hiện sự biến đổi và độ lệch (Change and deviation detection).[5] Đối với Goebel & Gruenwald, các kỹ thuật Khai phá dữ liệu như: Các mô hình thống kê (Statistical Models), Mạng nơron (Neural Networks), cây quyết định (Decision Trees), Quy nạp luật (Rule Induction), mạng Bayesian tin cậy (Bayesian Belief Networks), các thuật toán về lập trình Gen (Genetic algorithms), tập mờ (Fuzzy Sets), tập thô (Rough Sets).[4] Đối với Aggarwal & Yu, các kỹ thuật Khai phá dữ liệu gồm: Luật kết hợp (Association rules), Phân nhóm (Clustering), Phân lớp (Classification). Tựu chung lại, các kỹ thuật Khai phá dữ liệu thực chất không có gì mới. Nó là sự kế thừa, kết hợp và mở rộng của các kỹ thuật cơ bản đã được nghiên cứu từ trước như học máy, nhận dạng, thống kê (hồi quy, phân loại, phân nhóm), các mô hình đồ thị, các mạng Bayes, trí tuệ nhân tạo, thu thập tri thức hệ chuyên gia,… Tuy nhiên, với sự kết hợp tài tình của Khai phá dữ liệu, kỹ thuật này có ưu thế hơn hẳn các phương pháp trước đó, đem lại nhiều triển vọng trong việc ứng dụng phát triển nghiên cứu khoa học cũng như áp dụng vào thực tiễn và nó có thể được chia làm 2 nhóm chính sau: Kỹ thuật khai phá dữ liệu mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Nhóm kỹ thuật này gồm các phương pháp: phân nhóm (Clustering), tổng hợp hóa (Summerization), Phát hiện sự biến đổi và độ lệch (Change and deviation detection), phân tích luật kết hợp (Association Rules), ... Kỹ thuật khai phá dữ liệu dự đoán: có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời. Nhóm kỹ thuật này gồm các phương pháp: phân lớp (Classification), hồi quy (Regression), ... 3.4.2.1. Phân lớp và dự đoán (Classification & Prediction): Là việc xác định một hàm ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã được biết trước đó. Mục tiêu của việc phân lớp là tìm ra mối quan hệ nào đó giữa thuộc tính dự báo và thuộc tính phân lớp hay nói cách khác là dự đoán nhãn lớp cho các mẫu dữ liệu. Như thế quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Các kiến thức được phát hiện biểu diễn dưới dạng luật theo các cách sau: “Nếu các thuộc tính dự báo của một mục thỏa mãn điều kiện của các tiền đề thì mục đó nằm trong lớp chỉ ra trong kết luận”. Ví dụ : phân lớp loại cước hoặc loại dịch vụ dựa trên số máy bị gọi của cuộc gọi, phân lớp khu vực dựa trên số máy chủ gọi, phân lớp giờ cao điểm, thấp điểm dựa trên giờ bắt đầu đàm thoại, ... Phân lớp là một lĩnh vực rất quan trọng trong khai phá dữ liệu. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình để phân lớp dữ liệu. Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát (supervised learning) khác với phân nhóm dữ liệu là học không có giám sát (unsupervised learning). Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết chúng ta phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp như: Cây quyết định (Decision Tree), K-Láng giềng gần nhất (k-Nearest Neighbor), Mạng Nơron (Neural networks), Giải thuật di truyền (Genetic algorithms), Mạng Bayesian (Bayesian networks), Tập mờ và tập thô (Rough and Fuzzy Sets). a) Cây quyết định (Decision Tree). Các kỹ thuật phân lớp sử dụng cây quyết định để phân tách các dữ liệu cho đến khi mỗi phần chứa đựng hầu hết các mẫu từ một lớp đặc trưng, kết quả của quá trình sẽ cho ra một cây quyết định. Điểm phân tách trong cây quyết định là một nút (không phải là nút lá) sẽ sử dụng một số điều kiện để quyết định dữ liệu sẽ được phân tách như thế nào. Các nút cuối cùng trong cây quyết định chứa đựng các bộ mẫu giống nhau. Lợi thế của cây quyết định là các thuật toán chạy khá nhanh, với kết quả khá tốt và có thể giải thích được rõ ràng. Tuy nhiên, bất lợi mà các thuật toán của cây quyết định có thể gặp phải đó là chúng có thể tìm ra các điểm tới hạn cục bộ, đưa ra các kết quả không đúng. b)K-láng giềng gần nhất (k-Nearest Neighbor). Thuật toán này tìm ra các láng giềng gần nhất của mẫu thử nghiệm và quy về các nhãn lớp của chúng dựa trên các nhãn đa số, điều đó có nghĩa là các mẫu được quy về cùng lớp khi chúng là lân cận của nhau. Kỹ thuật này cho rằng vị trí trong không gian đặc trưng hàm ý một quan hệ họ hàng gần gũi ở giữa các nhãn lớp. Lợi thế của các thuật toán K-Láng giềng gần nhất là dễ thực thi, và kết quả mà nó đem lại khả năng dễ dàng giải thích. Nhưng một điểm bất lợi là các thuật toán này đưa ra các mô hình rất lớn với một tập dữ liệu nhỏ. c) Mạng nơron (Neural networks). Mạng nơron là mạng được mô phỏng theo bộ não của con người. Đó là một cấu trúc dữ liệu của các hàm với một hoặc nhiều trọng số đầu vào, với kết quả đầu ra là một nhãn các lớp. Từng phần riêng biệt của dữ liệu được đưa vào mạng nơron và các hàm - các trọng số trong mạng nơron bị thay đổi (học - huấn luyện) tùy theo tỷ lệ lỗi của đầu ra. Phương pháp này thường đưa đến một khoảng thời gian huấn luyện dài ngay cả khi tập dữ liệu nhỏ. Lợi thế của mạng nơron là đưa đến các kết quả khá chính xác, nhưng bất lợi của nó là thường đòi hỏi thời gian huấn luyện dài và đưa ra các kết quả khó hiểu, cứng nhắc, bị bao bọc trong một hộp đen, khó giải thích tường minh. d) Giải thuật di truyền (Genetic algorithms). Các giải thuật di truyền được sử dụng để đưa ra công thức giả thuyết về sự phụ thuộc giữa các biến. Đối với một giải thuật di truyền phải sử dụng các giải pháp như cạnh tranh, lựa chọn và kết hợp giữa các tập hợp cá thể. Lợi thế của Giải thuật di truyền là thường đưa đến các kết quả kiểm tra khá chính xác, nhưng bất lợi của nó là kết quả có được thông qua việc lập trình tiến hóa và các kết quả cũng thường cứng nhắc, khó hiểu. e) Mạng Bayesian (Bayesian networks) Trong mạng Mạng Bayesian sử dụng các đồ thị có hướng, không có chu trình để miêu tả sự phân lớp có thể được. Các đồ thị này cũng có thể được sử dụng để miêu tả các tri thức chuyên gia. Các nút miêu tả các biến thuộc tính và các trạng thái (sự kiện) và mỗi một cạnh miêu tả khả năng sự phụ thuộc giữa chúng. Kết hợp với mỗi nút là các lớp cục bộ có thể và các cung được vẽ từ nút nguyên nhân đến nút bị ảnh hưởng. Khai phá dữ liệu trong mạng Bayesian bao gồm việc sử dụng đầu vào các tri thức chuyên gia và sau đó sử dụng một CSDL để cập nhật, lọc và cải tiến tri thức đó trong mạng. Các đồ thị mới có thể là kết quả từ các cải tiến này và nguyên nhân của các mối quan hệ giữa các nút kết quả có thể được giải thích một cách dễ dàng. Lợi thế của mạng Bayesian là thường đưa ra các kết quả dễ hiểu, nhưng bất lợi của nó là cần thu thập được các tri thức chuyên gia truyền thống. f) Tập mờ và tập thô (Rough and Fuzzy Sets) Lý thuyết về tập mờ và tập thô dựa trên một sơ sở toán học không chắc chắn. Đối với các mô hình tập thô, một giới hạn trên và giới hạn dưới sẽ được xác định. Một tập thô định nghĩa một lớp C là một xấp xỉ bởi hai tập. Tập cận dưới (lower) của C bao gồm tất cả các mẫu dữ liệu, mà dựa vào tri thức của các mẫu dữ liệu có thể quyết định một mẫu bất kỳ thuộc phân lớp C một cách rõ ràng. Tập cận trên của C bao gồm tất cả các mẫu với giá trị của thuộc tính được mô tả không thể thuộc vào phân lớp C. Mô hình tập mờ không dốc về cực đại cục bộ bằng các thuật toán cây quyết định, và cũng giống như mô hình tập thô, chúng dùng để đối phó với những điều không chắc chắn tốt hơn bất kỳ một thuật toán nào khác. 3.4.2.2. Phân tích luật kết hợp (Association Rules): Luật kết hợp là dạng luật biểu diễn tri thức ở dạng tương đối đơn giản. Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật Khai phá dữ liệu là tập luật kết hợp tìm được. Chẳng hạn: phân tích CSDL bán hàng nhận được thông tin về những khách hàng mua máy tính có khuynh hướng mua phần mềm quản lý tài chính trong cùng lần mua được miêu tả trong luật kết hợp sau: “Máy tính => Phần mềm quản lý tài chính” [Độ hỗ trợ: 2%, độ tin cậy: 60%] Độ hỗ trợ và độ tin cậy là hai độ đo của sự đáng quan tâm của luật. Chúng tương ứng phản ánh sự hữu ích và sự chắc chắn của luật đã khám phá. Độ hỗ trợ 2% có nghĩa là 2% của tất cả các tác vụ đã phân tích chỉ ra rằng máy tính và phần mềm quản lý tài chính là đã được mua cùng nhau. Còn độ tin cậy 60% có nghĩa là 60% các khách hàng mua máy tính cũng mua phần mềm. Khai phá luật kết hợp được thực hiện qua 2 bước: Bước 1: tìm tất cả các tập mục phổ biến, một tập mục phổ biến được xác định qua tính độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu. Bước 2: sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu. Luật kết hợp có khả năng ứng dụng trong nhiều lĩnh vực khác nhau như kinh doanh, y học, tài chính, thị trường chứng khoán, phân tích quyết định, phân tích thị trường, … Tuy luật kết hợp là một dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa. Thông tin mà dạng luật này đem lại rất có lợi trong các hệ hỗ trợ gia quyết định. Tìm kiếm được những luật kết hợp đặc trưng và mang nhiều thông tin từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực Khai phá dữ liệu. 3.4.2.3. Khai thác mẫu tuần tự (Sequential / Temporal patterns): Tương tự như khai thác luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X -> Y phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính dự báo cao. 3.4.2.4. Phân nhóm- đoạn (Clustering / Segmentation): Mục tiêu chính của việc phân nhóm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các nhóm sao cho mức độ tương tự giữa các đối tượng trong cùng một nhóm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các nhóm khác nhau là nhỏ nhất. Các nhóm có thể tách nhau hoặc phân cấp gối lên nhau và số lượng các nhóm là chưa biết trước. Một đối tượng có thể vừa thuộc nhóm này, nhưng cũng có thể vừa thuộc nhóm khác. Không giống như phân lớp dữ liệu, phân nhóm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân nhóm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example). Trong phương pháp này bạn sẽ không thể biết kết quả các nhóm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các nhóm thu được. Phân nhóm còn được gọi là học không có giám sát (unsupervised learning). Phân nhóm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web, … Ngoài ra phân nhóm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán Khai phá dữ liệu khác. Theo Gray & Orlowska thì các thuật toán phân nhóm bao gồm một trong hai dạng thức điển hình sau: - Phân nhóm theo thứ bậc (Hierarchical clustering): Các thuật toán này định dạng tập dữ liệu bằng cách lặp đi lặp lại việc nối hoặc phân chia những nhóm đã tồn tại vào trong các nhóm mới. Lợi ích của việc phân nhóm theo thứ bậc là sinh ra các luật rõ ràng từ dữ liệu mà không cần giám sát. Nhưng bất lợi của nó là các thuật toán phân nhóm theo vùng thực thi tốt hơn so với việc phân theo thứ bậc. - Phân nhóm theo vùng (Partition-clustering): Các thuật toán này sẽ phân tách tập dữ liệu bằng một con số nhóm xác định bằng việc lặp đi lặp lại việc lựa chọn các điểm tiêu biểu cho mỗi một nhóm, xác định sự phân chia dữ liệu dựa trên những điểm đặc trưng này và đánh giá các vùng thông qua khoảng cách hoặc tiêu chuẩn mô hình cơ bản. Các kỹ thuật đo khoảng cách tìm ra k-cách (k-way) phân chia tốt nhất, vì vậy các trường hợp nằm trong mỗi một khối thuộc một vùng sẽ gần nhau hơn (về khoảng cách) so với các trường hợp trong các vùng khác khác. Các kỹ thuật về mô hình cơ bản tìm sự thích hợp nhất cho một mô hình giả thiết đối với mỗi nhóm. Có thể các phép đo được sử dụng để độ thích hợp của mô hình đối với một nhóm. 3.4.2.5. Hồi quy (Regression). Phân tích hồi qui (regression analysis) là một công cụ mà nhiều người biết. Dạng đơn giản nhất, xây dựng một mô hình dự đoán để liên kết một biến dự đoán X (predictor variable), với một biến trả lờI Y (response variable), thông qua một mối liên hệ dạng Y=aX + b. Ví dụ, chúng ta muốn xây dựng một mô hình cho phép dự đoán mức tiết kiệm của một người khi cho biết thu nhập của họ. Rõ ràng là mô hình có thể sẽ không là hoàn hảo, nhưng do mức tiết kiệm tăng cùng với mức thu nhập, vì vậy mô hình có thể là mô tả thô (rough characterization). Đối chiếu với các bước liệt kê ở trên, chúng ta có kịch bản sau: Biểu diễn là một mô hình mà biến trả lời, mức tiết kiệm, là phụ thuộc tuyến tính với biến dự đoán, mức thu nhập, Hàm cho điểm đuợc sử dụng chung nhất trong tình huống này là tổng các bình phương sự khác nhau (sum of squared discrepancies) giữa mức tiết kiệm dự đoán của mô hình và mức tiết kiệm quan sát trong dữ liệu. Tổng này càng nhỏ thì mô hình càng phù hợp với dữ liệu, Giải thuật tối ưu là không phứp tạp trong trường hợp hồi qui tuyến tính: a và b có thể được tính toán như các hàm tường minh của các giá trị quan sát của các biến mức tiết kiệm và mức thu nhập. Trừ khi tập dữ liệu là lớn, một vài vấn đề quản lý dữ liệu nảy sinh với các giải thuật hồi qui. Các tổng số của dữ liệu (tổng số, tổng các bình phương, tổng của các tích các giá trị X và Y) dễ dàng được thực hiện một cách hiệu quả để cuối cùng ước lượng a và b. Chỉ cần một lần duyệt CSDL sẽ sinh ra các ước lượng của a và b. Trong Khai phá dữ liệu, hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng hạn như hồi quy tuyến tính. Tuy nhiên phương pháp mô hình hóa cũng có thể được sử dụng như Cây quyết định. ứng dụng của hồi quy là rất nhiều, ví dụ: Dự đoán số lượng sinh vật phát quang hiện thời trong khu rừng bằng cách dò tìm vi sóng của các thiết bị cảm biến từ xa, ước lượng xác suất người bệnh có thể chết bằng cách kiểm tra các triệu chứng bệnh lý, dự báo nhu cầu của người dùng đối với một sản phẩm, ... 3.4.2.6. Tổng hợp hóa (Summarization). Là công việc liên quan đến các phương pháp tìm kiếm một mô tả tập con dữ liệu. Kỹ thuật mô tả khái niệm và tổng hợp hóa thường áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Nhiệm vụ chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trưng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận”. Cần lưu ý rằng luật dạng này có khác biệt so với luật phân lớp. Luật phát hiện đặc trưng cho lớp chỉ sản sinh khi các mục đã thuộc về lớp đó. 3.4.2.7. Mô hình hóa sự phụ thuộc (dependency modeling). Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính theo hai mức. Mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị), trong đó, các biến phụ thuộc bộ phận vào các biến khác. Và mức định lượng mô hình mô tả mức độ phụ thuộc. Những phụ thuộc này thường được biểu thị dưới dạng theo luật “nếu - thì” - nếu tiền đề đúng thì kết luận đúng. Về nguyên tắc, cả tiền đề và kết luận đều có thể là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiền đề thường là nhóm các giá trị thuộc tính và kết luận chỉ là một thuộc tính. Hơn nữa, hệ thống có thể phát hiện các luật phân lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do người dùng chỉ ra trong kết luận. Quan hệ phụ thuộc cũng có thể biểu diễn dưới dạng mạng tin cậy Bayes. Đó là đồ thị có hướng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của liên kết phụ thuộc giữa các nút đó. 3.4.2.8. Phát hiện sự biến đổi và độ lệch (Change and deviation detection). Nhiệm vụ này tập chung vào khám phá hầu hết sự thay đổi có nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn, phát hiện độ lệch đáng kể giữa nội dung của tập con dữ liệu thực và nội dung mong đợi. Hai mô hình độ lệch hay dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian là sự thay đổi có ý nghĩa của dữ liệu thời gian. Độ lệch theo nhóm là sự khác nhau của dữ liệu trong hai tập con dữ liệu, ở đây xét cả trường hợp tập con dữ liệu này thuộc tập con kia. Nghĩa xác định dữ liệu trong một nhóm con của đối tượng có khác đáng kể so với toàn bộ đối tượng không? Theo cách này, sai sót dữ liệu hay sai lệch so với giá trị thông thường sẽ được phát hiện. Vì những nhiệm vụ này, yêu cầu số lượng và các dạng thông tin rất khác nhau nên chúng thường ảnh hưởng đến việc thiết kết và chọn phương pháp Khai phá dữ liệu khác nhau. 3.4.3. Những vấn đề khó khăn trong Khai phá dữ liệu. Như chúng ta đã biết Khai phá dữ liệu là một lĩnh vực liên ngành và được ứng dụng rất rộng rãi trên nhiều lĩnh vực. Tuy nhiên với đặc điểm là việc xử lý các CSDL lớn nên Khai phá dữ liệu cũng có những vấn đề khó khăn của riêng mình. ở đây chúng ta sẽ xem xét một số vấn đề sau: 3.4.3.1. Vấn đề về CSDL. Đầu vào của một hệ thống Khai phá dữ liệu thường là tập các dữ liệu thô sơ nhiều lúc không đầy đủ và bị nhiễu bởi nhiều nguyên nhân khác nhau. Ngoài ra trong thực tế dữ liệu lại luôn luôn biến động không ngừng và được bổ xung liên tục tạo thành một lượng dữ liệu khổng lồ chứa đựng cả những thông tin có ích và không có ích. Chính vì vậy trong bất kỳ một hệ Khai phá dữ liệu nào việc đầu tiên cần làm là phân tích và xem xét CSDL mà hệ thống sẽ khai phá. 3.4.3.1.1. CSDL lớn. Việc sử dụng công cụ phân tích trực tuyến không khai thác được hết những thông tin của CSDL hiện thời, chính vì vậy những người xử lý dữ liệu không còn cách nào khác là lưu dữ liệu lại để phục vụ cho việc sử dụng sau này. Dữ liệu được lưu trữ chứa đựng cả thông tin hữu ích chưa được khai phá và cả những thông tin không có ích. Việc tích lũy này ngày càng lớn và cho đến nay các CSDL tới hàng triệu bản ghi có kích thước lên đến Tetabytes là chuyện bình thường. Tùy từng ứng dụng cụ thể, việc làm như thế nào để loại bỏ những dữ liệu thừa, những thông tin vô nghĩa lại có những cách thức khác nhau, vì vậy phương pháp xử lý dữ liệu hết sức đa dạng và phức tạp, không có một quy tắc chung nhất cho mọi ứng dụng. 3.4.3.1.2. Số chiều dữ liệu lớn. Tập dữ liệu thực chất là một tập các số đo từ môi trường hoặc quá trình. Trường hợp đơn giản nhất, chúng ta có tập hợp các đối tượng, mỗi đối tượng có một tập p số đo. Số đo chính là thuộc tính của các thực thể (đối tượng, bản ghi, ...). Cùng với yêu cầu của thông tin là đa dạng và đầy đủ mà dữ liệu cần lưu được thì số lượng các thuộc tính cũng cần phải nhiều lên. Mỗi một thuộc tính có thể được coi là một chiều trong không gian CSDL. Chính vì thể số chiều của bài toán trong hệ Khai phá dữ liệu cũng rất lớn. Một tập dữ liệu có số chiều lớn sẽ làm tăng không gian tìm kiếm của mô hình suy diễn. Hơn nữa nó sẽ làm tăng khả năng tìm thấy các mẫu giả trong các giải thuật của Khai phá dữ liệu. Biện pháp khắc phục vấn đề này là phải giảm số chiều của dữ liệu cần khai phá, và sử dụng các tri thức có sẵn để loại bỏ những biến không phù hợp. 3.4.3.1.3. Dữ liệu thay đổi liên tục. Đặc điểm cơ bản của hầu hết các CSDL là nội dung của chúng thay đổi liên tục. Đặc điểm này chính là việc dữ liệu có thể thay đổi theo thời gian và gây ra hệ quả là việc Khai phá dữ liệu bị ảnh hưởng tại thời điểm quan sát dữ liệu. Ví dụ trong CSDL thị trường chứng khoán, một số giá trị thuộc tính là hằng số, một số khác lại thay đổi liên tục theo thời gian như giá cổ phiếu, chỉ số Index, trong khi đó một số khác lại thay đổi tùy thuộc vào tình huống như số lượng cổ phiếu được giao dịch trong một phiên, ... Việc thay đổi dữ liệu nhanh chóng có thể làm mất giá trị của các mẫu trước đó, hơn nữa các biến trong CSDL của ứng dụng đã cho cũng bị thay đổi, bị xóa hoặc bị tăng lên theo thời gian. 3.4.3.1.4. Các thuộc tính dữ liệu không phù hợp. Một đặc điểm quan trọng khác của CSDL là tính không phù hợp của dữ liệu, nghĩa là mục dữ liệu trở thành không thích hợp với ý nghĩa hiện tại của việc khai phá. Một khía cạnh khác của tính không phù hợp của thuộc tính đó là giá trị của thuộc tính đó không phản ánh được ý nghĩa hiện tại mà chỉ thích hợp trong lịch sử của nó. 3.4.3.1.5. Dữ liệu bị thiếu không đầy đủ. Việc thiếu hụt không đầy đủ ở đây bao hàm cả sự không đầy đủ về giá trị và thuộc tính của dữ liệu. Sự có mặt hay không có mặt của giá trị các thuộc tính phù hợp ảnh hưởng rất lớn đến việc Khai phá dữ liệu. Việc quan sát không đầy đủ một CSDL có thể đưa đến các kết luận sai lầm. Việc quan sát dữ liệu phải được thực hiện trên toàn bộ các thuộc tính hữu ích có thể dùng các giải thuật về Khai phá dữ liệu để áp dụng giải quyết bài toán. Chính việc thiếu hụt dữ liệu có thể gây lên việc tìm ra các mẫu giả, dẫn đến kết quả là tri thức khám phá được có thể sai lệch với thực tế. 3.4.3.1.6. Dữ liệu bị nhiễu và không chắc chắn. Ngoài việc dữ liệu bị lỗi hay không đầy đủ thì bản thân dữ liệu cũng tiềm ẩn khả năng bị nhiễu, không chắc chắn. Đối với các thuộc tính đã phù hợp, thì giá trị của thuộc tính đó có thực tế phản ánh được quy luật trong dữ liệu hay không? Các giá trị của các thuộc tính khác nhau có thể là các số thực, số nguyên, có thể là chuỗi hoặc là tập các giá trị định danh. Các giá trị định danh này có thể được sắp xếp theo thứ tự từng phần, đầy đủ và thậm chí có thể có cấu trúc ngữ nghĩa. Một yếu tố khác của độ nhiễu chính là tính kế thừa hoặc độ chính xác mà dữ liệu cần có. Nói cách khác là độ nhiễu trên các phép đo và phân tích có ưu tiên. Mô hình thống kê mô tả tính ngẫu nhiên được tạo ra và được sử dụng để định nghĩa độ mong muốn và độ dung sai của dữ liệu. Thường thì các mô hình thống kê được áp dụng theo các cách đặc biệt để xác định một cách chủ quan các thuộc tính để đạt được các đánh giá thống kê của các giá trị thuộc tính. Đặc biệt đối với dữ liệu kiểu số, sự đúng đắn của dữ liệu là một yếu tố vô cùng quan trọng trong việc Khai phá. Ví dụ trong cách đo nhiệt độ cơ thể có thể cho phép chênh lệch đến 0,1 độ. Nhưng nếu phân tích theo xu hướng nhạy cảm nhiệt độ của cơ thể thì cần độ chính xác cao hơn nhiều. 3.4.3.1.7. Mối quan hệ phức tạp giữa các thuộc tính. Dữ liệu tồn tại trong nhiều dạng (forms) và không đặt trong một sự phân cấp đầy đủ (complete taxonomy). Thực vậy, rất khó xây dựng một phân cấp đầy đủ do một khía cạnh của dữ liệu trong tình huống này có thể lại không quan trọng trong tình huống khác. Dù vậy, có những sự phân biệt rõ ràng mà chúng ta nên để ý tới. Một là sự khác nhau giữa các số đo phân loại và định lượng. Các thuộc tính định lượng được đo trong một thang số và có thể nhận một giá trị bất kỳ (ví dụ bảng lương, giá cổ phiếu, ...). Ngược lại, các biến có giá trị thuộc tính phân loại (categorical variables) như là giới tính, trạng thái, loại cổ phiếu, trình độ học vấn, ... chỉ có thể nhận giá trị xác định, rời rạc. Các thuộc tính có giá trị phân loại có thể là sắp thứ tự được (có thứ tự tự nhiên, như là trình độ học vấn) hoặc là tên của các loại (đặt tên đơn giản cho các loại, như là marital status - tình trạng hôn nhân). Một kỹ thuận phân tích dữ liệu chỉ thích hợp cho một kiểu dữ liệu này mà có thể không thích hợp với kiểu dữ liệu khác (mặc dù nó dựa trên cùng mục đính phân tích). Ví dụ, ngay cả khi tình trạng hôn nhân được biểu diễn bằng số nguyên (1 ứng với chưa có gia đình, 2 - đã có gia đình, 3 - góa, ...), nó cũng sẽ không có nghĩa hoặc không thích hợp để tính giá trị trung bình thuộc tính này trên mẫu (sample). Tương tự, hồi qui tuyến tính đơn giản (dự đoán một biến định lượng như một hàm của các biến khác) thường thích hợp áp dụng cho biến định lượng, áp dụng nó cho dữ liệu có giá trị phân loại là không phù hợp; các kỹ thuật khác có mục tiêu tương tự (mục tiêu có thể giống nhau đối với các kiểu dữ liệu khác nhau), có thể thích hợp hơn với kiểu có giá trị phân loại. Các mối quan hệ giữa các thuộc tính và các phương tiện phức tạp để diễn tả tri thức về nội dung của CSDL yêu cầu các giải thuật phải có khả năng sử dụng một cách hiệu quả thông tin này. Ban đầu, kỹ thuật Khai phá dữ liệu chỉ được ứng dụng cho các thực thể có giá trị thuộc tính đơn giản. Tuy nhiên, ngày nay người ta đang tìm cách phát triển các kỹ thuật nhằm rút ra mối quan hệ giữa các biến này. 3.4.3.2. Các vấn đề khác. 3.4.3.2.1. Vấn đề Overfitting. Với các hệ thống Khai phá dữ liệu theo mô hình học có giám sát, tức là học theo tri thức đã biết trước, khi đó việc Khám phá dữ liệu có thể sẽ xảy ra tình trạng quá phù hợp với kết quả đã biết, nghĩa là kết quả của mô hình có thể sẽ phù hợp với tập dữ liệu huấn luyện nhưng lại không thực sự đưa ra các tri thức tốt theo nghĩa ứng với tập dữ liệu kiểm tra. Như vậy, nếu để xảy ra tình trạng overfitting thì mô hình hoạt động sẽ rất kém hiệu quả. Để khắc phục tình trạng này thường phải thực hiện thêm việc kiểm tra chéo (cross validation) để đánh giá mô hình, hoặc sử dụng các biện pháp thống kê cổ điển. 3.4.3.2.2. Khả năng biểu đạt của mẫu. Trong ứng dụng, điều quan trọng là phải diễn giải kết quả của bài toán càng rõ ràng, càng gần gũi, dễ hiểu đối với người sử dụng càng tốt. Cũng như vậy, một hệ thống Khai phá dữ liệu yêu cầu tính giải thích những tri thức rút trích được từ dữ liệu. Những tri thức này được mô tả từ các tập luật, mô hình đồ thị hoặc ngôn ngữ tự nhiên hay sử dụng các kỹ thuật trực quan hóa dữ liệu và tri thức, ... 3.4.3.2.3. Khả năng tương tác với người sử dụng. Rất nhiều công cụ và phương pháp Khai phá dữ liệu không thực sự có khả năng tương tác với người sử dụng và không dễ dàng kết hợp cùng với các tri thức đã biết trước đó. Việc sử dụng tri thức miền là rất quan trọng trong Khai phá dữ liệu. Có nhiều biện pháp khắc phục vấn đề này như sử dụng CSDL suy diễn để phát hiện tri thức, những tri thức này sau đó được sử dụng để hướng dẫn cho việc tìm kiếm, Khai phá dữ liệu hoặc sử dụng sự phân bố xác suất dữ liệu trước đó như một dạng mã hóa tri thức có sẵn. 3.4.3.2.4. Khả năng tích hợp với các hệ thống khác. Một ứng dụng để đạt được hiệu quả cao và linh hoạt cần có khả năng tích hợp với các hệ thống khác, nhưng trên thực tế việc này khá khó khăn trong các hệ Khai phá dữ liệu. Điều này xuất phát từ chính trong các kỹ thuật Khai phá dữ liệu là phải xây dựng một mô hình phù hợp để tìm ra các mẫu đặc trưng. 3.5. SO SÁNH KHAI PHÁ DỮ LIỆU VỚI MỘT SỐ PHƯƠNG PHÁP CỔ ĐIỂN. Như đã biết, Khai phá dữ liệu là một lĩnh vực liên quan tới rất nhiều ngành học khác như: hệ CSDL, thống kê, trực quan hóa, ... Hơn nữa, tuỳ vào cách tiếp cận được sử dụng, Khai phá dữ liệu còn có thể áp dụng một số kỹ thuật như mạng nơ ron, lí thuyết tập thô hoặc tập mờ, biểu diễn tri thức, … So với các phương pháp này, khai phá dữ liệu có một số ưu thế rõ rệt: + So với phương pháp học máy: Khai phá dữ liệu có lợi thế hơn ở chỗ, Khai phá dữ liệu có thể sử dụng với các CSDL chứa nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục. Trong khi đó phương pháp học máy chủ yếu được áp dụng trong các CSDL đầy đủ, ít biến động và tập dữ liệu không quá lớn, + Với phương pháp hệ chuyên gia: Phương pháp này khác với Khai phá dữ liệu ở chỗ các tri thức của chuyên gia thường ở mức chất lượng cao hơn nhiều so với các dữ liệu trong CSDL, và chúng thường chỉ bao hàm được các trường hợp quan trọng. Hơn nữa các chuyên gia sẽ xác nhận giá trị và tính hữu ích của các mẫu phát hiện được, + Phương pháp thống kê: Là một trong những nền tảng lí thuyết của Khai phá dữ liệu, nhưng khi so sánh hai phương pháp với nhau ta có thể thấy các phương pháp thống kê còn tồn tại một số điểm yếu mà Khai phá dữ liệu đã khắc phục được: Các phương pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều các CSDL, Các phương pháp thống kê hoạt động hoàn toàn theo dữ liệu, nó không sử dụng tri thức sẵn có về lĩnh vực, Kết quả phân tích của thống kê có thể sẽ rất nhiều và khó có thể làm rõ được, Phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu, 3.6. HƯỚNG NGHIÊN CỨU VÀ VIỆC ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU HIỆN NAY. Khai phá dữ liệu là một lĩnh vực mới và mặc dù còn rất nhiều vấn đề chưa được nghiên cứu một cách chọn vẹn, nhưng tiềm năng và khả năng ứng dụng của nó rất cao và đã được chứng minh qua nhiều ứng dụng thực tế. Hiện nay có một số hướng nghiên cứu mà Khai phá dữ liệu quan tâm đến là: OLAM (OnLine Analytical Mining) : Là sự tích hợp giữa CSDL, kho dữ liệu, và Khai phá dữ liệu. Một số hệ cơ sở dữ liệu như Oracle, MS SQL Server đã tích hợp tính năng xây dựng kho dữ liệu và phân tích trực tuyến (OLAP). Những tính năng này được hỗ trợ dưới dạng các công cụ đi kèm và người sử dụng phải mua nếu cần sử dụng. Các nhà nghiên cứu trong lĩnh vực CSDL còn muốn có thêm sự tích hợp giữa CSDL, kho dữ liệu, và Khai phá dữ liệu. Khám phá được nhiều tri thức khác nhau từ các kiểu dữ liệu khác nhau. Tính chính xác và hiệu quả, khả năng mở rộng và tích hợp, xử lý dữ liệu bị nhiễu không đầy đủ và tính có ích của tri thức được khám phá. Vấn đề song song hoá và phân tán quá trình Khai phá dữ liệu. Vấn đề ngôn ngữ truy vấn trong Khai phá dữ liệu phải cung cấp cho người sử dụng một ngôn ngữ thuận tiện, gần gũi tương tự như SQL trong CSDL quan hệ. Biểu diễn các tri thức khai phá được sao cho trực quan và gần gũi với người sử dụng để người sử dụng tri thức có hiệu quả hơn. Khai phá dữ liệu đã được ứng dụng rất thành công trong CSDL thị trường, đây là một phương pháp phân tích CSDL khách hàng, tìm kiếm các mẫu trong số các khách hàng và sử dụng các mẫu này để lựa chọn các khách hàng tiềm năng trong tương lai. Tạp chí Business Week của Mỹ đã đánh giá có hơn 50% các nhà bán lẻ đang và có ý định sử dụng CSDL thị trường cho hoạt động kinh doanh của họ. Các ứng dụng khác của Khai phá dữ liệu trong kinh doanh như phân tích thị trường chứng khoán, phân tích các văn kiện tài chính, phân tích và báo cáo các thay đổi trong dữ liệu bán hàng của siêu thị, phát hiện và phòng chống gian lận, … 3.7. ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU –KHÁM PHÁ TRI THỨC. Khám phá tri thức và Khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực như: Thống kê, Trí tuệ nhân tạo, Hệ chuyên gia, CSDL, thuật toán, tính toán song song, CSDL, ... Đặc biệt Khám phá tri thức và Khai phá dữ liệu rất gần gũi với lĩnh vực thống kê, sử dụng các phương pháp thống kê để mô hình dữ liệu và phát hiện các mẫu, luật, ... Các CSDL lớn và các công cụ phân tích trực tuyến (OLAP) cũng liên quan rất chặt chẽ với công cụ Khai phá dữ liệu và Khám phá tri thức. Một hệ thống Khai phá dữ liệu điển hình bao gồm các phương thức, thuật toán, kỹ thuật từ nhiều lĩnh vực khác nhau, điểm chung giữa các hệ thống này là chúng đều trích rút từ các kho dữ liệu có kích thước rất lớn. Khai phá dữ liệu - Khám phá tri thức được sử dụng rất nhiều trong các lĩnh vực khoa học, kinh doanh, ..., đặc biệt trong các ngành có CSDL lớn, phức tạp, chứa đựng nhiều tri thức như: Bảo hiểm, tài chính và TTCK: ở đây Khai phá dữ liệu có nhiệm vụ phân tích tình hình tài chính và dự báo giá, chỉ số của các loại cổ phiếu trong TTCK. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện các giao dịch gian lận, ... Thống kê, phân tích dữ liệu và hỗ trợ ra quyết định: Dựa vào dữ liệu sẵn có, phân tích dự liệu để đưa ra những quyết định đúng lúc, có lợi nhất. Điều trị y học và chăm sóc y tế: Một số thông tin về chuẩn đoán bệnh lưu trong các hệ thống quản lý bệnh viện, từ đó phân tích các mối liên hệ giữa triệu chứng bệnh, chuẩn đoán và phương pháp điều trị hợp lý. Text Mining và Web Mining: Phân lớp văn bản và các trang Web, tóm tắt nội dung văn bản, ... từ đó có thể nhóm các văn bản, trang Web theo các chủ đề, lọc bỏ các trang Web độc hại, ... Quản trị mạng và phát hiện các truy cập bất thường: Phân tích các dữ liệu truy cập để phát hiện ra các truy cập bất thường hay các truy cập với mục đích xấu. Lĩnh vực khoa học: Quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật, tìm kiếm, so sánh các hệ gene và thông tin di truyền đã được mã hóa, mối liên hệ gene với một số bệnh di truyền ... Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi, sự cố, chất lượng dịch vụ, ... CHƯƠNG IV : ỨNG DỤNG QUY TRÌNH KHÁM PHÁ TRI THỨC VÀO VIỆC PHÂN TÍCH CSDL CHỨNG KHOÁN (CSDL CHUỖI THỜI GIAN) 4.1. CÁC KHÁI NIỆM VỀ CSDL CHUỖI THƠI GIAN. a. CSDL chuỗi thời gian - Time Series DataBase (TSDB): Cơ sở dữ liệu chuỗi thời gian là một tập hợp các bản ghi , trong đó mỗi một bản ghi chứa một tập các thuộc tính và giá trị thời gian [6]. Mỗi một thuộc tính có thể nhận giá trị thực hoặc giá trị rời rạc và có hoặc không có mối liên hệ với giá trị thời gian. Nếu thuộc tính có mối liên hệ với giá trị thời gian thì nó được gọi là thuộc tính động, trong trong trường hợp ngược lại thì được gọi là thuộc tính tĩnh. Còn giá trị thời gian được đưa ra trên thang chia thời gian ứng với mỗi khoảng thời gian, ví dụ như là phút, ngày, tháng, năm. b. Hàm thuộc tính: đó là hàm của thời gian mà các phần tử của nó là các giá trị của thuộc tính trong bản ghi, ký hiệu là . (4.1) Trong đó – là thuộc tính theo thời gian với khoảng (Interval) thời gian ; – là bản ghi thứ trong CSDL chuỗi thời gian với interval thời gian ; – là nhãn thời gian tương ứng với bản ghi đó. Nếu như hàm thuộc tính có thể được sấp xỉ cũng bởi một hàm thời gian khác trên khoảng thời gian thì người ta nói rằng và các tham số của nó chính là đặc tínhg của trên khoảng thời gian . Ví dụ, nếu trên một khoảng thời gian nào đó, thì có thể nói rằng trong khoảng thời gian đó hàm có độ lệch , ở đây độ lệch chính là đặc tính được rút ra từ trên một khoảng thời gian nào đó. Sự thay đổi các đặc chưng giữa hai khoảng thời gian liền kề được gọi là sự kiện. Thường thì dữ liệu của CSDL thời gian được sinh ra từ các hệ thống “nhiễu loạn”. Hệ thống nhiều loạn là một hệ thống mà các đối tượng trong nó chịu tác động của rất nhiều các yếu tố khác nhau, ngẫu nhiên và không xác định. Ví dụ như, sự phát triển của các chỉ số chứng khoán chịu ảnh hưởng của rất nhiều các yếu tố như tính chất của thị trường (mới hay đã ổn định), trình độ và tâm lý của nhà đầu tư, trình độ phát triển kinh tế xã hội, các biến đổi của tình hình kinh tế – tài chính trên thế giới, các biến động do tự nhiên gây ra vv… 4.2. CSDL THỊ TRƯỜNG CHỨNG KHOÁN. Cở sở dữ liệu chứng khoán là một trong những dạng điển hình của CSDL chuỗi thời gian, nó phản ánh các hoạt động thương mại của sàn giao dịch trên thế giới thực. Với mỗi một khoảng thời gian (Interval) và một chỉ số xác định luôn ứng với một tập các giá của phiên giao dịch Mua-Bán, đó là: giá mở (Open), giá Max(Hight), giá Min (Low) và giá đóng (Close). Các yếu tố ảnh hưởng đến tập các giá trị này hết sức là đa dạng, ngẫu nhiên và không xác định : chẳng hạn như tính chất của thị trường chứng khoán (chưa ổn định, hay đã ổn định vv..), trình độ, tâm lý người chơi, tình hình kinh tế chính trị trong nước và ngoài nước, các tác động của tự nhiênvv.. đều có thể ảnh hưởng đến giá của chỉ số chứng khoán. Và như vậy khi tham gia vào đầu tư chứng khoán, ngoài các phân tích tài chính đơn thuần, thì một quy trình phân tích không thể thiếu nữa đó là phân tích ký thuật, đây là mọtt trong những giải pháp được ưa chuộng và đem lại hiệu quả rất tốt. Phân tích kỹ thuật dựa trên việc áp dụng CNTT vào việc phân tích CSDL chứng khoán để đưa ra các dự báo về xu hướng phát triển của chỉ số chứng khoán. Và hiện nay, việc áp dụng quy trình khám phá tri thức để phát triển các hệ thống phân tích kỹ thuật, đặc biệt là xu hướng dự báo đang là một giải pháp khá hiệu quả và được nhiều nhà phân tích nghiên cứu, ứng dụng. 4.3 CÁC ĐẶC ĐIỂM CỦA CSDL CHỨNG KHOÁN. - Đây là một dạng điển hình của cơ sở dữ liệu thời gian. - Hệ thống phân tích là một hệ thống “nhiễu loạn”, bởi giá trị của chỉ số chứng khoán chịu ảnh hưởng của rất nhiều yếu tố ngẫu nhiên, không xác đinh, như: tính chất của thi trường, trình độ, tâm lý nhà đầu tư, sựa phát triển và tiềm năng của các công ty niêm yết, tính chuyên nghiệp của đội ngũ môi giơi, ảnh hưởng của các biến động kinh tế - chính trị trong và ngoài nước …vv. - Các thông tin có ích phản ánh sự biến đổi của xu hướng của các chỉ số chứng khoán không thể hiện dưới dạng dữ liệu tường minh, mà nó tồn tại dưới dạng phi cấu trúc trong các trạng thái tự do của hệ thống. - Sự biến đổi xu hướng của chỉ số chứng khoán không chỉ được phản ánh trong giá trị của giá đóng (Close), mà nó còn được thể hiện ở sự trênh lệch giữa giá đóng, giá Max (Hight) và giá Min(Low) so với giá mở (Open). - Không gian giữ liệu cần phân tích là rất lớn, không đầy đủ và nhiều “nhiễu” . 4.4 TIỀN XỬ LÝ DỮ LIỆU CHUỖI THỜI GIAN. Như đã đề cập ở chương 2 và chương 3, trong quy trình khám phá tri thức công đoạn tiền xử lý dữ liệu là một bước rất quan trọng, làm nền tảng cho các giải thuật khai phá dữ liệu. Tuy nhiên thông thường trước khi thực hiện công đoạn này, người ta thường chuyển đổi dữ liệu cho phù hợp với tính chất và đặc điểm cần khai phá. Đối với các đối tượng biến đổi theo thời gian thì yêu cầu là phải tính đến khía cạnh thời gian khi thực hiện khai phá, có nghĩa là cần phả chuyển các dữ liệu ban đầu về các “tiết diện” thời gian khác nhau để kết hợp phân tích, mà thực chất là chuyển chúng về dưới dạng cấu trúc khoảng thời gian (Interval). Để làm điều đó ta phải dựa vào tính chất của đối tượng biến đổi. Cụ thể đối với chỉ số chứng khoán thì giá Open phản ánh giá khởi điểm của phiên giao dịch, giá Close phản ánh giá trị kết thúc một phiên giao dịch, giá Hight phản ánh giá trị lớn nhất trong phiên giao dịch, còn giá Low phản ánh giá trị nhỏ nhất. Khi đó chẳng hạn tao muốn chuyển đổi dữ liệu từ dạng 1 ngày (dữ liệu thô ban đầu) sang dữ liệu của Interval 5 ngày ta sẽ phải thực hiện như sau: Giả sử ta có tập giá trị của 5 ngày giao dịch đầu tiên lần lượt là Day1 : (Open1, Hight1, Low1, Close1). Day2: (Open2, Hight2, Low2,Close2). Day3: (Open3, Hight3, Low3 ,Close3). Day4: (Open4, Hight4, Low4, Close4). Day5: (Open5, Hight5, Low5, Close5). Thì khi đó bộ giá trị đầu tiên ứng với Interval 5 ngày sẽ là : (Open1, Max(Hight1, Hight2, Hight3, Hight4, Hight5), Min(Low1, Low2, Low3, Low4, Low5), Close5). Chú ý: Nếu ngày thứ nhất không có giao dịch thì giá trị Open của Interval sẽ được lấy sang giá trị Open của ngày thứ hai, còn nếu ngày thứ 5 không có giao dịch thì giá trị Close của Interval sẽ được lấy sang giá trị Close của ngày thứ 4. Cứ như vậy với việc chuyển các mốc Interval ta sẽ chuyển dữ liệu ban đầu về dữ liệu ứng với các khoảng thời gian khác nhau. Thực chất của quá trình tiền xử lý dữ liệu chính là lọc dữ liệu nhằm nhận được các dữ liệu “sạch” với càng ít các nhiễu hay tạp chất càng tốt. Giả sử dữ liệu thô bao gồm tín hiệu của xu hướng dài hạn và nhiễu , tức là : (4.2) Thủ thuật làm sạch thực chất là tìm ra là sấp xỉ gần đúng của . Để làm được điều đó chúng ta phải phân biệt được và . Tín hiệu nhiễu nó có tính chất ngẫu nhiên, và hàng ngày chịu tác động của rất nhiều các yếu tố từ các nguồn khác nhau. Ngược lại tín hiệu dài hạn thì ổn định và chịu tác động của rất ít các yếu tố. Nếu áp dụng khai triển Fourier (biểu diễn tín hiệu thành một dãy các sóng hình sin), chúng ta sẽ nhận thấy rằng, tín hiệu dài hạn được xây dựng chủ yếu từ các sóng có tần số thấp (thay đổi chậm theo thời gian), trong khi đó tín hiệu nhiễu lại được xây dựng từ sóng có tần số cao (thay đổi nhanh theo thời gian) . Do vậy thông thường để làm sạch dữ liệu người ta thường sử dụng thủ thuật lọc tần số thấp (Low Pass Filter - LPF). Có rất nhiều phương pháp lọc tần số thấp trong lĩnh vực thời gian và tần số, như: phương pháp trung bình trượt đơn giản, trung bình trượt có trọng số … Đại đa số các nhà phân tích hiện nay lựa chọn phương pháp làm trơn hàm mũ mà thực chất là việc tìm trung bình trượt hàm mũ EMA (Exponential Moving Average) với công thức hồi quy như sau: (4.3) Với, được gọi là hằng số làm trơn (hay trọng số), là giá trị cần làm trơn tại thời điểm , là giá trị đã làm trơn ở thời điểm , là dữ liệu thô tại thời điểm . Về mặt tính toán, phương pháp này yêu cầu số lượng tính toán ít góp phần làm tăng tốc độ trong quá trình phân tích dữ liệu. Còn về mặt phân tích khi biểu diễn trên đố thị thì đường trung bình trượt số mũ bám theo xu hướng biến đổi trơn hơn các phương pháp khác, đồng thời số điểm nhảy và điểm trễ cũng ít hơn [7], điều đó rất thuật tiện cho việc phân tích hệ đồ thị biến đổi của đối tượng quan sát. Để chọn hệ số cho quá trình lọc dữ liệu, người ta dựa vào đặc điểm của mối liên hệ của đối tượng quan sát giữa các chu kỳ kế tiếp nhau (khoảng thời gian liền kề nhau). Do các đối tượng biến đổi theo thời gian thường có tính chất là: sự biến đổi của các chu kỳ trước có ảnh hưởng nhất định lên các chu kỳ tiếp theo, do đó các nhà phân tích dữ liệu thường sử dụng các giá trị của dãy số Fibonacci để thiết lập hệ số . Trong bài toán chúng ta sẽ chọn. ở đây sở dĩ ta chọn tập hợp 3 giá trị bởi vì khi phân tích xu hướng biến đổi của các đối tượng biến đổi theo thời gian chúng ta cần phải kết hợp thành phần tĩnh (giá trị nhỏ - ) của xu hướng khi đó đường dữ liệu sau lọc sẽ phản ánh xu hướng dài hạn, và thành phần động (giá trị lớn - ) khi đó đường dữ liệu sau lọc bám theo đường dữ liệu thô dưới dạng đường cong trơn. Và ta có thể chuyển về công thức lọc dữ liệu cụ thể như sau: (4.4) Ở đây: là giá đóng tại thời điểm , là giá trị trung bình trượt số mũ tại thời điểm , là giá trị trung bình trượt số mũ tại thời điểm . Khi áp dụng phương pháp này vào thì trường FOREX, ta nhận được kết quả như hình 4.1: Hình 4.1: Trung bình trượt hàm mũ Trên hình 4.1, thể hiện đường trung bình trượt giá đóng của cặp chỉ số tiền tệ EUR-USD với khoảng thời gian 15 phút, đường mầu đen là đường trung bình trượt hàm mũ với chu kỳ , còn đường mầu xanh và màu đỏ là đường với chu kỳ . Đối với thị trường FOREX các phiên giao dịch được thực hiện theo đơn vị thời gian là phút, do đó khi phân tích dữ liệu của thị trường này các khoảng thời gian đưa vào phân tích cần tuân theo quy tắc: các khoảng thời gian cần cách nhâu một số lần nào đó, vì vậy chúng ta sẽ chọn . 4.5 CHỈ SỐ XU HƯỚNG TỔNG QUÁT. Sự thay đổi giá của thị trường chứng khoán được diễn ra dưới dạng các xu hướng, mà đặc tính của xu hướng lại được xác định bởi rất nhiều các yếu tố. Có rất nhiều các yếu tố khác nhau tác động lên sự dịch chuyển của gía chứng khoán mà chúng ta đã đề cập ở phần trước. Do đó, tại thời điểm xuất hiện xu hướng thì nguyên nhân xuất hiện của nó hầu hết là không rõ ràng. Các chỉ số kỹ thuật của thị trường chính là các công cụ được dùng để xác định các xu hướng cũng như những sự thay đổi trong chúng. Các chỉ số kỹ thuật hiện nay thường được giới hạn trong phạm vi số các chỉ số chứng khoán và từng interval thời gian cụ thể, thậm chí đôi khi các chỉ số lại là sự tổng hợp của các chỉ số khác. Giả sử - là hàm thuộc tính ứng với giá đóng của chỉ số chứng khoán thứ trong chu kỳ trên interval . Còn (, ) – là sấp xỉ gần đúng của nó dưới dạng các trung bình trượt hàm mũ với các chu kỳ T=8 (13, 55). Còn (, ) – là đặc tính của hàm thuộc tính, được định nghĩa giống như góc lệch của hàm sấp xỉ (giá trị đạo hàm). Khi đó chỉ số xu hướng tổng quát sẽ được tính theo công thức sau: (4.5) Nếu chỉ sử dụng một chỉ số I(t) thì sẽ rất khó khăn cho việc Khai phá dữ liệu, bởi I(t) mới chỉ được biểu diễn trên không gian một chiều, khó áp dụng cho việc tích lũy thống kê. Mặt khác, lại thấy I(t) cũng là tín hiệu biến đổi theo thời gian, nên ta có thể tiếp tục làm trơn tín hiệu này bằng phương pháp trung bình trượt hàm mũ lần nữa. Tuy nhiên, lúc này chỉ áp dụng với một tiết diện thời gian phù hợp, trong trường hợp này ta chọn interval=5 phút bởi vì đặc tính của thị trường FOREX các phiên giao dịch được thực hiện theo phút do đó khoảng thời gian 5 phút là một khoảng thời gian phù hợp. Giả sử (, ) – là trung bình trượt hàm mũ ứng với T=8 (13, 55), còn (, ) – là độ lệch của nó. Khi đó ta sẽ thiết lập được chỉ số xu hướng của chính I(t) như sau: (4.6) Hình 4.2: Chỉ số xu hướng Trên hình 3.2 thể hiện đồ thị của chỉ số xu hướng tổng quát (đồ thị ở giữa), và đồ thị của chỉ số xu hướng của chính là (đồ thị trên cùng). 4.6.PHÂN LOẠI TRẠNG THÁI CỦA HỆ THỐNG NHIỄU LOẠN – TÍCH LŨY THÔNG TIN THỐNG KÊ. Đối với các hệ thống nhiễu loạn để có thể tích lũy thông tin có ích của các trạng thái tự do bất kỳ, mà trong đó có chứa các quy luật biến đổi tiềm ẩn chúng ta phải thực hiện việc phân loại trạng thái của hệ thống, mà thực chất là việc chuyển không gian vô hạn các trạng thái tự do về không gian hữu hạn nào đó. Để làm được điều này, bắt buộc các nhà phân tích phải dựa vào đặc điểm của đối tượng quan sát, trong bài toán này đối tượng quan sát của chúng ta chính là giá Close của chỉ số chứng khoán. Và như ta đã nói ở trên, sự thay đổi của thị trường chứng khoán được diễn ra dưới dạng các xu hướng, và do đó ta sẽ dựa vào các chỉ số xu hướng để thực hiện việc phân loại trạng thái của hệ thống. Từ công thức 3.5 và 3.6 ta thấy , còn , như vậy nếu chia các miền giá trị của , lần lượt thành và đoạn bằng nhàu và biểu diễn chúng trên hệ tọa độ 2 chiều , khi đó ta sẽ nhận được cặp tọa độ, và ta coi mỗi cặp tọa độ đó là một trạng thái chuẩn của hệ thống. Rõ ràng là với việc tạo ra cặp chỉ số xu hướng và ta đã chuyển được không gian trạng thái của hệ thống từ vô hạn về hữu hạn, mỗi một trạng thái tự do của hệ thống sẽ được đặc chưng bởi cặp giá trị . Và khi đó ta sẽ phân tất cả các trạng thái tự do của hệ thống được bao bởi 4 trạng thái chuẩn gần chúng nhất vào một nhóm, sau đó tiến hành tích lũy thông tin có ích của chúng vào các trạng thái chuẩn với việc sử dụng hệ số tích lũy , ở đây hệ số chính là đặc chưng về mặt định lượng cho vị trí tương đối của trạng thái tự do so với trạng thái chuẩn , hệ số được tính toán theo công thức sau: (4.7) Trong đó, thang chia đối với miền gián trị của , còn là thang chia đối với miền giá trị của . Khi đó ta có thể thực hiện việc tích lũy thông tin thống kê theo công thức sau: (4.8) Trong đó, - là thông tin tích lũy của trạng thái chuẩn tại thời điểm , - là thông tin tích lũy của trạng thái chuẩn tại thời điểm , là hệ số tích lũy của trạng thái tự do tương ứng với trạng thái chuẩn , còn là thông tin có ích cần tích lũy, chẳng hạn như độ trênh lệch của giá đóng tại thời điểm so với thời điểm , nghĩa là , hoặc là độ lệch của giá đóng tại thời điểm so với giá mở ở thời điểm …vvv. Và ta có sơ đồ thuật toán sau: Hình 4.3 : Sơ đồ thuật toán tích lũy thông tin thống kê 4.7. DỰ BÁO TRẠNG THÁI CỦA HỆ THỐNG NHIỄU LOẠN. Sau khi đã thực hiện phân loại và tích lũy thông tin thống kê với một không gian dữ liệu đủ lớn, thì tại một thời điểm nào đó khi ta xác đính được giá trị của cặp chỉ số , ta có thể dự báo trạng thái của hệ thống này sau khoảng thời gian dựa trên thông tin tích lũy của 4 trạng thái chuẩn bao quanh - , khi đó trạng thái của hệ thống có thể được tính toán theo công thức sau: (4.9) Sơ đồ thuật toán cho việc xây dựng trạng thái tự do của hệ thống được thể hiện trên sơ đồ Hình 4.4 : sơ đồ thuật toán dự báo trạng thái của hệ thống nhiễu loạn Như vậy, với việc sử dụng cặp chỉ số ta đã tìm được một giải pháp phân loại trạng thái cho hệ thống “nhiễu loạn” cụ thể ở đây là TTCK, từ đó ta tiến hành tích lũy thông tin thống kê vào các trạng thái chuẩn, sau đó sử dụng bài toán ngược để xây dựng các trạng thái tự do của hệ thống tại một thời điểm nào đó trong tương lai khi biết được giá trị của cặp chỉ số . Đây chính là giai đoạn khai phá dữ liệu, tri thức mà chúng ta nhận được chính là các các thông tin có ích được tích lũy trong không gian trạng thái chuẩn của hệ thống. KẾT LUẬN 1. KẾT QUẢ ĐẠT ĐƯỢC. Với mục tiêu đặt ra, luận văn đã bày những vấn đề cơ bản nhất về khám phá tri thức và khai phá dữ liệu, nghiên cứu những bước cơ bản của một quy trình Khám phá tri thức. Đồng thời, trong luận văn cũng so sánh tổng thể lợi ích khi sử dụng Khai phá dữ liệu với những phương pháp cổ điển khi giải quyết các bài toán trên các hệ CSDL lớn, và những thành tựu đạt được khi áp dụng Khám phá tri thức - Khai phá dữ liệu trong thực tế. Trong luận văn cũng giới thiệu những khái niệm về cơ sở dữ liệu chuỗi thời gian, cùng với đó là một phương pháp hiệu quả cho công đoạn làm sạch dữ liệu chuỗi thời gian mà thực chất của nó là việc sử dụng phương pháp trung bình trượt hàm mũ để loại bỏ các “nhiễu” trong CSDL. Cùng với đó, luận văn cũng giới thiệu một phương pháp mới cho việc phân loại trạng thái và tích lũy thông tin thống kê bằng việc tạo ra cặp chỉ số xu hướng và , từ đó đưa ra bài toán dự báo trạng thái tự do của hệ thống tại một thời điểm nào đó trong tương lai. Trong quá trình thực hiện luận văn, mặc dù được sự chỉ bảo tận tình của thầy giáo hướng dẫn, được sự giúp đỡ của bạn bè và các thầy cô khác, cũng như sự cố gắng hết mình của bản thân; nhưng do thời gian có hạn và đây cũng là những vấn đề rất mới hiện nay, cho nên chắc chắn luận văn sẽ không tránh khỏi những hạn chế, thiếu sót. Rất mong được sự góp ý, nhận xét của các thầy cô, bạn bè, và những người quan tâm để tôi có thể hoàn thiện tốt hơn kết quả nghiên cứu của mình. 2. HƯỚNG NGHIÊN CỨU TIẾP THEO. Hiện nay Khai phá dữ liệu - Khám phá tri thức trong các hệ CSDL lớn và các bài toán về CSDL thời gian là những vấn đề đang được nhiều nhà khoa học tập trung nghiên cứu bởi các kết quả của nó rất có giá trị để ứng dụng trong nhiều lĩnh vực, nhất là trong các lĩnh vực kinh doanh và các lĩnh vực khoa học mang tính thời đại. Trong luận văn mới chỉ nghiên cứu tìm hiểu một cách cơ bản nhất quy trình khám phá tri thức – khai phá dữ liệu, cũng như đề cập đến một phương án cụ thể có thể áp dụng vào công đoạn khai phá dữ liệu. Vì vậy, trong thời gian tới tôi sẽ tập chung nghiên cứu một cách tổng thể về CSDL thời gian, xem xét các hướng tiếp cận mới đối với CSDL chuỗi thời gian, tìm hiểu và nghiên cứu rộng hơn nữa về các giải pháp khai phá dữ liệu, đặc biệt là trong vấn đề dự báo. Từ đó góp phần phát triển một hướng mới trong ngành công nghệ thông tin nước nhà đó là Khám phá tri thức – Khai phá dữ liệu. Tài liệu tham khảo 1. Bao Ho Tu (1998), Introduction to Knowledge Discovery and Data mining, Institute of Information Technology National Center for Natural Science and Technology. 2. Heikki Mannila(1998), Knowledge discovery in Databases, the search for frequent patterns, Hannu Toivonen. 3. Solange Oliveira Rezende, Robson Butaca T. de Oliveira, Luis Carlos Molina, FÐlix Claudio Alex Jorge da Rocha (2002); Visualization for Knowledge Discovery in Database; Department of Computer Science and Statistics Institute of Mathematical and Computer Sciences University of S·o Paulo, Brazil. 4. M. Goebel, L. Gruenwald (1999), “A Survey Of Data Mining And Knowledge Discovery Software Tools”, SIGKDD Explorations, Vol. 1, No. 1, P. 20-33. 5. U. M. Fayyad (1998), “Mining Databases: Towards Algorithms for Knowledge Discovery”, Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, Vol. 21, No. 1, P. 39-48 6. П. И. Васькин, Нгуен Доан Куонг (2005), “Анализ баз данных с применением временных рядов”, International Conference on Soft Computing and Measurements, Ses. 5, P. 239-241. 7. Dreyer W., Kotz Dittrich A., Schmidt D., “Research Perspectives for Time Series Management Systems”, Data Mining and Knowledge Discovery. 1994. Vol. 23, N 1. P. 10-15. 8. Nguyễn Kim Anh (2006), Nguyên lý của các hệ Cơ sở dữ liệu, Nhà xuất bản Đại học Quốc gia Hà nội .  Danh mục các ký hiệu, các từ viết tắt Từ viết tắt Tiếng Anh Tiếng Việt AI Artificial Intelligence Trí tuệ nhân tạo CNTT Information Technology Công nghệ thông tin CSDL Database Cơ sở dữ liệu EMA Exponential Moving Average Trung bình trượt hàm mũ DSSs Decision Support Systems Các hệ hỗ trợ ra quyết định EDA Exploratory Data Analysis Phân tích dữ liệu khám phá HQTCSDL Database management System – DBMS Hệ quản trị Cơ sở dữ liệu KDD Knowledge Discovery in Databases Khám phá tri thức trong các cơ sở dữ liệu LPF Low Pass Filter Lọc tần số thấp OLAM OnLine Analytical Mining Khai phá phân tích trực tuyến OLAP On-Line Analytical Processing Xử lý phân tích trực tuyến SQL Standard Query Language Ngôn ngữ vấn tin chuẩn TSDB Time Series DataBase CSDL chuỗi thời gian TTCK Securities Market Thị trường chứng khoán MỤC LỤC MỞ ĐẦU .................................................................................................................1 CHƯƠNG I : GIỚI THIỆU CHUNG..............................................................................1 1.1. Sự cần thiết của việc nghiến cứu quy trình khám phá tri thức – khai phá dữ liệu.................2 1.2. Mục đích nghiên cứu của đề tài. ...........................................................................................2 1.3. Phạm vi nghiên cứu của đề tài ...... .......................................................................................2 1.4. Cách thiết kế các phần nội dung chính trong bản thuyết minh..............................................3 CHƯƠNG II : TỔNG QUAN VỀ KHÁM PHÁ TRI THỨC – KHAI PHÁ DỮ LIỆU 2.1. Thế nào là Khám phá tri thức - Khai phá dữ liệu..................................................................4 2.2. Sự cần thiết của Khám phá tri thức........................................................................................5 2.3. Khám phá tri thức và các lĩnh vực liên quan..................................................................6 2.4 Thế nào là khai phá dữ liệu...............................................................................................7 2.5. Định nghĩa Khai phá dữ liệu..................................................................................................7 CHƯƠNG III : NGHIÊN CỨU QUY TRÌNH KHÁM PHÁ TRI THỨC 3.1. Các giai đoạn của quá trình Khám phá tri thức....................................................................10 3. 2. Nhiệm vụ của quá trình Khám phá tri thức.........................................................................12 3.3. Quy trình Khám phá tri thức................................................................................................14 3.4. Hướng tiếp cận và kỹ thuật chính trong Khai phá dữ liệu...................................................15 3.4.1.Các dạng dữ liệu có thể khai phá.............................................................................15 3.4.2.Các phương pháp,kĩ thuật chính trong khai phá dữ liệu...........................................16 3.4.2.1. Phân lớp và dự đoán (Classification & Prediction)....................................17 3.4.2.2. Phân tích luật kết hợp (Association Rules).................................................19 3.4.2.3. Khai thác mẫu tuần tự (Sequential / Temporal patterns)............................20 3.4.2.4. Phân nhóm- đoạn (Clustering / Segmentation)...........................................20 3.4.2.5. Hồi quy (Regression)..................................................................................21 3.4.2.6. Tổng hợp hóa (Summarization)..................................................................22 3.4.2.7. Mô hình hóa sự phụ thuộc (dependency modeling) ...................................22 3.4.2.8. Phát hiện sự biến đổi và độ lệch (Change and deviation detection)...........22 3.4.3. Những vấn đề khó khăn trong Khai phá dữ liệu. 3.4.3.1. Vấn đề về CSDL.........................................................................................23 3.4.3.1.1. CSDL lớn........................................................................................23 3.4.3.1.2. Số chiều dữ liệu lớn........................................................................23 3.4.3.1.3. Dữ liệu thay đổi liên tục.................................................................24 3.4.3.1.4. Các thuộc tính dữ liệu không phù hợp...........................................24 3.4.3.1.5. Dữ liệu bị thiếu không đầy đủ........................................................24 3.4.3.1.6. Dữ liệu bị nhiễu và không chắc chắn.............................................24 3.4.3.1.7. Mối quan hệ phức tạp giữa các thuộc tính......................................25 3.4.3.2. Các vấn đề khác..........................................................................................25 3.4.3.2.1. Vấn đề Overfitting..........................................................................25 3.4.3.2.2. Khả năng biểu đạt của mẫu............................................................26 3.4.3.2.3. Khả năng tương tác với người sử dụng.........................................26 3.4.3.2.4. Khả năng tích hợp với các hệ thống khác......................................26 3.5. So sánh Khai phá dữ liệu với một số phương pháp cổ điển.................................................26 3.6. Hướng nghiên cứu và việc ứng dụng của Khai phá dữ liệu hiện nay..................................27 3.7. ứng dụng của Khai phá dữ liệu - Khám phá tri thức............................................................28 CHƯƠNG IV : ỨNG DỤNG QUY TRÌNH KHÁM PHÁ TRI THỨC VÀO VIỆC PHÂN TÍCH CSDL CHƯNG KHOÁN (CSDL CHUỖI THỜI GIAN) 4.1. Các khái niệm về CSDL chuỗi thời gian.............................................................................30 4.2. CSDL thị trường chứng khoán:...........................................................................................30 4.3 Các đặc điểm của CSDL chứng khoán.................................................................................31 4.4 Tiền xử lý dữ liệu chuỗi thời gian.........................................................................................32 4.5 Chỉ số xu hướng tổng quát ...................................................................................................35 4.6 Phân loại trạng thái của hệ thống nhiễu loạn – tích lũy thông tin thống kê..........................36 4.7. Dự báo trạng thái của hệ thống nhiễu loạn. .........................................................................38 KẾT LUẬN 1. Kết quả đạt được.....................................................................................................................41 2. Hướng nghiên cứu tiếp theo....................................................................................................41