Lập trình

Vì vậy, đến nay chúng tôi đã chỉ nhìn thấy học giám sát, ở đây chúng tôi biết trước những gì là nhãn (hay còn gọi là "câu trả lời đúng") là gì và chúng tôi đang cố gắng để có được mô hình của chúng tôi để được là chính xác càng tốt, được xác định bởi số liệu đánh giá của chúng tôi lựa chọn.

K -means là kỹ thuật học không giám sát đầu tiên chúng ta sẽ xem xét, trong khi mục tiêu của thuật toán là để xác định các định nghĩa của các câu trả lời đúng bằng cách tìm các cụm dữ liệu cho bạn.

Hãy nói rằng bạn có một số loại dữ liệu ở cấp độ người dùng, ví dụ, dữ liệu Google+, số liệu điều tra, dữ liệu y tế, hoặc điểm số SAT.

Bắt đầu bằng cách thêm vào cấu trúc dữ liệu của bạn. Cụ thể, giả sử mỗi hàng của tập dữ liệu của bạn tương ứng với một người sử dụng như sau:

age gender income state household size

Mục tiêu của bạn là để phân khúc người dùng. Quá trình này được gọi bằng nhiều tên khác nhau: ngoài việc bị gọi là năng phân đoạn, bạn có thể nói rằng bạn đang đi để phân tầng (stratify), nhóm (group), hoặc phân cụm (cluster) dữ liệu. Chúng, tất cả có nghĩa là tìm kiếm các loại tương tự của người sử dụng và tụ nhóm chúng lại với nhau.

Tại sao bạn muốn làm điều này? Đây là vài ví dụ:

• Bạn có thể muốn cung cấp cho người dùng khác nhau những kinh nghiệm khác nhau. Thị tiếp thị các thường thực hiện điều này; ví dụ, để cung cấp mực cho những người được gọi để sở hữu máy in.

• Bạn có thể có một mô hình hoạt động tốt hơn cho các nhóm cụ thể. Hoặc bạn có thể có các mô hình khác nhau cho các nhóm khác nhau.

• Mô hình phân cấp trong thống kê làm một cái gì đó như thế này; ví dụ, để tách riêng mô hình các tác động địa lý từ tác hộ gia đình trong các kết quả khảo sát.

Để xem tại sao một thuật toán như thế này có thể có ích, trước tiên hãy thử để khởi tạo một cái gì đó thủ công. Điều đó có thể có nghĩa là bạn muốn người dùng sử dụng bộ ngưỡng thực hiện bằng tay.

Vì vậy, cho một thuộc tính như độ tuổi, bạn muốn tạo các thùng chứa: 20-24, 25-30, v.v… Các kỹ thuật tương tự có thể được sử dụng cho các thuộc tính khác như thu nhập. Hoa, thành phố trong một số cảm nhận xô riêng của họ, nhưng bạn có thể muốn xô ít hơn, tùy thuộc vào mô hình của bạn và số lượng các điểm dữ liệu. Trong trường hợp đó, bạn có thể bộ chứa các thùng và nghĩ về " East Coast" và "Midwest" hoặc một cái gì đó như thế.

Giả sử bạn đã làm điều đó cho mỗi thuộc tính. Bạn có thể có 10 thùng chứa tuổi, 2 thùng chứa giới tính, và như vậy, mà sẽ cho kết quả trong 10 × 2 × 50 × 10 × 3 = 30.000 thùng chứa có thể, đó là số lớn.

Hãy tưởng tượng dữ liệu này tồn tại trong một không gian năm chiều nơi mỗi trục tương ứng với một thuộc tính. Vì vậy, có một trục giới tính, một trục thu nập, và cũng như vậy. Bạn cũng có thể gắn nhãn các thùng khác nhau có thể cùng các trục tương ứng, và nếu bạn đã làm như vậy, các lưới kết quả sẽ bao gồm tất cả các thùng -một thùng cho mỗi sự kết hợp có thể có của các thuộc tính.

Mỗi người dùng sau đó sẽ sống ở một trong 30.000 ô năm chiều. Bây giờ bạn có thể xem các tiện ích của việc, có một thuật toán để làm điều này cho bạn, đặc biệt là nếu bạn có thể chọn trước bao nhiêu thùng tùy bạn muốn. Một cách chính xác, k-means là một thuật toán phân nhóm (clustering), trong đó k là số thùng.

2D version

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Hình 3.9. Phân cụm ở hai chiều; nhìn vào bảng theo cột bên trái từ trên xuống dưới, và sau đó cột bên phải từ trên xuống dưới

Nhìn bề ngoài, bạn có thể nhìn thấy ở góc trên bên trái mà các dữ liệu một cách tự nhiên rơi vào cụm. Điều này có thể dễ dàng thự hiện khi nó chỉ ở hai chiều và không có nhiều điểm, nhưng khi bạn nhận được để kích thước cao hơn và nhiều dữ liệu hơn, bạn cần một thuật toán để giúp cho quá trình mô-việc tìm kiếm này. k-means là thuật toán tìm kiếm cụm trong kích thước d, trong đó d là số tính năng cho mỗi điểm dữ liệu.

Đây là cách các thuật toán được minh họa trong hình 3-9 hoạt động:

1. Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm được đại diện bằng các tâm của cụm.

2. Tính khoảng cách giữa các đối tượng (objects) đến K tâm (thường dùng khoảng cách Euclidean)

3. Nhóm các đối tượng vào nhóm gần nhất

4. Xác định lại tâm mới cho các nhóm

5. Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối tượng

Nó thuộc vào bạn để giải thích nếu có một cách tự nhiên để mô tả các nhóm khi các thuật toán được thực hiện. Đôi khi bạn sẽ cần phải đưa đẩy nhẹ xung quanh k một vài lần trước khi bạn nhận được các nhóm tự nhiên.

Đây là một ví dụ của việc học không có giám sát bởi vì các nhãn không được biết đến và thay vào đó phát hiện bởi các thuật toán.

K-means có một số vấn đề:

• Lựa chọn k là một nghệ thuật hơn là một khoa học, mặc dù có những giới hạn: 1 ≤ k ≤ n, trong đó n là số điểm dữ liệu.

• Có những vấn đề hội tụ các giải pháp có thể không tồn tại, nếu thuật toán rơi vào một vòng lặp, ví dụ, và tiếp tục đi lại giữa hai giải pháp có thể, hay nói cách khác, không có một giải pháp duy nhất duy nhất.

• Diễn giải có thể là một vấn đề đôi khi câu trả lời không phải là ở tất cả các hữu ích. Thực tế đó là thường vấn đề lớn nhất.

Hãy sao lưu vào một ví dụ đơn giản hơn so với một năm chiều, chúng tôi chỉ thảo luận. Hãy nói rằng bạn có người sử dụng mà bạn biết có bao nhiêu quảng cáo đã được hiển thị cho mỗi người dùng (số lần hiển thị) và bao nhiêu lần mỗi đã nhấp vào quảng cáo (số lần nhấp chuột).

Hình 3.9 cho thấy một hình ảnh đơn giản để minh họa điều này có thể trông như thế nào.

Mặc dù những vấn đề này, nó khá nhanh (so với các thuật toán phân cụm khác), và có những ứng dụng rộng rãi trong lĩnh vực marketing, máy tính (phân vùng một hình ảnh), hoặc như là một điểm khởi đầu cho các mô hình khác.

Trong thực tế, đây chỉ là một dòng mã trong R:

kmeans(x, centers, iter.max = 10, nstart = 1,

algorithm = c("Hartigan-Wong", "Lloyd", "Forgy", "MacQueen"))

Bộ dữ liệu của bạn cần có một ma trận, x, mỗi cột trong số đó là một trong những tính năng của bạn. Bạn chỉ rõ k bằng cách chọn các trung tâm. Nó mặc định một số lượng nhất định lặp đi lặp lại, mà là một đối số bạn có thể thay đổi. Bạn cũng có thể chọn các thuật toán cụ thể nó sử dụng để khám phá các cụm.

Bối cảnh lịch sử của k-means

K-means chuẩn thuật toán là do làm việc riêng biệt bởi Hugo Steinhaus và Stuart Lloyd vào năm 1957, nhưng nó đã không được gọi là "k- means". Người đầu tiên sử dụng thuật ngữ đó là James MacQueen vào năm 1967. Nó đã không được xuất bản ra bên ngoài Bell Labs, cho đến năm 1982.

Phiên bản mới hơn của thuật toán là Hartigan-Wong và Lloyd và Forgy, đặt tên cho phát minh của họ và phát triển trong suốt thập niên 60 và 70. Các thuật toán chúng ta mô tả là mặc định, Hartigan-Wong. Nó là tốt để sử dụng mặc định.

Nhưng gần đây, nó trở nên có giá trị trong việc kiểm thử k-means ++, được phát triển vào năm 2007 bởi David Arthur và Sergei Vassilvit- SK-II (tại Google), giúp tránh các vấn đề hội tụ với k-means bằng cách tối ưu các hạt ban đầu.