{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12085","repository_url":"https://api.github.com/repos/scikit-learn/scikit-learn","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12085/labels{/name}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12085/comments","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12085/events","html_url":"https://github.com/scikit-learn/scikit-learn/pull/12085","id":360439388,"node_id":"MDExOlB1bGxSZXF1ZXN0MjE1Njk5MTA5","number":12085,"title":"[MRG] sklearn.ensemble.IsolationForest._average_path_length returns incorrect values for input < 3. #11839","user":{"login":"joshuakennethjones","id":658049,"node_id":"MDQ6VXNlcjY1ODA0OQ==","avatar_url":"https://avatars1.githubusercontent.com/u/658049?v=4","gravatar_id":"","url":"https://api.github.com/users/joshuakennethjones","html_url":"https://github.com/joshuakennethjones","followers_url":"https://api.github.com/users/joshuakennethjones/followers","following_url":"https://api.github.com/users/joshuakennethjones/following{/other_user}","gists_url":"https://api.github.com/users/joshuakennethjones/gists{/gist_id}","starred_url":"https://api.github.com/users/joshuakennethjones/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/joshuakennethjones/subscriptions","organizations_url":"https://api.github.com/users/joshuakennethjones/orgs","repos_url":"https://api.github.com/users/joshuakennethjones/repos","events_url":"https://api.github.com/users/joshuakennethjones/events{/privacy}","received_events_url":"https://api.github.com/users/joshuakennethjones/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":6,"created_at":"2018-09-14T20:12:36Z","updated_at":"2018-09-20T01:00:16Z","closed_at":null,"author_association":"NONE","pull_request":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/pulls/12085","html_url":"https://github.com/scikit-learn/scikit-learn/pull/12085","diff_url":"https://github.com/scikit-learn/scikit-learn/pull/12085.diff","patch_url":"https://github.com/scikit-learn/scikit-learn/pull/12085.patch"},"body":"\r\n#### Reference Issues/PRs\r\nFixes #11839 \r\n(sklearn.ensemble.IsolationForest._average_path_length returns incorrect values for input < 3.)\r\n\r\n\r\n#### What does this implement/fix? Explain your changes.\r\n\r\nWhen an input value to _average_path_length() is in {0,1}, the return value should be zero, not one, as in the existing implementation. Also, when the input value is 2, the return value should be 1, not 0.15... as in the current implementation. These results should be expected for two reasons: first, based on the 2012 iForest paper (the original paper indicated a zero value for terminal nodes to which < 2 training examples had been sorted in the first paragraph of section 4.2, but left this vague in the algorithm/equation specifications, and did not specify a unique value for nodes to which exactly two training examples had been sorted), where it is explicitly stated that c(n) (the value computed by _average_path_length) should take the value zero for n in {0,1} and takes the value 1 for n=2. Also, from a rational perspective, we want these values to monotonically increase with n, and in the current implementation this is not the case. This is a pretty straightforward fix -- I have altered the existing cases for inputs in {0,1} to return zero instead of 1 (which was already hard-coded for these cases) and added a case for an input value of 2 to return 1. \r\n\r\nThanks!\r\n\r\nLiu, Fei Tony, Ting, Kai Ming and Zhou, Zhi-Hua. \"Isolation-based anomaly detection.\" ACM Transactions on Knowledge Discovery from Data (TKDD) 6.1 (2012): 3.\r\n\r\n#### Steps to Test\r\n\r\n```python\r\nimport numpy as np\r\nfrom sklearn.ensemble.iforest import _average_path_length\r\n_average_path_length(np.array([0,1,2,3]))\r\n```\r\n\r\n#### Results from Submitted Code\r\n```array([0.        , 0.        , 1., 1.20739236])```\r\n\r\n\r\n\r\n#### Results From Existing Code\r\n```array([1.        , 1.        , 0.15443133, 1.20739236])```\r\n"},"comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/423005184","html_url":"https://github.com/scikit-learn/scikit-learn/pull/12085#issuecomment-423005184","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12085","id":423005184,"node_id":"MDEyOklzc3VlQ29tbWVudDQyMzAwNTE4NA==","user":{"login":"joshuakennethjones","id":658049,"node_id":"MDQ6VXNlcjY1ODA0OQ==","avatar_url":"https://avatars1.githubusercontent.com/u/658049?v=4","gravatar_id":"","url":"https://api.github.com/users/joshuakennethjones","html_url":"https://github.com/joshuakennethjones","followers_url":"https://api.github.com/users/joshuakennethjones/followers","following_url":"https://api.github.com/users/joshuakennethjones/following{/other_user}","gists_url":"https://api.github.com/users/joshuakennethjones/gists{/gist_id}","starred_url":"https://api.github.com/users/joshuakennethjones/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/joshuakennethjones/subscriptions","organizations_url":"https://api.github.com/users/joshuakennethjones/orgs","repos_url":"https://api.github.com/users/joshuakennethjones/repos","events_url":"https://api.github.com/users/joshuakennethjones/events{/privacy}","received_events_url":"https://api.github.com/users/joshuakennethjones/received_events","type":"User","site_admin":false},"created_at":"2018-09-20T01:00:16Z","updated_at":"2018-09-20T01:00:16Z","author_association":"NONE","body":"@albertcthomas -- thanks for taking a look! I'm looking into the test further. I'm working to verify that the current behavior is due to a tie in anomaly scores. I'm pretty sure that has to be the reason, but I agree that it makes sense to double check. I also have an idea about how to fix the test in a way that won't be subject to capturing \"good luck\" in the random seed values, which I believe was essentially the case when it previously succeeded. Of course, the change we are discussing here is going to change the anomaly scores produced, so no surprise there. Practically speaking, increasing the tolerance would probably make the test pass, because the odds of creating a random dataset with three examples in a critical position that have equal values should be quite low -- but it's still nonzero. If I'm going to fix the test I'd rather do something that deterministically succeeds regardless of random chance, to eliminate the possibility of this kind of thing biting someone in the future. Will update again when I have something ready."}}
{"actor":{"display_login":"joshuakennethjones"}}