Cách tiếp cận tập thô để phát hiện tri thức trong cơ sở dữ liệu

- Nguyễn Ngọc Hiếu cách tiếp cận tập thô để phát hiện tri thức trong cơ sở dữ liệu luận văn thạc sĩ khoa học kỹ thuật Hà Nội - 2004 bộ giáo dục và đào tạo tr−ờng đại học bách khoa hà nội.
- Nguyễn Ngọc Hiếu cách tiếp cận tập thô để phát hiện tri thức trong cơ sở dữ liệu Chuyên ngành: Công nghệ thông tin luận văn thạc sĩ khoa học kỹ thuật ng−ời h−ớng dẫn khoa học: PGS.
- Tụi làm luận văn tốt nghiệp cao học với đề tài "Cỏch tiếp cận tập thụ để phỏt hiện tri thức trong cơ sở dữ liệu", do PGS.
- Hà nội, ngày 20 thỏng 11 năm 2004 Người cam đoan Nguyễn Ngọc Hiếu 2Mục lục Lời cam đoan Mục lục Danh mục cỏc hỡnh vẽ và cỏc bảng Mở đầu Chương 1 - Tổng quan về phỏt hiện tri thức trong cơ sở dữ liệu.
- Khỏi niệm về phỏt hiện tri thức.
- Tiến trỡnh phỏt hiện tri thức trong cơ sở dữ liệu.
- Cỏc nhiệm vụ chớnh của khai phỏ dữ liệu.
- Tập thụ.
- 19 Chương 2 - Tập thụ và cỏch tiếp cận tập thụ mở rộng .
- Cỏc khỏi niệm cơ bản của tập thụ.
- Cỏc hệ thụng tin.
- Cỏch tiếp cận tập thụ đối với hệ thụng tin đa trị.
- Cỏc hệ thụng tin đa trị.
- Cỏc luật quyết định.
- 38 Chương 3 - Rỳt gọn dữ liệu dựa vào cỏch tiếp cận tập thụ mở rộng.
- Cỏch tiếp cận lọc.
- Cỏch tiếp cận wrapper.
- Rỳt gọn cỏc giỏ trị thuộc tớnh trong hệ thụng tin đa trị để phỏt hiện luật quyết định theo cỏch tiếp cận lập luận boolean.
- Cỏch tiếp cận lập luận boolean để rỳt gọn dữ liệu.
- 54 Chương 4 - Phỏt hiện cỏc luật quyết định tối thiểu dựa vào cỏch tiếp cận tập thụ mở rộng.
- Phỏt hiện cỏc luật quyết định tối thiểu dựa vào ma trận phõn biệt.
- Sử dụng tập thụ kết hợp với giải thuật Apriori để phỏt hiện cỏc luật quyết định tối thiểu.
- Mụ hỡnh tập thụ cú độ chớnh xỏc thay đổi (VPRSM.
- Giải thuật phỏt hiện cỏc luật quyết định tối thiểu cú độ tin cậy α.
- 69 Kết luận Tài liệu tham khảo Danh mục cỏc hỡnh vẽ và cỏc bảng Hỡnh 1.1 - Tiến trỡnh KDD 9Bảng 2.1 - Hệ thụng tin T1 20Bảng 2.2 - Hệ thụng tin T2 25Bảng 2.3 - Hệ thụng tin đa trị về cỏc bệnh nhõn bị nghẽn mạch 27Bảng 3.1 - Hệ thụng tin đa trị T sau khi ỏp dụng ρ 45Bảng 3.2 - Hệ thụng tin đa trị T1 49Bảng 3.3 - Ma trận phõn biệt của hệ thụng tin đa trị T1 49Bảng 3.4 - Ma trận phõn biệt của hệ quyết định đa trị T2 51Bảng 3.5 - Ma trận phõn biệt của hệ quyết định đa trị T2 sau khi được rỳt gọn 51Bảng 4.1 - Hệ quyết định đa trị MDT ban đầu 58Bảng 4.2 - Hệ quyết định đa trị MDT sau khi ỏp dụng ρ 58Bảng 4.3 - Ma trận phõn biệt của hệ quyết định đa trị MDT 59 5 Mở đầu Với tốc độ tin học hoỏ rất nhanh trong vài thập kỷ qua, hầu hết cỏc tổ chức và cỏ nhõn đều thu thập và lưu trữ một khối lượng dữ liệu khổng lồ trong cỏc cơ sở dữ liệu của họ.
- Dữ liệu được thu thập trong cỏc cơ sở dữ liệu vỡ thế trở thành dữ liệu "bị chụn vựi.
- Cỏc quyết định thường được thực hiện dựa vào trực giỏc của người tạo quyết định mà khụng dựa vào dữ liệu giàu thụng tin cú sẵn trong cơ sở dữ liệu.
- Tỡnh huống lỳc này được mụ tả như "Giàu dữ liệu nhưng nghốo thụng tin" [13].
- Cỏc cụng cụ phỏt hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) ra đời thực hiện việc phõn tớch dữ liệu để phỏt hiện cỏc tri thức cú ớch như cỏc dạng hay cỏc mụ hỡnh.
- Lý thuyết tập thụ được Pawlak đề xuất vào đầu những năm 1980 được xem như một cỏch tiếp cận mới để phỏt hiện tri thức và nú "tạo thành một cơ sở vững chắc cho cỏc ứng dụng khai phỏ dữ liệu" [9].
- Chỳng ta đó chứng kiến sự phỏt triển rất nhanh trong việc nghiờn cứu lý thuyết tập thụ và cỏc ứng dụng của chỳng trờn thế giới.
- Cho đến nay, đó cú hàng ngàn bài bỏo được cụng bố về tập thụ và cỏc ứng dụng của chỳng.
- Lý thuyết tập thụ đó được ỏp dụng thành cụng trong nhiều lĩnh vực như y học, dược học, ngõn hàng, tài chớnh, phõn tớch thị trường.
- Tiếp cận tập thụ cũng đúng vai trũ quan trọng đối với nhiều ứng dụng kỹ thuật như mỏy chẩn đoỏn, khoa học vật liệu.
- Cỏc ứng dụng phi thường của phương phỏp này đối với việc phỏt hiện tri thức đó chứng minh tớnh chất lợi ớch của nú.
- Lý thuyết tập thụ đưa ra cỏc cụng cụ toỏn học để phỏt hiện cỏc dạng ẩn trong dữ liệu: nhận biết một phần hoặc toàn bộ sự phụ thuộc (vớ dụ, cỏc quan hệ nguyờn nhõn-kết quả) trong cỏc cơ sở dữ liệu, loại ra cỏc dữ liệu thừa, đưa ra cỏch tiếp cận đối với vấn đề dữ liệu khụng đầy đủ (dữ liệu khụng cú giỏ trị, thiếu dữ liệu, dữ liệu động.
- Dữ liệu khụng đầy đủ ở đõy cú nhiều dạng, trong đú cú nhiều trường hợp dữ liệu lưu trữ là khụng chắc chắn được thể hiện qua cỏc hệ thụng tin với cỏc thuộc tớnh đa trị.
- Cỏch tiếp cận lý thuyết tập thụ của Pawlak khụng xem xột trường hợp này, do đú làm hạn chế cỏc ứng dụng của nú trong xử lý dữ liệu.
- Luận văn này đưa ra một cỏch tiếp cận tập thụ để xử lý cỏc hệ thụng tin đa trị.
- Dựa trờn mụ hỡnh được xõy dựng theo cỏch tiếp cận này, luận văn phỏt triển một số phương phỏp về rỳt gọn dữ liệu đó cú trong cỏch tiếp cận tập thụ truyền thống và đề xuất một số giải thuật để phỏt hiện cỏc luật từ cỏc hệ thụng tin đa trị.
- Chương 1, Tổng quan về phỏt hiện tri thức trong cơ sở dữ liệu.
- Chương này trỡnh bày cỏc khỏi niệm cơ bản của lĩnh vực nghiờn cứu KDD, quy trỡnh KDD, cỏc nhiệm vụ chủ yếu của khai phỏ dữ liệu (Data Mining - DM), cỏc phương phỏp DM, cỏc ứng dụng của KDD và cỏc thỏch thức của lĩnh vực nghiờn cứu này.
- 7 Chương 2, Tập thụ và cỏch tiếp cận tập thụ mở rộng.
- Chương này trỡnh bày cỏc khỏi niệm cơ bản lý thuyết tập thụ, đề xuất một cỏch tiếp cận tập thụ để xử lý cỏc hệ thụng tin với cỏc thuộc tớnh đa trị .
- Chương 3, Rỳt gọn dữ liệu dựa vào cỏch tiếp cận tập thụ mở rộng.
- Chương này trỡnh bày hai phương phỏp để rỳt gọn dữ liệu từ cỏc hệ thụng tin đa trị sử dụng cỏch tiếp cận tập thụ mở rộng.
- Chương 4, Phỏt hiện cỏc luật quyết định tối thiểu dựa vào cỏch tiếp cận tập thụ mở rộng.
- Chương này đề xuất hai giải thuật để phỏt hiện cỏc luật quyết định tối thiểu cho cỏc hệ thụng tin đa trị.
- 8Chương 1 Tổng quan về phỏt hiện tri thức trong cơ sở dữ liệu KDD là một lĩnh vực nghiờn cứu tớch cực, cú nhiều lợi ớch trong cỏc ứng dụng khoa học và thương mại.
- Cỏc tổ chức, chớnh phủ và cộng đồng những người nghiờn cứu khoa học ngày nay đang bị tràn ngập trong dũng chảy dữ liệu được thu thập và lưu trữ hàng ngày từ cơ sở dữ liệu trực tuyến.
- Việc phõn tớch dữ liệu này và trớch rỳt cỏc dạng cú ớch trong một thời gian hợp lý là rất khú khăn nếu khụng cú sự trợ giỳp của mỏy tớnh và cỏc cụng cụ phõn tớch mạnh.
- KDD được xem là một trong cỏc lĩnh vực nghiờn cứu cú triển vọng nhất từ những năm 1990 bởi cỏc nhà nghiờn cứu về học mỏy và cơ sở dữ liệu.
- Khỏi niệm về phỏt hiện tri thức KDD là lĩnh vực nghiờn cứu và ứng dụng tập trung vào dữ liệu, thụng tin và tri thức.
- Núi chung, chỳng ta thường xem dữ liệu như là một chuỗi cỏc bit, cỏc số hay cỏc ký hiệu, cỏc đối tượng mà cú ý nghĩa khi được gửi đến cho một chương trỡnh theo một định dạng cho trước (nhưng vẫn chưa hiểu được).
- Chỳng ta sử dụng cỏc bit để đo thụng tin và xem nú như là dữ liệu đó được lược bỏ cỏc dư thừa và được rỳt gọn tới mức tối thiểu cần thiết để tạo nờn cỏc quyết định mà đặc tả được bản chất của dữ liệu (dữ liệu hiểu được).
- Chỳng ta cú thể xem tri thức như là thụng tin được kết hợp, bao gồm cỏc sự kiện và cỏc quan hệ của chỳng, là cỏi mà được hiểu, được phỏt hiện hay được biết như "hỡnh ảnh trớ tuệ" của chỳng ta.
- Núi cỏch khỏc, tri thức cú thể được xem như dữ liệu ở mức cao của sự trừu tượng hoỏ và tổng quỏt hoỏ.
- 9KDD là lĩnh vực nghiờn cứu cú liờn quan đến nhiều lĩnh vực học thuật khỏc, đú là sự kết hợp của cơ sở dữ liệu, thống kờ, học mỏy và cỏc lĩnh vực liờn quan để trớch rỳt ra cỏc thụng tin và tri thức quý giỏ từ cỏc khối lượng dữ liệu rất lớn.
- KDD là tiến trỡnh xỏc định tớnh giỏ trị, mới lạ, tớnh ớch lợi tiềm ẩn và cuối cựng là cỏc mụ hỡnh/cỏc dạng cú thể hiểu được trong dữ liệu.
- DM là một bước trong tiến trỡnh KDD bao gồm cỏc giải thuật DM cụ thể mà dưới một vài giới hạn về khả năng tớnh toỏn cú thể chấp nhận, tỡm ra được cỏc dạng hay cỏc mụ hỡnh trong dữ liệu.
- Núi cỏch khỏc, KDD là tiến trỡnh để tỡm ra cỏc dạng và cỏc mụ hỡnh quan tõm tồn tại trong cỏc cơ sở dữ liệu nhưng ẩn giữa cỏc khối dữ liệu lớn.
- Tiến trỡnh phỏt hiện tri thức trong cơ sở dữ liệu Tiến trỡnh KDD bao gồm nhiều bước được chỉ ra trong hỡnh 1.1.
- Sử dụng tri thức được phỏt hiện Giải thớch và đỏnh giỏ kết quảKhai phỏ DLThu thập và tiền xử lý dữ liệu Nhận biết và xỏc địnhvấn đề Hỡnh 1.1 - Tiến trỡnh KDD Bước thứ nhất là hiểu miền ứng dụng và xỏc định, phỏt biểu vấn đề.
- Bước này rừ ràng là điều kiện tiờn quyết cho việc trớch rỳt cỏc tri thức cú ớch và lựa chọn cỏc phương phỏp DM thớch hợp ở bước thứ ba theo mục đớch ứng dụng và bản chất dữ liệu.
- Bước thứ ba là DM để trớch rỳt ra cỏc dạng và cỏc mụ hỡnh ẩn trong dữ liệu.
- Một mụ hỡnh cú thể được xem như "một sự mụ tả toàn bộ một cấu trỳc để tổng kết cỏc thành phần cơ bản của dữ liệu một cỏch cú hệ thống hay mụ tả dữ liệu cú thể được xuẩt hiện như thế nào".
- Bước thứ tư là giải thớch tri thức được phỏt hiện, nhất là giải thớch cỏc điều kiện được chấp nhận của sự mụ tả và dự bỏo – hai mục đớch chớnh của cỏc hệ thống phỏt hiện tri thức trong thực tế.
- Cỏc kinh nghiệm cho thấy rằng cỏc mụ hỡnh hay cỏc dạng được phỏt hiện từ dữ liệu ngay từ đầu khụng phải luụn đỳng, do đú tiến trỡnh KDD lặp đi lặp lại một cỏch tất yếu để đỏnh giỏ tri thức được phỏt hiện.
- Một cỏch thức chuẩn để đỏnh giỏ cỏc luật được đưa ra là chia dữ liệu thành hai tập, huấn luyện trờn tập đầu tiờn và kiểm thử trờn tập thứ hai.
- Bước cuối cựng là đưa tri thức được phỏt hiện sử dụng trong thực tế.
- Trong một số trường hợp, một ai đú cú thể sử dụng tri thức được phỏt hiện mà khụng cần nhỳng trong một hệ thống mỏy tớnh.
- Ngược lại, người dựng cú thể cho rằng tri thức được phỏt hiện cú thể đưa vào trong cỏc mỏy tớnh và được khai thỏc bởi một số chương trỡnh.
- Cỏc nhiệm vụ chớnh của khai phỏ dữ liệu Trong thực tế, DM cú hai mục đớch chớnh là dự bỏo và mụ tả.
- Mục đớch thứ nhất đũi hỏi phải sử dụng một số biến hoặc trường trong cơ sở dữ liệu để dự bỏo cỏc giỏ trị chưa biết hoặc sẽ cú của cỏc biến quan tõm khỏc.
- Mục đớch thứ hai tập trung vào việc tỡm cỏc dạng mụ tả dữ liệu cú thể hiểu được.
- Mối quan hệ của hai mục đớch này đối với cỏc ứng dụng khai phỏ dữ liệu cú thể thay đổi một cỏch đỏng kể.
- Mụ tả lớp cung cấp một sự tổng kết ngắn gọn và sỳc tớch của một sự thu thập dữ liệu.
- Sự tổng kết của một sự thu thập dữ liệu được gọi là đặc tả lớp.
- ngược lại, sự so sỏnh giữa hai hoặc nhiều hơn cỏc thu thập dữ liệu được gọi là so sỏnh hoặc phõn biệt lớp.
- Mụ tả lớp khụng chỉ bao gồm cỏc tớnh chất tổng kết của nú, như count, sum và average, mà cũn cả cỏc tớnh chất về sự phõn tỏn dữ liệu như variance, outliers, quartiles .v.v.
- Sự kết hợp là việc phỏt hiện cỏc mối quan hệ kết hợp hay cỏc quan hệ chung giữa một tập cỏc item.
- Chỳng thường được biểu diễn ở dạng luật chỉ ra cỏc điều kiện giỏ trị-thuộc tớnh xuất hiện thường xuyờn cựng với nhau trong một tập dữ liệu đó cho.
- Một luật kết hợp ở dạng X⇒Y được hiểu như "cỏc bộ dữ liệu mà thoả món X thỡ cú khả năng thoả món Y".
- Cỏc phõn tớch kết hợp được sử dụng một cỏch rộng rói trong cỏc cơ sở dữ liệu giao dịch đối với xu hướng tiếp thị, cỏc sản phẩm cú quan hệ với nhau, thiết kế catalog và cỏc quy trỡnh tạo quyết định thương mại khỏc.
- Việc nghiờn cứu đỏng kế được thực thi gần đõy dựa trờn cỏc phõn tớch kết hợp với cỏc giải thuật hiệu quả đó được đề xuất, bao gồm tỡm kiếm apriori, khai phỏ đa cấp, cỏc kết hợp đa chiều, khai phỏ cỏc kết hợp đối với dữ liệu số, categorical, dữ liệu khoảng, meta-pattern hay khai phỏ cỏc tương quan.
- Sự phõn lớp phõn tớch một tập dữ liệu huấn luyện (vớ dụ, một tập cỏc đối tượng mà nhón lớp được biết) và xõy dựng một mụ hỡnh cho mỗi lớp dựa vào cỏc đặc trưng trong dữ liệu.
- Một cõy quyết định hoặc một tập cỏc luật phõn lớp được tạo bởi một quy trỡnh phõn lớp như thế cú thể sau đú được dựng cho một sự hiểu biết tốt hơn của mỗi lớp trong cơ sở dữ liệu và cho sự phõn lớp của dữ liệu trong tương lai.
- Cú nhiều phương phỏp phõn lớp được phỏt triển trong cỏc lĩnh vực học mỏy, thống kờ, cơ sở dữ liệu, mạng nơron, tập thụ.
- Chức năng khai phỏ này dự bỏo cỏc giỏ trị cú thể của một số dữ liệu bị thiếu hoặc sự phõn bố giỏ trị của cỏc thuộc tớnh nào đú trong một tập đối tượng.
- Nú bao gồm việc tỡm tập thuộc tớnh liờn quan với thuộc tớnh quan tõm (vớ dụ, một số phõn tớch thống kờ) và dự bỏo phõn bố giỏ trị dựa trờn tập dữ liệu tương tự với cỏc đối tượng đó chọn.
- Cỏc phõn tớch phõn cụm phõn vựng dữ liệu thành cỏc cụm.
- Nghiờn cứu DM tập trung vào tớnh chất lượng và cỏc phương phỏp phõn cụm scalable (khả năng sử dụng cựng một giải thuật cho một số lượng lớn cỏc đầu vào) đối với cơ sở dữ liệu lớn và nhiều chiều.
- Cỏc phõn tớch theo thời gian là để phõn tớch một tập dữ liệu theo thời gian để phỏt hiện cỏc quy tắc nào đú và cỏc đặc trưng quan tõm, bao gồm tỡm kiếm cỏc chuỗi hay cỏc chuỗi con tương tự, và khai phỏ cỏc dạng, cỏc chu kỳ, cỏc xu hướng và độ lệch tuần tự.
- Việc nhận biết cỏc nhiệm vụ DM mới để cú được cỏch sử dụng dữ liệu tốt hơn là vấn đề nghiờn cứu thỳ vị.
- í tưởng của tập thụ dựa vào cỏc quan hệ tương đương, cho phộp phõn chia một tập dữ liệu thành cỏc lớp tương đương và bao gồm cỏc tập được định nghĩa như một cặp của cỏc tập, được gọi là cỏc xấp xỉ trờn và xấp xỉ dưới.
- Do đú tập thụ là một xấp xỉ của một tập.
- Lý thuyết tập thụ đối với thụng tin cú thể được mụ tả như một bảng.
- Tập thụ đó được ứng dụng thành cụng trong việc rỳt gọn thuộc tớnh và thiết kế cỏc hệ chuyờn gia.
- Việc sử dụng lý thuyết tập mờ trong khai phỏ dữ liệu cú thể được hiểu rừ bằng vớ dụ sau đõy.
- Cỏc tội phạm chưa tỡm ra cú thể được phỏt hiện bởi việc kết hợp cỏc kẻ phạm tội với cỏc tội ỏc đó biết cựng với việc điều tra cỏc phạm nhõn này một cỏch kỹ lưỡng hơn

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt