Phương pháp phân cụm và ứng dụng

thấy phân khúc sản xuất khi các tính năng lọc Gabor được ghép để chứa các thông tin không gian (tọa độ pixel). Bộ lọc này dựa vào kỹ thuật Gabor đã được chứng minh rất mạnh và đã được mở rộng tới các phân đoạn tự động của văn bản trong tài liệu [Jain và hattacharjee 1992] và phân đoạn của các đối tượng trong nền phức tạp [Jain et al. 1997]. -70- (a) (b) Hình 28. Kết quả của kết cấu phân đoạn ảnh (a): kết cấu khảm 4 lớp. (b): bốn nhóm giải pháp thực hiện bởi giải thuật CLUSTER với tọa độ điểm ảnh bao gồm trong các tính năng thiết lập. Phân cụm dữ liệu có thể được sử dụng như là một giai đoạn tiền xử lý để xác định các lớp học mẫu để phân loại giám sát tiếp theo. Taxt và Lundervold [1994] và Lundervold et al. [1996] mô tả một thuật toán clustering partitional và một kỹ thuật ghi nhãn hướng dẫn sử dụng để xác định các lớp vật liệu (ví dụ, não tủy chất lỏng, chất trắng, bắp Khối, khối u) trong các hình ảnh được đăng ký của một con người có được ở đầu năm kênh khác nhau hình ảnh cộng hưởng từ (yielding một năm chiều tính năng vector tại mỗi điểm ảnh). Một số phân cụm đã thu được và kết hợp với kiến thức tên miền (nhân lực chuyên môn) để xác định các lớp khác nhau. Quyết định quy định phân loại giám sát được dựa trên những lớp này được lấy. Hình 29 (một) cho thấy một trong những kênh của một đầu vào-đa quang phổ hình ảnh; phần b cho thấy 9-cụm kết quả. Thuật toán K-means là đã được áp dụng cho các phân khúc của LANDSAT hình ảnh trong Solberg et al. [1996]. Các trung tâm cụm ban đầu được chọn tương tác của một nhà điều hành đào tạo, và tương ứng với các lớp học sử dụng đất như khu vực đô thị, đất (thực vật miễn phí) các khu vực, rừng, đồng cỏ, và nước. Hình 30 (một) cho thấy những hình ảnh đầu vào hoàn trả như màu xám; phần b cho thấy kết quả của thủ tục phân cụm dữ liệu. -71- (a) (b) Hình 29. Phân đoạn ảnh y tế đa quang phổ. (a)Kênh duy nhất của ảnh đầu vào. (b) 9 cụm phân đoạn ảnh (a) (b) Hình 30: Phân đoạn ảnh LANDSAT. (a) Bản gốc hình ảnh ESA / EURIMAGE / Sattelitbild). (b): Cảnh đã được phân cụm. 2.Nhận dạng đối tƣợng và ký tự 2.1 Nhận dạng đối tƣợng Việc sử dụng các phân nhóm để xem nhóm đối tượng 3D cho mục đích công nhận đối tượng trong phạm vi dữ liệu đã được mô tả trong Dorai và Jain [1995]. Các thuật ngữ dùng để chỉ xem một hình ảnh phạm vi của một đối tượng thu được từ bất cứ quan điểm tùy ý. Hệ thống xem xét, làm việc theo một quan điểm phụ thuộc (hoặc xem trung tâm) cách tiếp cận đối với vấn đề công nhận đối tượng; mỗi đối tượng được công nhận là đại diện trong điều khoản của một thư viện hình ảnh loạt các đối tượng đó. -72- Có rất nhiều ý có thể có của một đối tượng 3D và mục tiêu một trong những công việc mà là để tránh kết hợp một đầu vào xem không rõ đối với từng hình ảnh của từng đối tượng. Một chủ đề phổ biến trong văn học công nhận đối tượng được lập chỉ mục, trong đó xem chưa biết được sử dụng để chọn một tập hợp con của điểm của một tập hợp con của các đối tượng trong cơ sở dữ liệu để so sánh hơn nữa, và từ chối tất cả các điểm khác của đối tượng. Một trong những cách tiếp cận để đánh chỉ sử dụng các khái niệm của các tầng lớp xem; một lớp học xem là tập hợp các điểm chất lượng tương tự của một đối tượng. Trong tác phẩm đó, các lớp học xem đã được xác định bởi phân cụm dữ liệu; phần còn lại của tiểu mục này vạch ra các kỹ thuật. Xem đối tượng đã được nhóm lại vào các lớp học dựa trên hình dạng giống nhau của các tính năng phổ. Mỗi hình ảnh đầu vào của một đối tượng xem trong sản lượng cô lập một vector tính năng mà nó mô tả. Các tính năng vector chứa trong mười phút đầu tiên trung tâm của một hình bình thường    h hHhm )()(1 hoá quang phổ phân phối, )(hH  , của một đối tượng xem là thu được từ dữ liệu phạm vi của nó bằng cách xây dựng một biểu đồ của các giá trị chỉ số hình dạng (có liên quan đến các giá trị bề mặt cong) và tích lũy tất cả các đối tượng điểm ảnh mà rơi vào mỗi thùng. Bởi bình thường hóa quang phổ đối với diện tích tổng số đối tượng, quy mô (size) khác nhau mà có thể tồn tại giữa các đối tượng khác nhau được gỡ bỏ. Tại thời điểm đầu tiên m1 tính toán mà có ý nghĩa )(hH :    h hHhm )()(1 . (1) Với momen trung tâm khác, mp, 102  p được định nghĩa là :      h p p hHmhm _ 1 (2) Do đó các vecto đặc tính được biểu thị bằng  ,,...,, 1021 mmmR  nằm Trong khoảng [-1,1]. Tại O =  nOOO ,...,, 21 là một lựa chọn của n đối tượng 3D với cảnh nằm -73- trong cơ sở dữ liệu. MD. cảnh thứ i của j đối tượng, i jO trong cơ sở dữ liệu được biểu thị bằng i j i j RL , , nơi i jL là đối tượng nhãn và i jR là vecto đặc tính. Cho một tập đối tượng đại diện Ri =  iiii RLRL 1111 ,,,  mà mô tả m cảnh của i đối tượng, mục tiêu là để lấy ra một phần của cảnh P i =  ikii iCCC ,,, 21  . Mỗi cụm trong Pi chứa những cảnh của đối tượng thứ i mà đối tượng đó đã được cấp tượng tự dựa trên sự không giô ́ng nhau giữa các thời điểm tương ứng với các tính năng của hình quang phổ của các cảnh . Các biện pháp của không giô ́ng nhau giữa i jR và i kR được định nghĩa : D       10 1 2 , l i kl i jl i k i j RRRR (3) Phân cụm dữ liệu Cảnh(Views) Một cơ sở dữ liệu chứa khoảng 3,200 ảnh của 10 đối tượng điêu khắc khác nhau với 320 cảnh được sử dụng [Dorai and Jain 1995]. Các hình ảnh dao động từ 320 quan điểm có thể (xác định bởi lưới tổ ong của xem-mặt cầu bằng cách sử dụng khối 20 mặt ) của các đối tượng đã được tổng hợp. Hình 31 cho thấy một tập hợp con của tập hợp các điểm của Rắn hổ mang được sử dụng trong thử nghiệm. Hình dạng phổ của từng xem là tính véc tơ đặc tính và sau đó tính năng của nó được xác định. Cảnh của từng đối tượng đang tụ tập, dựa trên D đo không giô ́ng nhau giữa vectơ thời điểm của họ bằng cách sử dụng các kết nối Đề án clustering thứ bậc [Jain và Dubes 1988]. Các nhóm thứ bậc thu được với 320 cảnh của đối tượng Rắn hổ mang được hiển thị trong hình 32. Cảnh của nhóm phân cấp chín đối tượng khác cũng tương tự như các dendrogram trong hình 32. Dendrogram này được cắt ở mức độ không giô ́ng nhau là 0,1 hoặc ít hơn để có được nhỏ gọn và cũng cách nhau cụm. Các clusterings thu được theo cách này chứng minh rằng quan điểm của từng đối tượng rơi vào một vài cụm khác biệt rõ rệt. Các trọng tâm của mỗi cụm này đã được xác định bởi máy tính trung bình của vectơ thời điểm của lượt xem rơi vào một cụm. -74- Hình 31. Một tập con các cảnh của ảnh Rắn hổ mang được chọn từ 320 cảnh Dorai và Jain [1995] chứng minh rằng phân nhóm này dựa trên xem nhóm đối tượng phù hợp với thủ tục tạo điều kiện về tính chính xác phân loại và số lượng phù hợp cần thiết cho việc phân loại đúng của xem thử. Xem đối tượng được nhóm thành các cụm xem nhỏ gọn và đồng nhất, như vậy chứng tỏ sức mạnh của cluster dựa trên sơ đồ tổ chức xem và phù hợp với đối tượng có hiệu quả. -75- Hình 32 : Cấu trúc của một nhóm gồm 320 cảnh của một tác phẩm điêu khắc con rắn hổ mang. 2.2 Nhận dạng ký tự. Kỹ thuật nhận dạng ký dựa vào phân cụm dữ liệu được phát triển bởi Connell và Jain [1998] để nhận biết lexemes trong văn bản viết tay cho các mục đích của nhà văn viết tay công nhận độc lập. Sự thành công của một hệ thống nhận dạng chữ viết là cực kỳ phụ thuộc vào chấp nhận bởi người sử dụng tiềm năng. Nhà văn phụ thuộc hệ thống cung cấp một mức độ cao hơn sự công nhận chính xác hơn so với các hệ thống nhà văn độc lập, nhưng đòi hỏi một lượng lớn dữ liệu đào tạo. Một nhà văn độc lập hệ thống, mặt khác, phải có khả năng nhận ra nhiều phong cách văn bản nhằm đáp ứng một người dùng cá nhân. Khi các biến thiên của phong cách văn bản phải được bắt giữ bởi một hệ thống tăng, nó càng trở nên khó khăn để phân biệt đối xử giữa các lớp khác nhau do số lượng chồng chéo nhau trong không gian tính năng này. Một trong những giải pháp cho vấn đề này là để tách các dữ liệu từ những -76- phong cách viết khác nhau cho mỗi lớp học vào lớp con khác nhau, được gọi là lexemes. Những lexemes đại diện cho các phần của dữ liệu được dễ dàng hơn tách ra từ các dữ liệu của các tầng lớp khác hơn mà lexeme thuộc. Trong hệ thống này, chữ viết là bị bắt bởi số hoá các tọa độ (x, y) và vị trí của các cây bút và vị trị đặt điểm bút (lên hoặc xuống) với tỷ lệ lấy mẫu không đổi. Sau một số lấy lại mẫu, bình thường hoá, và làm mịn, mỗi nét bút là đại diện như là một chuỗi dài biến-điểm. Một số liệu dựa trên đàn hồi mẫu lập trình phù hợp và năng động, được xác định để cho phép khoảng cách giữa hai nét để được tính toán. Sử dụng các khoảng cách tính bằng cách này, một ma trận gần nhau được xây dựng của từng loại chữ số (tức là, 0 thông qua 9). Mỗi biện pháp ma trận khoảng cách lớp trong cho một lớp chữ số cụ thể. Chữ số trong một lớp đặc biệt là nhóm trong một thực nghiệm để tìm một số lượng nhỏ các nguyên mẫu. Phân cụm được thực hiện bằng cách sử dụng chương trình CLUSTER mô tả ở trên [Jain và Dubes 1988], trong đó véc tơ tính năng cho một chữ số của nó là N lân cận đến con số của cùng một lớp. CLUSTER phân nhóm tốt nhất cho mỗi giá trị của K trên một số phạm vi, trong đó K là số cụm vào đó dữ liệu này là để được phân vùng. Theo dự đoán, có nghĩa là lỗi bình phương (MSE) giảm đơn điệu như là một chức năng của K. Các "tối ưu" giá trị của K được chọn bằng cách xác định một “đầu gối” trong biểu đồ của MSE vs K. Khi đại diện cho một cụm chữ số của một mẫu thử nghiệm duy nhất, tốt nhất nhận diện on-line kết quả được công nhận đã thu được bằng cách sử dụng các chữ số đó là gần nhất để tới trung tâm cụm's. Sử dụng sơ đồ này, một tỷ lệ nhận diện chính xác là 99,33%. 3. Truy hồi thông tin Thông tin hồi thông tin (Information Retrieval) có liên quan với lưu trữ tự động và lấy các tài liệu [Rasmussen 1992]. Nhiều thư viện các trường đại học sử dụng hệ thống IR để cung cấp truy cập vào các cuốn sách, tạp chí, và các tài liệu khác. Các thư viện đó sử dụng đề án Li•brary of Congress Classification (LCC) (Phân loại Thư viện Quốc hội Mỹ), đề án này hiệu quả cho việc lưu trữ và truy tìm sách. Đề án LCC bao gồm các lớp có nhãn A đến Z [LC Classification Outline 1990] được sử dụng để ký tự hóa sách thuộc các đối tượng khác nhau. Ví dụ, nhãn Q tương ứng với sách trong lĩnh vực khoa -77- học, và bảo đảm chất lượng phân lớp được phân công toán học. Nhãn QA76 tới QA76.8 được sử dụng để phân loại sách liên quan đến máy tính và các lĩnh vực khác của khoa học máy tính. Có một số vấn đề liên quan đến việc phân loại các sách bằng cách sử dụng sơ đồ LCC. Một số trong số này được liệt kê dưới đây: (1) Khi một người sử dụng đang tìm kiếm một cuốn sách trong thư viện mà với một chủ đề anh ta quan tâm, số LCC một mình có thể không thể để lấy tất cả các sách có liên quan. Điều này là do số lượng phân loại được chỉ định cho những cuốn sách hay các loại chủ đề thường được nhập vào trong cơ sở dữ liệu không có đủ thông tin liên quan đến tất cả các chủ đề được bảo hiểm trong một cuốn sách. Để minh họa điểm này, chúng ta hãy xem xét cuốn sách “Các thuật toán cho phân cụm dữ liệu” của Jain và Dubes [1988]. Số LCC của nó là 'QA 278.J35'. Trong số này LCC, QA 278 tương ứng với chủ đề 'phân tích cụm', J tương ứng với tên tác giả đầu tiên và 35 là số serial phân công của Thư viện Quốc hội. Các loại chủ đề cho cuốn sách này được cung cấp bởi nhà xuất bản (mà thường được nhập vào trong cơ sở dữ liệu để tạo điều kiện tìm kiếm) là nhóm phân tích, xử lý dữ liệu và thuật toán. Có một chương trong sách này [Jain và Dubes 1988] rằng đề với tầm nhìn máy tính, xử lý hình ảnh, và phân khúc hình ảnh. Vì vậy, một người sử dụng tìm kiếm cho văn học trên máy vi tính và tầm nhìn, đặc biệt, hình ảnh phân khúc sẽ không thể truy cập cuốn sách này bằng cách tìm kiếm cơ sở dữ liệu với sự giúp đỡ của một trong hai số LCC hoặc các loại đối tượng được cung cấp trong cơ sở dữ liệu. Số LCC cho sách tầm nhìn máy tính được TA 1632 [LC Classification 1990] đó là rất khác với QA số 278.J35 được đăng ký cho cuốn sách này. 2) Có một vấn đề cố hữu trong giao LCC số sách ở một khu vực phát triển nhanh. Ví dụ, chúng ta hãy xem xét các khu vực của các mạng thần kinh. Ban đầu, thể loại 'QP' trong LCC Đề án đã được sử dụng để nhãn sách và thủ tục tố tụng tại hội nghị khu vực này. Ví dụ, Proceedings of the Joint International Conference on Neural Networks [IJCNN'91] được giao QP của số 363,3 '. Tuy nhiên, hầu hết các cuốn sách gần đây trên các mạng thần kinh được cho một số cách sử dụng các nhãn thể loại 'QA'; Proceedings of IJCNN'92 các [IJCNN'92] được phân công bảo đảm chất lượng của số 76,87 '. Nhiều nhãn cho sách đối phó với cùng một chủ đề sẽ buộc họ được đặt trên -78- ngăn xếp khác nhau trong một thư viện. Do đó, có một cần phải cập nhật các nhãn phân loại theo thời gian trong một kỷ luật mới nổi. (3) việc giao một số cho một cuốn sách mới là một vấn đề khó khăn. Một cuốn sách có thể đối phó với các chủ đề tương ứng với hai hoặc nhiều số LCC, và do đó, chỉ định một số duy nhất cho cuốn sách như vậy là rất khó khăn. Murty và Jain [1995] mô tả một kiến thức dựa trên lược đồ phân nhóm để đại diện nhóm các cuốn sách, trong đó thu được bằng cách sử dụng CR ACM (Hội máy tính Máy vi tính Xem lại) phân loại cây [ACM CR Classifications 1994]. Cây này được sử dụng bởi các tác giả góp phần ACM ấn phẩm khác nhau để cung cấp các từ khóa trong các hình thức thể loại ACM nhãn CR. Cây này bao gồm 11 nút ở cấp độ đầu tiên. Các nút là có nhãn A đến K. Mỗi nút trong cây này có một nhãn đó là một chuỗi của một hay nhiều ký hiệu. Những biểu tượng này được ký tự chữ-số. Ví dụ, I515 là nhãn của một nút cấp độ thứ tư trong cây. 3.1 Biểu diễn mẫu Mỗi cuốn sách được thể hiện như một danh sách tổng quát [Sangal 1991] của những dây bằng cách sử dụng phân loại cây ACM CR. Vì mục đích ngắn gọn trong đại diện, các cấp, các nút thứ tư trong cây phân loại ACM CR được gắn nhãn bằng cách sử dụng chữ số 1-9 và ký tự A đến Z. Ví dụ, các nút con của I.5.1 (mô hình) được dán nhãn I.5.1 0,1 đến I.5.1.6. Ở đây, I.5.1.1 tương ứng với các nút có nhãn xác định, và I.5.1.6 là viết tắt của nút có nhãn structural.Ina thời trang tương tự, tất cả các cấp, các nút thứ tư trong cây có thể được gắn nhãn là cần thiết. Từ bây giờ, các dấu chấm ở giữa biểu tượng kế tiếp sẽ được bỏ qua để đơn giản hóa các đại diện. Ví dụ, I.5.1.1 sẽ được ký hiệu là I511. Minh họa cho quá trình này đại diện với sự giúp đỡ của các cuốn sách của Jain và Dubes [1988]. Có năm chap-ters trong cuốn sách này. Để đơn giản chế biến, chỉ xem xét có các thông tin trong các nội dung chương. Có một mục duy nhất trong bảng nội dung cho các chương 1, 'Giới thiệu', và vì vậy không lấy bất kỳ từ khoá từ này. Chương 2, có nhãn ' Dữ liệu Đại diện,' đã đề mục tương ứng với các nhãn của các nút trong cây phân loại ACM CR [ACM CR Classifications 1994] được đưa ra dưới đây: (1a) I522 (feature evaluation and selection), -79- (2b) I532 (similarity measures), and (3c) I515 (statistical). Dựa trên những phân tích trên, Chương 2 của Jain và Dubes [1988] có thể được đặc trưng bởi sự phân ly trọng ((I522 ∨ I532 ∨ I515) (1,4)). Các trọng lượng (1,4) biểu thị rằng nó là một trong bốn chương, trong đó có vai trò trong các đại diện của cuốn sách. Căn cứ vào bảng nội dung, chúng tôi có thể sử dụng một hoặc nhiều dây I522, I532, I515 và đại diện cho Chương 2. Tương tự như vậy, chúng tôi có thể đại diện cho chương khác trong cuốn sách này như các phép tuyển trọng dựa trên các bảng nội dung và phân loại cây ACM CR. Các đại diện của toàn bộ cuốn sách, sự kết hợp của tất cả các cơ quan đại diện chương, được cho bởi (((I522 ∨ I532 ∨ I515) (1,4) ∧ ((I515 ∨ I531) (2,4)) ∧ ((I541 ∨ I46 ∨ I434) (1,4))). Hiện nay, các đại diện được tạo ra bằng tay bằng cách quét các bảng nội dung của sách trong lĩnh vực khoa học máy tính như ACM cây phân loại CR cung cấp kiến thức về cuốn sách khoa học máy tính. Các chi tiết của bộ sưu tập của cuốn sách được sử dụng trong nghiên cứu này có sẵn trong Murty và Jain [1995]. 3.2 Phép đo tƣơng tự Sự giống nhau giữa hai cuốn sách dựa trên sự giống nhau giữa các chuỗi tương ứng. Hai trong số các chức năng nổi tiếng, khoảng cách giữa một cặp dây được [Baeza-Yates 1992] khoảng cách Hamming và sửa khoảng cách. Không phải của các chức năng này khoảng cách hai có thể được sử dụng trong các ứng dụng có ý nghĩa này. Ví dụ sau minh hoạ điểm. Hãy xem xét ba dây I242, I233, và H242. Những chuỗi là các nhãn (predicate logic đại diện cho kiến thức, lập trình logic, và các hệ thống cơ sở dữ liệu phân tán) trong ba cấp độ thứ tư, các nút trong cây phân loại ACM CR. Các nút I242 và I233 là cháu của các nút có nhãn I2 (trí tuệ nhân tạo) và H242 là một cháu của các nút có nhãn H2 (cơ sở dữ liệu quản lý). Vì vậy, khoảng cách giữa I242 và I233 phải nhỏ hơn mà giữa I242 và H242. Tuy nhiên, khoảng cách Hamming và sửa khoảng cách [Baeza-Yates 1992] cả hai đều có một giá trị 2 giữa I242 và I233 và giá trị của 1 giữa I242 và H242. Hạn chế này thúc đẩy định nghĩa của một biện pháp tương tự mới mà bắt đúng sự giống nhau giữa các chuỗi ở trên. Sự giống nhau giữa hai chuỗi được định nghĩa là tỷ lệ chiều dài của tiền -80- tố phổ biến nhất [Murty và Jain 1995] giữa hai dây với chiều dài của chuỗi đầu tiên. Ví dụ, sự giống nhau giữa chuỗi I522 và I51 là 0,5. Các biện pháp tương tự được đề xuất là không đối xứng, vì sự giống nhau giữa I51 và I522 là 0,67. Các giá trị tối thiểu và tối đa là biện pháp tương tự này là 0,0 và 1,0, tương ứng. Các kiến thức về các mối quan hệ giữa các nút trong cây phân loại ACM CR là bị bắt bởi các đại diện trong các hình thức dây. Ví dụ, nút có nhãn công nhận là mẫu đại diện là I5 chuỗi, trong khi I53 chuỗi tương ứng với các nút có nhãn clustering. Sự giống nhau giữa hai nút (I5 và I53) là 1,0. Một biện pháp đối xứng của tương [Murty và Jain 1995] được sử dụng để xây dựng một ma trận tương tự có kích thước 100 x 100 tương ứng với 100 cuốn sách được sử dụng trong các thí nghiệm. 3.3 Một giải thuật cho phân cụm dữ liệu sách Vấn đề phân nhóm có thể được nêu như sau. Cho một bộ sưu tập B của cuốn sách, chúng ta cần để có được một tập C thiết lập các cụm. Một gần dendrogram(cây các cụm) [Jain và Dubes 1988], sử dụng Thuật toán phân cụm kết nối kết tụ hoàn toànhoàn để thu thập 100 cuốn sách được thể hiện trong hình 33. Bảy cụm thu được bằng cách chọn một ngưỡng   có giá trị 0,12. Nó nổi tiếng mà các giá trị khác nhau cho   có thể cung cấp cho clusterings khác nhau. Ngưỡng giá trị này được chọn bởi vì " khoảng cách " trong dendrogram giữa các cấp mà sáu và bảy cụm được hình thành là lớn nhất. Xét nghiệm các lĩnh vực chủ đề của cuốn sách [Murty và Jain 1995] trong các cụm tiết lộ rằng các cụm thu được là thực sự có ý nghĩa. Mỗi cụm được đại diện bằng cách sử dụng một danh sách các chuỗi s và cặp sf tần số, nơi sf là số sách trong các cụm, trong đó s là hiện tại. Ví dụ, cụm c1 chứa 43 cuốn sách thuộc về nhận diện mô hình, các mạng thần kinh, trí tuệ nhân tạo và tầm nhìn máy tính; một phần của R(C1) đại diện của nó được đưa ra dưới đây. W(C1) = ((B718,1), (C12,1), (D0,2), (D311,1), (D312,2), (D321,1), (D322,1), (D329,1),... (I46,3), (I461,2), (I462,1), (I463, 3), ... (J26,1), (J6,1), (J61,7), (J71,1)) -81- Những cụm sách và mô tả cluster tương ứng có thể được sử dụng như sau: Nếu một người sử dụng đang tìm kiếm sách, nói, về hình ảnh phân khúc (I46), sau đó chúng ta chọn cụm C1 vì đại diện của mình có chứa I46 chuỗi. Sách B2 (Neurocomputing) và B18 (Neural Networks: Lateral Inhibition) là cả hai thành viên của nhóm C1 mặc dù số LCC của họ khá khác nhau (B2 là QA76.5.H4442, B18 là QP363.3.N33). Bốn sách bổ sung có nhãn B101, B102, B103, B104 và đã được sử dụng để nghiên cứu các vấn đề của việc phân công phân loại số sách mới. Những số LCC của những cuốn sách này là: (B101) Q335.T39, (B102) QA76.73.P356C57, (B103) QA76.5.B76C.2, và (B104) QA76.9D5W44. Những quyển sách này được giao cho các cụm dựa trên phân loại hàng xóm gần nhất. Những hàng xóm gần nhất của B101, một cuốn sách về nhân tạo tình báo, là B23 và vì vậy B101 được phân công cụm C1. Nó được quan sát thấy sự phân công của bốn sách các cụm tương ứng là có ý nghĩa, chứng tỏ rằng kiến thức dựa trên phân cụm dữ liệu rất hữu ích trong việc giải quyết các vấn đề liên quan đến lấy tài liệu. 4. Khai phá dữ liệu Trong những năm gần đây chúng ta đã thấy bao giờ tăng khối lượng dữ liệu thu thập của tất cả các loại. Với rất nhiều dữ liệu có sẵn, nó là cần thiết để phát triển các thuật toán mà có thể lấy thông tin từ các cửa hàng có ý nghĩa rộng lớn. Tìm kiếm nuggets hữu ích của thông tin giữa các số lượng rất lớn của các dữ liệu đã được biết đến như là các lĩnh vực khai phá dữ liệu. Khai phá dữ liệu có thể được áp dụng cho quan hệ, giao dịch, và cơ sở dữ liệu không gian, cũng như các cửa hàng lớn dữ liệu có cấu trúc như World Wide Web. Có nhiều dữ liệu trong hệ thống khai thác sử dụng ngày nay, và các ứng dụng bao gồm Cục Ngân khố Hoa Kỳ phát hiện rửa tiền, Hiệp hội Bóng rổ Quốc gia huấn luyện viên phát hiện xu hướng và mô hình của các cầu thủ chơi cho cá nhân và các đội, và phân loại các mô hình của trẻ em trong hệ thống chăm sóc nuôi dưỡng [Hedberg 1996] . Một số tạp chí gần đây đã có những vấn đề đặc biệt về khai phá dữ liệu [1996 Cohen, Cross 1996, Wah 1996]. -82- 4.1 Khai phá dữ liệu bằng Phƣơng pháp tiếp cận. Khai phá dữ liệu, giống như phân cụm dữ liệu, là một hoạt động thăm dò, do đó, phương pháp phân cụm dữ liệu đang rất thích hợp để khai phá dữ liệu. Phân cụm dữ liệu thường là một bước khởi đầu quan trọng của một số trong quá trình khai phá dữ liệu [Fayyad 1996]. Một số phương pháp khai phá dữ liệu sử dụng phương pháp phân cụm dữ liệu được cơ sở dữ liệu phân khúc, mẫu tiên đoán, và trực quan hóa cơ sở dữ liệu lớn. Phân đoạn. Phương pháp phân cụm dữ liệu được sử dụng trong khai phá dữ liệu vào cơ sở dữ liệu phân khúc thành các nhóm đồng nhất. Điều này có thể phục vụ mục đích của nén dữ liệu (làm việc với các cụm hơn là các cá nhân), hoặc để nhận biết các đặc điểm của dân số phụ thuộc mà có thể được nhắm mục tiêu cho các mục đích cụ thể (ví dụ, tiếp thị nhằm vào người già). Thuật toán phân cụm dữ liệu K-means [Faber 1994] đã được sử dụng để phân cụm điểm ảnh trong hình ảnh Landsat [Faber et al. 1994]. Mỗi điểm ảnh ban đầu có 7 giá trị từ các ban nhạc vệ tinh khác nhau, bao gồm hồng ngoại. Những giá trị 7 là khó khăn cho con người để đồng hóa và phân tích mà không cần sự trợ giúp. Các điểm ảnh với các giá trị 7 tính năng được nhóm thành 256 nhóm, sau đó mỗi điểm ảnh được gán giá trị của cụm trung tâm. Hình ảnh này sau đó có thể được hiển thị với những thông tin không gian còn nguyên vẹn. Con người người xem có thể nhìn vào một hình ảnh đơn và xác định một khu vực quan tâm (ví dụ, đường cao tốc hoặc rừng) và nhãn nó như là một khái niệm. Hệ thống này sau đó xác định điểm ảnh khác trong cùng một nhóm như là một ví dụ của khái niệm đó. Đoán trước mẫu. Thống kê phương pháp phân tích dữ liệu thường liên quan đến thử nghiệm một mô hình giả thuyết của các nhà phân tích đã có trong tâm trí. Khai thác dữ liệu có thể giúp người dùng phát hiện giả thuyết tiềm năng trước khi sử dụng các công cụ thống kê. Đoán trước mô hình sử dụng phân nhóm để các nhóm, sau đó infers quy tắc để characterize các nhóm và đề xuất các mô hình. Ví dụ, người đăng ký tạp chí có thể được nhóm dựa trên một số yếu tố (tuổi tác, giới tính, thu nhập, vv), sau đó các nhóm kết quả đặc trưng trong một nỗ lực để tìm một mô hình mà sẽ phân biệt các thuê bao này sẽ gia hạn đăng ký của họ từ những người mà sẽ không [Simoudis 1996]. Hình ảnh. Cụm trong cơ sở dữ liệu lớn có thể được sử dụng để hình dung, để -83- hỗ trợ các nhà phân tích của con người trong việc xác định các nhóm và nhóm con có đặc điểm tương tự. WinViz [Lee và Ong 1996] là một công cụ khai thác dữ liệu trực quan, trong đó có nguồn gốc cụm có thể được xuất khẩu như các thuộc tính mới mà sau đó có thể được đặc trưng bởi hệ thống. Ví dụ, ngũ cốc ăn sáng được nhóm theo calo, đạm, chất béo, natri, chất xơ, carbohydrate, đường, kali, vitamin và các nội dung trên phục vụ. Khi thấy các cụm kết quả, người sử dụng có thể xuất các cụm để Win-Viz là thuộc tính. Hệ thống này cho thấy rằng một trong những cụm được đặc trưng bởi nội dung kali cao, và các nhà phân tích của con người nhận ra các cá nhân trong nhóm như là thuộc cám "gia đình ngũ cốc", dẫn đến một khái quát rằng "ngũ cốc, cám nhiều chất kali." 4.2 Khai phá dữ liệu có cấu trúc lớn. Khai thác dữ liệu thường được thực hiện trên cơ sở dữ liệu quan hệ giao dịch và cũng đã xác định các lĩnh vực mà có thể được sử dụng như là các tính năng, nhưng đã được nghiên cứu gần đây về cơ sở dữ liệu có cấu trúc lớn như World Wide Web [Etzioni 1996]. Ví dụ về các nỗ lực gần đây để phân loại các văn bản web bằng cách sử dụng từ ngữ hoặc các chức năng của các từ như tính năng bao gồm Maarek và Shaul [1996] và Chekuri et al. [1999]. Tuy nhiên, bộ tương đối nhỏ các mẫu đào tạo có nhãn và chiều hạn chế rất lớn sự thành công cuối cùng của tự động phân loại tài liệu web dựa trên những từ như tính năng. Chứ không phải là nhóm tài liệu trong một không gian tính từ, Wulfekuhler và Punch [1997] cụm từ từ một bộ sưu tập nhỏ của World Wide Web tài liệu trong không gian văn bản. Các dữ liệu mẫu thiết lập bao gồm 85 tài liệu từ các miền trong sản xuất người dùng khác nhau 4-xác định loại (lao động, luật pháp, chính phủ, và thiết kế). 85 tài liệu chứa 5.190 thân cây khác biệt từ sau khi các từ thông dụng (các, và, trong) đã được gỡ bỏ. Kể từ từ được chắc chắn không phải không tương quan, họ sẽ rơi vào nơi cụm từ được sử dụng một cách thống nhất trên toàn bộ tài liệu có giá trị tương tự như của tần số trong mỗi tài liệu. Phương pháp phân cụm bằng K-means có nghĩa là phân nhóm đã được sử dụng để nhóm các từ 5.190 thành 10 nhóm. Một kết quả đáng ngạc nhiên là trung bình 92% trong các từ rơi vào một cụm duy nhất, mà sau đó có thể -84- được loại bỏ để khai thác dữ liệu mục đích. Các cụm nhỏ nhất có điều khoản đó vào một con người có vẻ ngữ nghĩa liên quan. Các cụm 7 nhỏ nhất từ một hoạt động tiêu biểu được thể hiện trong hình 34. Điều khoản được sử dụng trong ngữ cảnh bình thường, hoặc điều kiện duy nhất mà không xảy ra thường xuyên trên toàn bộ tài liệu đào tạo sẽ có xu hướng cụm thành nhóm thành viên lớn 4000. Điều này sẽ chăm sóc các lỗi chính tả, tên riêng mà không thường xuyên, và các điều khoản được sử dụng theo cách tương tự trong suốt đặt toàn bộ tài liệu. Điều khoản sử dụng trong bối cảnh cụ thể (như tập tin trong bối cảnh nộp đơn sáng chế, hơn là một tập tin máy tính) sẽ xuất hiện trong các tài liệu phù hợp với điều kiện thích hợp khác cho rằng bằng sáng chế (bối cảnh đó, phát minh ra) và do đó sẽ có xu hướng cụm lại với nhau. Trong số các nhóm từ, ngữ cảnh đặc biệt nổi bật so với đám đông. Sau khi discarding cluster lớn nhất, các thiết lập nhỏ hơn các tính năng có thể được sử dụng để xây dựng các truy vấn để tìm ra các tài liệu khác có liên quan trên Web tiêu chuẩn sử dụng công cụ tìm kiếm web (ví dụ, Lycos, Alta Vista, mở văn bản). Tìm kiếm trên Web với các điều khoản lấy từ cụm từ cho phép phát hiện ra các chủ đề hạt mịn (ví dụ, gia đình y tế để lại) trong vòng loại được định nghĩa rộng rãi (ví dụ, lao động). 4.3 Khai phá dữ liệu trong Cơ sở dữ liệu địa chất. Khai phá cơ sở dữ liệu là một nguồn lực quan trọng trong việc thăm dò dầu mỏ và sản xuất. Nó được phổ biến kiến thức trong ngành công nghiệp dầu mà chi phí điển hình của một khoan mới ra nước ngoài cũng là trong khoảng $ 3-40, nhưng cơ hội của trang web đó là một thành công kinh tế là 1 trong 10. Thêm thông tin và có hệ thống khoan quyết định một cách đáng kể có thể làm giảm chi phí sản xuất chung. Tiến bộ trong công nghệ khoan và các phương pháp thu thập dữ liệu có dẫn đến các công ty dầu mỏ và ancillaries của họ thu thập một lượng lớn địa vật lý / dữ liệu địa chất từ giếng sản xuất và các trang web thăm dò, và sau đó tổ chức chúng thành các cơ sở dữ liệu lớn. Kỹ thuật khai thác dữ liệu gần đây đã được sử dụng để lấy được chính xác phân tích mối quan hệ giữa các hiện tượng quan sát và các thông số. Những mối quan hệ sau đó có thể được sử dụng để định lượng dầu và khí đốt. -85- Về chất lượng, trữ lượng tốt phục hồi có bão hòa hydrocarbon cao đang mắc kẹt bởi trầm tích rất xốp (chứa porosity) và bao quanh bởi số lượng lớn các loại đá cứng có ngăn chặn sự rò rỉ dầu khí từ xa. Một khối lượng lớn các trầm tích xốp là rất quan trọng để tìm dự trữ phục hồi tốt, do đó phát triển đáng tin cậy và chính xác các phương pháp cho dự toán của porosities trầm tích từ các dữ liệu thu thập là chìa khóa để ước tính tiềm năng dầu khí. Các quy tắc chung của các chuyên gia ngón cái sử dụng cho tính toán độ xốp, rỗng là nó là một chức năng luật số mũ của chiều sâu: Độ xốp =   DepthxxxF meK .,,, 21.  (4) Một số yếu tố như các loại đá, cấu trúc, và xây bă ̀ng xi măng như các thông số của F chức năng bối rối mối quan hệ này. Điều này đòi định nghĩa của ngữ cảnh thích hợp, trong đó cố gắng khám phá ra công thức đo độ xốp. Bối cảnh địa chất được thể hiện trong điều khoản của hiện tượng địa chất, như là hình học, lithology, nén chặt, và lún, liên kết với khu vực. Nó nổi tiếng rằng những thay đổi bối cảnh địa chất từ lưu vực để lưu vực (các khu vực địa lý khác nhau trên thế giới) và cũng từ khu vực tới khu vực trong một lưu vực [Allen và Allen 1990; Biswas 1995]. Hơn nữa, tính năng tiềm ẩn trong bối cảnh có thể khác nhau rất nhiều. Mô hình kết hợp các kỹ thuật đơn giản, mà làm việc trong lĩnh vực kỹ thuật mà là hạn chế bởi hành vi của con người gây ra hệ thống và cũng thành lập luật của vật lý, không thể áp dụng trong lĩnh vực thăm dò dầu khí. Đến địa chỉ này, phân nhóm dữ liệu đã được sử dụng để xác định ngữ cảnh có liên quan, và sau đó phát hiện ra phương trình được thực hiện trong bối cảnh mỗi. Mục đích là để lấy các tập con x1, x2, ..., xm từ một tập lớn các tính năng địa chất, và F mối quan hệ chức năng nhất định chức năng đo độ rỗng, xốp trong khu vực. Các phương pháp tổng thể minh hoạ trong Hình 35, bao gồm hai bước chính: (i) Bối cảnh định nghĩa bằng cách sử dụng các kỹ thuật Phân cụm không giám sát, và (ii) phát hiện bằng cách phân tích Phương trình hồi quy [Li và Biswas 1995]. Bất thăm dò dữ liệu thu thập từ một vùng ở lưu vực Alaska được phân tích bằng cách sử dụng phương pháp phát triển. Các đối tượng dữ liệu (mẫu) được mô tả về 37 đặc điểm địa chất, như độ xốp, tính thấm, mật độ kích thước hạt, và phân loại, số lượng các mảnh khoáng sản khác nhau (ví dụ, thạch anh, Chert, fenspat) hiện nay, tính chất của các mảnh -86- đá , lỗ chân lông đặc điểm, và xây bă ̀ng xi măng. Tất cả những tính năng các giá trị được đo bằng số được thực hiện trên mẫu được lấy từ các bản ghi tốt trong quá trình khoan thăm dò. Thuật toán phân cụm dữ liệu K-means đã được sử dụng để xác định một tập các đồng nhất cấu trúc địa chất nguyên thủy (g1, g2, ..., gm). Những nguyên thủy này sau đó đã được ánh xạ vào mã đơn vị so với bản đồ đơn vị địa tầng học. Hình 36 mô tả một bản đồ một phần cho một tập hợp các giếng và bốn cấu trúc nguyên thủy. Bước tiếp theo trong quá trình phát hiện được xác định phần của khu vực giếng được tạo thành từ cùng một trình tự của địa chất nguyên thủy. Mỗi trình tự quy định một Ci ngữ cảnh. Từ một phần của bản đồ Hình 36, trong bối cảnh C1 = g2 . g1 . g2 . g3 đã được xác định tại hai khu vực tốt (của 300 và 600 series). Sau khi bối cảnh đã được xác định, dữ liệu điểm thuộc bối cảnh từng được nhóm lại với nhau cho derivation phương trình. Thủ tục dẫn xuất derivation làm việc phân tích hồi qui [Sen và Srivastava 1990]. Phương pháp này được áp dụng cho một tập dữ liệu của khoảng 2.600 đối tượng tương ứng với mẫu đo thu thập từ giếng là các lưu vực Alaska. K-means đã nhóm dữ liệu này đặt thành bảy nhóm. Như minh hoạ, Chúng ta chọn một bộ 138 đối tượng đại diện cho một bối cảnh để phân tích. Các tính năng nhất định nghĩa cụm này đã được lựa chọn, và các chuyên gia surmised rằng bối cảnh đại diện cho một vùng độ xốp rỗng thấp, được mô hình bằng cách sử dụng các thủ tục hồi qui. 4.4 Tóm tắt Có rất nhiều ứng dụng, nơi ra quyết định và phân tích mẫu thăm dò đã được thực hiện trên dữ liệu lớn đặt ra. Ví dụ, trong lấy tài liệu, một tập hợp các tài liệu có liên quan có thể tìm thấy một vài trong số hàng triệu tài liệu của các chiều của hơn 1000. Có thể xử lý những vấn đề này rất hữu ích nếu một số trừu tượng của dữ liệu được thu được và được sử dụng trong việc ra quyết định, hơn là trực tiếp bằng cách sử dụng dữ liệu toàn bộ thiết lập. Bởi trừu tượng hóa dữ liệu, chúng tôi có nghĩa là một đại diện đơn giản và gọn nhẹ của dữ liệu. Đơn giản này giúp máy chế biến có hiệu quả hay một con người trong comprehending cấu trúc trong dữ liệu một cách dễ dàng. Thuật toán phân cụm dữ liệu rất lý tưởng cho việc đạt được các dữ liệu trừu tượng. -87- Trong bài này, chúng ta đã kiểm tra các bước khác nhau trong phân nhóm: (1) mô hình đại diện, (2) tính toán tương tự, (3) nhóm quy trình, và (4) đại diện cụm. Ngoài ra, cũng đề cập đếnận thống kê, mờ, thần kinh, tiến hóa, và kiến thức dựa trên phương pháp tiếp cận để phân cụm dữ liệu. Chúng ta có bốn mô tả các ứng dụng của phân nhóm: (1) Phân đoạn ảnh, (2) nhận diện đối tượng, (3) truy hồi tài liệu, và (4) khai phá dữ liệu. Hình 36. Mã vùng so với bản đồ đơn vị địa tầng một phần của khu vực nghiên cứu. Phân cụm dữ liệu là một quá trình của các nhóm dữ liệu dựa trên một thước đo tương tự. Phân cụm dữ liệu là một quá trình chủ quan; cùng một bộ các dữ liệu thường xuyên cần phải được phân vùng khác nhau cho các ứng dụng khác nhau. Chủ quan này làm cho quá trình phân nhóm khó khăn. Điều này là do một thuật toán đơn hoặc phương pháp tiếp cận là không đủ để giải quyết mọi vấn đề phân cụm dữ liệu. Một giải pháp có thể nằm trong chủ quan này phản ánh trong các hình thức kiến thức. Kiến thức này được sử dụng hoặc ngầm hoặc rõ ràng trong một hoặc nhiều giai đoạn của Phân cụm dữ liệu. Kiến thức dựa trên thuật toán phân nhóm sử dụng kiến thức một cách rõ ràng. Bước khó khăn nhất trong phân nhóm là tính năng khai thác hoặc mẫu đại diện. Các nhà nghiên cứu mẫu nhận diện công nhận thuận tiện tránh bước -88- này bằng cách giả sử rằng các đại diện được khuôn mẫu có sẵn như là đầu vào của thuật toán phân cụm dữ liệu. Kích thước nhỏ, tập hợp dữ liệu, đại diện mô hình có thể thu được dựa trên kinh nghiệm trước đây của người dùng với vấn đề này. Tuy nhiên, trong trường hợp các bộ dữ liệu lớn, đó là khó khăn cho người sử dụng để theo dõi sự quan trọng của mỗi tính năng trong phân cụm dữ liệ. Một giải pháp là làm cho các phép đo như nhiều trên các mẫu càng tốt và sử dụng chúng trong khuôn mẫu đại diện. Nhưng nó không thể sử dụng một bộ sưu tập lớn các phép đo trực tiếp trong phân cụm dữ liệu vì chi phí tính toán. Vì vậy, một số tính năng khai thác / lựa chọn phương pháp tiếp cận đã được thiết kế để có được kết hợp tuyến tính hoặc phi tuyến của các phép đo có thể được dùng để đại diện cho các mẫu. Hầu hết các đề án đề nghị cho khai thác tính năng / lựa chọn thường được lập lại trong tự nhiên và không thể được sử dụng trên các tập dữ liệu lớn do chi phí tính toán. Bước thứ hai trong phân nhóm là giống nhau tính toán. Một loạt các đề án đã được sử dụng để tính toán giống nhau giữa hai mô hình. Họ sử dụng kiến thức hoặc ngầm hoặc rõ ràng. Hầu hết các kiến thức dựa trên thuật toán phân nhóm sử dụng kiến thức rõ ràng trong tính toán tương tự. Tuy nhiên, nếu không phải là đại diện cho các mẫu bằng cách sử dụng các tính năng phù hợp, sau đó nó không phải là có thể làm cho một phân vùng có ý nghĩa không phân biệt chất lượng và số lượng kiến thức được sử dụng trong tính toán tương tự. Không có đề án phổ chấp nhận được đối với máy tính giống nhau giữa các mẫu đại diện bằng cách sử dụng một hỗn hợp của cả hai tính năng định lượng. Không giô ́ng nhau giữa một cặp mẫu được đại diện bằng cách sử dụng một thước đo khoảng cách đó có thể hoặc không thể có một số liệu. Bước tiếp theo trong phân nhóm là nhóm các bước lại với nhau. Có hai nhóm đề án rộng rãi: đề án theo kế thừa và phân vùng. Các đề án có nhiều thứ bậc linh hoạt, và các đề án phân vùng ít tốn kém. Các thuật toán phân vùng nhằm tối đa hóa khả năng lôi tiêu chí bình phương. Thúc đẩy bởi sự thất bại của các lỗi bình phương thuật toán phân cụm dữ liệu phân vùng trong việc tìm kiếm các giải pháp tối ưu cho vấn đề này, một bộ sưu tập lớn các phương pháp đã được đề xuất và được sử dụng để có được một giải pháp toàn cầu tối ưu cho vấn đề này. Tuy nhiên, các đề án được giới hạn cho phép về mặt tính toán trên dữ liệu lớn đặt ra. Đề án phân cụm dữ liệu dựa trên mạng -89- nowrron(ANN) được triển khai thần kinh của các thuật toán phân nhóm, và họ chia sẻ các tài sản không mong muốn của các thuật toán. Tuy nhiên, ANNs có khả năng tự động bình thường hóa dữ liệu và trích xuất các tính năng. Một quan sát quan trọng là ngay cả khi một đề án có thể tìm thấy giải pháp tối ưu cho vấn đề phân vùng bình phương lỗi, nó vẫn có thể thu ngắn của các yêu cầu vì không thể-đẳng hướng bản chất của các cụm. Trong một số ứng dụng, ví dụ trong truy hồi tài liệu, nó có thể hữu ích để có một phân nhóm đó không phải là một phân vùng. Điều này có nghĩa là các cụm chồng chéo. Phân cụm dữ liệu mờ Fuzzy là chức năng rất lý tưởng cho mục đích này. Ngoài ra, các thuật toán phân nhóm mờ có thể xử lý dữ liệu hỗn hợp các loại. Tuy nhiên, một vấn đề lớn với phân cụm dữ liệu mờ là nó rất khó để có được các giá trị thành viên. Một cách tiếp cận tổng hợp có thể không làm việc vì bản chất chủ quan của phân cụm dữ liệu. Nó là cần thiết để đại diện cho các cụm thu được trong một hình thức thích hợp để giúp nhà sản xuất quyết định. Kiến thức dựa trên phân nhóm đề án tạo ra các mô tả bằng trực giác hấp dẫn của các cụm. Họ có thể được sử dụng ngay cả khi các mô hình được đại diện bằng cách sử dụng một sự kết hợp các đặc tính và định lượng, miễn là kiến thức liên kết một khái niệm và các tính năng hỗn hợp có sẵn. Tuy nhiên, việc triển khai các đề án về khái niệm phân cụm dữ liệu có ước tính rất đắt tiền và không phù hợp cho nhóm tập hợp dữ liệu lớn. Thuật toán K-means và giải thuật dựa trên mạng nowrron thần kinh của , lưới Kohonen, là thành công nhất được sử dụng trên bộ dữ liệu lớn. Điều này là do là thuật toán K-means đơn giản để thực hiện và ước tính hấp dẫn vì thời gian tuyến tính phức tạp của nó. Tuy nhiên, nó không khả thi để sử dụng ngay cả thuật toán này thời gian tuyến tính trên dữ liệu lớn đặt ra. Thuật toán gia tăng như lãnh đạo và thực hiện thần kinh của nó, mạng Art, có thể được sử dụng để cụm tập dữ liệu lớn. Nhưng họ có xu hướng tự phụ thuộc. Phân chia và chinh phục là một heuristic mà đã được khai thác theo đúng thiết kế thuật toán máy tính để giảm chi phí tính toán. Tuy nhiên, cần khôn ngoan sử dụng trong các phân nhóm để đạt được kết quả có ý nghĩa. Tóm lại, Phân cụm dữ liệu là một vấn đề thú vị, hữu ích, và đầy thách thức. Nó có tiềm năng lớn trong các ứng dụng như nhận điện đối tượng, phân đoạn hình ảnh, và các chọn lọc và truy hồi thông tin. Tuy nhiên cần cẩn thận thiết kế một vài lựa chọn có thể để khai thác tiềm năng này. -90- KẾT LUẬN Các vấn đề đƣợc tìm hiểu trong luận văn Tổng hợp, nghiên cứu những nét cơ bản lý thuyết và ứng dụng thực tiễn của Phân cụm dữ liệu. Với sự phát triển ngày càng lớn như vũ bão của Công nghệ thông tin và sự to ra về Cơ sở dữ liệu thông tin. Do đó yêu cầu về nghiên cứu hoàn thiện, áp dụng phương pháp, kỹ thuật Phân cụm dữ liệu là rất cần thiết và có ý nghĩa to lớn Trong chương 1, luận văn trình bày tổng quan, lý thuyết về phân cụm dữ liệu, và một số lý thuyết liên quan trực tiếp đến khai phá dữ liệu. Chương 2, giới thiệu tổng quát các thuật toán phân cụm dữ liệu, thuật toán phân cụm dữ liệu là rất nhiều, Luận văn chỉ đề cập một số thuật toán phổ biến, thông dụng. Chương 3 là nói về một số ứng dụng tiêu biểu của phân cụm dữ liệu như Phân đoạn ảnh, Nhận diện ký tự và đối tượng, Truy hồi thông tin, và Khai phá dữ liệu. HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI Phân cụm dữ liệu và ứng dụng của Phân cụm dữ liệu là hướng nghiên cứu cần thiết, quan trọng, Tuy nhiên đây cũng là mảng rất rộng, bao hàm nhiều phương pháp, kỹ thuật, và hình thành nhiều nhóm khác nhau. Trong quá trình nghiên cứu, thực hiện luận văn mặc dù đã cố gắng tập trung nghiên cứu và tham khảo nhiều tài liệu, bài báo, tạp chí khoa học trong và ngoài nước, nhưng do trình độ còn có nhiều giới hạn không thể tránh khỏi thiếu sót và hạn chế. Em rất mong được sự chỉ bảo đóng góp nhiều hơn nữa của các thày, cô giáo, các nhà khoa học… HƢỚNG NGHIÊN CỨU PHÁT TRIỂN - Tiếp tục nghiên cứu thêm về lý thuyết về phân cụm dữ liệu - Xây dựng, phát triển thêm các kỹ thuật, ứng dụng của Phân cụm dữ liệu. -91- PHỤ LỤC : XÂY DỰNG CHƢƠNG TRÌNH “PHÂN CỤM DỮ LIỆU VỚI THUẬN TOÁN K-MEANS BẰNG NGÔN NGỮ VISUAL BASIC 6.0” Giao diện chương trình : -92- * Người sử dụng chọn số lượng cụm dữ liệu, sau đó click ngẫu nhiên vào khung( nhập dữ liệu X, Y). Chương trình tạo cụm trên cơ sở tối giản bình phương khoảng cách giữa dữ liệu và cụm trọng tâm tương ứng, mỗi điểm biểu thị cho một đối tượng và tọa độ (X, Y) mô tả hai thuộc tính của đối tượng. Màu sắc của điểm và số nhãn biểu thị cho cụm dữ liệu * Thuật toán phân cụm K-Means làm việc như sau : Nếu số lượng dữ liệu nhỏ hơn số cụm thì ta gán mỗi dữ liệu là một trọng tâm của cụm. Mỗi trọng tâm sẽ có một số cụm. Nếu số lượng lớn dữ liệu lớn hơn số cụm, với mỗi dữ liệu, ta tính toán khoảng cách tới tất cả các trọng tâm và lấy khoảng cách tối thiểu. Dữ liệu này được nói là thuộc về cụm có khoảng cách tối thiểu tới dữ liệu này. Khi chúng ta không chắc chắn về vị trị của trọng tâm, ta cần điều chỉnh vị trí trọng tâm dựa vào dữ liệu đã cập nhật hiện tại. Sau đó, ta gán tất cả dữ liệu tới trọng tâm mới này. Quá trình này được lặp lại cho tới khi không còn dữ liệu di chuyển sang cụm khác. Về mặt toán học, vòng lặp này có thể chứng minh là hội tụ. -93- Ví dụ sau khi chạy chương trình với số cụm = 9 -94- Mã nguồn chƣơng trình Option Explicit Private Data() ' Row 0 = cluster, 1 =X, 2= Y; Sè l•îng d÷ liÖu trong c¸c cét Private Centroid() As Single ' côm trung t©m (X vµ Y) cña c¸c côm; Sè l•îng côm = Sè l•îng cét Private totalData As Integer ' Tæng sè d÷ liÖu (tæng sè cét) Private numCluster As Integer ' Tæng sè c¸c côm ############################################################## ' C¸c form ®iÒu khiÓn ' + Form_Load ' + cmdReset_Click ' + txtNumCluster_Change ' + Picture1_MouseDown ' + Picture1_MouseMove ' ############################################################## Private Sub Form_Load() Dim i As Integer Picture1.BackColor = &HFFFFFF ' ®Æt mÇu = tr¾ng Picture1.DrawWidth = 10 ' §é lín cña ®iÓm Picture1.ScaleMode = 3 ' pixels '§•a ra sè l•îng cña côm numCluster = Int(txtNumCluster) ReDim Centroid(1 To 2, 1 To numCluster) For i = 0 To numCluster - 1 'T¹o nh·n If i > 0 Then Load lblCentroid(i) lblCentroid(i).Caption = i + 1 lblCentroid(i).Visible = False Next i End Sub Private Sub cmdReset_Click() ' refress l¹i d÷ liÖu Dim i As Integer Picture1.Cls ' Lµm s¹ch ¶nh -95- Erase Data ' Xãa d÷ liÖu totalData = 0 For i = 0 To numCluster - 1 lblCentroid(i).Visible = False ' Kh«ng hiÖn nh·n Next i 'Cho phÐp thay ®æi sè l•îng côm txtNumCluster.Enabled = True End Sub Private Sub txtNumCluster_Change() 'Thay ®æi sè l•îng côm vµ reset l¹i d÷ liÖu Dim i As Integer For i = 1 To numCluster - 1 Unload lblCentroid(i) Next i numCluster = Int(txtNumCluster) ReDim Centroid(1 To 2, 1 To numCluster) 'Gäi sù kiÖn cmdReset_Click For i = 0 To numCluster - 1 If i > 0 Then Load lblCentroid(i) lblCentroid(i).Caption = i + 1 lblCentroid(i).Visible = False Next i End Sub Private Sub Picture1_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single) 'Thu thËp d÷ liÖu vµ tr×nh diÔn kÕt qu¶ Dim colorCluster As Integer Dim i As Integer 'V« hiÖu kh¶ n¨ng cã thÓ thay ®æi sè l•îng côm txtNumCluster.Enabled = False ' T¹o d÷ liÖu chøc n¨ng totalData = totalData + 1 ReDim Preserve Data(0 To 2, 1 To totalData) ' Chó ý : B¾t ®Çu víi 0 cho dßng Data(1, totalData) = X Data(2, totalData) = Y -96- 'Thùc hiÖn k-mean clustering Call kMeanCluster(Data, numCluster) 'Tr×nh diÔn kÕt qu¶ Picture1.Cls For i = 1 To totalData colorCluster = Data(0, i) - 1 If colorCluster = 7 Then colorCluster = 12 ' NÕu mÇu tr¾ng (NÕu gièng mÇu nÒn th× thay ®æi thµnh mµu kh¸c) X = Data(1, i) Y = Data(2, i) Picture1.PSet (X, Y), QBColor(colorCluster) Next i 'HiÖn thÞ côm trung t©m For i = 1 To min2(numCluster, totalData) lblCentroid(i - 1).Left = Centroid(1, i) lblCentroid(i - 1).Top = Centroid(2, i) lblCentroid(i - 1).Visible = True Next i End Sub Private Sub Picture1_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single) lblXYValue.Caption = X & "," & Y End Sub ' ############################################################## ' FUNCTIONS ' + kMeanCluster: ' + dist: Kho¶ng c¸ch tÝnh to¸n ' + min2: Trë l¹i gi¸ trÞ nhá nhÊt gi÷a hai sè ' ############################################################## Sub kMeanCluster(Data() As Variant, numCluster As Integer) ' Hµm chÝnh ®Ó ph©n côm d÷ liÖu thµnh k côm ' input: + Ma trËn d÷ liÖu (0 tíi 2, 1 tíi TotalData); Row 0 = cluster, 1 =X, 2= Y; D÷ liÖu trong c¸c cét ' + numCluster: Sè l•îng côm ng•êi dïng muèn d÷ liÖu ®•îc ph©n côm ' + C¸c biÕn ®Þa ph•¬ng: Centroid, TotalData ' ouput: o) Côm trung t©m ®· ®•îc cËp nhËt ' o) G¸n sè l•îng c¸c côm vµo d÷ liÖu (= row 0 of Data) Dim i As Integer -97- Dim j As Integer Dim X As Single Dim Y As Single Dim min As Single Dim cluster As Integer Dim d As Single Dim sumXY() Dim isStillMoving As Boolean isStillMoving = True If totalData <= numCluster Then Data(0, totalData) = totalData Centroid(1, totalData) = Data(1, totalData) ' X Centroid(2, totalData) = Data(2, totalData) ' Y Else 'TÝnh to¸n kho¶ng c¸ch tèi thiÓu ®Ó g¸n d÷ liÖu míi min = 10 ^ 10 'Sè lín X = Data(1, totalData) Y = Data(2, totalData) For i = 1 To numCluster d = dist(X, Y, Centroid(1, i), Centroid(2, i)) If d < min Then min = d cluster = i End If Next i Data(0, totalData) = cluster Do While isStillMoving ' Vßng lÆp nµy ch¾c ch¾n héi tô 'TÝnh to¸n c¸c träng t©m míi ReDim sumXY(1 To 3, 1 To numCluster) ' 1 =X, 2=Y, 3= §Õm sè l•îng d÷ liÖu For i = 1 To totalData sumXY(1, Data(0, i)) = Data(1, i) + sumXY(1, Data(0, i)) sumXY(2, Data(0, i)) = Data(2, i) + sumXY(2, Data(0, i)) sumXY(3, Data(0, i)) = 1 + sumXY(3, Data(0, i)) Next i For i = 1 To numCluster Centroid(1, i) = sumXY(1, i) / sumXY(3, i) Centroid(2, i) = sumXY(2, i) / sumXY(3, i) Next i 'G¸n tÊt c¶ d÷ liÖu tíi c¸c träng t©m míi isStillMoving = False For i = 1 To totalData -98- min = 10 ^ 10 'Sè lín X = Data(1, i) Y = Data(2, i) For j = 1 To numCluster d = dist(X, Y, Centroid(1, j), Centroid(2, j)) If d < min Then min = d cluster = j End If Next j If Data(0, i) cluster Then Data(0, i) = cluster isStillMoving = True End If Next i Loop End If End Sub Function dist(X1 As Single, Y1 As Single, X2 As Single, Y2 As Single) As Single ' TÝnh to¸n kho¶ng c¸ch Euclidean dist = Sqr((Y2 - Y1) ^ 2 + (X2 - X1) ^ 2) End Function Private Function min2(num1, num2) ' Trë vÒ gi¸ trÞ nhá nhÊt gi÷a hai sè If num1 < num2 Then min2 = num1 Else min2 = num2 End If End Function -99- TÀI LIỆU THAM KHẢO [1]. M.R Anderber, Cluster analysis of application, A cademic Press, New York, 1973 [2]. B.S. Everitt, Cluster Analysis, Edward Amold coblished by Haisted Press and imprint of john Wiley & Sons Inc., 3rd edition, 1993 [3]. D.Fisher, Knowledged acquisition via incremental conceptual clustering, in Machine Learing [4] Zou, H., T. Hastie, and R. Tibshirani: Sparse principal component analysis. Journal of Computational and Graphical Statistics, 15(2):265{286, 2006. [5] Hall, P., H.G. Muller, and J.L. Wang: Properties of principal component methods for functional and longitudinal data analysis. Ann. Statist, 34(3):1493{1517, 2006. [6] Yao, F., H.G. Muller, A.J. Cli_ord, S.R. Dueker, J. Follett, Y. Lin, B.A. Buchholz, and J.S. Vogel: Shrinkage Estimation for Functional Principal Component Scores with Application to the Population Kinetics of Plasma Folate. Biometrics, 59:676{ 685, 2003. [7] Liang, K.Y. and S.L. Zeger: Longitudinal data analysis using generalized linear models. Biometrika, 73(1):13{22, 1986. [8] Maaten, L. J. P. van der, E. O. Postma, and H. J. van den Herik: Dimensionality reduction: A comparative review. 2007. Preprint published online. [9] Fan, J. and I. Gijbels: Variable Bandwidth and Local Linear Regression Smoothers. The Annals of Statistics, 20(4):2008{2036, 1992. [10] Data Clustering Theory, Algorithms, and Applications. Guojun Gan, Chaoqun Ma, Jianhong Wu. 2007