Tài liệu Thuật toán phát hiện phần tử ngoại lai và ứng dụng

i LỜI CAM ĐOAN Tôi cam đoan những kết quả trong luận văn là của việc tìm hiểu, có trích dẫn và tham chiếu đến các nguồn tư liệu tin cậy. Nội dung luận văn không sao chép từ các kết quả của các luận văn, luận án khác. ii LỜI CẢM ƠN Lời đầu tiên, tôi xin được gửi lời cảm ơn sâu sắc nhất tới thầy giáo TS. Lê Văn Phùng, người thầy đã trực tiếp dành nhiều thời gian tận tình hướng dẫn, cung cấp những thông tin, tài liệu quý báu giúp đỡ tôi hoàn thành bản luận văn này. Tôi cũng xin gửi lời cảm ơn đến các giảng viên trường Đại học công nghệ thông tin và truyền thông - Đại học Thái Nguyên, các thầy Viện công nghệ thông tin - Viện hàn lâm khoa học công nghệ Việt Nam đã giảng dạy, truyền đạt những kiến thức và giúp đỡ tôi trong suốt quá trình học tập của mình. Tôi cũng xin gửi lời cảm ơn tới Phòng giáo dục và đào tạo huyện Văn Yên, tỉnh Yên Bái, đã tạo mọi điều kiện thuận lợi cho tôi tham gia khóa học và trong suốt quá trình hoàn thành luận văn. Cuối cùng, tôi xin cảm ơn những người thân, bạn bè và gia đình đã luôn cổ vũ động viên tôi hoàn thành luận văn tốt nghiệp này. Mặc dù đã hết sức cố gắng hoàn thành luận văn với tất cả sự nỗ lực của bản thân, nhưng luận văn không tránh khỏi những thiếu sót. Kính mong nhận được những ý kiến đóng góp của quý thầy cô và bạn bè, đồng nghiệp. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 05 tháng 05 năm 2016 Học viên Phạm Hồng Hải iii MỤC LỤC LỜI CAM ĐOAN ......................................................................................... I MỤC LỤC ................................................................................................. III DANH MỤC CÁC TỪ VIẾT TẮT ............................................................ VI DANH MỤC CÁC BẢNG, HÌNH VẼ ..................................................... VII MỞ ĐẦU ....................................................................................................... 1 CHƯƠNG 1. PHẦN TỬ NGOẠI LAI VÀ ỨNG DỤNG TRONG ............ 3 KHAI PHÁ DỮ LIỆU .................................................................................. 3 1.1 Khai phá dữ liệu và phát hiện tri thức ...................................................... 3 1.1.1 Một số khái niệm ................................................................................... 3 1.1.2 Khai phá dữ liệu .................................................................................... 3 1.1.3 Phát hiện tri thức ................................................................................... 5 1.2. MộT Số KHÁI NIệM LIÊN QUAN ĐếN PHầN Tử NGOạI LAI ................................. 7 1.2.1. Khái niệm về ngoại lai .......................................................................... 7 1.2.2. Khái niệm ngoại lai trong cơ sở dữ liệu ................................................ 9 1.3. Phát hiện các phần tử ngoại lai trong dữ liệu ......................................... 12 1.4 Ứng dụng phát hiện phần tử ngoại lai .................................................... 16 1.4.1 Phát hiện xâm nhập ............................................................................. 16 1.4.2 Phát hiện gian lận ................................................................................ 17 1.4.3 Phát hiện bảo hiểm yêu cầu bồi thường gian lận ................................. 18 1.4.4 Ứng dụng trong y tế công cộng............................................................ 18 1.4.5 Phát hiện thiệt hại công nghiệp ............................................................ 19 1.4.6 Xử lý hình ảnh ..................................................................................... 19 1.4.7 Mạng cảm biến .................................................................................... 20 CHƯƠNG 2. CÁC THUẬT TOÁN TÌM KIẾM PHẦN TỬ NGOẠI LAI THEO TỶ LỆ KHÁC BIỆT DB(PCT,DMIN) .......................................... 21 2.1. Định nghĩa các phần tử ngoại lai theo tỷ lệ khác biệt ............................ 21 iv 2.2 Thuật toán đánh giá theo ô..................................................................... 22 2.2.1 Các khái niệm và tính chất liên quan ................................................... 22 2.2.2 Thuật toán FindAllOutsM cho các tập dữ liệu trong bộ nhớ chính ...... 24 2.2.2.1 Tư tưởng thuật toán .......................................................................... 24 2.2.2.2 Mô tả thuật toán FindAllOutsM (Find All Outliers in Memory) ...... 26 2.2.2.3 Đánh giá độ phức tạp thuật toán trong không gian hai chiều ............ 28 2.2.2.4 Tổng quát cho trường hợp nhiều chiều ............................................. 30 2.2.2.5 Đánh giá độ phức tạp trong không gian nhiều chiều ........................ 31 2.3 Phát hiện các phần tử ngoại lai DB(pct,Dmin) trong các tập dữ liệu lớn, ở bộ nhớ ngoài................................................................................................. 32 2.3.1 Phân tích tổng quát .............................................................................. 32 2.3.2 Thuật toán FindAllOutsD cho các phần tử ngoại lai nằm trong bộ nhớ ngoài ............................................................................................................ 36 2.3.2.1 Tư tưởng thuật toán .......................................................................... 36 2.4 Xử lý thực nghiệm .................................................................................. 39 2.4.1 Thiết lập thực nghiệm .......................................................................... 39 2.4.2 Thay đổi cỡ của tập dữ liệu.................................................................. 40 2.4.3 Thay đổi giá trị của pct ........................................................................ 42 2.4.4 Thay đổi chiều dữ liệu và số lượng ô .................................................. 42 2.5. Kết luận chương ................................................................................... 43 CHƯƠNG 3 ................................................................................................ 44 CHƯƠNG TRÌNH THỰC NGHIỆM ....................................................... 44 3.1 Hiện trạng và đặt bài toán ....................................................................... 44 3.1.1 Chỉnh sửa dữ liệu................................................................................. 44 3.1.2 Chỉnh lỗi cú pháp ................................................................................ 45 3.1.3 Phát hiện ngoại lai ............................................................................... 46 3.2 Cài đặt thuật toán và chạy chương trình................................................. 46 v 3.2.1 Sử dụng các luật trong bảng điểm ........................................................ 46 3.2.1.1 Xử lí dữ liệu thủ công ...................................................................... 46 3.2.1.2 Cài đặt thuật toán .............................................................................. 47 3.2.1.3 Một số qui luật xác định ngoại lai .................................................... 48 3.2.1.4 Các xã thuộc huyện Văn Yên........................................................... 49 3.2.1.5 Những xã đặc biệt khó khăn ............................................................ 50 3.2.1.6 Các dân tộc thiểu số trong huyện Văn Yên ...................................... 51 3.2.2 Ứng dụng thuật toán FindAllOutsD tìm phần tử ngoại lai theo tỷ lệ khác biệt. ...................................................................................................... 51 3.3. Kết luận chương .................................................................................... 54 KẾT LUẬN ................................................................................................. 55 TÀI LIỆU THAM KHẢO.......................................................................... 56 PHỤ LỤC.................................................................................................... 57 vi DANH MỤC CÁC TỪ VIẾT TẮT CNTT Công nghệ thông tin KDD Khám phá tri thức SQL Ngôn ngữ hỏi SQL, Structured Query Language MySQL Hệ quản trị cơ sở dữ liệu MySQL ECG(Electrocardiograms) Điện tâm đồ Electroencephalograms Điện não đồ ID (Identification) Nhận biết FindAllOutsM Find All Outliers in memory FindAllOutsD Find All Outliers in Disk ADN – Aciddeoxyribonuclic Chuỗi phân tử Outlier Ngoại lai DB (Distance Based) Dựa theo khoảng cách ĐBKK Đặc biệt khó khăn THCS Trung học cơ sở vii DANH MỤC CÁC BẢNG, HÌNH VẼ Hình 1.1. Vai trò của tri thức....................................................................... 5 Hình 1.2. Phát hiện tri thức ......................................................................... 7 Hình 1.3. Phần tử ngoại lai trong tập điểm có tọa độ (x,y) trên mặt phẳng có giá trị tung độ y nhỏ hơn hẳn các phần tử khác của tập hợp. ... 9 Hình 1.4. Thí dụ phân tích dữ liệu ngoại lai ............................................. 11 Hình1.5: Minh họa- giá trị ngoại lai trong một bộ dữ Hình 1.6: Các thành phần chính liên quan đến kỹ thuật phát hiện ngoại lai ................................................................................................................. 14 Hình 1.7: Biểu đồ nhiệt độ tại các tháng khác nhau trong năm .............. 16 Hình 2.2 a .................................................................................................... 29 Hình 2.2b..................................................................................................... 29 Hình 2.2c ..................................................................................................... 30 Hình 2.2d..................................................................................................... 30 Hình 2.3 Thời gian chạy của CPU+I/O với các tập dữ liệu ba chiều nằm trong bộ nhớ ngoài. Với pct=0.9999. ......................................................... 40 Hình 2.4 ....................................................................................................... 42 Hình 3.1. Dữ liệu ban đầu, chưa điều chỉnh thủ công .............................. 45 Hình 3.2. Bảng điểm đã điều chỉnh, cho phù hợp với yêu cầu tin học hóa ..................................................................................................................... 47 Hình 3.3. Bản đồ Huyện Văn Yên – Tỉnh Yên Bái ................................... 49 Hình 3.4: Tệp Excel bảng điểm cơ sở dữ liệu đầu vào ............................. 52 Hình 3.5: Các danh mục ............................................................................ 52 Hình 3.6: Ta có thể thêm vào hoặc xóa tên các dân tộc............................ 53 Hình 3.7. Ta có thể sửa thêm vào hoặc xóa tên các trường THCS .......... 53 Hình 3.8. Ta có thể sửa, xóa hoặc thêm môn thi ....................................... 54 Hình 3.9. Kết quả tìm phần tử ngoại lai .................................................... 54 1 MỞ ĐẦU Trong vài thập niên gần đây, cùng với sự thay đổi và phát triển không ngừng của ngành công nghệ thông tin dẫn đến sự bùng nổ thông tin và dữ liệu. Luồng thông tin được chuyển tải mau lẹ rất nhanh chóng.Công nghệ khai phá dữ liệu và phát hiện tri thức đang là chủ đề được quan tâm trong công nghệ thông tin và được áp dụng rộng rãi trong nhiều lĩnh vực và đem lại những thành tựu to lớn. Xác định phần tử ngoại lai(outlier) trong tập hợp dữ liệu là một hướng mới được quan tâm, nghiên cứu và có nhiều ứng dụng thiết thực. Tuy nhiên với số lượng dữ liệu được tập trung và lưu trữ trong cơ sở dữ liệu ngày càng lớn thì việc tìm kiếm các phần tử ngoại lệ hoặc các phần tử ngoại lai trong quá trình sử dụng và khai thác thông tin ngày càng được chú trọng. Do tính hấp dẫn của khai phá dữ liệu, đặc biệt là các thuật toán phát hiện phần tử ngoại lai, tôi đã chọn đề tài “Thuật toán phát hiện phần tử ngoại lai và ứng dụng” là luận văn cao học của mình. Hiện nay lĩnh vực giáo dục đang phát triển mạnh mẽ, hệ thống trường lớp ngày càng được mở rộng, việc áp dụng công nghệ thông tin trong quản lý và giảng dạy, học tập ngày càng được chú trọng, trong đó có quản lý điểm thi trong kỳ thi học sinh giỏi các môn văn hóa do phòng giáo dục và đào tạo huyện Văn Yên, tỉnh Yên Bái tổ chức. Với mong muốn phát hiện tự động những sai sót trong bảng dữ liệu thi học sinh giỏi tại huyện Văn Yên, Yên Bái, từ đó sử dụng phần mềm phát hiện tự động các ngoại lai, rồi điều chỉnh theo ý kiến chuyên gia giáo dục. Xuất phát từ thực tế đó, luận văn này được trình bày nhằm mục đích: 1. Tìm hiểu các khái niệm về khai phá dữ liệu và phát hiện tri thức, một số khái niệm liên quan đến phần tử ngoại lai, phát hiện phần tử ngoại lai trong cơ sở dữ liệu và ứng dụng… 2 2. Khảo cứu một số thuật toán phát hiện phần tử ngoại lai theo tỷ lệ khác biệt trên dữ liệu lớn, nhiều chiều. 3. Kiểm tra thuật toán FindAllOutsD cho các phần tử ngoại lai nằm trong bộ nhớ ngoài trên dữ liệu thực tế. 3 CHƯƠNG 1. PHẦN TỬ NGOẠI LAI VÀ ỨNG DỤNG TRONG KHAI PHÁ DỮ LIỆU Nội dung của chương này giới thiệu quá trình phát hiện tri thức, khai phá dữ liệu, trình bày một số khái niệm liên quan đến phần tử ngoại lai và phát hiện phần tử ngoại lai trong cơ sở dữ liệu. Đồng thời, đi sâu tìm hiểu ứng dụng thực tế của phần tử ngoại lai trong các lĩnh vực của cuộc sống. 1.1 Khai phá dữ liệu và phát hiện tri thức 1.1.1 Một số khái niệm Người ta xác định rõ dữ liệu, thông tin, tri thức và vai trò của chúng trong xã hội tri thức. Nói chung, dữ liệu bao gồm những mệnh đề phản ánh thực tại. Một phân loại lớn của các mệnh đề quan trọng trong thực tiễn là các đo đạc hay quan sát về một đại lượng biến đổi. Các mệnh đề đó có thể bao gồm các số, từ hoặc hình ảnh. Tri thức hay kiến thức bao gồm những dữ kiện, thông tin, sự mô tả, hay kỹ năng có được nhờ trải nghiệm hay thông qua giáo dục. Trong tiếng Việt, cả "tri" lẫn "thức" đều có nghĩa là biết. Tri thức có thể chỉ sự hiểu biết về một đối tượng, về mặt lý thuyết hay thực hành. Nó có thể tiềm ẩn, chẳng hạn những kỹ năng hay năng lực thực hành, hay tường minh, như những hiểu biết lý thuyết về một đối tượng, nó có thể ít nhiều mang tính hình thức hay có tính hệ thống. Mặc dù có nhiều lý thuyết về tri thức, nhưng hiện không có một định nghĩa nào về tri thức được tất cả mọi người chấp nhận. Thành tựu tri thức liên quan đến những quá trình nhận thức phức tạp: tri giác, truyền đạt, liên hệ, và suy luận. Trong triết học, ngành nghiên cứu về tri thức được gọi là tri thức luận. 1.1.2 Khai phá dữ liệu Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập 4 kỷ 80, nó bao hàm một loạt kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các kho dữ liệu. 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 để tìm ra các mẫu tri thức trong tập dữ liệu. Trong thực tế có nhiều kỹ thuật khai phá dữ liệu khác nhau và được chia thành hai nhóm chính: kỹ thuật khai phá dữ liệu mô tả, kỹ thuật khai phá dữ liệu dự đoán. Một số kỹ thuật phổ biến thường được sử dụng để khai phá dữ liệu hiện nay là: phân cụm dữ liệu, khai phá luật kết hợp, hồi quy, phân lớp dữ liệu, giải thuật di truyền, mạng nơ ron… Có rất nhiều ứng dụng trong các lĩnh vực khác nhau sử dụng các kỹ thuật khai phá dữ liệu nhằm hỗ trợ cho mục đích sử dụng. Ví dụ: trong thương mại, một công ty hay một tổ chức sử dụng các kỹ thuật khai thác dữ liệu để tặng khuyến mãi cho các khách hàng dựa vào tần suất truy cập website, kiểu khách hàng, số lượng hàng đã mua ở các lần trước. Trong ngân hàng sử dụng các kỹ thuật khai thác dữ liệu để xác định rủi ro về thẻ tín dụng. Trong các công ty bảo hiểm thì xác định các lỗi và các trường hợp rủi ro cao có thể xảy ra. Các tổ chức chống tội phạm sử dụng các kỹ thuật khai thác dữ liệu để tìm kiếm, nhận dạng tội phạm. Các công cụ tìm kiếm trang web áp dụng các kỹ thuật thông minh để có thể tìm kiếm được những trang web theo yêu cầu của người sử dụng với độ chính xác cao. Các kỹ thuật khai thác dữ liệu còn được áp dụng trong các lĩnh vực khác như phân tích thị trường chứng khoán, dự báo tỷ lệ thay đổi ngoại tệ, mô hình hóa Protein, tìm kiếm các gene trong các chuỗi DNA, dự báo thời tiết, nhận dạng ảnh và văn bản… Do khai phá dữ liệu được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều kiểu dữ liệu khác nhau:  Cơ sở dữ liệu quan hệ 5  Kho dữ liệu  Cơ sở dữ liệu giao dịch  Dữ liệu không gian và thời gian  Dữ liệu chuỗi thời gian  Cơ sở dữ liệu đa phương tiện 1.1.3 Phát hiện tri thức Với sự tiến bộ của khoa học kỹ thuật và nhu cầu con người ngày càng tăng đã tạo nên một thời đại bùng nổ thông tin trong mọi lĩnh vực của đời sống. Với lượng thông tin “khổng lồ” đó thì cần có các kỹ thuật khai phá dữ liệu hiệu quả để lấy ra những thông tin hữu ích. Một số các ngôn ngữ truy vấn như SQL được sử dụng nhằm lấy ra những thông tin theo yêu cầu của người sử dụng, nhưng hầu hết các ngôn ngữ này chỉ lấy ra được dữ liệu theo những yêu cầu đơn giản. Các kiểu dữ liệu đa phương tiện được một số các hệ thống cơ sở dữ liệu hỗ trợ như: Dữ liệu âm thanh, hình ảnh…không thể đáp ứng được khi các yêu cầu của người sử dụng ngày càng cao và phức tạp. Hình 1.1. Vai trò của tri thức Do đó, với nhu cầu tìm kiếm tri thức trong cơ sở dữ liệu đã hình thành một lĩnh vực mới: Phát hiện tri thức trong cơ sở dữ liệu. Phát hiện tri thức là toàn bộ quá trình tìm kiếm tri thức từ dữ liệu, bao gồm các bước sau: 1. Chuẩn bị dữ liệu: Dữ liệu được tập trung vào trong các cơ sở dữ liệu, các 6 kho dữ liệu. Dữ liệu có thể là chưa sạch tức là có cả dữ liệu sai sót, không phù hợp, nhiễu, và các dữ liệu không đủ thông tin. Do đó, trong bước này dữ liệu được làm sạch để loại bỏ các dữ liệu không phù hợp, dữ liệu không liên quan. Công việc này có thể được tiến hành trước hoặc sau khi phát hiện dữ liệu bị nhiễm bẩn. Đồng thời, sau khi được làm sạch, dữ liệu được làm giàu để bổ sung những thông tin cần thiết. Sau đó dữ liệu được biến đổi theo các dạng phù hợp để thực hiện quá trình khai thác dữ liệu. 2. Khai thác dữ liệu: Khai thác dữ liệu là một bước quan trọng trong quá trình khám phá tri thức. Bước này sử dụng các kỹ thuật, các phương thức thông minh để xác định các mẫu dữ liệu theo yêu cầu. Khai thác dữ liệu được định nghĩa là quá trình khai thác, khám phá những thông tin hữu ích, chưa được biết trước, tiềm ẩn và không tầm thường từ những tập dữ liệu lớn. Khai thác dữ liệu có thể bao gồm:  Tìm kiếm các luật kết hợp: Sử dụng các luật đơn giản để biểu diễn tri thức. Tìm kiếm những mỗi quan hệ có ích của dữ liệu.  Dự báo: Xác định các hàm hồi quy.  Nhận dạng và phân lớp mẫu: tìm kiếm, xác định các mẫu theo yêu cầu, phân chia các mẫu thành các lớp nhằm phục vụ cho mục đích sử dụng.  Phát hiện phần tử ngoại lệ : Tìm kiếm và xác định các đối tượng dữ liệu lỗi, bất thường, và các phần tử ngoại lai. Môi trường khám phá tri thức nhằm mục đích hỗ trợ quá trình khai thác dữ liệu. Do đó, hai thuật ngữ “khai phá dữ liệu" và “phát hiện tri thức” thường được sử dụng để thay thế cho nhau. 3. Đánh giá: Bước đánh giá bao gồm đánh giá mẫu và biểu diễn tri thức. Đánh giá mẫu là tìm ra những mẫu quan tâm từ các mẫu đã có trong bước 7 khai phá dữ liệu. Có thể sử dụng các ngưỡng cần thiết để lọc ra các mẫu cần khai phá. Biểu diễn tri thức là quá trình cho phép người sử dụng tương tác với hệ thống bằng các nhiệm vụ hoặc các truy vấn tìm kiếm dữ liệu cụ thể. Cung cấp thông tin nhằm mục đích trợ giúp việc tìm kiếm và thực hiện khai thác dữ liệu chi tiết dựa trên dữ liệu đã được khai thác. Ngoài ra, biểu diễn tri thức cho phép người sử dụng trình duyệt các lược đồ cơ sở dữ liệu và kho dữ liệu hoặc các cấu trúc dữ liệu.[3] Cấu trúc của quá trình phát hiện tri thức trong cơ sở dữ liệu: Hình 1.2. Phát hiện tri thức 1.2. Một số khái niệm liên quan đến phần tử ngoại lai 1.2.1. Khái niệm về ngoại lai Từ điển kinh tế, triết học đã xác định khái niệm ngoại lai. Ảnh hưởng ngoại lai, trong kinh tế học, là ảnh hưởng gây ra bởi hoạt động của một chủ thể kinh tế này và tác động trực tiếp tới chủ thể kinh tế khác (nghĩa là không thông qua cơ chế thị trường). Nếu chủ thể kinh tế chịu tác động bị tổn thất, thì có ảnh hưởng ngoại lai tiêu cực. Còn nếu chủ thể kinh tế chịu tác động được lợi, thì có ảnh hưởng ngoại lai tích cực. Ô nhiễm môi trường do chất thải của một nhà máy đối với dân cư trong khu vực là ví dụ về ảnh hưởng ngoại lai tiêu cực. Sự dễ chịu do cảnh đẹp ở vườn nhà hàng xóm tới nhà mình là ví dụ về ảnh hưởng ngoại lai tích cực. Ảnh hưởng ngoại lai 8 tích cực thường gắn liền với nạn kẻ đi xe không trả tiền (ngồi không hưởng lợi). Giải pháp khắc phục ảnh hưởng ngoại lai tiêu cực, trong kinh tế học được gọi là các biện pháp nội bộ hóa ảnh hưởng ngoại lai. Phần tử ngoại lai có thể có nhiều nguyên nhân bất thường. Một bộ máy vật lý cho lấy số đo có thể đã phải chịu đựng một sự cố thoáng qua. Có thể có một lỗi trong truyền dữ liệu hoặc sao chép. Ngoại lai phát sinh do sự thay đổi trong hệ thống hành vi, hành vi gian lận, lỗi của con người, lỗi công cụ, hay chỉ đơn giản là thông qua độ lệch tự nhiên trong quần thể. Một mẫu có thể đã bị nhiễm các yếu tố từ bên ngoài dân số được kiểm tra. Ngoài ra, một ngoại lai có thể là kết quả của một lỗ hổng trong lý thuyết giả định, kêu gọi tiếp tục điều tra bởi các nhà nghiên cứu. Phần tử ngoại lai là quan sát xa nhất, có thể bao gồm tối đa hoặc tối thiểu mẫu, hoặc cả hai, tùy thuộc vào việc phần tử đó cao hay thấp. Tuy nhiên, tối đa và tối thiểu mẫu không phải lúc nào cũng là giá trị ngoại lai bởi vì có thể không có bất thường xa với quan sát khác. Giải thích của các số liệu thống kê từ các tập dữ liệu bao gồm các giá trị ngoại lai có thể gây hiểu nhầm. Ví dụ: Nếu một người tính toán nhiệt độ trung bình của 10 đối tượng trong một căn phòng, và chín trong số đó là từ 20oC đến 25oC, nhưng một đối tượng ở 175°C, trung bình của các dữ liệu sẽ được giữa 20oC và 25°C, nhưng nhiệt độ trung bình sẽ vào khoảng 35,5oC và 40°C. Trong trường hợp này, trung bình tốt hơn phản ánh nhiệt độ của một đối tượng lấy mẫu ngẫu nhiên hơn so với trung bình. Tuy nhiên giải thích nghĩa là "một mẫu điển hình", tương đương với mức trung bình, là không chính xác. Như minh họa trong trường hợp này, giá trị ngoại lai có thể chỉ ra các điểm dữ liệu mà thuộc về một dân số khác biệt so với phần còn lại của tập hợp mẫu. Ước lượng khả năng đối phó với các ngoại lệ được cho là mạnh mẽ.[9] 9 1.2.2. Khái niệm ngoại lai trong cơ sở dữ liệu Trong các tập dữ liệu thường tồn tại các đối tượng dữ liệu không tuân theo một hình thức hoặc một mô hình dữ liệu chung, các đối tượng dữ liệu mà giá trị dữ liệu được xem là nằm ngoài phạm vi hoặc không liên quan tới tập dữ liệu còn lại. Những đối tượng có đặc tính trên được gọi là các phần tử ngoại lai. Phần tử ngoại lai của một tập dữ liệu là các phần tử mà theo một cách nhìn nào đó có các đặc tính không giống với tập hợp đa số còn lại của tập dữ liệu. Chẳng hạn trong hình cho thấy một phần tử ngoại lai theo vị trí hình học Hình 1.3. Phần tử ngoại lai trong tập điểm có tọa độ (x,y) trên mặt phẳng có giá trị tung độ y nhỏ hơn hẳn các phần tử khác của tập hợp. Các phần tử ngoại lai có thể là ngoại lại gây ra bởi lỗi thực hiện hoặc là lỗi phép đo. Ví dụ việc hiển thị một người có tuổi 199 có thể là do việc thiết lập mặc định chương trình không giới hạn tuổi dữ liệu. Mặt khác, các phần tử ngoại lai có thể là kết quả của quá trình tự nhiên. Có nhiều thuật toán khai thác dữ liệu cố gắng làm cực tiểu hoá sự ảnh hưởng của các phần tử ngoại lai, loại bỏ chúng cùng một lúc. Tuy nhiên, điều đó có thể làm mất những thông tin tiềm ẩn quan trọng khi “nhiễu của người này lại là tín hiệu của người khác”. Nói khác đi, các phần tử ngoại lai có thể trở thành một lĩnh vực cụ thể như là trong công việc phát hiện lỗi nơi các phần tử ngoại lai đóng vai trò là lỗi. Do đó, việc phân tích và phát hiện phần 10 tử ngoại lai là một công việc khai thác dữ liệu thú vị được đề cập tới như là khai thác phần tử ngoại lai.[1] Có nhiều định nghĩa được đưa ra để định nghĩa phần tử ngoại lai như định nghĩa của Barnet và Levis “Một phần tử ngoại lai là một đối tượng xuất hiện không nhất quán với tập dữ liệu còn lại”.[4] Hawkins mô tả định nghĩa trực quan về phần tử ngoại lai có thể là “ Một đối tượng mà nó lệch hướng rất nhiều với đối tượng khác do đó dẫn đến sự nghi ngờ rằng chúng được tạo ra bởi một kỹ thuật khác”. Nói khác đi, các đối tượng không cùng một mô hình thực hiện với tập dữ liệu còn lại được xem là các phần tử ngoại lai.[7] Có nhiều cách định nghĩa và hiểu khác nhau về phần tử ngoại lai. Tuy nhiên chúng có điểm chung là: Một phần tử ngoại lai là những quan trắc mà có sự khác biệt đáng kể đối với những quan trắc còn lại. Có nhiều công trình nghiên cứu về phát hiện phần tử ngoại lai. Các phương pháp chính để phát hiện phần tử ngoại lai bao gồm: 1. Xác định phần tử ngoại lai theo khoảng cách (Distance – Based): Theo hướng tiếp cận này cần phải xác định một hàm đo khoảng cách(metric) giữa các phần tử trong tập dữ liệu. Các phần tử ngoại lai là những phần tử nằm khá xa với tập các phần tử còn lại. Điển hình cho hướng tiếp cận này là các tác giả Knorr and Ng.[5] 2. Xác định theo thống kê (Statistical – Based): Hướng nghiên cứu này dựa trên việc xác định các mô hình phân phối thống kê mà các phần tử phải tuân theo(phân phối chuẩn, phân phối X2…). Phần tử ngoại lai là những phần tử không tuân theo luật này. Điển hình cho hướng tiếp cận này là các tác giả Barnett and lewis[4] 11 3. Xác định theo độ khác biệt (Deviation – Based): Hướng nghiên cứu này dựa trên những đặc trưng cơ bản của các phần tử trong một tập các phần tử. Các phần tử có những đặc trưng khác biệt quá lớn so với các phần tử còn lại thì là các phần tử ngoại lai. Điển hình cho hướng tiếp cận này là các tác giả Arning, Agrawal, Raghaval.[1] Một phần tử ngoại lai có thể là một đối tượng dữ liệu trong các trường hợp sau: 1. Nằm trong một phân bố khác với phân bố của tập dữ liệu còn lại. 2. Là một đối tượng có giá trị hợp lệ nhưng không phải là đối tượng mong muốn. 3. Là đối tượng dữ liệu được đánh giá, hoặc sinh ra do sai sót, không chính xác. Hình 1.4. Thí dụ phân tích dữ liệu ngoại lai Đối với trường hợp các phần tử ngoại lai có thể là các đối tượng hợp lệ nhưng chúng có giá trị không mong muốn. Chúng không cần thiết phải loại bỏ khỏi tập dữ liệu nhưng các đối tượng này phải được xác định hay nhận dạng. Draper và Smith nhận xét rằng một phần tử ngoại lai có thể “cung cấp thông tin mà các đối tượng khác không thể bởi vì nó xuất hiện từ sự kết hợp bất bình thường của một số trường hợp có thể là thực sự cần thiết” [4]. Có 12 thể các phần tử ngoại lai thực sự liên quan tới một mô hình xác xuất cụ thể hoặc cũng có thể là nằm trong mô hình cần được làm mịn. Nếu một phần tử ngoại lai không phải là một đối tượng hợp lệ (có thể là do nó được đánh giá và đưa vào không đúng). Thì nó có thể phải được phát hiện, khắc phục và đánh giá trong miền chuyên gia. Do đó, phụ thuộc vào từng ngữ cảnh các phần tử ngoại lai có thể được loại bỏ từ tập dữ liệu để làm tăng tính thuần nhất của dữ liệu còn lại. Ví dụ, trong một cơ sở dữ liệu đáp ứng thời gian thực cho hệ thống giao dịch trực tuyến, các phần tử ngoại lai có thể là những giá trị cực đại trong các phiên giao dịch mà các kết nối mạng phục vụ. Các phiên giao tiếp được xem như là không thành công trong hệ thống trực tuyến. Đây là một trường hợp có ý nghĩa là loại bỏ giá trị ngoại lai để tránh sự vượt quá thời gian đáp ứng trung bình của các phiên giao dịch. Nói tóm lại, các phần tử ngoại lai là những đối tượng đủ khác với hầu hết các điểm khác. Tuy nhiên, không có một định nghĩa về phần tử ngoại lai nào được chấp nhận rộng rãi. Các phần tử ngoại lai thường được xem xét là các điểm không thoả mãn dưới mô hình của dữ liệu. Việc phần tử ngoại lai có bị loại bỏ hay không còn phụ thuộc vào từng chương trình ứng dụng và quyết định từ chuyên gia. 1.3. Phát hiện các phần tử ngoại lai trong dữ liệu Phát hiện phần tử ngoại lai là các mẫu trong dữ liệu mà không phù hợp với một định nghĩa khái niệm về hành vi bình thường . Hình 1.5 minh họa giá trị ngoại lai trong một bộ dữ liệu hai chiều đơn giản. Những dữ liệu có hai khu vực bình thường N1 và N2 , vì hầu hết các quan sát nằm ở hai vùng này. Điểm đó là đủ xa cách xa các khu vực ví dụ: chỉ o1 và o2, và điểm trong khu vực O3, là giá trị ngoại lai . x y N1 N2 o1 o2 O3 13 Hình1.5: Minh họa- giá trị ngoại lai trong một bộ dữ liệu 2 chiều đơn giản Những khó khăn trong việc phát hiện phần tử ngoại lai trong cơ sở dữ liệu:  Bao gồm việc xác định mọi hành vi bất bình thường có thể có trong khu vực cơ sở dữ liệu.  Chỉ ra được ranh giới không chính xác giữa bình thường và ngoại lai.  Mỗi một lĩnh vực thì khái niệm phần tử ngoại lai có thể khác nhau. Chính vì vậy lĩnh vực ứng dụng để áp dụng kỹ thuật tìm kiếm phát hiện phần tử ngoại lai là rất khó khăn. Do những thách thức trên, vấn đề phát hiện phần tử ngoại lai ở dạng chung nhất của nó, không phải là dễ dàng để giải quyết. Trong thực tế, hầu hết các phần tử ngoại lai hiện các kỹ thuật phát hiện giải quyết cụ thể xây dựng vấn đề được gây ra bởi các yếu tố khác nhau. Chẳng hạn như tính chất của dữ liệu, sẵn có của dữ liệu được dán nhãn, loại các giá trị ngoại lai được phát hiện… Thông thường những yếu tố này xác định bởi các miền ứng dụng, trong đó giá trị ngoại lai cần phải được phát hiện. Các nhà nghiên cứu áp dụng các khái niệm từ các môn học đa dạng như thống kê, học máy, khai thác dữ liệu, thông tin, lý thuyết quang phổ, và áp dụng chúng vào vấn đề cụ thể. Hình 1.6 cho thấy sự quan trọng nêu trên các thành phần liên quan đến