Luận văn Nghiên cứu một số kỹ thuật lấy tin tự động trên internet

n phân cụm phân hoạch điển hình như k-means, PAM, CLARA, CLARANS… sẽ được trình bày chi tiết ở những chương sau. 2.1.2 Phân cụm dữ liệu phân cấp Phân cụm phân cấp sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Cây phân cụm có thể được xây dựng theo hai phương pháp tổng quát: phương pháp dưới lên (Bottom up) và phương pháp trên xuống (Top down) [5]. Phương pháp “dưới lên” (Bottom up): Phương pháp này bắt đầu với mỗi đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được hòa nhập vào một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến khi các điều kiện kết thúc thỏa mãn. Như vậy, cách tiếp cận này sử dụng chiến lược ăn tham trong quá trình phân cụm. Ví dụ: Dùng phương pháp "dưới lên" để phân cụm cho tập dữ liệu S= {a, b, c, d, e}. Các bước thực hiện phân cụm được diễn tả như sau : Bước 0: Mỗi đối tượng dữ liệu được gán cho mỗi cụm tương ứng, đồng thời xác định tâm D cho mỗi cụm, và tính độ tương tự cho các cặp cụm dữ liệu trên bằng cách xác định độ tương tự giữa cặp tâm của chúng. Như vậy ta sẽ có các cụm ban đầu là {a}, {b}, {c}, {d}, {e}. Bước 1: Xác định ngưỡng µ, các cặp cụm có độ tương tự bé hơn hoặc bằng ngưỡng µ thì được gộp vào một cụm. Các cặp cụm dữ liệu có độ tương tự lớn hơn µ thì xếp vào các cụm khác nhau. Trong thí dụ này chỉ có {a} và {b} là được gộp vào thành một cụm lớn hơn là {a, b}. Các cụm thu được sau bước này là: {a, b}, {c}, {d}, {e}. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24 Bước 2: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1, sau bước này ta gộp cụm {d}, {e} thành {d, e}. Các cụm thu được là {a, b}, {c}, {d, e}. Bước 3: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1, sau bước này ta gộp cụm {c} với {d, e} thành {c, d, e}. Các cụm thu được là {a, b}, {c, d, e}. Bước 4: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1, sau bước này ta gộp cụm hai cụm {c, d, e} với {a, b} thành {a, b, c, d, e}. Tuy nhiên, trong quá trình trên chúng ta có thể dừng ở một bước bất kỳ khi mà việc phân cụm đáp ứng tốt nhất các yêu cầu đã đặt ra. Các bước thực hiện trên được mô tả trực quan như hình 2.1 dưới đây. Hình 2.1: Phân cụm phân cấp theo phương pháp “dưới lên”-Bottom Up Phương pháp “trên xuống” (Top Down): Bắt đầu với trạng thái là tất cả các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá trình phân cụm. Ví dụ: Dùng phương pháp "dưới lên" để phân cụm cho tập dữ liệu S= {a, b, c, d, e}. Các bước thực hiện phân cụm được diễn tả như sau: Bước 0 Bước 1 Bước 2 Bước 3 Bước 4 b d c e a a b d e c d e a b c d e Bottom up Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 Bước 0: Các đối tượng dữ liệu ban đầu được xếp vào một cụm, ta thu được cụm {a, b, c, d, e}. Tính độ tương tự giữa các đối tượng dữ liệu trong cụm {a, b, c, d, e}. Bước 1: Xác định ngưỡng µ , cụm ban đầu được tách ra thành các cụm sao cho các đối tượng dữ liệu trong mỗi cụm con tách ra có độ tương tự bé hơn hoặc bằng µ Sau bước này thì cụm {a, b, c, d, e} chia thành hai cụm {a, b} và {c, d, e}. Bước 2: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1 cho từng cụm con. Với ngưỡng µ, chỉ có cụm con {c, d, e} được tách ra thành hai cụm con lần lượt là {c} và {d, e}. Các cụm thu được sau bước này là {a, b}, {c}, {d, e}. Bước 3: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1 cho các cụm đã thu được ở bước 2, ở đây chỉ có cụm {d, e} được chia thành 2 cụm con {d}, {e}. Các cụm thu được sau bước này là {a, b}, {c}, {d}, {e}. Bước 4: Cập nhật lại ngưỡng µ và thực hiện tương tự như trong bước 1 cho cụm {a, b} và sau bước này ta thu được các cụm: {a}, {b}, {c}, {d}, {e}. Tuy nhiên trong quá trình trên chúng ta có thể dừng ở một bước bất kỳ khi mà việc phân cụm đáp ứng tốt nhất các yêu cầu đã đặt ra. Các bước thực hiện trên được mô tả trực quan như hình 2.2 dưới đây: Hình 2.2 : Phân cụm phân cấp theo phương pháp “trên xuống”-Top Down B Bước 3 Bước 2 Bước 1 Bước 0 b d c e a a b d e c d e a b c d e Top Down Bước 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 Thực tế áp dụng, có nhiều trường hợp người ta kết hợp cả hai phương pháp phân cụm phân hoạch và phương phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân cấp có thể cải tiến thông quan bước phân cụm phân hoạch. Phân cụm phân hoạch và phân cụm phân cấp là hai phương pháp Phân cụm dữ liệu cổ điển, hiện nay đã có nhiều thuật toán cải tiến dựa trên hai phương pháp này đã được áp dụng phổ biến trong Data Mining. 2.1.3 Phân cụm dữ liệu dựa trên mật độ Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng nào đó. Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định thì nó tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các đối tượng lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác định trước. Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Tuy vậy, việc xác định các tham số mật độ của thuật toán rất khó khăn, trong khi các tham số này lại có tác động rất lớn đến kết quả phân cụm dữ liệu. Hình 2.3 dưới đây là một minh hoạ về các cụm dữ liệu với các hình thù khác nhau dựa trên mật độ được khám phá từ 3 Cơ sở dữ liệu khác nhau. Hình 2.3 : Một số hình dạng cụm dữ liệu khám phá được bởi kỹ thuật Phân cụm dữ liệu dựa trên mật độ CSDL 1 CSDL 2 CSDL 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Một số thuật toán Phân cụm dữ liệu dựa trên mật độ điển hình như DBSCAN, OPTICS, DENCLUE… sẽ được trình bày chi tiết trong phần tiếp theo. 2.1.8 Phân cụm dữ liệu dựa trên lưới Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều chiều, để giải quyết cho đòi hỏi này, người ta đã dử dụng phương pháp phân cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để Phân cụm dữ liệu, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian [5]. Thí dụ như dữ liệu được biểu diễn dưới dạng cấu trúc hình học của đối tượng trong không gian cùng với các quan hệ, các thuộc tính, các hoạt động của chúng. Mục tiêu của phương pháp này là lượng hoá tập dữ liệu thành các ô (Cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao tác Phân cụm dữ liệu làm việc với các đối tượng trong từng Cell này. Cách tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các cell mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một cell. Trong ngữ cảnh này, phương pháp này gần giống với phương pháp phân cụm phân cấp nhưng chỉ có điều chúng không trộn các Cell. Do vậy các cụm không dựa trên độ đo khoảng cách (hay còn gọi là độ đo tương tự đối với các dữ liệu không gian) mà nó được quyết định bởi một tham số xác định trước. Ưu điểm của phương pháp Phân cụm dữ liệu dựa trên lưới là thời gian xử lý nhanh và độc lập với số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số cell trong mỗi chiều của không gian lưới. Một thí dụ về cấu trúc dữ liệu lưới chứa các cell trong không gian như hình 2.4 sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 Hình 2.4 : Mô hình cấu trúc dữ liệu lưới Một số thuật toán Phân cụm dữ liệu dựa trên cấu trúc lưới điển hình như: STING, WAVECluster, CLIQUE… 2.1.9 Phân cụm dữ liệu dựa trên mô hình Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà chúng tinh chỉnh các mô hình này để nhận dạng ra các phân hoạch. Phương pháp Phân cụm dữ liệu dựa trên mô hình cố gắng khớp giữa dữ liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai tiếp cận chính: Mô hình thống kê và Mạng Nơron. Phương pháp này gần giống với phương pháp dựa trên mật độ, bởi vì chúng phát triển các cụm riêng biệt nhằm cải tiến các mô hình đã được xác định trước đó, nhưng đôi khi nó không bắt đầu với một số cụm cố định và không sử dụng cùng một khái niệm mật độ cho các cụm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 2.1.10 Phân cụm dữ liệu có ràng buộc Sự phát triển của phân cụm dữ liệu không gian trên Cơ sở dữ liệu lớn đã cung cấp nhiều công cụ tiện lợi cho việc phân tích thông tin địa lý, tuy nhiên hầu hết các thuật toán này cung cấp rất ít cách thức cho người dùng để xác định các ràng buộc trong thế giới thực cần phải được thoả mãn trong quá trình Phân cụm dữ liệu. Để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần được thực hiện để cung cấp cho người dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm [5]. 2.2. Phân cụm dữ liệu dựa vào thuật toán K-means 2.2.1. Tư tưởng thuật toán K-means là một trong số những phương pháp học không có giám sát cơ bản nhất thường được áp dụng trong việc giải các bài toán về phân cụm dữ liệu. Mục đích của thuật toán k-means là sinh ra k cụm dữ liệu {C1, C2, …,Ck} từ một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = (xi1, xi2, …, xid) ( ni ,1 ), sao cho hàm tiêu chuẩn [5]:    k i x iC mxE i1 2 đạt giá trị tối thiểu. Trong đó: mi là trọng tâm của cụm Ci, là khoảng cách giữa hai đối tượng [2]. Trọng tâm của một cụm là một véc tơ, trong đó giá trị của mỗi phần tử của nó là trung bình cộng của các thành phần tương ứng của các đối tượng véc tơ dữ liệu trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra của thuật toán là các trọng tâm của các cụm dữ liệu. Độ đo khoảng cách d giữa các đối tượng dữ liệu thường được sử dụng là khoảng cách Euclide, bởi vì đây là mô hình khoảng cách dễ để lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định cụ thể hơn tuỳ vào ứng dụng hoặc các quan điểm của người dùng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30 Để dễ hình dung về thuật toán k-means ta xét ví dụ đơn giản sau: Cho tập dữ liệu bao gồm có 15 phần tử thực trong không gian 1 chiều S= {1, 4, 8, 5, 10, 15, 16, 23, 25, 27, 13, 37, 2, 18, 20}, người ta cần phân cụm dữ liệu này ra thành 3 cụm (k=3) theo thuật toán k-means. Các bước thực hiện của thuật toán được trình bày như sau: Bước khởi tạo: chọn 3 tâm ngẫu nhiên CL1 = 8, CL2= 16, CL3= 23 Ta thu được phân hoạch ban đầu như sau: Cụm 1, với tâm là CL1, gồm có các phần tử: 1, 2, 4, 5, 8, 10 Cụm 2, với tâm là CL2, gồm có các phần tử: 13, 15, 16, 18 Cụm 3, với tâm là CL3, gồm có các phần tử: 23, 25, 27, 20, 37 (Ở đây độ đo tương tự giữa hai đối tượng được xác định bằng công thức: d(a, b)=|a-b|) Như vậy, ta có : E = {(1-8)2 + (2-8)2 + (4-8)2+ (5-8)2+ (8-8)2+ (10 - 8)2} + {(13-16)2 + (15-16)2 + (16-16)2+ (18-16)2}+ {(25-23)2 + (23-23)2 + (27- 23)2+ (37-23)2+ (20-23)2} = 353. Bước lặp thứ nhất: Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8+10)/6 = 5; Tương tự ta có: CL2=13; CL3=26.4; Phân hoạch tương ứng với các tâm mới như sau: Cụm 1, với tâm là CL1 gồm có các phần tử: 1, 2, 4, 5, 8 Cụm 2, với tâm là CL2 gồm có các phần tử: 10, 13, 15, 16, 18 Cụm 3, với tâm là CL3 gồm có các phần tử: 23, 25, 27, 20, 37 Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 249.2. Do giá trị của hàm mục tiêu này bé hơn sơ với trạng thái của nó trước đó nên ta có bước lặp thứ hai như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 Bước lặp thứ hai: Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8)/5 = 4; Tương tự ta có: CL2=14.4; CL3=26.4; Phân hoạch tương ứng với các tâm mới như sau: Cụm 1, với tâm là CL1 gồm có các phần tử: 1, 2, 4, 5, 8 Cụm 2, với tâm là CL2 gồm có các phần tử: 10, 13, 15, 16, 18, 20 Cụm 3, với tâm là CL3 gồm có các phần tử: 23, 25, 27, 37 Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 224.8 Do giá trị của hàm mục tiêu này bé hơn sơ với trạng thái của nó trước đó nên ta có bước lặp thứ ba như sau: Bước lặp thứ ba: Cập nhật lại tâm mới: Cl1 = (1+2+4+5+8)/5 = 4; Tương tự ta có: CL2=15.33; CL3=28; Phân hoạch tương ứng với các tâm mới như sau: Cụm 1, với tâm là CL1, gồm có các phần tử: 1, 2, 4, 5, 8 Cụm 2, với tâm là CL2, gồm có các phần tử: 10, 13, 15, 16, 20 Cụm 3, với tâm là CL3, gồm có các phần tử: 23, 25, 27, 37 Với phân hoạch này ta có giá trị hàm mục tiêu là: E= 209.33 Chúng ta thực hiện thuật toán với bước tiếp theo do giá trị của hàm mục tiêu thu được vẫn bé hơn giá trị trước đó. Ở bước tiếp theo ta thấy thuật tóan sẽ dừng do tâm mới cập nhật sẽ không bị thay đổi. Như vậy, kết quả phân cụm ta sẽ xác định giá trị của ba tâm như sau: CL1= 4; CL2=15.33; CL3=28; 2.2.2 Mô tả thuật toán Input: K, và dữ liệu về n mẫu của 1 Cơ sở dữ liệu. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 Output: Một tập gồm K cluster sao cho cực tiểu về tổng sai-số vuông. Các bước thuật toán: Bước 1: Chọn ngẫu nhiên K mẫu vào K cluster. Coi tâm của cluster chính là mẫu có trong cluster. Bước 2: Tìm tâm mới của cluster. Bước 3: Gán các mẫu vào từng cluster sao cho khoảng cách từ mẫu đó đến tâm của cluster đó là nhỏ nhất. Bước 4: Nếu các cluster không có sự thay đổi nào sau khi thực hiện bước 3 thì chuyển sang bước 5, ngược lại sang bước 2. Bước 5: Dừng thuật toán. Ví dụ: Trong không gian hai chiều, cho 12 điểm (n = 12) cần phân 12 điểm này thành hai cluster (k=2). Đầu tiên, chọn hai điểm ngẫu nhiên vào hai cluster (chọn 2 điểm màu đỏ: (1,3); (9,4)) Coi điểm (1,3) là tâm của cluster 1 và điểm (9,4) là tâm của cluster 2. Tính toán khoảng cách từ các điểm khác đến hai điểm này và gán được các điểm còn lại này vào một trong hai cluster, những điểm có màu xanh lơ vào cluster 1, những điểm có màu xanh đậm vào cluster 2. Hiệu chỉnh lại tâm của hai cluster, điểm màu đỏ là tâm mới của hai cluster. Tính lại các khoảng cách các điểm đến tâm mới và gán lại các điểm này. Tiếp tục hiệu chỉnh lại tâm của hai cluster. Rồi, lặp lại cho đến khi không còn sự thay đổi nữa thì dừng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 Hình 2.5: Minh họa thuật toán K-means Độ phức tạp của thuật toán này là O(tKn). Trong đó n là số mẫu trong Cơ sở dữ liệu, K là số cluster, t là số lần lặp. Thông thường t, k << n. Nên thuật toán này có hiệu quả tương đối với các Cơ sở dữ liệu lớn [2]. 2.3 Phân cụm dữ liệu dựa vào thuật toán K-medios 2.3.1. Tư tưởng thuật toán Để tìm ra k cụm với n đối tượng thì k-medoids chọn ngẫu nhiên k đối tượng vào k cụm, coi mỗi đối tượng này là tâm của cụm. Phân bổ các đối tượng còn lại vào cụm mà sự khác nhau của nó với đối tượng tâm của cụm là gần nhất. Sau đó lặp lại quá trình: Thay đổi đối tượng tâm của mỗi cụm sao cho chất lượng của cụm được cải thiện. Chất lượng của cụm được lượng giá bởi một hàm đo sự khác nhau giữa một đối tượng và đối tượng tâm của cụm chứa nó. Quá trình lặp cho đến khi không còn sự thay đổi nào về lực lượng cũng như hình dạng của các cụm [2]. Để chọn một đối tượng không là đối tượng tâm Orandom thay thế tốt cho một đối tượng tâm Oj thì mỗi đối tượng p xét theo 4 trường hợp sau đây: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34 Trường hợp 1: p đang thuộc vào cụm có tâm là Oj (từ nay gọi là cụm Oj). Nếu Oj được thay thế bởi Orandom và p gần nhất với Oi (ij) thì p được gán lại vào Oi Trường hợp 2: p đang thuộc vào Oj. Nếu Oj được thay thế bởi Orandom và p gần nhất với Orandom thì p được gán lại vào Orandom. Trường hợp 3: p đang thuộc vào Oi (ij). Nếu Oj được thay thế bởi Orandom và p vẫn gần nhất với Oi thì không thay đổi gì cả. Tức là p vẫn thuộc Oi. Trường hợp 4: p đang thuộc vào Oi (ij). Nếu Oj được thay thế bởi Orandom và p gần nhất với Orandom thì p được gán lại vào Orandom. Hình 2.6: Các trường hợp đối với điểm p 2.3.2. Mô tả thuật toán Input: Số nguyên k và Cơ sở dữ liệu gồm n đối tượng cần phân cụm. Output: Một tập gồm k cụm mà tổng giá trị của sự khác nhau của tất cả các đối tượng đến đối tượng tâm của nhóm chứa nó là nhỏ nhất. Thuật toán: Bước 1: Chọn k đối tượng bất kì vào k cụm. Coi mỗi đối tượng này là tâm của nhóm. Bước 2: Lặp Bước 3: Gán mỗi đối tượng còn lại vào một cụm mà nó gần với đối tượng tâm của cụm nhất. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35 Bước 4: Chọn ngẫu nhiên một đối tượng không là đối tượng tâm, Orandom. Bước 5: Tính lại giá trị, S, đối với việc đổi Oj với Orandom. Bước 6: Nếu S<0 thì đổi Oj với Orandom để tạo ra một tập với đối tượngtâm mới. Bước 7: Đến khi không có sự thay đổi nào nữa thì dừng. Ví dụ: Trong không gian hai chiều cho n = 10 điểm, cần chia thành k =2 cụm. Các bước thực hiện của thuật toán k-medoids được chỉ ra: Hình 2.7: Các bước thực hiện của k-medoids Đầu tiên, chọn hai điểm bất kì vào hai cụm (điểm màu xanh đậm), rồi xét các điểm còn lại và đưa chúng vào một trong hai cụm với điểm tâm lần lượt là hai điểm đã chọn ban đầu. Tiếp theo, chọn một điểm bất kì khác điểm tâm (điểm màu đỏ). Tính giá của phép chuyển đổi điểm tâm từ điểm màu xanh -> điểm màu đỏ. Nếu giá này chất lượng hơn thì coi điểm đỏ là tâm của cụm mới và thực lặp lại quá trình đó cho đến khi không còn sự thay đổi nào. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 2.3.3 Nhận xét: Thuật toán k-medoids mạnh hơn thuật toán k-means trong các trường hợp dữ liệu có nhiễu vì k-medoids chịu ảnh hưởng ít hơn của nhiễu và các giá trị chênh lệnh so với giá trị trung bình. Tuy nhiên cả hai thuật toán này đều yêu cầu đưa vào số lượng cụm k [2]. 2.4. Phân cụm dữ liệu dựa vào thuật toán BIRCH 2.4.1. Tư tưởng thuật toán BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) là thuật toán phân cụm phân cấp sử dụng chiến lược phân cụm trên xuống (top down). Ý tưởng của thuật toán là không cần lưu toàn bộ các đối tượng dữ liệu của các cụm trong bộ nhớ mà chỉ lưu các đại lượng thống kê. Đối với mỗi dữ liệu, BIRCH chỉ lưu một bộ ba (n, LS, SS), trong đó n là số đối tượng trong cụm, LS là tổng các giá trị thuộc tính của các đối tượng trong cụm và SS là tổng bình phương của các giá trị thuộc tính của các đối tượng trong cụm. Các bộ ba này được gọi là các đặc trưng của cụm (Cluster Features - CF) và được lưu giữ trong một cây được gọi là cây CF (CF-tree). Người ta đã chứng minh rằng [5][10], các đại lượng thống kê chuẩn, như là độ đo khoảng cách, có thể xác định từ cây CF. Hình 2.8 dưới đây biểu thị một ví dụ về cây CF. Chúng ta thấy rằng, tất cả các nút trong của cây lưu tổng các đặc trưng cụm CF, của nút con, trong khi đó các nút lá lưu trữ các đặc trưng của các cụm dữ liệu [4]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 Hình 2.8: Cây CF được sử dụng bởi thuật toán BIRCH Cây CF là cây cân bằng, nhằm để lưu trữ các đặc trưng của cụm (CF). Cây CF chứa các nút trong và nút lá, nút trong là nút chứa các nút con và nút lá thì không có con. Nút trong lưu giữ tổng các đặc trưng cụm (CF) của các nút con của nó. Một cây CF được đặc trưng bởi hai tham số: Yếu tố nhánh (Branching Factor -B): Nhằm xác định số tối đa các nút con của mỗi nút trong của cây. Ngưỡng (Threshold - T): Khoảng cách tối đa giữa bất kỳ một cặp đối tượng trong nút lá của cây, khoảng cách này còn gọi là đường kính của các cụm con được lưu tại các nút lá. Hai tham số này có ảnh hưởng đến kích thước của cây CF. Thuật toán BIRCH thực hiện qua giai đoạn sau: Giai đoạn 1: BIRCH duyệt tất cả các đối tượng trong Cơ sở dữ liệu và xây dựng một cây CF khởi tạo. Trong giai đoạn này, các đối tượng lần lượt được chèn vào nút lá gần nhất của cây CF (nút lá của cây đóng vai trò là cụm con), sau khi chèn xong thì tất cả các nút trong cây CF được cập nhật thông tin. Nếu đường kích của cụm con sau khi chèn là lớn hơn ngưỡng T, thì nút lá được tách. Quá trình này lặp cho đến khi tất cả các đối tượng đều được chèn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 vào trong cây. Ở đây ta thấy rằng, mỗi đối tượng trong cây chỉ được đọc một lần, để lưu toàn bộ cây CF trong bộ nhớ thì cần phải điều chỉnh kích thước của cây CF thông qua điều chỉnh ngưỡng T. Giai đoạn 2: BIRCH lựa chọn một thuật toán Phân cụm dữ liệu (như thuật toán phân cụm phân hoạch chẳng hạn) để thực hiện Phân cụm dữ liệu cho các nút lá của cây. 2.4.2 Mô tả thuật toán: Bước 1: Các đối tượng dữ liệu lần lượt được chèn vào cây CF, sau khi chèn hết các đối tượng ta thu được cây CF khởi tạo. Một đối tượng được chèn vào nút lá gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn hơn T thì nút lá được tách. Khi một đối tượng thích hợp được chèn vào nút lá, tất cả các nút trỏ tới gốc của cây được cập nhật với các thông tin cần thiết. Bước 2: Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành cây dựng một cây CF nhỏ hơn: Kích thước của cây CF được điều khiển bởi tham số T và vì vậy việc chọn một giá trị lớn hơn cho nó sẽ hoà nhập một số các cụm con thành một cụm, điều này làm cho cây CF nhỏ hơn. Bước này không cần yêu cầu bắt đầu đọc dữ liệu lại từ đầu nhưng vẫn đảm bảo hiệu chỉnh cây dữ liệu nhỏ hơn. Bước 3: Thực hiện phân cụm: Các nút lá của cây CF lưu giữ các đại lượng thống kê của các cụm con. Trong bước này, BIRCH sử dụng các đại lượng thống kê này để áp dụng một số kỹ thuật phân cụm thí dụ như k-means và tạo ra một khởi tạo cho phân cụm. Bước 4: Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối tượng trọng tâm cho các cụm đã được khám phá từ bước 3: Đây là một bước tuỳ chọn để duyệt lại tập dữ liệu và gán nhãn lại cho các đối tượng dữ liệu tới Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 các trọng tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi tạo và loại bỏ các đối tượng ngoại lai. Với cấu trúc cây CF được sử dụng, BIRCH có tốc độ thực hiện Phân cụm dữ liệu nhanh và có thể áp dụng đối với tập dữ liệu lớn, đặc biệt, BIRCH hiệu quả khi áp dụng với tập dữ liệu tăng trưởng theo thời gian. BIRCH là chỉ duyệt toàn bộ dữ liệu một lần với một lần quét thêm tuỳ chọn, nghĩa là độ phức tạp của nó là O(n), với n là số đối tượng dữ liệu. Nhược điểm của nó là chất lượng của các cụm được khám phá không được tốt. Nếu BIRCH sử dụng khoảng cách Euclide, nó thực hiện tốt chỉ với các dữ liệu số. Mặt khác, tham số vào T có ảnh hưởng rất lớn tới kích thước và tính tự nhiên của cụm. Việc ép các đối tượng dữ liệu làm cho các đối tượng của một cụm có thể là đối tượng kết thúc của cụm khác, trong khi các đối tượng gần nhau có thể bị hút bởi các cụm khác nếu chúng được biểu diễn cho thuật toán theo một thứ tự khác. BIRCH không thích hợp với dữ liệu đa chiều [4]. 2.5. Cải tiến thuật toán K-means trong phân cụm dữ liệu tự động 2.5.1. Tư tưởng thuật toán Bài toán thu thập, phân cụm dữ liệu tự động là một bài toán mang tính thời sự, vì trong thời đại công nghệ thông tin, với sự trợ giúp của máy tính thì việc áp dụng công nghệ thông tin vào thu thập dữ liệu tự động trên internet, sau đó phân tích phục vụ cho việc phận cụm và từ đó hình thành các chủ đề thôn tin với các dữ liệu thu thập tự động từ internet. Trên cơ sở đó, chúng ta tiến hành phân tích dữ liệu và đưa ra những dự báo trong tương lai với từng chủ đề khác nhau như: dự báo tốc độ tăng trưởng kinh tế, GDP, chỉ số chứng khoán, giá cả hàng hoá... Điều này làm cơ sở cho chúng ta có thể đưa ra một chính sách phát triển kinh tế trong cả nước [2]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 Tuy nhiên, để có được những dữ liệu và phân cụm được những dữ liệu đó theo các chủ đề khác nhau thì chúng ta phải có các kỹ thuật. Như mục 2.2, nhóm tác giả đã trình bày thuật toán K-Means, tuy nhiên thuật toán có những hạn chế nhất định [2]. Do đó, nhóm tác giả cải tiến thuật toán này nhằm khắc phục những hạn chế của thuật toán K-means. Cải tiến thuật toán K-means: thay vì chọn số điểm (k) làm trọng tâm, chúng ta không chọn số điểm (k) làm trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng cách đưa trung tâm cụm mới vào cụm có mức độ biến dạng Max và tính lại trọng tâm các cụm. Với thuật toán K- means bắt đầu bằng cách chọn k cụm và chọn ngẫu nhiên k điểm làm trung tâm cụm, hoặc chọn phân hoạch ngẫu nhiên k cụm và tính trọng tâm của từng cụm này. Việc chọn ngẫu nhiên k điểm làm trung tâm cụm như đã nói ở trên có thể cho ra các kết quả khác nhau tùy vào chọn k điểm này. Thuật toán cải tiến K-means nhìn chung vẫn dựa trên thuật toán k- means nhưng sẽ không chọn k điểm làm trọng tâm cho k cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng cách đưa trung tâm cụm mới vào cụm có mức độ biến dạng max (tăng số cụm) và tính lại trọng tâm các cụm. 2.5.2. Mô tả thuật toán Bước 1: Khởi tạo giá trị ban đầu cho K: K=1 Bước 2: Bước 2.1: Kiểm tra điều kiện K Nếu K=1: chọn bất kỳ một điểm làm trung tâm của cụm. Nếu K>1: thêm trung tâm của cụm mới vào cụm có biến dạng max. Bước 2.2: Gán từng điểm vào cụm có trung tâm gần nhất với điểm đang xét và cập nhật lại trung tâm cụm Bước 2.3: Nếu trung tâm cụm không thay đổi, chuyển sang bước 3. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 Ngược lại, quay trở lại bước 2.2 (bước 2). Bước 3: (Tăng số cụm) Nếu K≤ giá trị ấn định số cụm thì K:=K+1, quay trở lại bước 2.1 (bước 2). Ngược lại, thuật toán dừng. Với thuật toán K-means cải tiến: đưa ra sự khác biệt, đó là mức độ biến dạng của các cụm (Dựa trên biến dạng để phân cụm). Mức độ biến dạng của các cụm được tính như sau: I=S-N (d (w,x )) Trong đó: w: trung tâm của cụm, N: Số các thành phần trong cụm. S: Tổng bình phương khoảng cách giữa các thành phần trong cụm và trung tâm của không gian Euclidean. I: Mức độ biến dạng của cụm d (w,x): là khoảng cách giữa trung tâm w của cụm và trung tâm của không gian Euclidean x. 2.5.3 Nhận xét: + Một cụm có mức độ biến dạng lớn thì trung tâm cụm đó có vị trí không thích hợp. + Việc xác định các cụm cũng như xác định trung tâm của cụm, như vậy thuật toán chủ yếu tìm trung tâm cụm chính xác và xác định lại các thành phần trong cụm. Với thuật toán K-means cải tiến: + Bước 2: như K-means nhưng khác là: không xác định trước k điểm mà tăng k lên dần từ 1. Và chọn cụm có mức độ biến dạng lớn để phân ra 2 cụm (khi đó 2 cụm này có mức độ biến dạng giảm, nhỏ hơn). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 + Thuật toán cải tiến K-means có độ phức tạp là O( k 2 nt), như vậy so với thuật toán K-means có độ phức tạp O(tkn) thì: O( k 2 nt)>O(tkn), nhưng không bằng K-mendoids, do k<<n. Tuy nhiên ưu điểm của thuật toán là giảm sự phụ thuộc vào việc khởi tạo các cụm ban đầu nên ta sẽ không phải lập lại thuật toán với việc chọn các cụm ban đầu khác nhau để tìm ra kết quả tối ưu như ở K-Means. 2.3.4 Thử nghiệm: Để đánh giá thuật toán cải tiến K-means, nhóm tác giả sử dụng các dữ liệu lấy từ các trang Web với các nguồn chính sau: + Các trang được lấy tự động từ các website trên internet, việc tìm kiếm được thực hiện bằng cách dùng Google, chương trình sẽ dựa vào URL để lấy tài liệu và lưu trữ lại phục vụ cho quá trình tìm kiếm sau này. + Tìm kiếm có chọn lọc với các chủ đề tin về "Chứng khoán", khoảng 250 bài; Chủ đề tin về "Tỷ giá hối đoái", khoảng 100 bài; Chủ đề tin về "Giá vàng", khoảng 150 bài; Chủ đề tin về "Thời tiết", khoảng 50 bài. Các chủ đề đều có tần số xuất hiện nhiều. Trên cơ sở thuật toán K-means, thuật toán K-medoids, nhóm tác giả so sánh kết quả thực hiện phân cụm với các chủ đề tin trên. Kết quả bảng dưới đây: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 Số tài liệu (Cơ sở dữ liệu) Số cụm Thời gian phân cụm trung bình (giây) K-means K-medoids K-means cải tiến 250 10 9,756 9,106 8,56 250 15 12,375 11,525 10,972 100 10 2,518 2,218 2,118 100 15 3,719 3,119 3,219 150 10 4,115 4,015 3,005 150 15 5,723 5,110 5,123 50 10 0,957 0,907 0,857 50 15 1,13 1,11 1,00 Với độ phức tạp của các thuật toán trên, nhóm tác giả thấy thời gian thực hiện thuật toán phụ thuộc vào độ lớn cơ sở dữ liệu và số cụm cần phân cụm [2]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 Chương 3: ỨNG DỤNG TRONG LẤY TIN TỰ ĐỘNG 3.1. Bài toán Thu thập dữ liệu về kinh tế trên Internet Trong thời đại bùng nổ thông tin như hiện nay thì việc khai thác, thu thập và chia sẻ thông tin đóng một vai trò quan trọng. Với một dữ liệu khổng lồ trên mạng, làm sao ta có thể nắm bắt được thông tin mới nhất, nhanh chóng nhất mà không phải tốn thời gian xem từng website để đọc và tìm kiếm thông tin. Trên cơ sở này, hệ thống bóc tách thông tin được xây dựng nhằm phục vụ cho việc trích xuất thông tin từ các website, rồi tất cả thông tin được hiển thị trên một website, giúp cho người đọc có thể nắm bắt được thông tin một cách xúc tích, nhanh chóng và tiết kiệm thời gian. Đối tượng sử dụng hệ thống là tất cả cộng đồng người sử dụng mạng. Quản trị viên có thể quản lý tài khoản người dùng, quản lý các đường dẫn (link). Khảo sát, phân tích và đánh giá yêu cầu Khảo sát một số chương trình hỗ trợ đọc tin tức RSS 3.1.1 iCA iCA là tên gọi tắt của "Information Catcher", là phần mềm được xây dựng dựa trên nền tảng và công nghệ dot NET của Microsoft. Phần mềm iCA hoạt động với tính năng nhận các thông tin từ Website tổng hợp sau đó hiển thị đầy đủ. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 45 Hình 3.1: Giao diện của iCA 3.1.2 Google Reader Google Reader là một sản phẩm của Google dựa trên nền Web Form, có rất nhiều tính năng nổi trội: lựa chọn số tin tức được hiển thị, chia sẻ tin với bạn bè, phân nhóm tin tức, tìm kiếm tin tức….. Hình 3.2: Giao diện trang chủ Google Reader Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 46 3.1.3 iGoogle iGoogle là một cổng cá nhân (Personal Portal), sử dụng công nghệ AJAX và .NET Framework 3.5. Khi người dùng thêm kênh tin từ trang Google Reader, thì nó sẽ được tự động cập nhật vào trang iGoogle. Hình 3.3: Giao diện trang chủ của iGoogle iGoogle còn cung cấp sẵn một directory Hình 3.4: Giao diện trang Gagdet của iGoogle Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 47 3.1.4 Trình duyệt Firefox Hiện nay các trình duyệt phiên bản mới nhất cũng hỗ trợ công nghệ RSS. Ví dụ như: Internet Explorer 8.0 của Microsoft, Opera, Firefox… Khi ta vào một website nào đó mà sử dụng công nghệ RSS thì trên trình duyệt của Firefox có xuất hiện biểu tượng màu da cam, ở giữa có ba chấm trắng. Hình 3.5: Giao diện trình duyệt FireFox Nếu ta muốn lấy tin từ trang tin đó, ta chỉ cần kích vào biểu tượng đó và nó sẽ tự động chuyển tới trang lấy tin của Google Reader và iGoogle. Hoặc ta có thể sử dụng Live Bookmark được tích hợp trong trình duyệt Firefox để lấy tin. Hình 3.6: Giao diện trang lấy tin RSS Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 48 3.1.5 Tổng hợp yêu cầu của người dùng Mục tiêu của đề tài là xây dựng nên một hệ thống hỗ trợ người dùng chọn kênh tin tức, thu thập tin tức, quản lý các kênh tin, tạo ra một website tin tức cho chính người dùng mà không phải lướt từng website để đọc tin tức. Thông qua việc khảo sát một số phần mềm đọc tin tức trong và ngoài nước, và yêu cầu từ phía người dùng, có thể tóm tắt yêu cầu của người dùng đối với hệ thống bóc tách thông tin như sau: - Người dùng có thể tạo ra kênh tin tức cho riêng mình bằng cách chỉ cần đăng ký một tài khoản và đăng nhập vào nhập đường dẫn link tới địa chị trang website cần lấy tin. - Người dùng có thể tổ chức, quản lý kênh tin tức của mình với các chức năng: - Tạo nhóm tin tức (như: tin giáo dục, xã hội, tin chứng khoán…), sửa nhóm tin và xoá nhóm tin. - Lựa chọn số tin tức được hiển thị. - Người dùng còn có thể tìm kiếm thông tin. 3.1.6 Đánh giá và lựa chọn giải pháp Thông qua việc khảo sát một số website, phần mềm hỗ trợ đọc tin tức RSS ở trên, ta thấy có giải pháp để xây dựng hệ thống đó là: Win Form và Web Form. Sau đây là những thuận lợi hay khó khăn của hai giải pháp trên. Và cuối cùng sẽ lựa chọn giải pháp cho chương trình của mình. - Sử dụng Win Form: + Ưu điểm: Hỗ trợ nhiều tính năng Khả năng chạy không cần mạng (offline) + Nhược điểm: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 49 Người dùng phải mất thời gian cài đặt Khó khăn trong việc nâng cấp: mỗi khi hệ thống nâng cấp, cập nhật thêm chức năng mới thì người dùng phải cài lại chương trình. - Sử dụng Web Form: + Ưu điểm: Tính cơ động: Không cần cài đặt, không cần cấu hình, với ứng dụng sử dụng Web Forms, người dùng chỉ cần dùng một trình duyệt web kết nối với mạng Internet là có thể truy cập ở bất cứ chỗ nào. Đây có thể nói là ưu điểm lớn nhất của các ứng dụng Web Forms. Dễ thay đổi: Sử dụng Web Forms đồng nghĩa với tất cả dữ liệu và chương trình đã nằm trên máy chủ. Chính vì vậy khi muốn sửa đổi, nâng cấp hệ thống, việc nâng cấp trên Web Forms có thể diễn ra rất dễ dàng. Người cung cấp dịch vụ chỉ cần cập nhật trực tiếp lên máy chủ, còn phía người dùng, các công việc này hoàn toàn trong suốt. Tính chia sẻ: có thể chia sẻ tin tức. Sau khi xem xét các khía cạnh, ưu và nhược điểm của các công nghệ cho thấy Web Form là một giải pháp tối ưu để phát triển hệ thống. Cụ thể ở đây là công nghệ .NET của Microsoft, sử dụng ngôn ngữ lập trình C# và hệ quản trị Cơ sở dữ liệu Microsoft SQL Server 2000. 3.2 Phân tích chức năng hệ thống 3.2.1 Biểu đồ Use Case Biểu đồ Use Case thể hiện sự tương tác giữa người dùng và hệ thống. Từ đó xác định được hệ thống cần phải làm gì. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 50 Hình 3.8: Biểu đồ User – case 3.2.2 Đặc tả các Use - case  Đặc tả Use – case đăng nhập + Tóm tắt Use case này mô tả cách đăng nhập vào hệ thống bóc tách thông tin. + Dòng sự kiện chính - Use case này bắt đầu khi một actor (người dùng, quản trị viên) muốn đăng nhập vào hệ thống. - Hệ thống yêu cầu các actor nhập tên và mật khẩu. - Hệ thống kiểm tra tên và mật khẩu mà actor đã nhập. Nếu đúng hệ thống cho phép actor đăng nhập vào hệ thống. + Dòng sự kiện khác - Tên / mật khẩu sai: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 51 Nếu trong dòng sự kiện chính các actor nhập tên, mật khẩu sai thì hệ thống sẽ báo lỗi. Actor có thể quay trở về đầu dòng sự kiện hoặc huỷ bỏ việc đăng nhập, lúc này use case kết thúc. + Các yêu cầu đặc biệt Không có. + Điều kiện tiên quyết Không có. + Post condition Nếu use case thành công thì người đăng nhập sẽ có các quyền sử dụng hệ thống tương ứng. Ngược lại trạng thái của hệ thống không đổi. + Điểm mở rộng Không có.  Đặc tả Use-case quản lý tin tức + Tóm tắt Use case này cho phép người sử dụng (đã là đăng nhập thành công) quản lý tin tức: thêm, sửa, xoá nhóm tin, lựa chọn số tin tức được hiển thị và thêm, xoá kênh tin. + Dòng sự kiện Use case này bắt đầu khi người dùng đăng nhập vào hệ thống và thêm kênh tin và nhóm tin. + Dòng sự kiện chính - Hệ thông sẽ liệt kê các nhóm tin, kênh tin của riêng thành viên đó. - Thêm, sửa, xoá nhóm tin và kênh tin, lựa chọn số tin tức hiển thị. + Các yêu cầu đặc biệt Không có + Điểu kiện tiên quyết Không có Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 52 + Post conditions Nếu use case thành công, thông tin về nhóm tin, kênh tin sẽ được cập nhật vào cơ sở dữ liệu. + Điểm mở rộng Không có  Đặc tả Use- case quản lý người dùng + Tóm tắt Use case này cho phép quản trị viên thêm, sửa, xoá, tìm kiếm thông tin về thành viên sử dụng hệ thống. Quản lý trang tin của các thành viên (thêm, sửa, xoá trang tin của người sử dụng). + Dòng sự kiện chính - Quản trị viên lựa chọn chức năng quản lý người dùng - Hệ thống nhận thông tin từ quản trị viên. - Hệ thống kiểm tra thông tin nhập vào - Hệ thống truy xuất cơ sở dữ liệu. - Theo từng yêu cầu của quản trị viên hệ thống sẽ thực hiện như sau: Nếu quản trị viên yêu cầu thêm, sửa, xoá hoặc cập nhật lại thông tin về trang tin riêng của người sử dụng thì hệ thống sẽ cập nhật lại cơ sở dữ liệu tương ứng với các yêu cầu. Nếu quản trị viên yêu cầu tìm kiếm thông tin người sử dụng thì hệ thống đưa ra những người sử dụng thoả yêu cầu của quản trị viên. - Hệ thống thông báo thực hiện thành công. - Use – case kết thúc. + Dòng sự kiện phụ Nếu hệ thống không truy xuất được cơ sở dữ liêu thì sẽ báo lỗi, use – case kết thúc. + Các yêu cầu đặc biệt Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 53 Không có. + Điều kiện tiên quyết Người quản lý đăng nhập vào hệ thống với quyền quản trị viên trước khi use – case bắt đầu. + Post conditions Nếu use – case thành công thì thông tin của người sử dụng sẽ được cập nhật vào hệ thống. Ngược lại trạng thái của hệ thống không thay đổi. + Điểm mở rộng Không có.  Đặc tả Use-case tìm kiếm tin tức + Tóm tắt Use case này cho phép người sử dụng tìm kiếm thông tin mà mình muốn tìm. + Dòng sự kiện Use case này bắt đầu khi người dùng chọn chức năng tìm kiếm tin tức. + Dòng sự kiện chính - Người dùng nhập thông tin muốn tìm. - Công cụ Google sẽ tìm kiếm. - Liệt kê tất cả thông tin thoả yêu cầu. + Dòng sự kiện phụ Nếu không tìm thấy thì thông báo cho người dùng biết là không tìm thấy. + Các yêu cầu đặc biệt Không có. + Điều kiện tiên quyết Không có. + Post conditions Không có. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 54 3.2.3 Biểu đồ tuần tự (Sequence Diagram) Hoạt động của hệ thống: Nhìn một cách bao quát, hệ thống gồm những thao tác cơ bản sau: Hình 3.9: Biểu đồ tuần tự - Toàn cảnh hệ thống Đăng ký tài khoản: Để có thể tạo trang tin cá nhân người sử dụng cần phải đăng ký một tài khoản. Người dùng chỉ cần điền đúng và đầy đủ các thông tin mà chương trình đưa ra. Server có trách nhiệm cung cấp tài khoản mới cho người dùng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 55 Hình 3.10: Biểu đồ tuần tự - Đăng ký tài khoản Đăng nhập hệ thống: Là hành động người dùng sử dụng tài khoản được cấp để vào hệ thống. Sau khi nhập các thông tin cần thiết, chương trình sẽ kết nối và kiểm tra tính hợp lệ. Người dùng sẽ được phản hồi kết quả. Hình 3.11: Biểu đồ tuần tự - Đăng nhập hệ thống Thêm đường dẫn: Để lấy thông tin từ website khác, người dùng có thể nhập trực tiếp đường dẫn tới tập tin RSS, chương trình sẽ tự động trích rút tin tức và hiện thị lên cho người dùng. Hoặc người dùng có thể nhập đường dẫn Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 56 tới website cung cấp RSS, chương trình sẽ trích rút các đường dẫn tới các tập tin RSS cho người dùng lựa chọn. Hình 3.12: Biểu đồ tuần tự - Thêm đường dẫn link Thêm nhóm tin: Là thao tác mà người dùng thêm mới nhóm để phân loại tin tức. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 57 Hình 3.13: Biểu đồ tuần tự - Thêm nhóm tin Sắp xếp, phân loại nhóm tin: Hình 3.14: Biểu đồ tuần tự - Sắp xếp nhóm tin Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 58 Tìm kiếm tin tức: Trước hết người dùng chọn chế độ tìm kiếm, đó là tìm kiếm tin tức trong hệ thống hay tìm kiếm trên Google search. Hình 3.15: Biểu đồ tuần tự - Tìm kiếm thông tin Quản lý người dùng: Đây là thao tác chỉ dành cho người dùng có quyền là quản trị. Quản trị viên có thể cung cấp tài khoản mới cho người dùng, có thể xoá tài khoản người dùng, quản lý trang tin cá nhân của người dùng. Hình 3.16: Biểu đồ tuần tự - Quản lý người dùng Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 59 3.3 Thiết kế cơ sở dữ liệu 3.3.1 Đặc tả chi tiết các bảng dữ liệu Bảng Urls: chứa thông tin về địa chỉ website chứa các kênh tin. Bảng 3.1: Bảng Urls (địa chỉ website) Bảng Channels: chứa thông tin về các kênh tin tức Bảng 3.2: Bảng Channels (kênh tin) Bảng Items: chứa thông tin về những tin tức mà hệ thống bóc tách lấy về. tblItems STT Tên trường Kiều dữ liệu Độ dài Ghi chú Diễn giải 1 ItemID int 4 Khoá chính Mã tin tức 2 ChannelID int 4 Khác rỗng Mã kênh tin 3 iLink nvarchar 50 Khác rỗng Đường dẫn tới chi tiết của tin tức 4 iTitle nvarchar 50 Khác rỗng Tiêu đề của tin tức 5 iDescription nvarchar MAX Khác rỗng Nội dung chi tiết của tin tức 6 iPubDate datetime Ngày xuất bản tin 7 iAuthor nvarchar 50 Tác giả viết tin Bảng 3.3: Bảng Items (tin tức) tblUrls STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải 1 UrlID int 4 Khoá chính Mã địa chỉ 2 uLink nvachar 50 Khác rỗng Đường dẫn tới website 3 uTitle nvarchar 50 Tiêu đề của website 4 uDescription nvarchar 50 Đặc tả về website tblChannels STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải 1 ChannelID int 4 Khoá chính Mã kênh tin 2 cLink nvachar 50 Khác rỗng Đường dẫn tới file RSS 3 cTitle nvarchar 50 Khác rỗng Tiêu đề của kênh tin 4 cDescription navarchar MAX Khác rỗng Đặc tả chi tiết về kênh tin 5 LastUpdated dateTime Khác rỗng Thời gian cập nhật kênh tin 6 ItemCount int 4 Khác rỗng Số lượng tin tức có trong kênh tin Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 60 Bảng Group: chứa thông tin về nhóm tin của mỗi người sử dụng Bảng 3.4: Bảng Group (nhóm tin tức) Bảng User Blog: chứa thông tin về blog tin tức của mỗi người dùng. Bảng 3.5: Bảng User Blog (kho tin tức của mỗi người dùng) tblGroup STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải 1 GroupID int 4 Khoá chính Mã nhóm 2 GroupName nvachar 50 Khác rỗng Tên nhóm 3 UserName nvarchar 50 Khác rỗng Tên đăng nhập của người sử dụng tblUserBlog STT Tên trường Kiểu dữ liệu Độ dài Ghi chú Diễn giải 1 UserBlogID int 4 Khoá chính Mã trang blog tin tức của mỗi người dùng 2 UserName nvarchar 50 Khác rỗng Tên đăng nhập của người sử dụng 3 ChannelID int 4 Khác rỗng Mã kênh tin 4 GroupID int 4 Khác rỗng Mã nhóm 5 NumberToShow int 4 Số lượng tin người dùng chọn trên mỗi kênh tin Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 61 3.3.2 Mô hình quan hệ Hình 3.17: Mô hình quan hệ dữ liệu giữa các bảng 3.4 Qui trình tự động lấy đường dẫn tới tập tin RSS Khi người dùng nhập đường dẫn tới website (chẳng hạn: ), thì nhiệm vụ của hệ thống là lấy tất cả những file RSS mà website đó cung cấp. Bước 1: Ta phải tải nội dung trang HTML của website đó về. Bước 2: Ta sử dụng đến biểu thức chính qui (Regular Expression) để lọc ra những thẻ chứa đường dẫn tới file RSS. Bước 3: Lọc ra đường dẫn tới file RSS, ta cũng dùng biểu thức chính qui để match() được href chứa đường dẫn tới file RSS. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 62 Bước 4: Sau khi đã lấy được đường dẫn tới file RSS, lưu vào Cơ sở dữ liệu. Tiếp theo, đọc file RSS đó. 3.5 Qui trình đọc tập tin RSS Người dùng có thể nhập trực tiếp đường dẫn tới file RSS. Nhiệm vụ của hệ thống là trích rút dữ liệu từ file RSS. Để trích rút dữ liệu ta làm như sau: Bước 1: Trước tiên là thiết kế lớp RSSItem để chứa các dữ liệu mà ta trích rút từ file RSS. Bước 2: Đọc file RSS 3.6 Một số màn hình giao diện đạt được Hình 3.18: Giao diện trang đăng nhập Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 63 Hình 3.19: Giao diện trang quản lý người dùng Hình 3.20: Giao diện blog Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 64 Hình 3.21: Giao diện thư mục RSS cung cấp sẵn Hình 3.22: Giao diện trang lấy link RSS tự động Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 65 Hình 3.23: Giao diện trang tin tức lấy về Hình 3.24: Giao diện trang quản lý nhóm tin Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 66 PHẦN KẾT LUẬN Tầm quan trọng của vấn đề lấy tin tự động trên Internet Với sự phát triển nhanh chóng của Internet như ngày nay, thì mỗi ngày, tuần, tháng, quý, năm... mỗi con người chúng ta phải xử lý hàng trăm, triệu, tỷ... thông tin, dữ liệu khác nhau, điều này có nghĩa là chúng ta đã gặp phải những rắc rối không mong muốn trong thời đại công nghệ số này. Vì vậy, bài toán tìm kiếm tài liệu Web và phân cụm tài liệu là một bài toán phức tạp và được ứng dụng trong thực tế, đặc biệt trong các ứng dụng Web. Trên cơ sở những dữ liệu thu thập được từ internet thì chúng ta cần phải tiến hành phân loại, nhóm phân cụm thành các cụm khác nhau theo các chủ đề khác nhau từ đó phục vụ cho việc phân tích dữ liệu và dự báo kinh tế [1]. Hiện nay, có nhiều phương pháp tìm kiếm khác nhau, nhưng nhìn chung là các cách tiếp cận đều dựa vào các trọng số trang Web (Chỉ số quan trọng của trang trong tập kết quả), như: Page Bank, HITS...Tức là các trang này chủ yếu là dựa vào các liên kết để xác định trọng số [16]. Mặt khác, chúng ta có thể dựa vào nội dung các tài liệu để xác định trọng số, nếu các tài liệu gần nhau về nội dung thì gán cho chúng một trọng số và khi đó chúng thuộc cùng một nhóm. Các vấn đề đã được tìm hiểu trong luận văn Luận văn đã nêu vấn đề cải tiến thuật toán K-means trong phân cụm tài liệu web, thay vì chọn số điểm làm trọng tâm thì không chọn số điểm làm trọng tâm cho số cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng cách đưa trung tâm cụm mới vào cụm có mức độ biến dạng Max và tính lại trọng tâm các cụm và đã cài đặt thử nghiệm trên các bộ cơ sở dữ liệu, cho kết quả bước đầu khá khả quan. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 67 Hướng nghiên cứu tiếp theo Tiếp tục nghiên cứu các kỹ thuật phân cụm dữ liệu, trong đó nhấn mạnh đến kỹ thuật phân cụm K-Means mở rộng, thời gian tuyến tính đáp ứng được các yêu cầu của bài toán phân cụm tài liệu Web. Đề xuất ra giải pháp xây dựng quy trình công nghệ và phát triển hệ thống phần mềm thu thập, đánh giá và phân cụm thông tin tự động trên Internet phục vụ cho việc nghiên cứu, học tập và giảng dạy ngành Hệ thống thông tin Kinh tế, và phục vụ cho việc phân tích, tổng hợp, xử lý dữ liệu và dự báo phát triển kinh tế xã hội của khu vực trung du và miền núi phía Bắc. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 68 DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN VĂN 1. Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh Hà, Nguyễn Thanh Dương (2009), "Tìm kiếm và phân cụm tài liệu Web tự động", Tập 56, số 8, 2009 - Tạp chí khoa học và công nghệ, Đại học Thái Nguyên, tr. 60 - 64. 2. Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh Hà (2009), "Cải tiến thuật toán K-Means và ứng dụng phân cụm dữ liệu tự động", Báo cáo Hội thảo Khoa học tại ĐH Lạc Hồng, Đồng Nai. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 69 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh Hà, Nguyễn Thanh Dương (2009), "Tìm kiếm và phân cụm tài liệu Web tự động", Tập 56, số 8, 2009 - Tạp chí khoa học và công nghệ, Đại học Thái Nguyên, tr. 60 - 64. [2] Phạm Việt Bình, Nguyễn Văn Huân, Vũ Xuân Nam, Trương Mạnh Hà (2009), "Cải tiến thuật toán K-Means và ứng dụng phân cụm dữ liệu tự động", Báo cáo Hội thảo Khoa học tại ĐH Lạc Hồng, Đồng Nai. [3] Lê Thu Trang (2008), "Khai phá dữ liệu bằng phương pháp phân cụm", Luận văn thạc sĩ Công nghệ thông tin, Khoa Công nghệ thông tin - Đại học Thái Nguyên. [4] Hoàng Văn Dũng, "Khai phá dữ liệu web bằng kỹ thuật phân cụm", [5] Đỗ Văn Đại (2009), "Phân cụm dữ liệu trong không gian có chướng ngại vật", Đồ án tốt nghiệp Đại học, Khoa Công nghệ thông tin - Đại học Giao thông vận tải. Tài liệu tiếng Anh [6] Athena Vakali (2004), "Web data clustering Current research status & trends", Aristotle University, Greece. [7] Raghu Krishnapuram, Anupam Joshi, and Liyu Yi (2001), A Fuzzy Relative of the K - Medoids Algorithm with Application toWeb Document and Snippet Clustering. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 70 [8] Filippo Geraci, Marco Pellegrini, Paolo Pisati, and Fabrizio Sebastiani (2006), A scalable algorithm for high-quality clustering of Web Snippets, Italy, ACM. [9] Hiroyuki Kawano (2004), Applications of Web mining- from Web search engine to P2P filtering, IEEE. [10] Raymond and Hendrik (2000), Web Mining Research: A Survey, ACM. [11] Hua-Jun Zeng, Qi-Cai He, Zheng Chen, Wei-Ying Ma, Jinwen Ma (2004), Learning to Cluster Web Search Results, ACM. [12] Lizhen Liu, Junjie Chen, Hantao Song (2002), The research of Web Mining, IEEE. [13] Maria Rigou, Spiros Sirmakessis, and Giannis Tzimas (2006), A Method for Personalized Clustering in Data Intensive Web Applications. [14] Oren Zamir and Oren Etzioni (1998), Web document Clustering: A Feasibility Demonstration, University of Washington, USA, ACM. [15] Periklis Andritsos (2002), Data Clusting Techniques, University Toronto. [16] Yitong Wang, Masaru Kitsuregawa (2002), Evaluating Contents- Link Coupled Web Page Clustering for Web Search Results, ACM. [17] Zifeng Cui, Xu , Weifeng Zhang, Junling Xu (2005), Web Documents Clustering with Interest Links, IEEE. [18] Wenyi Ni (2004), A Survey of Web Document Clustering, Southern Methodist University. [19] Bing Liu (2007), Web mining, Springer.