Các kết quả khác nhau từ việc thực hiện LOF trong ELKI và RapidMiner

Question

Tôi đã viết thực hiện LOF của riêng mình và tôi đang cố gắng so sánh kết quả với các triển khai trong ELKI và RapidMiner, nhưng cả 3 đều cho kết quả khác nhau! Tôi đang cố gắng giải thích tại sao.

Tập dữ liệu tham chiếu của tôi là một chiều, 102 giá trị thực với nhiều bản sao. Tôi sẽ thử và đăng nó dưới đây.

Đầu tiên, triển khai RapidMiner. Điểm số LOF rất khác với ELKI và từ kết quả của tôi; nhiều người trở lại với một LOF vô cùng. Việc triển khai này có được xác thực là chính xác không?

Kết quả của tôi tương tự như ELKI, nhưng tôi không nhận được chính xác cùng giá trị LOF. Từ việc quét nhanh các nhận xét trong mã nguồn ELKI, tôi nghĩ điều này có thể là do sự khác biệt về cách tính toán k-lân cận.

Trong giấy LOF, tham số MinPts (ở nơi khác được gọi là k) chỉ định số không tối thiểu. các điểm được bao gồm trong khu phố k. Trong việc thực hiện ELKI, tôi nghĩ rằng họ đang xác định k-khu phố là chính xác k điểm hơn là tất cả các điểm trong khoảng cách k hoặc khoảng cách k riêng biệt. Bất cứ ai có thể xác nhận chính xác như thế nào ELKI xây dựng k-khu phố? Ngoài ra còn có một biến riêng cho phép các điểm chính nó được bao gồm trong khu phố riêng của nó, nhưng có vẻ như mặc định là không bao gồm nó.

Có ai biết về tập dữ liệu tham chiếu công khai có điểm LOF được đính kèm cho mục đích xác thực không?

--- biết thêm chi tiết theo ---

tham khảo: ELKI mã nguồn là ở đây:

http://elki.dbs.ifi.lmu.de/browser/elki/trunk/src/de/lmu/ifi/dbs/elki/algorithm/outlier/lof/LOF.java

RapidMiner mã nguồn là ở đây:

http://code.google.com/p/rapidminer-anomalydetection/source/browse/trunk/src/de/dfki/madm/anomalydetection/evaluator/nearest_neighbor_based/LOFEvaluator.java

đây là tập dữ liệu thử nghiệm của tôi:

4,32323 5,12595 5,12595 5,12595 5,12595 5,7457 5,7457 5,7457 5,7457 5,7457 5,7457 5,97766 5,97766 6,07352 6,07352 6,12015 6,12015 6,12015 6,44797 6,44797 6,48131 6,48131 6,48131 6,48131 6,48131 6,48131 6,6333 6,6333 6,6333 6,70872 6,70872 6,70872 6,70872 6,70872 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 6,77579 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,03654 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,10361 7,15651 7,1 5651 7,15651 7,15651 7,15651 7,15651 7,15651 7,15651 8,22598 8,22598 8,22598 8,22598 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538 8,5538

Ví dụ, tôi nhận được số điểm LOF sau cho số đầu tiên (4,32323):

• RapidMiner: vô cực (với MinPts cận dưới/trên thiết lập để 10.100)
• ELKI: 2.6774 (với k = 10 và distfunction/reachdistfunction thiết lập để mặc định)
• thực hiện của tôi: 1,9531

Một số chi tiết về những gì thực hiện tôi đang làm:

1. MinPts là 10, vì vậy tôi m tìm thấy 10 hàng xóm khác nhau của điểm. Vì vậy, các khu phố của 4.32323 thực sự là 48 điểm, từ 5.12595 lên đến 6.77579.
2. Điều đó mang lại cho tôi một khoảng cách k-biệt của 2,45256
3. Tôi đang tính toán khoảng cách reachability của những người hàng xóm đầu tiên là 1,58277
4. Tôi đang tính LRD của mẫu như 1/(99,9103/48)
5. Sum của LRD (o)/LRD (p) cho tất cả 48 xóm là 93,748939
6. Divide bởi 48 để có được một LOF của 1,9531

Answer 1

tôi thực sự không ngạc nhiên chúng khác nhau. Bạn cũng có thể thêm vào việc triển khai LOF của Weka và có thể bạn sẽ nhận được một câu trả lời khác.

Dưới đây là một sự khác biệt nữa để bạn thêm vào phương trình của mình: theo như tôi biết, triển khai nhanh hơn hợp nhất các điểm có cùng toạ độ. Nhưng có lẽ, họ quên lấy những trọng số này khi tính toán các nước láng giềng gần nhất!

Trong ngữ cảnh cơ sở dữ liệu cổ điển, bạn sẽ không hợp nhất toạ độ trùng lặp thành một quan sát đơn lẻ. Chúng vẫn là các bản ghi cơ sở dữ liệu hợp lệ và phải được tính là bản ghi đầy đủ.

Tôi không biết liệu có bất kỳ người nào trong số họ thực hiện một số xử lý trước dữ liệu tự động chẳng hạn như thay đổi kích thước tập dữ liệu.

Việc triển khai ELKI đã được xác minh đối với một số ví dụ về sách giáo khoa mà chúng tôi sử dụng để giảng dạy.

Tuy nhiên, có các trường hợp góc trong thuật toán không phải là 100% cố định, do đó, có chỗ cho sự khác biệt ngay cả khi triển khai "theo nghĩa đen" của thuật toán. Bạn đã chạy vào ba trong số này:

1. Làm thế nào để điều trị điểm trùng lặp: A) tổng hợp, B) thả, C) xem xét khác nhau

   Từ một điểm khai thác dữ liệu của view, C là đúng, và A (khi được triển khai chính xác) là một tối ưu hóa có thể tiết kiệm cho bạn các tính toán khoảng cách không cần thiết. B là chế độ xem toán học phổ biến, nhưng không có ý nghĩa nhiều đối với bối cảnh cơ sở dữ liệu. Nếu tôi có hai "John Doe", họ có phải là cùng một người không?

2. Định nghĩa của k lân cận gần nhất và k-distance.

   Định nghĩa thông thường của k-distance là: khoảng cách nhỏ nhất, sao cho có ít nhất k quan sát được chứa. Khi loại trừ các điểm truy vấn, điều này mang lại sự inverval lên đến 5.7457 từ điểm xuất phát: có 10 quan sát khác trong bán kính 5.7457 - 4.32323.

   Các k lân cận gần nhất thường được định nghĩa là bất kỳ điểm nào trong khoảng cách này, có thể lớn hơn k.Nhưng sau đó tất cả các đối tượng bổ sung phải có khoảng cách tương tự là k2! Dường như nếu RapidMiner sử dụng chính xác k, mà không phù hợp với việc xuất bản LOF (xem Định nghĩa 4 trong ấn phẩm LOF!)

   Nó thực sự k láng giềng gần nhất (trong đó có mối quan hệ, nhưng khác hơn là không nhiều so với k đối tượng), không phải là k-ths nhỏ nhất riêng biệt khoảng cách. Bạn đã nhận được "khác biệt" từ đâu?

   Defintions 3 và 4 trong ấn phẩm LOF khá rõ ràng về việc sử dụng LOF của kNN.

   Vùng lân cận 48 đối tượng của bạn như vậy là không chính xác.

3. Phải làm gì nếu có hơn minPts lặp lại điểm (một việc thực hiện nghĩa đen sẽ mang lại một phép chia cho không, nhưng vì lý do rõ ràng điểm nên được trao một LOF 1,0)

   Đây là có lẽ là những gì xảy ra với Rapidminer.

Và sau đó là khoảng cách reachability: đây là một trong thực sự khó khăn, bởi vì nó không phải là một khoảng cách toán học. Đó là không đối xứng.

Các reachability của quan sát đầu tiên từ thứ hai sẽ xảy ra là k-khoảng cách thứ hai, mà từ một cái nhìn nhanh chóng (không kiểm tra kép) reach-dist(x[0], x[1]) = max(5.97766 - 5.12595, 5.12595 - 4.32323) = 0.80272

Xem my extensive tutorial slides on outlier detection cho một bước-by- bước trình diễn cách tính LOF. Theo như tôi có thể nói, đây là LOF theo nghĩa đen. Nó không chạm vào tất cả các trường hợp góc, nhưng nó thúc đẩy thiết kế của thuật toán LOF và khá đầy đủ.

Answer 2

Nếu bạn đang sử dụng Tiện ích phát hiện bất thường cho RapidMiner [1] (không phải là LOF dựng sẵn), bạn sẽ nhận được kết quả chính xác. LOF tích hợp bị hỏng. Đây là những kết quả tương tự như ELKI. Việc triển khai này nhanh hơn nhiều so với ELKI vì nó bị đe dọa nhiều và cũng sử dụng ít bộ nhớ hơn nhiều. Nó cũng có thể xử lý các bản sao (thậm chí nhiều hơn k + 1), trong đó ELKI ném ngoại lệ. (Dựa trên k-biệt)

nhất, Hans

[1] http://marketplace.rapid-i.com/UpdateServer/faces/product_details.xhtml?productId=rmx_anomalydetection