Subject: [Thuban-list] Patch: classifiers

From: "Daniel Calvelo Aros" <[email-masked]>
Date: Mon, 9 Feb 2004 01:58:40 -0500

Hi all.

The attached patch provides four classifiers to thuban's available three.

1. "Custom": that's a debugged version of my early "visual classifier". I
found it quite useful if used alongside the current classification window and
*after* another classifier has been used. It will start with the current
classification breaks and allow you to edit them. I used a very ugly hack to
do that. Could knowledgeable people give it a look and advise? Besides, that
will work only if you classify then *close* the classgen dialog and reopen it.

2. "Distribution discontinuities": this is based on a very nice idea and code
from J.P. Grimmeau of the ULB (thanks Moritz!). It will automatically find
discontinuities in the data distribution and select breaks accordingly. I'm
not sure on the proper way of giving credit, though.

3. "Distribution classes": this is based on a k-means classification of the
data, followed by a break-finding simple rule (nearest centroid). It also
fixes the number of classes although an initial value is required.

4. "Optimized distribution classes": an extra optimization pass after the
previous clustering. The optimization is a simulated annealing applied with a
target function based on Jenks & Caspall (1971). It's not really useful for
now, but all the hooks are there to use it as a "natural breaks" finder.

Since the last three algorithms are pretty sophisticated for the average SIG
user (AFAICT), I included a short description in the interface itself.

I tried to keep the algorithms generic, so they could be used elsewhere.

The zipped file includes a patch (for both classgen.py's mainly) and some new
files.

Please give it a try and I will do my best to improve the thing.

Some notes for the more guts-savvy people: these classifiers need to load the
entire dataset into memory to massage it properly; this can become pretty slow
on large datasets: are there plans to allow access to large datasets (I mean,
larger than available python memory)? I'm sure many things in the code can be
adapted to progressive calculations and other tricks.

BTW has anybody thought about interfacing thuban with Terralib? Lots of
interesting algorithms in there!

Daniel.

PS. I couldn't manage to reverse my previous patch for HSV ramps, so it's also
included here. Sorry for the inconvenience!

PPS. Still working on getting "natural breaks" to work...

-- Daniel Calvelo Aros
-- Dirección General de Información Agraria
-- Ministerio de Agricultura del Perú
-- (51-1)424-9001

---

From: "Moritz Lennert" <[email-masked]>
Date: Mon, 9 Feb 2004 11:09:44 +0100 (CET)

> The attached patch provides four classifiers to thuban's available three.
[...]

> not sure on the proper way of giving credit, though.

If it is possible to include the mention "Jean-Pierre Grimmeau, IGEAT-ULB,
grimmeau at ulb.ac.be" in the description text, that would be great.

> now, but all the hooks are there to use it as a "natural breaks" finder.

I haven't had time to look at your patch, but one of the weak points of
the use of the Jenks algorithm in ArcView is the absence of information
about the evolution of variance with the number of classes. So, do you
think it would be possible to include a little table, showing the
proportion of intra-group variance in the total variance for a series of
solutions (i.e. 2 classes to 12 classes) as a decision-aid on the best
number of classes ?

Again, thanks a lot for your work ! These classifiers plus (hopefully one
day) proportionate circles will make it much easier for me to convince my
colleagues to switch to Thuban.

Moritz

---

From: Frank Koormann <[email-masked]>
Date: Mon, 9 Feb 2004 20:23:22 +0100

Daniel,

thank you very much for your patches. I only had a glimpse at it so far,
but I like the HSV patch very much :)

[...]
> Please give it a try and I will do my best to improve the thing.

Regarding the classification updates I encountered some problems when 
loading a session with classifications and trying to reclassify -
however on fresh sessions it seems to work smart. Will sent more details 
tomorrow.

Best regards,

        Frank

-- 
Frank Koormann                             <[email-masked]>
 Professional Service around Free Software       (http://intevation.net/)
 FreeGIS Project                                 (http://freegis.org/)

---

From: "Moritz Lennert" <[email-masked]>
Date: Tue, 10 Feb 2004 12:54:13 +0100 (CET)

> however on fresh sessions it seems to work smart. Will sent more details

Will these patches be integrated into the CVS version ?

Moritz

---

From: Frank Koormann <[email-masked]>
Date: Tue, 10 Feb 2004 15:12:06 +0100

Moritz, all,

> Frank Koormann said:
[HSV patch and classifier patch by Daniel Calvelo Aros]
> Will these patches be integrated into the CVS version ?

yes, I think so. But the patches will be reviewed before uploading,
since we encountered some problems with the current CVS version.

Best regards,

        Frank

---

From: Bernhard Reiter <[email-masked]>
Date: Tue, 10 Feb 2004 15:17:09 +0100

> since we encountered some problems with the current CVS version.

(Reports from different people 
that they work well on current CVS
on several platforms might accellerate the Integration. (Hint Hint))

---

From: "Moritz Lennert" <[email-masked]>
Date: Tue, 10 Feb 2004 16:03:20 +0100 (CET)

> on several platforms might accellerate the Integration. (Hint Hint))

Ok I got the hint ;-)

I just (superficially) tested the patches and the classifiers are just
great. Just one remark concerning the discontinuities classifier: would it
be possible to let the user chose the number of classes she wants ? The
original code from J.P. Grimmeau gives the solutions for a number of
different classes. Ideally the use should be given a choice of the number
of classes based on a list of the potential breaks. At the current state,
I can obviously fusion two classes, but I do not have the info on which
break is the smallest...

Concerning the hsv patch, I don't seem to understand how it works. At
least when I chose the extreme colors and then click on "Generate" I get
exactly the same colors, whatever the chosen mode.

Moritz

---

From: "Daniel Calvelo Aros" <[email-masked]>
Date: Tue, 10 Feb 2004 16:35:40 -0500

---------- Forwarded Message -----------
From: "Daniel Calvelo" <[email-masked]>
To: Frank Koormann <[email-masked]>
Sent: Tue, 10 Feb 2004 15:40:10 -0500
Subject: Re: [Thuban-list] Patch: classifiers

On Tue, 10 Feb 2004 15:14:10 +0100, Frank Koormann wrote
> Daniel,
> 
> thanks again for your contributions. Just to clarify thinks, what was
> the basis for your implementation? The current CVS or another version.
> 
> Best regards,
> 
>         Frank

I diff'ed against CVS root from 20040122.

> * Frank Koormann <[email-masked]> [040210 11:27]:
> > Daniel,
> > 
>  Professional Service around Free Software       
> (http://intevation.net/) FreeGIS Project                             
>     (http://freegis.org/)

-- Daniel Calvelo Aros
------- End of Forwarded Message -------

-- Daniel Calvelo Aros

---

From: "Daniel Calvelo Aros" <[email-masked]>
Date: Tue, 10 Feb 2004 16:36:10 -0500

On Tue, 10 Feb 2004 16:03:20 +0100 (CET), Moritz Lennert wrote
[...]
> I just (superficially) tested the patches and the classifiers are 
> just great. Just one remark concerning the discontinuities 
> classifier: would it be possible to let the user chose the number of 
> classes she wants ? The original code from J.P. Grimmeau gives the 
> solutions for a number of different classes. Ideally the use should 
> be given a choice of the number of classes based on a list of the 
> potential breaks. At the current state, I can obviously fusion two 
> classes, but I do not have the info on which break is the smallest...

Ok, I'll work on that. But the original code DEFINES the number of breaks.
It's part of its strength. Giving you an indicator of the overall quality for
the visual classifier would be helpful, I reckon. Let me think around it a bit.

> least when I chose the extreme colors and then click on "Generate" I 
> get exactly the same colors, whatever the chosen mode.
> 
> Moritz

Both methods give quite similar results for e.g. black to blue, white to red,
but very different for, e.g. red to green. Try that one. In principle, ramps
that vary mainly in saturation or value should be similar. If hue changes are
involved, the HSV classifier moves along the spectrum, in the "closest
direction" (e.g. red to blue goes through purple but red to green goes through
yellow, not purple and blue).

Daniel.

-- Daniel Calvelo Aros

---

From: Bernhard Reiter <[email-masked]>
Date: Thu, 12 Feb 2004 12:58:45 +0100

> great. 

Thanks. 
When doing such useful reports, can you give us more details
on the version of the components and your system?
Then we can say: Thuban (with such and such capabilities)
is known to run on X Y..

---

From: "Moritz Lennert" <[email-masked]>
Date: Thu, 12 Feb 2004 14:08:08 +0100 (CET)

(bringing this back to the list, as I think others might be interested)

Daniel Calvelo Aros said:
> On Wed, 11 Feb 2004 18:49:20 +0100 (CET), Moritz Lennert wrote
>> No, the program defines the maximum number of classes that make any sense
>> according to the stopping criterion defined in the code, but it does
not define the best number of classes.
>
> You mean it's not "best" according to cartographic or other criteria
different
> from the implicit "best" of the stopping criterion?
>

No, what I mean is that the stopping criterion does not imply "best"
number of solution, but measures the statistical significance of creating
another class break. The algorithm stops when the creation of another
break would not give more information than not creating one.

The definition of "best" number of solution is independant of that.
Especially, because cartographic issues enter into play as well, so what
is "best" (as always) depends on what one aims for.

>> I actually don't know how it
>> would do that. I've attached a results file generated with the
>> original code and as you can see it gives a number of solutions from
which I can chose. It would be nice to have such a table in thuban.
>
> I see. From what I understood in the code, those are printouts of each
step of
> the algorithm as it partitions further the dataset. The stopping
criterion
> is
> something like "difference between original class and best partition is
statistically insignificant", for a hard-wired significance threshold of
95%.

Exactly, it is a question of statistical significance of an additional
partition, not of best number of partitions. So when in your thuban verion
it says "Got X breakpoints in the distribution of Y", it should maybe say
something like: "Got X statistically significant (95%) breakpoints ...". A
really sophisticated version of this could even let the user decide the
level of desired significance...but I think this would be overkill :-)

> Now, what you suggest would be (correct me, please) to use the results from
> the partitioning steps as inputs into a quality measure of each
> classification
> (in the sense of your former definition of "best"), and from there let
either
> the user or some automated thing define the number of classes.
>
> I still don't have a Jenks-Caspall-like quality measure, so for now only
the
> user is available as a criterion of classification quality.

I don't really believe in the existence of _one_ quality measure. I think
that this depends on too many factors, including "purely"
graphical/cartographic ones. So I would agree with you saying that "only
the
user is available as a criterion of classification quality.", but I would
say that this is always the case, not just for now...

>
> In this order of ideas, the easiest way would be to fix the maximum
number
> of
> classes attainable by the algorithm, unless "automatic" is specified. In
both
> cases, if the hardwired stopping criterion is fulfilled, stop and give a
warning if Nclasses<specified. Would that be ok?

That sounds good, but I don't think the user should have to determine a
number of classes a priori. The algorithm should be seen as decision-aid,
not more and so, it should give the user all the necessary information to
make a good decision. So, giving her at least the potential class limits
and the number of observations per class, should help her in deciding on
the number of classes (the original code also provides a measure of
density, dividing the proportion of observations in a class by the
classes' proportion of the total amplitude). Sometimes, she might want to
subdivide a class, just because it contains too many observations...

I know this makes the whole thing more complicated to program, but I am
very suspicious of "automatic" cartography and in my eyes this is one of
the weak points of ArcView.

Moritz

---

From: "Moritz Lennert" <[email-masked]>
Date: Thu, 12 Feb 2004 14:13:50 +0100 (CET)

> Then we can say: Thuban (with such and such capabilities)

Yes, sorry.

I'm running Thuban CVS on Debian testing/unstable, using python2.3-dev.

Any other information you think would be useful ?

Moritz

---

From: Bernhard Reiter <[email-masked]>
Date: Thu, 12 Feb 2004 14:47:22 +0100

> > Then we can say: Thuban (with such and such capabilities)
No problem at all.

> Any other information you think would be useful ?

Probably the platform (i386, ppc?)
and the CVS checkout date and what other modules you have 
activated and build in.

We probably have to make a list for people who want to support
us with test reports of what to report.
Or a script that makes this easier.

---

From: "Moritz Lennert" <[email-masked]>
Date: Thu, 12 Feb 2004 14:56:37 +0100 (CET)

> and the CVS checkout date and what other modules you have

i386 (i686)
CVS of 11/2/2004

About info:
Thuban Release Version 1.0.0

Currently using:
	wxPython 2.4.2.4
	Python 2.3.3
	PySQLite 0.4.3
	SQLite 2.8.9
	GDAL 1.2+cvs
	psycopg 1.1.10

Compiled for:
	GTK 1.2.10
	proj 4.4.7

> Or a script that makes this easier.

Couldn't the above About info be extended easily ?

Moritz

---

From: Bernhard Reiter <[email-masked]>
Date: Thu, 12 Feb 2004 15:25:29 +0100

> Couldn't the above About info be extended easily ?

AFAIK There is no precise way to find out on which system you are.

---

From: "Moritz Lennert" <[email-masked]>
Date: Thu, 12 Feb 2004 17:04:11 +0100 (CET)

> included here. Sorry for the inconvenience!

I am having some trouble with the patching of the two...

The hsv.patch contains code changing the GetRamp function:

*** 979,985 ****
          topSizer.SetSizeHints(self)

      def GetRamp(self):
!         return CustomRamp(self.startPropCtrl.GetProperties(),
                            self.endPropCtrl.GetProperties())

      def _OnCopyStart(self, event):
--- 985,995 ----
          topSizer.SetSizeHints(self)

      def GetRamp(self):
!       if self.modeChoice.GetStringSelection()==_("HSV Ramp"):
!           rampType = HSVCustomRamp
!       else:
!           rampType = CustomRamp
!         return rampType(self.startPropCtrl.GetProperties(),
                            self.endPropCtrl.GetProperties())

However, the hsv+class.patch doesn't seem to do the same change:

          topSizer.SetSizeHints(self)

      def GetRamp(self):
!         return CustomRamp(self.startPropCtrl.GetProperties(),
                            self.endPropCtrl.GetProperties())

      def _OnCopyStart(self, event):
--- 1268,1274 ----
          topSizer.SetSizeHints(self)

      def GetRamp(self):
!         return HSVCustomRamp(self.startPropCtrl.GetProperties(),
                            self.endPropCtrl.GetProperties())

      def _OnCopyStart(self, event):

When I try to use both patches, I get

$ patch -p0 < hsv+class.patch
patching file thuban/Thuban/Model/classgen.py
patching file thuban/Thuban/Model/color.py

$ patch -p0 < hsv.patch
patching file thuban/Thuban/Model/classgen.py
Reversed (or previously applied) patch detected!  Assume -R? [n]

(and the same when I try to apply the patches in reverse order)

Could someone tell me how to solve this ?

Moritz
patching file thuban/Thuban/UI/classgen.py

---

From: "Daniel Calvelo Aros" <[email-masked]>
Date: Thu, 12 Feb 2004 14:59:08 -0500

On Thu, 12 Feb 2004 15:25:29 +0100, Bernhard Reiter wrote
> AFAIK There is no precise way to find out on which system you are.

sys.version, sys.platform inside the About box might be informative. I'm not
sure it's enough. 

We could maybe add somewhere a thuban_version = "$Id$" or alike to have also a
CVS version number (which would be the appropriate file, then?).

Along those lines, I think we could hook the platform information needed for
compilation somewhere... I'm not familiar with distutils though.

Daniel.

-- Daniel Calvelo Aros

---

From: Bernhard Herzog <[email-masked]>
Date: Thu, 12 Feb 2004 21:14:17 +0100

> The attached patch provides four classifiers to thuban's available three.

Thanks.  It would be nice to have that functionality in Thuban.  Before
we check it in, though, I'd like to see some improvements in the code.

First some stylistic things.  To make the code more maintainable in the
context of Thuban and to make it easier for us to review the patch,
please try to follow the style and practices used in the code already
there.  These might also serve as the beginning of a "patch submission
guideline".

 - All lines should be at most 79 characters long

 - Put spaces around binary operators and after commas, colons and
   semicolons (but not before them).

 - Every class, function and method should have a doc string.  The doc
   string should start with a brief one-line description of the class or
   method.  If more explanations are needed add an empty line and one or
   more paragraphs.
   
   The isn't adhered to in the code as well as it should.  New code
   should follow it, though.

 - New functionality and bug fixes should have corresponding tests in
   the test suite.

 - Changes should be documented in the ChangeLog file

 - Do not use "from module import *"

   This form of the import statement leads to code that is hard to
   maintain for several reasons:

    - If the module's contents change the names bound in the code that
      executes the import statement change as well and might
      accidentally override python builtins or names already bound in
      the module

    - It's hard to find out which of the objects in the imported module
      are actually used by the importing code.  It's especially hard to
      find out whether the import is still needed if the code has
      changed.

   "from wxPython.wx import *" is tolerable, but I try to avoid that too.

 - Try to submit small patches.  Smaller patches are easier to
   understand, take less time to review and are therefore much more
   likely to be applied quickly.  That you submitted the HSV support as
   a separate patch first was a good example of this.

More specific comments on the code

 - Thuban/Model/color.py: rgb2hsv and hsv2rgb duplicate functionality
   from Python's colorsys module

 - Thuban/Model/classgen.py: green_to_red_ramp defines a different ramp
   now.  This is an incompatible interface change.  If we really do need
   a predefined ramp for this it should be called something else,
   perhaps hsv_green_to_red_ramp.  

   Ideally all these predefined ramps don't belong in Thuban.Model
   anyway.  Currently they would be better in Thuban.UI.  But that would
   have to wait until create the branch in CVS as that kind of change
   doesn't belong in a stable branch.

 - Thuban/Model/classgen.py: Line 18f: The new import statements are not
   necessary.  sqrt and random are never used.  I guess they were
   required by an earlier version of your code

 - Thuban/Model/classgen.py: Renaming the __SetProperty method is OK.  I
   suggest to rename it to interpolate_colors and have it return the new
   color instead of passing the setf function in.  E.g.

   def interpolate_colors(self, color1, color2, weigth):
       """Return a weighted average of the colors color1 and color2

       The returned color is effectively 

            (1 - weight) * color1 + weight * color2

       weight should be a float in the range 0.0 to 1.0
       """

   Come to think of it, it's probably be even better to put that method
   as a function into Thuban/Model/color.py and add an optional
   parameter to CustomRamp defaulting to that new function.  The
   _SetProperty implementation in HSVCustomRamp could be another
   function in colors.py, perhaps interpolate_colors_hsv (and the other
   should get an _rgb suffix, then).  There'd be no need for the new classes
   HSVCustomRamp and HSVRamp, even.

 - Thuban/UI/sliders.py: Line 11: Yes, it should use a better way to
   find the bitmap file.  That's what the functions in
   Thuban/UI/resource.py are for.

 - Thuban/UI/classgen.py: The sum function is new as a built-in in
   Python 2.3.  Thuban 1.0.x should remain compatible with Python 2.2.
   Thuban 1.1.x will probably also remain 2.2 compatible.

I haven't looked at all of the code yet, but this should be enough for
now :)

   Bernhard

-- 
Intevation GmbH                                 http://intevation.de/
Skencil                                http://sketch.sourceforge.net/
Thuban                                  http://thuban.intevation.org/

---

From: Jan-Oliver Wagner <[email-masked]>
Date: Thu, 12 Feb 2004 21:50:34 +0100

> there.  These might also serve as the beginning of a "patch submission

I've put your guideline into a web page:
http://thuban.intevation.org/patch-submission.html

It is not yet linked, but I think it already useful.
Should we add it to the navigation?
I vote for putting it right before "CVS".

Best

	Jan

-- 
Jan-Oliver Wagner               http://intevation.de/~jan/

Intevation GmbH	              	     http://intevation.de/
FreeGIS	                               http://freegis.org/

---

From: "Daniel Calvelo Aros" <[email-masked]>
Date: Fri, 13 Feb 2004 15:00:03 -0500

On Thu, 12 Feb 2004 21:50:34 +0100, Jan-Oliver Wagner wrote
> http://thuban.intevation.org/patch-submission.html

Great! I still have some style points to be enlightened about:

- Use '\' systematically for line breaks?

- Blank lines within code blocks to enhance readability, for code sections,
algorithm phases, etc.?

- Use c_style_caps_as_in_gtk for helper functions but SmalltalkLikeMixedCaps
for classes and class members?

- TODO, FIXME or XXX marks for pending stuff?

- Any guidelines on code comments? One or two ##? doxygen-like openings?

- Adhere to StructuredTextNG in docstrings?

Jan, in the on-line version, there is a weird phrase: " The isn't adhered to
in the code as well as it should. ", and a reference to my HSV patch which
shouldn't be there, IMO. The point Bernhard made about 2.2 compatibility is
VERY important. Please include it.

Do you think this should be in CVS? I'd vote yes, with a reference to it in
the README. HTML? STNG?

> I vote for putting it right before "CVS".

I'd rather have it between CVS via ssh and Mailing List. Is it time already to
section the menu between users, developers, general info?

Daniel.

-- Daniel Calvelo Aros

---

From: "Daniel Calvelo" <[email-masked]>
Date: Fri, 13 Feb 2004 14:54:48 -0500

On Thu, 12 Feb 2004 17:04:11 +0100 (CET), Moritz Lennert wrote
[...]

Rats. I really messed up the patches. Try the attached patch, which only puts
back the HSV-related code not updated by the hsv+class patch. Recapitulate:
apply hsv+class, *then* the attached. You get classifications AND hsv ramps.
Apply hsv.patch and you get only hsv ramps.

Apologies to everybody.

Daniel.

-- Daniel Calvelo Aros

---

From: "Moritz Lennert" <[email-masked]>
Date: Mon, 16 Feb 2004 16:57:02 +0100 (CET)

Daniel Calvelo said:
>> > PS. I couldn't manage to reverse my previous patch for HSV ramps, so
>> it's
>> > also

Ok, perfect, now I see the difference between hsv and rgb.

Thank you Daniel !

Moritz

---

From: Bernhard Herzog <[email-masked]>
Date: Mon, 16 Feb 2004 19:38:10 +0100

> - Use '\' systematically for line breaks?

Only where necessary.  In most cases where one needs to split a logical
line over several physical lines the implicit rules for line joining
make it unnecessary.  In the other cases it's usually easy to introduce
and extra pair of parentheses.

> - Blank lines within code blocks to enhance readability, for code sections,

Yes.

> for classes and class members?

More or less.  I prefer lower cases names for non-public methods,
though.  So CamelCase with an upper case first letter for classes,
public methods and package names.  lowercase_with_underscores for
functions, variables, interfaces for derived classes and module names.
_leading_underscore_and_lowercase for more private things.
__double_leading_undescore only where there's a somewhat higher chance
of accidental name clashes in derived classes.  ALL_UPPERCASE for
constants.

> - TODO, FIXME or XXX marks for pending stuff?

Yes.

> - Any guidelines on code comments? One or two ##?

One

> doxygen-like openings?

The kind of information that would be extracted by a tool like doxygen
is in the doc-strings.

> - Adhere to StructuredTextNG in docstrings?

I sometimes use formatting taken from an earlier StructuredText version,
but usually I don't bother with it.

> shouldn't be there, IMO.

Removed.

> The point Bernhard made about 2.2 compatibility is

Added.

> Do you think this should be in CVS? I'd vote yes,

+1.  It should be in a directory under Doc.

> with a reference to it in
> the README. HTML? STNG?

Simple plain text.  If we need more than that we could adopt a format
like the one used by the Python PEPs.  We don't need to be as formal at
this point, of course.

These patch submission guide lines are actually more coding guide lines.
There's only one paragraph that's specific to patches.

   Bernhard