I have a large codebase, and I'd like to refactor the package structure so that classes which interact heavily go in the same package.
It seems that it should be possible to create a tool that could look at the interactions between classes, and then group together those classes that interact heavily. These groupings might then suggest a good hierarchy for packages.
Does such a tool exist? (open source is preferred).
Just a comment (not really an answer since I am not aware of a specific tool but I can't comment yet)
Have you looked at formal concept analysis?
Generally it's a way of grouping together entities that share the same properties. For example, Siff and Reps (google for the paper) did automatic modularization by looking at the relation between functions and global variables. In my own research, I used the relations of class methods that access the same fields. Siff and Reps (google for paper) did automatic modularization.
FCA may not be the best approach here since you are trying to group classes against themselves, but I think that they can still be applied.
Something that can at least tell you if you're on the right track design-wise is JDepend. It encourages dependency on highly abstract packages (that presumably will change less than packages with code that is less abstract) and will warn you when your packages have circular dependencies. I find it to be a good reality check.
There are numerous ways to use it, including as an Eclipse plugin.
You could try Lattix, which uses the Dependency Structure Matrix to show you dependencies and hidden structure within your code at both class and package level. I've found it helpful for this kind of stuff in the past.
Structure101 is another product that can analyze the structure of your code and do dependency and what-if analysis.
http://www.headwaysoftware.com/products/structure101/index.php
Structure Analysis for Java is an Eclipse plugin that does some dependency analysis: