text:
The Moon is Earth's only permanent natural satellite. It is the fifth-largest natural satellite in the Solar System, and the largest among planetary satellites relative to the size of the planet that it orbits (its primary). It is the second-densest satellite among those whose densities are known (after Jupiter's satellite Io).

The Moon is thought to have formed approximately 4.5 billion years ago, not long after Earth. There are several hypotheses for its origin; the most widely accepted explanation is that the Moon formed from the debris left over after a giant impact between Earth and a Mars-sized body called Theia.

The Moon is in synchronous rotation with Earth, always showing the same face, with its near side marked by dark volcanic maria that fill the spaces between the bright ancient crustal highlands and the prominent impact craters. It is the second-brightest regularly visible celestial object in Earth's sky after the Sun, as measured by illuminance on Earth's surface. Its surface is actually dark (although it can appear a very bright white) with a reflectance just slightly higher than that of worn asphalt. Its prominence in the sky and its regular cycle of phases have made the Moon an important cultural influence since ancient times on language, calendars, art, and mythology.

The Moon's gravitational influence produces the ocean tides, body tides, and the slight lengthening of the day. The Moon's current orbital distance is about thirty times the diameter of Earth, with its apparent size in the sky almost the same as that of the Sun, resulting in the Moon covering the Sun nearly precisely in total solar eclipse. This matching of apparent visual size will not continue in the far future. The Moon's linear distance from Earth is currently increasing at a rate of 3.82 ± 0.07 centimetres (1.504 ± 0.028 in) per year, but this rate is not constant.

The Soviet Union's Luna programme was the first to reach the Moon with unmanned spacecraft in 1959; the United States' NASA Apollo program achieved the only manned missions to date, beginning with the first manned lunar orbiting mission by Apollo 8 in 1968, and six manned lunar landings between 1969 and 1972, with the first being Apollo 11. These missions returned over 380 kg (840 lb) of lunar rocks, which have been used to develop a geological understanding of the Moon's origin, the formation of its internal structure, and its subsequent history. After the Apollo 17 mission in 1972, the Moon has been visited only by unmanned spacecraft.

## Name and etymology

The usual English proper name for Earth's natural satellite is "the Moon".[17][18] The noun moon is derived from moone (around 1380), which developed from mone (1135), which is derived from Old English mōna (dating from before 725), which ultimately stems from Proto-Germanic *mǣnōn, like all Germanic language cognates. Occasionally, the name "Luna" is used. In literature, especially science fiction, "Luna" is used to distinguish it from other moons, while in poetry, the name has been used to denote personification of our moon.

The principal modern English adjective pertaining to the Moon is lunar, derived from the Latin Luna. A less common adjective is selenic, derived from the Ancient Greek Selene (Σελήνη), from which is derived the prefix "seleno-" (as in selenography).[19][20] Both the Greek Selene and the Roman goddess Diana were alternatively called Cynthia.[21] The names Luna, Cynthia, and Selene are reflected in terminology for lunar orbits in words such as apolune, pericynthion, and selenocentric. The name Diana is connected to dies meaning 'day'.

## Formation

Several mechanisms have been proposed for the Moon's formation 4.527 ± 0.010 billion years ago, some 30–50 million years after the origin of the Solar System.[24] Recent research presented by Rick Carlson indicates a slightly lower age of between 4.40 and 4.45 billion years.[25] [26] These mechanisms included the fission of the Moon from Earth's crust through centrifugal force[28] (which would require too great an initial spin of Earth), the gravitational capture of a pre-formed Moon[30] (which would require an unfeasibly extended atmosphere of Earth to dissipate the energy of the passing Moon), and the co-formation of Earth and the Moon together in the primordial accretion disk (which does not explain the depletion of metals in the Moon). These hypotheses also cannot account for the high angular momentum of the Earth–Moon system.[32]

The prevailing hypothesis today is that the Earth–Moon system formed as a result of a giant impact, where a Mars-sized body (named Theia) collided with the newly formed proto-Earth, blasting material into orbit around it that accreted to form the Moon.[33][34]

This hypothesis perhaps best explains the evidence, although not perfectly. Eighteen months prior to an October 1984 conference on lunar origins, Bill Hartmann, Roger Phillips, and Jeff Taylor challenged fellow lunar scientists: "You have eighteen months. Go back to your Apollo data, go back to your computer, do whatever you have to, but make up your mind. Don't come to our conference unless you have something to say about the Moon's birth." At the 1984 conference at Kona, Hawaii, the giant impact hypothesis emerged as the most popular.

Before the conference, there were partisans of the three "traditional" theories, plus a few people who were starting to take the giant impact seriously, and there was a huge apathetic middle who didn’t think the debate would ever be resolved. Afterward there were essentially only two groups: the giant impact camp and the agnostics.[35]

Giant impacts are thought to have been common in the early Solar System. Computer simulations modelling a giant impact are consistent with measurements of the angular momentum of the Earth–Moon system and the small size of the lunar core. These simulations also show that most of the Moon came from the impactor, not from the proto-Earth.[38] However, more-recent tests suggest more of the Moon coalesced from Earth and not the impactor.[39][40][43][44] Meteorites show that other inner Solar System bodies such as Mars and Vesta have very different oxygen and tungsten isotopic compositions to Earth, whereas Earth and the Moon have nearly identical isotopic compositions. Post-impact mixing of the vaporized material between the forming Earth and Moon could have equalized their isotopic compositions,[47] although this is debated.[48]

The large amount of energy released in the giant impact event and the subsequent re-accretion of material in Earth orbit would have melted the outer shell of Earth, forming a magma ocean.[50][52] The newly formed Moon would also have had its own lunar magma ocean; estimates for its depth range from about 500 km (300 miles) to the entire radius of the Moon (1,737 km (1,079 miles)).[50]

Despite its accuracy in explaining many lines of evidence, there are still some difficulties that are not fully explained by the giant impact hypothesis, most of them involving the Moon's composition.[54]

In 2001, a team at the Carnegie Institute of Washington reported the most precise measurement of the isotopic signatures of lunar rocks.[58] To their surprise, the team found that the rocks from the Apollo program carried an isotopic signature that was identical with rocks from Earth, and were different from almost all other bodies in the Solar System. Because most of the material that went into orbit to form the Moon was thought to come from Theia, this observation was unexpected. In 2007, researchers from the California Institute of Technology announced that there was less than a 1% chance that Theia and Earth had identical isotopic signatures. Published in 2012, an analysis of titanium isotopes in Apollo lunar samples showed that the Moon has the same composition as Earth,[59] which conflicts with what is expected if the Moon formed far from Earth's orbit or from Theia. Variations on the giant impact hypothesis may explain this data.

## Physical characteristics

### Internal structure

Chemical composition of the lunar surface regolith (derived from crustal rocks)[60]
CompoundFormulaComposition (wt %)
MariaHighlands
silicaSiO245.4%45.5%
aluminaAl2O314.9%24.0%
limeCaO11.8%15.9%
iron(II) oxideFeO14.1%5.9%
magnesiaMgO9.2%7.5%
titanium dioxideTiO23.9%0.6%
sodium oxideNa2O0.6%0.6%
Total99.9%100.0%

The Moon is a differentiated body: it has a geochemically distinct crust, mantle, and core. The Moon has a solid iron-rich inner core with a radius of 240 km (150 mi) and a fluid outer core primarily made of liquid iron with a radius of roughly 300 km (190 mi). Around the core is a partially molten boundary layer with a radius of about 500 km (310 mi).[61] This structure is thought to have developed through the fractional crystallization of a global magma ocean shortly after the Moon's formation 4.5 billion years ago.[63] Crystallization of this magma ocean would have created a mafic mantle from the precipitation and sinking of the minerals olivine, clinopyroxene, and orthopyroxene; after about three-quarters of the magma ocean had crystallised, lower-density plagioclase minerals could form and float into a crust on top.[64] The final liquids to crystallise would have been initially sandwiched between the crust and mantle, with a high abundance of incompatible and heat-producing elements.[2] Consistent with this, geochemical mapping from orbit shows the crust is mostly anorthosite,[16] and Moon rock samples of the flood lavas erupted on the surface from partial melting in the mantle confirm the mafic mantle composition, which is more iron rich than that of Earth.[2] Geophysical techniques suggest that the crust is on average circa 50 km (31 mi) thick.[2]

The Moon is the second-densest satellite in the Solar System, after Io. However, the inner core of the Moon is small, with a radius of about 350 km (220 mi) or less,[2] around 20% of the radius of the Moon. Its composition is not well constrained, but it is probably metallic iron alloyed with a small amount of sulfur and nickel; analyses of the Moon's time-variable rotation indicate that it is at least partly molten.[67]

### Surface geology

The topography of the Moon has been measured with laser altimetry and stereo image analysis.[68] The most visible topographic feature is the giant far-side South Pole–Aitken basin, some 2,240 km (1,390 mi) in diameter, the largest crater on the Moon and the second-largest confirmed impact crater in the Solar System.[71][73] At 13 km (8.1 mi) deep, its floor is the lowest point on the surface of the Moon.[71][74] The highest elevations on the surface of the Moon are located directly to the northeast, and it has been suggested that this area might have been thickened by the oblique formation impact of the South Pole–Aitken basin.[75] Other large impact basins, such as Imbrium, Serenitatis, Crisium, Smythii, and Orientale, also possess regionally low elevations and elevated rims.[71] The lunar far side is on average about 1.9 km (1.2 mi) higher than the near side.[2]

The discovery of fault scarp cliffs by the Lunar Reconnaissance Orbiter suggest that the Moon has shrunk within the past billion years, by a radius of about 90 metres (300 ft).[76] Similar shrinkage features exist on Mercury.

#### Volcanic features

The dark and relatively featureless lunar plains that can clearly be seen with the naked eye are called maria (Latin for "seas"; singular mare), because they were believed by ancient astronomers to be filled with water.[77] They are now known to be vast solidified pools of ancient basaltic lava. Although similar to terrestrial basalts, lunar basalts have more iron and no minerals altered by water.[78] The majority of these lavas erupted or flowed into the depressions associated with impact basins. Several geologic provinces containing shield volcanoes and volcanic domes are found within the near side maria.[81]

Almost all maria are on the near side of the Moon, covering 31% of the surface on the near side,[82] compared with a few scattered patches on the far side covering only 2%.[83] This is thought to be due to a concentration of heat-producing elements under the crust on the near side, seen on geochemical maps obtained by Lunar Prospector's gamma-ray spectrometer, which would have caused the underlying mantle to heat up, partially melt, rise to the surface and erupt.[64][87][88] Most of the Moon's mare basalts erupted during the Imbrian period, 3.0–3.5 billion years ago, although some radiometrically dated samples are as old as 4.2 billion years. Until recently, the youngest eruptions, dated by crater counting, appeared to have been only 1.2 billion years ago.[90] In 2006, a study of Ina, a tiny depression in Lacus Felicitatis, found jagged, relatively dust-free features that, due to the lack of erosion by infalling debris, appeared to be only 2 million years old.[91] Moonquakes and releases of gas also indicate some continued lunar activity.[91] In 2014 NASA announced "widespread evidence of young lunar volcanism" at 70 irregular mare patches identified by the Lunar Reconnaissance Orbiter, some less than 50 million years old. This raises the possibility of a much warmer lunar mantle than previously believed, at least on the near side where the deep crust is substantially warmer due to the greater concentration of radioactive elements.[92][8][8][8] Just prior to this, evidence has been presented for 2–10 million years younger basaltic volcanism inside Lowell crater,[8][8] Orientale basin, located in the transition zone between the near and far sides of the Moon. An initially hotter mantle and/or local enrichment of heat-producing elements in the mantle could be responsible for prolonged activities also on the far side in the Orientale basin.[8][8]

The lighter-coloured regions of the Moon are called terrae, or more commonly highlands, because they are higher than most maria. They have been radiometrically dated to having formed 4.4 billion years ago, and may represent plagioclase cumulates of the lunar magma ocean.[90] In contrast to Earth, no major lunar mountains are believed to have formed as a result of tectonic events.[8]

The concentration of maria on the Near Side likely reflects the substantially thicker crust of the highlands of the Far Side, which may have formed in a slow-velocity impact of a second moon of Earth a few tens of millions of years after their formation.[8][8]

#### Impact craters

The other major geologic process that has affected the Moon's surface is impact cratering, with craters formed when asteroids and comets collide with the lunar surface. There are estimated to be roughly 300,000 craters wider than 1 km (0.6 mi) on the Moon's near side alone.[105] Some of these are named for scholars, scientists, artists and explorers.[106] The lunar geologic timescale is based on the most prominent impact events, including Nectaris, Imbrium, and Orientale, structures characterized by multiple rings of uplifted material, typically hundreds to thousands of kilometres in diameter and associated with a broad apron of ejecta deposits that form a regional stratigraphic horizon.[107] The lack of an atmosphere, weather and recent geological processes mean that many of these craters are well-preserved. Although only a few multi-ring basins have been definitively dated, they are useful for assigning relative ages. Because impact craters accumulate at a nearly constant rate, counting the number of craters per unit area can be used to estimate the age of the surface.[107] The radiometric ages of impact-melted rocks collected during the Apollo missions cluster between 3.8 and 4.1 billion years old: this has been used to propose a Late Heavy Bombardment of impacts.[109]

Blanketed on top of the Moon's crust is a highly comminuted (broken into ever smaller particles) and impact gardened surface layer called regolith, formed by impact processes. The finer regolith, the lunar soil of silicon dioxide glass, has a texture resembling snow and a scent resembling spent gunpowder.[110] The regolith of older surfaces is generally thicker than for younger surfaces: it varies in thickness from 10–20 km (6.2–12.4 mi) in the highlands and 3–5 km (1.9–3.1 mi) in the maria. Beneath the finely comminuted regolith layer is the megaregolith, a layer of highly fractured bedrock many kilometres thick.[112]

#### Lunar swirls

Lunar swirls are enigmatic features found across the Moon’s surface, which are characterized by having a high albedo, appearing optically immature (i.e. having the optical characteristics of a relatively young regolith), and (often) having a sinuous shape. Their curvilinear shape is often accentuated by low albedo regions that wind between the bright swirls.

#### Presence of water

Liquid water cannot persist on the lunar surface. When exposed to solar radiation, water quickly decomposes through a process known as photodissociation and is lost to space. However, since the 1960s, scientists have hypothesized that water ice may be deposited by impacting comets or possibly produced by the reaction of oxygen-rich lunar rocks, and hydrogen from solar wind, leaving traces of water which could possibly survive in cold, permanently shadowed craters at either pole on the Moon.[115][118] Computer simulations suggest that up to 14,000 km2 (5,400 sq mi) of the surface may be in permanent shadow.[119] The presence of usable quantities of water on the Moon is an important factor in rendering lunar habitation as a cost-effective plan; the alternative of transporting water from Earth would be prohibitively expensive.[120]

In years since, signatures of water have been found to exist on the lunar surface.[121] In 1994, the bistatic radar experiment located on the Clementine spacecraft, indicated the existence of small, frozen pockets of water close to the surface. However, later radar observations by Arecibo, suggest these findings may rather be rocks ejected from young impact craters.[122] In 1998, the neutron spectrometer located on the Lunar Prospector spacecraft, indicated that high concentrations of hydrogen are present in the first meter of depth in the regolith near the polar regions.[125] In 2008, an analysis of volcanic lava beads, brought back to Earth aboard Apollo 15, showed small amounts of water to exist in the interior of the beads.[128]

The 2008 Chandrayaan-1 spacecraft has since confirmed the existence of surface water ice, using the on-board Moon Mineralogy Mapper. The spectrometer observed absorption lines common to hydroxyl, in reflected sunlight, providing evidence of large quantities of water ice, on the lunar surface. The spacecraft showed that concentrations may possibly be as high as 1,000 ppm.[131] In 2009, LCROSS sent a 2,300 kg (5,100 lb) impactor into a permanently shadowed polar crater, and detected at least 100 kg (220 lb) of water in a plume of ejected material.[132][133] Another examination of the LCROSS data showed the amount of detected water to be closer to 155 ± 12 kg (342 ± 26 lb).[136]

In May 2011, Erik Hauri et al. reported[138] 615–1410 ppm water in melt inclusions in lunar sample 74220, the famous high-titanium "orange glass soil" of volcanic origin collected during the Apollo 17 mission in 1972. The inclusions were formed during explosive eruptions on the Moon approximately 3.7 billion years ago. This concentration is comparable with that of magma in Earth's upper mantle. Although of considerable selenological interest, Hauri's announcement affords little comfort to would-be lunar colonists—the sample originated many kilometers below the surface, and the inclusions are so difficult to access that it took 39 years to find them with a state-of-the-art ion microprobe instrument.

### Gravitational field

The gravitational field of the Moon has been measured through tracking the Doppler shift of radio signals emitted by orbiting spacecraft. The main lunar gravity features are mascons, large positive gravitational anomalies associated with some of the giant impact basins, partly caused by the dense mare basaltic lava flows that fill these basins.[141][142] These anomalies greatly influence the orbit of spacecraft about the Moon. There are some puzzles: lava flows by themselves cannot explain all of the gravitational signature, and some mascons exist that are not linked to mare volcanism.[144]

### Magnetic field

The Moon has an external magnetic field of about 1–100 nanoteslas, less than one-hundredth that of Earth. It does not currently have a global dipolar magnetic field and only has crustal magnetization, probably acquired early in lunar history when a dynamo was still operating.[147][148] Alternatively, some of the remnant magnetization may be from transient magnetic fields generated during large impact events, through the expansion of an impact-generated plasma cloud in the presence of an ambient magnetic field—this is supported by the apparent location of the largest crustal magnetizations near the antipodes of the giant impact basins.[150]

### Atmosphere

The Moon has an atmosphere so tenuous as to be nearly vacuum, with a total mass of less than 10 metric tons (9.8 long tons; 11 short tons).[153] The surface pressure of this small mass is around 3 × 10−15 atm (0.3 nPa); it varies with the lunar day. Its sources include outgassing and sputtering, the release of atoms from the bombardment of lunar soil by solar wind ions.[16][157] Elements that have been detected include sodium and potassium, produced by sputtering, which are also found in the atmospheres of Mercury and Io; helium-4 and neon[158] from the solar wind; and argon-40, radon-222, and polonium-210, outgassed after their creation by radioactive decay within the crust and mantle.[160][162] The absence of such neutral species (atoms or molecules) as oxygen, nitrogen, carbon, hydrogen and magnesium, which are present in the regolith, is not understood.[160] Water vapour has been detected by Chandrayaan-1 and found to vary with latitude, with a maximum at ~60–70 degrees; it is possibly generated from the sublimation of water ice in the regolith.[164] These gases can either return into the regolith due to the Moon's gravity or be lost to space, either through solar radiation pressure or, if they are ionized, by being swept away by the solar wind's magnetic field.[160]

#### Dust

A permanent asymmetric moon dust cloud exists around the Moon, created by small particles from comets. Estimates are 5 tons of comet particles strike the Moon's surface each 24 hours. The particles strike the Moon's surface ejecting moon dust above the Moon. The dust stays above the Moon approximately 10 minutes, taking 5 minutes to rise, and 5 minutes to fall. On average, 120 kilograms of dust are present above the Moon, rising to 100 kilometers above the surface. The dust measurements were made by LADEE's Lunar Dust EXperiment (LDEX), between 20 and 100 kilometers above the surface, during a six-month period. LDEX detected an average of one 0.3 micrometer moon dust particle each minute. Dust particle counts peaked during the Geminid, Quadrantid, Northern Taurid, and Omicron Centaurid meteor showers, when the Earth, and Moon, pass through comet debris. The cloud is asymmetric, more dense near the boundary between the Moon's dayside and nightside.[165][168]

### Seasons

The Moon's axial tilt with respect to the ecliptic is only 1.5424°,[169] much less than the 23.44° of Earth. Because of this, the Moon's solar illumination varies much less with season, and topographical details play a crucial role in seasonal effects.[170] From images taken by Clementine in 1994, it appears that four mountainous regions on the rim of Peary Crater at the Moon's north pole may remain illuminated for the entire lunar day, creating peaks of eternal light. No such regions exist at the south pole. Similarly, there are places that remain in permanent shadow at the bottoms of many polar craters,[119] and these dark craters are extremely cold: Lunar Reconnaissance Orbiter measured the lowest summer temperatures in craters at the southern pole at 35 K (−238 °C; −397 °F)[171] and just 26 K (−247 °C; −413 °F) close to the winter solstice in north polar Hermite Crater. This is the coldest temperature in the Solar System ever measured by a spacecraft, colder even than the surface of Pluto.[170] Average temperatures of the Moon's surface are reported, but temperatures of different areas will vary greatly depending upon whether a spot is in sunlight or in shadow.[172]

## Relationship to Earth

### Orbit

The Moon makes a complete orbit around Earth with respect to the fixed stars about once every 27.3 days (its sidereal period). However, because Earth is moving in its orbit around the Sun at the same time, it takes slightly longer for the Moon to show the same phase to Earth, which is about 29.5 days (its synodic period).[82] Unlike most satellites of other planets, the Moon orbits closer to the ecliptic plane than to the planet's equatorial plane. The Moon's orbit is subtly perturbed by the Sun and Earth in many small, complex and interacting ways. For example, the plane of the Moon's orbital motion gradually rotates, which affects other aspects of lunar motion. These follow-on effects are mathematically described by Cassini's laws.[173]

### Relative size

The Moon is exceptionally large relative to Earth: a quarter its diameter and 1/81 its mass.[82] It is the largest moon in the Solar System relative to the size of its planet, though Charon is larger relative to the dwarf planet Pluto, at 1/9 Pluto's mass.[174] Earth and the Moon are nevertheless still considered a planet–satellite system, rather than a double planet, because their barycentre, the common centre of mass, is located 1,700 km (1,100 mi) (about a quarter of Earth's radius) beneath Earth's surface.[175]

### Appearance from Earth

The Moon is in synchronous rotation: it rotates about its axis in about the same time it takes to orbit Earth. This results in it nearly always keeping the same face turned towards Earth. The Moon used to rotate at a faster rate, but early in its history, its rotation slowed and became tidally locked in this orientation as a result of frictional effects associated with tidal deformations caused by Earth.[177] The side of the Moon that faces Earth is called the near side, and the opposite side the far side. The far side is often inaccurately called the "dark side", but in fact, it is illuminated as often as the near side: once per lunar day, during the new moon phase we observe on Earth when the near side is dark.[178] In 2016, planetary scientists, using data collected on the much earlier Nasa Lunar Prospector mission, found two hydrogen-rich areas on opposite sides of the Moon, probably in the form of water ice. It is speculated that these patches were the poles of the Moon billions of years ago, before it was tidally locked to Earth.[179]

The Moon has an exceptionally low albedo, giving it a reflectance that is slightly brighter than that of worn asphalt. Despite this, it is the brightest object in the sky after the Sun.[82] This is partly due to the brightness enhancement of the opposition effect; at quarter phase, the Moon is only one-tenth as bright, rather than half as bright, as at full moon.[180]

Additionally, colour constancy in the visual system recalibrates the relations between the colours of an object and its surroundings, and because the surrounding sky is comparatively dark, the sunlit Moon is perceived as a bright object. The edges of the full moon seem as bright as the centre, with no limb darkening, due to the reflective properties of lunar soil, which reflects more light back towards the Sun than in other directions. The Moon does appear larger when close to the horizon, but this is a purely psychological effect, known as the Moon illusion, first described in the 7th century BC. The full moon subtends an arc of about 0.52° (on average) in the sky, roughly the same apparent size as the Sun (see ).

The highest altitude of the Moon in the sky varies with the lunar phase and the season of the year. The full moon is highest during winter. The 18.6-year nodes cycle also has an influence: when the ascending node of the lunar orbit is in the vernal equinox, the lunar declination can go as far as 28° each month. This means the Moon can go overhead at latitudes up to 28° from the equator, instead of only 18°. The orientation of the Moon's crescent also depends on the latitude of the observation site: close to the equator, an observer can see a smile-shaped crescent moon.[181]

The Moon is visible for two weeks every 27.3 days at the North and South Pole. The Moon's light is used by zooplankton in the Arctic when the sun is below the horizon for months on end.[182]

The distance between the Moon and Earth varies from around 356,400 km (221,500 mi) to 406,700 km (252,700 mi) at perigees (closest) and apogees (farthest), respectively. On 19 March 2011, it was closer to Earth when at full phase than it has been since 1993, 14% closer than its farthest position in apogee.[183] Reported as a "super moon", this closest point coincides within an hour of a full moon, and it was 30% more luminous than when at its greatest distance due to its angular diameter being 14% greater, because ${displaystyle scriptstyle 1.14^{2}approx 1.30}$.[184][185] At lower levels, the human perception of reduced brightness as a percentage is provided by the following formula:[186][187]

${displaystyle {text{perceived reduction}}%=100times {sqrt {{text{actual reduction}}% over 100}}}$

When the actual reduction is 1.00 / 1.30, or about 0.770, the perceived reduction is about 0.877, or 1.00 / 1.14. This gives a maximum perceived increase of 14% between apogee and perigee moons of the same phase.[188]

There has been historical controversy over whether features on the Moon's surface change over time. Today, many of these claims are thought to be illusory, resulting from observation under different lighting conditions, poor astronomical seeing, or inadequate drawings. However, outgassing does occasionally occur, and could be responsible for a minor percentage of the reported lunar transient phenomena. Recently, it has been suggested that a roughly 3 km (1.9 mi) diameter region of the lunar surface was modified by a gas release event about a million years ago.[189][192] The Moon's appearance, like that of the Sun, can be affected by Earth's atmosphere: common effects are a 22° halo ring formed when the Moon's light is refracted through the ice crystals of high cirrostratus cloud, and smaller coronal rings when the Moon is seen through thin clouds.[193]

The illuminated area of the visible sphere (degree of illumination) is given by ${displaystyle {frac {1}{2}}(1-cos e)}$, where ${displaystyle e}$ is the elongation (i.e. the angle between Moon, the observer (on Earth) and the Sun).

### Tidal effects

The tides on Earth are mostly generated by the gradient in intensity of the Moon's gravitational pull from one side of Earth to the other, the tidal forces. This forms two tidal bulges on Earth, which are most clearly seen in elevated sea level as ocean tides.[195] Because Earth spins about 27 times faster than the Moon moves around it, the bulges are dragged along with Earth's surface faster than the Moon moves, rotating around Earth once a day as it spins on its axis.[195] The ocean tides are magnified by other effects: frictional coupling of water to Earth's rotation through the ocean floors, the inertia of water's movement, ocean basins that get shallower near land, and oscillations between different ocean basins.[198] The tidal effect of the Sun on Earth's oceans is almost half that of the Moon, and their gravitational interplay is responsible for spring and neap tides.[195]

Gravitational coupling between the Moon and the bulge nearest the Moon acts as a torque on Earth's rotation, draining angular momentum and rotational kinetic energy from Earth's spin.[195][200] In turn, angular momentum is added to the Moon's orbit in a process confusingly known as tidal acceleration, which lifts the Moon into a higher orbit with a lower orbital speed and a longer period. Thus the distance between Earth and Moon is increasing, and Earth's spin is slowing down.[200] Measurements from lunar ranging experiments with laser reflectors left during the Apollo missions have found that the Moon's distance to Earth increases by 38 mm (1.5 in) per year[202] (roughly the rate at which human fingernails grow).[17] Atomic clocks also show that Earth's day lengthens by about 15 microseconds every year,[17] slowly increasing the rate at which UTC is adjusted by leap seconds. Left to run its course, this tidal drag would continue until the spin of Earth and the orbital period of the Moon matched, creating mutual tidal locking between the two, as is already currently the case with Pluto and its moon Charon. However, the Sun will become a red giant long before that, engulfing Earth.[17][17]

The lunar surface also experiences tides of around 10 cm (4 in) amplitude over 27 days, with two components: a fixed one due to Earth, because they are in synchronous rotation, and a varying component from the Sun.[200] The Earth-induced component arises from libration, a result of the Moon's orbital eccentricity; if the Moon's orbit were perfectly circular, there would only be solar tides.[200] Libration also changes the angle from which the Moon is seen, allowing about 59% of its surface to be seen from Earth (but only half at any instant).[82] The cumulative effects of stress built up by these tidal forces produces moonquakes. Moonquakes are much less common and weaker than earthquakes, although they can last for up to an hour—a significantly longer time than terrestrial earthquakes—because of the absence of water to damp out the seismic vibrations. The existence of moonquakes was an unexpected discovery from seismometers placed on the Moon by Apollo astronauts from 1969 through 1972.[17]

### Eclipses

Eclipses can only occur when the Sun, Earth, and Moon are all in a straight line (termed "syzygy"). Solar eclipses occur at new moon, when the Moon is between the Sun and Earth. In contrast, lunar eclipses occur at full moon, when Earth is between the Sun and Moon. The apparent size of the Moon is roughly the same as that of the Sun, with both being viewed at close to one-half a degree wide. The Sun is much larger than the Moon but it is the precise vastly greater distance that gives it the same apparent size as the much closer and much smaller Moon from the perspective of Earth. The variations in apparent size, due to the non-circular orbits, are nearly the same as well, though occurring in different cycles. This makes possible both total (with the Moon appearing larger than the Sun) and annular (with the Moon appearing smaller than the Sun) solar eclipses.[17] In a total eclipse, the Moon completely covers the disc of the Sun and the solar corona becomes visible to the naked eye. Because the distance between the Moon and Earth is very slowly increasing over time,[195] the angular diameter of the Moon is decreasing. Also, as it evolves toward becoming a red giant, the size of the Sun, and its apparent diameter in the sky, are slowly increasing. The combination of these two changes means that hundreds of millions of years ago, the Moon would always completely cover the Sun on solar eclipses, and no annular eclipses were possible. Likewise, hundreds of millions of years in the future, the Moon will no longer cover the Sun completely, and total solar eclipses will not occur.[209]

Because the Moon's orbit around Earth is inclined by about 5° to the orbit of Earth around the Sun, eclipses do not occur at every full and new moon. For an eclipse to occur, the Moon must be near the intersection of the two orbital planes.[210] The periodicity and recurrence of eclipses of the Sun by the Moon, and of the Moon by Earth, is described by the saros, which has a period of approximately 18 years.[211]

Because the Moon is continuously blocking our view of a half-degree-wide circular area of the sky,[213] the related phenomenon of occultation occurs when a bright star or planet passes behind the Moon and is occulted: hidden from view. In this way, a solar eclipse is an occultation of the Sun. Because the Moon is comparatively close to Earth, occultations of individual stars are not visible everywhere on the planet, nor at the same time. Because of the precession of the lunar orbit, each year different stars are occulted.[214]

## Observation and exploration

### Ancient and medieval studies

Understanding of the Moon's cycles was an early development of astronomy: by the 5th century BC, Babylonian astronomers had recorded the 18-year Saros cycle of lunar eclipses,[216] and Indian astronomers had described the Moon's monthly elongation. The Chinese astronomer Shi Shen (fl. 4th century BC) gave instructions for predicting solar and lunar eclipses. Later, the physical form of the Moon and the cause of moonlight became understood. The ancient Greek philosopher Anaxagoras (d. 428 BC) reasoned that the Sun and Moon were both giant spherical rocks, and that the latter reflected the light of the former.[217] Although the Chinese of the Han Dynasty believed the Moon to be energy equated to qi, their 'radiating influence' theory also recognized that the light of the Moon was merely a reflection of the Sun, and Jing Fang (78–37 BC) noted the sphericity of the Moon. In the 2nd century AD Lucian wrote a novel where the heroes travel to the Moon, which is inhabited. In 499 AD, the Indian astronomer Aryabhata mentioned in his Aryabhatiya that reflected sunlight is the cause of the shining of the Moon.[218] The astronomer and physicist Alhazen (965–1039) found that sunlight was not reflected from the Moon like a mirror, but that light was emitted from every part of the Moon's sunlit surface in all directions. Shen Kuo (1031–1095) of the Song dynasty created an allegory equating the waxing and waning of the Moon to a round ball of reflective silver that, when doused with white powder and viewed from the side, would appear to be a crescent.

In Aristotle's (384–322 BC) description of the universe, the Moon marked the boundary between the spheres of the mutable elements (earth, water, air and fire), and the imperishable stars of aether, an influential philosophy that would dominate for centuries. However, in the 2nd century BC, Seleucus of Seleucia correctly theorized that tides were due to the attraction of the Moon, and that their height depends on the Moon's position relative to the Sun.[221] In the same century, Aristarchus computed the size and distance of the Moon from Earth, obtaining a value of about twenty times the radius of Earth for the distance. These figures were greatly improved by Ptolemy (90–168 AD): his values of a mean distance of 59 times Earth's radius and a diameter of 0.292 Earth diameters were close to the correct values of about 60 and 0.273 respectively. Archimedes (287–212 BC) designed a planetarium that could calculate the motions of the Moon and other objects in the Solar System.[222]

During the Middle Ages, before the invention of the telescope, the Moon was increasingly recognised as a sphere, though many believed that it was "perfectly smooth".[224]

In 1609, Galileo Galilei drew one of the first telescopic drawings of the Moon in his book Sidereus Nuncius and noted that it was not smooth but had mountains and craters. Telescopic mapping of the Moon followed: later in the 17th century, the efforts of Giovanni Battista Riccioli and Francesco Maria Grimaldi led to the system of naming of lunar features in use today. The more exact 1834–36 Mappa Selenographica of Wilhelm Beer and Johann Heinrich Mädler, and their associated 1837 book Der Mond, the first trigonometrically accurate study of lunar features, included the heights of more than a thousand mountains, and introduced the study of the Moon at accuracies possible in earthly geography.[226] Lunar craters, first noted by Galileo, were thought to be volcanic until the 1870s proposal of Richard Proctor that they were formed by collisions.[82] This view gained support in 1892 from the experimentation of geologist Grove Karl Gilbert, and from comparative studies from 1920 to the 1940s,[227] leading to the development of lunar stratigraphy, which by the 1950s was becoming a new and growing branch of astrogeology.[82]

### By spacecraft

#### 20th century

##### Soviet missions

The Cold War-inspired Space Race between the Soviet Union and the U.S. led to an acceleration of interest in exploration of the Moon. Once launchers had the necessary capabilities, these nations sent unmanned probes on both flyby and impact/lander missions. Spacecraft from the Soviet Union's Luna program were the first to accomplish a number of goals: following three unnamed, failed missions in 1958,[228] the first human-made object to escape Earth's gravity and pass near the Moon was Luna 1; the first human-made object to impact the lunar surface was Luna 2, and the first photographs of the normally occluded far side of the Moon were made by Luna 3, all in 1959.

The first spacecraft to perform a successful lunar soft landing was Luna 9 and the first unmanned vehicle to orbit the Moon was Luna 10, both in 1966.[82] Rock and soil samples were brought back to Earth by three Luna sample return missions (Luna 16 in 1970, Luna 20 in 1972, and Luna 24 in 1976), which returned 0.3 kg total.[229] Two pioneering robotic rovers landed on the Moon in 1970 and 1973 as a part of Soviet Lunokhod programme.

##### United States missions

The United States launched unmanned probes to develop an understanding of the lunar surface for an eventual manned landing: the Jet Propulsion Laboratory's Ranger program produced the first close-up pictures; the Lunar Orbiter program produced maps of the entire Moon; the Surveyor program landed its first spacecraft four months after Luna 9. NASA's manned Apollo program was developed in parallel; after a series of unmanned and manned tests of the Apollo spacecraft in Earth orbit, and spurred on by a potential Soviet lunar flight, in 1968 Apollo 8 made the first crewed mission to lunar orbit. The subsequent landing of the first humans on the Moon in 1969 is seen by many as the culmination of the Space Race.[230]

Neil Armstrong became the first person to walk on the Moon as the commander of the American mission Apollo 11 by first setting foot on the Moon at 02:56 UTC on 21 July 1969.[231] An estimated 500 million people worldwide watched the transmission by the Apollo TV camera, the largest television audience for a live broadcast at that time.[232][233] The Apollo missions 11 to 17 (except Apollo 13, which aborted its planned lunar landing) returned 380.05 kilograms (837.87 lb) of lunar rock and soil in 2,196 separate samples.[236] The American Moon landing and return was enabled by considerable technological advances in the early 1960s, in domains such as ablation chemistry, software engineering and atmospheric re-entry technology, and by highly competent management of the enormous technical undertaking.[237]

Scientific instrument packages were installed on the lunar surface during all the Apollo landings. Long-lived instrument stations, including heat flow probes, seismometers, and magnetometers, were installed at the Apollo 12, 14, 15, 16, and 17 landing sites. Direct transmission of data to Earth concluded in late 1977 due to budgetary considerations,[238][240] but as the stations' lunar laser ranging corner-cube retroreflector arrays are passive instruments, they are still being used. Ranging to the stations is routinely performed from Earth-based stations with an accuracy of a few centimetres, and data from this experiment are being used to place constraints on the size of the lunar core.[243]

##### 1980s–2000

After the first Moon race there were years of near quietude but starting in the 1990s, many more countries have become involved in direct exploration of the Moon. In 1990, Japan became the third country to place a spacecraft into lunar orbit with its Hiten spacecraft. The spacecraft released a smaller probe, Hagoromo, in lunar orbit, but the transmitter failed, preventing further scientific use of the mission.[244] In 1994, the U.S. sent the joint Defense Department/NASA spacecraft Clementine to lunar orbit. This mission obtained the first near-global topographic map of the Moon, and the first global multispectral images of the lunar surface.[245] This was followed in 1998 by the Lunar Prospector mission, whose instruments indicated the presence of excess hydrogen at the lunar poles, which is likely to have been caused by the presence of water ice in the upper few meters of the regolith within permanently shadowed craters.[246]

India, Japan, China, the United States, and the European Space Agency each sent lunar orbiters, especially ISRO's Chandrayaan-1 has contributed to confirming the discovery of lunar water ice in permanently shadowed craters at the poles and bound into the lunar regolith. The post-Apollo era has also seen two rover missions: the final Soviet Lunokhod mission in 1973, and China's ongoing Chang'e 3 mission, which deployed its Yutu rover on 14 December 2013. The Moon remains, under the Outer Space Treaty, free to all nations to explore for peaceful purposes.

#### 21st century

The European spacecraft SMART-1, the second ion-propelled spacecraft, was in lunar orbit from 15 November 2004 until its lunar impact on 3 September 2006, and made the first detailed survey of chemical elements on the lunar surface.[247]

China has pursued an ambitious program of lunar exploration, beginning with Chang'e 1, which successfully orbited the Moon from 5 November 2007 until its controlled lunar impact on 1 March 2009.[248] In its sixteen-month mission, it obtained a full image map of the Moon. China followed up this success with Chang'e 2 beginning in October 2010, which reached the Moon over twice as fast as Chang'e 1, mapped the Moon at a higher resolution over an eight-month period, then left lunar orbit in favor of an extended stay at the Earth–Sun L2 Lagrangian point, before finally performing a flyby of asteroid 4179 Toutatis on 13 December 2012, and then heading off into deep space. On 14 December 2013, Chang'e 3 improved upon its orbital mission predecessors by landing a lunar lander onto the Moon's surface, which in turn deployed a lunar rover, named Yutu (Chinese: 玉兔; literally "Jade Rabbit"). In so doing, Chang'e 3 made the first lunar soft landing since Luna 24 in 1976, and the first lunar rover mission since Lunokhod 2 in 1973. China intends to launch another rover mission (Chang'e 4) before 2020, followed by a sample return mission (Chang'e 5) soon after.[249]

Between 4 October 2007 and 10 June 2009, the Japan Aerospace Exploration Agency's Kaguya (Selene) mission, a lunar orbiter fitted with a high-definition video camera, and two small radio-transmitter satellites, obtained lunar geophysics data and took the first high-definition movies from beyond Earth orbit.[250][251] India's first lunar mission, Chandrayaan I, orbited from 8 November 2008 until loss of contact on 27 August 2009, creating a high resolution chemical, mineralogical and photo-geological map of the lunar surface, and confirming the presence of water molecules in lunar soil.[20] The Indian Space Research Organisation planned to launch Chandrayaan II in 2013, which would have included a Russian robotic lunar rover.[20][20] However, the failure of Russia's Fobos-Grunt mission has delayed this project.

The U.S. co-launched the Lunar Reconnaissance Orbiter (LRO) and the LCROSS impactor and follow-up observation orbiter on 18 June 2009; LCROSS completed its mission by making a planned and widely observed impact in the crater Cabeus on 9 October 2009,[20] whereas LRO is currently in operation, obtaining precise lunar altimetry and high-resolution imagery. In November 2011, the LRO passed over the Aristarchus crater, which spans 40 km (25 mi) and sinks more than 3.5 km (2.2 mi) deep. The crater is one of the most visible ones from Earth. "The Aristarchus plateau is one of the most geologically diverse places on the Moon: a mysterious raised flat plateau, a giant rille carved by enormous outpourings of lava, fields of explosive volcanic ash, and all surrounded by massive flood basalts", said Mark Robinson, principal investigator of the Lunar Reconnaissance Orbiter Camera at Arizona State University. NASA released photos of the crater on 25 December 2011.[20]

Two NASA GRAIL spacecraft began orbiting the Moon around 1 January 2012,[20] on a mission to learn more about the Moon's internal structure. NASA's LADEE probe, designed to study the lunar exosphere, achieved orbit on 6 October 2013.

Upcoming lunar missions include Russia's Luna-Glob: an unmanned lander with a set of seismometers, and an orbiter based on its failed Martian Fobos-Grunt mission.[20][20] Privately funded lunar exploration has been promoted by the Google Lunar X Prize, announced 13 September 2007, which offers US\$20 million to anyone who can land a robotic rover on the Moon and meet other specified criteria.[20] Shackleton Energy Company is building a program to establish operations on the south pole of the Moon to harvest water and supply their Propellant Depots.[20]

NASA began to plan to resume manned missions following the call by U.S. President George W. Bush on 14 January 2004 for a manned mission to the Moon by 2019 and the construction of a lunar base by 2024.[264] The Constellation program was funded and construction and testing begun on a manned spacecraft and launch vehicle,[265] and design studies for a lunar base.[266] However, that program has been cancelled in favor of a manned asteroid landing by 2025 and a manned Mars orbit by 2035.[267] India has also expressed its hope to send a manned mission to the Moon by 2020.[268]

## Astronomy from the Moon

For many years, the Moon has been recognized as an excellent site for telescopes.[269] It is relatively nearby; astronomical seeing is not a concern; certain craters near the poles are permanently dark and cold, and thus especially useful for infrared telescopes; and radio telescopes on the far side would be shielded from the radio chatter of Earth.[270] The lunar soil, although it poses a problem for any moving parts of telescopes, can be mixed with carbon nanotubes and epoxies in the construction of mirrors up to 50 meters in diameter.[271] A lunar zenith telescope can be made cheaply with ionic liquid.[272]

In April 1972, the Apollo 16 mission recorded various astronomical photos and spectra in ultraviolet with the Far Ultraviolet Camera/Spectrograph.[273]

## Legal status

During the Cold War, the United States Army conducted a classified feasibility study in the late 1950s called Project Horizon, to construct a manned military outpost on the Moon, which would have been home to a bombing system targeted at rivals on Earth. The study included the possibility of conducting a lunar-based nuclear test.[274] The Air Force, which at the time was in competition with the Army for a leading role in the space program, developed its own, similar plan called Lunex.[275] However, both these proposals were ultimately passed over as the space program was largely transferred from the military to the civilian agency NASA.

Although Luna landers scattered pennants of the Soviet Union on the Moon, and U.S. flags were symbolically planted at their landing sites by the Apollo astronauts, no nation claims ownership of any part of the Moon's surface.[276] Russia and the U.S. are party to the 1967 Outer Space Treaty,[277] which defines the Moon and all outer space as the "province of all mankind".[276] This treaty also restricts the use of the Moon to peaceful purposes, explicitly banning military installations and weapons of mass destruction.[278] The 1979 Moon Agreement was created to restrict the exploitation of the Moon's resources by any single nation, but as of 2014, it has been signed and ratified by only 16 nations, none of which engages in self-launched human space exploration or has plans to do so.[279] Although several individuals have made claims to the Moon in whole or in part, none of these are considered credible.[280][281][282]

## In culture

### Mythology

The Moon was often personified as a lunar deity in mythology and religion. A 5,000-year-old rock carving at Knowth, Ireland, may represent the Moon, which would be the earliest depiction discovered.[283] The contrast between the brighter highlands and the darker maria creates the patterns seen by different cultures as the Man in the Moon, the rabbit and the buffalo, among others. In many prehistoric and ancient cultures, the Moon was personified as a deity or other supernatural phenomenon, and astrological views of the Moon continue to be propagated today.

In the Ancient Near East, the moon god (Sin/Nanna) was masculine. In Greco-Roman mythology, Sun and Moon are represented as male and female, respectively (Helios/Sol and Selene/Luna). The crescent shape form an early time was used as a symbol representing the Moon. The Moon goddess Selene was represented as wearing a crescent on her headgear in an arrangement reminiscent of horns. The star and crescent arrangement also goes back to the Bronze Age, representing either the Sun and Moon, or the Moon and planet Venus, in combination. It came to represent the goddess Artemis or Hecate, and via the patronage of Hecate came to be used as a symbol of Byzantium.

An iconographic tradition of representing Sun and Moon with faces developed in the late medieval period.

The splitting of the moon (Arabic: انشقاق القمر) is a miracle attributed to Muhammad.[24]

### Calendar

The Moon's regular phases make it a very convenient timepiece, and the periods of its waxing and waning form the basis of many of the oldest calendars. Tally sticks, notched bones dating as far back as 20–30,000 years ago, are believed by some to mark the phases of the Moon.[24][24] The ~30-day month is an approximation of the lunar cycle. The English noun month and its cognates in other Germanic languages stem from Proto-Germanic *mǣnṓth-, which is connected to the above-mentioned Proto-Germanic *mǣnōn, indicating the usage of a lunar calendar among the Germanic peoples (Germanic calendar) prior to the adoption of a solar calendar. The PIE root of moon, *méh1nōt, derives from the PIE verbal root *meh1-, "to measure", "indicat[ing] a functional conception of the moon, i.e. marker of the month" (cf. the English words measure and menstrual),[24][24][24] and echoing the Moon's importance to many ancient cultures in measuring time (see Latin mensis and Ancient Greek μείς (meis) or μήν (mēn), meaning "month").[24][25][25][25] Most historical calendars are lunisolar. The 7th-century Islamic calendar is an exceptional example of a purely lunar calendar. Months are traditionally determined by the visual sighting of the hilal, or earliest crescent moon, over the horizon.[25]

### Modern art and literature

The Moon has been the subject of many works of art and literature and the inspiration for countless others. It is a motif in the visual arts, the performing arts, poetry, prose and music.

### Lunacy

The Moon has long been associated with insanity and irrationality; the words lunacy and lunatic (popular shortening loony) are derived from the Latin name for the Moon, Luna. Philosophers Aristotle and Pliny the Elder argued that the full moon induced insanity in susceptible individuals, believing that the brain, which is mostly water, must be affected by the Moon and its power over the tides, but the Moon's gravity is too slight to affect any single person.[291] Even today, people who believe in a lunar effect claim that admissions to psychiatric hospitals, traffic accidents, homicides or suicides increase during a full moon, but dozens of studies invalidate these claims.[291][292][293][294][296]


text:
# Knowledge Discovery and Data Mining

Clustering using Monte Carlo Cross-Validation

Department of Information and Computer Science University of California, Irvine CA 92717-3425
smyth@ics.uci.edu

This paper appeared in the Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96), Portland, OR, Aug 1996, AAAI Press, pp.126--133.

Finding the \right" number of clusters, k, for a data set is a di cult, and often ill-posed, problem. In a probabilistic clustering context, likelihood-ratios, penalized likelihoods, and Bayesian techniques are among the more popular techniques. In this paper a new cross-validated likelihood criterion is investigated for determining cluster structure. A practical clustering algorithm based on Monte Carlo crossvalidation (MCCV) is introduced. The algorithm permits the data analyst to judge if there is strong evidence for a particular k, or perhaps weaker evidence over a sub-range of k values. Experimental results with Gaussian mixtures on real and simulated data suggest that MCCV provides genuine insight into cluster structure. v-fold cross-validation appears inferior to the penalized likelihood method (BIC), a Bayesian algorithm (AutoClass v2.0), and the new MCCV algorithm. Overall, MCCV and AutoClass appear the most reliable of the methods. MCCV provides the data-miner with a useful data-driven clustering tool which complements the fully Bayesian approach.

Abstract

are few. Furthermore, \optimality" can be di cult to pin down in this context without some assumptions being made. One viewpoint is that the problem of nding the best number of clusters is fundamentally ill-de ned and best avoided (cf. Gelman et al , page 424, in a mixture modelling context). While we sympathize with this view we adopt a more pragmatic approach in this paper, namely, let the data tell us as much as possible about cluster structure, including the number of clusters in the data. If either the data are too few, or the measurement dimensions too noisy, then the data may not reveal much. However, when the data contain interesting structure one seeks an algorithmic technique which can reveal this structure. A fundamental point is that the process of structure discovery in data needs to be interactive, i.e., the data analyst must interpret the results as they see t. In this paper we limit our attention to Gaussian mixture models: however, any probabilistic clustering model for which a likelihood function can be dened is amenable to the proposed approach. The method could conceivably be extended to clustering algorithms which do not possess clear probabilistic semantics (such as the k-means family of algorithms), but this is not pursued here.

Also with the Jet Propulsion Laboratory 525-3660, California Institute of Technology, Pasadena, CA 91109.

Cluster analysis is the process of automatically searching for natural groupings in a data set and extracting characteristic descriptions of these groups. It is a fundamental knowledge discovery process. Clustering algorithms (of which there are many) typically consist of a speci cation of both (1) a criterion for judging the quality of a given grouping and (2) a search method for optimizing this criterion given data (see Jain and Dubes (1988) for an overview). A particularly vexing question, which is often glossed over in published descriptions of clustering algorithms, is \how many clusters are there in the data ?". Formal methods for nding the \optimal" number of clusters

Introduction

Probabilistic Clustering Using Mixture Models Finite Mixture Models

The probabilistic mixture modelling approach to clustering is well-known: one assumes that the data are generated by a linear combination of component density functions resulting in a mixture probability density function of the form: k X fk (xj k ) = (1) j gj (xj j )
j =1

where x is a particular value of a d-dimensional feature vector X, k is the number of components in the model, j are the parameters associated with density component gj , the j are the \weights" for each component j , and k = f 1; . . . ; k; 1 ; . . . ; k g denotes the set of

Estimating the Clusters from Data

parameters for the overall model. We will adopt the notation that ^ k denotes parameters whichP been have estimated from data. It is assumed that j j = 1 and j > 0; 1 j k. The component density functions are often assumed to be multivariate Gaussian with parameters j = f j ; j g where j and j are the mean and covariance matrix, respectively. Thus the mean j speci es the location of the j th component density in feature space and the covariance matrix j prescribes how the data belonging to component j are typically dispersed or scattered around j . The exibility of this model has led to its widespread application, particularly in applied statistics (McLachlan and Basford 1988), and more recently in machine learning and knowledge discovery (Cheeseman and Stutz 1996).

1. Assume that the data are generated by a mixture model, where each component is interpreted as a cluster or class !j and it assumed that each data point must have been generated by one and only one of the classes !j . 2. Given a data set where it is not known which data points came from which components, infer the characteristics (the parameters) of the underlying density functions (the clusters). In particular, given an \unlabelled" data set D = fx1 ; . . . ; xN g, and assuming that the number of clusters k and the functional forms of the component densities gj in Equation 1 are xed, estimate the model parameters ^ k . Given ^ k , one can then calculate the probability that data point x belongs to class !j (by Bayes' rule): g (xj^ ) ^ 1 j k; (2) p(!j jx) = Pk j j ^ j ^ l=1 gl (xj l ) ^l where ^ denotes an estimate of the true parameter . Here, ^ j = p(!j ), i.e., an estimate of the marginal or ^ prior for each cluster. Since the mixture likelihood (or posterior) surface (as a function of the parameters) can have many local maxima, and no closed form solution for the global maximum exists, parameter estimation for mixtures is non-trivial. Much of the popularity of mixture models in recent years is due to the existence of e cient iterative estimation techniques (in particular, the expectation-maximization (EM) algorithm).

Clustering (in this mixture model context) is as follows:

The classical approach is based on hypothesis testing, where hypothesis k states that the underlying density is a mixture of k components. As discussed in Titterington, Smith and Makov (1985, Section 5.4), these techniques are largely unsatisfactory due to the \failure of standard regularity conditions" on the mixture likelihood function. A second approach is the full Bayesian solution where the posterior probability of each value of k is calculated given the data, priors on the mixture parameters, and priors on k itself. A potential di culty with this approach is the computational complexity of integrating over the parameter space to get the posterior probabilities on k. The AutoClass algorithm (Cheeseman and Stutz 1996) uses various approximations to get around the computational issues. Sampling techniques have also been applied to this problem with some success (cf. Diebolt and Robert 1994). A third method (related to the Bayesian approach, see Chickering and Heckerman, 1996) is that of penalized likelihood (such as the Bayesian Information Criterion (BIC) and various coding-based (e.g., MDL/MML) criteria). A penalty term is added to the log-likelihood to penalize the number of parameters (e.g., Sclove 1983). A signi cant problem here is that the general assumptions underlying the asymptotic optimality of the penalized criteria do not hold in the mixture modelling context (Titterington, Smith and Makov, Section 5.4). In theory, the full Bayesian approach is fully optimal and probably the most useful of the three methods listed above. However, in practice it is cumbersome to implement, it is not necessarily straightforward to extend to non-Gaussian problems with dependent samples, and the results will be dependent in a non-transparent manner on the quality of the underlying approximations or simulations. Thus, there is certainly room for exploring alternative methods. Let f (x) be the \true" probability density function for x. Let D = fx1; . . . ; xN g be a random sample from f .

Cross-Validated Likelihood for Choosing k

Choosing the Number of Clusters k

Consider that we t a set of nite mixture models with k components to D, where k ranges from 1 to kmax . Thus, we have an indexed set of estimated models, fk (xj ^ k ); 1 k kmax , where each fk (xj ^ k ) has been tted to data set D. The data log-likelihood for the kth model is de ned as N N Y X fk (xi j ^ k ) = log fk (xi j ^ k ): Lk (D) = log
i=1 i=1

Above we have assumed that k, the number of clusters, is known a priori. While there may be situations where k is known, one would often like to determine k from the data if possible. Prior work on automatically nding k can roughly be divided into three categories.

(3) Assume that the parameters for the kth mixture model were estimated by maximizing this likelihood as a function of k , keeping the data D xed (standard maximum likelihood estimation). We then get that Lk (D) is

a non-decreasing function of k since the increased exibility of more mixture components allows better t to the data (increased likelihood). Thus, Lk (D) can not directly provide any clue as to the true mixture structure in the data, if such structure exists1 . Imagine that we had a large test data set Dtest which is not used in tting any of the models. Let Lk (Dtest ) be the log-likelihood as de ned in Equation 3, where the models are t to the training data D but the likelihood is evaluated on Dtest . We can view this likelihood as a function of the \parameter" k, keeping all other parameters and D xed. Intuitively, this \test likelihood" should be a more useful estimator (than the training data likelihood) for comparing mixture models with di erent numbers of components. However, in practice, we can not a ord, or do not have available, a large independent test set such ^k as Dtest . Let Lcv be a cross-validation estimate of Lk (Dtest )|we discuss in the next section the particu^k ^k lars of how Lcv is calculated. What can Lcv tell us ^ k ) is to the true about how close the model fk (xj data-generating density f ? Following Silverman (1986, p.53) and Chow, Geman, and Wu (1983) , it can be shown under appropriate assumptions that Z f (x) ^k dx + C (4) E Lcv = f (x) log fk (xj ^ k ) where C is a constant independent of k and fk (xj ^ k ), and the expectation E is taken with respect to the true density f (x). The term in square brackets is the KullbackLeibler (K-L) information distance between f (x) and fk (xj ^ k ), namely I (f; fk ( ^ k )). I (f; fk ( ^ k )) is strictly positive unless f = fk ( ^ k ). Thus, the k which minimizes I (f; fk ( ^ k )) tells us which of the mixture models is closest to the true density f . From Equation 4, ^k Lcv is an approximately unbiased estimator (within a constant) of the expected value of the K-L distance ?I (f; fk ( ^ k )). Given that f (and I (f; fk ( ^ k ))) is un^k known, maximizing Lcv over k is a reasonable estimation strategy and is the approach adopted in this paper.

su er from high variance. v = 10 has been a popular choice in practice (e.g., the CART algorithm for decision tree classi cation). In Monte Carlo cross validation (MCCV) the data are partitioned M times into disjoint train and test subsets where the test subset is a fraction of the overall data (Burman 1989, Shao 1993). The key distinction between MCCV and vCV is that in MCCV the di erent test subsets are chosen randomly and need not be disjoint. Typically can be quite large, e.g., 0.5 or larger, and hundreds or thousands of runs (M ) can be averaged. In the regression context it was shown by Shao (1993) that keeping relatively large reduces estimation variability in the test data (compared to vCV methods). Intuitively, the MCCV estimates should be unbiased (being an average of M individually unbiased estimates) and have desirable variance properties: however, there are few theoretical results available on MCCV in general and none on MCCV in a likelihood estimation context. The algorithm operates as follows. The outer loop consists of M cross-validation runs over M randomlychosen train/test partitions. For each partition, k is varied from 1 to kmax and the EM algorithm is used to t the k components to the training data. The EM algorithm is initialized using a variant of the k-means algorithm, which is itself initialized randomly. To avoid local minima, the k-means algorithm is run t times (default value is t = 10) from di erent starting points and the highest likelihood solution used to begin the EM estimation. The EM estimation is constrained away from singular solutions in parameter space by limiting the diagonal elements of the component covariance matrices j to be greater than (default value is = 0:001 where is the standard deviation of the unclustered data in the relevant dimension). The EM algorithm iterates until the change in likelihood is less than (default value is = 10?6), or up to a prespeci ed maximum number of iterations (default is 30), whichever occurs rst. Keeping the maximum number of EM iterations small allows for quicker execution of the algorithm: the intuition is that since we are averaging multiple cross-validation runs, it is su cient that the EM estimates be somewhere near a peak in the likelihood surface|this assumption warrants further investigation. Each of the tted models with k components are then applied to the unseen data in the test partition, and the test-data log-likelihood (Equation 3) is calculated for each. As indicated earlier, this is repeated M times, and the M cross-validated estimates are aver^k aged for each k to arrive at Lcv ; 1 k kmax . Similarly the standard deviation over the M runs can be calculated for each k, indicating the variability of the likelihood estimates. ^k The data analyst can plot the Lcv as a function of k along with the standard deviations to see what the data

Speci cation of the MCCV Algorithm

A Monte Carlo Cross-Validated Clustering Algorithm Choosing a Particular Cross-Validation Method

There are several possible cross-validation methods ^k one could use to generate Lcv . v-fold cross validation (vCV) consists of partitioning the data into v disjoint subsets. v = 1 yields the well-known \leave-one-out" cross validated estimator, but this is well-known to

1 Traditionally this is the departure point for penalized likelihood and likelihood ratio testing methods.

says about the number of clusters. Another approach is to roughly calculate the posterior probabilities for each k, where one e ectively assumes equal priors on the values of k: ^ exp(Lcv ) p(kjD) Pkmax k ^ cv ; 1 k kmax : l=1 exp(Ll ) The distribution of p(kjD) is essential to interpreting the results in the following sense. If one of the p(kjD)'s is near 1, then there is strong evidence for that particular number of clusters. If the p(kjD)'s are more spread out, then the data are not able to resolve the cluster structure, although \bunching" about a particular k value may allow one to focus on a sub-range of k. It is not recommended that the procedure be implemented as a \black-box" where simply the maximum k value is reported. The complexity of the EM algorithm for xed k is O(kd2NE ) where d is the dimensionality of the data, and E denotes the average number of iterations of the EM algorithm. Thus, the overall computational complexity of the MCCV clustering algorithm 2 is O(Mkmax d2NE ), i.e., linear in the number of samples N if one assumes that E does not depend on N .

3

2

1

feature 2

0

?1

?2

?3 ?2

?1

0

1 feature 1

2

3

4

5

(a) 2-class data.
3 2

Experimental Results Overall Experimental Methodology

1

feature 2

0

The MCCV algorithm was evaluated on both simulated and real data sets. Unless stated otherwise, the algorithm was run with M = 20 (the number of runs) and = 0:5 (the fraction of data left out in each run). The value of M = 20 was chosen for pragmatic reasons to reduce simulation time (the MCCV procedure is currently coded in MATLAB which is not particularly e cient). The value of = 0:5 was based on some initial experimentation which suggested that keeping the cross-validation train and test partitions roughly the same size gave better results than the more \traditional" 90/10 type partitions. Other details of these experiments are omitted here due to lack of space. Three other methods were compared to MCCV: AutoClass v2.0 (from the authors at NASA Ames), vCV (with v = 10), and BIC (using the standard (qk =2) log N penalty term where qk is the number of parameters in the mixture model with k components). The v-CV and BIC methods used the same version of the EM algorithm as MCCV. The maximum number of classes for each of the algorithms (kmax ) was set to 8 or 15, depending on the true number of classes in the data. It is important to note that all of the algorithms have random components. The initialization of the EM algorithm (used by each of the clustering algorithms) for xed k is based on randomly choosing k initial cluster means. The cross-validation algorithms contain further randomness in their choice of particular partitions of the data. Finally, the simulated data sets can

?1

?2

?3 ?3

?2

?1

0 feature 1

1

2

3

(b) 3-class data.
1.2 1

0.8

feature 2

0.6

0.4

0.2

0

?0.2 ?1

?0.8

?0.6

?0.4

?0.2 0 feature 1

0.2

0.4

0.6

0.8

(c) 4-class data. Figure 1: 2-d scatterplots of simulated data.

be regenerated randomly according to the probability model. An ideal set of experiments would average over all of these sources of randomness. Thus, although the experiments in principle could be more extensive (for example, by averaging results over multiple simulated realizations of the simulated problems for a given N ) they nonetheless provide clear insight into the general behavior of the algorithms. Experiments were run on relatively small-sample, low-dimensional data sets (Figures 1 and 2). From a data mining viewpoint this may seem uninteresting. In fact, the opposite is true. Small sample sizes are the most challenging problems for methods which seek to extract structure from data (since the MCCV algorithm scales roughly linearly with sample size, scaling up to massive data sets does not pose any particular problems). The focus on low-dimensional problems was driven by a desire to evaluate the method on problems where the structure can easily be visualized, the availability of well-known data sets, and the use (in this paper) of full-covariance Gaussian models (which scale poorly with dimensionality from an estimation viewpoint). For all data sets the classes are roughly equiprobable. Finally due to space limitations we only summarize the experimental results obtained, namely, provide the value of k which maximizes the relevant criterion for each algorithm. Note that, as discussed in the previous section, this is not the recommended way to use the MCCV algorithm: rather the full posterior probabilities and variances for each k should be reported and interpreted by the user. Table 1 contains a brief summary of the experimental results on simulated data. Experiment 1 consisted of a \control" experiment: data from a single 2-dimensional Gaussian (with = I (the identity matrix)). BIC, AutoClass, and MCCV correctly determined the presence of only a single class. vCV on the other hand exhibited considerable variability and incorrectly detected multiple clusters. In general, across di erent experiments, the vCV method (with v=10) was found to be an unreliable estimator compared to the other methods. The second simulation problem consists of 2 Gaussian clusters in 2 dimensions, both with covariance matrices 1 = 2 = I and means 1 = (0; 0); 2 = (0; 3). There is considerable overlap of the clusters (Figure 1(a)) making this a non-trivial problem. MCCV nds evidence of only one cluster with N = 100, but for N = 600; 1200 it correctly nds both clusters. This conservative tendency of the MCCV algorithm (whereby it nds evidence to support fewer clusters given less data) is pleasing and was noted to occur across di erent data sets. BIC and AutoClass detected the same number of clusters as MCCV: vCV was consistently incorrect on this problem.

2.5

2

petal width [cm]

1.5

1

0.5

0 1

2

3

4 petal length [cm]

5

6

7

(a) 2d iris data.
800 700

600

500

insulin area

400

300

200

100

Details of Experiments on Simulated Data

0 0

200

400

600

800 1000 glucose area

1200

1400

1600

(b) 2d diabetes data.
1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.1

formant 2 (scaled to [0,1])

0.2

0.3

0.4 0.5 0.6 0.7 formant 1 (scaled to [0,1])

0.8

0.9

1

(c) Vowel data. Figure 2: 2-d scatterplots of real data.

Table 1: Experimental results on simulated data. Problem Sample Size BIC AC vCV MCCV Truth 1-Class 50 1 1 2 1 1 200 1 1 1 1 1 800 1 1 5 1 1 2-Class 100 1 1 4 1 2 600 2 2 3 2 2 1200 2 2 3 2 2 3-Class 100 3 3 4 3 3 600 3 3 3 3 3 1200 3 3 4 3 3 4-Class 100 2 3 5 3 4 500 3 4 5 4 4 1000 4 4 6 4 4 The 3-Class problem (Figure 1(b)) follows the simulated Gaussian structure (in two dimensions) used in Ban eld and Raftery (1993). Two of the clusters are centred at (0; 0) but are oriented in \orthogonal" directions. The third cluster overlaps the \tails" of the other two and is centred to the right. MCCV, BIC and AutoClass each correctly detected 3 clusters: once again, vCV was not reliable. The nal simulation problem (Figure 1(c)) contains 4 classes and is taken from Ripley (1994) where it was used in a supervised learning context (here, the original class labels were removed). vCV is again unreliable. Each of BIC, MCCV and AutoClass \zero-in" on the correct structure given enough data, with BIC appearing to require more data to nd the correct structure. ments have limited precision, somewhat invalidating the Gaussian assumption). Given these caveats, and the relatively small sample size, each of the methods are both providing useful insight into the data.

Diabetes Data Reaven and Miller (1979) analyzed

Real Data Sets

Below we discuss the application of MCCV (and the comparison methods) to several real data sets. Table 2 contains a brief summary of the results. Each of these data sets has a known classi cation: the clustering algorithms were run on the data with the class label information removed. Note that unlike the simulated examples, the number of classes in the original classied data set is not necessarily the \correct" answer for the clustering procedure, e.g., it is possible that the a particular class in the original data is best described by two or more \sub-clusters," or that the clusters are in fact non-Gaussian. Iris Data The classic \iris" data set contains 150 4-dimensional measurements of plants classi ed into 3 species. It is well known that 2 of the species are overlapped in the feature-space and the other is wellseparated from these 2 (Figure 2(a)). MCCV indicates 2 clusters with some evidence of 3. AutoClass found 4 clusters and BIC found 2 (the fact that vCV found 3 clusters is probably a uke). It is quite possible that the clusters are in fact non-Gaussian and, thus, do not match the clustering model (e.g., the measure-

3-dimensional plasma measurement data for 145 subjects who were clinically diagnosed into three groups: normal, chemically diabetic, or overtly diabetic. This data set has since been analyzed in the statistical clustering literature by Symons (1981) and Ban eld and Raftery (1993). When viewed in any of the 2dimensional projections along the measurement axes, the data are not separated into obvious groupings: however, some structure is discernible (Figure 2(b)). The MCCV algorithm detected 3 clusters in the data (as did vCV and AutoClass). BIC incorrectly detected 4 classes. It is encouraging that the MCCV algorithm found the same number of classes as that of the original clinical classi cation. We note that the \approximate weight of evidence" clustering criterion of Ban eld and Raftery (1993) (based on a Bayesian approximation) was maximized at k = 4 clusters and indicated evidence of between 3 to 6 clusters.

Speech Vowel Data Peterson and Barney (1952) measured the location of the rst and second prominent peaks (formants) in 671 estimated spectra from subjects speaking various vowel sounds. They classied the spectra into 10 di erent vowel sounds based on acoustic considerations. This data set has since been used in the neural network literature with the best cross-validated classi cation accuracies being around 80%. As can be seen in Figure 2(c) the classes are heavily overlapped. Thus, this is a relatively di cult problem for methods which automatically try to nd the correct number of clusters. AutoClass detected 5 clusters, while MCCV detected 7, with some evidence between 6 and 9 clusters. BIC completely underestimated the number of clusters at 2. Given the relatively

Table 2: Experimental results on non-simulated data. Problem Sample Size BIC AC vCV MCCV \Truth" Iris 150 2 4 3 2 3 Diabetes 145 4 3 3 3 3 Vowels 671 2 5 8 7 10 small sample size (one is tting each cluster using only roughly 30 sample points), the MCCV algorithm is doing well to indicate the possibility of a large number of clusters. The MCCV method performed roughly as well as AutoClass on the particular data sets used in this paper. The BIC method performed quite well, but overall was not as reliable as MCCV or AutoClass. vCV (with v=10) was found to be largely unreliable. Further experimentation on more complex problems may reveal some systematic di erences between the Bayesian (AutoClass) and cross-validation (MCCV) approaches, but both produced clear insights into the structure of the data sets used in the experiments in this paper. We note in passing that Chickering and Heckerman (1996) have investigated a problem which is equivalent to that addressed in this paper, except that the feature vector x is now discrete-valued and and the individual features are assumed independent of the (hidden) class variable. Chickering and Heckerman empirically evaluated the performance of AutoClass, BIC, and other approximations to the full Bayesian solution on a wide range of simulated problems. Their results include conclusions which are qualitatively similar to those reported here: namely that the AutoClass approximation to the full Bayesian solution outperforms BIC in general and that BIC tends to be overly conservative in terms of the number of components it prefers. The theoretical basis of the MCCV algorithm warrants further investigation. For example, MCCV is somewhat similar to the bootstrap method. A useful result would be a characterization (under appropriate assumptions) of the basic bias-variance properties of the MCCV likelihood estimate (in the mixture context) as a function of the leave-out fraction , the number of cross-validation runs M , the sample size N , and some measure of the problem complexity. Prescriptive results for choosing automatically (as developed in Shao (1993) in a particular regression context) would be useful. For example, it would be useful to justify in theory the apparent practical utility of = 0:5. On the practical front, clearly there is room for improvement over the basic algorithm described in this paper. The probabilistic cluster models can easily be extended beyond the full-covariance model to incorporate, for example, the geometric shape and Poisson \outlier" models of Ban eld and Raftery (1993) and Celeux and Govaert (1995), and the discrete variable models in AutoClass. Diagnostic tests for detecting non-Gaussianity could also easily be included (cf. McLachlan and Basford (1988), Section 2.5) and would be a useful practical safeguard. Some obvious improvements could also be made to the search strategy. Instead of \blindly" searching over each possible value of k from 1 to kmax a more intelligent search could be carried out which \zeros-in" on the range of k which has appreciable posterior probability mass (the current implementation of the AutoClass algorithm includes such a search algorithm). Data-driven methods for automatically selecting the leave-out fraction method are also a possibility, or possibly averaging results over multiple values of . When the data are few relative to the number of clusters present, it is possible for the cross-validation partitioning to produce partitions where no data from a particular cluster is present in the training partition. This will bias the estimate towards lower k values (since the more fractured the data becomes, the more likely this \pathology" is to occur). A possible solution is some form of data-driven strati ed cross-validation (Kohavi (1995) contains a supervised learning implementation of this idea). Both the EM and MCCV techniques are amenable to very e cient parallel implementations. For large sample sizes N , it is straightforward to assign 1=p of the data to p processors working in parallel which communicate via a central processor. For large numbers of cross-validation runs M , each of p processors can independently run M=p runs. Finally we note that our attention was initially drawn to this problem in a time-series clustering context using hidden Markov models. In this context, the general MCCV methodology still applies but because of sample dependence the cross-validation partitioning strategy must be modi ed|this is currently under development. The MCCV approach to mixtures described here can also be applied to supervised learning with mixtures: the MCCV procedure provides an automatic method for determining how many components to use to model each class. Other extensions to learning of graphical models (Bayesian networks) and image segmentation are also possible. MCCV clustering appears to be a useful idea for determining cluster structure in a probabilistic clustering context. Experimental results indicate that

Discussion

Conclusions

the method has signi cant practical potential. The method complements Bayesian solutions by being simpler to implement and conceptually easier to extend to more complex clustering models than Gaussian mixtures. The author would like to thank Alex Gray for assistance in using the AutoClass software. The research described in this paper was carried out by the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration. Ban eld, J. D., and Raftery, A. E. 1993. Modelbased Gaussian and non-Gaussian clustering,' Biometrics, 49, 803{821. Burman, P. 1989 A comparative study of ordinary cross-validation, v-fold cross-validation, and the repeated learning-testing methods,' Biometrika, 76(3), 503{514. Celeux, G., and Govaert, G. 1995. Gaussian parsimonious clustering models,' Pattern Recognition, 28(5), 781{793. Cheeseman, P. and Stutz. J. 1996. Bayesian classi cation (AutoClass): theory and results,' in Advances in Knowledge Discovery and Data Mining, U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy (eds.), Cambridge, MA: AAAI/MIT Press, pp. 153{180. Chickering, D. M., and Heckerman, D. 1996. E cient approximations for the marginal likelihood of incomplete data given a Bayesian network,' MSRTR-96-08 Technical Report, Microsoft Research, Redmond, WA. Chow, Y. S., Geman, S. and Wu, L. D. 1983. Consistent cross-validated density estimation,' The Annals of Statistics, 11(1), 25{38. Diebolt, J. and Robert, C. P. 1994. Bayesian estimation of nite mixture distributions,' J. R. Stat. Soc. B, 56, 363{375. Gelman, A., J. B. Carlin, H. S. Stern, D. B. Rubin. 1995. Bayesian Data Analysis, London, UK: Chapman and Hall. Jain, A. K., and R. C. Dubes. 1988. Algorithms for Clustering Data, Englewood Cli s, NJ: Prentice Hall. Kohavi, R. 1995. A study of cross-validation and bootstrap for accuracy estimation and model selection,' Proc. Int. Joint. Conf. AI, Montreal. McLachlan, G. J. and K. E. Basford. 1988. Mixture Models: Inference and Applications to Clustering, New York: Marcel Dekker.

Acknowledgments

References

Peterson, G. and Barney, H. 1952. Control methods used in the study of vowels,' . J. Acoust. Soc. Am., 24, 175{184. Reaven, G. M., and Miller, R. G. 1979. An attempt to de ne the nature of chemical diabetes using a multi-dimensional analysis,' Diabetologia, 16, 17{24. Ripley, B. D. 1994. Neural networks and related methods for classi cation (with discussion),' J. Roy. Stat. Soc. B, 56, 409{456. Sclove, S. C. 1983. Application of the conditional population mixture model to image segmentation,' IEEE Trans. Patt. Anal. Mach. Intell., PAMI-5, 428{433. Shao, J. 1993. Linear model selection by crossvalidation,' J. Am. Stat. Assoc., 88(422), 486{494. Silverman, B. W. 1986. Density Estimation for Statistics and Data Analysis, Chapman and Hall. Symons, M. 1981. Clustering criteria and multivariate normal mixtures,' Biometrics, 37, 35{43. Titterington, D. M., A. F. M. Smith, U. E. Makov. 1985. Statistical Analysis of Finite Mixture Distributions, Chichester, UK: John Wiley and Sons.

ÔÞÖúÉÌÁ´½Ó
Ïà¹ØÎÄÕÂ:
COMP5318 Knowledge Discovery and Data Mining_2011 S...
COMP5318 Knowledge Discovery and Data Mining_2011 Semester 1_tutorialweek11_µçÄÔ»ù´¡ÖªÊ¶_IT/¼ÆËã»ú_×¨Òµ×ÊÁÏ¡£University of Sydney_COMP5318 Knowledge ...
COMP5318 Knowledge Discovery and Data Mining_2011 S...
COMP5318 Knowledge Discovery and Data Mining_2011 Semester 1_tutorialweek9_µçÄÔ»ù´¡ÖªÊ¶_IT/¼ÆËã»ú_×¨Òµ×ÊÁÏ¡£University of Sydney_COMP5318 Knowledge Discovery...
COMP5318 Knowledge Discovery and Data Mining_2011 S...
COMP5318 Knowledge Discovery and Data Mining_2011 Semester 1_tutorialweek2_µçÄÔ»ù´¡ÖªÊ¶_IT/¼ÆËã»ú_×¨Òµ×ÊÁÏ¡£University of Sydney_COMP5318 Knowledge Discovery...
COMP5318 Knowledge Discovery and Data Mining_2011 S...
COMP5318 Knowledge Discovery and Data Mining_2011 Semester 1_tutorialweek6_µçÄÔ»ù´¡ÖªÊ¶_IT/¼ÆËã»ú_×¨Òµ×ÊÁÏ¡£University of Sydney_COMP5318 Knowledge Discovery...
COMP5318 Knowledge Discovery and Data Mining_2011 S...
COMP5318 Knowledge Discovery and Data Mining_2011 Semester 1_tutorialweek4_µçÄÔ»ù´¡ÖªÊ¶_IT/¼ÆËã»ú_×¨Òµ×ÊÁÏ¡£University of Sydney_COMP5318 Knowledge Discovery...
COMP5318 Knowledge Discovery and Data Mining_2011 S...
COMP5318 Knowledge Discovery and Data Mining_2011 Semester 1_tutorialweek3_µçÄÔ»ù´¡ÖªÊ¶_IT/¼ÆËã»ú_×¨Òµ×ÊÁÏ¡£University of Sydney_COMP5318 Knowledge Discovery...
Êý¾ÝÍÚ¾ò ×ÊÔ´
Knowledge Discovery and Data Mining http://www.acm.org/sigkdd/ Data Mining News http://www.idagroup.com/ NCDM National Center For Data Mining http:...
²Î¿¼ÎÄÏ×-new
308¡«317 185 22 Williklosgen. Knowledge Discovery in Database and Data Mining. 9th International Symposium on Foundations of Intelligent Systems, 1996, 623...
SCI,EI¼ìË÷¼ÇÂ¼
(9th Pacific-Asia International Conference on Knowledge Discovery and Data Mining) http://www.jaist.ac.jp/PAKDD-05/PAKDD2005-C MT.html ISNN 2005 (The...
KDD Knowledge Discovery in Databases
Fayyad,Piatetsky-Shapiro ºÍ Smyth ÔÚ 1996 ÄêºÏ×÷·¢²¼µÄÂÛÎÄ<From Data Mining to knowledge discovery>ÖÐ×Ü½á³öÁË KDD °üº¬µÄ 5 ¸ö×î»ù±¾²½Öè(ÈçÍ¼). 1: ...

format: plain


text:
# Minimum beam dimension for specific max stress

1. Oct 12, 2012

### vesu

1. The problem statement, all variables and given/known data
A beam (note: part of a truss, I chose to use the beam in the truss with the most force and length for my calculations, which I assume is the correct thing to do) of length $6m$ with a force of $9N$ is being constructed out of a material with a Young's Modulus of $E = 70 \times 10^9 N/m^2$ and it's ultimate stress is $σ_{u} = 110 \times 10^6 N/m^2$. What is the minimum dimension of the square beam (i.e. cross-section) so that the structure will not fail?

2. Relevant equations
Spring constant of beam: $k_{beam} = \frac{A \times E}{L}$
Hooke's Law: $F = k \times ΔL$

$E = \frac{σ}{ε} = \frac{F/A}{ΔL/L}$

3. The attempt at a solution
I'm pretty lost on what to do here, we barely covered this stuff in lectures. My first thought was simply letting $σ = F/A$ but that doesn't make much sense because surely length is a factor and that method doesn't use the young's modulus at all. My second thought was to substitute $k_{beam}$ into the hooke's law equation, giving $F = \frac{A \times E}{L} \times ΔL$ => $9 = \frac{A \times 70 \times 10^9}{6}$ but I'm not sure where this gets me.

P.S. Sorry if I didn't explain the question very well, I paraphrased a bit because the original question is part of a series of questions and doesn't make a lot of sense on it's own.

2. Oct 12, 2012

### cake of doom

Just so its clear in my mind: we have a beam spanning 6m with a force of 9N? do you have a sketch of what you are doing? Or perhaps scan in the question page. Just so we're all on the same page lol

3. Oct 12, 2012

### vesu

We have a truss with seven beams in total, this part of the question is asking for the minimum area of the square cross-section of an individual beam so that the structure will not fail (i.e. so that any individual beam will not fail). There is one beam that has the greatest length and force (6m and 9N) so I am assuming that is the one that should be used for calculations as it will be under the most stress (I think?).

I think that the fact that the beam is part of a truss structure is largely irrelevant to this part of the question but I may be approaching this the wrong way.

4. Oct 12, 2012

### PhanthomJay

Well, it is relevant in that the 9N force is an axial force directed along the longitudinal axis of the member.
Please check the units of the force...9 Newtons is barely any force at all.
You must determine whether the member is in compression or tension.
If in tension, then your F/A equation applies; if in compression, you must not only check F/A, but also buckling allowables. Length and modulus E is important when condsidering compressive loads, in addition to the properties of the cross section. For the tension case, typically you just need to know the area.
You dont have to get into strain or stiffness calculations if you are not looking for deformations.

5. Oct 12, 2012

### vesu

Hi, sorry the beam is in compression I forgot to mention that. It is definitely 9N.

6. Oct 12, 2012

### PhanthomJay

Elements of a truss are typically not called 'beams', especially in this case where the loading is so slight that you have very small 'members'.
Anyway, compare the compressive stress F/A versus the Euler buckling stress to see which controls the member size required.

7. Oct 13, 2012

### vesu

Woops sorry, the wording in the question seems to alternate between using "beam" and "member" to describe them. I'll give that a shot, thanks! Somehow I completely missed that when looking through my lecture notes.

8. Oct 13, 2012

### PhanthomJay

OK and please check again on the value of the force which you state is 9N. Are you assuming the members have no weight? The weight alone is probably more than that. Where does that number come from?

9. Oct 13, 2012

### vesu

They have given us the value of 9N. This is a very introductory class so I think they are just trying to teach us the basics with examples that are not necessarily practical or realistically possible. The weight of the members hasn't been mentioned at any point in anything we've covered involving trusses. Example questions involving calculating the force in a member done in our lectures have had similarly low forces (typically 2-10N) as the answer.

10. Oct 15, 2012

### vesu

Thanks PhanthomJay, I figured it and the rest of the questions out. Also my apologies, after all my stubbornness it was actually 9kN. I don't know how I managed to repeatedly misread that every time.

11. Oct 15, 2012

Ok, good!