A comparison of di erent treatment strategies does not always result in determining the best one for all patients, one needs to study subgroups of patients with signi cant di erence in e ciency between treatment strategies. To solve this problem an approach to subgroups generation is proposed, where data are described in terms of a pattern structure and pattern concepts stay for patient subgroups and their descriptions. To nd the most promising pattern concepts in terms of the di erence of treatment strategies in e ciency a version of CbO algorithm is proposed. An application to the analysis of data on childhood acute lymphoblastic leukemia is considered.
Randomized controlled trial (RCT)[
Several approaches were proposed in [2{11]. Most of them [5{11] are based on
the idea of decision or regression trees which locally optimize some measure at
every iteration of the algorithm. This approach is more suitable when we operate
on the big datasets or constantly increasing dataset because they allow to nd
some subgroups quickly. In the case of treatment optimization the datasets, as
a rule, are not very big and do not increase in size rapidly. Moreover, collecting
such datasets demands a lot of time and e orts. So, it is more important to carry
out more detailed analysis of the data then to make it fast. Also, in RCT on
cancer, heart conditions or chronic diseases the outcome of the therapy can be
censored, while only few papers like [
The rest of the paper is organized as follows. In section 2 we recall basic
de nitions of pattern structures and give examples of pattern structures [14{17]
relevant to the analyzed data. In section 3 a version of Close-by-One (CbO)
algorithm [
In this section we recall pattern structures and examples of pattern structures used for nominal and numerical features.
Let G be a set (of objects), (D; u) be a meet-semilattice (of all possible object descriptions), and : G ! D be a mapping. Then (G; (D; u); ) is called a pattern structure, provided that the set (G) = f (g) j g 2 Gg generates a complete subsemilattice (D ; u) of (D; u), i.e. every subset X of (G) has an in mum FX in (D; u). Elements of D are called patterns and are naturally ordered by subsumption relation v: c v d , cud = c, where c; d 2 D. Operation u is also called a similarity operation. If (G; (D; u); ) is a pattern structure we de ne the derivation operators which form a Galois connection between the powerset of G and (D; u) as:
A = gF2A (g) d = fg 2 G j d v (g)g for A G for d 2 D (1) The pairs (A; d) satisfying A G, d 2 D, A = d, and A = d are called pattern concepts of (G; (D; u); ), with pattern extent A and pattern intent d. Pattern concepts are ordered with respect to set inclusion on extents. The ordered set of pattern concepts makes a lattice, called pattern concept lattice. Operator ( ) is an algebraical closure operator on patterns, since it is idempotent, extensive, and monotone.
If objects are described by binary attributes from set M , then D = }(M ), the powerset of M , and (g) is prime operator ( )0 in the context (G; M; I): (g) = fm 2 M j gImg, and d1 u d2 = d1 \ d2 where d1; d2 2 D. So, subsumption corresponds to set inclusion: d1 v d2 , d1 u d2 = d1 , d1 \ d2 = d1 , d1 d2.
So, if all patients' initial features are binary we can use them as binary attributes directly. However we also aim at dealing with nominal initial features. Consider patients are described by k initial features f 1; :::; kg, all of them are nominal (binary is a particular case) and their values are coded as natural numbers. So, if i takes li values we assume that the range of i is f1; :::; lig. For each i we construct li binary attributes f i1; :::; ili g such that ij : G ! f0; 1g and ij (g) : g ! i(g) = j where g 2 G; j = 1; :::; li. As a result we get Pi=1;:::;n li binary attributes to which pattern structures can be applied as it is shown above. 2.2
To operate with numerical features interval pattern structures [15{17] can be applied. Let us consider each patient is described by n numerical and no nominal initial features. In our notation G corresponds to the set of patients. So, let f'1; '2; :::; 'ng be a set of functions represented patients' initial features such that 'i : G ! R for i = 1; :::; n. For each feature 'i we construct a corresponding interval attribute i : G ! [R; R] such that if 'i(g) = x for g 2 G, then i(g) = [x; x], where x 2 R. These attributes are used for pattern structures construction.
Each object is described by a n-dimensional tuple of intervals. Let a and b be tuples of n intervals, so a = h[vi; wi]ii=1;:::;n and b = h[xi; yi]ii=1;:::;n, where vi; wi; xi; yi 2 R 8i = 1; :::; n. In this case the similarity operation u is de ned by the meet of tuple components:
a u b = h[vi; wi]ii=1;:::;n u h[xi; yi]ii=1;:::;n = h[vi; wi] u [xi; yi]ii=1;:::;n; where [vi; wi] u [xi; yi] = [min(vi; xi); max(wi; yi)].
Hence, subsumption on tuples of interval is de ned as: a v b , [vi; wi] v [xi; yi]i=1;:::;n , [vi; wi] u [xi; yi] = [vi; wi]i=1;:::;n , , [min(vi; xi); max(wi; yi)] = [vi; wi]i=1;:::;n , [vi; wi] [xi; yi]i=1;:::;n: For example, h[2; 6]; [4; 5]i v h[3; 4]; [5; 5]i as [2; 6] v [3; 4] and [4; 5] v [5; 5]. (2) (3) 2.3
In the previous sections we consider separately the cases of nominal and numerical initial features. However, the situation when patients have both nominal and numerical initial features seems more natural. As it is described above we associate the set of binary attributes with each nominal feature and an interval attribute - with each numerical one. So, d 2 D is a tuple, where components are intervals and binary attributes. Let us have k binary and n interval attributes. Assume d = h ; i where is the tuple of intervals of length n, and is the subset of binary attributes. If d1; d2 2 D, d1 = h 1; 1i, and d2 = h 2; 2i similarity operator can be set as d1 u d2 = h 1 u 2; 1 u 2i where similarity operators for the tuples of intervals and the sets of binary attributes are de ned above. The subsumption is also de ned by subsumption on the tuples of intervals and the sets of binary attributes: Pattern concepts can be computed by Close by One (CbO) algorithm. It produces a tree structure on pattern concepts where edges represent a subset of lattice edges. For the following analysis we do not need the whole lattice but the tree-structure provided by CbO is helpful for implementation of stopping criterion. Considering the top of the lattice is the pair (G; G ), and the bottom is (;; ; ) CbO starts from the bottom and proceeds \object-wise". However, when the number of objects is larger than the number of attributes processing top-down allows one to reduce computation time. Moreover, for the given problem we need to generate pattern concepts with as large extents as possible to detect the di erence in treatment e ciency. So, it is more reasonable to start generation process from the top of the lattice. As we operate on descriptions consisting from interval and binary attributes classical CbO must be adapted to such descriptions. For this purpose a version of CbO is proposed below. The idea is to order elements of descriptions, and start to reduce descriptions by changing its elements in this order.
Let objects be described by n interval and k binary attributes. So, we can rewrite description as d = hv1; w1; :::; vn; wn; b1; :::; bki, where vi and wi are the left and right bounds of the i-th interval attribute for i = 1; :::; n, and bj indicates whether description d contains the j-th binary attribute for j = 1; :::; k. So, if bj is 0 (g) does not contain the j-th binary attribute for all g 2 d , and if bj is 1, then (g) may or may not contain the j-th binary attribute for all g 2 d . In other words, 1 u 0 = 0 or 0 v 1. The de nition of similarity operator remains the same: we take minimum of left bounds, maximum of right bounds, and set intersection, which in the given notation can be written as element-wise conjunction of indicator vectors: d1 u d2 = hhmin(v1;i; v2;i); max(w1;i; w2;i)ii=1;:::;n; hb1;j ^ b2;j ij=1;:::;ki : (5)
The introduced version of CbO starts from the most general description and speci es it by reducing intervals and adding binary features. For interval reduction it is necessary to choose some step value si for each interval attribute (i = 1; :::n;). If we aim at some sort of scaling we can set these values by ourselves, or if scaling is unwanted si is set to the smallest di erence between values of the initial feature corresponding to the i-th interval attribute.
Further we denote dall = gF2G (g), min(d1; d2) denotes the minimum position of unequal elements of tuples d1 and d2 in element-wise comparison. Let suc(d) denote the set of all children of the node corresponding to the description d. Let prev(d) return the parent of d, address(d) return the address of d, and nexti(d) store the position of the description tuple d which must be changed at the next algorithm returning to d. Let denote integer division, % denote residue of division, and [ ] be an operator of taking the element of the tuple. Function AddConcept set required links between tree nodes when a new node is added. Function OneIteration changes the description dcurr given as argument in position nexti(dcurr) and takes closure of the changed description by ( ) . If min of the closure and dcurr is not less than nexti(dcurr) then the function returns the closure, otherwise it returns dcurr. 1. 2. 3. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.
def AddConcept(parent; child) suc(parent) address(child) prev(child) := parent nexti(child) := nexti(parent) def OneIteration(dcurr) dnew := dcurr i := nexti(dcurr) if i 2n then q = i 2 r = i%2 dnew[i] := dnew[i] sq(2r 1) dadd := dnew if dnew[2q] dnew[2q + 1] and min(dcurr; dadd)
AddConcept(dcurr; dadd) return dadd else return dcurr else dnew[i] := d[i] ^ 1 dadd := dnew if dnew[i] 6= d[i] and min(d; dadd)
AddConcept(dcurr; dadd) return dadd else return dcurr i then 0. d := dall; nexti(d) := 1; prev(d) := ;; suc(d) := ; 1. until d = dall and nexti(d) > 2n + k do 2. until nexti(d) > 2n + k do 3. dadd:=OneIteration(d) 4. if d 6= dadd then i then 5. 6. 7. 8.
d := dadd output(d; d ) else nexti(d) := nexti(d) + 1 d := prev(d)
Lines 7 and 14 of function OneIteration has complexity O((2n + k)jGj), and all lines 3{8 of the main part of the algorithm are performed at most in this time. The loop starting at line 2 is repeated 2njGj + k times at worst (as in the worst case each boundary of all interval attributes can take jGj values), while the loop starting at line 1 is repeated jLj times exactly, where jLj is the number of pattern concepts. So, the algorithm has complexity O((2n+k)jGj(2njGj+k)jLj). The complexity is higher than that of CbO, O((2n + k)jGj2jLj), but in practice our algorithm may become faster when n and k are small, and the number of numerical values in data is less than jGj. 4
As it is mentioned above it may not be required to generate all pattern concepts, and the version of CbO may stop when subgroups with di erence in treatment e ciency and maximal possible extent are generated. To estimate the di erence in e ciency for some description d we de ne a di erence measure which depends on the sets of outcomes of patients who match d and have received the same treatment, and if the value of this measure satis es some criterion of signi cance the proposed version of CbO stops to generate speci cation of the description which is currently in work.
Let p be the number of comparing treatment strategies, and d is the description currently processed by the algorithm. Assume Qi = foutcome(g) j g 2 d ; treatment(g) = ig for all i = 1; :::; p, where outcome(g) is the outcome of g, and treatment(g) is the treatment assigned to g. So, jQij denotes the number of patients received treatment i. We de ne di erence measure which takes the sets of outcomes corresponding to each treatment strategy and returns the estimation of di erence, and set threshold ".The criterion looks like if (Q1; :::; Qp) > " the algorithm does not generate the children of the currently processed node and returns to its parent node.
Except the stopping criterion itself several additional restrictions are necessary. So, if a subgroup does not contain patients per each of p treatment strategies we are not able to compute and need to return to the parent subgroup without generating children nodes, since the antimonotonicity of operator ( ) ensures this property for all descendants of the current node. Also, it may be important to result in descriptions with approximately equal number of patients per treatment strategy in corresponding subgroups. Therefore, additional parameter 2 [0; 1] is provided to control the ratio of each treatment strategy in a subgroup (see line 4 in function Restrictions). If is set to one this restriction is deactivated, if it is set to zero the numbers of patients per each treatment strategy must be equal. Let outc(d) be hQiii=1;:::;n, outc(d)[i] be Qi, and j j return the power of the set. Function Restrictions checks ful llment of these restrictions for a particular description. Let isempty(d) be F alse if the subgroups corresponding to description d do not contain patients from every treatment strategy, and T rue otherwise. Let also notBalanced(d) be F alse if the subgroup corresponding to d is not balanced (do not satisfy restriction on proportion of treatment strategies in the subgroup), and T rue otherwise.
def Restrictions(d) 0. isempty(d) := F alse; notBalanced(d) := F alse 1. for j from 1 to p do 2. isempty(d) := isempty(d) _ (joutc(d)[j]j = 0) 43.. snhoatBreal:=ancjoeudtj(cd(dd)j)[:j=]j notBalanced(d) _ ( 1 p
The algorithm outputs the set of maximal size subgroups (i.e. maximal extents) with signi cant di erence in treatment e ciency. Since we do not construct the whole pattern lattice the resulting set may contain subgroups which subsumed under the other subgroups from this set. Smaller subgroups should be excluded from the output by post-processing. 5 5.1
The dataset consists of more than 2000 patients from 1 to 18 years old with newly
diagnosed ALL. All of them were included into the standard risk group (SRG) or
into the intermediate risk group (ImRG) of randomized clinical trial
MB-ALL2008 [
Each patient from the dataset is described by the set of initial features, treatment strategy which he or she was assigned at randomization, and outcome features. From all initial features 8 were chosen for the analysis: sex (male or female), age (in years from the birth date to the start of the therapy), initial white blood count (per nl) (WBC), immunophenotype (B- or T-ALL), central nervous system (CNS) status (normal, cytosis is less than 5 per mcl and blast cells, neuroleukemia), liver enlargement (in cm), spleen enlargement (in cm), mediastinum status (normal or pathological). As for outcome features of the dataset each outcome feature consists of two parts: the result of the therapy and time from the beginning of the therapy to the date when the result was xed (in years). In this dataset we have two such features. One of them is xing the time before patient's death.This feature has three possible states: alive, lost to follow-up or death. When a patient is alive or lost to follow-up we say that censoring happened because we cannot measure exactly the time before death. The other outcome feature represents the time before a negative event . This feature can possess the following states: alive in remission, lost to follow-up, death in remission, secondary tumor, relapse or metastases, nonresponse to the therapy or disease progression, or death in induction. Alive in remission and lost to follow-up events correspond to censoring. Two types of outcomes are used for di erent variants of treatment e ciency estimation which are presented below.
Finally, we exclude patients with missed values from the further analysis and result in 1221 SRG patients: 387, 366, and 368 patients received T1, T2, and T3 respectively. 929 patients in ImRG: 467 and 462 patients received T4 and T5 respectively. 5.2
As it was shown above the initial features of the patients should be transformed into the tuple of interval and binary attributes. Age, WBC, liver enlargement, and spleen enlargement are numerical features, so for each of them an interval attribute is created. Moreover, we scale them a little to obtain subgroup descriptions which make sense for physicians. For example, it is not correct enough in medical terms that one treatment is more e ective for patients, let's say, up to 5.4 years old. Similar limitations should also be applied to other 3 numerical features. To answer these limitations we propose the following way of interval attributes construction: 1. Let one set the steps of interval reduction in CbO to sage = sliver = sspleen = 1 and sW BC = 10. 2. For each name 2 fage; liver; spleen; W BCg and for every g 2 D, where D is the set of all patients, if name(g) = x then the value of the corresponding interval attribute is set to [sname bx=snamec; sname dx=snamee].
All nominal features (sex, immunophenotype, CNS status, and mediastinum status) are converted to the set of binary attributes in the way presented in section 2.1. For instance, we construct two binary attributes corresponding to sex: one indicating males and another indicating females. 5.3
The algorithm of subgroup descriptions generation is proposed in Section 4. It
requires to set the di erence measure. For the data of the childhood ALL we
choose log-rank statistics [
As in SRG three treatment strategies (T1; T2; T3) are compared, the algorithm selected those subgroups where the di erence between any pair of the treatment strategies is signi cant. Assume one of descriptions we get is d. For the subgroup described by this description we should compare every pair of treatment strategies: T1 and T2, T1 and T3, and T2 and T3. For each pair where log-rank test detects the di erence with con dence 95% and power 80% we make a hypothesis. For instance, if pair Ti and Tj satis es these requirements then a hypothesis says that treatment strategies Ti and Tj a ect patients described by d di erently. At the same time if the survival curve for Ti, for instance, is located above the survival curve for Tj we can even say that Ti is better for patients described by d than Tj . For patients from ImRG only two treatment strategies are compared. Therefore it is enough to estimate power, and if it is more than 80% we make a hypothesis in the same way. 5.4
The proposed algorithm was run to compare separately overall survival (OS)[
The results of experiments for SRG are presented in Table 1. OS, EFS, and
RFS stand for three types of survival described above, CbO stands for the
proposed approach, and IT stands for Interaction Tree from [
We would like to thank Prof. Alexander I. Karachunskiy and his colleagues from the Federal Research Institute of Pediatric Hematology, Oncology and Immunology, Moscow, Russia for helpful discussions and for providing us with data on MB-ALL-2008 protocol.