{"action":"created","issue":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12040","repository_url":"https://api.github.com/repos/scikit-learn/scikit-learn","labels_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12040/labels{/name}","comments_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12040/comments","events_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12040/events","html_url":"https://github.com/scikit-learn/scikit-learn/issues/12040","id":358304571,"node_id":"MDU6SXNzdWUzNTgzMDQ1NzE=","number":12040,"title":"Isolation forest - decision_function & average_path_length method are memory inefficient","user":{"login":"anant9","id":5839680,"node_id":"MDQ6VXNlcjU4Mzk2ODA=","avatar_url":"https://avatars0.githubusercontent.com/u/5839680?v=4","gravatar_id":"","url":"https://api.github.com/users/anant9","html_url":"https://github.com/anant9","followers_url":"https://api.github.com/users/anant9/followers","following_url":"https://api.github.com/users/anant9/following{/other_user}","gists_url":"https://api.github.com/users/anant9/gists{/gist_id}","starred_url":"https://api.github.com/users/anant9/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/anant9/subscriptions","organizations_url":"https://api.github.com/users/anant9/orgs","repos_url":"https://api.github.com/users/anant9/repos","events_url":"https://api.github.com/users/anant9/events{/privacy}","received_events_url":"https://api.github.com/users/anant9/received_events","type":"User","site_admin":false},"labels":[{"id":12995801,"node_id":"MDU6TGFiZWwxMjk5NTgwMQ==","url":"https://api.github.com/repos/scikit-learn/scikit-learn/labels/Enhancement","name":"Enhancement","color":"d7e102","default":false},{"id":705180250,"node_id":"MDU6TGFiZWw3MDUxODAyNTA=","url":"https://api.github.com/repos/scikit-learn/scikit-learn/labels/Performance","name":"Performance","color":"d93f0b","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":3,"created_at":"2018-09-08T15:26:57Z","updated_at":"2018-09-13T09:34:41Z","closed_at":null,"author_association":"NONE","body":"#### Description\r\nIsolation forest consumes too much memory due to memory ineffecient implementation of anomoly score calculation. Due to this the parallelization with n_jobs is also impacted as anomoly score cannot be calculated in parallel for each tree.\r\n\r\n#### Steps/Code to Reproduce\r\nRun a simple Isolation forest with n_estimators as 10 and as 50 respectively.\r\nOn memory profiling, it can be seen that each building of tree is not taking much memory but in the end a lot of memory is consumed as a for loop is iteration over all trees and calculating the anomoly score of all trees together and then averaging it.\r\n-iforest.py line 267-281\r\n```py\r\n        for i, (tree, features) in enumerate(zip(self.estimators_,\r\n                                                 self.estimators_features_)):\r\n            if subsample_features:\r\n                X_subset = X[:, features]\r\n            else:\r\n                X_subset = X\r\n            leaves_index = tree.apply(X_subset)\r\n            node_indicator = tree.decision_path(X_subset)\r\n            n_samples_leaf[:, i] = tree.tree_.n_node_samples[leaves_index]\r\n            depths[:, i] = np.ravel(node_indicator.sum(axis=1))\r\n            depths[:, i] -= 1\r\n\r\n        depths += _average_path_length(n_samples_leaf)\r\n\r\n        scores = 2 ** (-depths.mean(axis=1) / _average_path_length(self.max_samples_))\r\n\r\n        # Take the opposite of the scores as bigger is better (here less\r\n        # abnormal) and add 0.5 (this value plays a special role as described\r\n        # in the original paper) to give a sense to scores = 0:\r\n        return 0.5 - scores\r\n````\r\n\r\nDue to this, in case of more no. of estimators(1000), the memory consumed is quite high.\r\n\r\n#### Expected Results\r\nPossible Solution:\r\nThe above for loop should only do the averaging of anomoly score from each estimator instead of calculation. The logic of isoforest anomoly score calculation can be moved to base estimator class so it is done for each tree( i guess bagging.py file-similar to other method available after fitting)\r\n#### Actual Results\r\nThe memory consumption is profound as we increase no. of estimators.\r\n```py\r\nmodel=Isolationforest()\r\nmodel.fit(data)\r\n```\r\n\r\nThe fit method calls decision function & average anomoly score which are taking quite a lot memory.\r\nthe memory spike is too high in the very end, that is in finall call to `average_path_length()` method.\r\n```\r\ndepths += _average_path_length(n_samples_leaf)\r\n```\r\n#### Versions\r\n\r\n<!-- Thanks for contributing! -->\r\n\r\n[isoForest_memoryConsumption.docx](https://github.com/scikit-learn/scikit-learn/files/2363437/isoForest_memoryConsumption.docx)\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/comments/420945484","html_url":"https://github.com/scikit-learn/scikit-learn/issues/12040#issuecomment-420945484","issue_url":"https://api.github.com/repos/scikit-learn/scikit-learn/issues/12040","id":420945484,"node_id":"MDEyOklzc3VlQ29tbWVudDQyMDk0NTQ4NA==","user":{"login":"anant9","id":5839680,"node_id":"MDQ6VXNlcjU4Mzk2ODA=","avatar_url":"https://avatars0.githubusercontent.com/u/5839680?v=4","gravatar_id":"","url":"https://api.github.com/users/anant9","html_url":"https://github.com/anant9","followers_url":"https://api.github.com/users/anant9/followers","following_url":"https://api.github.com/users/anant9/following{/other_user}","gists_url":"https://api.github.com/users/anant9/gists{/gist_id}","starred_url":"https://api.github.com/users/anant9/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/anant9/subscriptions","organizations_url":"https://api.github.com/users/anant9/orgs","repos_url":"https://api.github.com/users/anant9/repos","events_url":"https://api.github.com/users/anant9/events{/privacy}","received_events_url":"https://api.github.com/users/anant9/received_events","type":"User","site_admin":false},"created_at":"2018-09-13T09:34:41Z","updated_at":"2018-09-13T09:34:41Z","author_association":"NONE","body":"Hello, yes that exactly the issue with isolation forest. The dataset is indeed large 257K samples with 35 numerical features. However, that even needs to be more than that as per my needs and so looking for memory efficiency too in addition to time.\r\n\r\nI have gone through the links and they are quite useful to my specific usecases(I was even facing memory issues with sillloutte score and brute  algo).\r\nI'm also exploring dask package that works on chunks using dask arrays/dataframes and if can alternatively be used in places where sklearn is consuming memory.\r\n\r\nWill be first working on handling the data with chunks and probably in coming weeks will be making the PR for isoforest modification as have to go through the research paper on iso forest algo too. Also looking for other packages/languages than sklearn as how they are doing isoforest.\r\nHere's the bagging implementation seems quite different, i.e. I think the tree is getting build for each sample instead of simply making n_estimators tree and then apply on each sample- In any case I have to understand few other things before starting work/discussion on this in detail.\r\n\r\n"}}
{"actor":{"display_login":"anant9"}}