Phân cụm hiệu quả của ma trận tương tự

Question

chủ đề của tôi là sự giống nhau và phân cụm (một loạt) văn bản. Tóm lại: Tôi muốn nhóm các văn bản thu thập lại với nhau và chúng sẽ xuất hiện trong các cụm có ý nghĩa ở cuối. Để làm điều này, cách tiếp cận của tôi cho đến bây giờ là như sau, vấn đề của tôi là trong clustering. Phần mềm hiện tại được viết bằng php.

1) Tương tự: Tôi xử lý mọi tài liệu dưới dạng "bag-of-words" và chuyển đổi các từ thành vectơ. Tôi sử dụng

• lọc (chỉ "thật" từ)
• tokenization (split câu diễn tả bằng lời)
• bắt nguồn (giảm từ để hình thức cơ bản của họ; Stemmer Porter)
• tỉa (cắt chữ với quá cao & tần số thấp)

làm phương pháp giảm kích thước. . Sau đó, tôi đang sử dụng cosin tương đồng (như đề xuất/mô tả trên các trang web khác nhau trên web and here

Kết quả sau đó là một ma trận tương tự như thế này:

 A B C D E 
    A 0 30 51 75 80 
    B X 0 21 55 70 
    C X X 0 25 10 
    D X X X 0 15 
    E X X X X 0 

A ... E là văn bản của tôi và Bởi vì sim (A, B) == sim (B, A) chỉ có một nửa của ma trận được điền vào. Vì vậy, sự giống nhau của văn bản A để văn bản D là 71%

Tôi muốn tạo ra một số nhóm chưa biết (!) Chưa biết trước của ma trận này. Các cụm phải đại diện cho các mục tương tự (đến một điểm dừng nhất định) p tiêu chí) với nhau.

Tôi đã thử một thực hiện cơ bản bản thân mình, đó là cơ bản như thế này (60% như một ngưỡng tương đồng cố định)

foreach article 
     get similar entries where sim > 60 
       foreach similar entry 
       check if one of the entries already has a cluster number 
       if no: assign new cluster number to all similar entries 
       if yes: use that number 

Nó làm việc (bằng cách nào đó), nhưng là không tốt chút nào và kết quả thường các cụm quái vật. Vì vậy, tôi muốn làm lại điều này và đã có một cái nhìn vào tất cả các loại thuật toán phân cụm, nhưng tôi vẫn không chắc cái nào sẽ hoạt động tốt nhất. Tôi nghĩ rằng nó nên là một thuật toán kết tụ, bởi vì mỗi cặp văn bản có thể được xem như là một cụm trong đầu. Nhưng vẫn còn các câu hỏi là những gì các tiêu chí dừng là và nếu thuật toán nên phân chia và/hoặc hợp nhất các cụm hiện có với nhau.

Xin lỗi nếu một số nội dung có vẻ cơ bản nhưng tôi tương đối mới trong lĩnh vực này. Cảm ơn đã giúp đỡ.

Answer 1

Chỉ cần thử một số. Có rất nhiều thuật toán phân cụm, không ai biết tất cả chúng. Ngoài ra, nó cũng phụ thuộc rất nhiều vào tập dữ liệu của bạn và cấu trúc phân cụm đó là ở đó. Cuối cùng, cũng có thể chỉ có một cụm quái vật này liên quan đến khoảng cách cosin và các tính năng BofW.

Answer 2

Vì bạn vừa mới vào trường, có số cụm không xác định và đã sử dụng khoảng cách cosin, tôi sẽ đề xuất thuật toán phân cụm FLAME.

Trực quan, dễ triển khai và có triển khai bằng nhiều ngôn ngữ (không phải PHP mặc dù phần lớn là do rất ít người sử dụng PHP cho khoa học dữ liệu).

Chưa kể, nó thực sự đủ tốt để được sử dụng trong nghiên cứu bởi một số lượng lớn người.Nếu không có gì khác bạn có thể có được một ý tưởng về những gì chính xác những thiếu sót trong thuật toán phân cụm mà bạn muốn giải quyết trong việc di chuyển lên một số khác.

Answer 3

Có thể bạn có thể biến đổi ma trận tương tự thành ma trận không giống nhau như chuyển x thành 1/x, thì vấn đề của bạn là cụm một ma trận không giống nhau. Tôi nghĩ rằng cụm phân cấp có thể hoạt động. Chúng có thể giúp bạn: hierarchical clustering và Clustering a dissimilarity matrix