Re: Things that are hard to do in SQL (datamining?)

In article <3992sk$d0i@infmx.informix.com> proberts@informix.com (Paul Roberts) writes: >From: proberts@informix.com (Paul Roberts) >Subject: Re: Things that are hard to do in SQL (datamining?) >Date: 2 Nov 1994 22:12:36 GMT >In article <783607681snz@sambusys.demon.co.uk> psb@sambusys.demon.co.uk writes: >> >>I suppose you are interested in a GENERAL solution to the problem. >>For example, a tool that you would let loose on a database that >>didn't know anything about the data dictionary but would tell you >>that only one of 5000 male employees has a maiden name. [Useful.] >>Or that only three customers have zip codes equal to their credit >>balance [Less useful.] >It would be neat, wouldn't it? I understand that marketers are striving >to build up huge databases on all our buying preferences (and if you pay >by credit/ATM card and your purchases are laser-scanned, it wouldn't be >too difficult). They'd love to be able to spot patterns, I'm sure. They do already, cat owners prefer prego. (people that buy cat food also tend to buy prego) What does that tell you???? >Thanks to everyone who replied. I've been thinking about the problem a >bit more, I'm going to take the liberty of rambling on a bit more about >it. Those who think this all too vague or silly, please hit 'n' now! >It strikes me that in "real life" problems, we don't have the table of >"departments". We just have the list of "who attended which classes". >From this, we might be able to infer that there is in fact a hidden >entity "department". For instance, we see that 100 employees have taken >classes A, D, F and 150 other employees have taken classes D, G, H. >We might conclude from this alone that there is something going on >here, and that there are two "employees types". >It strikes me that drawing this inference is the same process as >normalisation. We have a single large table, and we compute two smaller >tables such that joining those two tables yields the original large >table. In the example given we start with a table relating employees >to classes-taken, and it has 750 records. We 'factor' this into a >table that relates each employee to a single 'employee type' (250 rows) >and another table that relates 'employee type' to 'classes-taken' >(6 rows). >This can be done fairly simply once we allow ourselves to calculate >'signatures' for 'set of classes taken'. That is, go from three rows >that look like this: >emp # class >----- ----- >1 D >1 A >1 F >to one row that looks like this >emp # class-sig >----- --------- >1 'ADF' >Then it is suddenly easy to answer questions like "Who took the same set >of classes as Joe?", "Did Bill and Joe take the same set of classes?", >"Which is the most commonly-taken combination of classes?". The signatures >might be just the concatenation of sorted class codes, or sort of bit-vector, >or an integer -- > \\ i > / 2 > -- where i is an integer code for each class > 1 4 >(if you took only classes #1 and #4 then you get a signature of 2 + 2 = 17) >All the matters is that each unique combination of classes yields a unique >signature. Something inside me object "But calculating these signatures is >NOT RELATIONAL!" but expect this is just superstition. >It seems remarkable difficult to answer the above questions in "pure SQL", >though (i.e. without calculating something akin to these signatures). >Now the other, harder, problem is "Do the same thing, but assume there is >`noise' - just because there are a few execptions isn't to prevent one >from inferring the general rule". Obviously we have to rather arbitrarily >pick some statistical notion of how many expections can be tolerated. In >fact what this really amounts to is this - every employee has taken a >certain set of classes, and thus can be associated with a point in 'class >space'. 'Class space' is the set of all signatures, with some sort of >metric defined on it. Isn't 'Hamming distance' the metric which is >essentially 'count up the numbers of elements at which the bit vectors >differ'? - this is the only metric that occurs to me. Then the problem >becomes: >"Here is a large number of points in 'class space' - identify all the clusters." > I imagine there are statistical methods to do things like 'identify clusters', >certainly in nice metric spaces like R, RxR, and RxRxR (points long a line, >points in a plane, points in 3D space). I imagine - though with somewhat >less conviction - that there are statistical methods that could be applied >to my 'class space'. > Having decided that statisticans probably have ways to analyse these >things, I think I might be able to let the problem go. > End of rambling, back to work..... >Paul