基于非参数分类k最邻近节点算法的多维放射诊断数据评价

Matthias Dietzel, Andreas Dietzel, Ramy Zoubi, Hartmut P.Burmeister, Martin Bogdan,Werner A.Kaiser, Pascal A.T.Baltzer

1 INTRODUCTION

In modern radiology, final diagnosis is based on an increasing amount of information provided by one single examination.Particularly in magnetic resonance imaging (MRI), the radiologist is challenged with numerous different sequences, complex enhancement data and hundreds of images[1].Thus, in MRI it is particularly dif fi cult to condense all information into one fi nal, binary diagnostic decision, e.g.: “Do we deal with a malignant or benign lesion?” Recent developments in MRI, frequently address the univariate evaluation of further technical aspects, e.g.spectroscopy, diffusion weighted imaging etc[2-3].On the one hand, such research further increases knowledge on technical and biological issue.Yet to date, no diagnostic item has been developed that can solve a diagnostic question as a standalone method.Moreover, most clinical decisions are usually a multidimensional one.This is why on the other hand such research also runs the risk to significantly complicate the integration of diagnostic information into the fi nal clinical decision.And such: To get caught be the so-called “curse of dimensionality”[4].

Breast MRI is a typical example of this development: in the third decade of clinical evaluation,it is backed up by an increasing level of evidence in numerous clinical scenarios[1,5-7].However, in the literature specificity of breast MRI is still discussed controversially.Accordingly, numerous researches have focused on new techniques to further increase this parameter: Some recommend additional sequences,e.g.diffusion weighted imaging to further refine tissue assessment.Others use computer assisted diagnosis(CAD) interpretation to guide analysis of enhancement characteristics[2-3,8].This approach leads to a further increase of data, as CAD provides numerous parameters to the operator.Further investigators favor to go “back to the roots” and to read breast MRI examination in a very detailed way[9-10].To report such findings,multiple categorical descriptors are used, which allow -hypothetically-a more detailed tissue analysis and thus to increase accuracy.Although all such approaches are concurring, they have one thing in common: they add further data to every single diagnostic exam.Data that has to be read in combination with all other information available and thus making differential diagnosis to a challenging multidimensional task.

Our human brain has limited capabilities to process multidimensional data.Furthermore, we are more used to linear relations of single items.Thus, non-linear associations of diagnostic information, with numerous degrees of freedom are difficult to assess.Similarly,ordinal scoring systems, as they are frequently used in clinical routine, have significant methodological limitations[9].This is particularly problematic if such scores are applied to multidimensional, nonlinear data[11].Machine learning methods provide algorithms,which can automatically learn and recognize complex pattern based on empirical data irrespective of data distribution.The k-nearest neighbors algorithm (kNN) is among the oldest machine learning methods for pattern recognition[12].The basic principle of classification is shown in Figure 1.KNN is flexible to incorporate different types of data and is feasible to adapt to irregular feature spaces.It has been successfully applied to many medical fields[13].However, kNN are not commonly used for the evaluation of complex multidimensional MRI data in modern radiology and for differential diagnosis[14].

Fig.1 Schematic drawing of the basic principle of the k-nearest neighbor algorithm (kNN): “triangles” indicates lesions with known malignant histology, whereas “circles” are lesions with known benign histology.“Star” is a lesion with unknown histology.In this example a two dimensional input vector is used.Each dimension equals one descriptor.All lesions are clearly de fi ned within this feature space by there coordinates,i.e.descriptors.

Therefore, this study aims to evaluate the potential of kNN for nonparametric classification within a large radiological dataset and to systematically investigate diagnostic accuracy of the algorithm depending on the dimension of the input vector.

2 METHODS

2.1 Database

Basis of this investigation were all breast MRI examinations performed at our institution over 12 consecutive years.Indications for MRI were: unclear or suspicious findings in preceding breast examinations,i.e.mammography and/or breast ultrasound.Eligible for inclusion into the database were all patients with subsequent histological verification at our Institute of Pathology after MRI.To control for post therapeutical bias, patients with recent breast biopsy, surgery or radiation and/or chemotherapy (up to 12 months before MRI) were not eligible.This study was approved by our local ethical committee and patients had given written consent to the examination.

2.2 Index Test

Standardized protocols were applied at 1.5 Tesla field strength using dedicated receive only bilateral breast coils (Symphony/VisionPlus; Siemens AG,Erlangen/Germany; Intera/GyroscanACSII; Phillips Medical Systems, Best/ The Netherlands).Standard scan orientation was axial and patient position was prone in all cases.Protocols started with repetitive spoiled dynamic T1-weighted gradient echo sequences at 1-minute intervals (n=8).After the first pre-contrast scan, the contrast agent (Gd-DTPA: Magnevist, Bayer/Schering HealthCare, Leverkusen, Germany) was administered intravenously as a bolus using an automated injector(3 ml/sec).After a delay of 35 seconds, the remaining 7 measurements were performed.Postprocessing provided subtractions of pre- from postcontrast dynamic images.To further refine tissue analysis, one T2-TSE sequence (Phillips: FFE) without fat saturation was acquired in the same orientation and slice position.Technical parameters for T1w scans were 100—110ms (TR), 5 ms (TE), 80° (flip angle), 3—4 mm (Slice thickness), 350mm (FOV) and 256—384 pixel (Matrix).Technical parameters for T2WI scans were 4000—8900ms (TR), 200—300ms (TE), 90° (Flip Angle), 3—4 mm (slice thickness), 350mm (FOV) and 256-512 pixel(Matrix).

2.3 Interpretation of Index Test

Two radiologists with high level of experience and special training (＞500breast MRI) evaluated all examinations in consensus.They were blinded to histopathological outcome.For image interpretation,definition of the term “lesion” was in agreement with the literature[9-10,15].For size measurement, the largest diameter of the enhancing lesion upon postcontrast T1 weighted images was used.Following the TNM classification, it was categorized as follows: ≤5 mm,5—10mm, 10—20mm, 20—30mm, 30—50mm and ＞50mm[16].Composition of every lesion was analyzed using a catalogue of previously published descriptors[9,10].Presence of each single descriptor was documented in the database (categorical scale):

First, it included basic dynamic (Wash-in; Wash-out, persistent increase, Plateau) and morphologic descriptors (shape, margin, internal structure, septation).Such, were defined and assessed as published previously[15,17].

Second, it integrated more detailed breast MRI descriptors.These have been included in a linear interpretation model for the differentiation of benign from malignant breast masses[9]: “Blooming sign”addresses dynamic enhancement of lesions[9].It describes findings with initially sharply shaped borders (1 min after injection of Gd-DTPA), getting unsharp 7 min after contrast media application.If markedly prolonged T2 times of soft tissue were present, “Edema” was diagnosed[18].“Hook sign” describes spiculated dendrites coming from the lesion’s center with clear connection to the pectoral wall[19].“Necrosis Sign” describes central colliquitations in T2WI scans and was positive,if a hyperintense center in a hypointense lesion was present[10].“Root sign” was positive in case of isolated Spicula (irregularity in the lesion’s margin) without contact to the pectoral wall[9-10].“Skin thickening” was diagnosed, if the ipsilateral breast revealed skin thicker than the contralateral one.If a vessel leading to a lesion could be clearly delineated, “Adjacent Vessel” was diagnosed[20].If asymmetric vessels were present in the ipsilateral breast, this fi nding was de fi ned as “Prominent Vessels”.More detailed de fi nition and examples of each descriptor can be found in the primary literature[9-10,15].Table 1 summarizes breast MRI descriptors as applied in this investigation.

2.4 Reference Standard & Dataset

Toachieve most accurate results,surgicopathological verification of lesions was defined as reference standard.It was performed at our af fi liated Institute of Pathology by experienced, board certified breast pathologists.The Elston-Ellis method was used for tumor grading[21].According to results of the histological investigation, the dataset of the present study was extracted from the database.To initially evaluate the kNN algorithm within the given setting, we selected all invasive ductal cancers (malignant subgroup) and all papillomas, phylloid tumors and fi broadenomas (benign subgroup).This was done, as such histopathologies usually present as clear “mass lesions” for which the interpretation criteria used in this study were initially evaluated[9].

2.5 K-Nearest Neighbor Algorithm (kNN)

A kNN was applied to process the dataset.For this purpose, dedicated software was used (Matlab 7,The-Math Works/Inc., Natick, MA/USA; the Spider for Matlab Version 1.7, MPI Tubingen/Germany),which was operated by a computational scientist with high experience in non parametric machine learning[12].A gaussian radial basis function (sigma=1.2)was implemented to assess nearest neighbors.Breast MRI descriptors including lesion sizes were defined as input variables resulting in an n-dimensional inputvector (n: number of descriptor included into the model).Histological results (“benign” or “malignant”) were set as target variable.Predictive values were assigned by the kNN to every single lesion.For this purpose 4-fold Cross Validation was applied.Thus, bias due to overlap between model-building data and testing samples could be excluded, leading to a realistic estimate of prediction quality[22].In the next step, the value “k” was fine-tuned.This value addresses the number of nearest neighbors that are considered by the kNN when making a prediction.According to methodological and empirical considerations, “k” was subsequently set to 1, 3, 5, 7, 911 and 21, respectively.Predictive values of all seven corresponding kNN were then saved as described above.

2.6 Recursive Feature Elimination (RFE)

To identify the optimal dimensionality of the inputvector, RFE was applied[23].This was done to address the number of training instances, the dimensionality of the input vector and to decrease possible noise or redundancy.Recursive Feature Elimination is an intelligent algorithm based on support-vector machines and was used to analyze importance of individual features.Accordingly, RFE assigned every descriptors to a rank[23].The latter coded the importance of individual descriptors (rank 1 to rank 18).According to the results,4 categories of descriptors were created as follows:Top-3 (rank 1—3), top-7 (rank 1—7), top-12 (rank 1—12) and all (rank 1-18).The corresponding input vectors were then further processed by the kNN as described above.

2.7 Statistical Evaluation

Receiver operating characteristics (ROC) analyzes were applied to analyze predictive values of the given kNN in correlation to the reference standard (histology).It was followed by quantification of the correspondingarea under the ROC curve (AUC).This was done for all 4 sets of descriptors separately (i.e.: “top-3”, “top-7”,“top-12”, “all”), using seven different values for “k” for each set (k: 1, 3, 5, 7, 911, 21).The “k” yielding the highest AUC within each category was defined as the most appropriate.Finally, the four corresponding kNN with such optimized k were assessed by means of inter-AUC comparison.For statistical analysis appropriate

software packages were used (PASW 18, SPSS, Chicago,III/USA and MedCalc 11, Mariakerke/Belgium).

Tab.1 Prevalence of MRM-descriptors in benign vs.malignant lesions and importance for differential diagnosis

3 RESULTS

3.1 Participants and Reference Standard

543 lesions in 480patients were included into the dataset (mean age: 55.1 years, range of 16 to 87 years).Histological veri fi cation de fi ned 63.9% (347/543) of all lesions as malignant (invasive ductal cancer: mean age:58.6 years, range of 25 to 87 years).Thirty-one cancers were grade 1 (8.9%), 136 grade 2 (39.2%) and 174 grade 3 (50.1%).In 6 lesions no grade could be determined(1.7%).Histology diagnosed 36.1% (196/543) of all lesions as benign (mean age: 49.1 years, range of 16 to 78 years).52.6% were fibroadenomas (103/196), 5.1%were phylloid tumors (10/196) and 42.3% papillomas(83/196).As summarized in table 2 small lesions tended be benign, whereas prevalence of malignity was associated with advanced tumor size (P＜0.001).Table 1 summarizes prevalence of all descriptors in association with histology.

3.2 K-Nearest Neighbor Algorithm (kNN)

Recursive Feature Elimination (RFE): Tumor diameter was of minor importance for differentialdiagnosis (rank 13).Further rankings of individual descriptors were assigned by RFE as summarized in Table 1.As demonstrated there, most basic descriptors were of minor importance for differential diagnosis by the kNN (e.g.Internal structure, Wash-in, Internal enhancement, Shape)[17].On the other hand, numerous additional descriptors were amongst the highest ranks(Signal intensity [T2WI], Necrosis-sign, Root-sign, Skin thickening, and Destruction of nipple line)[24].According to such results, 4 categories of input-vector were created,i.e.“top-3”, “top-7”, “top-12” and “all”.

Tab.2 Association of lesion size with histology

Optimization of kNN: Top-3 descriptors: optimal AUC was reached, if a high number of k (n=21) was chosen (AUC=0.816).Top-7 performed best, if k was set to 11 (AUC=0.895).If the input vector included the twelve highest ranking descriptors (top-12), it performed best using k=7 (AUC=0.928).If all descriptors were set as input variables, intermediate number of k was sufficient for accurate differential diagnosis (k=11,AUC=0.940).Detailed results on association of AUC with “k” are summarized in table 3.

Inter AUC-comparison: Highest AUC was reached, if all 18 descriptors were used (AUC=0.940, standard error=0.01, P [vs.AUC=0.5]＜0.001).

Tab.3 Association of “k” with diagnostic accuracy within four different input-vectors

Tab.4 Diagnostic accuracy of the kNN using four different input-vectors

Accuracy decreased slightly by 0.01, if dimensionality of the input vector was decreased by one third (all vs.top-12: P=0.23).Any further decrease of input variables significantly lowered overall accuracy of the classifier(P＜0.05).Table 4 summarizes diagnostic accuracy of the kNN using four different input vectors.Figure 2 gives the ROC curve of the most accurate classi fi er (18 input variables).Figure 3 demonstrates classification results using box plots.

4 DISCUSSION

Our results indicate the feasibility of kNN to automatically recognize complex radiological patterns and to apply those patterns for differential diagnosis[12].Accordingly, diagnostic accuracy of this classical Machine learning algorithm was “excellent”, reaching an AUC up to 0.940[25].These results were achieved using 4-fold Cross-Validation, omitting overfitting of the algorithm on previously known data and thus are likely to re fl ect accuracy of the system in a less scienti fi c setting[22].

Breast cancer is a heterogenous disease.Accordingly, it can not be characterized with single items[9].Such hypothesis is in consistence with our data:Overall accuracy of the classi fi er increased signi fi cantly with raising dimensionality of the input vector.Accuracy could even be further increased, if a binary number of descriptors was chosen [“top-12”[9,17]].Generally, raising the quantity of input dimensions also raises the risk of getting caught by the “curse of dimensionality”.If one is

Fig.2 Diagnostic accuracy of the kNN (k-nearest neighbor algorithm) for differential diagnosis of malignant vs.benign breast lesions: Applying 4-fold “cross validation” in 543 histologically veri fi ed lesions an AUC (area under the curve)of 0.940could be identified (confidence interval: 0.921—0.959).In this case k (i.e.number of nearest neighbors) was set to 11 and all descriptors as given in table 1 were used as input variables.(thick line: AUC, thin lines 95% confidence intervals; dotted line: zero-hypothesis, i.e.AUC=0.5).

Fig.3 Graphical illustration of true and false positive classi fi cations of 347 malignant and 196 benign lesions in MR Mammography by the kNN (k-nearest neighbor algorithm).Box plots are based on cut-off values for the predicted probability and were set to ＞0.6346 in the given example(model parameters as of fi g.2).

dealing with a database of fi xed size, this “curse” limits assessment of accuracy.If data is possibly non-linear and cross correlated, this “curse” is particularly problematic.Notably, such assumptions have to be made, if linear scores are applied to radiological systems.Yet, if such assumptions are not valid, results could be signi fi cantly biased.The kNN is a nonparametric multivariate classi fi er.It was accurate, using an input vector of up to 18 single descriptors.Accordingly, our data demonstrate the potential of kNN to handle multidimensional in a radiological setting.

Importance analysis of individual descriptors by the Recursive Feature Extraction, showed surprising results[23]: Beside the criterion “margin”, none of the classical breast MRI descriptors were among the top 7 ranking descriptors.Moreover, most classical items ranked low, e.g.“shape” (rank 13) and “internal structure” (rank 18; c.f.table 1)[17].The assessment of“margin”, “signal intensity (T2WI)” and “Necrosis-sign”allowed accurate differential diagnosis of lesions (top-3:AUC=0.816).Such results were somewhat unexpected from an empirical perspective[17].Besides “margin”,these three descriptors are usually used to further re fi ne tissue assessment, but not for initial assessment of lesions.The fundamental assessment of breast MRI is based on human empirical criteria[9,15,17].Such learning rules are often based on, e.g.: (subjective) experience,(pathophysiological) assumptions or (empirical)knowledge.Without question this list is worthy of discussion and will never be complete.Nevertheless, it illustrates that assessment depends on distinct perception criteria, which are entirely different from the learning rules applied by learning algorithms.The latter simply do not know anything beyond the data and just classi fi es dependent on distinct algorithms (c.f.Figure 1).Accordingly, there is also a shift of perspective between both approaches.And this shift of perspective also is likely to shift the importance of single features for overall classi fi cation.Such considerations might be one approach to explain why typical diagnostic criteria, e.g.BI-RADS descriptors, were less important for the RFE-algorithm[9,15,17].

We could demonstrate that kNN is a feasible candidate for differential diagnosis within the given dataset[12].Yet, as any other learning algorithm, kNN has several limitations: first, it is not a very efficient algorithm from a computational perspective.Practically it means that calculation time significantly increases with amount of input data (roughly exponentially).Yet,this aspect is only of signi fi cant practical importance, if sizes of databases are major (＞10.000samples).As such quantities are not to be expected in the given radiological setting, this disadvantage is likely to play a minor role.Second, kNN do not produce a model or formula that could be saved and used for further evaluations[26].This is why it rather works as a black box and no learning or decision rule can be deduced.

Classification results significantly depend on quality of input data: On the one hand our dataset contained selected material: As this was a surgical series, a selection bias towards malignant lesion had to be accepted.However, this was necessary as we aimed to achieve the highest possible reference standard[27].Accordingly, we choose histological veri fi cation as gold standard.On the other hand, the used descriptors are qualitative and categorical parameters.Accordingly,observer related bias can not be excluded[27].We aimed to control this bias, as we chose consensus rating by two experienced readers, which were highly familiar with the nomenclature of the descriptors.

Future studies should include a case by case comparison of different classification systems.Such investigations could correlate the results of machine learning algorithms with the human reader and thus identify incremental value of the system[27].As described in the introduction section, several approaches exist to further optimize accuracy of breast MRI[2-3,8].This is why ultimately, the input-vector should be further maximized and include all currently available clinical breast MRI data on a suf fi cient sized database.Thus, it could include information from different newer sequences (MRS, DWI etc.) and postprocessing methods(CAD) etc.[2-3,8].Such analysis would further allow identifying the most promising technical development not only in a uni- but also multivariate pattern and thus might aid radiological research in a distinct, less empirical direction.

Summarizing, kNN was a highly accurate classi fi er for the evaluation of complex multidimensional radiological information.Using a large clinical dataset,cross validated results reached high diagnostic accuracy(AUC=0.940).Recursive feature extraction demonstrated increase of accuracy, even if number of input variables was already binary.This underlines the potential bene fi t of kNN for the assessment of multivariate radiological data.Future studies should further validate our results and aim to identify incremental clinical value as a second reader opinion to the radiologist in the assessment of diagnostic examinations.

ACKNOWLEDGEMENTS

The long term database of this study could only be collected due to the ongoing contribution of the whole tean.therefore, we would like to thank all those, who participated in data collection, in particular our MRI technicians and former colleagues.

[1]Schnall MD, Blume J, Bluemke DA, et al.Diagnostic architectural and dynamic features at breast MR imaging:multicenter study.Radiology, 2006, 238(1): 42-53.

[2]Mountford C, Ramadan S, Stanwell P, et al.Proton MRS of the breast in the clinical setting.NMR Biomed, 2009,22(1): 54-64.

[3]Baltzer PAT, Renz DM, Herrmann KH, et al.Diffusionweighted imaging (DWI) in MR mammography (MRM):clinical comparison of echo planar imaging (EPI) and half-Fourier single-shot turbo spin echo (HASTE) diffusion techniques.Eur Radiol, 2009, 19(7): 1612-1620.

[4]Bellmann R.Adaptive Control Processes: A Guided Tour.Princeton, NJ: Princeton University Press, 1961.

[5]Houssami N, Ciatto S, Macaskill P, et al.Accuracy and surgical impact of magnetic resonance imaging in breast cancer staging: systematic review and meta-analysis in detection of multifocal and multicentric cancer.J Clin Oncol, 2008, 26(19): 3248-3258.

[6]Kaiser W.MRI of the female breast.First clinical results.Arch Int Physiol Biochim,1985, 93(5): 67-76.

[7]DeMartini W, Lehman C.A review of current evidencebased clinical applications for breast magnetic resonance imaging.Top Magn Reson Imaging, 2008, 19(3): 143-150.

[8]Baltzer PA, Freiberg C, Beger S, et al.Clinical MR-mammography: are computer-assisted methods superior to visual or manual measurements for curve type analysis?A systematic approach.Acad Radiol, 2009, 16(9): 1070-1076.

[9]Malich A, Fischer DR, Wurdinger S, et al.Potential MRI interpretation model: differentiation of benign from malignant breast masses.AJR Am J Roentgenol, 2005,185(4): 964-970.

[10]Kaiser WA.Signs in MR-Mammography.Berlin,Heidelberg, New York: Springer, 2007.

[11]Duda RO, Hart PE, Stork DG.Pattern Classi fi cation.NewYork: Wiley-Interscience, 2000.

[12]Patrick EA, Fischer FP.A generalized k-nearest neighbor rule.Information and Control, 1970, 16(2): 128-152.

[13]Yao Z, Ruzzo WL.A regression-based K nearest neighbor algorithm for gene function prediction from heterogeneous data.BMC Bioinformatics, 2006, 7(Suppl 1): S11.

[14]Lucht RE, Delorme S, Hei J, et al.Classi fi cation of signaltime curves obtained by dynamic magnetic resonance mammography: statistical comparison of quantitative methods.Invest Radiol, 2005, 40(7): 442-447.

[15]American College of Radiology (ACR).ACR BI-RADS®- MRI.In: Breast imaging reporting and data system atlas(BI-RADS atlas).4th ed.Reston, VA: American College of Radiology, 2003.

[16]Edge S, Byrd D, Carducci M, et al.TNM Classi fi cation of Malignant Tumours.New York: Springer, 2009.

[17]Fischer U, Kopka L, Grabbe E.Breast carcinoma: effect of preoperative contrast-enhanced MR imaging on the therapeutic approach.Radiology, 1999, 213(3): 881-888.

[18]Baltzer PA, Yang F, Dietzel M, et al.Sensitivity and speci fi city of unilateral edema on T2w-TSE sequences in MR-Mammography considering 974 histologically veri fi ed lesions.Breast J, 2010, 16(3): 233-239.

[19]Dietzel M, Baltzer PA, Vag T, et al.The hook sign for differential diagnosis of malignant from benign lesions in magnetic resonance mammography: Experience in a study of 1084 histologically verified cases.Acta Radiol, 2010,51(2): 137-143.

[20]Dietzel M, Baltzer PAT, Vag T, et al.The Adjacent Vessel Sign on Breast MRI: New Data and a Subgroup Analysis for 1,084 Histologically Veri fi ed Cases.Korean J Radiol,2010, 11(2): 178-186.

[21]Elston CW, Ellis IO.Pathological prognostic factors in breast cancer.I.The value of histological grade in breast cancer: experience from a large study with long-term follow-up.Histopathology, 1991, 19(5): 403-410.

[22]Stone M.Cross-validation and multinomial prediction.Biometrika, 1974, 61(3): 509-515.

[23]Guyon I, Weston W, Barnhill S, et al.Gene Selection for Cancer Classification using Support Vector Machines.Machine Learning, 2002, 46(1-3): 389-422.

[24]Fischer DR, Wurdinger S, Boettcher J, et al.Further signs in the evaluation of magnetic resonance mammography: a retrospective study.Invest Radiol, 2005, 40(7): 430-435.

[25]Swets JA.Measuring the accuracy of diagnostic systems.Science, 1988, 240(4857): 1285-1293.

[26]McLaren CE, Chen WP, Nie K, et al.Prediction of malignant breast lesions from MRI features: a comparison of artificial neural network and logistic regression techniques.Acad Radiol, 2009, 16(7): 842-851.

[27]Bossuyt PM, Reitsma JB, Bruns DE, et al.Towards complete and accurate reporting of studies of diagnostic accuracy: The STARD Initiative.Radiology, 2003, 226(1):24-28.