Patient distance metrics There are umpteen million research papers regarding relationships between various patient attributes (e.g. how does gene x affect condition y?). What I am interested in though is a distance metric between patients in toto. Sort of like if I were constructing a dating site, I'd want to know how similar two people are. (Except in this case "similarity" means health similarity rather than personality similarity or whatever dating sites look at.)
Could anyone point me to research regarding this problem? So far the only paper I've found that really attempts to tackle this is:
Melton, G. B., S. Parsons, F. P. Morrison, A. S. Rothschild, M. Markatou, and G. Hripcsak. “Inter-patient distance metrics using SNOMED CT defining relationships.” Journal of Biomedical Informatics 39, no. 6 (2006): 697-705.
EDIT:
To clarify my question (because it's slightly different than many on this site): I am not asking "I have some data set, how can I analyze it?" I am asking "if I gave a doctor a data set, how would they analyze it?" I don't particularly care if there is some relation between attribute X and Y. What I care about is if a doctor thinks there is a relation between X and Y. 
I.e. my question is: I give a doctor two patient charts. How can I predict what they think the similarity is? Do they look at certain attributes? Is it even possible to make a statement like "they are .9 similar?" Is a better statement "they are .9 similar on dimension X and .8 similar on dimension Y?" How are chronic conditions different than temporary ones? etc. etc.
This is maybe on the fringes of what this site is intended for, but I'm hoping someone has dealt with this and can point me in a good direction, even though it's not a question about a given statistical technique per se.
EDIT 2:
Thank you all for your suggestions. However, I was really looking for people who have done this work before - I don't have access to a lot of data, so I was hoping to find someone who did have these data and utilize their conclusions.
 A: You asked a difficult question, but I'm a little bit surprised that the various clues that were suggested to you received so little attention. I upvoted all of them because I think they basically are useful responses, though in their actual form they call for further bibliographic work.
Disclaimer: I never had to deal with such a problem, but I regularly have to expose statistical results that may differ from physician's a priori beliefs and I learn a lot from unraveling their lines of reasoning. Also, I have some background in teaching human decision/knowledge from the perspective of Artificial Intelligence and Cognitive Science, and I think what you asked is not so far from how experts actually decide that two objects are similar or not, based on their attributes and a common understanding of their relationships.
From your question, I noticed two interesting assertions. The first one related to how an expert assess the similarity or difference between two set of measurements:

I don't particularly care if there is
  some relation between attribute X and
  Y. What I care about is if a doctor
  thinks there is a relation between X
  and Y.

The second one, 

How can I predict what they think the
  similarity is? Do they look at certain
  attributes?

looks like it is somewhat subsumed by the former, but it seems more closely related to what are the most salient attributes that allow to draw a clear separation between the objects of interest.
To the first question, I would answer: Well, if there is no characteristic or objective relationship between any two subjects, what would be the rationale for making up an hypothetical one? Rather, I think the question should be: If I only have limited resources (knowledge, time, data) to take a decision, how do I optimize my choice? To the second question, my answer is: Although it seems to partly contradicts your former assertion (if there is no relationship at all, it implies that the available attributes are not discriminative or useless), I think that most of the time this is a combination of attributes that makes sense, and not only how a given individual scores on a single attribute.
Let me dwell on these two points.
Human beings have a limited or bounded rationality, and can take a decision (often the right one) without examining all possible solutions. There is also a close connection with abductive reasoning.
It is well known that there is some variability between individual judgments, and even between judgments from the same expert at two occasions. This is what we are interested in in reliability studies. But you want to know how these experts elaborate their judgments. There is a huge amount of papers about that in cognitive psychology, especially on the fact that relative judgments are easier and more reliable than absolute ones. Doctors' decisions are interesting in this respect because they are able to take a "good" decision with a limited amount of information, but at the same time they benefit from an ever growing internal knowledge base from which they can draw expected relationships (extrapolation). In other words, they have a built-in inference (assumed to be hypothetico-deductive) machinery and accumulate positive evidence or counterfactuals from there experience or practice. Reproducing this inferential ability and the use of declarative knowledge was the aim of several expert or production rule systems in the 70s, the most famous one being MYCIN, and more generally of Artifical Intelligence earlier in 1946 (Can we reproduce on an artificial system the intelligent behavior observed in man?). Automatic treatment of speech, problem solving, visual shape recognition are still active projects nowadays and they all have to do with identifying salient features and their relationships to make an appropriate decision (i.e., how far should two patterns be to be judged as the emanation of two distinct generating processes?).
In sum, our doctors are able to draw an optimal inference from a limited amount of data, compensating from noise that arises simply as a byproduct of individual variability (at the level of the patients). Thus, there is a clear connection with statistics and probability theory, and the question is what conscious or subconscious methodology help doctors forming their judgments. Semantic networks (SN), belief networks, and decision trees are all relevant to the question you asked. The paper you cited is about using an ontology as a basis of formal judgments, but it is no more than an extension of SNs, and many projects were initiated in this direction (I can think of the Gene Ontology for genomic studies, but many others exist in different domains). 
Now, look at the following hierarchical classification of diagnostic categories (it is roughly taken from Dunn 1989, p. 25):

And now take a look at the ICD classification; I think it is not too far from this schematic classification. Mental disorders are organized into distinct categories, some of them being closer one to each other. What render them similar is the closeness of their expression (phenotype) in any patient, and the fact that they share some similarities in their somatic/psychological etiology. Assessing whether two doctors would make the same diagnostic is a typical example of an inter-rater agreement study, where two psychiatrists are asked to place each of several patients in mutually exclusive categories. The hierarchical structure should be reflected in the disagreement between each doctor, that is they may not agree on the finer distinction between diagnostic classes (the leafs) but if they were to disagree between insomnia and schizophrenia, well it would be little bit disconcerting... How these two doctors decide on which class a given patient belongs to is no more than a clustering problem: How likely are two individuals, given a set of observed values on different attributes, to be similar enough so that I decide they share the same class membership? 
Now, some attributes are more influential than others, and this is exactly what is reflected in the weight attributed to a given attribute in Latent Class Analysis (which can be thought of as a probabilistic extension of clustering methods like k-means), or the variable importance in Random Forests. We need to put things into boxes, because at first sight it's simpler. The problem is that often things overlap to some extent, so we need to consider different levels of categorization.
In fact, cluster analysis is at the heart of the actual DSM categories, and many papers actually turn around assigning one patient to a specific syndromic category, based on the profile of his response to a battery of neuropsychological assessments. This merely looks like a subtyping approach; each time, we seek to refine a preliminary well-established diagnostic category, by adding exception rules or an additional relevant symptom or impairment. 
A related topic is decision trees which are by far the most well understood statistical techniques by physicians. Most of the time, they described a nested series of boolean assertions (Do you have a sore throat? If yes, do you have a temperature? etc.; but look at an example of public influenza diagnostic tree) according to which we can form a decision regarding patients proximity (i.e. how similar patients are wrt. attributes considered for building the tree -- the closer they are the more likely they are to end up in the same leaf). Association rules and the  C4.5 algorithm rely quite on the same idea. On a related topic, there's the patient rule-induction method (PRIM). Now clearly, we must make a distinction between all those methods, that make an efficient use of a large body of data and incorporate bagging or boosting to compensate for model fragility or overfitting issues, and doctors who cannot process huge amount of data in an automatic and algorithmic manner. But, for small to moderate amount of descriptors, I think they perform quite good after all.
The yes-or-no approach is not the panacea, though. In behavioral genetics and psychiatry, it is commonly argued that the classification approach is probably not the best way to go, and that common diseases (learning disorders, depression, personality disorders, etc.) reflect a continuum rather than classes of opposite valence. Nobody's perfect!
In conclusion, I think doctors actually hold a kind of internalized inference engine that allows them to assign patients into distinctive classes that are characterized by a weighted combination of available evidences; in other words, they are able to organize their knowledge in an efficient manner, and these internal representations and the relationships they share may be augmented throughout experience. Case-based reasoning probably comes into play at some point too. All of this may be subjected to (a) revision with newly available data (we are not simply acting as definitive binary classifiers, and are able to incorporate new data in our decision making), and (b) subjective biases arising from past experience or wrong self-made association rules. However, they are prone to errors, as every decision systems...
All statistical techniques reflecting these steps -- decisions trees, bagging/boosting, cluster analysis, latent cluster analysis -- seems relevant to your questions, although they may be hard to instantiate in a single decision rule. 
Here are a couple of references that might be helpful, as a first start to how doctors make their decisions:


*

*A clinical decision support system for clinicians for determining appropriate radiologic imaging examination

*Grzymala-Busse, JW. Selected Algorithms of Machine Learning from Examples. Fundamenta Informaticae 18 (1993), 193–207

*Santiago Medina, L, Kuntz, KM, and Pomeroy, S. Children With Headache Suspected of Having a Brain Tumor: A Cost-Effectiveness Analysis of Diagnostic Strategies. Pediatrics 108 (2001), 255-263

*Building Better Algorithms for the Diagnosis of Nontraumatic Headache

*Jenkins, J, Shields, M, Patterson, C, and Kee, F. Decision making in asthma exacerbation: a clinical judgement analysis. Arch Dis Child 92 (2007), 672–677

*Croskerry, P. Achieving quality in clinical decision making: cognitive strategies and detection of bias. Acad Emerg Med 9(11) (2002), 1184-204.

*Cahan, A, Gilon, D, Manor, O, and Paltiel. Probabilistic reasoning and clinical decision-making: do doctors overestimate diagnostic probabilities? QJM 96(10) (2003), 763-769

*Wegwarth, O, Gaissmaier, W, and Gigerenzer, G. Smart strategies for doctors and doctors-in-training: heuristics in medicine. Medical Education 43 (2009), 721–728

A: I might be misunderstanding your goals here, but to me it sounds like a multi-dimensional scaling (MDS) problem.  I've never used MDS myself, but my sense is that it should allow you to derive a global measure of similarity as well as dimensional measures of similarity. My memory is that it is able to handle both continuous items (e.g. pulse rate) and nominal items (e.g. Gender) which seems like it would be an important consideration for what you are trying to do.
A: The whole field of Cluster Analysis is relevant to your concept of multi-variable statistical distance.  The linked book on the subject is very short and pretty good.   
A: The simple idea is to make PCA and base distance of few first components (yet I don't like this technique because of assumptions it makes).
The complex idea is to use machine learning; the resulting distances will expose the classifier structure, so will be about as good as the classification accuracy. The simplest approach here is just random forest object distance (Breiman's example), but you can also use the kernel justified by SVM, see for instance Winters-Hilt & Merat 2007.
A: There is a subfield called Distance Metric Learning. One such method is Information Theoretic Metric Learning (ITML).
