Đăng ký Đăng nhập
Trang chủ Khoa học xã hội Địa lý Khai phá luật kết hợp trong cơ sở dữ liệu đa phương tiện...

Tài liệu Khai phá luật kết hợp trong cơ sở dữ liệu đa phương tiện

.PDF
22
454
93

Mô tả:

Ketnooi.com vi su nghiep giao duc Khai phá Luật kết hợp trong cơ sở dữ liệu đa phương tiện Nguyễn Thị Biên Trường Đại học Công nghệ Luận văn ThS. ngành: Công nghệ phần mềm; Mã số: 60 48 10 Người hướng dẫn: PGS.TS. Đặng Văn Đức Năm bảo vệ: 2012 Abstract. Tổng quan về phát hiện tri thức, quá trình phát hiện tri thức từ cơ sở dữ liệu và khai phá dữ liệu. Nghiên cứu cơ sở dữ liệu đa phương tiện cũng như hệ quản trị cơ sở dữ liệu đa phương tiện. Tìm hiểu về luật kết hợp trong khai phá dữ liệu qua định nghĩa, bài toán, hướng tiếp cận và một số thuật toán phát hiện luận kết hợp. Trình bày khai phá luật kết hợp trong cơ sở dữ liệu hình ảnh: dữ liệu hình ảnh; trích chọn đặc trưng trong khai phá ảnh; khai phá luật kết hợp dựa trên nội dung ảnh bằng thuật toán Apriori. Keywords. Công nghệ phần mềm; Cơ sở dữ liệu đa phương tiện; Khai phá dữ liệu Content MỞ ĐẦU Trong điều kiện và yêu cầu của thương trường, đòi hỏi phải có những phương pháp nhanh, phù hợp, tự động, chính xác và có hiệu quả để lấy được thông tin có giá trị. Các tri thức chiết xuất được từ cơ sở dữ liệu sẽ là một nguồn tài liệu hỗ trợ cho lãnh đạo trong việc lên kế hoạch hoạt động hoặc trong việc ra quyết định sản xuất kinh doanh. Vì vậy, tính ứng dụng của khai thác luật kết hợp từ cơ sở dữ liệu là một vấn đề đang được quan tâm. Khai phá dữ liệu là giai đoạn quan trọng trong tiến trình khai thác tri thức từ cơ sở dữ liệu, các tri thức này hỗ trợ cho việc ra quyết định trong khoa học và kinh doanh. Công nghệ Multimedia liên quan tới việc mô tả sự kết hợp các dạng thông tin khác nhau (âm thanh, hình ảnh, văn bản, video) dưới dạng tín hiệu số. Một cơ sở dữ liệu Multimedia đòi hỏi phải có các phương thức đặc biệt nhằm mục đích tối ưu hóa việc lưu trữ, truy cập và khai thác các dạng thông tin đặc biệt này. Luật kết hợp là phương tiện hữu ích để khám phá các mối liên kết trong dữ liệu. Khai phá luật kết hợp trong cơ sở dữ liệu Multimedia cho phép tiết kiệm chi phí và làm tăng hiệu suất làm việc. 1.1. CHƢƠNG 1- TỔNG QUAN VỀ PHÁT HIỆN TRI THỨC VÀ KHAI PHÁ DỮ LIỆU Phát hiện tri thức và khai phá dữ liệu Việc thu thập và lưu trữ các kho chứa dữ liệu khổng lồ dẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tự động chuyển đổi lượng dữ liệu khổng lồ thành các tri thức có ích. Do vậy, khai phá dữ liệu (KPDL) nhằm phát hiện các tri thức mới giúp ích cho hoạt động của con người đã trở thành một lĩnh vực quan trọng của ngành Công nghệ thông tin. 1.2. Quá trình phát hiện tri thức từ cơ sở dữ liệu Thông tin là một khái niệm trừu tượng, được thể hiện dưới nhiều dạng thức khác nhau. Thông tin có thể được phát sinh, lưu trữ, biến đổi trong những vật mang tin. Dữ liệu là sự biểu diễn thông tin và được thể hiện bằng các tín hiệu vật lý. Dữ liệu là một dãy các bit các số, sử dụng các bit để đo lường các 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. Có thể xem tri thức như là các thông tin 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 hiểu ra, có thể được phát hiện, hoặc có thể được học. Mục đích của phát hiện tri thức và KPDL là tìm ra các mẫu và các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi hàng “núi” dữ liệu. Quá trình phát hiện tri thức được mô tả tóm tắt trên Hình 1.1: Hình 1.1: Quy trình phát hiện tri thức từ cơ sở dữ liệu  Làm sạch dữ liệu: Loại bỏ dữ liệu nhiễu hoặc dữ liệu không thích hợp.  Tích hợp dữ liệu: Tích hợp dữ liệu từ các nguồn khác nhau.  Chọn dữ liệu: Chọn những dữ liệu liên quan trực tiếp đến nhiệm vụ.  Chuyển đổi dữ liệu: Chuyển DL về những dạng phù hợp cho việc khai phá.  Khai phá dữ liệu.  Đánh giá mẫu: Đánh giá mẫu hoặc tri thức đã thu được.  Trình diễn dữ liệu: Biểu diễn những tri thức khai phá được cho người sử dụng. 1.2.1. Xác định vấn đề Trong thực tế, các cơ sở dữ liệu được chuyên môn hóa và phân chia theo các lĩnh vực khác nhau như sản phẩm, kinh doanh, tài chính, … Vì vậy mà việc xác định lĩnh vực và định nghĩa bài toán giúp định hướng cho giai đoạn tiếp theo thu thập và tiền xử lý dữ liệu. 1.2.2. Thu thập và tiền xử lý dữ liệu Các cơ sở dữ liệu thu được thường chứa rất nhiều thuộc tính nhưng lại không đầy đủ, không thuần nhất, có nhiều lỗi và các giá trị đặc biệt. Vì vậy, giai đoạn thu thập và tiền xử lý dữ liệu trở nên rất quan trọng trong quá trình phát hiện tri thức từ cơ sở dữ liệu. Người ta chia giai đoạn thu thập và tiền xử lý dữ liệu thành các công đoạn như sau: a. Chọn lọc dữ liệu b. Làm sạch dữ liệu c. Làm giàu dữ liệu d. Mã hóa 1.2.3. Khai thác dữ liệu Giai đoạn khai thác dữ liệu được bắt đầu sau khi dữ liệu đã được thu thập và tiến hành xử lý. Trong giai đoạn này, công việc chủ yếu là xác định được bài toán khai thác dữ liệu, tiến hành lựa chọn phương pháp khai thác phù hợp với dữ liệu có được và tách ra các tri thức cần thiết. 1.2.4. Minh họa và đánh giá Các tri thức phát hiện từ cơ sở dữ liệu cần được tổng hợp dưới dạng các báo cáo phục vụ cho các mục đích hỗ trợ quyết định khác nhau. 1.2.5. Đưa kết quả vào thực tế Các kết quả của quá trình phát hiện tri thức có thể được đưa vào ứng dụng trong những lĩnh vực khác nhau. Do các kết quả có thể là các dự báo hoặc các mô tả nên chúng có thể được đưa vào các hệ thống hỗ trợ ra quyết định nhằm tự động hóa quá trình này. 1.3. Khai phá dữ liệu 1.3.1. Khái niệm về khai phá dữ liệu KPDL (data mining) là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có. KPDL là một bước trong quá trình khám phá tri thức bao gồm các thuật toán KPDL chuyên dùng dưới một số quy định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu và các mô hình trong dữ liệu. 1.3.2. Nhiệm vụ của khai phá dữ liệu Những nhiệm vụ cơ bản nhất của KPDL là:  Phân cụm, phân loại, phân nhóm, phân lớp.  Khai phá luật kết hợp.  Lập mô hình dự báo.  Phân tích đối tượng ngoài cuộc.  Phân tích sự tiến hóa. 1.3.3. Một số ứng dụng khai phá dữ liệu  Thương mại: Phân tích dữ liệu bán hàng và thi trường, phân tích đầu tư, quyết định cho vay, phát hiện gian lận.  Thông tin sản xuất: Điều khiển và lập kế hoạch, hệ thống quản lý, phân tích kết quả thử nghiệm.  Thông tin khoa học: dự báo thời tiết, CSDL sinh học: Ngân hàng gen, khoa học địa lý: dự báo động đất.  Trong y tế, marketing, ngân hàng, viễn thông, du lịch, internet. 1.3.4. Các kỹ thuật khai phá dữ liệu 1.3.4.1 Khai phá dữ liệu dự đoán Nhiệm vụ của KPDL dự đoán là đưa ra các dự đoán dựa vào các suy diễn trên cơ sở dữ liệu hiện thời. Bao gồm các kỹ thuật: Phân loại (Classification); Hồi qui (Regression … ). a) Phân loại Mục tiêu của phương pháp phân loại dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân loại dữ liệu thường gồm hai bước : xây dựng mô hình và sử dụng mô hình để phân loại dữ liệu.  Bước 1 : Xây dựng mô hình dựa trên việc phân tích các mẫu dữ liệu cho trước.  Bước 2 : Sử dụng mô hình để phân loại dữ liệu. Hay nói các khác, phân loại là học một hàm ánh xạ một mục dữ liệu vào trong số các lớp cho trước. b) Hồi quy Phương pháp hồi quy khác với phương pháp phân loại dữ liệu ở chỗ, hồi qui dùng để dự đoán về các giá trị liên tục còn phân loại dữ liệu chỉ dùng để dự đoán về các giá trị rời rạc. Hồi quy là một hàm học ánh xạ mục dữ liệu thành một biến dự đoán có giá trị thực. 1.3.4.2. Khai phá dữ liệu mô tả Kỹ thuật này 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ó. Bao gồm các kỹ thuật: Phân cụm; Khai phá luật kết hợp... a) Phân cụm Mục tiêu chính của phương pháp phân cụ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 cụm sao cho các đối tượng thuộc cùng một một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Hình 1.4. cho thấy sự phân cụm tập dữ liệu cho vay vào trong 3 cụm : Lưu ý rằng các cụm chồng lên nhau cho phép các điểm dữ liệu thuộc về nhiều hơn một cụm. Hình 1.4 : Phân cụm tập dữ liệu cho vay thành 3 cụm b) Khai phá luật kết hợp 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 cơ sở dữ liệu. Mẫu đầu ra của giải thuật KPDL là luật kết hợp tìm được. 1.3.5. Kiến trúc của hệ thống khai phá dữ liệu Kiến trúc điển hình của một hệ thống KPDL được trình bày trong hình 1.5. Hình 1.5 : Kiến trúc điển hình của một hệ thống khai phá dữ liệu CHƢƠNG 2 – CƠ SỞ DỮ LIỆU ĐA PHƢƠNG TIỆN 2.1. Tổng quan cơ sở dữ liệu đa phương tiện Công nghệ multimedia liên quan tới việc mô tả sự kết hợp các dạng thức thông tin khác nhau (văn bản, dữ liệu, hình ảnh, âm thanh, video) dưới dạng tín hiệu số. Có thể nêu ra đây một số ứng dụng multimedia như [3]. E-learning, Hội thảo Video (Video Conferencing), Thư viện điện tử (Elibrary), Hiện tại ảo (Vitual Reality). 2.1.1. Một số khái niệm cơ bản 2.1.1.1. Media Media là các loại thông tin hay loại trình diễn thông tin như dữ liệu văn bản, ảnh, âm thanh và video[1]. Media được chia thành 2 loại:  Media tĩnh: Là loại media không có chiều thời gian, nội dung và ý nghĩa của chúng không phụ thuộc vào thời gian trình diễn. Media tĩnh bao gồm dữ liệu văn bản, hình ảnh tĩnh..  Media động: Có chiều thời gian, ý nghĩa và độ chính xác của chúng phụ thuộc vào tốc độ trình diễn. Media động bao gồm annimation, video, audio. Media động phụ thuộc chặt chẽ vào tốc độ trình diễn. 2.1.1.2. Đa phương tiện (Multimedia) Khái niệm multimedia đề cập đến tập hợp các kiểu media được tích hợp với nhau trong đó ít nhất có một kiểu media không phải là văn bản. 2.1.1.3. Cơ sở dữ liệu và hệ quản trị cơ sở dữ liệu CSDL : Được hiểu là một bộ sưu tập hoặc một kho dữ liệu hoặc các mục media. Hệ quản trị cơ sở dữ liệu (DBMS) : Là một hệ thống dùng để quản trị cơ sở dữ liệu. 2.1.1.4. Truy tìm thông tin tài liệu văn bản Một hệ thống IR có chức năng lưu trữ và quản lý số lượng lớn các tài liệu khoa học theo cách thích hợp để các truy vấn có thể truy tìm thông tin một cách nhanh chóng theo yêu cầu của người sử dụng. 2.1.1.5. Truy xuất và truy tìm Multimedia Các DBMS truy xuất các khoản mục dựa trên các số liệu có cấu trúc. Việc truy xuất dữ liệu dựa vào những đặc trưng của từng lợi dữ liệu: màu sắc, lời giải thích văn bản về media đó. Việc truy xuất nội dung là tương tự thay vì đối sánh chính xác giữa các truy vấn và các mục media. MIRS: Là một hệ thống cơ sở cung cấp việc truy xuất thông tin Multimedia khi sử dụng tổ hợp DBMS. Trong một MIRS các vấn đề về bảo mật hay phiên bản không được thực hiện đầy đủ. Một MIRS đầy đủ gọi là một Hệ quản trị cơ sở dữ liệu đa phương tiện (MMDBMS). 2.1.1.6. Trích chọn đặc trưng, Biểu diễn nội dung và Xây dựng chỉ mục Một trong những nhiệm vụ quan trọng của MIRS là trích chọn đặc trưng hay biểu diễn nội dung. Trích chọn đặc trưng là tiến trình tự động hay bán tự động. Chỉ mục là danh từ, đề cập đến cấu trúc dữ liệu hay đề cập đến tổ chức các đặc trưng đã trích chọn để tìm kiếm hiệu quả. 2.1.2. Vai trò của MIRS Cần phải có MIRS vì:  Ngày càng có nhiều dữ liệu đa phương tiện được thu thập và lưu trữ, để sử dụng tốt cần phải có hệ thống truy tìm và chỉ số hóa tốt.  Khác với loại dữ liệu chữ và số, dữ liệu đa phương tiện có tính chất và yêu cầu đặc biệt, một CSDL truyền thống không phù hợp trong việc quản lý cơ sở dữ liệu đa phương tiện.  Các kỹ thuật truy tìm thông tin có thể giúp truy tìm đa phương tiện nhưng chúng chưa có khả năng quản lý hiệu quả dữ liệu đa phương tiện. 2.1.2.1. Các DBMS và vai trò của chúng trong việc xử lý dữ liệu Multimedia Các DBMS ngày nay được phát triển khá tốt và được sử dụng rông rãi cho các dữ liệu có cấu trúc. DBMS quen thuộc là DBMS quan hệ (Ralational Database Management System - RDBMS). Trong RDBMS, thông tin dược tổ chức thành bảng hoặc các quan hệ. [1] Một dạng khác của các DBMS là hệ thống quản trị CSDL hướng đối tượng (OODBMS- Object Oriented Database Management System). Các OODBMS kết nối các khả năng của cơ sơ dữ liệu (như lưu trữ và tìm kiếm) và các đặc trưng hướng đối tượng (tóm lược, sự thừa kế, tính đồng nhất đối tượng). Khả năng cần có trong hệ thống như sau:  Công cụ để tự động hoặc bán tự động trích chọn đặc trưng chứa trong dữ liệu đa phương tiện.  Cấu trúc chỉ số hóa đa chiều để quản lý các véctơ đặc trưng đa phương tiện.  Thước đo tương tự để truy tìm dữ liệu đa phương tiện thay cho đối sánh chính xác.  Phân hệ lưu trữ được thiết kế để đáp ứng yêu cầu dữ liệu lớn, băng thông rộng và thời gian thực.  Giao diện người sử dụng được thiết kế sao cho truy vấn mềm dẻo với các loại media khác nhau và cho khả năng trình diễn đa phương tiện. 2.1.2.2. Hệ thống IR và vai trò của nó trong việc truy xuất multimedia Công nghệ IR rất quan trọng trong hệ thống quản lý thông tin multimedia vì hai lý do chính:  Một là chúng tồn tại một lượng lớn các văn bản trong nhiều dạng tổ chức, ví dụ như các thư viện.  Hai là, văn bản có thể được sử dụng để chú giải các truyền thông khác như âm thanh, hình ảnh, video. Thông thường thì công nghệ IR có thể dược sử dụng cho việc phu ̣c h ồi thông tin đa truyền thông. 2.1.3. Khái quát về MIRS Các thao tác MIRS được mô tả trên hình 2.1. Dữ liệu (các mục thông tin) trong CSDL được tiền xử lý để trích chọn đặc trưng và nội dung ngữ nghĩa. Sau đó chúng được chỉ số hóa trên cơ sở đặc trưng và ngữ nghĩa. Trong khi truy tìm thông tin, câu truy vấn của người sử dụng được xử lý và các đặc trưng của nó được trích chọn. Các đặc trưng này sau đó được so sánh với các đặc trưng hay chỉ mục dữ liệu trong CSDL. Các mục thông tin nào có đặc trưng gần giống nhất với các đặc trưng của câu truy vấn thì được tìm ra và trình diễn cho người sử dụng. Hình 2.1. Một mẫu truy xuất thông tin tổng quát Mô hình trên đây cho thấy rất nhiều nhiệm vụ phải thực hiện, thí dụ:  Các mục thông tin có thể là tổ hợp bất kỳ các loại media.  Trích chọn đặc trưng từ các mục media này như thế nào?  Các đặc trưng được lưu trữ và cấu trúc như thế nào để truy tìm hiệu quả?  Đo tính “tương tự” giữa hai mục media như thế nào?  Thiết kế giao diện như thế nào để nó có thể chấp nhận các câu truy vấn phức tạp, mờ và mềm dẻo?  So sánh hiệu năng giữa các hệ thống MIRS bằng cách nào?  Làm thế nào để đáp ứng yêu cầu thời gian khi truyền tải hay trình diễn dữ liệu Multimedia? 2.1.4 Khả năng mong đợi và các ứng dụng của MIRS MIRS cần phải mạnh và mềm dẻo. Khả năng của chúng được miêu tả bằng các kiểu truy vấn mà chúng có thể hỗ trợ. Các loại truy vấn mong đợi của MIRS như sau:  Truy vấn trên cơ sở meta-data  Truy vấn trên cơ sở mô tả  Truy vấn trên cơ sở mẫu (pattern) hay đặc trưng  Truy vấn theo thí dụ (by example)  Truy vấn ứng dụng cụ thể:  Cuối cùng, các MIRS sẽ tập trung vào chính thông tin thay thế các loại truyền thông và việc miêu tả chúng có thể được sắp xếp hoặc dịch ra từ loại truyền thông này đến loại truyền thông khác. 2.2. Dữ liệu đa phương tiện Dữ liệu multimedia được chia thành hai lớp là các dữ liệu liên tục và các dữ liệu không liên tục. Các dữ liệu liên tục bao gồm các dữ liệu âm thanh, video thay đổi theo thời gian. Các dữ liệu không liên tục là các dữ liệu không phục thuộc vào thời gian, các loại dữ liệu đặc trưng cho dạng này là các dữ liệu văn bản (có hoặc không có định dạng), hình ảnh tĩnh và các đối tượng đồ họa. Các kiểu dữ liệu thông thường của một CSDL multimedia bao gồm:  Dữ liệu văn bản (có hoặc không có định dạng).  Đồ họa: là các bản vẽ, minh họa được mã hóa như các tệp postscript.  Hình ảnh: là các hình ảnh được mã hóa sử dụng các dạng thức chuẩn như là  JPEG hoặc MPEG.  Các hoạt hình.  Âm thanh.  Video. 2.3. Hệ quản trị cơ sở dữ liệu đa phương tiện 2.3.1 Mục đích của MDBMS Các chức năng của MDBMS cơ bản tương tự như các chức năng của DBMS, tuy nhiên, bản chất của thông tin tạo ra các đòi hỏi mới:  Sự thống nhất  Độc lập dữ liệu  Điều khiển nhất quán  Sự tồn tại  Tính riêng  Kiểm soát sự toàn vẹn  Khả năng phục hồi  Hỗ trợ truy vấn  Kiểm soát phiên bản 2.3.2 Các yêu cầu của một MMDBMS Để có được một MMDBMS đáp ứng được các yêu cầu đã nêu ra ở trên, chúng ta cần phải có được một số các yêu cầu cụ thể cho nó, các yêu cầu ở đây bao gồm:  Đầy đủ các khả năng của một DBMS truyền thống.  Có khả năng lưu trữ lớn.  Có khả năng khai thác dữ liệu thuận tiện.  Có khả năng tích hợp, tổng hợp và thể hiện.  Hỗ trợ truy vấn multimedia.  Có giao diện multimedia và tương tác. Bên cạnh các yêu cầu trên, để cho hệ thống hoạt động có thể hoạt động tốt cần phải giải quyết các vấn đề sau:  Hệ thống CSDL đa phương tiện sẽ được xây dựng như thế nào để có thể bao gồm các lĩnh vực ứng dụng khác nhau.     Xây dựng phần hạt nhân cho việc phân rã , lưu trữ và quản lý thông tin ở mức độ nào? Các công nghệ, cấu trúc nền tảng được sắp xếp và sử dụng như thế nào? Các kiến thức về tổng hợp dữ liệu đối với CSDL đa phương tiện,. Xác định được hạ tầng thể hiện nào mà một hệ thống đa phương tiện phải có để đạt được các yêu cầu và cách thức thể hiện khác nhau. . Giả sử các kiểu media khác nhau có các yêu cầu cập nhật và sửa đổi thông tin khác nhau thì hệ thống sẽ cập nhật các thành phần này như thế nào. 1. Khả năng quản trị lưu trữ lớn 2. Hỗ trợ truy vấn và khai thác dữ liệu 3. Tích hợp các phương tiện, tổng hợp và thể hiện 4. Giao diện và tương tác.. 5. Hiệu suất CHƢƠNG 3 – LUẬT KẾT HỢP TRONG KHAI PHÁ DỮ LIỆU 3.1. Bài toán kinh điển dẫn đến việc khai phá luật kết hợp Bài toán giỏ mua hàng trong siêu thị. Giả định chúng ta có rất nhiều mặt hàng, ví dụ như “bánh mì”, “sữa”,…(coi là tính chất hoặc trường). Khách hàng khi đi siêu thị sẽ bỏ vào giỏ mua hàng của họ một số mặt hàng nào đó, và chúng ta muốn tìm hiểu các khách hàng thường mua các mặt hàng nào đồng thời, chúng ta không cần biết khách hàng cụ thể là ai. Nhà quản lý dùng những thông tin này để điều chỉnh việc nhập hàng về siêu thị, hay đơn giản là để bố trí sắp xếp các mặt hàng gần nhau, hoặc bán các mặt hàng đó theo một gói hàng, giúp cho khắc đỡ mất công tìm kiếm. Khai phá luật kết hợp được mô tả như sự tương quan của các sự kiện những sự kiện xuất hiện thường xuyên một các đồng thời. Nhiệm vụ chính của khai phá luật kết hợp là phát hiện ra các tập con cùng xuất hiện trong một khối lượng giao dịch lớn của một cơ sở dữ liệu cho trước. 3.2. Định nghĩa về luật kết hợp Định nghĩa: Cho I={I1, I2, .., Im} là tập hợp của m tính chất riêng biệt. Giả sử D là CSDL, với các bản ghi chứa một tập con T các tính chất (có thể coi như ), các bản ghi đều có chỉ số riêng. Một luật kết hợp là một mệnh đề kéo theo có dạng XY, trong đó X, Y  I, thỏa mãn điều kiện XY=. Các tập hợp X và Y được gọi là các tập hợp tính chất (itemset). Tập X gọi là nguyên nhân, tập Y gọi là hệ quả. Có 2 độ đo quan trọng đối với luật kết hợp: Độ hỗ trợ (support) và độ tin cậy (confidence), được định nghĩa như phần dưới đây. Định nghĩa: Độ hỗ trợ Định nghĩa 3.1: Độ hỗ trợ của một tập hợp X trong cơ sở dữ liệu D là tỷ số giữa các bản ghi T D có chứa tập X và tổng số bản ghi trong D (hay là phần trăm của các bản ghi trong D có chứa tập hợp X), ký hiệu là support(X) hay supp(X) (support sẽ tự sinh ra khi cài thuật toán). S0 = | {T  D : Y  X} | |D| (3.1) Ta có: 0 supp(X) 1 với mọi tập hợp X. Định nghĩa 3.2: Độ hỗ trợ của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi chứa tập hợp X Y, so với tổng số các bản ghi trong D - Ký hiệu supp(XY). Supp(XY) = | {T  D : T  X  Y } | |D| (3.2) Khi chúng ta nói rằng độ hỗ trợ của một luật là 50%, có nghĩa là có 50% tổng số bản ghi chứa X Y. Như vậy, độ hỗ trợ mang ý nghĩa thống kê của luật. Định nghĩa: Độ tin cậy Định nghĩa 3.3: Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi trong D chứa X Y với số bản ghi trong D có chứa tập hợp X. Ký hiệu độ tin cậy của một luật là conf(r). Ta có 0 conf(r) 1 Nhận xét: Độ hỗ trợ và độ tin cậy có xác suất sau: Supp(XY)=P(XY) Conf (XY) = P(Y/X)=supp(XY)/supp(X) (3.3) (3.4) Định nghĩa 3.4: Độ tin cậy của một luật kết hợp XY là tỷ lệ giữa số lượng các bản ghi của tập hợp chứa X  Y, so với tổng số các bản ghi chứa X. Chúng ta nhận thấy rằng tri thức đem lại bởi luật kết hợp dạng trên có sự khác biệt rất nhiều so với những thông tin thu được từ các câu lệnh truy vấn dữ liệu thông thường như SQL. Đó là những tri thức, những mối liên hệ chưa biết trước và mang tính dự báo đang tiềm ẩn trong dữ liệu. Những tri thức này không đơn giản là kết quả của phép nhóm, tính tổng hay sắp xếp mà là của một quá trình tính toán khá phức tạp. Định nghĩa: Tập hợp thƣờng xuyên Định nghĩa 3.5: Tập hợp X được gọi là tập hợp thường xuyên (Frenquent itemset) nếu có supp(X) minsup, với minsup là ngưỡng độ hỗ trợ cho trước. Kí hiệu các tập này là FI Tính chất 3.1: Giả sử A,B  I là hai tập hợp với AB thì supp(A) supp(B). Như vậy, những bản ghi nào chứa tập hợp B thì cũng chứa tập hợp A Tính chất 3.2: Giả sử A, B là hai tập hợp, A,B I, nếu B là tập hợp thường xuyên và AB thì A cũng là tập hợp thường xuyên. Thật vậy, nếu B là tập hợp thường xuyên thì supp(B) minsup, mọi tập hợp A là con của tập hợp B đều là tập hợp thường xuyên trong cơ sở dữ liệu D vì supp(A) supp(B) (Tính chất 3.1) Tính chất 2.3: Giả sử A, B là hai tập hợp, A  B và A là tập hợp không thường xuyên thì B cũng là tập hợp không thường xuyên Định nghĩa 2.6: Một tập mục X được gọi là đóng (closed) nếu không có tập cha nào của X có cùng độ hỗ trợ với nó, tức là không tồn tại một tập mục X’ nào mà X’X và t(X) = t(X’) (với t(X) và t(X’) tương ứng là tập các giao chứa tập mục X và X’). Ký hiệu tập phổ biến đóng là FCI. Định nghĩa 2.7: Nếu X là phổ biến và không tập cha nào của X là phổ biến, ta nói rằng X là một tập phổ biến lớn nhất (maximally frequent itemset). Ký hiệu tập tất cả các tập phổ biến lớn nhất là MFI. Dễ thấy MFI FCI FI. Khai phá luật kết hợp là công việc phát hiện ra (tìm ra, khám phá, phát hiện) các luật kết hợp thỏa mãn các ngưỡng độ hỗ trợ () và ngưỡng độ tin cậy () cho trước. Bài toán khai phá luật kết hợp được chia thành hai bài toán nhỏ, hay như người ta thường nói, việc giải bài toán trải qua hai pha:   Pha 1: Tìm tất cả các tập phổ biến (tìm FI) trong CSDL T. Pha 2: Sử dụng tập FI tìm được ở pha 1 để sinh ra các luật tin cậy (interesting rules). Ý tưởng chung là nếu gọi ABCD và AB là các tập mục phổ biến, thì chúng ta có thể xác định luật AB →CD với tỷ lệ độ tin cậy: conf = supp(ABCD) supp(AB) (3.5) Nếu conf minconf thì luật được giữ lại (và thỏa mãn độ hỗ trợ tối thiểu vì ABCD là phổ biến). Khi các mẫu phổ biến (frequent patterm) dài có từ 15 đến 20 items) thì tập FI, thậm chí cả tập FCI trở nên rất lớn và hầu hết các phương pháp truyền thống phải đếm quá nhiều tập mục mới có thể thực hiện được. Các thuật toán dựa trên thuật toán Apriori – đếm tất cả 2k tập con của mỗi k- itemsets mà chúng quét qua, và do đó không thích hợp với các itemsets dài được. Các phương pháp khác sử dụng “lookaheads” để giảm số lượng tập mục được đếm. Tuy nhiên, hầu hết các thuật toán này đều sử dụng tìm kiếm theo chiều rộng. Cách làm này hạn chế hiệu quả của lookaheads, vì các mẫu phổ biến dài hơn mà hữu ích vẫn chưa được tìm ra. Thuật toán 1 – Thuật toán cơ bản: Input: I, D, Output: Các luật kết hợp thỏa mãn ngưỡng độ hỗ trợ , ngưỡng độ tin cậy . Algorithm: 1) Tìm tất cả các tập hợp các tính chất có độ hỗ trợ không nhỏ hơn ngưỡng . 2) Từ các tập hợp mới tìm ra, tạo ra các luật kết hợp có độ tin cậy không nhỏ hơn . Agrawal đã chỉ ra việc duyệt các tập hợp các tính chất để tính ra ngưỡng độ hỗ trợ của chúng và đánh giá có vượt ngưỡng  cho trước hay không, tốn rất nhiều thời gian tính toán (độ phức tạp hàm mũ). Còn một khi đã xác định xong các tập hợp thỏa mãn điều kiện trên (gọi là các tập hợp xuất hiện thường xuyên) thì việc khai phá luật kết hợp đỡ tốn thời gian hơn. Agrawal đề nghị một thuật toán như sau: Thuật toán 2- Tìm luật kết hợp khi đã biết các tập hợp thƣờng xuyên: Input: I, D, S Output: Các luật kết hợp thỏa mãn ngưỡng độ hỗ trợ , ngưỡng độ tin cậy . Algorithm: 1) Lấy ra một tập xuất hiện –thường xuyên SS, và một tập con X  S. 2) Xét luật kết hợp có dạng X → (SX), đánh giá độ tin cậy của nó xem có nhỏ hơn  hay không. Thực chất, tập hợp S mà ta xét đóng vai trò của tập hợp giao S = XY, và do X (S – X) = , nên coi như Y= S – X. Các thuật toán xoay quanh khai phá luật kết hợp chủ yếu nêu ra các giải pháp để đẩy nhanh việc thực hiện mục 1 của Thuật toán 1. 3.4. Một số thuật toán phát hiện luật kết hợp 3.4.1. Thuật toán Apriori Thuật toán dựa trên một nhận xét khá đơn giản là bất kỳ tập hợp con nào của tập xuất hiện  thường xuyên cũng là tập xuất hiện –thường xuyên. Do đó, trong quá trình đi tìm các tập ứng cử viên, nó chỉ cần dùng đến các tập ứng cử viên vừa xuất hiện ở bước ngay trước đó, chứ không cần dùng đến tất cả các tập ứng cử viên (cho đến thời điểm đó). Nhờ vậy, bộ nhớ được giải phóng đáng kể.    Bước 1: cho trước ngưỡng độ hỗ trợ 0 1. Tìm tất cả các mặt hàng xuất hiện – thường xuyên. Bước 2: Ta tiến hành ghép đôi các phần tử của L1 (không cần để ý đến thứ tự), được tập C2, tạp gọi là tập các ứng cử viên có 2 phần tử. Sở dĩ chỉ gọi là “ứng cử viên”, vì chưa chắc chúng đã là – thường xuyên. Sau khi kiểm tra (dùng định nghĩa), ta lọc ra được các tập hợp – thường xuyên có 2 phần tử. Ký hiệu tập hợp này là L2. Bước 3: Với chủ ý đã nêu (về tính chất tăng dần của các tập hợp – thường xuyên), ta tiến hành tìm các ứng cử viên có 3 phần tử (lấy từ L1). Gọi nó là tập C3. Lưu ý là nếu {A, B, C} muốn là “ứng cử viên” thì các tập 2 phần tử {A, B},{B,C},{C, A } đều phải là – thường xuyên, tức là chúng đều là phần tử của tập L2. Ta đi “kiểm tra tư cách đại biểu” trong tập C3 và lọc ra được tập các tập hợp – thường xuyên có 3 phần tử. Tập hợp này được ký hiệu là L3.  Bước 4: Ta tiến hành tìm các ứng cử viên có n phần tử. Gọi tập của chúng là tập Cn và từ đây, lọc ra Ln là tập tập các tập hợp – thường xuyên có n phẩn tử. Cốt lõi của thuật toán Apriori là hàm apriori_gen() do Agrawal đề nghị năm 1994. Hàm này hoạt động theo 2 bước, bước 1- tập hợp Lk-1 tự kết nối (join) với chính nó để tạo ra tập ứng cử viên Ck. Sau đó hàm apriori_gen() loại bỏ các tập hợp có một hợp con (k-1) phần tử không nằm trong Lk-1 (vì chúng không thể là tập hợp xuất hiện – thường xuyên, theo như nhận xét ban đầu). Method: apriori_gen() [Agrwal1994] Input: Lớp các tập hợp xuất hiện – thường xuyên có (k-1) phần tử, ký hiệu là Lk-1 Output: Lớp các tập hợp xuất hiện – thường xuyên có k phần tử, ký hiệu là Luật kết hợp // Bước tự kết nối Ii = Items i Insert into Ck Select p.I1, p.I2,…, p.Ik-1, q.Ik-1 From Lk-1 is p, Lk-1 is q Where p.I1 = q.I1 and….and p.Ik-2 = q.Ik-2 and p.Ik-1 < q.Ik-1 //Bước tỉa bớt Forall itemsets c Ck do Forall (k-1)- subsets s of c do If (s is not of Lk-1) then Delete c from Ck Hàm sau đây có nhiệm vụ rà soát từng tính chất và đo đếm xem giá đỡ của nó bằng bao nhiêu. Nói cách khác, ở bước đầu tiên Agrawal dùng hàm count() để tìm ra các tập hợp xuất hiện – thường xuyên có 1 phần tử. Function count(C:a set of itemsets, D: database) begin for each transaction T D = Di do begin forall subsets xT do if x C then x.count++; end end Dưới đây là toàn bộ Thuật toán Apriori: Thuật toán 3- Apriori [Agrawal1994] Input: I, D,  Output: L Algorithm: //Apriori Algorithm prposed by Agrawal R., Srikant, R. [Agrawal1994] //procedure LargeItemsets 1) C1: = I; // Tập ứng cử viên có 1 phần tử 2) Sinh ra L1 bằng cách tính tần số xuất hiện của mặt hàng trong các giao dịch; 3) for (k=2; Lk-1 ; k++) do begin //Tạo ra các tập ứng cử viên // Các tập ứng cử viên có k phần tử được sinh ra từ các tập (k-1)- phần tử xuất hiện – thường xuyên. 4) Ck = apriori-gen( Lk-1 ); // Tính độ hỗ trợ cho Ck 5) Count (Ck, D) 6) Lk = {c Ck| c.count } 7) end 8) L:= k Lk Thuật toán Apriori cải tiến cũng giải quyết 2 tình huống “xấu”, đó là khi Ck hoặc Lk1 to quá, không chứa đủ trong bộ nhớ tính toán. Khi đó, cần tu chỉnh lại hàm apriori_gen() một chút. *Thuật toán Apriori nhị phân: Thuật toán Apriori nhị phân sử dụng các vector bit cho các thuộc tính, vector nhị phân n chiều ứng với n giao tác trong cơ sở dữ liệu. Có thể biểu diễn cơ sở dữ liệu bằng một ma trận nhị phân trong đó dòng thứ I tương ứng với giao tác (bản ghi) ti và cột thứ j tương ứng với mục (thuộc tính ) ij. 3.4.2. Thuật toán Apriori-TID Thuật toán Apriori-TID là phần mở rộng theo hướng tiếp cận cơ bản của thuật toán Apriori. Thay vì dựa vào cơ sở dữ liệu thô thuật toán Apriori- TID biểu diễn bên trong mỗi giao dịch bởi các ứng cử viên hiện hành. Như ta đã thấy, thuật toán Apriori đòi hỏi phải quét toàn bộ cơ sở dữ liệu để tính độ hỗ trợ cho các tập hợp ứng cử viên ở mỗi bước. Đây là một sự lãng phí lớn. Dựa trên tư tưởng ước đoán và đánh giá độ hỗ trợ, Agrawal đề xuất cải tiến Apriori theo hướng chỉ phải quét cơ sở dữ liệu lần đầu tiên, sau đó tính độ hỗ trợ cho các tập hợp 1 phần tử. Từ bước thứ hai trở đi, Thuật toán Apriori-TID nhờ lưu trữ song song cả ID của giao dịch và các ứng cử viên, có thể đánh giá, ước lượng độ hỗ trợ mà khỏi phải quét lại toàn bộ cơ sở dữ liệu. Nội dung thuật toán Apriori-TID Input: Tập các giao dịch D, minsup Output: Tập Answer gồm các tập mục thường xuyên trên D Method: L1= {large 1 – itemset}; C1 = database D; for (k=2; Lk-1 ; k++) do begin Ck; For all entries t Ck-1do Begin //Xác định các candidate itemset //được chứa trong giao dịch với định danh t.TID C1={cCk|(c-c[k])t.set_of_itemset(c-c[k-1])t.set_of_itemset}; For all candidates c Ct do c.count++; if (C1) then Ck Ck t.TID,Ct  end Luật kết hợp= {c Ck | c.count minsup}; end Answer = k Lk Sự khác nhau giữa Apriori và AprioriTID là: cơ sở dữ liệu không được sử dụng để đếm các support sau lần đầu tiên quét qua cơ sở dữ liệu. Vì sau lần quét đầu tiên các 1itemset đã được sinh (các L1), các L1 này được dùng để lọc ra các giao dịch của cơ sở dữ liệu bất kỳ item nào là không phổ biến và những giao dịch trong C1 chỉ chứa những item không phổ biến. Kết quả đó được đưa vào C2 và sử dụng lần quét đó. Vì vậy kích thước của C2 là khá nhỏ hơn so với C1. Sự giống nhau của hai thuật toán này là đều sử dụng bước cắt tỉa trong hàm Apriori_gen(). 3.4.3. Thuật toán Apriori-Hybrid Thuật toán Apriori-Hybrid được coi như kết hợp giữa Thuật toán Apriori và thuật toán Apriori-TID. Trong thuật toán Apriori-Hybrid, được sử dụng khi tổ chức lặp và chuyển sang Apriori-TID khi đã chắc chắn rằng tập Ck đã vào bộ nhớ chính. Thuật toán AprioriHybrid được coi là tốt hơn so với Apriori và AprioriTID. CHƢƠNG 4 – KHAI PHÁ LUẬT KẾT HỢP TRONG CƠ SỞ DỮ LIỆU HÌNH ẢNH Khai phá hình ảnh có liên quan tới phát hiện tri thức trong cơ sở dữ liệu hình ảnh. Chương này đề cập tới việc khai phá dữ liệu sử dụng luật kết hợp dựa trên nội dung hình ảnh. Quá trình khai phá dữ liệu gồm 4 bước: Tiền xử lý (Preprocessing), Trích chọn đặc trưng (Feature Extraction), chuẩn bị cơ sở dữ liệu trung gian và khai phá luật kết hợp. [6] 4.1. Dữ liệu hình ảnh Ảnh số là hình ảnh được ghi nhận bởi bộ cảm biến điện tử và lưu lại dưới dạng dữ liệu trong bộ nhớ của máy (thẻ nhớ, đĩa, ....). Ảnh số được tạo nên từ hàng trăm ngàn cho đến hàng triệu ô vuông rất nhỏ- được coi là những thành tố của bức ảnh và thường được biết dưới tên gọi là pixels. Có hai dạng ảnh số: ảnh đa mức xám và ảnh màu. [1] Thông thường ảnh số được thu nhận từ các phương pháp sau:  Ảnh chụp bằng máy ảnh số và ảnh in bằng scanner.  Các frame của video số.  Ảnh tạo ra từ các phần mềm đồ họa. 4.1.1 Biểu diễn ảnh số Có hai dạng ảnh số: Ảnh đa mức xám và ảnh màu Biểu diễn ảnh đa mức xám Ảnh được hiển thị trên màn hình bởi các pixel. Các pixel có độ chói (cường độ) khác nhau. Dải cường độ từ đen đến trắng phụ thuộc vào chất lượng ảnh, hay tổng số bít sử dụng cho mỗi pixel. Thí dụ với 8 bit biểu diễn pixel thì có tới 255 mức cường độ khác nhau có thể biểu diễn. Ảnh đa mức xám được biểu diễn bằng mảng 2 chiều. Mỗi phần tử của mảng tương ứng với 1 pixel. Việc sắp xếp các giá trị pixel này trong vùng nhớ liên tục được gọi là bitmap. Khái niệm này xuất phát từ ánh xạ (map) các pixel ảnh vật lý vào các địa chỉ liên tục trong bộ nhớ. Bộ nhớ sử dụng để lưu trữ dữ liệu ảnh bitmap được gọi là “frame buffer”. Biểu diễn ảnh màu Ảnh màu bao gồm trường chữ nhật các pixel. Ảnh màu cần 3 giá trị để biểu diễn ảnh. Mỗi giá trị biểu diễn một màu cơ sở. Cách biểu diễn này xuất phát từ lý thuyết rằng màu có thể hình thành từ trộn ba màu cơ sở. Các màu cơ sở sử dụng trong TV và màn hình máy tính là Red, Green và Blue. Ảnh màu có thể biểu diễn bởi ba mảng hai chiều tương ứng với các màu cơ sở red, green và blue của ảnh. 4.1.2 Các tham số chính của ảnh số Kích thước ảnh: Ta thường nói kích thước ảnh là x pixel và y dòng. Tổng số cột pixel và tổng số pixel trên hàng. Số lượng pixel có trong bức ảnh sẽ quyết định kích cỡ ảnh, ảnh hưởng đến độ lớn của các tệp ảnh. Chất lượng của bức ảnh khi được in hay hiển thị trên màn hình phụ thuộc một phần vào số lượng các pixels tạo nên bức ảnh (đôi khi được gọi là độ phân giảiresolution). Số lượng các pixels càng nhiều thì các chi tiết càng được hiển thị rõ, mức độ sắc nét càng tăng đồng nghĩa với việc độ phân giải cũng lớn hơn. Nếu như phóng đại bức ảnh số đủ lớn thì mắt người sẽ nhận ra được các pixels này.[1] Tổng số bit biểu diễn từng pixel (pixel depth): Với ảnh đa mức xám chất lượng chấp nhận được đòi hỏi 8 bit/pixel. Với ảnh màu, cần 24 bít/pixel (mỗi thành phần màu cần 8 bít). Dữ liệu của ảnh được tính như sau: D= x.y.b Trong đó: x - tổng số pixel/dòng ảnh y - tổng số dòng ảnh và b – tổng số bit/pixel. Thí dụ, ảnh 512 pixel x512 dòng và độ sâu pixel 24 bít, thì kích thước dữ liệu sẽ là: D=512x512x24 bit = 768 KB. 4.2. Trích chọn đặc trưng trong khai phá ảnh Trích chọn đặc trưng ảnh là bước tiền xử lý trong khai phá ảnh. Đây là bước quyết định trong toàn bộ quá trình khai phá ảnh. Phương pháp trích chọn xuất phát từ hình ảnh - rút ra mẫu và nhận được tri thức từ các hình ảnh sưu tập, giải quyết phần lớn với việc nhận dạng và trích chọn những đặc trưng duy nhất của phạm vi cụ thể. Có nhiều giá trị dặc trưng khác nhau, mục đich chính là nhận ra những đặc trưng tốt nhất và từ đó rút ra những thông tin có liên quan từ ảnh. Trích chọn đặc trưng ảnh rất có giá trị trong kiểm tra ảnh. [9] Thông thường, hình ảnh có các đặc trưng sau: Màu sắc, kết cấu, hình dạng, cạnh, … 4.2.1. Trích chọn đặc trưng màu sắc Có một số kỹ thuật trích chọn đặc trưng về màu sắc – Trung bình màu trong tỷ lệ màu xám, Trung bình màu trong định dạng RBG, và Trung bình màu trong YCBCR (Y là độ sáng và CB, CR là các thành phần màu . Việc đánh giá các phương pháp khác nhau sử dụng Độ chính xác (Precision) và Nhớ lại (Recall), và nhận thấy rằng YCBCR thực hiện tốt hơn hai phương pháp còn lại. Do đó ta sử dụng YCBCR làm cơ sở trính chọn đặc trưng màu sắc được chỉ ra trong hình dưới đây. Hình 4.1: Sử dụng YCBCR làm cơ sở trích chọn đặc trưng màu sắc (4.1) Kết quả của phương pháp này là một ma trận, kích thước 30x30 (cho khối 10x10 hoặc 37X37 cho 8x8), với '1 'trong các miền tương ứng có sự hiện diện của phù hợp với màu sắc và "0" trong các lĩnh vực mà không có màu sắc phù hợp.[9] 4.2.2. Trích chọn đặc trưng Texture Texture cho phép định nghĩa các đặc trưng lân cận – như là một vùng hoặc một khối. Sự thay đổi của mỗi Pixel liên quan tới các pixcel lân cận định nghĩa texture. Texture là đặc trưng quan trọng của ảnh nhưng khó mô tả và cảm nhận. Mục tiêu của nghiên cứu đặc tả texture là mô tả càng phù hợp với cảm nhận con người càng tốt. Trong đặc tả của họ, texture được mô tả bởi 6 đặc trưng: tính thô (coarseness), tính tương phản (contrast), tính theo hướng (directionality), tính tương tự đoạn thẳng (line likeness), tính đều đặn (regularity) và tính gồ ghề (roughness). Mô tả về tính toán định lượng các đặc trưng là khó khăn, không được nghiên cứu tại đây. Sau đây là mô tả định tính của sáu đặc trưng này:[9]  Tính thô  Tương phản  Tính theo hướng: là đặc tính trên vùng cho trước.  Tương tự đoạn thẳng  Đều đặn  Gồ ghề 4.2.3. Trích chọn đặc trưng Edge Đặc trưng Edge đặc biệt quan trọng đối với những hình ảnh tối. May mắn, những hình ảnh mẫu có chất lượng trung bình và do vậy không cần sử dụng đặc trưng Edge. Phương pháp phát hiện cạnh Candy với ngưỡng 0 được sử dụng. Chỉ riêng đặc trưng Edge ít có hiệu quả, do vậy cần phải kết hợp nó với các đặc trưng mạnh mẽ hơn, như màu sắc. Đặc trưng Edge cùng với đặc trưng về màu sắc mô tả ranh giới và vùng bên trong của Egeria.[9] Những hình sau đây là kết quả thu được khi kiểm thử một tập các ảnh có màu tối Hình 4.2. Trích chọn đặc trưng Edge 4.2.4. Kết hợp các đặc trưng Tất cả các đặc trưng được kết hợp thành hình ảnh chiết xuất cuối cùng như hình bên. Hình 4.3. Kết hợp các đặc trưng Tất cả các khối có các đại lượng tương tự nhau cho mỗi đặc trưng. Do đó sau khi xử lý các đặc trưng được trích chọn, mỗi khối cụ thể là một chuỗi 1 (Yes) và 0 (No), chiều dài tương ứng với số đặc trưng được trích chọn. Việc kết hợp các đặc trưng được trích chọn đồng nghĩa với việc hình thành các công thức. Một luật (rule) kết hợp ba đặc trưng là color&edge|textures, có nghĩa là color AND edge OR textures.[9] Luật thứ nhất và luật thứ ba chỉ ra rằng màu sắc kết hợp với texture hoặc edge đưa đến kết luận rằng Edgeria là trong khối hiện tại. Luật thứ hai chỉ ra rằng khi không có đặc trưng nào là 1 thì Egeria chắc chắn vắng mặt. Luật thứ 4 chỉ ra rằng màu sắc không đủ chắc chắn để chứng minh sự hiện diện của Egeria. Bảng 4.1. Ví dụ minh họa sự kết hợp các đặc trưng Color Textures Edge Class 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 2 (Uncertain) 4.3. Khai phá luật kết hợp dựa trên nội dung ảnh bằng thuật toán Apriori Trong khai thác luật kết hợp truyền thống, một tập các quy tắc được thể hiện dưới hình thức RHS=>LHS, trong đó RHS và LHS đều cho phép chứa nhiều mục. Sự hỗ trợ của luật kết hợp được xác định là tỷ lệ giao dịch có chứa tất cả các mục (cả LHS và RHS) trong một luật kết hợp và độ tin cậy của một luật kết hợp được xác định là tỷ lệ phần trăm của LHS cũng chứa RHS. Một luật kết hợp giữ nếu hỗ trợ của nó lớn hơn minsup và độ tin cậy (confidence )lớn hơn mincof và mincof có thể được cấu hình. Vấn đề của việc tìm kiếm các luật kết hợp là bị phân rã thành các vấn đề nhỏ của việc tìm tất cả các tập mục thiết lập với sự hỗ trợ tối thiểu và sử dụng các mục lớn tạo ra các quy tắc mong muốn (Kiểm thử với confidence nhỏ nhất).[6] Bước 1: Giai đoạn tiền xử lý Dữ liệu trong thực tế cuộc sống thường không đầy đủ và không phù hợp, vì vậy tiền xử lý là điều cần thiết. Trong trường hợp hình ảnh có kích thước lớn (1024x1024) và gần 50% hình ảnh là nền và những phần không cần thiết. Ngoài ra, những hình ảnh này được quét sáng khác nhau nên một số quá sáng, một số quá tối. Bước đầu tiên nhằm mục đích loại bỏ đi những phần dư thừa. Bước tiếp theo của quá trình tiền xử lý hình ảnh là hình ảnh được nâng cao kỹ thuật.[6] Bước 2: Quá trình trích chọn đặc trưng Sau quá trình tiền xử lý, một quá trình trích chọn được áp dụng nhằm trích chọn đặc trưng texture sử dụng kỹ thuật thống kê GLCM các thông số như, độ lệch chuẩn, trung bình, moments, độ mịn, Tính đồng nhất, Entropy có thể được trích chọn từ các ảnh tiền xử lý bằng cách sử dụng GLCM (Ma trận Gray Level Cooccurrence). [6] Ma trận GLCM của một hình ảnh được tính toán bằng cách sử dụng một vector d, xác định bởi bán kính ä và định hướng è. Tần số thông thường có thể được sử dụng bằng cách phân chia giá trị trong mỗi ô bằng tổng số các cặp điểm ảnh có thể. Do đó các nhân tố bình thường cho 0 ° sẽ được (Nx - 1) × Ny với Nx là chiều rộng và Ny là chiều cao của hình ảnh. Cấp độ lượng tử không kém phần quan trọng trong việc xác định sự xuất hiện đặc trưng texture. Ngoài ra, sự xuất hiện của ma trân các phần tử lân cận có liên quan chặt chẽ chất lượng hình ảnh. Lựa chọn bán kính δ: Giá trị δ nằm trong khoảng từ 1, 2 đến 10. Áp dụng cho các giá trị khoảng cách lớn thì ma trận GLCM không nắm bắt được thông tin chi tiết texture. Có thể thấy rằng độ chính xác phân loại một cách tổng thể với δ =1,2,4,8 là có thể chấp nhận được với kết quả tốt nhất với δ = 1 và 2. Kết luận này là hợp lý, một điểm ảnh có nhiều tương quan với những điểm ảnh gần hơn là những điểm ảnh ở vị trí xa. Lựa chọn góc θ: Mỗi điểm ảnh đều có tám điểm ảnh lân cận, vì vậy lựa chọn góc θ là: 00, 450, 900, 1350, 1800, 2250, 2700 hoặc 3150. Tuy nhiên, khi đưa vào xem xét định nghĩa của GLCM, việc lựa chọn các cặp 00 và 1800 ; 450, 900 và 1350 là tương tự nhau. Do đó, chúng ta có 4 lựa chọn giá trị cho θ. Đánh giá kết cấu của hình ảnh chụp quang tuyến vú được cho trong bảng 4.2.sau đây: Bảng 4.2. Đánh giá kết cấu của hình ảnh Thời điểm Biểu thức Đánh giá texture Ý nghĩa m  i 0 ZiP(Zi) Độ lệch chuẩn σ= Độ mịn L 1 2 =  2 2 R=1-1/(1+σ ) Cường độ trung bình Độ tương phản trung bình Độ mịn liên quan đến mật độ
- Xem thêm -

Tài liệu liên quan