Phân cụm dữ liệu trong Dataming

điều kiện kết thúc (ví dụ số cụm) Cây các cụm: phân cấp cụm thường tạo cây các cụm hay còn được gọi là dendrogram Các lá của cây biểu diễn các đối tượng riêng lẻ Các nút trong của cây biểu diễn các cụm Hai loại phương pháp tạo kiến trúc cụm: Gộp- agglomerative (từ dưới lên) Đưa từng đối tượng vào cluster riêng của nó Trộn ở mỗi bước hai cụm tương tự nhất cho đến khi chỉ còn một cụm hay thỏa điều kiện kết thúc Phân chia – divisive (từ trên xuống) Bắt đầu bằng một cụm lớn chứa tất cả các đối tượng Phân chia cụm phân biệt nhất thành các cụm nhỏ hơn và xử lý cho đến khi co n cụm hay thỏa điều kiện kết thúc Hai loại phương pháp tạo kiến trúc phân cấp cụm Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step 0 Gộp-agglomerative Phân chia- divisive Các khoảng cách trong Thường có 3 cách được dùng để định nghĩa khoảng cách giữa các cụm: Phương pháp liên kết đơn (láng giềng gần nhất): Phương pháp liên kết hoàn toàn (láng giềng xa nhất): Phương pháp liên kết trung bình (trung bình cặp nhóm không có trọng ): Sức mạnh của các phương pháp phân cấp Khái niệm đơn giản Lý thuyết tốt Khi cụm được trộn/ tách, quyết định là vĩnh cửu => số các phương án khác nhau cần được xem xét bị rút giảm. Điểm yếu của phương pháp phân cấp Trộn/ tách các cụm là vĩnh cửu => các quyết định sai là không thể khắc phục về sau Các phương pháp phân chia là cần thời gian tính toán Các phương pháp là không scalable (mở rộng được) cho các tập dữ liệu lớn Phân tích outlier outliers Là các đối tượng bất tương tự với Có thể gây ra việc đo đạc hay lỗi thực hiện, hay Là kết quả của việc biến đổi dữ liệu kế thừa rất nhiều thuật toán khai phá dữ liệu cố gắng Giảm ảnh hưởng của outliers Giảm outliers Cực tiểu hóa ảnh hưởng của outliers và/ hay khử đi những outliers có thể gây ra mất mát thông tin Có thể quan tâm đến khai khác outlier mining Các ứng dụng của khai thác outlier Phát hiện phạm tội Tiếp thị Xử lý y khoa 2.2.1 Thuật toán BIRCH 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 tóan 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 của các cụm, BIRCH chỉ lưu một bộ ba (n, LS, SS), trong đó n là đố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ưa giữ trong một cây gọi là cây CF (CF tree). Người ta đã chứng minh rằng, các đại lượng thống kê chuẩn như độ đo khoảng cách, có thể xác định cây CF. Hình 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â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ụm dữ liệu 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 trữ 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ây, và Ngưỡng (Threshloid-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 được 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 qua 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ính 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 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 hai: 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 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. Thuật toán BIRCH thực hiện qua các bước cơ bản như hình sau: 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ỗi 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á thì 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. Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành dựng 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ẽ hòa nhập một số 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. 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 ví dụ như k-means và tạo ra một khởi tạo cho phân cụm 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 tùy 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 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 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 chỉ duyệt toàn bộ dữ liệu một lần với một lần quét thêm tùy chọn, nghĩa là độ phức tạp của nó là O(n), với n là đố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 dữ liệu số. Mặc 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ụ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. 2.2.2 Thuật toán CURE Việc chọn một cách biểu diễn cho các cụm có thể nâng cao chất lượng phân cụm. Thuật toán CURE (Clustering Using REpresentatives) là thuật toán sử dụng chiến lược dưới lên (Bottom up) của kĩ thuật phân cụm phân cấp. Thay vì sử dụng các trọng tâm hoặc các đối tượng tâm để biểu diễn cụm, CURE sử dụng nhiều đối tượng để diễn tả cho mỗi cụm dữ liệu. Các đối tượng đại diện cho cụm này ban đầu được lựa chọn rải rác đều ở các vị trí khác nhau, sau đó chúng được di chuyển bằng cách co lại theo một tỉ lệ nhất định. Tại mỗi bước của thuật toán, hai cụm có cặp đối tượng đại diện gần nhất (đối tượng thuộc về mỗi cụm) sẽ được trộn lại thành một cụm. Với cách thức sử dụng nhiều hơn một phần tử đại diện cho các cụm, CURE có thể khám phá được các cụm có các hình thù và kích thước khác nhau trong cơ sơ dữ liệu lớn. Việc co các đối tượng đại diện lại có tác dụng làm giảm tác động củ các phần tử ngoại lai, vì vậy, CURE có khả năng xử lý đối với các phần tử ngoại lai. Hình dưới đây là ví dụ về các dạng và kích thước cụm dữ liệu được khám phá bởi CURE Các phương pháp dựa trên mật độ Các cụm có thể được xem như các vùng có mật độ cao, được tách ra bởi các vùng không có hoặc ít mật độ. Khái niệm mật độ ở được xem như là các số các đối tượng láng giềng. Thuận toán DBSCAN Thuật toán phân cụm dựa trên mật độ thông dụng nhất là thuật toán DBSCAN (Density- Based Spatial Clustering of Applications with noise). Thuật toán đi tìm các đối tượng mà có số đối tượng láng giềng lớn hơn một ngưỡng tối thiểu. Tìm tất cả các đối tượng mà các láng giềng của nó thuộc về lớp các đối tượng đã xác định ở trên, một cụm được xác định bằng một tập tất cả các đối tượng kiên thông mật độ với các láng giềng của nó. DBSCAN có thể tìm ra các cụm với hình thù bất kì, trong khi đó tại cùng một thời điểm ít bị ảnh hưởng bởi thứ tự của các đối tượng dữ liệu nhập vào. Khi có một đối tượng dữ liệu được chèn vào chỉ tác động đến một láng giềng xác định. Mặc khác DBSCAN yêu cầu người dùng xác định bán kính Eps của các láng giềng và số các láng giềng tối thiểu Minpts, các tham số này khó mà xác định được tối ưu, thông thường nó được xác định bằng phép chọn ngẫu nhiên hoặc theo kinh nghiệm. Người ta áp dụng chỉ số không gian để giúp xác định các láng giềng của một đối tượng dữ liệu do vậy độ phức tạp của DBSCAN đã được cải tiến là O(nlogn) so với độ phức tạp của DBSCAN là O(n2) trong trường hợp nếu không áp dụng cấu trúc chỉ số. Khoảng cách Euclide được sử dụng để đo sự tương tác giữa các đối tượng nhưng không hiệu quả đối với dữ liệu đa chiều. Thuật toán DBSCAN dựa trên các khái niệm mật độ có thể áp dụng cho các tập dữ liệu không gian lớn đa chiều. Dưới đây là các định nghĩa và bổ đề được sử dụng trong thuật toán DBSCAN. Định nghĩa 1: lân cận với ngưỡng Eps của một điểm (Eps – Neighborhood of a point) Lân cận với ngưỡng Eps của một điểm P kí hiệu là NEps(p) được xác định như sau: NEps(p) = {q Î D | khoảng cach Dist(p,q) ≤ Eps}, D là tập dữ liệu cho trước. Một điểm p muốn nằm trong một cụm C nào đó thì NEps(p) thì phải có tối thiểu Minpts điểm. Số điểm tối thiểu được chọn là bao nhiêu cũng là bài toán khó, vì: Nếu số điểm tối thiểu lớn thì chỉ những điểm nằm thực sự trong cụm C mới đạt đủ tiêu chuẩn, trong khi đó những điểm nằm ngoài biên của cụm không thể đạt được điều đó. Ngược lại nếu số điểm tối thiểu là nhỏ thì mọi điểm sẽ rơi vào một cụm. Theo định nghĩa trên, chỉ những điểm thực sự nằm trong cụm mới thỏa mãn điều kiện là điểm thuộc vào cụm. Những điểm nằm ở biên của cụm thì không thỏa mãn điều kiện đó, bởi vì thông thường thì lân cận với ngưỡng Eps của điểm biên thì bé hơn lân cận với ngưỡng của Eps của điểm nhân (Core point). Để tránh được điều này, chúng ta có thể đưa ra một tiêu chuẩn khác để định nghĩa một điểm thuộc vào một cụm như sau: Nếu một điểm p muốn thuộc vào cụm C phải tồn tại một điểm q mà p ∊ NEps(q) và số điểm trong NEps(q) phải lớn hơn số điểm tối thiểu. Điều này có thể được định nghĩa một cách hình thức như sau: Định nghĩa 2: Đến được trực tiếp theo mật độ (Directly Density-reachable). Một điểm p được gọi là đến được trực tiếp từ điểm q với ngưỡng Eps nếu: p ∊ NEps(q) || NEps(q)|| ≥ Minpts (điều kiện nhân) Điểm q được gọi là điểm nhân (Core point). Có thể thấy là đến được trực tiếp một hàm phản xạ và đối xứng đối với hai điểm nhân và bất đối xứng nếu nếu một trong hai điểm đó không phải là điểm nhân. Định nghĩa 3: Đến được mật độ (Density- Reachable) Một điểm p được gọi là đến được từ một điểm q theo hai tham số Eps và Minpts nếu tồn tại một dãy p = p1, p2, ..., pn = q thỏa mãn pi+1 là có thể đến được trực tiếp từ pi với Hai điểm biên của một cụm C có thể không đến được nhau bởi vì cả hai có thể đều không thỏa mãn điều kiện nhân. Mặc dù vậy, phải tồn tại một điểm nhân C mà cả hai điểm đều có thể đến được từ điểm đó. Để cho thuận tiện chúng ta sẽ đưa ra một định nghĩa liên thông mật độ (Density- Connectivity) Định nghĩa 4: Liên thông mật độ (Density- Connectivity) Một điểm p được gọi là liên thông với điểm q theo hai tham số Eps với Minpts nếu như tồn tại một điểm o mà cả hai điểm p, q đều có thể đến được theo tham số Eps và Minpts. Liên thông mật độ có tính chất đối xứng và phản xạ. Định nghĩa 5: Cụm (Clustering) Giả sử D là một tập các điểm dữ liệu. Một tập con C khác rỗng của D được gọi là một cụm (cluster) thep Eps và Minpts nếu thỏa mãn hai điều kiện: Với mọi p,q Î D, nếu p Î C và q có thể đến được từ p theo Eps và MinPts thì qÎ C. Với mọi p,q Î C, p liên thông mật độ với q theo Eps và MinPts. Định nghĩa 6 : Dữ liệu nhiễu (Noise) Giả sử C1, C2, …, Ck là các cụm trong tập dữ liệu D theo tham số Eps và MinPts, điểm dữ liệu nhiễu là điểm dữ liệu không thuộc vào cụm nào trong các cụm C1, C2, …, Ck, tức là Noise = {p | với mọi i=1..k, p Ï Ci } Tiếp theo là hai bổ đề để chứng minh cho việc thuật toán phân cụm DBSCAN. Chúng phát biểu như sau: Với hai tham số Eps và MinPts cho trước, chúng ta có thể khám phá các cụm theo hai bước : Bước 1 : Chọn một điểm bất kỳ từ tập dữ liệu ban đầu thoả mãn điều kiện nhân Bước 2 : Lấy tất cả các điểm đến được mật độ với điểm nhân đã chọn ở trên để tạo thành cụm Hai bổ đề này có thể phát biểu một cách hình thức hơn như sau : Bổ đề 1 : Giả sử p là một điểm trong D trong đó || NEps(p)|| ≥ MinPts, tập O = {o|oÎD và o có thể đến được mật độ từ p theo Eps và MinPts}là một cụm theo Eps và MinPts. Như vậy, cụm C không hoàn toàn là duy nhất, tuy nhiên, mỗi một điểm trong C đến được mật độ từ bất cứ một một điểm nhân nào của C, vì vậy C chứa đúng một số điểm liên thông với điểm nhân tuỳ ý. Bổ đề 2 : Giả sử C là một cụm theo Eps và MinPts, p là một điểm bất kỳ trong C với || NEps(p)|| ≥ MinPts. Khi đó C trùng với tập O = {o|oÎD và o có thể đến được mật độ từ p theo Eps và MinPts}. Thuật toán DBSCAN : DBSCAN khởi tạo điểm p tuỳ ý và lấy tất cả các điểm đến được mật độ từ p với Eps và MinPts. Nếu p là điểm nhân thì thủ tục trên tạo ra một cụm theo Eps và MinPts (Bổ đề 2), Nếu p là một điểm biên, không có điểm nào đến được mật độ từ p và DBSCAN sẽ đi thăm điểm tiếp theo của tập dữ liệu. Nếu chúng ta chọn sử dụng giá trị trị toàn cục Eps và MinPts, DBSCAN có thể hoà nhập hai cụm theo định nghĩa 5 thành một cụm nếu mật độ của hai cụm gần bằng nhau. Giả sử khoảng cách giữa hai tập dữ liệu S1 và S2 được định nghĩa là Dist (S1,S2) = min{dist(p,q)| pÎ S1 và qÎ S2}. Hình sau diễn tả thuật toán DBSCAN chi tiết: {----------Mô đun chương trình chính-------} DBSCAN (SetOfPoints, Eps, MinPts) // SetOfPoints is UNCLASSIFIED ClusterId := nextId(NOISE); FOR i FROM 1 TO SetOfPoints.size DO Point := SetOfPoints.get(i); IF Point.ClId = UNCLASSIFIED THEN IF ExpandCluster(SetOfPoints, Point, ClusterId, Eps, MinPts) THEN ClusterId := nextId(ClusterId) END IF END IF END FOR END; // DBSCAN {--------------Thủ tục Expand -------------} ExpandCluster(SetOfPoints, Point, ClId, Eps, MinPts) : Boolean; seeds:=SetOfPoints.regionQuery(Point,Eps); IF seeds.size<MinPts THEN // no core point SetOfPoint.changeClId(Point,NOISE); RETURN False; ELSE // all points in seeds are density- // reachable from Point SetOfPoints.changeClIds(seeds,ClId); seeds.delete(Point); WHILE seeds Empty DO currentP := seeds.first(); result := SetOfPoints.regionQuery(currentP, Eps); IF result.size >= MinPts THEN FOR i FROM 1 TO result.size DO resultP := result.get(i); IF resultP.ClId IN {UNCLASSIFIED, NOISE} THEN IF resultP.ClId = UNCLASSIFIED THEN seeds.append(resultP); END IF; SetOfPoints.changeClId(resultP,ClId); END IF; // UNCLASSIFIED or NOISE END FOR; END IF; // result.size >= MinPts seeds.delete(currentP); END WHILE; // seeds Empty RETURN True; END IF END; // ExpandCluster {--------------End---------------------} Hình : Thuật toán DBSCAN Trong đó, SetOfPoints hoặc là tập dữ liệu ban đầu hoặc là cụm được khám phá từ bước trước, CLId (clusterId) là nhãn đánh dấu phần tử dữ liệu nhiễu có thể thay đổi nếu chúng có thể đến được mật độ từ một điểm khác từ CSDL, điều này chỉ xẩy ra đối với các điểm biên của dữ liệu. Hàm SetOfPoints.get(i) trả về phần tử thứ i của SetOfPoints. Thủ tục SetOfPoints.regionQuery(point, Eps) trả về một danh sách các điểm dữ liệu lân cận với điểm Point trong ngưỡng Eps từ tập dữ liệu SetOfPoints. Trừ một số trường hợp ngoại lệ, kết quả của DBSCAN độc lập với thứ tự duyệt các đối tượng dữ liệu. Eps và MinPts là hai tham số toàn cục được xác định bằng thủ công hoặc theo kinh nghiệm. Tham số Eps được đưa vào là nhỏ so với kích thước của không gian dữ liệu, thì độ phức tạp tính toán trung bình của mỗi truy vấn là O(log n). Thuật toán OPTICS Đây là thuật toán mở rộng cho thuật toán DBSCAN, bằng cách giảm bớt các tham số đầu vào. OPTICS (Ordering Points To Identify the Clustering Structure) sắp xếp các cụm theo thứ tự tăng dần nhằm tự động phân cụm dữ liệu. Thứ tự này diễn tả cấu trúc dữ liệu phân cụm dựa trên mật độ chứa thông tin tương đương với phân cụm dựa trên mật độ với một dãy các tham số đầu vào. OPTICS xem xét bán kính tối thiểu nhằm xác định các láng giềng phù hợp với thuật toán. DBSCAN và OPTICS tương tự với nhau về cấu trúc và có cùng độ phức tạp : O(nLogn) (N là kích thước của tập dữ liệu). Hình sau thể hiện về một thí dụ trong PCDL của thuật toán OPTICS [10][16]: thứ tự các cụm dữ liệu Khoảng cách đến được mật độ Chưa đánh dấuKh Thứ tự phân cụm của các đối tượng của OPTICS Thuật toán DENCLUE DENCLUE (DENsity - Based CLUstEring) là thuật toán PCDL dựa trên một tập các hàm phân phối mật độ. Ý tưởng chính của thuật toán này như sau [10][16]: Sự tác động của một đối tượng tới láng giềng của nó được xác định bởi hàm ảnh hưởng (Influence Function). Mật độ toàn cục của không gian các đối tượng được mô hình như là tổng tất cả các hàm ảnh hưởng của các đối tượng. Các cụm được xác định bởi các đối tượng mật độ cao (density attactors), các đối tượng này là các điểm cực đại của hàm mật độ toàn cục. Hàm ảnh hưởng được định nghĩa như sau : Cho x,y là hai đối tượng trong không gian d chiều Fd, hàm ảnh hưởng của đối tượng y lên đối tượng x được xác định như sau : : Fd , y =(x). Hàm ảnh hưởng là hàm tuỳ chọn, miễn là nó được xác định bởi khoảng cách d(x,y) của các đối tượng, thí dụ như khoảng cách Euclide. Một số thí dụ về hàm ảnh hưởng được cho như sau : Hàm sóng ngang : = , trong đó là một ngưỡng. Hàm Gaussian : Hàm mật độ của một đối tượng x Fd được tính bằng tổng tất cả các hàm ảnh hưởng của các đối tượng lên x. Giả sử ta có một tập dữ liệu D={x1, x2, ..., xn}. Hàm mật độ của x được xác định như sau : ; Hàm mật độ được thành lập dựa trên hàm ảnh hưởng Gauss được xác định như sau : . Thí dụ về kết quả PCDL của thuật toán DENCLUE với hàm chi phối Gaussian được biểu diễn như hình 21 sau. Các cực đại mật độ là các giá trị tại đỉnh của đồ thị. Một cụm cho một cực đại mật độ x* là tập con C, khi các hàm mật độ tại x* không bé hơn : Hình DENCLUE với hàm phân ph Gaussian Chúng ta thấy rằng, DENCLUE phụ thuộc nhiều vào ngưỡng nhiễu (Noise Threshold) và tham số mật độ , nhưng DENCLUE có các ưu điểm sau : Có cơ sở toán học vững chắc Có khả năng xử lý các phần tử ngoại lai Cho phép khám phá ra các cụm với hình thù bất kì ngay cả đối với các dữ liệu đa chiều Độ phức tạp tính toán của DENCLUE là O(nlogn). Các thuật toán dựa trên mật độ không thực hiện kỹ thuật phân mẫu trên tập dữ liệu như trong các thụât toán phân cụm phân hoạch, vì điều này có thể làm tăng thêm độ phức tạp do có sự khác nhau giữa mật độ của các đối tượng trong mẫu với mật độ của toàn bộ dữ liệu. Một số thuật tóan phân cụm dữ liệu đặc thù Một số thuật toán phân cụm áp dụng trong các trường hợp đặc thù như STING, CLIQUE, EM, ... Thuật toán STING STING (STatistical INformation Grid) là thuật toán dựa vào kỹ thuật phân cụm dựa trên lưới, STING phân rã tập dữ liệu không gian thành số hữu hạn các cell sử dụng cấu trúc phân cấp chữ nhật. Có nhiều mức khác nhau cho các cell trong cấu trúc lưới, các cell này hình thành nên cấu trúc phân cấp như sau : Mỗi cell ở mức cao được phân hoạch thành các cell mức thấp hơn trong cấu trúc phân cấp. Giá trị của các tham số thống kê (như các giá trị trung bình, tối thiểu, tối đa) cho các thuộc tính của đối tượng dữ liệu được tính toán và lưu trữ thông qua các tham số thống kê ở các cell mức thấp hơn (điều này giống với cây CF). Các đại tham số này bao gổm : tham số đếm count, tham số trung bình means, tham số tối đa max tham số tối thiểu min, độ lệch chuẩn s,… . Các đối tượng dữ liệu lần lượt được chèn vào lưới và các tham số thống kê ở trên được tính trực tiếp thông qua các đối tượng dữ liệu này. Các truy vấn không gian được thực hiện bằng cách xét các cell thích hợp tại mỗi mức của phân cấp. Một truy vấn không gian được xác định như là một thông tin khôi phục lại của dữ liệu không gian và các quan hệ của chúng. STING có khả năng mở rộng cao, nhưng do sử dụng phương pháp đa phân giải nên nó phụ thuộc chặt chẽ vào trọng tâm của mức thấp nhất. Đa phân giải là khả năng phân rã tập dữ liệu thành các mức chi tiết khác nhau. Khi hoà nhập các cell của cấu trúc lưới để hình thành các cụm, các nút của mức con không được hoà nhập phù hợp (do chúng chỉ tương ứng với các cha của nó) và hình thù của các cụm dữ liệu khám phá được có các biên ngang và dọc, theo biên của các cell. STING sử dụng cấu trúc dữ liệu lưới cho phép khả năng xử lý song song, STING duyệt toàn bộ dữ liệu một lần nên để tính toán các đại lượng thống kê cho mỗi cell nên độ phức tạp tính toán của STING là O(n), trong đó n là tổng số đối tượng. Sau khi xây dựng cấu trúc dữ liệu phân cấp, thời gian xử lý cho các truy vấn là O(g) với g là tống số cell tại mức thấp nhất (g<<n). 3.2 Thuật toán CLIQUE Trong không gian đa chiều, các cụm có thể tồn tại trong tập con của các chiều hay còn gọi là là không gian con. Thuật toán CLIQUE là thuật toán phân cụm không gian con. Nó phân hoạch tập dữ liệu thành các hình hộp chữ nhật và tìm các hình hộp chữ nhật đặc, nghĩa là các hình hộp này chứa một số các đối tượng dữ liệu trong số các đối tượng láng giềng cho trước. Hợp các hình hộp này tạo thành các cụm dữ liệu. CLIQUE trước hết tìm các cell đặc đơn chiều, tiếp đến chúng tìm các hình chữ nhật 2 chiều, rồi 3 chiều,…, cho đến khi hình hộp chữ nhật đặc k chiều được tìm thấy. CLIQUE có khả năng áp ụng tốt đối với dữ liệu đa chiều, nhưng nó lại rất nhạy cảm với thứ tự của dữ liệu vào, độ phức tạp tính toán của CLIQUE là O(n). 3.3 Thuật toán EM Thuật toán EM (Expectation -Maximization) được xem như là thuật toán dựa trên mô hình hoặc là mở rộng của thuật toán k-means. Thật vậy, EM gán các đối tượng cho các cụm dữ đã cho theo xác suất phân phối thành phần của đối tượng đó. Phân phối xác suất thường được sử dụng là phân phối xác suất Gaussian với mục đích là khám phá lặp các giá trị tốt cho các tham số của nó bằng hàm tiêu chuẩn là là,f logarit khả năng củ đoói tượng dữ liệu, dây là hàm tốt để mô hình xác suất cho các dối tượng dữ liệu. EM có khả năng khám phá ra nhiều hình dạng cụm khác nhau, tuy nhiên do thời gian lặp của thuật toán khá nhiều nhằm xác định các tham số tốt nên chi phí tính toán của thuật toán là khá cao: có thể nén,có thể sao lưu trong bộ nhớ và có thể hủy bỏ. Trong các của tiến nàym các đối tượng bị hủy bỏ khi biết chắc chắn được nhãn phân cụm của nó, chúng được nén khi không được loại bỏ và thuộc về một cụm quá lớn so với bộ nhớ và chúng sẽ được lưa giữ lại trong các trường hợp còn lại. Nói tóm lại, do PCDL là một ngành phát triển dựa trên sự kết hợp các khái niệm của nhiều ngành như : thống kê, nhận dạng mẫu, CSDL, học máy,... nên có nhiều các phương pháp cũng như thuật toán PCDL. Bảng dữ liệu sau (bảng 2) cho ta thông tin tổng quan về các đặc tính của các phương pháp và thuật toán PCDL, nhằm làm căn cứ cho việc lựa chọn phương pháp khi phát triển các ứng dụng. Thuật toán Tham số vào Thích hợp với Cấu trúc cụm Xử lý phần tử ngoại lai Độ phức tạp tính toán Phương pháp phân cụm phân hoạch K-means Số các cụm Các cụm tách rời Hình cầu Không O(Ikn) PAM Số các cụm Các cụm tách rời, tập dữ liệu nhỏ Hình cầu Không O(Ik(n-k)2) CLARA Số các cụm Tập dữ liệu tương đối lớn Hình cầu Không O(ks2+k(n-k)) CLARANS Số các cụm, số tối đa các láng giềng Tập dữ liệu không gian, chất lượng các cụm tốt hơn PAM và CLARA Hình cầu Không O(kn2) Phương pháp phân cụm phân cấp BIRCH Yếu tố nhánh, đường kính cụm Tập dữ liệu lớn Hình cầu Có O(n) CURE Số các cụm, số cụm đại diện Tập dữ liệu trung bình, hình dạng các cụm bất kỳ Bất kỳ Có O(n2 log n) Phương pháp phân cụm dựa trên mật độ DBSCAN Bán kính của cụm, số tối thiểu các đối tượng trong cụm Các cụm có hình dạng bất kỳ, tập dữ liệu lớn Bất kỳ Có O(n log n) DENCLUE Bán kính của các cụm, số tối thiểu các đối tượng Các cụm có hình dạng bất kỳ, tập dữ liệu lớn Bất kỳ Có O(n log n) OPTICS Bán kính của các cụm (min, max), số tối thiểu các đối tượng Các cụm có hình dạng bất kỳ, tập dữ liệu lớn Bất kỳ Có O(n log n) Các phương pháp phân cụm khác STING Số các Cell trong mức thấp nhất, số các đối tượng trong Cell Tập dữ liệu không gian lớn Giới hạn đứng và các giới hạn ngang Có O(n) WaveCluster Số các Cell cho mỗi chiều, sóng, số ứng dụng biến đổi Các cụm có hình dạng bất kỳ, tập dữ liệu lớn Bất kỳ Có O(n) CLIQUE Kích thước của lưới, số tối thiểu các điểm trong mỗi lưới Tập dữ liệu lớn đa chiều Bất lỳ Có O(n) Scalable EM Các tham số Gauss, giới hạn hội tụ Tập dữ liệu lớn với phân phối đồng nhất xấp xỉ Hình cầu Không O(n) Phân cụm dữ liệu nhờ mạng nơron nhân tạo Trong lịch sử, bộ não đã từng được xem là một dạng máy tính, và ngược lại. Tuy nhiên, điều này chỉ đúng theo nghĩa rộng nhất. Máy tính không phải là mô hình của bộ não (mặc dù có thể mô tả một quá trình suy luận logic như là một chương trình máy tính, hoặc có thể kích thích não bằng một cái máy tính) do chúng đã không được chế tạo với mục đích này. Tuy nhiên, từ xưa, các mạng nơ-ron dùng trong trí tuệ nhân tạo đã được xem là các mô hình đơn giản của hoạt động thần kinh trong não. Một chủ đề của các nghiên cứu hiện nay trong ngành thần kinh học lý thuyết là câu hỏi: mạng nơ-ron cần phức tạp đến đâu và cần có những tính chất gì để có thể tái tạo cái gì đó giống như trí thông minh của con người. Vì vậy người ta đã mô hình hóa một mạng lưới gồm các dây mô hình như các dây thần kinh của bộ não con người và cài vào đó những thuật toán để khám phá ra những tri thức trong kho tàng tri thức của nhân loại. Đó là mạng nơron nhân tạo. CHƯƠNG 2: MẠNG NƠRON NHÂN TẠO Mạng nơron sinh học Khái niệm: Mạng nơron sinh học: là một mạng lưới (plexus) các nơron kết nối hoặc có liên quan về mặc chức năng trực thuộc hệ thần kinh ngoại biên (peripheral nerous system) hay hệ thần kinh trung ương (central nerous system). Trong ngành thần kinh học nó thường được dùng để chỉ một nhóm nơ-ron thuộc hệ thần kinh là đối tượng nghiên cứu khoa học nhất định. Mô hình Mô hình mạng nơron sinh học Mạng nơron nhân tạo Khái niệm: Mạng nơron nhân tạo- ANN (Artifical Neural Network) là một mô phỏng xử lý thông tin, được nghiên cứu ra từ hệ thống thần kinh của sinh vật, giống như bộ não để xử lý thông tin. Nó bao gồm một số lượng lớn các mối gắn kết cấp cao để xử lý các yếu tố làm việc trong mối liên hệ giải quyết vấn đề rõ ràng. ANNs giống như con người, được học bởi kinh nghiệm, lưu những kinh nghiệm hiều biết và sử dụng trong những tình huống phù hợp. Đầu tiên ANN được giới thiệu năm 1943 bởi nhà thần kinh học Warren Mcculloch và nhà logic học Walter Pits. Nhưng với những kĩ thuật trong thời gian này chưa cho phép họ nghiên cứu được nhiều. Những năm gần đây mô phỏng ANN xuất hiện và phát triển. Các nghiên cứu ứng dụng đã được thực hiện trong các ngành: điện, điện tử, kĩ thuật chế tạo, y học, quân sự, kinh tế,..và mới nhất là nghiên cưú ứng dụng trong quản lý dự án xây dựng. Tại Việt Nam việc nghiên cứu ứng dụng ANN vào quản lý xây dựng chỉ mới bắt đầu trong vài năm gần đây và cần được phát triển. Từ đây chúng ta thống nhất với nhau là khi nhắc tới mạng nơ-ron tức là nói mạng nơ-ron nhân tạo. Dưới đây là mô hình toán học một mạng nơ-ron nhân tao: Các tín hiệu vào ( còn gọi là mẫu vào) pi (i=1..R) được đưa tới đầu vào của nơron S tạo thành ma trận tín hiệu vào P. Mỗi đầu vào của nơron S sẽ có một trọng số kí hiệu là ws,i (i=1..R) và các trọng số này tạo thành một ma trận trọng số đầu vào W. Mức ngưỡng q của nơron có thể được biểu diễn trong mô hình toán học bằng hệ số bias b (gọi là thế hiệu dịch). Như vậy tín hiệu vào là nnet sẽ được tính theo công thức sau: (2.1) Viết dưới dạng ma trận sẽ là: (2.2) Xem các biểu thức trên thì ta có thể coi hệ số bias như trọng số của một đầu vào với tín hiệu bằng 1. Có một số loại nơron có thể bỏ qua hệ số bias này. Hàm kích hoạt (activation function) hay còn gọi là hàm truyền (transfer function) được kí hiệu là f sẽ biến đổi tín hiệu đầu vào nnet thành tín hiệu đầu ra nơron a. Ta có biểu thức: a=f(nnet )=f(WP+b) (2.3) Thông thường thì hàm kích hoạt sẽ được chọn bởi người thiết kế tuỳ theo mục đích của mạng. Các trọng số và hệ số bias là các thông số điều chỉnh được của mạng nơron. Chúng được điều chỉnh bởi một số luật học (learning rule). Như vậy quan hệ giữa đầu ra và các đầu vào của nơron sẽ tuỳ thuộc vào việc nơron đó được dùng cho các mục đích cụ thể nào. Đặc điểm Thông thường một mạng nơ-ron bao gồm một hoặc nhiều nhóm các nơ-ron kết nối vật lý với nhau hoặc có liên quan với nhau về chức năng. Một nơ-ron đơn có thể được nối với nhiều nơ-ron khác và tổng số nơ-ron và kết nối trong một mạng có thể là một giá trị cực kì lớn. Các kết nối, gọi là các khớp thần kinh (synapses) thường nối từ các trục (axon) tới các tế bào gai tua thần kinh (dendrite), tuy có thể có các vi mạch và các kết nối khác. Ngoài tín hiệu điện, còn có các dạng tín hiệu khác phát sinh từ việc khuếch tán các chất truyền dẫn. Chúng có ảnh hưởng đối với tín hiệu điện. Do vậy, cũng như các mạng sinh học khác, mạng nơ-ron vô cùng phức tạp. Trong khi hiện nay, một mô tả chi tiết của hệ thần kinh có vẻ như chưa thể đạt được, người ta vẫn ngày càng hiểu tốt hơn về các cơ chế cơ bản. Giữa mạng nơron nhân tạo và mạng nơron sinh học có 3 điểm chung là Mạng được xây dựng bằng các phần tử tính toán đơn giản liên kết lại với nhau một cách phức tạp và hoạt động theo nguyên tắc song song. Chức năng của mạng được xác định qua cấu trúc mạng, quá trình xử lý bên trong các phần tử và mức độ liên kết giữa các phần tử. Mức độ liên kết giữa các phần tử được xác định thông qua quá trình học của mạng ( hay còn gọi là quá trình huấn luyện mạng - training). Điểm khác nhau về căn bản giữa mạng nơron nhân tạo và mạng nơron sinh học là ở tốc độ tính toán, độ phức tạp và tính song song. Tuy xét về tốc độ xử lý của các máy tính hiện đại là cao hơn rất nhiều so với tốc độ xử lý của não bộ con người nhưng bộ não lại có thể đồng thời kích hoạt toàn bộ các nơron để làm nhiều công việc khác nhau. Điều này mạng nơron nhân tạo không thể thực hiện được. Với sự phát triển nhanh chóng của khoa học như hiện nay thì ta có thể hi vọng sẽ có những bước đột phá mới trong lĩnh vực mô phỏng mạng nơron sinh học. Cấu trúc mạng nơ-ron nhân tạo 2.3.1Nút: F (.) ∑ wk3 wk2 wk1 Mỗi Neural (nút) là một đơn vị xử lý thông tin của mạng neural, là yếu tố cơ bản để cấu tạo nên mạng neural. Cấu trúc 1 nơ-ron xi: các tín hiệu input wkp: trọng số của từng input f(.): hàm hoạt động yk: kết xuất của Neural b: thông số ảnh hưởng đến ngưỡng ra của output Mạng nơron nhân tạo thường được cấu tạo thành các lớp gồm lớp vào (input layer) , lớp ra (output layer) và các lớp ẩn (hidden layer). Các nơron trong một lớp chỉ nối với các nơron lớp tiếp theo, không cho phép có các liên kết giữa các nơron trong cùng một lớp. Lớp vào là lớp nhận thông tin từ số liệu gốc. Thông tin này được đưa đến đầu vào của một số hay toàn bộ các nơron của lớp tiếp theo (lớp ẩn). Như vậy mỗi nơron của lớp ẩn sẽ nhận được tín hiệu của một số các nơron lớp vào. Các giá trị này sẽ được nhân với hệ số nhân (trọng số) của các nơron ẩn và đưa vào hàm thế sau khớp nối - PSP (Post Synaptic Potential function) thực hiện chức năng đầu vào để tạo tín hiệu duy nhất net. Chức năng kích hoạt đầu ra được thực hiện bằng hàm kích hoạt a(.) (activation function) hay còn gọi là hàm truyền f(.) (transfer function). Hàm này sẽ nhận tín hiệu đầu vào net để tạo ra tín hiệu đầu ra của nơron (kết xuất của nơron lớp ẩn). Tín hiệu ra của các nơron ẩn lại được đưa đến các nơron của lớp tiếp theo. Quá trình xử lý tương tự cho đến khi tín hiệu được đưa ra tại các nơron lớp ra. Đây chính là tín hiệu đầu ra của mạng. Nó chính là giá trị của các biến cần tìm. Mạng nơron có thể tổ chức theo kiểu liên kết đầy đủ (fully connected) tức là đầu ra của các nơron lớp trước sẽ có liên kết với tất cả các nơron ở lớp tiếp theo hoặc ngược lại theo kiểu không đầy đủ-mỗi đầu ra chỉ liên kết với một số nơron của lớp tiếp theo tuỳ theo chức năng của mạng. Phân loại cấu trúc mạng nơ-ron Mạng dẫn tiến một lớp neuron neuron neuron neuron Đây là cấu trúc mạng neural đơn giản nhất. Mạng neural này chỉ gồm 1 lớp xuất, không có lớp ẩn. Input output Hình: cấu trúc mạng nơ-ron một lớp Mạng dẫn tiến nhiều lớp Hình: Cấu trúc mạng nơ-ron nhiều lớp Mạng neural nhiều lớp có thể giải quyết các bài toán phi tuyến nhờ vào các lớp ẩn. Các lớp ẩn này xen giữa các input bên ngoài và output của mạng. Càng nhiều lớp ẩn thì khả năng mở rộng thông tin càng cao và xử lý tốt mạng có nhiều input và output. Ngoài ra còn có mạng hồi quy và mạng Neural dạng lưới. Các hàm hoạt động Các hàm hoạt động phải có các đặc tinh sau: Hàm bị chặn trên và chặn dưới Hàm có tính đơn điệu Hàm phải có tính liên tục và trơn Trong thực tế thông thường người ta thường chọn các hàm sau: Hàm Threhold 1 nếu u > 0 f (u) = 0 nếu u < 0 b. Hàm piecewwise – linear 1 nếu u > 1/2 f (u) = u nếu 1/2 > u > -1/2 0 nếu u < -1/2 c. Hàm sigmoid (logistic) f (u) = 1 1 + exp (-au) d. Hàm tang- hyperbol f (u) = tanh (u) = eu – e-u eu + e-u Kiến trúc mạng nơ-ron Mạng nơron nhân tạo như đã giới thiệu ở trên là sự liên kết của các nơron nhân tạo. Sự xắp xếp bố trí các nơron và cách thức liên hệ giữa chúng tạo nên kiến trúc mạng nơron. Theo cách sắp xếp nơron thì có kiểu kiến trúc một lớp (single layer) và kiến trúc đa lớp (Multiple layer), còn theo cách liên hệ giữa các nơron thì ta có kiến trúc mạng truyền thẳng (feedforward) và kiến trúc mạng hồi qui (recurrent). Ngoài ra còn một loại liên kết theo sự phân bố của các nơron trong không gian hai chiều trong một lớp, gọi là liên kết bên (lateral connection). Với loại liên kết bên này, Kohonen đã tạo ra loại mạng tự tổ chức (Self-Organizing Neural Network). Theo số lớp Nếu xét về số lớp thì mạng có cấu trúc là mạng nơron một lớp và mạng nơron nhiều lớp Mạng nơron một lớp là mạng chỉ có lớp vào và lớp ra. Đầu vào được đưa trực tiếp đến lớp ra. Mạng này có cấu trúc tương đối đơn giản, nó chủ yếu dùng cho các mạng làm chức năng phân loại và thực hiện các hàm đơn giản. Mạng nơron nhiều lớp là các mạng nơron có thêm một hoặc vài lớp ẩn. Do đó cấu trúc mạng vì vậy mà phức tạp hơn rất nhiều. Tuy nhiên các mạng nơron này lại có khả năng thực hiện các công việc phức tạp hơn. Nó có thể thực hiện được các hàm phân bố ngẫu nhiên với điều kiện thu thập được một tập mẫu tin cậy và đủ lớn. Theo kiểu liên kết của các nơron Xét theo kiểu liên kết của các nơron thì có cấu trúc mạng nơron truyền thẳng và mạng nơron quy hồi Mạng nơron truyền thẳng (feedforward Neural Network) là mạng có cấu trúc mà ở đó các liên kết nơron đi theo một hướng nhất định, không tạo thành đồ thị có chu trình (Directed Acrylic Graph) với các đỉnh là các nơron và các cung là các liên kết giữa chúng. Mạng quy hồi (Recurrent Neural Network) cho phép các liên kết nơron tạo thành chu trình tức là tồn tại những liên kết từ các nơron lớp sau quay trở lai các nơron lớp trước. Trong chu trình này, các tín hiệu ra của nơron lại được truyền ngược lại cho các nơron đã kích hoạt chúng do đó mà mạng hồi quy có khả năng lưu giữ trạng thái trong dưới dạng các ngưỡng kích hoạt ngoài các trọng số liên kết nơron. Mạng hồi quy có thể là hồi quy một lớp hoặc hồi quy nhiều lớp. Theo liên kết bên Loại liên kết bên (lateral connection) thực hiện trên một lớp được gọi là lớp cạnh tranh (competitive layer). Lớp cạnh tranh thường được tổ chức như một lưới nơron hai chiều, và một tập tín hiệu vào sẽ đồng thời được đưa đến tất cả các nơron của lớp. Mỗi nơron của lớp cạnh tranh có một liên kết kích thích (excitatory và có trọng số là dương) với chính nó và có các liên kết ức chế (inhibitory và có trọng số là âm) với các nơron lân cận cùng lớp - - - - - - - + Liên kết bên Nơron thắng Lớp cạnh tranh - - - - - - - + Liên kết bên Nơron thắng Lớp cạnh tranh Hình: Liên kết bên trên lớp cạnh tranh Chúng ta có thể tưởng tượng kiểu liên kết này như một cụm các nơron “cạnh tranh nhau” (competition), mỗi nơron sẽ kích hoạt chính nó đồng thời lại ức chế các nơron khác kế cận. Sau một chu kỳ số trao đổi tín hiệu trong mạng sẽ có các nơron với giá trị đầu vào net lớn hơn so với các nơron khác. Chúng sẽ được coi là các “nơron thắng” (winning neural) và được kích hoạt lên giá trị đầu ra lớn nhất, trong khi những nơron khác bị ức chế (giá trị đầu ra giảm xuống 0). Chính vì vậy đôi khi mạng này còn được gọi là “winner-takes-all”. Quá trình kích hoạt cạnh tranh này gọi là sự tiến hoá (evolution). Một số ứng dụng của mạng nơ-ron Mạng nơ-ron trong phân lớp Mạng nơron là một công cụ rất tốt cho quá trình phân lớp mẫu dữ liệu, có thể kể đến một số mô hình mạng Perceptron, mạng cạnh tranh, hay SOFM. Trong lĩnh vực phân cụm dữ liệu thì mạng nơron cũng có rất nhiều ứng dụng tốt. Đối với phân cụm dữ liệu rõ thì nhiều bài báo nói đến như. Còn trong phân cụm mờ có thể kể đến các kết quả của một số mạng như: mạng ánh xạ đặc trưng tự tổ chức (self-organizing feature maps) do Kohonen đề xuất, mạng Kohonen mờ (fuzzy Kohonen clustering network) do Tsao đề xuất hay mạng Hopfield mờ (fuzzy Hopfield neural network) do Lin đề xuất. Các mạng này đã có sự kết hợp với các công thức của fuzzy c-means để thực hiện quá trình phân cụm. Mạng nơ-ron trong nhận dạng Nhận dạng mẫu là một nghành khoa học mà vai trò của nó là phân lớp các đối tượng thành một số loại hoặc một số lớp riêng biệt. Tuỳ thuộc vào lĩnh vực ứng dụng, các đối tượng có thể ở dạng ảnh, dạng tín hiệu, kí hiệu, nói chung là “mẫu” (pattern). Hiện nay mạng nơron đã được sử dụng rất nhiều vào ngành khoa học này, có thể kể đến một số loại mạng như sau: mạng Perceptron, mạng Adaline, mạng sao vào (Instar)… Mạng nơ-ron trong dự báo Hiện nay phân tích dự báo sử dụng mô hình mạng nơron mờ được ứng dụng rộng rãi trong nhiều lĩnh vực, chẳng hạn như phân tích dự báo một số mặt hàng chiến lược ảnh hưởng đến nền kinh tế Việt Nam và ảnh hưởng của chúng có tác động rất lớn đến các hoạt động kinh tế khác. Đây là hướng nghiên cứu mới đang được các nhà khoa học quan tâm. Mạng nơ-ron và bài toán tối ưu Vấn đề chính ở đây là tìm những thuật toán huấn luyện mạng sao cho góp phần tìm nghiệm cho nhiều lớp bài toán tối ưu toàn cục. Có thể nêu lên các bước sau đây trong việc sử dụng mạng nơron để giải các bài toán tối ưu hoá hay còn gọi là ánh xạ các bài toán tối ưu lên mạng nơron: - Chọn sơ đồ biểu diễn để các đầu ra của các nơron có thể giải mã thành các nghiệm có thể của bài toán tối ưu - Chọn hàm năng lượng sao cho cực tiểu của nó ứng với nghiệm “tốt nhất” của bài toán cần ánh xạ - Gán giá trị cho các tham số của hàm năng lượng - điều này sẽ xác định các trọng số tương đối gán cho các thành phần khác nhau của hàm năng lượng - Rút ra phương trình động học của các nơron (tương ứng với việc xác định các trọng số liên kết và đầu vào ngoài) - Đặt giá trị đầu cho các tín hiệu vào Không có phương pháp trực tiếp ánh xạ các bài toán tối ưu có ràng buộc lên mạng nơron ngoại trừ việc thêm vào hàm mục tiêu các thành phần phạt khi các ràng buộc bị phá vỡ. Trong trường hợp hàm năng lượng được biểu diễn như tổng có trọng của hàm mục tiêu của bài toán và các thành phần phạt. Tiến trình học Tiến trình học là tiến trình quan trọng của con người, nhờ học mà bộ não ngày càng tích luỹ những kinh nghiệm để thích nghi với môi trường và xử lý tình huống tốt hơn. Mạng neural xây dựng lại cấu trúc bộ não thì cần phải có khả năng nhận biết dữ liệu thông qua tiến trình học, với các thông số tự do của mạng có thể thay đổi liên tục bởi những thay đổi của môi trường và mạng neural ghi nhớ giá trị đó. Huấn luyện ANN để thực hiện một ứng dụng cụ thể là điều chỉnh, xác lập các giá trị trọng số liên kết - còn được gọi là bộ trọng số kết nối của mạng (ký hiệu là W) - giữa các neuron trong mạng và của các bias. Trong học giám sát, các cặp tín hiệu vào ra được dùng để huấn luyện mạng sao cho tín hiệu ra của mạng tiệm cận tới tín hiệu ra mong muốn của hệ thống Hình tiến trình học của mạng nơ-ron Trong quá trình học, giá trị đầu vào được đưa vào mạng và theo dòng chảy trong mạng tạo thành giá trị ở đầu ra. Tiếp đến là quá trình so sánh giá trị tạo ra bởi mạng Neural với giá trị ra mong muốn. Nếu hai giá trị này giống nhau thì không thay đổi gì cả. Tuy nhiên, nếu có một sai lệch giữa hai giá trị này vượt quá giá trị sai số mong muốn thì đi ngược mạng từ đâu ra về đàu vào để thay đổi một số kết nối. Đây là một quá trình lặp liên tục và có thể không dừng khi không tìm các giá trị w sao cho đầu ra tạo bởi mạng Neural bằng đúng đầu ra mong muốn. Do đó trong thực tế người ta phải thiết lập tiêu chuẩn dựa trên một giá trị sai số nào đó của hai giá trị này, hay dựa trên một số lần lặp xác định. Để tiện cho việc trình bày, ta ký hiệu y là giá trị kết xuất của mạng Neural, t là giá trị ra mong muốn, e là sai lệch giữa hai giá trị này: e = t – y CHƯƠNG 3: SOM VÀ ỨNG DỤNG Tổng quan về SOM SOM, viết tắt của Selt Organized Map (bản đồ tự tổ chức), còn được biết đến là SOFM (Self Organized Feature Map) là một trong những mô hình biến dạng của mạng nơ-ron. SOM được Kohonen phát triển vào những năm 80, nên cũng thường được gọi là mạng Kohonen. SOM được dùng để gom cụm dữ liệu (data clustering) tức là học không có hướng dẫn (unsupervised learning) Cấu tạo của SOM Cũng như mạng nơ-ron khác, các đơn vị cơ bản của SOM là các nơ-ron. Mỗi nơ-ron sẽ có đầu vào, đầu ra. Trong SOM, tùy thuộc nơ-ron nằm ở lớp nào mà cấu trúc của nó có thể khác nhau. Một cách hình thức,SOM thường có hai lớp: lớp đầu vào (input layer) và lớp Kohonen Kohonen layer). Một trong những khía cạnh thú vị nhất đó là SOM là một dạng của thuật toán học để phân lọai dữ liệu huấn luyện mà không cần bất cứ sự giám sát bên ngoài nào so với các giải thuật “học có giám sát” truyền thống. Thế nên SOM còn được xem là một giải thuật học không có giám sát. Các nơ-ron của lớp đầu vào tương ứng với một thành phần trong vector đặc trưng đang xét. Ví dụ nếu xét dữ liệu có vector đặc trưng là 4 thành phần thì lớp đầu vào sẽ có 4 nơ-ron. Mỗi nơ-ron của lớp đầu vào được nối với tất cả các nơ-ron của lớp Kohonen. Các nơ-ron trong lớp Kohonen được tổ chức thành một không gian n chiều. N được gọi là số chiều của SOM. Ví dụ N = 2: lớp Kohonen là một lưới 2 chiều các nơ-ron. Với N = 3: lớp Kohonen là một khối 3 chiều các nơ-ron. Mỗi nơ-ron thuộc lớp Kohonen ngoài các giá đầu vào, đầu ra còn có vector trọng số liên kết với các nơ-ron thuộc lớp đầu vào. Hay nói cách khác, mỗi nơ-ron của lớp Kohonen sẽ có thể thêm một vector trọng số N chiều. Có thể xem mỗi nơ-ron trong lớp Kohonen như là một đại diện cho một cụm với vector trọng số chính là vector trọng tâm của cụm đó. Thực sự điều này không hẳn lúc nào cũng như vậy mà cần có sự linh hoạt trong việc xác đinh cầu hình (số chiều) và số nơ-ron trong lớp Kohonen (đây chỉ là một gợi ý cho những ai chưa biết về SOM trong cài đặt sau này) Thuật toán học trên SOM Thuật giải huấn luyện SOM có thể được mô tả theo các bước cơ bản như sau: Khởi tạo: Các vector trọng số cho từng nút trong mạng được khởi tạo. Các giá trị khởi tạo này thường được chọn một cách ngẩu nhiên và thỏa tiêu chuẩn đủ nhỏ. Chọn phần tử đại diện: Một vector sẽ được chọn ngẫu nhiên từ tập huấn luyện và trở thành phần tử đại diện của nhóm. Tìm mẫu khớp tốt nhất (MBU) - phần tử neuron chiến thắng: Mỗi nút trên mạng sẽ được kiểm tra để tính xem nút nào có trọng số gần với vector nhập nhất. Phần tử chiến thắng được xem là phần tử so khớp tốt nhất (BMU: Best Matching Unit). Thuật giải tìm mẫu khớp tốt nhất được thực hiện như sau: Duyệt tất cả các nút và tính khoảng cách Euclide giữa vector trọng số của mỗi nút và vector nhập hiện hành. Công thức để tính khoảng cách Euclide được cho như sau: V: vector nhập hiện hành W: vector trọng số của phần tử được chọn Nút có vector trọng số gần nhất với giá trị của vector nhập sẽ đựoc chọn là MBU Xây dựng các phần tử lân cận: Bán kính lân cận của MBU sẽ được tính lại. Bán kính được xác định lớn nhất thường sẽ là bán kính của mạng, nhưng sau đó giá trị này sẽ giảm dần sau những bước thực hiện. Tất cả những phần tử nằm trong bán kính trên sẽ được xem là phần tử lân cận của BMU. Trong mỗi vòng lặp, sau khi MBU được xác định bước tiếp theo là thực hiện lại việc tính toán trên các nút để xây dựng lại tập các phần tử lân cận mới của MBU. Các vector trọng số của các phần tử lân cận này sẽ được cập nhật lại ở bước tiếp theo. Các phần tử lân cận của MBU Tập các phần tử lân cận của MBU sẽ được cập nhật lại bằng cách duyệt qua các phần tử nằm trong bán kính lân cận hay vector khoảng cách của MBU. Đặc tính duy nhất của thuật toán học Kohonen là vùng lân cận của MBU được xây dựng trên vector khoảng cách sẽ được co lại sau một số lần lặp nhất định. Điều này được thực hiện bằng cách co lại bán kính của vùng lân cận theo số lần lặp. Phép co sẽ được thực hiện theo hàm mũ nội suy sau: Biểu thức (5): hàm mũ nội suy của phép co σ: chiều rộng của tập dữ liệu nhập tại thời điểm t σ0: chiều rộng của tập dữ liệu nhập tại thời điểm t0 λ: hằng số thời gian t: là bước lặp hiện tại σ0 được tính bằng công thức sau: σ0 = max(Width, Height)/2 Width: chiều rộng của mạng Kohonen Height: chiều cao của mạng Kohonen Giá trị của hằng số λ phụ thuộc vào σ và số lần lặp để chạy giải thuật. Nó được tính theo công thức sau: λ = N/log(σ0) N: số lần lặp để chạy giải thuật λ và σ sẽ được dùng để tính bán kính lân cận trong mỗi lần lặp của giải thuật. Một ví dụ về sự co lại của bán kính lân cận thực hiện theo công thức trên. Khi bán kính lân cận đã được xác định, việc xác định các phần tử lân cận của MBU sẽ được thực hiện đơn giản bằng cách duyệt tất cả các phần tử trong mạng để xem nó có nằm trong bán kính lân cận hay không. Hiệu chỉnh trọng số của các phần tử lân cận – quá trình học của giải thuật SOM: Trọng số của các phần tử lân cận (được xác định ở bước d) bao gồm cả BMU sẽ được điều chỉnh để chúng có giá trị gần giống với giá trị của vector nhập hơn. Phần tử càng gần với MBU, thì trọng số của nó sẽ càng đễ bị thay đổi nhiều hơn. Các vector trọng số sẽ được hiệu chỉnh theo công thức sau: t: bước lặp hiện tại L: tốc độ học (sẽ giảm dần theo số lần lặp) Biểu thức trên cho thấy trọng số của một nút sau khi hiệu chỉnh chính là giá trị trọng cũ W của nó cộng thêm phần giá trị khác biệt giữa trọng W và vector nhập V theo hệ số tốc độ học. Hàm nội suy tốc độ học L(t) cho mỗi bước lặp đựơc tính theo công thức sau: Biểu thức (7): hàm mũ nội suy của tốc độ học L0: Giá trị khởi tạo ban đầu của tốc độ học. λ: hằng số thời gian Càng tiến dần về điểm giữa thì tốc độ học sẽ càng giống với hàm mũ nội suy của phép co - biểu thức (5) Tốc độ học sẽ được nội suy dần theo tốc độ học và giá trị của hàm sẽ tiến dần về không khi số lần lặp đạt đến những bước cuối cùng. Dạng cải tiến của hàm hiệu chỉnh vector trọng số: Ta nhận thấy không chỉ tốc độ học phải nội suy theo thời gian học mà tính hiệu quả của phép học SOM còn phải tương ứng thay đổi theo khoảng cách của nút hiện tại đến neuron chiến thắng. Đặc điểm này cho thấy trong quá trình học các neuron trong vùng lận cận càng ở xa neuron chiến thắng sẽ học càng ít hơn. Về mặt lý tưởng , số lần học phải giảm dần theo khoảng cách thỏa mãn hàm nội suy Gaussian được cho bởi đồ thị sau: è Lúc này hàm hiệu chỉnh vector trọng số được biểu diễn lại như sau: q: Hàm nội suy theo thời gian học. Nó thể hiện sự tác động của khoảng cách đối với quá trình học và được tính theo công thức sau: dist: là khoảng cách từ một neuron đến neuron chiến thắng. σ: chiều rộng của tập huấn luyện tại thời điểm (được tính theo công thức (5)). Vòng lặp: Lặp lại bước b cho đến khi giải thuật tối ưu hoặc đạt đến số lần lặp xác định N cho trước Phân tích: Có 3 điểm cần lưu ý trong thuật toán học: Độ đo để xác định nơ-ron chiến thắng: dùng độ đo Euclide Cập nhật trọng số: các nơ-ron ở càng xa nơ-ron chiến thắng thì càng ít bị ảnh hưởng bới nơ-ron chiến thắng. Có thể sử dụng công thức sau, với Sigma là một hàm khoảng cách hình học, càng xa thì càng nhỏ. Winew = Wiold + Sigma*(Wwinner - V). Điều kiện dừng: có thể là dựa trên số lần lặp hay số mẫu học hay độ đo cân bằng của mạng sau một số lần lặp Lưu ý là một mẫu học có thể được đưa vào học nhiều lần. Hàm số Sigma có thể phụ thuộc vào thời điểm lặp, nghĩa là càng về cuối thì mức ảnh hưởng của nó càng cao/thấp. Ưu và nhược điểm của SOM Ưu điểm Giải thuật SOM được cài đặt tương đối đơn giản và dễ hiểu. SOM được sử dụng trong việc gom cụm các loại dữ liệu và trực quan hóa chúng trên bản đồ nhằm đơn giản hóa quá trình khai thác và thu thâp dữ liệu Nhược điểm Bên cạnh những ưu điểm của mình, SOM còn có một số nhược điểm: Mất mát thông tin Chi phí cho việc tính toán khá cao khi số chiều của dữ liệu tăng lên Tổng kết Khai khá dữ liệu là vấn đề rất cần thiết trong cuộc sống của chúng ta. Từ khai phá dữ liệu chúng ta có thể phát hiện ra tri thức. Đó là vấn đề cốt lõi của chúng ta. Có rất nhiều cách để con người khai phá được dữ liệu và một trong những cách đó là phân cụm dữ liệu. Có rất nhiều thuật toán phân cụm dữ liệu và trong đề tài này đã trình bày được một số thuật toán trong phân cụm dữ liệu. Đề tài tập trung vào ứng dụng của mạng nơ-ron để phân cụm trong thuật toán SOM. Do giới hạn về thời gian nên trong đề tài chưa được hoàn thiện. Trong thời gian tới đây tôi sẽ tiếp tục nghiên cứu để hoàn thiện đề tài và ứng dụng vào thực tế. Xin chân thành cảm ơn thầy giáo Nguyễn Tân Ân đã tận tình giúp đỡ em trong quá trình làm đề tài này.