KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU
Khai phá dữ liệu (Data Mining) là gì?
Sự phát triển mạnh mẽ của công nghệ điện tử và truyền thông đã làm tăng khả năng lưu trữ thông tin, dẫn đến sự gia tăng lượng dữ liệu trên các thiết bị nhớ Sự ra đời và phát triển của cơ sở dữ liệu đã tạo ra một "bùng nổ" thông tin toàn cầu, đồng thời khởi nguồn cho khái niệm "khủng hoảng" trong phân tích dữ liệu để cung cấp thông tin chất lượng cho các quyết định trong tổ chức tài chính, thương mại và khoa học Như John Naisbett đã cảnh báo, "Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức."
Dữ liệu không phải là yếu tố quan trọng nhất, mà chính là thông tin và tri thức được khai thác từ dữ liệu Do đó, Khai phá dữ liệu (Data Mining) đã ra đời như một lĩnh vực khoa học mới, nhằm tự động hóa quá trình tìm kiếm và khai thác những thông tin hữu ích tiềm ẩn trong các cơ sở dữ liệu.
Khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích vượt trội so với các công cụ phân tích dữ liệu truyền thống Hiện nay, nó được ứng dụng rộng rãi trong nhiều lĩnh vực như phân tích dữ liệu hỗ trợ ra quyết định, điều trị y học, tin-sinh học, thương mại, tài chính, bảo hiểm, text mining và web mining.
Khai phá dữ liệu là một lĩnh vực đang phát triển nhanh chóng với nhiều phương pháp và ứng dụng khác nhau Do đó, có nhiều quan điểm đa dạng về khái niệm này Ở mức độ trừu tượng, khai phá dữ liệu có thể được định nghĩa như một quá trình khám phá và phân tích thông tin từ tập dữ liệu lớn để rút ra những kiến thức hữu ích.
“Khai phá dữ liệu là quá trình tìm kiếm, phát hiện các tri thức mới, hữu ích tiềm ẩn trong cơ sở dữ liệu lớn”.
Quy trình khai phá dữ liệu
Khám phá tri thức trong CSDL (KDD) là mục tiêu chính của khai phá dữ liệu, vì vậy hai khái niệm này thường được coi là tương đương Tuy nhiên, nếu phân tích kỹ lưỡng, khai phá dữ liệu thực sự là một bước quan trọng trong quy trình KDD.
Khám phá tri thức trong CSDL là lĩnh vực liên quan đến nhiều ngành như:
Tổ chức dữ liệu, xác suất, thống kê, lý thuyết thông tin, học máy, cơ sở dữ liệu (CSDL), thuật toán, trí tuệ nhân tạo, tính toán song song và hiệu năng cao là những kỹ thuật chính áp dụng trong lĩnh vực công nghệ thông tin hiện đại.
Quá trình khám phá tri thức có thể phân ra các công đoạn sau:
Trích lọc dữ liệu là quá trình lựa chọn các tập dữ liệu cần khai phá từ những nguồn dữ liệu lớn như cơ sở dữ liệu, kho dữ liệu và kho lưu trữ dữ liệu, dựa trên các tiêu chí nhất định.
Tiền xử lý dữ liệu là bước quan trọng trong việc làm sạch và chuẩn hóa dữ liệu, bao gồm xử lý dữ liệu thiếu, dữ liệu nhiễu và không nhất quán Quá trình này cũng bao gồm tổng hợp dữ liệu thông qua nén, nhóm dữ liệu, xây dựng histograms, lấy mẫu và tính toán các tham số đặc trưng Sau khi hoàn tất, dữ liệu sẽ trở nên nhất quán, đầy đủ và được rút gọn, giúp nâng cao chất lượng phân tích và quyết định.
Biến đổi dữ liệu là quá trình chuẩn hóa và làm mịn dữ liệu, giúp dữ liệu trở nên phù hợp nhất cho việc áp dụng các kỹ thuật khai phá.
Khai phá dữ liệu là quá trình áp dụng các kỹ thuật phân tích, chủ yếu là học máy, để trích xuất thông tin và nhận diện các mẫu tin cùng mối quan hệ đặc biệt trong dữ liệu Đây là bước quan trọng và tốn thời gian nhất trong toàn bộ quy trình KDD Sau đó, các mẫu thông tin và mối quan hệ đã được phát hiện sẽ được chuyển đổi và biểu diễn dưới dạng dễ hiểu cho người sử dụng, như đồ thị, cây, bảng biểu, hay luật Bước này cũng bao gồm việc đánh giá các tri thức đã khai phá theo những tiêu chí nhất định.
Hình 1.1 dưới đây mô tả các công đoạn của KDD
Hình 1.1 Các bước thực hiện quá trình khai phá dữ liệu
Dữ liệu Tiền sử lý dữ liệu
Dữ liệu tiền xử lý
Khai phá dữ liệu Đánh gía và giải thích
Các mẫu Biểu diễn dữ liệu Tri thức
Các kỹ thuật khai phá dữ liệu
Theo quan điểm máy học (Machine Learning) thì các kỹ thuật khai phá dữ liệu bao gồm:
Học có giám sát (Supervised Learning) là phương pháp phân loại các đối tượng trong cơ sở dữ liệu bằng cách sử dụng một tập hợp các ví dụ huấn luyện, trong đó thông tin về nhãn lớp đã được biết đến.
Học không có giám sát (Unsupervised Learning) là phương pháp phân loại các đối tượng thành các cụm tương đồng mà không cần thông tin về nhãn lớp trước đó.
Học nửa giám sát (Semi-Supervised Learning) là phương pháp phân loại các đối tượng thành các lớp dựa trên một tập hợp nhỏ các ví dụ huấn luyện đã được gán nhãn Phương pháp này tận dụng thông tin từ các nhãn lớp đã biết để cải thiện độ chính xác trong việc phân loại các đối tượng chưa được gán nhãn.
Nếu căn cứ vào các lớp bài toán cần giải quyết, thì khai phá dữ liệu bao gồm các kỹ thuật sau
Phân lớp và dự đoán là quá trình xếp các đối tượng vào những lớp đã biết, như phân loại bệnh nhân hay loài thực vật Phương pháp này thường áp dụng các kỹ thuật học máy như cây quyết định và mạng nơ-ron nhân tạo Phân lớp và dự đoán còn được gọi là học có giám sát, giúp cải thiện độ chính xác trong việc xác định các nhóm đối tượng.
Phân cụm (Clustering/Segmentation): Là việc xếp các đối tượng theo từng cụm tự nhiên
Luật kết hợp (Association rules) là phương pháp phát hiện các quy luật thể hiện tri thức một cách đơn giản Chẳng hạn, một ví dụ điển hình là “70% nữ giới vào siêu thị mua phấn thì có tới 80% trong số họ cũng mua thêm son.”
Phân tích hồi quy là phương pháp học một hàm ánh xạ từ tập dữ liệu để dự đoán một biến có giá trị thực Nhiệm vụ của phân tích hồi quy tương tự như phân lớp, nhưng điểm khác biệt chính là thuộc tính dự báo trong hồi quy là liên tục thay vì rời rạc.
Phân tích các mẫu theo thời gian (Sequential/Temporal patters): Tương tự như khai phá luật kết hợp nhưng có quan tâm đến tính thứ tự theo thời gian
Mô tả khái niệm và tổng hợp (Concept description and summarization):
Thiên về mô tả, tổng hợp và tóm tắt các khái niệm Ví dụ: tóm tắt văn bản
Hiện nay, các kỹ thuật khai phá dữ liệu có khả năng xử lý nhiều loại dữ liệu khác nhau, bao gồm cơ sở dữ liệu giao tác, cơ sở dữ liệu quan hệ hướng đối tượng, dữ liệu không gian và thời gian, cơ sở dữ liệu đa phương tiện, cùng với dữ liệu văn bản và web.
Các ứng dụng của khai phá dữ liệu
Khai phá dữ liệu là một lĩnh vực đa ngành, liên quan đến các lĩnh vực như hệ cơ sở dữ liệu, thống kê và trực quan hóa Tùy thuộc vào phương pháp tiếp cận, khai phá dữ liệu có thể sử dụng nhiều kỹ thuật khác nhau, bao gồm mạng nơ-ron, phương pháp hệ chuyên gia, lý thuyết tập thô và tập mờ So với các phương pháp truyền thống, khai phá dữ liệu mang lại nhiều ưu thế nổi bật.
Phương pháp học máy thường được sử dụng cho các cơ sở dữ liệu (CSDL) ổn định và có kích thước vừa phải Ngược lại, kỹ thuật khai thác dữ liệu phù hợp hơn với các CSDL có nhiễu, dữ liệu không đầy đủ hoặc đang trong quá trình biến đổi liên tục.
Phương pháp hệ chuyên gia dựa trên tri thức từ các chuyên gia, cung cấp dữ liệu có độ sâu cao hơn so với dữ liệu trong CSDL khai phá và chỉ tập trung vào các trường hợp quan trọng Giá trị và tính hữu ích của các mẫu phát hiện từ hệ chuyên gia cũng được xác nhận bởi các chuyên gia.
Phương pháp thống kê là nền tảng lý thuyết quan trọng trong khai phá dữ liệu, nhưng khi so sánh, có thể nhận thấy rằng các phương pháp thống kê vẫn tồn tại một số điểm yếu mà khai phá dữ liệu có khả năng khắc phục hiệu quả.
Khai phá dữ liệu hiện đang được áp dụng rộng rãi trong nhiều lĩnh vực như marketing, tài chính, ngân hàng, bảo hiểm, khoa học, y tế và an ninh internet Nhiều tổ chức và công ty lớn trên thế giới đã thành công trong việc tích hợp kỹ thuật này vào hoạt động sản xuất và kinh doanh, mang lại lợi ích to lớn Các công ty phần mềm hàng đầu như Oracle và IBM cũng đang chú trọng phát triển các công cụ khai phá dữ liệu, với những ứng dụng nổi bật như Intelligence Miner.
Các ứng dụng này được phân loại thành ba nhóm khác nhau, bao gồm quản lý khách hàng và ứng dụng chuyên dụng cho việc phát hiện và xử lý lỗi trong hệ thống mạng.
Nhóm 1: Phát hiện gian lận (Fraud detection)
Gian lận là một vấn đề nghiêm trọng trong ngành viễn thông, gây thiệt hại hàng tỷ đồng mỗi năm Có hai hình thức gian lận phổ biến mà các công ty viễn thông thường gặp phải.
Trường hợp thứ nhất xảy ra khi một khách hành đăng ký thuê bao với ý định không bao giờ thanh toán khoản chi phí sử dụng dịch vụ
Trường hợp thứ hai liên quan đến một thuê bao hợp lệ nhưng lại có một số hoạt động bất hợp pháp gây ra bởi một người khác
Các ứng dụng này hoạt động theo thời gian thực, sử dụng dữ liệu chi tiết từ cuộc gọi Khi phát hiện cuộc gọi nghi ngờ gian lận, hệ thống sẽ ngay lập tức thực hiện các biện pháp ứng phó, chẳng hạn như hiển thị cảnh báo hoặc từ chối cuộc gọi nếu xác định đó là cuộc gian lận.
Hầu hết các phương thức nhận diện gian lận dựa vào việc so sánh hành vi sử dụng điện thoại của khách hàng trong quá khứ với hành vi hiện tại, nhằm xác định tính hợp lệ của cuộc gọi.
Nhóm 2: Các ứng dụng quản lý và chăm sóc khách hành
Các công ty viễn thông xử lý lượng lớn dữ liệu về thông tin khách hàng và chi tiết cuộc gọi, cho phép họ nhận diện đặc điểm của khách hàng Từ đó, các doanh nghiệp có thể xây dựng chính sách chăm sóc khách hàng phù hợp và phát triển các chiến lược tiếp thị hiệu quả.
Khai phá dữ liệu là một ứng dụng quan trọng trong việc phát hiện các luật kết hợp giữa các dịch vụ viễn thông mà khách hàng sử dụng Hiện nay, một khách hàng có thể sử dụng nhiều dịch vụ khác nhau trên điện thoại như gọi điện, truy cập internet, tra cứu thông tin từ hộp thư tự động, nhắn tin, và gọi dịch vụ 108 Bằng cách phân tích cơ sở dữ liệu khách hàng, chúng ta có thể khám phá các mối liên hệ trong việc sử dụng dịch vụ, từ đó đưa ra các quy luật như việc khách hàng gọi điện thoại quốc tế.
Các công ty viễn thông có thể tối ưu hóa vị trí đăng ký dịch vụ bằng cách phân tích các quy luật liên quan đến truy cập internet Ví dụ, điểm đăng ký điện thoại quốc tế nên được đặt gần với điểm đăng ký internet để thuận tiện cho người dùng.
Một ứng dụng quan trọng trong chiến lược marketing là sử dụng kỹ thuật khai phá luật kết hợp từ dữ liệu để xác định các thành phố và tỉnh thường xuyên liên lạc với nhau qua điện thoại Ví dụ, có thể nhận diện các thành phố phổ biến như Cần Thơ, HCM và Hà Nội Thông tin này rất hữu ích cho việc lập kế hoạch chiến lược tiếp thị và xây dựng các vùng cước phù hợp.
Sự thay đổi nhà cung cấp dịch vụ (customer churn) đang trở thành một vấn đề nghiêm trọng đối với các công ty viễn thông, đặc biệt là trong lĩnh vực di động, ảnh hưởng đến tốc độ phát triển thuê bao và doanh thu Để đối phó, nhiều nhà cung cấp dịch vụ di động đã triển khai các chương trình khuyến mãi hấp dẫn, khiến khách hàng thường xuyên chuyển đổi nhà cung cấp để tận dụng lợi ích Tuy nhiên, với sự hỗ trợ của các kỹ thuật khai phá dữ liệu, các công ty có thể phân tích dữ liệu lịch sử để xác định quy luật và dự đoán khách hàng có ý định rời bỏ dịch vụ Bằng cách áp dụng các phương pháp như cây quyết định và mạng nơ-ron nhân tạo trên dữ liệu cước, dữ liệu chi tiết cuộc gọi và dữ liệu khách hàng, các công ty viễn thông có thể phát hiện sớm ý định rời mạng của khách hàng, từ đó đưa ra các chiến lược phù hợp nhằm giữ chân họ.
Phân lớp khách hàng là một ứng dụng phổ biến, sử dụng kỹ thuật học trên cây quyết định để phân loại khách hàng dựa trên dữ liệu và chi tiết cuộc gọi Bằng cách này, chúng ta có thể xác định quy luật phân biệt giữa khách hàng thuộc đối tượng kinh doanh và nhà riêng.
Luật 1: Nếu không quá 43% cuộc gọi có thời gian từ 0 đến 10 giây và không đến 13% cuộc gọi vào cuối tuần thì đó là khách hàng kinh doanh
Luật 2: Nếu trong 2 tháng có các cuộc gọi đến hầu hết từ 3 mã vùng giống nhau và dưới 56,6% cuộc gọi từ 0-10 giây thì đó là khách hàng riêng
Trên cơ sở tìm được các luật tương tự như vậy, ta dễ dàng phân loại khách hàng, từ đó có chính sách phân khúc thị trường hợp lý
Nhóm 3: Các ứng dụng phát hiện và cô lập lỗi trên hệ thống mạng viễn thông (Network fault isolation)
Một số thách thức đặt ra cho việc khai phá dữ liệu
- Số đối tượng trong cơ sở dữ liệu thường rất lớn.
- Số chiều (thuộc tính) của cơ sở dữ liệu lớn.
- Dữ liệu và tri thức luôn thay đổi có thể làm cho các mẫu đã phát hiện không còn phù hợp.
- Dữ liệu bị thiếu hoặc nhiễu.
- Quan hệ phức tạp giữa các thuộc tính.
- Giao tiếp với người sử dụng và kết hợp với các tri thức đã có.
- Tích hợp với các hệ thống khác
Kết luận chương
Khai phá dữ liệu là một lĩnh vực khoa học mới, tập trung vào việc tự động hóa quá trình khai thác thông tin và tri thức hữu ích từ các cơ sở dữ liệu Điều này giúp giải quyết vấn đề ngày càng gia tăng: "Ngập trong dữ liệu mà vẫn đói tri thức" Nghiên cứu và ứng dụng thành công trong khai phá dữ liệu chứng minh rằng đây là một lĩnh vực tiềm năng, mang lại nhiều lợi ích và vượt trội hơn so với các công cụ phân tích dữ liệu truyền thống.
Chương 1 cung cấp cái nhìn tổng quan về khai phá dữ liệu, bao gồm tóm tắt quy trình khai thác, các phương pháp áp dụng, ứng dụng thực tiễn và những thách thức mà lĩnh vực này đang đối mặt.
PHÂN CỤM DỮ LIỆU VÀ CÁC GIẢI THUẬT THEO TIẾP CẬN PHÂN CẤP
2.1 Phân cụm dữ liệu (Data Clustering) là gì?
Phân cụm dữ liệu (PCDL) là một phương pháp quan trọng trong khai phá dữ liệu (Data Mining) và khám phá tri thức (KDD) Mục tiêu chính của phân cụm là tổ chức các đối tượng thành các nhóm, sao cho các đối tượng trong cùng một nhóm có tính tương đồng cao, trong khi độ bất tương đồng giữa các nhóm lại lớn Qua đó, PCDL cung cấp thông tin và tri thức hữu ích cho quá trình ra quyết định.
Data mining là một quá trình tìm kiếm, chắt lọc các tri thức mới, tiềm ẩn, hữu dụng trong tập dữ liệu lớn
Phân cụm dữ liệu, còn gọi là phân tích cụm hay phân tích phân đoạn, là một kỹ thuật trong khai thác dữ liệu (Data mining) nhằm tìm kiếm và nhóm các đối tượng tương tự trong tập dữ liệu lớn Kỹ thuật này giúp phát hiện các lớp đối tượng giống nhau, từ đó cung cấp thông tin và tri thức quan trọng cho quá trình ra quyết định.
Một cụm là tập hợp các đối tượng dữ liệu mà các phần tử trong cùng một cụm có sự tương đồng với nhau và khác biệt với các đối tượng trong các cụm khác Cụm dữ liệu có thể được coi là một nhóm trong nhiều ứng dụng khác nhau.
Số lượng cụm dữ liệu có thể được xác định dựa trên kinh nghiệm hoặc tự động trong quá trình thực hiện phương pháp phân cụm.
Chúng ta có thể minh hoạ vấn đề phân cụm như Hình 2.1 sau đây:
Hình 2.1: Mô phỏng vấn đề phân cụm dữ liệu
Trong hình trên, sau khi phân cụm, chúng ta có bốn cụm khác nhau Các phần tử "gần nhau" hay "tương tự" được xếp vào cùng một cụm, trong khi các phần tử "xa nhau" hay "phi tương tự" thuộc về các cụm khác nhau Để minh họa rõ hơn cho vấn đề này, hãy quan sát các hình ảnh sau.
Hình 2.2: Dữ liệu nguyên thủy
Hình 2.7: Kết quả của quá trình phân cụm
Các hình từ 2.2 đến 2.7 là thể hiện quá trình phân cụm từ khi“bắt đầu” cho đến khi “kết thúc”
Trong PCDL, khái niệm "Concept Clustering" cho phép nhóm hai hoặc nhiều đối tượng vào một cụm khi chúng chia sẻ định nghĩa chung hoặc gần gũi với các khái niệm đã được mô tả Điều này cho thấy PCDL không áp dụng khái niệm "tương tự" như đã được đề cập trước đó.
Trong học máy, phân cụm dữ liệu là một vấn đề học không có giám sát, nhằm tìm kiếm cấu trúc trong tập dữ liệu mà không cần biết trước thông tin về lớp hay dữ liệu huấn luyện Trong nhiều trường hợp, phân lớp (Classification) được coi là học có giám sát, trong khi phân cụm dữ liệu đóng vai trò quan trọng trong quá trình phân lớp, giúp khởi tạo các lớp bằng cách xác định nhãn cho các nhóm dữ liệu.
Trong phân cụm dữ liệu, một vấn đề phổ biến là sự tồn tại của dữ liệu "nhiễu" do quá trình thu thập không chính xác hoặc thiếu đầy đủ Để khắc phục tình trạng này, việc xây dựng chiến lược tiền xử lý dữ liệu là cần thiết nhằm loại bỏ hoặc giảm thiểu "nhiễu" trước khi tiến hành phân tích Dữ liệu "nhiễu" có thể bao gồm các đối tượng không chính xác hoặc thiếu thông tin về một số thuộc tính Một kỹ thuật phổ biến để xử lý nhiễu là thay thế giá trị thuộc tính của đối tượng "nhiễu" bằng giá trị tương ứng của đối tượng dữ liệu gần nhất.
Phân cụm dữ liệu là một vấn đề khó, vì rằng người ta phải đi giải quyết các vấn đề con cơ bản như sau:
- Xây dụng hàm tính độ tương tự
- Xây dựng các tiêu chuẩn phân cụm
- Xây dụng mô hình cho cấu trúc cụm dữ liệu
- Xây dựng thuật toán phân cụm và xác lập các điều kiện khởi tạo
- Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm
Phân cụm dữ liệu là một bài toán trong lĩnh vực học máy không giám sát, đang được áp dụng phổ biến để khai thác thông tin giá trị từ dữ liệu.
Phân cụm dữ liệu là quá trình chia một tập dữ liệu thành các cụm, trong đó các đối tượng trong cùng một cụm có sự tương đồng cao Để thực hiện điều này, cần xác định một phép đo khoảng cách hoặc độ tương tự giữa các đối tượng Một hàm tính độ tương tự cho phép đánh giá mức độ tương đồng giữa các cặp đối tượng; giá trị cao hơn cho thấy sự tương đồng lớn hơn Ngược lại, hàm tính độ phi tương tự lại tỉ lệ nghịch với độ tương tự.
2.2 Thế nào là phân cụm tốt?
Một phương pháp hiệu quả sẽ tạo ra các cụm dữ liệu chất lượng cao, với sự tương đồng cao trong cùng một lớp (intra-class) và sự tương đồng thấp giữa các lớp khác nhau (inter-class).
- Chất lượng của kết quả gom cụm phụ thuộc vào: độ đo tương tự sử dụng và việc cài đặt độ đo tương tự
- Chất lượng của phương pháp gom cụm cũng được đo bởi khả năng phát hiện các mẫu bị che (hidden patterns)
2.3 Bài toán phân cụm dữ liệu
Bài toán phân cụm dữ liệu thường được hiểu là một bài toán học không giám sát và được phát biểu như sau:
Cho tập X = {x 1 , , x n } gồm n đối tượng dữ liệu trong không gian p-chiều, p xi R Ta cần chia X thành k cụm đôi một không giao nhau: k i
C C, i j, nhằm đảm bảo rằng các đối tượng trong cùng một cụm có sự tương đồng nhất định, trong khi các đối tượng thuộc các cụm khác nhau lại có sự khác biệt rõ rệt theo một cách nhìn nhất định.
Số lượng cụm có thể được xác định trước hoặc thông qua phương pháp phân cụm Để thực hiện phân cụm, cần xác định mức độ tương tự giữa các đối tượng và tiêu chuẩn phân cụm, từ đó xây dựng mô hình và thực hiện phân cụm với các mục đích sử dụng khác nhau.
2.4 Các ứng dụng của phân cụm
Phân cụm DL là một trong những công cụ chính được ứng dụng trong nhiều lĩnh vực Một số ứng dụng điển hình trong các lĩnh vực sau:
Trong lĩnh vực thương mại, PCDL hỗ trợ các thương nhân xác định các nhóm khách hàng quan trọng với những đặc điểm tương đồng, đồng thời giúp họ phân tích hành vi mua sắm thông qua các mẫu dữ liệu trong cơ sở dữ liệu khách hàng.
Trong lĩnh vực sinh học, PCDL đóng vai trò quan trọng trong việc xác định các loại sinh vật, phân loại các gen có chức năng tương đồng và phân tích cấu trúc trong các mẫu sinh học.
CHƯƠNG TRÌNH DEMO
Để có cái nhìn trực quan về thuật toán phân cụm phân cấp em xin trình bày một chương trình demo đơn giản của thuật toán CURE
3.1 Bài toán và lưu đồ thuật toán
Input: Mảng S chứa các điểm trong không gian 2 chiều, mỗi điểm đặc trưng bởi 2 thuộc tính (x,y), k số cụm cần chia
Output: Các nhóm (cụm) điểm, trong đó các điểm gần nhau sẽ được gom vào một nhóm với mục tiêu là k cụm theo thuật toán CURE
Insert(Q,w) dist(x,x.closes t) < dist(x,w) x.closest=w relocate(Q,x) x.closest=closest_cluster(
T,x,dist(x,w)) dist(w,x)