accurate prediction of outcomes or survival rates of cancer patients is often key to stratify patients for prognosis and treatment .
outcomes of patients are usually    generated using standard survival functions and various factors recorded in the database ( such as seer   or ncdb ) that have prognostic potential .
all prognostic factors become integrated through determination of the outcome according to the survival rate .
this integration leads to a prognostic system that can be used to predict outcomes of any new patients .
clearly , a crucial question is how can one form a powerful prognostic system for cancer patients ?
the traditional answer to this question is to use the tnm system   that involves only three factors : tumor extent , lymph node involvement , and metastasis .
however , the outcome prediction from the tnm has been limited , mainly because any other potential prognostic factors are not used in the system . in this paper , we propose a computer - based prognostic system for cancer patients that admit multiple prognostic factors . here
is idea of our approach : ( i ) we partition patients from a cancer dataset into  natural  groups such that patients in the same group are more similar in survival than patients from different groups ; ( ii ) once  natural  groups are obtained , a survival function for each group can be estimated by a standard method .
our prognostic system then consists of groups of patients and survival functions associated with the groups .
mathematically , this step is equivalent to performing a cluster analysis on a cancer dataset .
however , this type of cluster analysis is different from traditional clustering approaches , which may be elaborated below .
suppose , after some simple management , a typical record for a patient contained in a cancer dataset is of the form : x , x1 , 
, xm , where x is the recorded patient 's survival time , which can be a censored time , and x1 ,  , xm are measurements made on m risk factors or variables such as tumor size , gender , and age .
cluster analysis rising in ( i ) means that clusters of patients are sought such that patients in the same cluster are more similar in their lifetime t than patients from different groups . here the connection between t and the observed time x is described as follows :
t = x if x is an actual time to death due to the cancer under study ;
therefore , cluster analysis from ( i ) is not equivalent to partitioning the set of vectors { ( x , x1 ,  , xk ) } or the set { ( x1 ,  , xk ) } which could be suggested by traditional clustering methods .
the above discussed difference between the cluster analysis in ( i ) and the traditional clustering indicates that clustering required in ( i ) may not be a trivial task .
other potential challenges in accomplishing ( i ) include presence of a high percentage of censored observations , different types of risk factors or variables , and a large dataset size [ 46 ] .
for example , an seer dataset of lung cancer patients diagnosed from 1973 through 2002 has more than 500 000 patients , comprises more than 30% records with censored survival times , and involves more than 80 variables that are either on the continuous , or ordinal , or nominal scale . to overcome the above mentioned possible difficulties
, we consider subsets of a cancer data , based on combinations of levels of some known key factors .
we then group these subsets by a hierarchical clustering algorithm , where the distance measure between two subsets is learnt through multiple clustering based on partitioning around medoids ( pam ) of kaufman and rousseeuw .
an application of our algorithm to establishing a prognostic system for lung cancer patients is provided in section 4 . and
, we will use the pam algorithm ( a partitioning algorithm ) and linkage methods ( special cases of hierarchical clustering techniques ) .
censored survival times often occur in a cancer dataset and represent on type of incomplete data .
a survival function provides a probability of survival to certain times for a cancer patient .  
pam is a partitioning method operating on a dissimilarity matrix , a matrix of pairwise dissimilarities or distances between objects .
it starts from selecting initial k ( a predetermined number ) representative objects , or medoids , assigning each data object to the nearest medoid , and then iteratively replaces one of the medoids by one of the nonmedoids which leads to a reduction in the sum of the distances of the objects to their closest medoids .
the similarity measure here includes , as a special case , the euclidean distance , which is used with the k - means algorithm .
pam is more robust than the k - means approach , because it employs as cluster centers the medoids not the means , and minimizes a sum of dissimilarities instead of a sum of squared euclidean distances .
commonly used linkage methods include single linkage ( sl ) , complete linkage ( cl ) , and average linkage ( al ) .
they are special cases of agglomerative clustering techniques , operate on a given dissimilarity matrix , and follow the same procedure beginning with the individual objects , at each intermediate step two least dissimilar clusters are merged into a single cluster , producing one less cluster at the next higher level .
the difference among the linkage methods lies in the dissimilarity measures between two clusters , which are used to merge clusters .
sl , cl , and al define , respectively , the dissimilarity between two clusters to be the minimum distance between objects from these two clusters , the maximum distance between objects from these two clusters , and the average distance between objects in the two clusters .
the output of a linkage method is often summarized into a plot where the nested clusters are graphically represented as a tree , called a dendrogram .
two clusters merge at a height along a dissimilarity axis that is equal to the dissimilarity between the two clusters .
cancer data are often time - to - event data that present themselves in different ways , imposing great challenges in analysis .
censored observations come from the mechanism of monitoring the progress of patients from some point in time , such as the time a surgical procedure is performed or a treatment regimen is initiated , until the occurrence of some predefined event such as death .
censoring comes in many different forms and right censoring is widely used in clinical studies .
right censoring is used to record the amount of time elapsing between the point at which the patient entered the study and the point at which he or she experienced one of the following three events : the event of interest ( e.g. , death for most of the cancer studies ) ; loss to follow - up for some reason such as death caused by a health problem other than the one being considered or having moved to another locality ; alive at the time the study is terminated .
the time elapsing between enrollment in the study and experiencing one of these three events is called the patient 's survival time .
a survival time is censored if it is not the actual time between enrollment and experiencing the event of interest .
given a censored survival time for a patient , all we know about the lifetime of the patient is that it is greater than some value .
in addition to the commonly used probability density function , the distribution of t can also be characterized by the survival function , defined to be s(t ) = p(t > t ) .
the function s(t ) provides the probability of surviving beyond t. the survival function is usually estimated by a nonparametric method referred to as the kaplan - meier estimator .
a direct comparison of several survival curves can be conducted by examining the curves appearing in a single graph .
a theoretical comparison of several survival functions can be made by conducting a commonly used test such as the log - rank test , gehan 's test , breslow 's test , and test of tarone and ware .
, the k - means clustering uses euclidean distance as a dissimilarity measure . since cancer data involve censored survival times , a direct use of existing clustering algorithms is not applicable . with cancer data , it is important to find a way to define objects and dissimilarity between objects prior to execution of any clustering algorithm .
suppose , for a cancer data set , a certain number of factors have been selected for consideration .
specifically , a combination is a subset of the data that correspond to one level of each factor .
, xn . a combination plays a role of an object in the cluster analysis . when developing a prognostic system , we need to find groups of patients such that patients within each group are more similar in survival than patients from different groups .
assuming that all patients coming from the same combination have a similar survival rate , then this is equivalent to finding natural groups of combinations .
after objects become available , we can start to define a dissimilarity measure between objects .
a dissimilarity measure dis(xi , xj ) is a nonnegative function that is symmetric with respect to xi and xj . for cancer data ,
a direct method is to define the dissimilarity between two combinations in light of the difference between the two corresponding survival functions , and the details follow below . given two combinations xi and xj , testing if there is a difference between the corresponding two survival functions can be done by conducting a commonly used test such as the log - rank test .
it is known that a smaller value of a test statistic shows a stronger evidence of no difference .
thus we can define dissimilarity or  distance  between xi and xj to be 
						 ( 1)dis0(xi , xj)=  the  value  of  a  test  statistic . 
					
this dissimilarity measure in ( 1 ) is not the one we actually use when developing cancer predictive systems .
in fact , we will use the dissimilarity ( 1 ) for the pam algorithm only and generate a learnt dissimilarity measure for the cancer data through combining assignments from multiple clusterings based on the pam algorithm .
this learnt dissimilarity will then be used with a hierarchical clustering algorithm to produce prognostic systems .
and then we present an ensemble clustering algorithm using the learnt dissimilarity and linkage methods to develop prognostic systems for cancer patients .
prior knowledge is often helpful in selecting an appropriate dissimilarity measure for a given problem .
we describe such a procedure as follows . partitioning methods are usually not stable in the sense that the final results often depend on initial assignments .
however , if two objects are assigned to the same cluster by a high percentage of the times of use of the same partitioning method , it is then very likely that these two objects come from a common  hidden  group .
this heuristic implies that the  actual  dissimilarity between two objects may be derived by combining the various clustering results from repeated use of the same partitioning technique .
, xn } , we can select k initial medoids and then run pam with the dissimilarity measure ( 1 ) to partition the data into k clusters .
each time a number k is randomly picked from a given interval [ k1 , k2 ] . by doing this
, we may end up with n possibly different final assignments . given two objects xi and xj ,
let pij denote the probability that they are not placed into the same cluster by the final assignment of a run of pam .
define l(i , j ) = 1 if the lth use of the pam algorithm does not assign xi and xj into the same cluster ; and l(i , j ) = 0 otherwise .
then 1(i , j ) , 2(i , j ) ,  , n(i , j ) are i.i.d bernoulli ( pij ) .
it is well known that the best unbiased estimator of pij is l = 1l(i , j)/n .
this estimate will be used as the dissimilarity measure between xi and xj , that is , 
								 ( 2)dis(xi , xj)=l=1nl(i , j)n . 
							 a smaller value of dis(xi , xj ) is expected to imply a bigger chance that xi and xj come from the same  hidden  group . with the learnt dissimilarity ( 2 ) between the combinations , we can choose a clustering method to form 
the final ensemble algorithm of clustering of cancer data ( eaccd ) is shown in algorithm 1 .   here
the word ensemble refers to the sequence of the pam procedures involved in the method .
early issues on ensemble clustering were discussed in   from the perspective of evidence accumulation .
the work in   combined the k - means algorithm and linkage methods to form an ensemble method of discovering sample classes using gene expression profiles .
in this study , we used the seer data   containing records of lung cancer patients diagnosed from the year 1988 through 1998 and examined the following factors : ajcc stage , grade , histological type , and gender .
we considered four factors , x1 , x2 , x3 , and x4 that were set to be stage , grade , histological type , and gender , respectively . for simplicity , we only investigated the following four important levels of x3 : adenocarcinoma , squamous cell carcinoma , large cell carcinoma , and small cell carcinoma .
the levels of other three variables were those commonly used in the lung cancer study .
factor x1 had four levels : i , ii , iii , and iv ; factor x2 had four levels : 1 , 2 , 3 , and 4 ; and factor x4 had two levels : 1 ( male ) and 2 ( female ) .
the final data we actually used involve 90,214   patients . a portion of the data , in terms of x(survival time ) , x1 , x2 , x3 , and x4 , is provided in table 1 . before running our algorithm eaccd
, we used the levels of four factors x1 , x2 , x3 , and x4 to partition the dataset into 128(= 4  4  4  2 ) combinations , shown in table 2 .
due to the approximation of the chi - square distribution to the log - rank test statistic , a combination containing less than 100 patients was dropped from our study . in this case , no further analysis was done for these combinations , and our attention was paid to all the other combinations that have a size equal to or larger than 100 . for example , comb 5 , comb 6 , comb 7 , comb 8 , comb 124 , as shown in table 2 , were dropped from our study . under this restriction we only kept   80 combinations , leaving out a total of 1,264   patients . to run our algorithm eaccd , we chose parameters as follows .
the choice of n depends on the rate at which dis in ( 2 ) converges to pij .
a large number should be chosen for n , and for this purpose we set n = 10000 .
any theoretically possible choices of k was used in running pam , and thus we set k1 = 2 and k2 = 79 , due to availability of 80 objects .
in addition , the log - rank test was used to obtain the measure ( 1 ) for the pam algorithm . and
the output of cluster analysis for these 80 combinations is shown in figure 1 , where for simplicity comb has been removed from each combination or label .
cutting off the dendrogram at a specified height of the dissimilarity axis partitions data into disjoint clusters or groups .
cutting at different heights usually leads to different numbers of groups . as an example ,
if we cut the dendrogram in figure 1   at a height slightly above 0.90 , then we obtain 7 groups shown in table 3 .
the log - rank test shows that any two groups differ significantly ( using a significance level of   0.01 ) in their survival functions .
figure 2   shows the kaplan - meier estimates of the survival curves for the 7 groups .
these 7 groups and their survival curves constitute a prognostic system for lung cancer patients , as discussed in step ( ii ) of the section of introduction .
prediction using this system is then carried out in the usual way . in comparison ,
those 4 survival curves from the tnm system , based on all the patients from the 80 combinations , are provided in figure 3 .
group 1 , 5 , 6 , and 7 only contain some cases from stage i , iii , iv , and iv , respectively .
both groups 2 and 3 contain stage i cancer cases , indicating that additional relevant parameters are associated with increased relative biologic aggressive tumor behavior .
group 4 consists of some cases from stage i , ii , and iii , suggesting that localized biologically aggressive cancers may have the same survival as more indolent advanced staged cancers .
in this paper we have introduced an ensemble clustering based approach to establish prognostic systems that can be used to predict an outcome or a survival rate of cancer patients .
generalizing or refining the work presented in this paper can be done in many ways .
our algorithm eaccd actually is a two - step clustering method . in the first step
, a dissimilarity measure is learnt by using pam , and in the second step , the learnt dissimilarity is used with a hierarchical clustering algorithm to obtain clusters of patients .
improvement of dissimilarity measures   ( 1 ) and ( 2 ) , as well as the effect of different algorithms used in each step will be investigated in our future work .
refined algorithms , based on eaccd , will be sought and resulting prognostic systems with clinical applications will be reported .
 accurate prediction of survival rates of cancer patients is often key to stratify patients for prognosis and treatment . 
 survival prediction is often accomplished by the tnm system that involves only three factors : tumor extent , lymph node involvement , and metastasis . 
 this prediction from the tnm has been limited , because other potential prognostic factors are not used in the system . 
 based on availability of large cancer datasets , it is possible to establish powerful prediction systems by using machine learning procedures and statistical methods . in this paper , we present an ensemble clustering - based approach to develop prognostic systems of cancer patients . 
 our method starts with grouping combinations that are formed using levels of factors recorded in the data . 
 the dissimilarity measure between combinations is obtained through a sequence of data 
 partitions produced by multiple use of pam algorithm . 
 this dissimilarity measure is then used with a hierarchical clustering method in order to find clusters of combinations . 
 prediction of survival is made simply by using the survival function derived from each cluster . 
 our approach admits multiple factors and provides a practical and useful tool in outcome prediction of cancer patients . 
 a demonstration of use of the proposed method is given for lung cancer patients . 
1. Introduction
2. Some Elements of Clustering and Survival Analysis
3. Algorithm of Clustering of Cancer Data
4. Results on Lung Cancer
5. Conclusion