Phân cụm trực quan tập các bài báo khoa học theo mô hình nguyên tử trong không gian ba chiều

Nội dung text: Phân cụm trực quan tập các bài báo khoa học theo mô hình nguyên tử trong không gian ba chiều

1. 1 PHÂN CỤM TRỰC QUAN TẬP CÁC BÀI BÁO KHOA HỌC THEO MÔ HÌNH NGUYÊN TỬ TRONG KHÔNG GIAN BA CHIỀU Visually clustering research papers using an atom model in 3D space Nghị Vĩnh Khanh1 Tóm tắt Abstract Bài báo này đề xuất một cách tiếp cận mới để This paper proposes a new approach to xây dựng một hệ thống phân cụm trực quan bằng construct a visually clustering system with 3D hình ảnh 3D cho việc phân nhóm các bài báo khoa image for scientific papers by using two combined học bằng cách sử dụng kết hợp hai kỹ thuật trong techniques in the field of artificial intelligence, lĩnh vực trí tuệ nhân tạo là SOM và k-means. Cụ which are SOM and k -means. Specifically, the thể, SOM sẽ đóng vai trò cho việc cung cấp một SOM will play an important role in providing a hình ảnh trực quan để quyết định tham số K cho visual image in order to determine parameter K thuật toán k-means tiếp theo. Một thiết kế đồ thị sẽ for k-means algorithm in the next step. A graph thể hiện các cụm mà mỗi cụm được đại diện bởi layout is designed to show the clusters, each of một hạt nhân (tâm của cụm) và các điện tử (các which is represented by an atomic nucleus (the bài báo) bao quanh. Các điện tử sẽ quay quanh hạt center of cluster) and electron (the papers) around. nhân bằng các lực hấp dẫn. Bên cạnh đó, chúng tôi The electron will orbit the nucleus by the force of sử dụng kỹ thuật ArcBall trong lĩnh vực đồ họa máy gravity. In addition, ArcBall techniques (in 3D tính ba chiều để hỗ trợ sự tương tác người dùng. computer graphics field) are used to support user Dựa trên hệ thống này, người dùng có thể thực interaction. Based on this system, users are able to hiện đánh giá sự thống nhất về cấu trúc cụm theo evaluate the unification of Cluster’s structure in a cách đơn giản hơn các phương pháp trước đây. simpler way than in the previous ones. Từ khóa: phân cụm, trực quan hóa, trí tuệ nhân Key words: clustering, visualization, artificial tạo, đồ họa ba chiều, tương tác người dùng. intelligence, 3D computer graphic, user interaction. 1. Giới thiệu 1 Trong bài báo này, chúng tôi đề xuất một thiết kế đồ họa trực quan ba chiều gọi là mô hình Sự phân cụm là một trong những kỹ thuật rất cấu trúc nguyên tử cho việc phân cụm dữ liệu. Mô cần thiết cho việc khám phá tri thức nhân loại. Nó hình này sử dụng giải thuật SOM để ước lượng giúp cho chúng ta tách các nhóm đối tượng từ tập số các cụm cần được tách ra từ tập các tài liệu nói dữ liệu dựa trên các đặc tính tương đồng trong chung và các bài báo khoa học nói riêng (được viết nhóm. Ngày nay, các kỹ thuật phân cụm được sử bằng tiếng Anh) có định dạng PDF. Sau đó, dựa dụng rộng rãi trong các ứng dụng như khai phá dữ trên mô hình không gian vector, cụ thể là vector liệu, xử lý ảnh, nhận dạng mẫu, thống kê, tin sinh tf-idf, chúng tôi sử dụng thuật toán k-means để học và các lĩnh vực khác. Bên cạnh đó, áp dụng các tách tập dữ liệu thành k nhóm. Cuối cùng các kỹ thuật trực quan trong việc phân tích cụm dữ liệu cụm sẽ được trực quan hóa thành dạng các cấu rất quan trọng trong việc thể hiện xu hướng của trúc nguyên tử trong không gian ba chiều. Để đơn các tập dữ liệu, nó cho chúng ta cái nhìn tổng quan giản, chúng tôi tổ chức một nguyên tử có tối đa cũng như sự hiểu biết chi tiết về tập dữ liệu. Hiện năm mức năng lượng được tính bằng độ tương nay, nhiều nghiên cứu đã và đang tập trung về vấn đồng Cosin giữa các vector điện tử và hạt nhân. đề phân tích trực quan các cụm rất thành công như Cách tiếp cận của bài báo này sẽ giải quyết Grand Tour, OPTICS, HD-EYE, H-BLOB, Star được các vấn đề sau: Coordinate (Ankerst, Mihael; Grinstein, Georges; Keim, Daniel;, 2002), SOM-based techniques - Thứ nhất, hiển thị được tập các vector nhiều (Kohoren, 1997), HOV3 (Zhang, Ke-Bing; Orgun, chiều (lớn hơn 1000) trong không gian ba chiều, trong đó thể hiện rõ sự phân phối dữ liệu, mối quan Mehmet A; Zhang, Kang;, 2006). hệ giữa mỗi tâm của các cụm cũng như giữa các 1 Thạc sĩ, Ban Phát triển Hệ thống CNTT, Trường ĐH Trà Vinh bài báo khoa học với nhau. Soá 16, thaùng 12/2014 1
2. 2 - Thứ hai, phương pháp tiếp cận của chúng tôi Trong thập niên qua, nhiều kỹ thuật phân tích tránh được lựa chọn tùy ý các cụm k bởi sự kết hợp cụm trực quan đã được phát triển, chẳng hạn của SOM và K-means. Do đó, mô hình này cung như Grand Tour, OPTICS, HD-EYE, H-BLOB, cấp cho người dùng một phương pháp trực quan có Fastmap, Star Coordinate, SOM-based techniques, mục đích và có hiệu quả vào việc phân tích cluster. HOV3, Nhìn chung, các kỹ thuật này góp phần quan trọng trong việc phân tích các cụm và có thể - Thứ ba, có thể vượt qua giới hạn của không giải quyết được các khía cạnh quan trọng của việc gian khi so sánh với các phương pháp 2D trước nhận thức trực quan: đó bằng cách sử dụng kỹ thuật arcball để tương tác. Nó tạo cho chúng ta cảm giác nhập vai vào hệ - Trực quan các dữ liệu lớn và đa chiều; thống và thao tác từng đối tượng giống như chơi - Cung cấp một cái nhìn tổng quan rõ ràng và game 3D hay sử dụng các hệ thống thực tế ảo - ví chi tiết về cấu trúc cụm; dụ CAVE (Cruz-Neira C; Sandin D.; DeFanti T.; Kenyon R.; Hart J.;, 1992). - Có độ phức tạp tính toán tuyến tính trên việc ánh xạ dữ liệu từ không gian chiều cao sang chiều Trong các phần sau, chúng tôi tổ chức cấu trúc không gian thấp hơn; bài báo như sau: phần 2 - tổng quan các kết quả nghiên cứu trước đây, phần 3 - phương pháp thực - Hỗ trợ tương tác động với các đại diện trực hiện, phần 4 - đánh giá kết quả và phần 5 - kết luận. quan của cụm; 2. Tổng quan các kết quả nghiên cứu trước đây - Kết nối kiến thức liên quan của các chuyên gia vào lĩnh vực thăm dò vào cụm; Để xây dựng được bộ công cụ phân tích các cụm trực quan, nhiều kỹ thuật đã được nghiên - Cho người dùng các chỉ dẫn có mục đích và cứu cho các quá trình biểu thị trực quan các đối chính xác của việc khảo sát/điều tra các cụm cũng tượng từ một tập dữ liệu lên màn hình máy tính. như hợp lệ hóa các cụm chứ không phải chỉ đơn Point-based techniques, line-based technique, giản là thăm dò cụm ngẫu nhiên. region-based technique, hierarchical techniques Hầu hết các kỹ thuật trên giải quyết được các (Ward, Matthew; Grinstein, Georges; Keim, yêu cầu này nhưng chúng vẫn còn hạn chế khi kích Daniel;, 2010) là những kỹ thuật phổ biến dùng thước và chiều của tập dữ liệu khá lớn. Hơn nữa, để trực quan hóa các tập dữ liệu nhiều chiều. Tuy một vài kỹ thuật trên gặp khó khăn khi cung cấp nhiên, hầu hết chúng đều gặp khó khăn khi trực một cái nhìn tổng quan sáng sủa của cấu trúc của quan các tập dữ liệu khá lớn cũng như dữ liệu cụm cũng như mức độ dễ sử dụng dành cho các có chiều của vector rất cao. Một vài kỹ thuật bị người dùng. giới hạn trong việc cung cấp một sự nhận thức 3. Phương pháp thực hiện rõ ràng từ các dạng trực quan cho người dùng. Như đã giới thiệu, để giải quyết các hạn chế trên, chúng tôi đề xuất giải pháp trực quan bằng một thiết kế đồ thị trực quan ba chiều có hỗ trợ tương tác dựa theo cấu trúc nguyên tử. Các bước thực hiện như sau: Hình 1. Quá trình trực quan thông tin (Ware, 2004) Soá 16, thaùng 12/2014 2
3. 3 Hình 2. Quy trình xây dựng hệ thống Bước tiền xử lý: Frequency (TFIDF) (Manning, Christopher D.; Raghavan, Prabhakar; Schutze, Hinrich;, 2009) Sau khi tách các ký tự từ file định dạng PDF, nhiệm vụ tiếp theo là chế biến từ vựng. Về cơ bản, chúng ta cần ba hoạt động: loại bỏ các từ vô nghĩa hoặc từ không mang thông tin trong ngữ cảnh cần xem xét (stop-word), chuyển các từ về dạng gốc (steamming), và tính trọng số của từng từ so với Trong đó: tf(w): term frequency (số lần từ w các từ khác (term weighting). này xuất hiện trong một tài liệu), df(w): document frequency (số lượng tài liệu chứa đựng từ w này), Các bước loại bỏ “Stop Words” và “Steamming” N: Tổng số tài liệu. sẽ giúp chúng ta giảm kích thước của tập từ vựng, do đó sẽ tiết kiệm được nguồn tài nguyên tính toán. Đại lượng tfidf(w) nói lên sự quan trọng của từ Bởi vì tập các bài báo khoa học đầu vào được viết w trong tài liệu. Từ công thức này, chúng ta tiến bằng tiếng Anh nên nó không khó để áp dụng giải hành tính giá trị của ma trận TFIDF. Trong đó, mỗi thuật tìm gốc từ; cụ thể giải thuật Porter stemming hàng là đại diện một tài liệu, các cột là giá trị tfidf (Porter, 1980) hiện được sử dụng rất hiệu quả cho của các từ trong tập Bag-Of-Words. một số ngôn ngữ như tiếng Anh mặc dù chưa hỗ Bởi vì kích thước của ma trận TFIDF có thể trợ được nhiều ngôn ngữ trên thế giới. Chúng ta sẽ rất lớn (bằng M tài liệu x N term trong Bag-Of- thật sự gặp khó khăn nếu tập các bài báo được viết Words). Thực tế, nếu ta có một tập gồm 100 bài báo bằng tiếng Việt vì cần có nhiều nghiên cứu chuyên khoa học của cùng một lĩnh vực nghiên cứu và mỗi sâu về ngôn ngữ tự nhiên của tiếng Việt để tìm bài báo khoảng 10 trang thì ma trận TFIDF có thể được từ gốc của chúng. có kích thước là 100x10000. Cần chú ý rằng nếu Kết quả sau khi loại bỏ “Stop Words” và ta chỉ dùng các keyword hay chỉ xác định Bag-Of- “Steamming” của tất cả các từ vựng trong tất cả Words từ trong phần Abstract của bài báo (nhằm các văn bản, ta sẽ xác định được một tập hợp duy rút gọn kích thước ma trận này) thì về mặt thống nhất các từ vựng, gọi là Bag-Of-Word. Tiếp theo, kê cũng như ngữ nghĩa sẽ đem lại một kết quả chúng ta sẽ tính trọng số của các từ này (term không chính xác cho sự khác biệt nội dung giữa weighting). Để xác định trọng số của mỗi từ vựng, các bài báo. Có nhiều phương pháp được dùng cho chúng tôi sử dụng một công thức rất phổ biến để việc giảm kích thước của ma trận TFIDF, trong đó tính đại lượng Term Frequency Invert Document kỹ thuật Latent semantic indexing analysis - LSI Soá 16, thaùng 12/2014 3
4. 4 (Manning, Christopher D.; Raghavan, Prabhakar; hợp ta có 6 văn bản (d1, d2, d3, d4, d5, d6) với Bag- Schutze, Hinrich;, 2009) được sử dụng khá phổ Of-Words có chiều là 5 (ship, boat, ocean, voyage, biến. Nó là một kỹ thuật thống kê nhằm cố gắn trip). Sau khi sử dụng kỹ thuật LSI để giảm chiều từ ước lượng cấu trúc nội dung được ẩn bên trong văn 5 thành 2 thì các chiều mới là “1” và “2” sẽ không bản bằng cách sử dụng kỹ thuật đại số tuyến tính còn mang ý nghĩa tương ứng của “ship”, “boat”, Singular-Value-Decomposition. “ocean”, “voyage”, “trip”. Điều đó có nghĩa là chúng ta không thể thực thi truy vấn để tìm thuộc tính ban LSI rất hiệu quả trong việc giảm chiều của tập đầu, ví dụ từ “ship” trong ma trận đã giảm chiều. dữ liệu. Tuy nhiên, việc sử dụng kỹ thuật này sẽ gặp Thực tế, thì đã có nhiều nghiên cứu để giải quyết trở ngại khi ta muốn thực hiện truy vấn tìm kiếm từ vấn đề này, tuy nhiên chúng tôi không đề cập đến trong ma trận TFIDF. Ví dụ từ hình trên, xét trường do nằm ngoài phạm vi nghiên cứu của bài báo này. Hình 3. Rút gọn ma trận C từ 5D thành 2D bằng LSI Sau quá trình tiền xử lý, chúng ta tiếp tục tiến cụm thì có ý nghĩa là chúng gần gũi, tính tương hành mô hình hóa và trực quan các tài liệu dựa trên đồng gần nhau. ma trận TFIDF. Cụ thể theo trình tự như sau: - Xây dựng graph layout cho mô hình. - Xây dựng mạng Nơ ron nhân tạo Self- ogranizing Map ba chiều (3D-S.O.M). Chi tiết sẽ được trình bày sau đây. - Xây dựng Graph layout cho 3D-S.O.M và Xây dựng 3D-SOM hiển thị, từ đó giúp người dùng cân nhắc chọn số Chúng tôi xây dựng một lưới ba chiều để thể nhóm cần phân cụm, đây chính là thông số k dùng hiện các nơron. Mỗi nơron có tọa độ (X,Y,Z) , cho giải thuật phân cụm k-means. vector (có cùng chiều với các vector TFIDF của - Áp dụng giải thuật k-means để phân các tập dữ liệu, cụ thể là cùng chiều với vector Bag- vector trong ma trận TFIDF (đại diện cho mỗi bài Of-Word) và trọng số. Ví dụ hình dưới là một lưới báo khoa học) thành K cụm. Các bài báo trong mỗi có 27 nơron (3x3x3). Hình 4. 3D SOM với 3x3x3 nơ ron (trái) và 6 winners (màu đỏ-phải) Đầu tiên, chúng ta gán tọa độ duy nhất (lấy 3D-SOM sẽ gặp hạn chế về vấn đề thời gian từ 3D-Grid) cho mỗi nơron. Trọng số của nơron thực thi khi chiều của vector khá lớn cũng như (d1,d2,d3, .,dn) có giá trị ngẫu nhiên trong độ ổn định của Mạng phụ thuộc vào số lần khoảng (0,1). lặp. Tuy nhiên, nó có lợi thế là Mạng Self- Tiếp theo, chúng ta sẽ huấn luyện mỗi nơron từ Ogranizing Map có thể phân loại dữ liệu mà tập hợp các mẫu (ma trận TFIDF) theo giải thuật không cần phải huấn luyện lại Mạng khi mà SOM (Kohoren, 1997). nó đã ổn định. Soá 16, thaùng 12/2014 4
5. 5 Sau khi xây dựng graph layout và hiển thị bề mặt của một khối cầu có bán kính so với tâm 3D-SOM, dựa vào hình ảnh trực quan nhìn thấy của hạt nhân bằng mức năng lượng của nó khi hệ được, chúng ta có thể ước lượng được giá trị K (số thống ở trạng thái không chuyển động. nhóm cần được phân cụm) cho giải thuật phân cụm - Mỗi electron sẽ có cùng kích thước quy ước K-means trong bước tiếp theo. Theo hình trên, ta có thể dễ dàng chỉ ra K = 3 cho tập dữ liệu. - Kích thước của nguyên tử = số electron * kích thước electron b) Nếu chúng ta có k nguyên tử (clusters): Sự phân bố của chúng sẽ được tính dựa trên kích thước của nó (cụ thể là số lượng electron – là các vector TFIDF của tài liệu) theo sau: - Tất cả hạt nhân của các nguyên tử được bố trí trên cùng một mặt phẳng. - Tạo ra một vòng tròn tưởng tượng, chia vòng Hình 5. Lưới 3D-SOM 10x10x10 của 25 này thành k góc – mỗi góc sẽ chứa một nguyên tử, độ lớn mỗi góc tương ứng tỉ lệ với kích thước Mô hình của chúng tôi sử dụng dạng cấu trúc nguyên tử cho việc hiển thị và tương tác, vì vậy nguyên tử của nó. Vector của tâm vòng tròn chúng ta cần biết tâm của Cụm mà nó sẽ thể hiện này được tính theo công thức: như là hạt nhân của nguyên tử. Trong các phương pháp phân cụm, chúng ta thấy phương pháp phân hoạch bằng k-means (MacQueen, 1967) là phù hợp nhất bởi vì ta sau khi phân cụm, ta có thêm giá trong đó W là tập tất cả các vector TFIDF của tập trị vector là tâm của cụm. Cần nói rõ thêm là hiện tài liệu, là vector TFIDF của một tài liệu trong W. nay đã có nhiều giải thuật cải tiến của K-means (ví dụ k-means ++) nhưng vì để đơn giản nên chúng - Hạt nhân của mỗi nguyên tử (tâm của tôi chỉ sử dụng k-means. mỗi cụm) sẽ nằm trên đường phân giác của góc; khoảng cách của hạt nhân so với tâm của đường Mô hình dạng cấu trúc nguyên tử cho việc tròn được tính theo công thức: phân cụm tập tài liệu: Sau khi xây dựng 3D-SOM và K-means, chúng ta sẽ tiến hành xây dựng mô hình. Chúng ta qui Lưu ý, để đảm bảo ngữ nghĩa về “tính tương tự” ước như sau: nên sẽ không dùng công thức khoảng cách Euclid. a) Mỗi cluster ω là một nguyên tử. - Dựa trên vị trí của các hạt nhân vừa tính được, Mỗi nguyên tử là đại diện của một Cụm. Cụ thể, ta sẽ xác định được sự phân bố của các electron so hạt nhân là Centroil của Cụm W, các electron với hạt nhân của nó dựa trên công thức tính mức bao quanh hạt nhân là các vector (vector TFIDF năng lượng như đã đề cập phần trên. của một bài báo) trong cùng nhóm. Ví dụ minh họa Hình 6, chúng ta có bốn Cụm Centroil của cluster W: C1, C2, C3, C4 với số electron tương ứng n1 < n2 < n3 < n4. Trong hình bên trái, chúng ta có thể thấy rõ các vùng sẽ chứa các nguyên tử được - Khoảng cách giữa electron và hạt nhân của tính toán dựa trên số lượng electron của nó. Trong nó được đo bằng sự giống nhau về ngữ nghĩa giữa Hình 6, chúng ta định vị trí các hạt nhân của các chúng (là hệ số cosin giữa 2 vector), còn gọi là cụm C1, C2, C3, C4 sau khi tính được vị trí của năng lượng của electron hạt nhân nguyên tử so với tâm của hình tròn. Lưu ý, khi xảy ra sự chồng chéo, đan xen giữa các quỹ đạo các Cụm, một hệ số tỉ lệ cần được thêm vào - Những electron có cùng mức năng lượng sẽ để dịch chuyển các vị trí hạt nhân ra xa tâm vòng nằm trên cùng quỹ đạo và được phân bố đều trên tròn nhằm tạo vùng không gian cách ly rộng hơn. Soá 16, thaùng 12/2014 5
6. 6 Hình 6. Tính vị trí cho bốn clusters dựa trên kích thước Như đã trình bày, mỗi nguyên tử sẽ có tối đa năm mức năng lượng để phân bố các electron của chúng. Sau khi chuẩn hóa các giá trị khoảng cách từ một electron đến hạt nhân theo khoảng cách tối đa qui ước, chúng sẽ là một số thực nằm trong khoảng [0, max_distance]. Trong một mức năng lượng cụ thể ở trạng thái tĩnh, các electron sẽ được phân bố đều trên một quả cầu mà có tâm là vị trí của hạt nhân và bán kính chính là giá trị mức năng lượng của nó. Để giải quyết bài toán phân bố đều các điểm trên một quả cầu, chúng tôi tham khảo các Hình 7. Phân bố đều các điểm trên quả cầu giải pháp từ các diễn đàn thảo luận (Bulatov, 1996). Hình 9. 4 nguyên tử với 25 electrons (trái) và 5 nguyên tử với 200 Theo cách tiếp cập này, chúng ta sẽ có được q = ( 0, visualization, cluster) một cái nhìn đầy đủ để phân tích từng Cụm và = (0,1,1) → vector đơn vị mối quan hệ giữa các cụm. Dựa trên không gian ba chiều, sự giới hạn về không gian cho việc trực quan hóa đã được xử lý một cách hiệu quả. Tính điểm Score (q,d) của mỗi tài liệu d ứng Truy vấn thông tin với truy vấn q theo công thức độ tương tự cosine: (Manning, Christopher D.; Raghavan, Prabhakar; Dựa vào tính chất thể hiện tài liệu bằng vector Schutze, Hinrich;, 2009) (cụ thể là TFIDF), ta có thể xem một truy vấn là một vector. Xét ví dụ với một truy vấn q = Score (q,d) = (visualization, cluster) từ tập vector tf-idf của ba Theo Bảng 1, Doc 3 có Score cao nhất ứng với tài liệu như sau: truy vấn q = (visualization, cluster). Điều này nói Trước tiên, chúng ta sẽ biến đổi truy vấn này lên rằng Doc 3 có mối quan hệ gần gũi nhất với thành vector đơn vị: truy vấn này. Soá 16, thaùng 12/2014 6
7. 7 Bảng 1. Kết quả tính điểm cho truy vấn q 4. Đánh giá Kết quả Term Doc 1 Doc 2 Doc 3 Để đánh giá hệ thống, chúng ta xem xét ba tiêu chí: Computer 0.996 0.993 0.847 (1) Tính trực quan: tiêu chí quan trọng đầu Visualization 0.087 0.120 0.466 tiên là sự tổ chức, sắp xếp các đối tượng trên một Cluster 0.017 0 0.254 màn hình máy tính mà nó phải thỏa mãn các yêu Score(q,d) 0.074 0.085 0.509 cầu về sự dễ hiểu, sự khả dụng và sự thẩm mỹ. Tương tác: Chúng tôi hiện thực hệ thống này trong không Dựa trên sự tổ chức các đối tượng theo mô hình gian ba chiều với đầy đủ tính năng của một hệ thống nguyên tử, hệ thống dễ dàng thể hiện một cách hiệu trực quan như là overview, zoom, filter, Detail-on- quả cái nhìn tổng quan cũng như mối quan hệ giữa demand, relative and extract (Shneiderman, 2010). các đối tượng riêng rẽ trong tập dữ liệu. Kết hợp Chúng tôi chọn kỹ thuật Arcball (Shoemake, 1992) với khả năng tương tác tốt, hệ thống sẽ cho chúng cho các thao tác trong một thế giới 3D một cách ta hiểu được nhiều thông tin hơn. Cụ thể như chúng trực quan bởi vì nó không đòi hỏi các thiết bị đặc ta có thể so sánh mức độ tương đồng giữa các Cụm biệt hỗ trợ tương tác như kỹ thuật 3D ball và Tracer. dữ liệu một cách gián tiếp dựa trên khoảng cách của các hạt nhân so với tâm chung. Khi muốn tìm hiểu mối quan hệ trực tiếp, hệ thống này sẽ hỗ trợ chúng ta so sánh ở chế độ lưới 3D-SOM. (2) Thời gian thực thi: là một trong những yêu cầu thiết yếu của hệ thống. Chúng ta xem thời gian thực thi của các tác vụ sau đây: Hình 8. Kỹ thuật Arcball Bảng 2. Thời gian thực thi cho 3 cụm với lần lượt 25x5052, 50x8865, 100x12348 (bài báo x số chiều của vector tfidf) Tính toán thời gian thực thi từng tác vụ 25 x 5052 50 x 8865 100x12348 Xây dựng TFIDF O(NxM) 00:00:17.66 00:00:53.93 00:02:36.86 K-means O(IKNM) 00:00:00.23 00:00:00.91 00:00:03.24 O(I x N x M x ) SOM 00:00:24.15 00:00:41.16 00:02:01.55 NumNeuron3 Phân bố đều trên quả cầu O( I x N2) 00:00:00.03 00:00:00.10 00:00:00.44 Đơn vị: giờ:phút:giây.%giây I:số vòng lặp, K: số cụm, N: số lượng bài báo, M: số chiều Vector của bài báo Thời gian thực thi hệ thống bằng tổng thời gian đảm bảo tính đúng đắn của việc phân cụm. các tác vụ. Nhìn chung, có thể thấy thời gian tính 5. Kết luận toán cho việc phân cụm trực quan 100 tài liệu chạy trên máy CPU Core i5, RAM 8 GB xấp xỉ 5 phút là Hệ thống trực quan hóa thông tin 3D này được chấp nhận được. Do không có số liệu đo của các hệ chúng tôi phát triển nhằm hỗ trợ việc phân cụm thống khác nên chưa thể đánh giá so sánh chúng. trực quan tập các bài báo khoa học nói riêng và các tài liệu, văn bản nói chung theo mô hình nguyên (3) Tính đúng đắn của giải thuật: như đã đề cập, tử trong không gian 3 chiều, nó trợ giúp các nhà cách tiếp cận này sử dụng hai giải thuật quá phổ khai phá dữ liệu trong việc phân tích Cụm với biến là SOM và K-Means vốn đã được chứng minh một tập dữ liệu có chiều rất lớn. Các thí nghiệm tính đúng đắn. Trong đó, chúng tôi trực quan hóa đã cho thấy rằng phương pháp tiếp cận của chúng giải thuật SOM để tạo tiền đề xác định tham số tôi có thể cải thiện hiệu quả của trực quan để phân K cho giải thuật K-means. Như vậy, hệ thống vẫn tích cluster. Như chúng ta đã thấy, hệ thống này Soá 16, thaùng 12/2014 7
8. 8 có khả năng giúp người dùng dễ dàng hiểu được từ tập dữ liệu). Kết quả là, với lợi thế của hệ thống mối quan hệ giữa các bài báo khoa học trong một này, những người khai phá dữ liệu có thể dễ dàng tập hàng ngàn bài báo. Công cụ này sẽ rất hữu ích ước tính số lượng cụm cũng như có một hướng trong việc hiển thị cụm và phơi bày những khoảng dẫn hiệu quả cho việc phân tích dữ liệu trong trống trong bộ dữ liệu (xu hướng tiết lộ thông tin những bước tiếp theo với thông tin chính xác hơn. Tài liệu tham khảo Ankerst, Mihael, Grinstein, Georges, Keim, Daniel. 2002. Visual Data Mining: Background, Techniques, and Drug Discovery Application. Alberta, s.n. Bulatov, V 1996. The Mathematical Atlas: A Geteway to modern mathematics. Xem 20.01.2013 . Cruz-Neira C, Sandin D., DeFanti T., Kenyon R., Hart J 1992. The CAVE. Communications of the ACM, 35(6), pp. 64-72. Kohoren, T 1997. Seft-Organizing Maps. In: Second extended Edition ed. Berlin: Springer. MacQueen, J. B 1967. Some methods for classification and analysis of multivariate observations. Berkeley, University of California Press, pp. 281-297. Manning, Christopher D., Raghavan, Prabhakar, Schutze, Hinrich. 2009. “An introduction to Information Retrieval”. Cambridge University Press. Porter, M. F 1980. “Algorithm for suffix stripping”.Program, pp. 130-137. Shneiderman, P 2010. Designing the user interaction interface: strategies for effective Human- Computer Interaction. 5th ed. s.l.:Addison Wesley. Shoemake. 1992. “Arcball: a user interface for specifying three-dimensional orientation using a mouse”. Proceedings of Graphics Interface’92, pp. 151-156. Ward, Matthew, Grinstein, Georges, Keim, Daniel. 2010. Interaction Data Visualization: Foundation, Techniques, and Application. s.l.:A K Peter, Ltd. Ware, C 2004. Information Visualization: Perception for design. 2nd ed. s.l.:Morgan Kaufman. Zhang, Ke-Bing, Orgun, Mehmet A, Zhang, Kang. 2006. HOV3: “An approach for Visual Cluster Analysis”. In Proceedings of The 2nd International Conference on Advanced Data Mining and Application, Volume LNAI 4093, pp. 316-327. Soá 16, thaùng 12/2014 8