2
$\begingroup$

I am currently reading this paper on Isolation Forest.

At page 3, there is a definition of Isolation Tree and there are a couple of sentences that I don't understand:

Given a sample of data X = {x1, ..., xn} of n instances from a d-variate distribution, to build an isolation tree (iTree), we recursively divide X by randomly selecting an attribute q and a split value p, until either: (i) the tree reaches a height limit, (ii) |X| = 1 or (iii) all data in X have the same values.

Here, I would like to understand what do the points (ii) & (iii) mean. In the point (iii), when the author says 'all data in X have same values', does it mean the same anomaly score?

And there is also a block of text which I am failing to understand completely. Can someone help me understand this text too..

Assuming all instances are distinct, each instance is isolated to an external node when an iTree is fully grown, in which case the number of external nodes is n and the number of internal nodes is n − 1; the total number of nodes of an iTrees is 2n − 1

Thanks

$\endgroup$
3
$\begingroup$

(ii) means after splitting the data you end up with a single instance in the node, so there is nothing left to do

(iii) means after splitting the data all the samples in the node are identical ("duplicates"), and again there is nothing left to do

Assuming all instances are distinct, each instance is isolated to an external node when an iTree is fully grown, in which case the number of external nodes is n and the number of internal nodes is n − 1; the total number of nodes of an iTrees is 2n − 1

Isolating an instance means splitting the data until that instance ends up in a leaf by itself. If you have $n$ instances, you will need $n$ external ("end") nodes. One for each instance. The internal nodes are all the nodes before the end nodes, including the root that contains all the instances. One can show that their number is $n-1$. For example, if you have $n=4$ you can split it in (4)-(2,2)-((1,1)(1,1)). So you have $1+1+1+1=4=n$ end nodes, and $1+2=3=n-1$ inner nodes.

Of course, the splits don't have to be equal. It could also be something like (4)-(3,1) Where you then split the (3) into (2,1) and the (2) into (1,1) But the counts will be the same. You'll have 3 inner nodes (4),(3) and (2) and 4 external nodes. (Best to draw it out)

The total is therefore the number of end nodes plus the number of inner nodes $n +(n-1) = 2n-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.